4線性方程組的直接解法

1、4 線性方程組的直接解法線性方程組的直接解法 （ Direct methods of Linear equations ） n 本章主要內(nèi)容本章主要內(nèi)容n 4.1 高斯消去法高斯消去法 n 4.2 三角分解法三角分解法 n 4.3 直接法的誤差分析直接法的誤差分析n 4.4 近似解的精度改善近似解的精度改善n 重點：重點：LU分解分解n 難點：追趕法、平方根法難點：追趕法、平方根法 直接法直接法（第（第4章）章）思想思想：對系數(shù)矩陣進(jìn)行分解分解、變換變換，經(jīng)有限次算術(shù)運算，求出精確解特點特點：準(zhǔn)確、可靠、無方法誤差無方法誤差適用適用：中、小規(guī)模問題，尤其是稠密系數(shù)矩陣問題問題：舍入誤差對病態(tài)方

2、程組的影響，算法可能不穩(wěn)定 常見的線性方程組常見的線性方程組數(shù)值方法分類數(shù)值方法分類 平方根分解法喬立斯基三對角方程組的追趕法分解克勞拉分解杜利特里分解分解法消去法主元消去法消去法消去法直接法迭代法迭代法迭代法迭代法)()()(CholesyCroutDoolittleLUJordanGaussGaussGaussSORSeidelGaussJacobi4.1 消去法消去法 4.1.1 高斯消去法高斯消去法用高斯消去法求解線性方程組，分為消元過程消元過程和回代過程?；卮^程。 消元過程消元過程將原始方程組 記作 。經(jīng)過n-1步消元后，得到Axb(1)(1)A xb記作( )( )nnAxb(1

3、)(1)(1)(1)1111121(2)(2)(2)22222( )( )nnnnnnnnbxaaaxaabxab ( )( )/(1, )kkikikkkmaaikn (1)( )( )( ,1, )kkkijijikkjaam ai jkn (1)( )( )(1, )kkkiiikkbbm bikn 其中注意：必須確保0kka 回代過程回代過程對于上三角方程組，容易得到( )( )( )( )( )1/()/(1,2,2,1)nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 可行性與計算量可行性與計算量1、系數(shù)矩陣A的各階順序階主子式均不為零。2、系數(shù)矩陣A對稱正定。3、系

4、數(shù)矩陣A嚴(yán)格對角占優(yōu)。消元和回代的乘除及加減法總次數(shù)總次數(shù)如下：65232)1()1)(332)1()1)()(2311231111nnnnnknknnnnnnknknknnknknk高斯消元法的消去過程和回代過程均要求 ，否則溢出停機。但在如下情況下，對原方程組不作任何處理，確保上述條件成立，使高斯消去法在計算機上順利執(zhí)行。 由于在此不予證明，僅列出一下三個條件條件： ), 2 , 1( 0)(nkakkk相比克萊姆法則的乘除法次數(shù)不在一個數(shù)量級上，減少了很多。nnnn) 1( !) 1(4.1.2 高斯列主元消去法高斯列主元消去法為擬制舍入誤差的傳播，在消元過程中希望主元 的絕對值最大，就

5、要在每步消元過程前選主元。通常有列主元列主元和全主元全主元兩種方法。 kka列主元消去法列主元消去法是第k步消元時，選取( )( )maxkkpkikk i naa 作為主元素，進(jìn)行消元。而全主元消去法全主元消去法是選取ijnjknikpqaamax作為第k步的主元素進(jìn)行消元。列主元列主元往往需要行的交換，而全主元全主元不僅需要行的交換，而且可能需要列的交換。列的交換實質(zhì)上是未知量的交換。列主元素消去法步驟及流程框圖 （p63-65）選主元的思想思想是消除零主元和小主元，策略策略是對方稱組進(jìn)行行或列的交換。4.2 三角分解法三角分解法 矩陣的初等（行）變換與初等方陣矩陣的初等（行）變換與初等方

6、陣矩陣的初等變換：三種形式初等方陣：三種形式類型，p(I,j), p(i(k),p(i(k),j)，與初等變換一一對應(yīng)初等變換與初等方陣的關(guān)系：初等方陣的逆陣、行列式、乘法此處主要使用第三種形式的初等方陣1111),(kjkiP1),(1111),(1jkiPkjkiP4.2.1 LU LU分解法分解法高斯消去法的消元過程是通過對增廣矩陣的初等行變換來完成的。 101001,/, 1/, 3/, 3 , 2/10010001,10010001,10010001,1001001000002121111211111211)1(1, 1)1(1,1,)()()2(22)2(22)1(11)1(111

7、,1221211121)()()(2)(2)(22)(1)(1)(12)(11)2()2()2(2)2(2)2(2)2(22)2(1)2(1)2(12)2(11)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnnnnnnnkkkkikikiiiinnnnkknnknnnnnnnnnnnnnnnnnnnnnnnnnnnnlllLALyLUyULyULLLbALLLLaalnkiaalniaalniaallLlLlLllLyUbALLLLyUbabaabaaabaabaabaaabaaabaaabaaabALUULALybLU分解。這

8、里的乘積，這就是矩陣的與上三角陣分解為單位下三角陣即將又可寫成階單位下三角陣，且陣的乘積構(gòu)成的它們都是若干個初等方則有令其中用矩陣乘法可表示為：例例4-2 P67用用LU分解法求解線性方程組的分解法求解線性方程組的步驟步驟（1）對）對A進(jìn)行進(jìn)行LU分解，即分解，即A=LU；公式見p69 （4-5）-（4-8）（2）求解）求解Ly=b；公式見p69 （4-9）（3）求解）求解Ux=y；公式見p70 （4-10） 例例4-3 p70用用LU分解法求解線性方程組的分解法求解線性方程組的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 存儲空間僅需一個存儲空間僅需一個n階的二維數(shù)組和一個階的二維數(shù)組和一個n階的一維數(shù)組（向量）階的一

9、維數(shù)組（向量）公式nnnnnnnnnnnnnnnxxxyyybbbulluuluuuaaaaaaaaaA212121212222111211212222111211思考思考：如何利用矩陣的LU分解求解矩陣方程 Ax=B。4.2.1 LU LU分解法分解法 直接三角分解直接三角分解 可以不經(jīng)過高斯消去過程，直接利用公式得到矩陣的可以不經(jīng)過高斯消去過程，直接利用公式得到矩陣的LU分解。令分解。令LUuuuuuulllaaaaaaaaaAnnnnnnnnnnnn000101001222112112121212222111211矩陣L,U的計算公式見教材p69 （4-5）-（4-8）。如上的LU分解成

10、為杜利特爾（杜利特爾（Doolittle）分解）分解。還有另一種分解法稱為克克勞特（勞特（Crout）分解）分解，它是將A分解為一個下三角陣L與一個單位上三角陣U的乘積的形式，可以自己推導(dǎo)L和U的計算公式。LU分解的唯一性定理分解的唯一性定理定理定理4-1 設(shè)設(shè)A為為n階方陣，若階方陣，若A的各階順序主子式不為零，則的各階順序主子式不為零，則A可分解可分解為單位下三角陣為單位下三角陣L與一個上三角陣與一個上三角陣U的乘積，且這種分解是唯一的。的乘積，且這種分解是唯一的。證明：反證法。見證明：反證法。見p67 列主元列主元LU分解的分解的矩陣描述矩陣描述的意義同上節(jié)。種形式的初等方陣，第的行時交

11、換次兩行所對應(yīng)素在第次交換選列主元其主元是第這里kkkiniininniininLikEbbELELELUAAELELELknn1,)()1(1 ,12,21,1)()1(1 ,12,21,1121121PbLUxPAxLUPALLLLLPALLLLAEEEEELEEEELEEELELLnnnniiiiiiinininninininninknnnnnnnnnnnn,)()(54p1211112111 ,2,2,12,1,2,32,1,1,21,1121, 11, 1221, 1122111從而有令），可得到如下形式（見拓展 列主元列主元LU分解計算分解計算步驟步驟和和公式公式 P73-744.

12、2.2 列主元列主元LULU分解法分解法4.2.3 三對角方程組的追趕法三對角方程組的追趕法 三對角矩陣三對角矩陣與三對角方程組與三對角方程組 三對角矩陣的克勞特分解的三對角矩陣的克勞特分解的唯一性唯一性 追趕法計算追趕法計算步驟步驟及及流程圖流程圖 追趕法計算時的追趕法計算時的存儲結(jié)構(gòu)存儲結(jié)構(gòu)nnnnndacdacdacdA11122211定理定理4-2 設(shè)設(shè)A為三對角矩陣，且對角占優(yōu)，則對為三對角矩陣，且對角占優(yōu)，則對A可以進(jìn)行可以進(jìn)行克勞特分解克勞特分解，且分解是唯一的。且分解是唯一的。1 , 2 , 1,3, 3 , 2)/()(,/21, 3 , 2)/(,/11111111111n

13、ixuyxyxniuadyabydbyniuadcudcuiiiinniiiiiiiiiiii步驟步驟步驟iiiiiiixyubcda4.2.4 對稱正定矩陣的平方根法對稱正定矩陣的平方根法定理定理4-3 設(shè)設(shè)A為對稱正定矩陣，則存在一個下三角陣為對稱正定矩陣，則存在一個下三角陣L使得使得 A=LLT 若限定若限定L的主對角線元素取正值，則這種分解是唯一的。的主對角線元素取正值，則這種分解是唯一的。nnnnnnnnjjjkjkikijijjkjkjjjjnkijjjjkjkikjkikijllllllllllLnjinjlllalnjlalnjjilllllla,11,123222131211

14、111112111,1;1,2,1/)(,2,1)(,1,21的計算次序為：用上式求由矩陣乘法，可得1 , 1,/)(,2, 1/)(111nnilxlyxnilylbyyxLbLyiinikkkiiiiiikkikiiT的計算公式如下：和求解4.3 直接法的誤差分析直接法的誤差分析4.3.1 病態(tài)方程組病態(tài)方程組 對于線性方程組對于線性方程組Ax=b，如果，如果A或者或者b有很小的擾動（誤差），但其有很小的擾動（誤差），但其解會有很大的擾動（誤差），則稱該方程組為解會有很大的擾動（誤差），則稱該方程組為病態(tài)方程組病態(tài)方程組。11,00001. 0000211,0001. 00220001.

15、19999. 011220001. 11110001. 220001. 1111212121xAxxbxxxxxx時當(dāng)精確解時當(dāng)原問題20000/ 12/0001. 0/0001. 02/ 1/1bbbxxx上例的第一種情況：10000/11/0001. 0/0001. 02/1/1AAAxxx上例的第二種情況：4.3.2 矩陣的條件數(shù)矩陣的條件數(shù)通常用條件數(shù)的大小來度量方程組病態(tài)的程度。通常用條件數(shù)的大小來度量方程組病態(tài)的程度。矩陣矩陣A的條件數(shù)定義為的條件數(shù)定義為 范數(shù)及可取2 , 1)(1AAACond時當(dāng)時當(dāng)0)(1)(0)()(1)(bAAAAACondACondxxAbbACondxxAAbbAAACondACondxx計算3階希爾伯特矩陣的條件數(shù)（例4-6）4.4 近似解的精度改善近似解的精度改善 基本