線性方程組的數(shù)值解法

1、第二章線性方程組的數(shù)值解法n線性方程組nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111n對于線性方程組Ax=b,其中若系數(shù)陣A非奇異，則方程組有唯一解. 1112111212222212,nnnnnnnnaaaxbaaaxbaaaxbAxb計(jì)算機(jī)上求解線性方程組的有效數(shù)值方法n直接法 直接解法是解線性方程組的重要方法. 它是指通過有限步的算術(shù)運(yùn)算求出精確解的方法（若計(jì)算過程沒有舍入誤差）. 其基本思想是通過等價(jià)變換將線性方程組化為結(jié)構(gòu)簡單、易于求解的形式，從而求解. n迭代法 迭代法的基本思想是用某種極限過程逐次逼近方程組的解的方法，是解線

2、性方程組的重要方法.它具有占有儲(chǔ)存單元少、程序設(shè)計(jì)簡單、原始系數(shù)矩陣在計(jì)算過程中不變的優(yōu)點(diǎn)，但需考慮收斂性和收斂速度問題.2.1 向量、矩陣的范數(shù)向量的范數(shù)n設(shè)Rn為實(shí)n維向量空間, Cn為復(fù)n維向量空間,記Kn為Rn或Cn , K為實(shí)數(shù)域R或復(fù)數(shù)域C.n定義定義若Kn上任一向量x，對應(yīng)一個(gè)非負(fù)實(shí)數(shù)x ，滿足如下條件（）非負(fù)性：|x|0 且 |x|=0 x=0 （）齊次性：|x|=|x| (K) （）三角不等式 |x+y|x|+|y| (x,yKn) 則稱x為向量x的一種范數(shù). 常用的向量范數(shù)n設(shè)x=(x1,x2,xn)， 1-范數(shù)： 2-范數(shù)： -范數(shù)： p-范數(shù)11()nppipixx11

3、niixx12221niixx1maxii nx x矩陣的范數(shù)n記Knn為Rnn或Cnnn定義定義 若Knn上任一矩陣A=(aij)nn ,對應(yīng)一個(gè)非負(fù)實(shí)數(shù)A ，滿足以下條件:（）非負(fù)性： |A|0 且 |A|=0 A=0 （）齊次性：|A|=|A| (K) （）三角不等式： |A+B|A|+|B| (A,BKnn) （） |AB|A|B| (A,BKnn) 則稱 A為矩陣A的一種范數(shù). n例 對于實(shí)矩陣A=(aij)nn是一種矩陣范數(shù),稱為矩陣的Frobenius范數(shù)，簡稱矩陣的F范數(shù).21211()nnijFijaA 考慮到矩陣范數(shù)總是與向量范數(shù)聯(lián)系在一起的. n定義定義 對于給定向量范數(shù)

4、 和矩陣范數(shù) ，如果對任何向量xKn和AKnn,都有不等式AxAx 成立，則稱所給的矩陣范數(shù)與向量范數(shù)是相容的.n下面給出一種定義矩陣范數(shù)的方法，它是由向量范數(shù)誘導(dǎo)出來的相容范數(shù). 定義定義 設(shè)xKn和AKnn ，且給定一種向量范數(shù) ，稱 或 為矩陣A的由向量范數(shù)x產(chǎn)生的從屬范數(shù)或算子范數(shù). 單位矩陣的任一種從屬范數(shù)都為1.0maxXAxAx1maxxAAx由向量1-范數(shù),2-范數(shù), -范數(shù)產(chǎn)生的從屬范數(shù)分別為n定理定理 設(shè)n階方陣A ，則1-范數(shù)：2-范數(shù)： ，AH 是A的共軛轉(zhuǎn)置-范數(shù)：111maxnijj niaA 11maxniji njaA 2()HA AA矩陣的譜半徑n定義設(shè)n階方

5、陣A的特征值為1,2,n ，則稱 為A的譜半徑（i為i的模）. 對于任意從屬范數(shù) ， (A)|A|但當(dāng)A是正規(guī)矩陣，即A AH = AH A時(shí)， (A)=|A|2顯然若A為實(shí)對稱矩陣，則(A)=|A|21( )maxii nA 范數(shù)的有關(guān)定理n定理2.1(范數(shù)連續(xù)性定理) 設(shè)f(x)=|x|為Rn上任一向量范數(shù), 則f(x)是x的連續(xù)函數(shù).n定理2.2(范數(shù)等價(jià)性定理) 設(shè)|x|s , |x|t為Rn上任意兩種向量范數(shù), 則存在常數(shù)c1 ,c20，使得 c1|x|s|x|t c2|x|s ， xRnn定理2.3 向量序列xk收斂于x*的充分且必要條件是 |xk-x*|0, k 其中 是任一向量

