計算方法Chapter05 - 線性方程組的解法

1、五線性方程組的解法2線性方程組的解法線性方程組的解法線性方程組求解概述線性方程組求解概述迭代法迭代法消元法基本思想消元法基本思想高斯消去法高斯消去法高斯高斯-約當消去法約當消去法列主元消去法列主元消去法方程組的病態(tài)問題方程組的病態(tài)問題3引言引言實際中，實際中，存在大量的解線性方程組的問題。存在大量的解線性方程組的問題。很多數(shù)值方法到最后也會涉及到線性方程組的求解問題：如很多數(shù)值方法到最后也會涉及到線性方程組的求解問題：如樣條插值的樣條插值的M和和m關(guān)系式，曲線擬合的正則方程組等問題。關(guān)系式，曲線擬合的正則方程組等問題。11 11221121 1222221 122,.nnnnnnnnnna x

2、a xa xba xa xa xba xa xa xb 其中其中nxxx,21未知量未知量ija第第i i個方程第個方程第j j個個未知量未知量x xj j的系數(shù)的系數(shù)常數(shù)項常數(shù)項全為全為0 0齊次線性方程組齊次線性方程組否則為非齊次否則為非齊次線性方程組線性方程組4上述線性方程組表示成矩陣形式為：上述線性方程組表示成矩陣形式為：bAx 系數(shù)矩陣系數(shù)矩陣未知量列向量未知量列向量常數(shù)項列向量常數(shù)項列向量問題：問題：(1) 方程組是否有解方程組是否有解?(2) 如果有解如果有解, 如何求出它的所有解如何求出它的所有解?求解求解Axb為增廣矩陣為增廣矩陣 bAA 引言引言5det( ) 0A 克萊姆

3、法則：當且僅當克萊姆法則：當且僅當時，有唯一的解，而且解為：時，有唯一的解，而且解為：nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,（1 1）計算）計算n+1n+1個個n n階行列式階行列式. . （計算一個（計算一個n n階行列式就需要做階行列式就需要做(n-1)n!(n-1)n!次乘法次乘法. . 要計算要計算n+1n+1個個n n階行列式階行列式, ,共需做共需做(n(n2 2-1)n!-1)n!次乘法）次乘法）. . （2 2）做）做n n次除法才能算出次除法才能算出x xi i(i=1, n).(i=1, n).（3 3）用此法

4、，需作乘除法的運算：）用此法，需作乘除法的運算： N=(nN=(n2 2-1)n!+n-1)n!+n例如例如, ,當當n=10(n=10(即求解一個含即求解一個含1010個未知量的方程組個未知量的方程組), ), 次數(shù)共為次數(shù)共為3265921032659210次；當次；當n n100100，10103333次次/ /秒的計算機要算秒的計算機要算1010120120年年克萊姆法則不能用于計算方程組的解克萊姆法則不能用于計算方程組的解引言引言6解線性方程組的方法可以分為解線性方程組的方法可以分為2類：類：迭代法：迭代法：是將方程組的解看作某種極限過程的向量極限的值，用迭代過程完成計算極限，在用迭

5、代算法時，不可能將極限過程算到底，只能將迭代進行有限多次，得到滿足一定精度要求的方程組的近似解。特點：特點：速度快，但有誤差直接法：直接法：經(jīng)過有限次四則運算，假定每一步運算過程沒有舍入誤差，最后得到方程組的解是精確解。特點：特點：準確，可靠，理論上得到的解是精確的一般地：對低階方程組用直接法，對高一般地：對低階方程組用直接法，對高階方程組和稀疏方程組用迭代法求解。階方程組和稀疏方程組用迭代法求解。引言引言7迭代法迭代法Jacobi迭代法迭代法迭代格式：迭代格式：設(shè)有設(shè)有n 階方程組階方程組 其中系數(shù)矩陣非奇異，且其中系數(shù)矩陣非奇異，且 ，i=1,2，niia0 將上式變形為將上式變形為nnn

