線性方程組的迭代法

1、第五章解線性方程組的迭代法 實際問題經(jīng)過簡單的分析可以直接歸結(jié) 為線性方程組，或者微分方程，后者可以轉(zhuǎn)換為線性方程組。 兩種方法： 直接法：中小型稠密矩陣 迭代法：大型稀疏矩陣5.1 Jacobi迭代法和Gauss-Seidel迭代法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111設(shè)線性方程組簡記 AX=bn其中1112121222n1n2n1212A()X,nnijn nnTTnnaaaaaaaaaaxxxbbbbn將方程組AX=b，改寫成便于迭代的形式 建立迭代格式 向量X(0)事先給定，稱為初始解向量，用公式逐步迭代求解的方法叫做迭

2、代法. 如果由產(chǎn)生的序列 收斂，則稱迭代法是收斂的，否則稱為迭代法發(fā)散. XBXg(1)( )(0,1,)kkkXBXg( )1kkXn若將方程組改寫為), 2 , 1(1nibxanjijij), 2 , 1()(11nixabaxnijjjijiiii0iia 1Jacobi迭代法n建立迭代格式其中(1)( )11()(1,2, ;0,1,2,)nkkiiijjjiij ixba xinka( )( )( )( )12(,)kkkkTnxxxXJacobi迭代法的矩陣表示n將方程組AX=b的系數(shù)A分解成 A=D+L+U其中D=diag(a11,a22,ann) ，L和U分別是A的對角線下方

3、元素和上方元素組成的嚴(yán)格下三角陣與嚴(yán)格上三角陣. 即000000000000000000211222112121nnnnnnaaaaaaaaaA()DXLU Xb()DLU Xb()DXLU Xb AXb11()XDLU XD b 迭代格式為：(1)1( )1()kkXDLU XD b (1)1( )1()kkXID A XD b對應(yīng)的分量表示形式為：(1)( )( )11()(1,2, ;0,1,2,)nkkkiiijjijiixxa xbinka另外一種矩陣形式是：的Jacobi迭代格式（三種）123121322531272xxxxxxx 寫出方程組122130207系數(shù)矩陣為：02200

4、0000U000100200L 100030007D(1)1()1(1)1()1()X(IDA )XDbkkkkXDLUXDb 迭 代 格 式 為 ：或 者Matlab計算過程如下： A=1 -2 2;-1 3 0;2 0 7A = 1 -2 2 -1 3 0 2 0 7 U=triu(A,1)U = 0 -2 2 0 0 0 0 0 0 L=tril(A,-1)L = 0 0 0 -1 0 0 2 0 0 D=diag(diag(A)D = 1 0 0 0 3 0 0 0 7 -inv(D)*(L+U)ans = 0 2.000000000000000 -2.000000000000000

5、0.333333333333333 0 0 -0.285714285714286 0 0 b=5;-1;2;inv(D)*bans = 5.000000000000000 -0.333333333333333 0.285714285714286 I=eye(3)I = 1 0 0 0 1 0 0 0 1 I-inv(D)*Aans = 0 2.000000000000000 -2.000000000000000 0.333333333333333 0 0 -0.285714285714286 0 0分量形式為:1232133125( 22)1( 1 (0)31(2(20)7xxxxxxxxx

6、(1)( )( )123(1)( )( )213(1)( )( )3125( 22)1( 1 (0)31(2(20)7kkkkkkkkkxxxxxxxxx Gauss-Seidel迭代法方程組改寫為：()LD XUXb 11()()XLDUXLDb 即得迭代格式：(1)1( )1()()kkXLDUXLDb Gauss-Seidel迭代法n迭代格式的分量形式：其中 1(1)(1)( )111()(1,2, ;0,1,2,)inkkkiiijjijjjj iiixba xa xinka ( )( )( )( )12(,)kkkkTnxxxX的Gauss-Seidel迭代格式（兩種）1231213

7、22531272xxxxxxx 寫出方程組例n 分別用Jacobi迭代法與Gauss-Seidel迭代法求解方程組精確到小數(shù)點后四位，并要求分別寫出其迭代法的分量形式和矩陣形式. 123123123202324812231530 xxxxxxxxx解n（1）用Jacobi迭代法，其迭代法的分量形式為(1)( )( )( )( )12323(1)( )( )( )( )21313(1)( )( )( )( )312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxx

8、xxxxxk迭代法的矩陣形式為其中 (1)1( )1()kkXID A XD b1100201 0 0202300.10.1510 1 0001810.12500.12580 0 123 150.13330.2010015ID A 11241.2201121.58130215Db(1)( )11(2)( )22(1)( )3300.10.151.20.12500.1251.50.13330.202.0kkkkkkxxxxxx 取初值X(0) =(0,0,0)，迭代可得(1)(2)(3)(4)(5)(6)(1.200 000,1.500 000,2.000 000) ,(0.750 000,1.

9、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,2TTTTTXXXXXX(7).125356) ,(0.767 355,1.138 410,2.125368) ,TTX迭代7次，得近似值. n（2）用Gauss-Seidel迭代法，其迭代法的分量形式為(0.767 355,1.138 410,2.125368)TX(1)( )( )( )( )12323(1)(1)( )(1

10、)( )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其迭代法的矩陣形式為其中(1)1( )1()()kkXDLUXDLb 1110020200011()1800160823 1519112 4004015DL 11002002311()0001160800019112 400401500.10.1500.01250.106 2500.1583330.00125 DLU 110020241.211()

11、0121.351608302.11191124004015DLb即 取初值X(0) =(0,0,0)，迭代可得(1)( )11(1)( )22(1)( )3300.10.151.200.01250.106251.350 0.1583330.001252.11kkkkkkxxxxxx迭代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 3

12、56,1.138 410,2.125368) .XXXXXTTTTT(0.767 356,1.138 410,2.12537)XT 向量和矩陣的模（范數(shù)）n為了研究線性方程組近似解的誤差估計和迭代法的收斂性，我們需要對Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，向量和矩陣的范數(shù)。向量和矩陣的范數(shù)n在一維數(shù)軸上，實軸上任意一點x到原點的距離用|x|表示。而任意兩點x1，x2之間距離用| x1-x2 |表示。向量和矩陣的范數(shù)n而在二維平面上，平面上任意一點P(x,y)到原點的距離用 表示。而平面上任意兩點P1(x1,y1),P2(x2,y2)的距離用 表示。 推廣到n維空間

13、，則稱為向量范數(shù)。|22OPyx22122121)()(|yyxxPP向量范數(shù),|,:1)|00|0;2)| |,;3),| |nnRkkkRRxxxxxxxxxx yxyxy設(shè)任一向量按某一確定的法則對應(yīng)于一非負實數(shù)且滿足非負性：，當(dāng)且僅當(dāng)時，奇次性：三角不等式：對任意都有，則稱為向量 的范數(shù)。常見的向量范數(shù)121112221111( ,.,)|( ,1)|(| )( ,2)( )|(| )( , )|max|( ,inf)Tnniiniinpppiiii nx xxxnorm xxnorm xornorm xxnorm x pxnorm xxxxxx 設(shè)向量對 同 一 向 量 來 說 ，

14、采 用 不 同 的 范 數(shù) ， 值 一 般 是 不 同 的 ，但 下 面 的 性 質(zhì) 告 訴 我 們 ， 有 限 維 向 量 的 模 是 相 互 等 價 的 ，所 以 在 討 論 向 量 序 列 收 斂 時 ， 可 采 用 任 意 一 種 范 數(shù) 。向量范數(shù)性質(zhì)R| | ,| | ,|nnm MmMRxxx 性質(zhì) 對中定義的任意兩種范數(shù)則必存在兩正數(shù)使得*limlim| 0kkkkx xx x例已知12(1,2, 3, 4),xxxx求 矩陣范數(shù),|,:1):| 00| 0;2)| |;3)| |,;4),|n nn nn nn nARAAAAkAkAkRABABA BRABABA BRAR定