6、范數(shù).矩陣范數(shù)也有相應(yīng)上述三個(gè)定理的結(jié)論例n x= (3,-1,5,8) ,求n解12,xxx1315817 x222223( 1)58993 11max 3 ,1, 5 , 88 xx例n 計(jì)算方陣 的各種常用范數(shù)n解 100024024A3131maxmax1,6,66Aijija 31131maxmax1,4,88Aijjia 1,AA21211()41nnijFijAaAHA的特征方程為(-1)(-8)(-32)=0所以(AHA)=32 從而 1001001000220240800440240032HA A2324 2A矩陣的條件數(shù)n設(shè)A為非奇異矩陣，稱數(shù) 為矩陣A的條件數(shù). n n條

7、件數(shù)與所取范數(shù)有關(guān) ,因此有時(shí)詳細(xì)記為1( )cond AAA11( )1condAAAAA1( )vvvcondAAA 解線性方程組的直接法 2.2 消去法Gauss消去法思想：Ax=bBx=d (其中B是上三角陣) 求解Bx=d Gauss消去法包括消元過程和回代過程兩個(gè)環(huán)節(jié)（一）消元過程1111112111211111211(1)(1)(1)0222221222211(1)(1)(1)2,3,12()iinnnnannarrainnnnnnnnaaabaaabaabaaabaabaaab第一步A b122(1)2212211121311(1)(1)(1)(1)2223220(2)(2)(

8、2)3333223,4,(2)(2)(2)3()iinnanarrainnnnnaaaabaaabaabaab （ ）（ ）第二步A b211(2),11(21,11112111(1)(1)(1)(1)222221011(1)(1)(1),(1)(1)(1)()kkkki kikkkkknknkakkkkkakkknkrrai knkkknknnnaaaabaaabaabaab（）第步Ab 1(1)(1111211111(1)(1)(1)(1)(1)22221220(1)(1)(1)(1)1( )( )( )11111,( )( )( )1kkkkikikkkkkknkknkakkkkkkkk

9、knkakkkrrkkknkai knkkknknnnaaaaabaaaabaaabaabaab （）第 步()kkA b211(2)11(2111112111(1)(1)(1)0222211(1)(1)()nnnnnnnnnnnnnannnarrnnannnaaabaabab）第步Abn n對 k=1,2,(n-1) ，依次計(jì)算 (1)(1)( )(1)(1)( )(1)(1)/( ,1,2, )kkikikkkkkkijijikkjkkkiiikkmaaaam ai jkknbbm biiijijbbaa)0()0(,n（二）回代過程(1)(1)(1)1()/(,1,1)niiiiiijj

10、iij ixbaxain n 選列主元的Gauss消去法nGauss消去法能夠進(jìn)行到底的條件是各步的主元素 . 另外既使主元素 不為零，但如果主元素的絕對值很小，用它作除數(shù)，勢必造成舍入誤差的嚴(yán)重?cái)U(kuò)散,以致于方程組的解的精度受到嚴(yán)重影響,為此引入選主元的方法，選列主元的具體方法如下：(1)kkka(1)0kkkan對方程組Ax=b仍按x1,x2,的順序依次消 元，只是在每一步消元前都增加一步按列選主 元的工作，如第k步消元前，就所 有 ，取絕對值最大者， 設(shè) ,將第l個(gè)方程與第k個(gè)方程互換 位置，這樣 成為第k步的主元素，然后進(jìn) 行第k步消元. 每步消元都如此，最后再進(jìn)行回 代過程，得出方程組

11、的解. (1)(,1, )kkak kn(1)(1)maxkklkkknaa (1)klka全選主元的Gauss消去法n對方程組Ax=b仍按x1,x2,的順序依次消元，只是在每 一步消元前都增加一步全選主元的工作，如第k步消 元前，就所有 ，取絕對值最大者， 設(shè) ，將第l個(gè)方程與第k個(gè)方程互 換位置，變元xs,xj互換位置，這樣 成為第k步的主元 素，然后進(jìn)行第k步消元. 每步消元都如此，最后再進(jìn)行 回代過程，得出方程組的解. (1)( ,1, )kijai jk kn(1)(1)maxkklsijk i nkj naa (1)klsan選列主元的Gauss消去法能壓制計(jì)算過程中舍入誤差的增長

12、，減少舍入誤差對計(jì)算結(jié)果的影響. 例n 利用Gauss消去法求解方程組Ax=b, 其中1212425327,2235112240Abn解 （1）消元過程用矩陣表示為2131413243(0)(0)2212312124121242532701121223510251712240001641212412124011210112100339003390016400077rrrrrrrrrr 第一步第二步第三步Ab(3)(3)Ab經(jīng)三步消元后；原方程組化為同解的上三角形方程組A(3)x=b(3) . n（2）回代過程對方程組A(3)x=b(3) 自下而上按未知元xi的下標(biāo)逆序逐步回代得原方程組的解為

13、x4=-1, x3=2, x2=-1, x1=2, 即x=(2,-1,2,-1) 例n 用選列主元素的Gauss法解下列方程組n解 消元過程用矩陣表示為1234123341518311151111631112xxxxn 2113141231181612334151831115123341518311151111611116311123111218311157100153371717310618186375102662rrrrrrrr 2選主元第一步消元選主元4218311153751026627171731061818671001533rr 324342721()()9252318311151

14、8311153751375100266226625085050850000027279272799114351400000025993rrrrrr 第二步消元第三步消元n得同解上三角方程組n回代求解得x4=0,x3=3,x2=2, x1=1, 即x=(1,2,3,0) 12342343441831537512662508502727991025xxxxxxxxxx 例n設(shè)系數(shù)矩陣A=(aij)nn的元素a110 . 經(jīng)過Gauss消去法一步以后A化為其中為n-1維列向量，A2為n-1階方陣. 證明：(1)若A為對稱矩陣，則A2也為對稱矩陣；(2)若A為嚴(yán)格對角占優(yōu)矩陣，則A2也是嚴(yán)格對角占優(yōu)矩

15、陣；(3)若A為對稱的嚴(yán)格對角占優(yōu)矩陣，則選列主元Gauss消去法就是（順序）Gauss消去法. 1120TaA n證 (1)經(jīng)Gauss消元一步后，A2的元素為n由于A對稱，故 aij=aji ，從而n因此A2為對稱矩陣. (1)1111( ,2,3, )iijijjaaaai jna1(1)(1)1111111jiijjijjiijiaaaaaaaaaan(2)設(shè)A是（按行）嚴(yán)格對角占優(yōu)矩陣（按列嚴(yán)格對角占優(yōu)可類似考慮） ，即 1(1,2, )niiijjj iaain(1)1111222211111111111221111111111121111(1)1111()(0)(2,3nnnni

16、iijijjijjjjjjj ij ij ij innniiijijiiijjjjj ij ij iniiiijiiiijiiiiiiaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaia, )n因此A2是嚴(yán)格對角占優(yōu)矩陣. n(3)由于A是對稱的嚴(yán)格對角占優(yōu)矩陣所以因而即第一步消元a11為主元素. 由(1)、(2)知A2是對稱的嚴(yán)格對角占優(yōu)矩陣. 記111112,(2,3, )njiijaaaain1111(2,3, )iiaaain(1)(1)(1)222322(1)(1)(1)23nnnnnaaaaaaAn則第二步消元 為主元素. 依次類推，選列主元Gauss消去法就是（

17、順序）Gauss消去法. (1)22a 2.3 矩陣三角分解法 nA1=L1-1A, b1=L1-1bnA2=L2-1A1=L2-1L1-1A, b2=L2-1b1=L2-1L1-1b nAn-1=Ln-1-1L2-1L1-1A, bn-1=Ln-1-1L2-1L1-1bn記記U=An-1=Ln-1-1L2-1L1-1A A=L1L2 Ln-1U= LU 12211101010001nmmL111101001001nnmL211131111010001nmmm L2112131321211111nnnnnmmmmmmLL LLn如果A的所有順序主子式均不為零，則A可唯一分解為 A=LU 其中L

18、為單位下三角陣，U為上三角陣. 以下討論中都假設(shè)上述條件成立.求解Ax=b求解LybUxyDoolittle分解法(直接三角分解法) ni）分解 A=LU, 其中L為單位下三角陣，U為上三角陣.即利用矩陣運(yùn)算比較兩邊得其分解公式:對k=1,2,3,n，其中111211112121222212221212100100100nnnnnnnnnnnnaaauuuaaaluuaaalluALU1111(,1, )()(1,2, )kkjkjkrrjrkikikirrkkkrual ujk knlal uuikkn010求解Ax=b求解nii）求解方程組Ly=b，即n其計(jì)算公式為n其中11(1,2, )

19、kkkkrrrybl ykn010nnnnbbbyyylll21212121101001LybUxyniii）求解方程組Ux=y，即n其計(jì)算公式為n其中 1()(,1,2,1)nkkkrrkkr kxyu xukn n 10nnnnnnnnyyyxxxuuuuuu212122211211000nDoolittle分解法的存儲(chǔ)可利用原系數(shù)矩陣的存儲(chǔ)單元，存儲(chǔ)形式111212122212nnnnnnuuuluulluA例用Doolittle分解法求解方程組n解 方程組的系數(shù)矩陣和右端項(xiàng)分別為12341234123412342426949615232691822615184047xxxxxxxxxx

20、xxxxxx242649615269186151840A9232247bn（1）分解A=LU，即 n（2）求解Ly=b，即n解得y=(9, 5,3,-1)12426211231213633211A123419212312122332147yyyyn求解Ux=y ，即n由公式解得x=( 0.5 ,2,3,-1)123424269123536311xxxxCrout分解法ni）記D=diag(u11,u22,unn), 其中 是下三角陣，是單位上三角陣.此分解是惟一的.利用矩陣運(yùn)算比較兩邊得其分解公式: 對k=1,2,3,n，111112112121222221221212001010 001nn

21、nnnnnnnnnnlaaauuaaaullaaalllALU1111(,1,2, )()/(1,2, )kikikirrkrkkjkjkrrjkkrlal uik kknual uljkkn11 ()(),ALULD D ULU LLD UD UL求解Ax=b求解nii）求解方程組 ，即n其計(jì)算公式為n其中11()/(1,2, )kkkkrrkkrybl ylkn010111122212212000nnnnnnlybybllyblllLybLybUxyniii）求解方程組x=y，即n其計(jì)算公式為n其中 1(,1,2,1)nkkkrrr kxyu xkn n 10nn1112122210100

22、1nnnnxyuuxyuxynCrout分解法的存儲(chǔ)可利用原系數(shù)矩陣的存儲(chǔ)單元，存儲(chǔ)形式111212122212nnnnnnluullulllAn例 用系數(shù)矩陣A的Crout分解求解線性方程組Ax=b. 其中 6211624101,1141510135Abn分解 ，即n求解方程組 ，得n求解方程組 ，得 ALU61111366102113015102371931000137191911000131074ALyb9461, 110 37yUx=y(1, 1,1, 1)xCholesky分解法(平方根法)ni）記D=diag(u11,u22,unn), = D-1U A=LU=(LD)(D-1U)

23、=LD (分解惟一)其中L是單位下三角陣，是單位上三角陣.n如果A是對稱正定的，則=L,其中 是下三角陣1122()()ALDLLDLDLLL稱為矩陣的Cholesky分解.利用矩陣運(yùn)算比較兩邊得其分解公式: 對k=1,2,3,n，其中1112111112112122221222221212000000nnnnnnnnnnnnnnaaallllaaallllaaallllALL12 1/2111()()/(1,2, )kkkkkkrrkikikir krkkrlallal llikkn010求解Ax=b求解nii）求解方程組 ，即 其計(jì)算公式為其中111122212212000nnnnnnyb

24、lybllyblllLy=b11(1,2, )kkkkrrkkrybl ylkn010rTLybL x=yniii）求解方程組 ，即 其計(jì)算公式為其中TL x=y1()(,1,2,1)nkkrkrkkr kxyl xlkn n 10nr n 111121122222000nnnnnnxylllxyllxyln平方根法是用于解系數(shù)矩陣為正定矩陣的線性方程組.n例 用平方根法（Cholesky分解）解方程組解 由于系數(shù)矩陣A對稱正定，故一定有分解形式其中 為下三角陣. （1）對系數(shù)矩陣進(jìn)行Cholesky分解 ，即L1233235220330127xxx TALLTA LL111121312122

25、2232313233333232203012llllllllllll由公式得解方程組 ，即得解方程組 ，即得 Ly=b11213122323323,332,6,33llllll 12335223337363yyy 511(,)363y12325333321636133xxx TL x=y1 1(1, )2 3x改進(jìn)的Cholesky分解法(改進(jìn)的平方根法)利用矩陣運(yùn)算比較兩邊得其分解公式:對k=1,2,3,n,1112112112122221221212100110011001nnnnnnnnnnnaaadllaaaldlALDLaaalld12111()/(1,2, )kkkkkrrrkik

26、ikirr krkrdal dlal d ldikknnii）求解方程組Ly=b 其中niii）求解方程組L x= D-1y 其中11(1,2, )kkkkrrrybl y kn1(,1,2,1)nkkkrkrr kxydl xkn n 10nr n 010rn 例 用改進(jìn)的平方根法解方程組n解系數(shù)矩陣是對稱的，故可分解為LDLT，設(shè)有分解n由公式得1233351035916591730 xxx1213121232313233351135911591711dllldllld12131232353,1,322,2,3dlldld解方程組Ly=b ，即得解方程組Lx= D-1y ，即得123110

27、1116530213yyy4(10,6, )3y111122133511103126143xdxdxd(1, 1,2)x解三對角方程組的追趕法n設(shè)方程組 Ax=d它的系數(shù)方陣A是一個(gè)階數(shù)較高的三對角方陣且滿足條件：(i) |b1|c1|0 , (ii) |bn|an|0 (iii)|bi| |ai|+|ci| , ai,ci0(i=2,3,n-1) 11222333111nnnnnbcabcabcabcabAni)對A進(jìn)行Crout分解利用矩陣運(yùn)算比較兩邊推得其分解公式：11112222223331111111111nnnnnnnnnnbcabcabcabcab1111111,/,(2, )(

28、2, )/(),(2,1)iiiiiiiiiiibcbainbaincbainni,可由ai, bi ,i-1, 產(chǎn)生，真正需計(jì)算的是i. i的遞推公式為1111/(),(2,1)iiiiicbcbain求解Ax=d求解nii）求解方程組 ，即其計(jì)算公式為 (k=2,3,n) 11111/()/()kkkkkkkydbyda ybaLyd111222211nnnnnnydydydLydUxy niii）求解方程組x=y，即n其計(jì)算公式為 (k=n-1,n-2, ,2,1)11122211111nnnxyxyxy1nnkkkkxyxyxn將求系數(shù)1 2 n-1及y1 y2 yn的過程稱之為追的過

29、程;求xn xn-1 x2 x1的過程稱之為趕的過程; 2.4 誤差分析 Ax=b (1)Ax =b (2)n(2)是(1)的近似方程組，研究二者解的近似程度n上面問題相當(dāng)于研究Ax=b的精確解x與(A+ A) (x+ x)=b+ b 的精確解x+ x的差 x與擾動(dòng) A和 b的關(guān)系方程組Ax=b 的右端b的擾動(dòng)對解的影響n設(shè) b為b的擾動(dòng)， 引起解x的擾動(dòng)為 x，則1cond( )xbbA AAxbb1()A xxbbxAb1xAbAxbxAA方程組Ax=b 的系數(shù)陣A的擾動(dòng)對解的影響設(shè) A為A的擾動(dòng)， 引起解x的擾動(dòng)為 x，則11()() xAA xxxAAxx()()()0AA xxbA

30、xA xx11假設(shè)足夠小，使AAA1111cond( )111 cond( )AAA AAAAxAAAAxAAA AAAAn對于一個(gè)確定的線性方程組，系數(shù)矩陣的條件數(shù)較?。ń咏?）時(shí)，方程組是良態(tài)的；反之，條件數(shù)較大（1）時(shí)，則方程組是病態(tài)的. 條件數(shù)越大，則病態(tài)越嚴(yán)重. 條件數(shù)的值刻劃了方程組病態(tài)的程度. 用一個(gè)穩(wěn)定的方法去解一個(gè)良態(tài)方程組，必然得到精度很高的解. 同樣，用一個(gè)穩(wěn)定的方法去解一個(gè)病態(tài)方程組，結(jié)果就可能很差. 2.5 解線性方程組的迭代法 n將方程組 Ax=b （2.5.1)改寫成等價(jià)方程組 x=Bx+g （2.5.2) 建立迭代格式 x(k+1)=Bx(k)+g (k=0,1

31、,2,) （2.5.3) 向量x(0)為初始預(yù)估解向量,用公式(2.5.3)逐步迭代求解的方法叫做迭代法.B稱為迭代矩陣. 如果產(chǎn)生的序列x(k)對于任意初始向量x(0)均收斂于x*，則稱迭代法是收斂的. 顯然x(k)的極限x*為方程組(2.5.2)的精確解.迭代法的誤差n記 (k)=x(k)-x* (k=0,1,2,)稱為第k步迭代的誤差向量. (k+1)=x(k+1)-x* =B(x(k)-x*)=B (k) (k+1)=Bk+1 (0) (k=0,1,2,)其中 (0)=x(0)-x*為初始誤差向量. 考察收斂性，就要研究B在什么條件下 (k)0 (k) ，即就要研究B滿足什么條件時(shí)有