6、nnnnn nnnnnxa xa xa xbaxa xa xaxbaxa xaxaxba11221331111221123322221122,111()1()1() nnnnnnnnnna xa xa xba xa xa xba xa xa xb11112211211222221122 8建立迭代格式建立迭代格式kkkknnkkkknnkkkknnnn nnnnnxa xa xaxbaxa xaxaxbaxaxaxaxba(1)()()()11221331111(1)()()()22112332222(1)()()()1122,111()1()1() 上面的迭代式稱為上面的迭代式稱為雅可比（雅

7、可比（Jacobi）迭代格式）迭代格式。迭代法迭代法nkkiiijjjiij ixba xina(1)( )11(),1,2, 9迭代法迭代法高斯高斯-塞德爾迭代法塞德爾迭代法假設(shè)已知近似值（假設(shè)已知近似值（x1(k), x2(k), x3(k), , xn(k), ）, 則迭代格式：則迭代格式： 其中系數(shù)矩陣非奇異，且其中系數(shù)矩陣非奇異，且 ，i=1,2，niia0 kkkkkkkknnkknnnnn nnnknknna xa xaxbaaa xaxbaaaabaxxxxxxx()()()1221331111()()212(1)1(1)(1)21(1)(1)(1)(1)12332222121

8、,11()1()1() inkkkiiijjijjjj iiixba xa xina1(1)(1)( )111(),1,2, 10迭代法迭代法超松弛法超松弛法實際上是高斯實際上是高斯-賽德爾迭代公式的一種加速方法。賽德爾迭代公式的一種加速方法。inkkkiiijjijjjj iiixba xa xa1(1)(1)( )111() 迭代：in1,2, kkkiiixxx(1)(1)( )=(1) 加速：松弛因子松弛因子11向量和矩陣的范數(shù)向量和矩陣的范數(shù)向量的范數(shù)：向量向量的范數(shù)：向量“大小大小”的某種衡量的某種衡量Tnxxxxx12(,) , 任給向量其范數(shù)記為基本性質(zhì)：基本性質(zhì)：p對于任意向

9、量對于任意向量x，| x |0，當且僅當，當且僅當x=0時，時， | x |=0p對于任意實數(shù)對于任意實數(shù)及任意向量及任意向量x，有，有 | x |=| | | x |p對于任意向量對于任意向量x和和y，有，有 | x+ y | x |+| y |12向量和矩陣的范數(shù)向量和矩陣的范數(shù)3種常用范數(shù)：種常用范數(shù)：p2-范數(shù)（長度）范數(shù)（長度）p1-范數(shù)范數(shù)p-范數(shù)范數(shù)niixx2 1/221() niixx11 ii nxx1max 13向量和矩陣的范數(shù)向量和矩陣的范數(shù)矩陣的范數(shù)：矩陣的范數(shù)：AxAxAn/對于給定的 階方陣 ，將比值的矩陣上確界稱為的范數(shù)直接由定義知，對于任意向量直接由定義知，對