15、義 設(shè)任意若按某一確定的法則對應(yīng)于一非負實數(shù)且滿足非負性，當(dāng)且僅當(dāng)時，奇次性：，三角不等式：相容性：，則稱為的一種范數(shù)。相容范數(shù)|,|,| | |nn nxARRAxAxAx定義設(shè)分別為和的一種范數(shù) 如果則稱該矩陣范數(shù)與此向量范數(shù)是相容的。算子范數(shù)（了解）0| | 1,|,| maxmax |,nn nnxxn nxRARRxAxAAxxR定理設(shè)并在上定義向量范數(shù)則為上的矩陣范數(shù) 且稱其為算子范數(shù)。算子范數(shù)（了解）0|1|1)| max0| 0,| 00,0n nxAAAARRAAAAAxxx xxxxx證明(了解)：由向量范數(shù)的連續(xù)性知，在有界閉集上一定能達到最大值所以定義了到的一個對應(yīng)法則

16、。所以下面只要驗證范數(shù)定義的四個條件。顯然成立，若則，因為只有可能。算子范數(shù)（了解）|)|(|)(|max|) 3|max|max|)2000 xxxxxxxxxxxxxxxBABABABARAAAAAkAkkAkAnxxx于是，則由算子范數(shù)（了解）1|max|,|)(|max|)(|010 xxIxIIRBAABBAxxBABABAxxBAnnx則為單位矩陣中任何矩陣算子范數(shù)對推論。同理可證即有所以對常見的矩陣范數(shù)1111|maxnijj niAa 范數(shù)：2max2|()TAAA范數(shù)：11|max|niji njAa 范數(shù)：列范數(shù)行范數(shù)譜范數(shù)例題112221,| (1,2,)24:|max2

17、 | 2|,| 1| 45|max2 | 1|,| 2| 46222181014241017810|0101723.466,1.534|23.4664.84pTTAApAAA AIA AA 例設(shè)矩陣求解因為由解得，故4。nMatlab計算過程如下：2范數(shù)： norm(A)1范數(shù)： norm(A,1)無窮范數(shù)： norm(A,inf) 矩陣的譜半徑11 2,( )max|( ),iii n(i, ,.,n)AAAAAAA 定義設(shè)為矩陣 的特征值 則稱為矩陣 的譜半徑。矩陣 的譜半徑不是 的一種范數(shù)但可能與 的任何一種范數(shù)有某種關(guān)系。例題33)(33,3304212|421221AAIA所以。特征

18、值得：解：由的譜半徑。求矩陣求特征值命令eig(A)2,(1)( ) |,|;(2),( ) |1,0( )maxn nTARAAAAAAAAAAAAAAAxxxxxxxx定理 設(shè)則這里為 的任意一種范數(shù)若則。證明 （ ）設(shè)為矩陣 的任一特征對，即則由于，故有由 的任意性，有。2max12(2)|( )|( )21, ( )33,|5,|6,24|4.844,( ) |TpAAAAAAAAAAAA因為，故。顯然所以。例2120121 ,A011TA 矩陣求（A）（A）,（A A），解：A的特征值為：lm=eig(A)lm = 1.500000000000000 + 1.658312395177

19、701i 1.500000000000000 - 1.658312395177701i 1.000000000000000 ( )A為：norm(lm,inf)ans = 2.236067977499790AA 的特征值為： lm1=eig(A*A)lm1 = 0.936075017171059 2.921124938072438 9.1428000447564982A為 ：sqrt( 9.142800044756498)ans = 3.023706342348162迭代法的收斂性n定理（迭代法的基本收斂定理） 迭代過程 X(k+1) =BX(k) +g對于任意初始向量X(0)及右端向量g均收斂的充要條件是迭代矩陣B的譜半徑(B)1, 并且(B) 愈小，收斂速度愈快. n定理（迭代法收斂的充分條件） 若迭代法 X(k+1) =BX(k) +g的迭代矩陣B滿足，B=q1,則對于任意的初始向量X(0)與右端向量g迭代法收斂.證明n證 設(shè)X*為方程組X=BX+g的精確解,則 X* =BX* +g X* -