32、Bk0(k).迭代法的收斂性n定理 設(shè)BKnn, 的充分必要條件是(B)1. n定理（迭代法的基本收斂定理）迭代過程 x(k+1) =Bx(k) +g對于任意初始向量x(0)及右端向量g均收斂的充分必要條件是迭代矩陣B的譜半徑(B)1, 并且(B) 愈小，收斂速度愈快. 由此可知：迭代法的收斂性與收斂速度與迭代矩陣B有關(guān)，而與右端向量g和初始向量x(0)無關(guān). limkkB 0迭代法的誤差估計(jì)n定理 設(shè)x*為方程組Ax=b的精確解. 若迭代法 xk+1) =Bx(k) +g的迭代矩陣B滿足B1, 其中.是某種算子范數(shù)，則對于任意的初始向量x(0)與右端向量g迭代法收斂， 且有如下兩個(gè)誤差估計(jì)式

33、：（1） （2.5.4)（2） （2.5.5) ( )( )(1)*1kkkBxxxxB( )(1)(0)*1kkBxxxxBn證 (B)B1，故對于任意的x(0)與g迭代收斂. x(k+1) - x* =B(x(k) -x*) x(k+1) - x(k) =B(x(k) - x(k-1) ) x(k+1) - x* Bx(k) -x* x(k+1) - x(k) Bx(k) - x(k-1) ， 利用x-yx-y Bx(k)-x(k-1)x(k+1)-x(k)x(k)-x*-x(k+1)- x* (1-B)x(k) -x*(1)成立.再反復(fù)利用x(k+1)- x(k)Bx(k)-x(k-1)

