太理水利工程計(jì)算及設(shè)計(jì)第二章 線性代數(shù)方程組的數(shù)值方法

1、第二章第二章 線性代數(shù)方程組的線性代數(shù)方程組的數(shù)值方法數(shù)值方法第一節(jié)第一節(jié) 線性代數(shù)方程組的直接解法線性代數(shù)方程組的直接解法第二節(jié)第二節(jié) 線性代數(shù)方程組的迭代解法線性代數(shù)方程組的迭代解法本章內(nèi)容本章內(nèi)容 各種直接解法的基本原理及構(gòu)造迭代格式的各種直接解法的基本原理及構(gòu)造迭代格式的基本原理?；驹?。重點(diǎn)重點(diǎn)第一節(jié)第一節(jié) 線性代數(shù)方程組的線性代數(shù)方程組的直接解法直接解法 直接解法是用有限次代數(shù)運(yùn)算得到方程組解的方法。直接解法是用有限次代數(shù)運(yùn)算得到方程組解的方法。如無舍入誤差，則由直接解法得到的解就是精確解。但舍如無舍入誤差，則由直接解法得到的解就是精確解。但舍入誤差以及誤差的積累是無法避免的，因

2、此直接解法給出入誤差以及誤差的積累是無法避免的，因此直接解法給出的仍是近似解。的仍是近似解。本節(jié)給出的各種直接解法都是適用于計(jì)算本節(jié)給出的各種直接解法都是適用于計(jì)算機(jī)的有效方法。機(jī)的有效方法。它們對稠密系數(shù)陣的較低階方程組（幾百它們對稠密系數(shù)陣的較低階方程組（幾百個(gè)方程）以及帶狀系數(shù)陣的高階方程組（幾千個(gè)方程）都個(gè)方程）以及帶狀系數(shù)陣的高階方程組（幾千個(gè)方程）都很有效。很有效。高斯消去法高斯消去法主元消去法主元消去法高斯高斯-約當(dāng)消去法約當(dāng)消去法三角分解法三角分解法對稱矩陣的三角分解對稱矩陣的三角分解-喬列斯基法喬列斯基法三對角陣的三角分解三對角陣的三角分解-追趕法追趕法方程組的逆矩陣解法與矩

3、陣求逆方程組的逆矩陣解法與矩陣求逆直接解法直接解法列主元法列主元法全主元法全主元法,22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa,2121212222111211nnnnnnnnbbbxxxaaaaaaaaa設(shè)有設(shè)有n階線性代數(shù)方程組階線性代數(shù)方程組 方程組的矩陣形式為方程組的矩陣形式為可簡記為可簡記為BAX 本節(jié)假定本節(jié)假定A A非奇異或其行列式不為零，方程組有解且非奇異或其行列式不為零，方程組有解且唯一。唯一。一、高斯消去法一、高斯消去法 高斯消去法是高斯消去法是解線性方程組的經(jīng)典方法解線性方程組的經(jīng)典方法，由它改進(jìn)得，由它改進(jìn)得到

4、的選主元的消去法到的選主元的消去法, ,是目前計(jì)算機(jī)上常用于求低階稠密是目前計(jì)算機(jī)上常用于求低階稠密矩陣方程組的有效方法矩陣方程組的有效方法, ,其特點(diǎn)就是通過消元將一般線性其特點(diǎn)就是通過消元將一般線性方程組的求解問題轉(zhuǎn)化為三角方程組的求解問題。方程組的求解問題轉(zhuǎn)化為三角方程組的求解問題。高高 斯斯 消消 去去 法法舉例舉例11221733230636321321321xxxxxxxxx112217332521321321321xxxxxxxxx第一步第一步 消元過程消元過程(1)(2)(3)消消x1式式(1)/6(4)(5)(6)式式(5)-式式(4) 2式式(6)-式式(4) 623725

5、213232321xxxxxxx(7)(8)(9)高高 斯斯 消消 去去 法法623725213232321xxxxxxx62327215213232321xxxxxxx消消x2式式(8)/2式式(12)-式式(11) (3/2)(7)(8)(9)(10)(11)(12)43412721521332321xxxxxx(13)(14)(15)高高 斯斯 消消 去去 法法43412721521332321xxxxxx第二步第二步 回代過程回代過程321321xxx(13)(14)(15) 由式（由式（15）得到）得到x3，代入式（，代入式（14）得到）得到x2，再代入式，再代入式（13） 得到得到