10、于任意向量x，有：，有：| A x | A | | x |基本性質(zhì)：基本性質(zhì)：p對于任意方陣對于任意方陣A，| A |0，當且僅當，當且僅當A=0時，時， | A |=0p對于任意實數(shù)對于任意實數(shù)及任意方陣及任意方陣A ，有，有 | A |=| | | A |p對于任意方陣對于任意方陣A和和B，有，有 | A+ B | A|+| B | AB | A| | B |14消元法消元法1.三角方程組的解三角方程組的解niabxaaadiagAiiiinn, 1,),(221111 112222nnnna xba xba xb對角形方程組：對角形方程組：下面有3種方程的解我們可以直接求出：15nilx

11、lbxllllllAiiijjijiinnnn, 1,1121222111下三角形方程組：下三角形方程組：11 1121 122221 122nnnnnnl xbl xl xbl xl xl xb消元法消元法161 ,122211211niuxubxuuuuuuAiinijjijiinnnn1111221122222nnnnnnnnuxuxuxbuxuxbuxb上三角形方程組：上三角形方程組：消元法消元法17例：解方程組例：解方程組12121328xxxx方程方程（3 3）加到方程中得：）加到方程中得：21x 1221055xxx代入得代入得12x 相當于對方程組得增廣矩陣做行的初等變換：相當

12、于對方程組得增廣矩陣做行的初等變換：111111328055AAbAb消元法消元法18對方程組，作如下的變換，解不變對方程組，作如下的變換，解不變交換兩個方程的次序交換兩個方程的次序一個方程的兩邊同時乘以一個非一個方程的兩邊同時乘以一個非0 0的數(shù)的數(shù)一個方程的兩邊同時乘以一個非一個方程的兩邊同時乘以一個非0 0數(shù)，加到另一個方程數(shù)，加到另一個方程因此，對應的對增廣矩陣因此，對應的對增廣矩陣(A，b)，作如下的變換，解不變，作如下的變換，解不變交換矩陣的兩行交換矩陣的兩行某一行乘以一個非某一行乘以一個非0 0的數(shù)的數(shù)某一個乘以一個非某一個乘以一個非0 0的數(shù)，加到另一行的數(shù)，加到另一行消元法消

13、元法 ：就是對增廣矩陣作上述行的初等變換，變：就是對增廣矩陣作上述行的初等變換，變?yōu)槲覀円阎臑槲覀円阎?種類型之一，而后求根種類型之一，而后求根消元法的基本思想消元法的基本思想思路：首先將思路：首先將A化為上三角陣化為上三角陣 ，再回代求解。，再回代求解。=nnnnnnnbaaabaaabaaa21222221111211(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333( )( )000000nnnnnnnnaaaabaaabaabab高斯消去法高斯消去法Step 1：設(shè)：設(shè) ，計算因子，計算因子0)1(11 a(1)(1)111

14、1/(2,., )iimaain 將增廣矩陣將增廣矩陣第第 i 行行 + mi1 第第1行行，(2)(1)(1)11(2)(1)(1)1 1( ,2,., )ijijijiiiaam ai jnbbm b其中其中nnnnnnnbaaabaaabaaa21222221111211)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa實施步驟如下：實施步驟如下：運算量運算量 ：(n-1)(1+n)（n-1）次運算（n-1）（n-1）次運算（n-1）次運算高斯消去法高斯消去法)3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(2211

15nnnnnnbaabaabaaabaaaa運算量運算量 ：(n-2)(1+n-1)=(n-2)n)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaaStep 2：設(shè)：設(shè) ，計算因子，計算因子(2)220a(2)(2)2222/(3,., )iimaain 將增廣矩陣將增廣矩陣第第 i 行行 mi2 第第2行行，(3)(2)(2)22(3)(2)(2)22( ,3, .,)ijijijiiiaam ai jnbbm b其中其中（n-2）次運算（n-2）（n-2）次運算（n-2）次運算高斯消去法高斯消去法Step k：設(shè)：設(shè) ，計算

16、因子，計算因子且計算且計算0)( kkka( )( )/(1,., )kkikikkkmaaikn (1)( )( )(1)( )( )( ,1,., )kkkijijikkjkkkiiikkaam abbm bi jkn將增廣矩陣將增廣矩陣第第 i 行行 mik 第第k行行。運算量：運算量：(nk)(1nk1)=(nk)(nk2)（n-k）次運算（n-k）（n-k）次運算（n-k）次運算高斯消去法高斯消去法共進行共進行(n-1)步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()()3(3)3(3)3(33)2(2)

17、2(2)2(23)2(2211131211000000nnnnnnnnbabaabaaabaaaa消元的運算量為：消元的運算量為：32115()(2)326nknnnnk nk高斯消去法高斯消去法回代回代: :)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii回代的運算量為：回代的運算量為：總運算量為：總運算量為：Gaussian Elimination 的總乘除次數(shù)為的總乘除次數(shù)為 ，運算量為，運算量為 級。級。nnn31323 33n（n1）n/232115()(2)326nknnnnk nk消元的運算量為：消元的運算量為：高斯消去法高斯

18、消去法注意到，計算過程中注意到，計算過程中( )kkka處在被除的位置，因此整個計算過程要保證它不為處在被除的位置，因此整個計算過程要保證它不為0所以，所以，Gauss消元法的可行條件為：消元法的可行條件為：( )0kkka即，要求即，要求A的所有順序主子式均不為的所有順序主子式均不為0:niaaaaiiii, 1, 0det1111p 因此，有些有解的問題，不能用因此，有些有解的問題，不能用Gauss消元求解消元求解p 若若A的所有順序主子式的所有順序主子式 均不為均不為0，則高斯消元無需換行即可進行到底，則高斯消元無需換行即可進行到底，得到唯一解。得到唯一解。事實上，只要事實上，只要 A

19、非奇異，即非奇異，即 A 1 存在，則可通過逐次消存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。元及行交換，將方程組化為三角形方程組，求出唯一解。高斯消去法高斯消去法與與 Gaussian Elimination 的主要區(qū)別：的主要區(qū)別： 每步作第每步作第k行行 mik第第i行；行； 把把 akk(k) 所在列的上、下元素全消為所在列的上、下元素全消為0;( )( ),1,1,1,kikikkkkamikkna將該行上三角地部分也變?yōu)閷⒃撔猩先堑夭糠忠沧優(yōu)? 0 運算次數(shù)比運算次數(shù)比Gauss消元多，約為消元多，約為(n3/2)量級。量級。高斯高斯-約當消去法約當消去