34、 得(2)成立.基本迭代公式n將方程組Ax=b的系數(shù)A分解成 A=L+D+U其中D=diag(a11,a22,ann) ，L和U分別是A的對角線下方元素和上方元素組成的嚴(yán)格下三角陣與嚴(yán)格上三角陣. 即111212122212000000000000000000nnnnnnaaaaaaaaa AJacobi迭代法n若aii0 (i=1,2,n), 將方程組 建立迭代格式 (k=0,1,2,)稱為解方程組Ax=b的Jacobi迭代法.nnnnnnnnnnbxaxaxabxaxaxabxaxaxa2211222221211121211113112112311111111232212213222222

35、22112121nnnnn nnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa (1)( )( )( )13112112311111111(1)( )( )( )232212213222222221(1)( )( )( )12121kkkknnkkkknnn nkkkknnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa nJacobi迭代法的分量形式若aii0，將方程組改寫為建立迭代格式), 2 , 1(1nibxanjijij), 2 , 1()(11nixabaxnijjjijiiii(1)(

36、 )11()(1,2, ;0,1,2,)nkkiiijjjiij ixba xinkaJacobi迭代法nJacobi迭代法矩陣形式若aii0 (i=1,2,n), 即D非奇異，將方程組Ax=b改寫成 Dx=-(L+U)x+b x=-D-1(L+U)x+D-1b建立迭代格式 x(k+1)=-D-1(L+U)x(k)+D-1b (k=0,1,2,)稱為解方程組Ax=b的Jacobi迭代法.n迭代矩陣BJ=-D-1(L+U)=E-D-1A1121111221222212000nnJnnnnnnaaaaaaaaBaaaaGauss-Seidel迭代法n Gauss-Seidel迭代法分量形式nGau

37、ss-Seidel迭代法矩陣形式 將方程組Ax=b，改寫成 (D+L)x=-Ux+b x=-(D+L)-1Ux+(D+L)-1b 建立迭代格式 x(k+1)=-(D+L)-1Ux(k)+(D+L)-1b (k=0,1,2,)稱為解方程組Ax=b的Gauss-Seidel迭代法.迭代矩陣BG=-(D+L)-1U1(1)(1)( )111() (1,2, ;0,1,2, )inkkkiiijjijjjj iiixba xa xinka 超松弛迭代法(SOR方法)n由Gauss-Seidel迭代法得由此得公式即稱為超松弛迭代法(SOR方法),其中為松弛因子. 超松弛法的矩陣表示為當(dāng) =1時(shí),就是Ga

38、uss-Seidel迭代法.)()(11)1()()1(nijkjijijkjijiiikikixaxabaxx)()1()1()1 (kikikixxx)(11)(11)1()1(nijkjijijkjijiiikixaxabax(1)1( )1() (1)()kkxDLDU xDLbn定理 超松弛法收斂的必要條件為02n證 設(shè)其迭代矩陣B的特征值為1,2, n , 由于迭代收斂,故有(B)1 從而 又 因此|1-| 1 ,即02121det(max)1nnii n B111221122detdet() ) det(1)1(1)(1)nnnnnna aaa aaBDLDU關(guān)于解某些特殊方程組

