線性方程組的直接法.ppt

1,第三章解線性方程組的直接方法1引言2高斯消去法3選主元素的高斯消去法4矩陣的三角分解5解三對角線方程組的追趕法6解對稱正定矩陣方程組的平方根法,2,1引言,學(xué)習(xí)線性方程組數(shù)值解法的必要性科學(xué)計(jì)算中經(jīng)常遇到線性方程組求解問題如電路分析、分子結(jié)構(gòu)、測量學(xué)、運(yùn)籌學(xué)、流體力學(xué)、數(shù)值逼近及微分方程的數(shù)值解法等當(dāng)線性方程組的階數(shù)較大時(shí)，人工求解已不可能。當(dāng)求解方法不得當(dāng)時(shí)，即使計(jì)算機(jī)求解都很難實(shí)現(xiàn)。對20階的線性方程組，用Cramer法則求解，乘除法的運(yùn)算次數(shù)達(dá)到9.71020，若用每秒鐘一億次的計(jì)算機(jī)計(jì)算也要30萬年；而用Gauss消去法求解，則只需乘除法次數(shù)為3060次，不需1秒鐘就可計(jì)算出來。線性方程組求解方法的分類直接法、間接法,3,矩陣的特征值和譜半徑,4,特征值的性質(zhì)及特征多項(xiàng)式,特征值的有關(guān)性質(zhì)AT和A具有相同的特征向量及特征值；若A非奇異，則A1與A的特征值互為倒數(shù)，特征向量相同；相似矩陣具有相同的特征值。特征多項(xiàng)式,例題：P.22例3.1求矩陣的特征值及譜半徑,5,對稱正定矩陣,定義性質(zhì)非奇異，且其逆矩陣也對稱正定；所有特征值大于零；所有對角元也大于零；所有順序主子式都大于零。,6,初等矩陣,定義性質(zhì),7,初等置換矩陣,初等置換矩陣的性質(zhì)（1）是對稱矩陣；（2）是正交矩陣；（3）行列式為1；（4）左乘矩陣A相當(dāng)于將A的第i，j行互換，右乘A相當(dāng)于將A的第i,j列互換。,8,初等下三角陣（Gauss變換矩陣）,定義：,性質(zhì)：,9,Household變換（初等反射矩陣）,定義性質(zhì),10,2高斯消去法高斯消去法是一個(gè)古老的求解線性方程組的方法，但由它改進(jìn)得到的選主元的高斯消去法則是目前計(jì)算機(jī)上常用的解低階稠密矩陣方程組的有效方法。例1用高斯消去法解方程組解第1步：將方程（2.1）乘上（-3/2）加到方程（2.2）將方程（2.1）乘上（-1/2）加到方程（2.3）則得到與原方程等價(jià)的方程組,（2.1）,（2.3）,（2.2）,11,其中方程（2.4），（2.5）已消去了未知數(shù)。第2步：方程（2.4）乘上2加到方程（2.5），消去（2.5）式中未知數(shù)，得到等價(jià)的三角形方程組由上述方程組，用回代的方法，即可求得原方程組的解。,（2.4）,（2.5）,12,若用矩陣來描述消去法的約化過程，即為這種求解過程，稱為具有回代的高斯消去法。從上例看出，用高斯法解方程組的基本思想是用矩陣的初等變換將系數(shù)矩陣約化為具有簡單形式的矩陣（上三角矩陣，單位矩陣等），從而容易求解。下面討論求解一般線形方程組的高斯消去法，設(shè)有n個(gè)未知數(shù)的線性方程組：,13,引進(jìn)記號(hào),(2.7),(2.7)可用矩陣形式表示,(2.8),14,為了討論方便，記假設(shè)為非奇異矩陣（即設(shè))。第1步（k=1）：設(shè)計(jì)算乘數(shù)用乘上（2.7）第一個(gè)方程，加到第i個(gè)中方程上去，即施行行初等變換：,15,(2.9),消去第2到第n個(gè)方程的未知數(shù)，得到（2.7）的等價(jià)方程組,其中（2.9）式中方框內(nèi)元素為這一步需要計(jì)算的元素，計(jì)算公式為：,記為,16,第k步：繼續(xù)上述消去過程，設(shè)第1步至第k-1步計(jì)算已經(jīng)完成，得到與原方程組等價(jià)的方程組。,（2.10）,17,記為,現(xiàn)進(jìn)行第k步消元計(jì)算，設(shè)，計(jì)算乘數(shù),用乘（2.10）的第k個(gè)方程加到第i個(gè)方程消去（2.10）中第i個(gè)方程的未知數(shù)得到原方程組的等價(jià)方程組。,18,(2.11),簡記為,其中元素計(jì)算公式為：,19,重復(fù)上述約化過程，即且設(shè)，共完成n-1步消元計(jì)算，得到與原方程組（2.7）等價(jià)的三角形方程組,(2.12),(2.13),20,用回代法，即可求得（2.13）的解，計(jì)算公式為：,（2.14）,元素稱為約化的主元素。將（2.7）約化為（2.13）的過程稱為消元過程；（2.13）求解過程（2.14）稱為回代過程，由消元過程和回代過程求解線性方程組的方法稱為高斯消去法。,21,定理1（高斯消去法）設(shè)其中如果約化的主元素則可通過高斯消去法（不進(jìn)行交換兩行的初等變換）將方程組約化為三角形矩陣方程組（2.13），且消元和求解公式為：1.消元計(jì)算,定理證明詳見課本P.26定理2.2,22,2.回代計(jì)算,當(dāng)A為非奇異矩陣時(shí)，也可能有某但在第k列存在元素,23,于是可能通過交換（A，b）的第k行和第行將調(diào)到位置，然后再進(jìn)行消元計(jì)算。于是，在A為非奇異矩陣時(shí)，只要引進(jìn)行交換，則高斯消去法可將原線性方程組約化為三角形方程組（2.13），且通過回代法即可求得方程組的解。高斯消去法計(jì)算量:（1）消元計(jì)算：第k步1.計(jì)算乘數(shù)：需要作（n-k）次除法運(yùn)算；2.消元：需作次乘法運(yùn)算；3.計(jì)算：需作（n-k）次乘法運(yùn)算；于是，完成全部消元計(jì)算共需作乘除運(yùn)算的次數(shù)為s：,24,（2）回代計(jì)算：共需要作n(n+1)/2次乘除運(yùn)算。于是，用高斯消去法解的計(jì)算量為共需作,（2.15）,次乘除運(yùn)算。,25,下面比較用高斯消去法和用克萊姆（Cramer）法則解20階方程組的計(jì)算量。,如果計(jì)算在每秒作10億次乘除法運(yùn)算的計(jì)算機(jī)上進(jìn)行，那么用高斯消去法解20階方程組約需要0.000003秒時(shí)間即可完成，而用克萊姆法則大約需小時(shí)完成（大約相當(dāng)于年）。由此可知克萊姆法則完全不適用在計(jì)算機(jī)上求解高維方程組。,26,在計(jì)算機(jī)上用高斯消去法解低階稠密矩陣線性方程組時(shí)要注意幾點(diǎn):(1)要用一個(gè)二維數(shù)組A(n,n)存放系數(shù)矩陣A的元素，用一維數(shù)組b(n)存放常數(shù)項(xiàng)b向量；(2)需要輸入的數(shù)據(jù)：A，b，n(3)約化的中間結(jié)果元素沖掉A元素，沖掉b，乘數(shù)沖掉。,(4)在高斯消去法中一般要引進(jìn)行交換；如果不存在使,要輸出方程沒有唯一解的信息。,27,例題：用Gauss消去法解方程組并求其系數(shù)矩陣行列式的值。,28,消去法與三角分解,Guass消元的過程從矩陣變換角度出發(fā)，實(shí)質(zhì)上是進(jìn)行了(n-1)次Gauss變換，即,29,3選主元素的高斯消去法用高斯消去法解時(shí)，其中設(shè)A為非奇異矩陣，可能出現(xiàn)情況，這時(shí)必須進(jìn)行帶行交換的高斯消去法。但在實(shí)際計(jì)算中即使但其絕對值很小時(shí)，用作除數(shù)，會(huì)導(dǎo)致中間結(jié)果矩陣元素?cái)?shù)量級(jí)嚴(yán)重增長和舍入誤差的擴(kuò)散,使得最后的計(jì)算結(jié)果不可靠。例2設(shè)有方程組,30,解精確解為方法1：用高斯消去法求解(用具有舍入的6位浮點(diǎn)數(shù)進(jìn)行運(yùn)算),回代得到計(jì)算解。與精確解比較,這是一個(gè)很壞的結(jié)果。,31,回代求解。對于用具有舍入的6位浮點(diǎn)數(shù)進(jìn)行運(yùn)算，這是一個(gè)很好的計(jì)算結(jié)果。方法1計(jì)算失敗的原因，是用了一個(gè)絕對值很小的數(shù)作除數(shù)，乘數(shù)很大，引起約化中間結(jié)果數(shù)量很嚴(yán)重增長，再舍入就使得結(jié)果不可靠了。,方法2用具有行交換的高斯消去法(避免小主元)。,32,在采用高斯消去法解方程組時(shí)，小主元可能導(dǎo)致計(jì)算失敗，故在消去法中應(yīng)避免采用絕對值很小的主元素。對一般方程組，需要引進(jìn)選主元的技巧，即在高斯消去法的每一步應(yīng)該選取系數(shù)矩陣或消元后的低階矩陣中選取絕對值最大的元素作為主元素，保持乘數(shù)以便減少計(jì)算過程中舍入誤差對計(jì)算解的影響；對同一個(gè)數(shù)值問題，用不同的計(jì)算方法，得到的結(jié)果的精度大不一樣，一個(gè)計(jì)算方法，如果用此方法的計(jì)算過程中舍入誤差得到控制，對計(jì)算結(jié)果影響較小，稱此方法為數(shù)值穩(wěn)定的；如果用此計(jì)算方法的計(jì)算過程中舍入誤差增長迅速，計(jì)算結(jié)果受舍入誤差影響較大，稱此方法為數(shù)值不穩(wěn)定。解數(shù)值問題時(shí)，應(yīng)選擇和使用數(shù)值穩(wěn)定的計(jì)算方法，否則，如果使用數(shù)值不穩(wěn)定的計(jì)算方法去解數(shù)值計(jì)算問題，就可能導(dǎo)致計(jì)算失敗。,33,3.1完全主元素消去法設(shè)有線性方程組其中A為非奇異矩陣。方程組的增廣矩陣為,第1步（k=1）:首先在A中選主元素,即選擇，使,34,再交換A，b的第1行與第行元素，交換A的第1列與第列元素(相當(dāng)于交換未知數(shù)與)，將調(diào)到(1，1)位置(交換后為簡單起見增廣陣仍記為A，b，其元素仍記為)然后，進(jìn)行消元計(jì)算。,第k步：繼續(xù)上述過程，設(shè)已完成第1步到第k-1步計(jì)算，A,b約化為下述形式（仍記元素為為元素為）：,35,第k步選主元區(qū)域,對于做到（3）(1)選主元素：選取使,36,（2）如果；則交換A,b第k行與第行元素，若，則交換A的第k列與第列元素。（3）消元計(jì)算（4）回代求解。經(jīng)過上面的過程，即從第1步到n-1步完成選主元，交換兩行，交換兩列，消元計(jì)算，原方程組約化為,37,其中為未知數(shù)調(diào)換后的次序?；卮蠼?3.2列主元素消去法完全主元消去法是解低階稠密矩陣方程組的有效方法，但完全主元素方法在選主元時(shí)要花費(fèi)一定的計(jì)算時(shí)間；引入一種在實(shí)際計(jì)算中常用的部分選主元（列主元）消去法。列主元消去法即是每次選主元時(shí)，僅依次按列選取絕對值最大的元素作為主元素，且僅交換兩行，再進(jìn)行消元計(jì)算。,38,第k步選主元區(qū)域,設(shè)列主元素消去法已經(jīng)完成第1步到第k-1步的按列選主元，交換兩行，消元計(jì)算得到與原方程組等價(jià)的方程組,39,第k步計(jì)算如下：對于做到（4）（1）按列選主元：即確定使（2），則A為奇異陣，停止計(jì)算。（3），則交換A,b第與第k行元素。（4）消元計(jì)算：,40,（5）回代計(jì)算：,計(jì)算解在常數(shù)項(xiàng)內(nèi)得到。例2的方法2就是列主元消去法。例3用列主元素消去法解方程組,41,解精確解為（舍入值）：,42,回代即得到計(jì)算解本例是用具有舍入的4位浮點(diǎn)數(shù)進(jìn)行運(yùn)算，所得到的計(jì)算解還是比較準(zhǔn)確的。完全主元素消去法框圖（圖61）,43,圖6-1,完全主元高斯消去法方法框圖,44,圖6-2,列主元高斯消去法方法框圖,45,圖6-3,不選主元高斯消去法方法框圖,46,用完全主元素法解，可用一整型數(shù)組開始記錄未知數(shù)次序即，最后記錄調(diào)整后未知數(shù)的足標(biāo)。系數(shù)矩陣A存放在二維數(shù)組內(nèi)，常數(shù)項(xiàng)b存放在內(nèi)，解存放在數(shù)組內(nèi)。,47,4矩陣的三角分解現(xiàn)用矩陣?yán)碚搧硌芯扛咚瓜シ?，設(shè)約化主元素由于對A施行行的初等變換相當(dāng)于用初等矩陣左乘于A，高斯消去法第1步：對應(yīng)有其中,一、利用Gauss消元法實(shí)現(xiàn)矩陣的三角分解,48,第k步消元過程：對應(yīng)有其中,k列,(4.1),49,利用遞推公式（4.1）,則有,k列,(4.2),50,由（4.2）式得到,(4.3),其中,51,L為由乘數(shù)構(gòu)成的單位下三角陣，U為上三角陣，（4.3）式表明,用矩陣?yán)碚搧矸治龈咚瓜シ?得到一個(gè)重要結(jié)果,即在條件下,高斯消去法實(shí)質(zhì)上是將A分解為兩個(gè)三角矩陣的乘積A=LU。二、矩陣三角分解實(shí)現(xiàn)的條件顯然，由本章高斯消去法及行列式性質(zhì)知，如果,則有,52,反之，可用歸納法證明：如果A的順序主子式則總結(jié)上述討論，得到下述重要定理。,其中,53,定理2（矩陣的三角分解）設(shè)，如果A的順序主子式則A可分解為一個(gè)單位下三角陣與一個(gè)上三角陣的乘積，即且分解是唯一的。證明僅就來證明唯一性。設(shè)有其中為下三角角陣，為上三角陣。,（4.4）,54,上式右邊為上三角陣，左邊為單位下三角陣，故應(yīng)為單位陣。即,由假設(shè)知存在，于是從（4.4）可得,稱矩陣的三角分解為杜利特爾（Doolittle)分解。其中,55,在定理2條件下，同樣可有三角分解其中L為下三角陣,U為單位上三角陣。稱矩陣的這種分解為克勞特（Crout)分解。例4由例1可得到A的三角分解,設(shè)有方程組。如果實(shí)現(xiàn)了,則求解問題化為：,56,求解兩個(gè)三角形方程組是容易的。如果A為非奇異矩陣，則由列主元消去法知A通過行交換后可實(shí)現(xiàn)三角分解，即存有置換陣P使其中L為單位下三角陣，U為上三角陣。,即,57,三.矩陣的直接三角分解法當(dāng)矩陣A非奇異且順序主子式，則A可做LU分解，即A=LU.這時(shí)方程組Ax=b可以轉(zhuǎn)化為求解LUx=b，等價(jià)于以下兩個(gè)三角形方程組Lyb，及Uxy.現(xiàn)在通過矩陣乘法直接求得L及U的元素。對比兩邊元素，直接可得,58,若己經(jīng)求得U的第r-1行及L的第r-1列，則由矩陣乘法可得即從而可以求得U的第r行元素。L的第r列元素可由若,可得,59,求解三角形方程組的算法：對下三角方程組Ly=b,有對上三角方程組Ux=y,有,60,例5利用直接三角分解法求下列方程組的解,解法：將A進(jìn)行三角分解,解方程組Ly=b，得y1=1，y2=-1，y3=4解方程組Ux=y，得x1=-1/2,x2=1,x3=0.,61,5解三對角方程組的追趕法在一些實(shí)際問題中，如用三次樣條函數(shù)的插值問題，用差分解二階線形常微分方程邊值問題等，最后都導(dǎo)致解三對角方程組即,（5.1),62,其中A滿足條件,（5.2),對于具有條件（5.2)的方程組(5.1),可用下述的追趕法求解。追趕法具有計(jì)算量少，方法簡單，算法穩(wěn)定等特點(diǎn)。定理3設(shè)三對角方程組，且A滿足條件(5.2)，則A為非奇異矩陣。證明用歸納法證明，顯然，對n=2時(shí)有,63,現(xiàn)設(shè)定理對n-1階滿足條件（5.2)的三對角陣成立，求證對滿足條件(5.2)的n階三對角陣定理亦成立。因，消去法執(zhí)行一步后得,顯然,64,其中,于是由歸納法假設(shè)，則有,65,定理4設(shè)，其中A為滿足條件（5.2）的三對角陣，則A的所有順序主子式都不為零，即,故,證明由于A是滿足（5.2）的n陣三對角陣，因此，A的任一個(gè)順序主子陣亦是滿足（5.2）的三對角陣，由定理3，則有：,66,即,于是，由矩陣的三角分解定理，則有,67,由矩陣乘法，可得計(jì)算待定系數(shù)的計(jì)算公式，即,68,于是，得到解（5.1)的追趕法公式：(1)分解計(jì)算公式A=LU,(2)求解的遞推公式,69,(3)求解的遞推公式,將計(jì)算的過程稱為追的過程,計(jì)算方程組解的過程稱為趕的過程.追趕法解僅需要5n-4次乘除運(yùn)算。只需要用3個(gè)一維數(shù)組分別存貯A的系數(shù)且還需要用三個(gè)一維數(shù)組保存計(jì)算的中間結(jié)果,70,例5用追趕法解方程組,解(1)計(jì)算(2)計(jì)算(3)求解計(jì)算,71,6解對稱正定方程組的平方根法一、引言在工程技術(shù)問題中,例如用有限元方法解結(jié)構(gòu)力學(xué)中問題時(shí),常常需要求解具有對稱正定矩陣方程組,對于這種具有特殊性質(zhì)系數(shù)矩陣,利用矩陣的三角分解法求解就得到解對稱正定矩陣方程組的平方根法，這是一種解對稱正定矩陣方程組的有效方法。二、對稱正定矩陣設(shè)有方程組,(6.1),其中,若A滿足下述條件：,72,（1）A對稱：即（2）對任意非零向量有則稱A為對稱正定矩陣。對稱正定矩陣A具有性質(zhì)：a.設(shè)A為對稱正定陣，則A的順序主子式都大于零，即,b.A的特征值滿足：,73,三、平方根法由設(shè)A為對稱正定矩陣，則A有三角分解,(6.2),其中,74,75,由設(shè),于是為單位下三角陣，為上角陣，由矩陣三角分解的唯一性，則，從而對稱正定矩陣A有唯一分解式由(6.2)式可知,(6.3),又因?yàn)?，?76,代入（6.3），則有,于是，對角陣D還可分解,其中為下三角陣。,77,定理5（對稱正定陣的三角分解）設(shè)A為n階對稱正定矩陣，則有三角分解（且唯一）：（1），其中L為單位下三角陣，D為對角陣，或（2），其中L為下三角陣且當(dāng)限定L的對角元素為正時(shí)這種分解是唯一的。這種矩陣分解稱為喬來斯金（Cholesky）分解。分解計(jì)算的遞推公式及求解公式：,78,設(shè)有，其中為對稱正定陣，于是有三角分解,其中,79,由此得解對稱正定矩陣方程組的平方根法計(jì)算公式：,由矩陣乘法，則有L的第一列元素為,同理，可確定L的第j列元素,80,（一）分解計(jì)算,（1）,（2）對于,（二）求解計(jì)算（3）求解,81,（4）求解,平方根法僅需計(jì)算L，計(jì)算量約為次乘除法運(yùn)算，大約為一般高斯消去法計(jì)算量的一半。,82,由分解公式有,（6.4）,（6.4）說明解的平方根法所得的中間數(shù)據(jù)是有界的，即數(shù)量級(jí)不會(huì)增長。因此，雖然解對稱正定矩陣方程組的平方根法沒有進(jìn)行選主元素，但平方根法是數(shù)值穩(wěn)定的。因?yàn)锳為對稱矩陣，因此，電算時(shí)只需用一維數(shù)組存貯A的對角線以下元素，即,83,存區(qū),用一維數(shù)組按行存貯：,84,解精確解,（1）分解計(jì)算A=LLT,且矩陣A的元素在一維數(shù)組中表示為：,計(jì)算得到的L的元素存放在A的對應(yīng)位置。例6用平方根法解方程組,85,（2）求解兩個(gè)三角形方程組，求解得到求解，即得的解,86,四、改進(jìn)的平方根法,對稱正定矩陣A可分解為A=LDLT其中,87,改進(jìn)平方根法求解對稱正定方程組,