6、x1。結(jié)果如下。結(jié)果如下高高 斯斯 消消 去去 法法高斯消去法的步驟高斯消去法的步驟)0()0(2)0(21)0(1)0(2)0(22)0(221)0(21)0(1)0(12)0(121)0(11nnnnnnnnnnbxaxaxabxaxaxabxaxaxa第一步消元第一步消元)1()1(3)1(32)1(2)1(2)1(23)1(232)1(22)1(1)1(13)1(132)1(121nnnnnnnnnnbxaxaxabxaxaxabxaxaxax原方程原方程（一）消元過程（一）消元過程高高 斯斯 消消 去去 法法niababbabbnjiaaaaaaaaabbnjaaaaiiiiijii

7、jjiijijjj2 ,/,2 ,/2 ,/0)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)1(1)0(11)0(1)1(1)0(11若niababbabbnjiaaaaaaaababbaaaababbaaaaiiiiijiijjiijijjjjjjj2 ,/,2 ,/)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()1(1)0(31)0(3)1(3)1(1)0(31)0(3)1(3)1(1)0(21)0(2)1(2)1(1)0(

8、21)0(2)1(2niababbabbnjiaaaaaaaaabbnjaaaaiiiiijiijjiijijjj2 ,/,2 ,/2 ,/0)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)1(1)0(11)0(1)1(1)0(11若第第k-1步消元的結(jié)果步消元的結(jié)果)1()1(1)1(1)1()1()1(1)1(1)1()1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkkknkknkkkkkkkkkknknkkkkkknnnn

9、bxaxaxabxaxaxabxaxaxbxaxaxbxaxaxax)()(1)(1)()(1)(1)1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkknkkkkkkknknkkkkkknnnnbxaxabxaxaxbxaxaxbxaxaxbxaxaxax第第k部消元部消元高高 斯斯 消消 去去 法法)( ,0)( ,),( ,/)( ,/0)()()1()1()()()1()1()()1()1()()1()1()()1(nikanikbabbnjikaaaaabbnjkaaaakikkkkikkikikkjkikki

10、jkijkkkkkkkkkkkkjkkjkkk?以上為高斯消去法的以上為高斯消去法的消元過程消元過程的算法。的算法。高高 斯斯 消消 去去 法法第第k個(gè)方個(gè)方程程第第k+1到第到第n個(gè)方程個(gè)方程第第n-1步消元結(jié)果步消元結(jié)果)1()1(1)()2(2)1(1)1()1(1)()(1)2(2)2(23)1(1)1(13)1(1210111nnnnkknnnnnnkknkkknnbbbbbaaaaaaaaa?O（二）回代過程（二）回代過程高高 斯斯 消消 去去 法法)1()1()1()1(/nnnnnnnnnnnnabxbxankjjkkjkkknkknkkkkkkkkknkknkkkkkxabx

11、xaxabxbxaxax1)()()(1)(1)()()(1)(1)() 1 , 2 , 1(/1)()()1()1(nkxabxabxnkjjkkjkkknnnnnn以上為高斯消去法的以上為高斯消去法的回代過程回代過程的算法。的算法。高高 斯斯 消消 去去 法法102212423321321321xxxxxxxxx題題1 試用高斯消去法解下列方程（小數(shù)點(diǎn)后取試用高斯消去法解下列方程（小數(shù)點(diǎn)后取4位數(shù)位數(shù)字計(jì)算）。字計(jì)算）。解解: 第一步消元第一步消元6667. 83333.116667. 06667. 23333. 003333. 16667. 303333. 03333. 01BA高高 斯

12、斯 消消 去去 法法第二步消元第二步消元6365. 70909. 36667. 05455. 2003636. 0103333. 03333. 01BA回代結(jié)果回代結(jié)果0000. 30001. 20000. 1X高高 斯斯 消消 去去 法法題題2 試用高斯消去法解下列方程。試用高斯消去法解下列方程。52213614282321321321xxxxxxxxx高高 斯斯 消消 去去 法法 二、主元消去法（二、主元消去法（ 稱為主元）稱為主元）11221732521321321321xxxxxxxxx6237521323321xxxxxx)1( kkka主主 元元 消消 去去 法法（1）Gauss消

13、去法消去法消消x1得得消消x2無法進(jìn)行，因?yàn)闊o法進(jìn)行，因?yàn)?。0)1(22a12102221xyzxyzxyz 121212121212121212102101010210101021010zyzyzyx（2）考慮如下線性方程組的）考慮如下線性方程組的Gauss消去法消去法 假定計(jì)算能保證假定計(jì)算能保證10位有效數(shù)字，則在此精度內(nèi)位有效數(shù)字，則在此精度內(nèi)x=y=z=1 是真解。是真解。消消x無法求解。原因無法求解。原因:第一個(gè)主元第一個(gè)主元 過小。過小。解（一）解（一）:主主 元元 消消 去去 法法12)0(1110a12102221xyzxyzxyz 12102212zyxzyxzyx332

14、22yzyzyx選較大主元選較大主元消消x結(jié)果結(jié)果 x=y=z=1 選擇選擇絕對值盡可能大的系數(shù)絕對值盡可能大的系數(shù)作為主元，會減少舍入誤差作為主元，會減少舍入誤差的影響，提高解的精度，并保證算法的穩(wěn)定性。的影響，提高解的精度，并保證算法的穩(wěn)定性。解（二）解（二）:主主 元元 消消 去去 法法 主元消去法主元消去法 在每一步消元中選取在每一步消元中選取絕對值絕對值盡可盡可能大的主元的高斯消去法稱為主元消去法。能大的主元的高斯消去法稱為主元消去法。列主元法列主元法全主元法全主元法有兩種主元消去法：有兩種主元消去法：主主 元元 消消 去去 法法 在消去在消去 的系數(shù)前，先從的系數(shù)前，先從 中選取中

15、選取絕對值最大者作為主元，交換第絕對值最大者作為主元，交換第k行與此主元所在的行，再行與此主元所在的行，再按高斯消去法消去第按高斯消去法消去第k行之后的方程中行之后的方程中 的系數(shù)，只要方的系數(shù)，只要方程是可解的，這一過程定能執(zhí)行到底。程是可解的，這一過程定能執(zhí)行到底。（一）列主元法（一）列主元法kxkx)1()1(1)1(,knkkkkkkkaaa主主 元元 消消 去去 法法)1()1(1)1(1)1()1()1(1)1(1)1()1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkkknkknkkkkkkkkkknkn

16、kkkkkknnnnbxaxaxabxaxaxabxaxaxbxaxaxbxaxaxax.40371. 00020. 20028. 2047471. 00010. 161077. 008563. 10010. 13920. 11)() 1 () 1 (bA4178. 745625. 5996. 33816. 1078125. 014 . 022002. 0)0()0(bA解：解： 4178. 745625. 5996. 33814. 178125. 04 . 022002. 032121321xxxxxxxx舉例：列主元法舉例：列主元法 第一步選列主元為第一步選列主元為 ，交換第，交換第1行與

17、第行與第3行，再消行，再消元計(jì)算得元計(jì)算得996. 331a 第二步選列主元為第二步選列主元為 ,交換第交換第2行與第行與第3行，再消行，再消元計(jì)算得元計(jì)算得0028. 232a.35159.039047.00020157.09996.0108563.10010.13920.11)()2()2(bA回代計(jì)算得到解為回代計(jì)算得到解為這個(gè)例題的精確解是這個(gè)例題的精確解是 9273. 1,69850. 0,90043. 0123xxx,)900423. 0 ,698496. 0,92730. 1 (Tx,)88888. 0 ,68695. 0,9300. 1 (Tx高斯消去法的結(jié)果是高斯消去法的結(jié)果

18、是主主 元元 消消 去去 法法（二）全主元法（二）全主元法,22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxan階線性代數(shù)方程組階線性代數(shù)方程組 nnnnnnnnbbbxxxaaaaaaaaa2121212222111211矩陣形式矩陣形式行交換變行交換變量順序？量順序？列交換變列交換變量順序？量順序？ （2）從方程組系數(shù)）從方程組系數(shù) 中選出絕對值最大者，中選出絕對值最大者，作為第一個(gè)主元。交換第一行與此元素所在的行，并交換第一作為第一個(gè)主元。交換第一行與此元素所在的行，并交換第一列與此元素所在的列，使選出的主元位于第一行第一列，一般列與此

19、元素所在的列，使選出的主元位于第一行第一列，一般地，在第地，在第k次消元之前，先從次消元之前，先從 中選出絕對值最中選出絕對值最大者作為主元，假定其位于第大者作為主元，假定其位于第p行第行第q列，然后交換系數(shù)陣列，然后交換系數(shù)陣A及及右端項(xiàng)陣右端項(xiàng)陣B的第的第k行與第行與第p行，并交換行，并交換A的第的第k列與第列與第q列，且交換列，且交換序列向量的第序列向量的第k個(gè)元素與第個(gè)元素與第q個(gè)元素的內(nèi)容。個(gè)元素的內(nèi)容。（1）設(shè)置一標(biāo)識變量順序的一維向量，其初始內(nèi)容為）設(shè)置一標(biāo)識變量順序的一維向量，其初始內(nèi)容為 基本思想基本思想Tn,3,2,1),1 (njiaij；),()1(njikakij主主

20、 元元 消消 去去 法法 （3）按高斯消去法完成第）按高斯消去法完成第k步消元，反復(fù)執(zhí)行（步消元，反復(fù)執(zhí)行（2），），直至消元過程結(jié)束；直至消元過程結(jié)束； （4）回代求解，解的順序就是序列向量所示的順序。）回代求解，解的順序就是序列向量所示的順序。主主 元元 消消 去去 法法167. 5944. 0167. 105333. 210833. 0056. 0167. 01消元第一次 1513181533126111 153181533126321321321xxxxxxxxx解解 6111153312151318行行互互換換第第一一、三三舉例：全主元法舉例：全主元法167. 5944. 0167.

21、 105333. 210833. 0056. 0167. 01消元第一次144. 3572. 100143. 2429. 010833. 0167. 0056. 01消元第二次解為解為000. 1,000. 3,000. 2132 xxx167. 5167. 1944. 0051333. 20833. 0167. 0056. 01列互換第二、三x2和和x3次序次序變化變化 全主元法的精度略優(yōu)于列主元法，這是由于全主元法全主元法的精度略優(yōu)于列主元法，這是由于全主元法是在全體系數(shù)中選主元，故它對控制舍入誤差比較有效。是在全體系數(shù)中選主元，故它對控制舍入誤差比較有效。但全主元法在計(jì)算過程中，需同時(shí)作

22、行與列的互換，因而但全主元法在計(jì)算過程中，需同時(shí)作行與列的互換，因而程序比較復(fù)雜，計(jì)算時(shí)間較長。列主元法的精度雖稍低于程序比較復(fù)雜，計(jì)算時(shí)間較長。列主元法的精度雖稍低于全主元法，但其計(jì)算簡單，工作量大為減少，實(shí)踐表明，全主元法，但其計(jì)算簡單，工作量大為減少，實(shí)踐表明，它與全主元法同樣具有良好的數(shù)值穩(wěn)定性，故列主元法是它與全主元法同樣具有良好的數(shù)值穩(wěn)定性，故列主元法是求解中小型稠密線性方程組的最好方法之一。求解中小型稠密線性方程組的最好方法之一。一般采用列一般采用列主元法。主元法。說明：說明：主主 元元 消消 去去 法法題題3 分別用列主元消去法和全主元消去法求解線性分別用列主元消去法和全主元消

23、去法求解線性方程組。方程組。000. 3643. 5072. 1000. 2000. 2623. 4712. 3000. 1000. 1000. 3000. 2001. 0321321321xxxxxxxxx精確解舍入到精確解舍入到4位有效數(shù)字為位有效數(shù)字為Tx)3675. 0 ,05104. 0,4904. 0(主主 元元 消消 去去 法法關(guān)于主元法的幾點(diǎn)討論關(guān)于主元法的幾點(diǎn)討論 （1 1）有兩類系數(shù)陣可以避免選主元，直接使用高斯）有兩類系數(shù)陣可以避免選主元，直接使用高斯消去法便可得到滿意的結(jié)果。它們是：嚴(yán)格對角占優(yōu)矩消去法便可得到滿意的結(jié)果。它們是：嚴(yán)格對角占優(yōu)矩陣和對稱正定矩陣。陣和對稱

24、正定矩陣。嚴(yán)格對角占優(yōu)矩陣是指其元素滿足嚴(yán)格對角占優(yōu)矩陣是指其元素滿足)1 ( ,niaanijijii或以列為準(zhǔn)，其元素滿足或以列為準(zhǔn)，其元素滿足)1( ,njaanjiijjj 嚴(yán)格對角占優(yōu)矩陣嚴(yán)格對角占優(yōu)矩陣必定是非奇異陣，且每步消元后，必定是非奇異陣，且每步消元后，仍保持對角占優(yōu)的性質(zhì)，因此，不必選主元。仍保持對角占優(yōu)的性質(zhì)，因此，不必選主元。 對稱正定矩陣對稱正定矩陣其行列式大于零，方程組可解，且在每其行列式大于零，方程組可解，且在每步消元中，剩下的子陣仍保持對角占優(yōu)和對稱性，因此不步消元中，剩下的子陣仍保持對角占優(yōu)和對稱性，因此不必選主元。必選主元。行行列列（2）關(guān)于病態(tài)方程）關(guān)于

25、病態(tài)方程002755853. 0006324242. 0068528. 2446949. 1446949. 1012671. 121xxTX9057. 5,4448. 80062807. 00063242. 000090000. 004469. 10127. 121xx其具有其具有5位有效數(shù)字的正確解為位有效數(shù)字的正確解為如把其系數(shù)陣也取成如把其系數(shù)陣也取成5位有效數(shù)字位有效數(shù)字0027559. 00063242. 00685. 24469. 14469. 10127. 121xx給出的錯(cuò)誤解答為給出的錯(cuò)誤解答為TX9786. 6,9773. 9第一步消元后第一步消元后該方程為一個(gè)病態(tài)方程。該

26、方程為一個(gè)病態(tài)方程。判斷是否為病態(tài)方程判斷是否為病態(tài)方程: :行列式很大或很?。ㄈ缒承┬辛惺浇葡嚓P(guān)）；行列式很大或很小（如某些行列式近似相關(guān)）；元素間相差大數(shù)量級，且無規(guī)則；元素間相差大數(shù)量級，且無規(guī)則；主元消去過程中出現(xiàn)小主元；主元消去過程中出現(xiàn)小主元；特征值相差大數(shù)量級。特征值相差大數(shù)量級。解決方法解決方法在已知方程組是病態(tài)的情況下（通過試算或理論分析），在已知方程組是病態(tài)的情況下（通過試算或理論分析），宜采用雙倍或多倍字長進(jìn)行高精度運(yùn)算，以減弱有效位損宜采用雙倍或多倍字長進(jìn)行高精度運(yùn)算，以減弱有效位損失的影響。失的影響。下面的誤差校正算法下面的誤差校正算法主主 元元 消消 去去 法法（

27、3）使解精確化的誤差校正算法）使解精確化的誤差校正算法)1()1()1()1()1()1()1()1()(RAYXXYRXXAAXBR設(shè)設(shè)X(1)是方程組是方程組AX=B的解。則得到誤差向量的解。則得到誤差向量（1）（2）（3）（4）（5）由（由（1），則），則令令則（則（2）即為）即為求解（求解（4），則校正后的近似解是），則校正后的近似解是 由于由于X（1），Y（1）是有誤差的，故對解的校正可繼續(xù)，是有誤差的，故對解的校正可繼續(xù)，直到滿足誤差要求為止。直到滿足誤差要求為止。)1()1()2(YXX主主 元元 消消 去去 法法檢驗(yàn)相對誤差。設(shè)檢驗(yàn)相對誤差。設(shè)為給定精度，如果為給定精度，如果

28、則執(zhí)行則執(zhí)行，繼續(xù)修正近似解，直到，繼續(xù)修正近似解，直到 為止。對為止。對某個(gè)某個(gè)K，若，若 ，說明算法失效，不能使解精確，說明算法失效，不能使解精確化，則終止計(jì)算?；?，則終止計(jì)算。整個(gè)算法綜述如下整個(gè)算法綜述如下:取取用主元法解用主元法解修正近似解修正近似解計(jì)算誤差向量計(jì)算誤差向量計(jì)算相對誤差計(jì)算相對誤差BReAXBRYXXkRAYkkkkkkkkk/;, 2 , 1 , 0,)1()1()1()1()()()1()()()()1(kkee)(ne)()1(kkee; 1,)0()0()0(eBROX主主 元元 消消 去去 法法 三、高斯三、高斯約當(dāng)消去法約當(dāng)消去法12254632132321xxxxxxxx 前述消去法前述消去法包括消元回代兩個(gè)過程包括消元回代兩個(gè)過程。將消元過程略。將消元過程略加修改，把系數(shù)陣化為單位對角陣，則可免去回代。這加修改，把系數(shù)陣化為單位對角陣，則可免去回代。這種種將兩個(gè)過程合二為一的消元算法就是高斯將兩個(gè)過程合二為一的消元算法就是高斯約當(dāng)消