39、迭代法的收斂性n定理定理 若線性方程組Ax=b b的系數(shù)矩陣A為 對稱正定陣，則Gauss-Seidel迭代法 收斂.定理定理 若線性方程組Ax=b的系數(shù)矩陣A為 對稱正定陣，則當(dāng)02時(shí), SOR方 法收斂.n稱方陣A=(aij)nn 為嚴(yán)格對角占優(yōu)的，如果 或n定理 若線性方程組Ax=b的系數(shù)方陣A=(aij)nn是按行(或按列)嚴(yán)格對角占優(yōu)的，則Jacobi迭代法和Gauss-Seidel迭代法都是收斂的.), 2 , 1(1niaaiinijjij), 2 , 1(1njaajjnjiiijnJacobi迭代矩陣由于A是按行嚴(yán)格對角占優(yōu),即故從而Jacobi迭代收斂11max1nijJi

40、 njiij iaa B11211112211222212000nnJnnnnnnaaaaaaaaaaaaBED A), 2 , 1(1niaaiinijjijn設(shè)方程組的精確解為nGauss-Seidel迭代公式為n兩式相減得*12(,)nxx xx 1(1)(1)( )111()(1,2, ;0,1,2,)inkkkiiijjijjjj iiixba xa xinka )(11*11*nijjijijjijiiiixaxabax )()(11)(*11)1(*)1(*nijkjjijijkjjijiikiixxaxxaaxxn令 ,設(shè)n則n整理得n由于系數(shù)陣A是按行嚴(yán)格對角占優(yōu)的,故)(*

41、1maxkiinikxx )1(*)1(*11maxkllkiinikxxxxnljkljljkljllkllkaaaxx1111)1(*1)(1kljllljnljllljkaaaa11111 令 ， n從而n所以Gauss-Seidel迭代 法收斂.1111(1)1knljj llllklljjllaarlnaa (1)1100()kkkxxrk maxklrrn定理定理 若線性方程組Ax=b的系數(shù)矩陣A為嚴(yán)格對角占優(yōu)矩陣，則當(dāng)01時(shí),SOR方法收斂.n定理定理 設(shè)A是具有正對角線元素的對稱矩陣，則解線性方程組Ax=b的Jacobi迭代法收斂的充分必要條件是A和2D-A都為對稱正定陣.nJ

42、acobi迭代法收斂的充要條件:(BJ)1 A和2D-A都為對稱正定陣(A是具有正對角線元素的對稱矩陣). 充分條件： BJ1 A是嚴(yán)格對角占優(yōu)的nGauss-Seidel迭代法收斂的充要條件:(BG)1 充分條件： BG1 A是嚴(yán)格對角占優(yōu)的 A為對稱正定陣nSOR方法收斂的充要條件:(B)1 充分條件： B1 A是嚴(yán)格對角占優(yōu)的，且01 A為對稱正定陣， 02 必要條件：02n例1 分別用Jacobi迭代法與Gauss-Seidel迭代法求解方程組取初值x(0)=(0,0,0),123123123202324812231530 xxxxxxxxx解n（1）系數(shù)陣嚴(yán)格對角占優(yōu)，故Jacobi

43、迭代法與Gauss-Seidel迭代均收斂.法用Jacobi迭代法，其迭代法的分量形式為(1)( )( )( )( )12323(1)( )( )( )( )21313(1)( )( )( )( )312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxkJacobi迭代法的矩陣形式為 x(k+1)=(E-D-1A)x(k)+D-1b即 (1)( )11(2)( )22(1)( )3300.10.151.20.12500.1251.50.13330.2

44、02.0kkkkkkxxxxxx 取初值x(0) =(0,0,0)，迭代可得迭代7次，得近似值(1)(2)(3)(4)(5)(6)(1.200 000,1.500 000,2.000 000) ,(0.750 000,1.100 000,2.140 000) ,(0.769 000,1.138750,2.120 000) ,(0.768125,1.138875,2.125 217) ,(0.767 330,1.138332,2.125358) ,(0.767 363,1.138 414,2xxxxxx(7).125356) ,(0.767 355,1.138 410,2.125368) ,x(

45、0.767 355,1.138 410,2.125368)x(2)用Gauss-Seidel迭代法,其迭代法的分量形式為(1)( )( )( )( )12323(1)(1)( )(1)( )21313(1)(1)(1)(1)(1)312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxk其迭代法的矩陣形式為x(k+1)=-(D+L)-1Ux(k)+(D+L)-1b (k=0,1,2,)即 (1)( )11(1)( )22(1)( )3300.10.15

46、1.200.01250.106251.350 0.1583330.001252.11kkkkkkxxxxxx取初值x(0) =(0,0,0)，迭代可得迭代5次，得近似值(1)(2)(3)(4)(5)(1.200 000,1.350 000,2.110 000) ,(0.748500,1.142 688,2.128738) ,(0.766 421,1.138105,2.125 432) ,(0.767 375,1.138399,2.125363) ,(0.767 356,1.138 410,2.125368) .xxxxx(0.767 356,1.138 410,2.12537)xn例2 對方程

47、組分別討論用Jacobi迭代法和Gauss-Seidel迭代法求解的收斂性. 1231231232212223xxxxxxxxxn解 系數(shù)矩陣則Jacobi迭代法的迭代矩陣為其特征方程為因此有1=2=3=0,即(BJ)=01 ，所以Gauss-Seidel迭代法發(fā)散. 11100022022()110001023221000002G BDLU222023(2)0002EBG n例3 設(shè)方程組Ax=b中分別討論用Jacobi迭代法、Gauss-seidel迭代法和逐次超松馳迭代法(02)求解的收斂性. 111221112211122An解 顯然A是對稱矩陣. 現(xiàn)考慮A的各階順序主子式從而A是對稱

48、正定陣，故Gauss-Seidel迭代法收斂. 又由已知0f(x*).n 線性方程組Ax=b的求解問題等價(jià)于求一簇n維橢球面的公共中心問題.min( )( *)nxffRxx1(*)(*)( *)2CfxxA xxx11( )( *)( (*),*)(*)(*)22ffxxA xxxxxxA xxn思想：構(gòu)造向量序列xk，使 (1)f(x(k+1) f(x(k) f(x(1) f(x(0) (2)當(dāng)k時(shí), f(x(k) f(x*)這與要求x(k)x*(k)是一致的.n具體方法：由第k個(gè)近似x(k)構(gòu)造下一個(gè)近似x(k+1)，首先選定一個(gè)向量pk作為方向，要在直線x= x(k) +tpk (t為

49、參數(shù))上找一個(gè)使f(x)為極小的點(diǎn)x(k+1) ，即確定參數(shù)t使f(x(k)+tpk )為極小.單變量t的二次函數(shù)令(t)=t(Apk, pk)-(r(k), pk)=0得且這時(shí)有(t)=(Apk, pk)0, 從而得極小f(x(k+1).其中( )2( )( )1( )()(,)(,)()2kkkkkkktftttfxpAppbAxpx( )(,)(,)kkkkrptApp(1)( )( )(,)(,)kkkkkkkkkxxprpApp考察直線x= x(k) +tpk與橢球面f(x)=C的交點(diǎn)，二次方程(t)= f(x(k) +tpk)=C，當(dāng)C=f(x(k+1) 時(shí)只有一個(gè)重根k，因此pk

50、與橢球面f(x)=f(x(k+1)相切于x(k+1). 另外，r(k+1)=b-Ax(k+1)=b-A(x(k)+kpk)=r(k)-kApk(r(k+1), pk)= (r(k), pk)- k(Apk, pk)=0 r(k+1)與 pk正交.最速下降法在n維空間定義的二次函數(shù)f(x)在點(diǎn)x(k)的改變率最大的方向是f(x)在點(diǎn)x(k)的梯度 gradf(x)|x= x(k)=-r(k) ，因此沿方向r(k)函數(shù)f(x)瞬時(shí)下降的最快，所以取這個(gè)方向?yàn)閜k而得到新的近似x(k+1)的方法就叫最速下降法.只要r(k)0,最速下降法就繼續(xù)下去,這里有(r(k+1), r(k) )=0.(1)(

51、)( )( )( )( )( )0,1,2,(,)(,)kkkkkkkkkkxxrrrArr共軛梯度法n求解Ax=b的最速下降法的最速下降方向,即 r(k)=-gradf(x(k)具有局部性質(zhì),在x(k) 附近f(x)沿r(k) 下降最快. 但總體看,這個(gè)方向未必是函數(shù)下降最理想的方向.下面介紹更合理地選擇方向pk的方法,這種方法只要經(jīng)過有限步( n)就能找到n維橢球面簇的公共中心x*的一種迭代法，即共軛梯度法，它是具有迭代形式的精確解法.定義定義 ARnn為對稱正定矩陣, p,lRn，如果 (p, Al)=0,則稱p與l為A-正交或A-共軛.n先考察二維情形n共軛梯度法的具體步驟n第1步（采用最速下降法） 對于初始向量x(0)，r(0)=b-Ax(0)0，取p0=r(0), 從x(0)出發(fā)沿方向p0尋找新的近似(f(x)的極小點(diǎn))x(1).n計(jì)算r(1)=b-Ax(1)=r(0) - 0Ap0，且有(r(1), p0)=0，若 r(1)0 (1)(0)00(0)0000(,)(,)xxprpAppn第2步 選擇方向向量p1,滿足條件 ) p1=r(1) +0p0 ； ) p1與p0為A-正交或A-