20、法例：單精度解方程組例：單精度解方程組 211021219xxxx/* 精確解為精確解為 和和 */.1000.00. 1101191 x8個個.8999.99. 0212 xx8個個用高斯消去法計算：用高斯消去法計算：9212111/10maa 9992221110.0.01 101010am 8個個92212110bm 9991010011100, 112 xx小可能導致計算失小可能導致計算失敗。敗。另外，如果某個另外，如果某個( )kkka很小的話，會引入大的誤差很小的話，會引入大的誤差列主元消去法列主元消去法每次僅選一列中最大的元每次僅選一列中最大的元在在Gauss消元第消元第k步之前

21、，做如下的事情：步之前，做如下的事情：|max)()(kjkkiknikaa若若交換交換k行和行和j行行行的交換，不改變方程組的解，同時又有效地克服了行的交換，不改變方程組的解，同時又有效地克服了Gauss消元地缺陷消元地缺陷例：例：1,112 xx 21111109 110211 11102119 列主元消去法列主元消去法29方程組的病態(tài)問題方程組的病態(tài)問題矩陣的條件數(shù)與線性方程組的性態(tài)矩陣的條件數(shù)與線性方程組的性態(tài) 給定線性方程組給定線性方程組 Ax =b，現(xiàn)在考察，系數(shù)矩陣，現(xiàn)在考察，系數(shù)矩陣 A 和常數(shù)列和常數(shù)列 b 有了微小變化有了微小變化 A，b ，它如何影，它如何影響解向量響解向

22、量 x，即，解向量，即，解向量 x 的變化量的變化量 x 何樣？何樣？ 由于由于A （或（或 b）的元素是測量得到的，或者是）的元素是測量得到的，或者是計算的結(jié)果，在前種情況下，計算的結(jié)果，在前種情況下， A （或（或 b）常常帶有）常常帶有某些觀測誤差，在后種情況下，某些觀測誤差，在后種情況下， A （或（或 b）包含舍）包含舍入誤差，因此我們處理的實際矩陣是入誤差，因此我們處理的實際矩陣是A + A （或（或 b+ b ）。）。301122112112, 11.0001211.00012.0001xxxx 精確解 (2, 0)精確解 (1, 1) 考察方程組考察方程組 Ax = b, 當當 A 或或 b 有微小擾動時有微小擾動時, 對對解的影響，首先看一個例子：解的影響，首先看一個例子： 方程組的病態(tài)問題方程組的病態(tài)問題31方程組的病態(tài)問題方程組的病態(tài)問題定義定義 如果矩陣如果矩陣 A 或常數(shù)項或常數(shù)項 b 的微小變化，引起的微小變化，引起方程組方程組 Ax =b 的解的巨大變化，則稱方程組為的解的巨大變化，則稱方程組為“病病態(tài)態(tài)”方程組方程組，矩陣，矩陣 A 稱為稱為“病態(tài)病態(tài)”矩陣矩陣；否則稱方；否則稱方程組為程組為“良態(tài)良態(tài)”方程組，方程組， A 稱為稱為“良態(tài)矩陣良態(tài)矩陣”。32定理定理