線性方程組的解法講課適用

1、線性方程組的解法線性方程組的解法解線性方程組的迭代法解線性方程組的迭代法iterative methods for linear systemsjacobi迭代和迭代和gauss-seidel迭代迭代迭代法的矩陣表示迭代法的矩陣表示matrix form of the iterative methods1優(yōu)選課堂線性方程組的解法在計(jì)算數(shù)學(xué)中占有極其線性方程組的解法在計(jì)算數(shù)學(xué)中占有極其重要的地位。重要的地位。線性方程組的解法大致分為線性方程組的解法大致分為迭代法迭代法與與直接直接法法兩大類兩大類雅可比雅可比(jacobi)迭代法迭代法舉例說明雅可比迭代法的基本思路舉例說明雅可比迭代法的基本思路

2、131581079321321321xxxxxxxxx例例4.1特點(diǎn)特點(diǎn):系數(shù)矩陣主系數(shù)矩陣主對(duì)角元均不為零對(duì)角元均不為零2優(yōu)選課堂 15/ )13(10/ )8(9/ )7(213312321xxxxxxxxx取迭代初值取迭代初值x1(0) =0， x2(0) =0， x3(0) =0將方程改寫成如下等價(jià)形式將方程改寫成如下等價(jià)形式據(jù)此建立迭代公式據(jù)此建立迭代公式 15/ )13(10/ )8(9/ )7()()()1()()()1()()()1(213312321kkkkkkkkkxxxxxxxxx3優(yōu)選課堂 x(0) 0 0 0 x(1) 0.7778 0.8000 0.8667 x(2

3、)0.96300.96440.9778 x(3)0.99290.99350.9952 x(4) 0.99870.99880.9991x1* 1.0000，x2* 1.0000，x3* 1.0000準(zhǔn)確解準(zhǔn)確解可以看出，迭代每前進(jìn)一步，結(jié)果就逼近準(zhǔn)確解一步可以看出，迭代每前進(jìn)一步，結(jié)果就逼近準(zhǔn)確解一步 迭代過程收斂迭代過程收斂4優(yōu)選課堂矩陣形式矩陣形式: 15/1310/89/7015/115/110/1010/19/19/10)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxxfbxx)()1( kk以上這種迭代方法稱雅可比以上這種迭代方法稱雅可比(jacobi)迭代法。迭代法。

4、基本思想：基本思想：將方程組的求解問題轉(zhuǎn)化為重復(fù)將方程組的求解問題轉(zhuǎn)化為重復(fù)計(jì)算一組彼此獨(dú)立的線性表達(dá)式。計(jì)算一組彼此獨(dú)立的線性表達(dá)式。5優(yōu)選課堂 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(i = 1,2, ,n; k=0,1,2, ) nijkjijijkjijiiikixaxabax1)(11)()1(1injjijbxa 1(i = 1,2, ,n)設(shè)有方程組設(shè)有方程組將第將第i個(gè)方程的第個(gè)方程的第i個(gè)變量個(gè)變量xi分離出來，據(jù)此建立分量形式分離出來，據(jù)此建立分量形式的的雅可比迭代公式雅可比迭代公式如果如果迭代發(fā)散迭代發(fā)散否則

5、否則迭代收斂迭代收斂*)(limikikxx 6優(yōu)選課堂用矩陣形式來表示雅可比迭代公式用矩陣形式來表示雅可比迭代公式設(shè)有方程組設(shè)有方程組: ax = b 其中其中a(aij)n為非奇異矩陣，為非奇異矩陣，x=(x1, x2, , xn)t, b=(b1, b2, , bn)t，唯一解為，唯一解為x*=(x1*, x2*, , xn*)t將將a分解為：分解為：au+d+l其中其中 0000u2112nnaaa nnaaa00d2211 0000l2121nnaaa7優(yōu)選課堂于是于是 (u+d+l)x = b得得 x d (u+l)x +db據(jù)此得矩陣形式的據(jù)此得矩陣形式的雅可比迭代公式雅可比迭代

6、公式 x(k+1)d(u+l)x(k) +db記記 bd (u+l)， f db有有b：迭代矩陣迭代矩陣( k=0,1,2, )x(k+1)= bx(k) + f任取任取 x(0), 迭代計(jì)算產(chǎn)生向量序列迭代計(jì)算產(chǎn)生向量序列:若若*lim)(xxkk 則迭代過程收斂。則迭代過程收斂。x* 是方程組是方程組 ax = b 的解的解x(1), x(2), x(k),8優(yōu)選課堂9優(yōu)選課堂迭代法適用于解迭代法適用于解大型稀疏方程組大型稀疏方程組(萬階以上的方程組萬階以上的方程組,系數(shù)矩陣中零元素占很系數(shù)矩陣中零元素占很大比例大比例,而非零元按某種模式分布而非零元按某種模式分布)背景背景: 電路分析、邊

7、值問題的數(shù)值解和數(shù)學(xué)物電路分析、邊值問題的數(shù)值解和數(shù)學(xué)物理方程理方程問題問題: (1)如何構(gòu)造迭代格式？如何構(gòu)造迭代格式？ (2)迭代格式是否收斂？迭代格式是否收斂？ (3)收斂速度如何？收斂速度如何？ (4)如何進(jìn)行誤差估計(jì)？如何進(jìn)行誤差估計(jì)？10優(yōu)選課堂高斯塞德爾高斯塞德爾gauss-seidel迭代法迭代法gauss-seidel迭代法是通過對(duì)迭代法是通過對(duì)jacobi迭代法稍加改迭代法稍加改進(jìn)得到的。進(jìn)得到的。jacobi迭代法的每一步迭代新值迭代法的每一步迭代新值 x(k+1)=x1(k+1),x2(k+1) , ,xn(k+1)t 都是用前一步的舊值都是用前一步的舊值 x(k)=x

8、1(k),x2(k) , ,xn(k)t的全部分量計(jì)算出來的。那么在計(jì)算第的全部分量計(jì)算出來的。那么在計(jì)算第i個(gè)分量個(gè)分量xi(k+1) 時(shí)，已經(jīng)計(jì)算出時(shí)，已經(jīng)計(jì)算出 x1(k+1),x2(k+1) , ,xi-1(k+1) (i-1)個(gè)個(gè)分量，這些分量新值沒用在計(jì)算分量，這些分量新值沒用在計(jì)算xi(k+1) 上。將這些上。將這些11優(yōu)選課堂injjijbxa 1(i = 1,2,n) nijkjijijkjijiiikixaxabax1)(11)1()1(1(i = 1,2,n; k =0,1,2,)將這些分量利用起來，有可能得到一個(gè)收斂更將這些分量利用起來，有可能得到一個(gè)收斂更快的迭代公式

9、?？斓牡健＞唧w作法：將分量形式的雅可比迭代公式右端具體作法：將分量形式的雅可比迭代公式右端前前(i-1)個(gè)分量的上標(biāo)為個(gè)分量的上標(biāo)為k換成換成k+1，即，即分量形式的分量形式的高斯高斯-塞德爾迭代公式塞德爾迭代公式。12優(yōu)選課堂用矩陣形式來表示高斯用矩陣形式來表示高斯-塞德爾迭代公式塞德爾迭代公式dx(k+1)b-lx(k+1) - ux(k)即即 (d+l)x(k+1) -ux(k)+b如果如果 (d+l)存在，則存在，則 x(k+1) (d+l) ux(k)+ (d+l) b記記 b(d+l)， f (d+l) b則則( k=0,1,2,)x(k+1)= bx(k) + f矩陣形式的

10、矩陣形式的高斯高斯-塞德爾迭代公式。塞德爾迭代公式。b：迭代矩陣迭代矩陣13優(yōu)選課堂例例 131581079321321321xxxxxxxxx15/ )13()(2)(1)1(3kkkxxx 15/1310/89/7015/115/110/1010/19/19/10)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxx9/ )7()(3)(2)1(1kkkxxx 10/ )8()(3)(1)1(2kkkxxx 15/ )13(10/ )8(9/ )7(213312321xxxxxxxxx 000)0(3)0(2)0(1xxx14優(yōu)選課堂例例 131581079321321321x

11、xxxxxxxx15/ )13()1(2)1(1)1(3 kkkxxx 15/1310/89/700010/1009/19/10115/115/10110/1001)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxx9/ )7()(3)(2)1(1kkkxxx 10/ )8()(3)1(1)1(2kkkxxx 15/ )13(10/ )8(9/ )7(213312321xxxxxxxxx 000)0(3)0(2)0(1xxx15優(yōu)選課堂 15/1310/89/7135/21350/109/190/109/19/1015/1310/89/700010/1009/19/10115/1

12、150/110110/100115/1310/89/700010/1009/19/10115/115/10110/1001)(3)(2)(1)(3)(2)(1)(3)(2)(1)1(3)1(2)1(1kkkkkkkkkkkkxxxxxxxxxxxx16優(yōu)選課堂jacobi迭代算法迭代算法a=9 -1 -1;-1 10 -1;-1 -1 15;b=7;8;13;x=0;0;0;er=1;k=0;while er0.00005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+a(i,j)*x(j); end x(i)=t; y(i)=(

13、b(i)-s)/a(i,i); er=max(abs(x(i)-y(i),er); end x=y;xend 131581079321321321xxxxxxxxx0.7778 0.8000 0.86670.9630 0.9644 0.97190.9929 0.9935 0.99520.9987 0.9988 0.99910.9998 0.9998 0.99981.0000 1.0000 1.00001.0000 1.0000 1.000017優(yōu)選課堂gauss-seidel迭代算法迭代算法 131581079321321321xxxxxxxxxa=9 -1 -1;-1 10 -1;-1 -1

14、 15;b=7;8;13;x=0;0;0;er=1;k=0;while er0.00005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+a(i,j)*x(j); end x(i)=(b(i)-s)/a(i,i); er=max(abs(x(i)-t),er); end xend 0.7778 0.8778 0.9770 0.9839 0.9961 0.9987 0.9994 0.9998 0.9999 1.0000 1.0000 1.0000 1.0000 1.0000 1.000018優(yōu)選課堂從計(jì)算結(jié)果可以明顯看出，從計(jì)算結(jié)果

15、可以明顯看出，gauss-seidel迭代迭代法比法比jacobi迭代法效果好。迭代法效果好。一般而言，一般而言， gauss-seidel迭代法收斂速度比迭代法收斂速度比jacobi迭代法快，但這兩種迭代法的收斂范圍迭代法快，但這兩種迭代法的收斂范圍并不完全重合，而只是部分相交，有的時(shí)候并不完全重合，而只是部分相交，有的時(shí)候jacobi迭代法可能比迭代法可能比gauss-seidel迭代法收斂速迭代法收斂速度更快。甚至可以舉出度更快。甚至可以舉出jacobi迭代法收斂而迭代法收斂而gauss-seidel迭代法發(fā)散的例子。迭代法發(fā)散的例子。19優(yōu)選課堂gauss-seidel迭代法和迭代法和

16、jacobi迭代法的異同：迭代法的異同：jacobi迭代法：公式簡(jiǎn)單，每次只需做矩陣和向量的迭代法：公式簡(jiǎn)單，每次只需做矩陣和向量的 一次乘法；特別適合于并行計(jì)算；一次乘法；特別適合于并行計(jì)算；不足之處：需存放不足之處：需存放x(k)和和x(k+1)兩個(gè)存儲(chǔ)空間。兩個(gè)存儲(chǔ)空間。gauss-seidel迭代法：只需一個(gè)向量存儲(chǔ)空間，一旦迭代法：只需一個(gè)向量存儲(chǔ)空間，一旦計(jì)算出了計(jì)算出了xj(k+1)立即存入立即存入xj(k)的位置，可節(jié)約一套存儲(chǔ)單的位置，可節(jié)約一套存儲(chǔ)單元元 ；有時(shí)起到加速收斂的作用。；有時(shí)起到加速收斂的作用。是一種典型的串行算法，每次迭代中必須依次計(jì)算解是一種典型的串行算法，

17、每次迭代中必須依次計(jì)算解的各個(gè)分量。的各個(gè)分量。20優(yōu)選課堂超松馳超松馳(sor)迭代法迭代法超松馳迭代法是迭代方法的一種加速方法，其計(jì)超松馳迭代法是迭代方法的一種加速方法，其計(jì)算公式算公式 簡(jiǎn)單，但需要選擇合適的松馳因子，以保簡(jiǎn)單，但需要選擇合適的松馳因子，以保證迭代過程有較快的收斂速度。證迭代過程有較快的收斂速度。設(shè)有方程組設(shè)有方程組 ax = b 其中其中a(aij)n為非奇異矩陣，為非奇異矩陣，x=(x1, x2, , xn)t, b=(b1, b2, , bn)t，記，記x(k)為第為第k步迭代近似值，則步迭代近似值，則 r(k) = b ax(k）表示近似解表示近似解x(k)的殘余

18、誤差，引進(jìn)如下形式的加速迭的殘余誤差，引進(jìn)如下形式的加速迭代公式代公式21優(yōu)選課堂 x(k+1) x(k)+w(b ax)w稱作松馳因子。其分量形式為稱作松馳因子。其分量形式為選擇適當(dāng)?shù)乃神Y因子，可期望獲得較快的收斂速度。選擇適當(dāng)?shù)乃神Y因子，可期望獲得較快的收斂速度。如果在計(jì)算分量如果在計(jì)算分量xi(k+1) 時(shí)，考慮利用已經(jīng)計(jì)算出來時(shí)，考慮利用已經(jīng)計(jì)算出來的分量的分量x1(k+1),x2(k+1) , ,xi-1(k+1) ，又可得到一個(gè)新的，又可得到一個(gè)新的迭代公式迭代公式特別當(dāng)特別當(dāng)aii0時(shí)，將上面迭代公式應(yīng)用于方程組時(shí)，將上面迭代公式應(yīng)用于方程組1)()()1( njkjijikik

19、ixabwxx(i=1,2, n) nijkjijijkjijikikixaxabwxx)(11)1()()1(iiinjjiiijabxaa 122優(yōu)選課堂由此得下列由此得下列超松馳超松馳(sor)迭代公式迭代公式)(11)1()()1( nijkjijijkjijiiikikixaxabaxx (i=1,2, n; k = 0,1,2,3, )當(dāng)當(dāng)w1時(shí)，稱超松馳法；當(dāng)時(shí)，稱超松馳法；當(dāng)w1時(shí)，稱低松時(shí)，稱低松馳法；當(dāng)馳法；當(dāng)w1時(shí)，就是時(shí)，就是gauss-seidel迭代公迭代公式。式。所以超松馳所以超松馳(sor)迭代法可以看成是迭代法可以看成是gauss-seidel迭代法的加速，而

20、迭代法的加速，而gauss-seidel迭代法迭代法是超松馳方法的特例。是超松馳方法的特例。23優(yōu)選課堂定理定理4.8 若若a是對(duì)稱正定矩陣是對(duì)稱正定矩陣,則當(dāng)則當(dāng)0w2時(shí)時(shí)sor迭代法解方程組迭代法解方程組 ax = b 是收斂的是收斂的定理定理4.9 若若a是嚴(yán)格對(duì)角占優(yōu)矩陣是嚴(yán)格對(duì)角占優(yōu)矩陣,則當(dāng)則當(dāng)0w0.0005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+a(i,j)*x(j); end x(i)=(1-w)*t+w*(b(i)-s)/a(i,i); er=max(abs(x(i)-t),er); endendkk=

21、10 x= 1.1999 1.3999 1.5999=1.2,只需只需k=625優(yōu)選課堂 塊迭代法簡(jiǎn)介塊迭代法簡(jiǎn)介設(shè)設(shè) arnn, xrn, brn將方程組將方程組a x = b中系數(shù)矩陣中系數(shù)矩陣a分塊分塊 rrrrrrrrbbbxxxaaaaaaaaa2121212222111211其中其中, aiirnini, aijrninj , xirni, birni26優(yōu)選課堂將將a分解分解, a = db lb ub (1)jacobi塊迭代塊迭代 db x(k+1) = (lb + ub)x(k) + b ijkjijikiiixabxa)() 1(i=1,2, r(2)gauss-seid

22、el塊迭代塊迭代 db x(k+1) = lb x(k+1)+ ubx(k) + b rijkjijijkjijikiiixaxabxa1)(11)1()1(i=1,2, r27優(yōu)選課堂迭代法的收斂性迭代法的收斂性convergence of iterative method迭代矩陣譜半徑迭代矩陣譜半徑spectral radius對(duì)角占優(yōu)矩陣對(duì)角占優(yōu)矩陣diagonally dominant matrix 28優(yōu)選課堂原始方程原始方程: ax = b迭代格式迭代格式: x(k+1) = bx(k) + f定理定理4.1(迭代法基本定理迭代法基本定理) 迭代法迭代法 x(k+1) = bx(k

23、) + f收斂的收斂的充要條件充要條件是是 (b) 1迭代法有著算法簡(jiǎn)單，程序設(shè)計(jì)容易以及可節(jié)迭代法有著算法簡(jiǎn)單，程序設(shè)計(jì)容易以及可節(jié)省計(jì)算機(jī)存貯單元等優(yōu)點(diǎn)。但是迭代法也存在省計(jì)算機(jī)存貯單元等優(yōu)點(diǎn)。但是迭代法也存在著收斂性和收斂速度等方面的問題。因此弄清著收斂性和收斂速度等方面的問題。因此弄清楚迭代法在什么樣的條件下收斂是至關(guān)重要的。楚迭代法在什么樣的條件下收斂是至關(guān)重要的。29優(yōu)選課堂證證 對(duì)任何對(duì)任何 n 階矩陣階矩陣b都存在非奇矩陣都存在非奇矩陣p使使 b = p 1 j p其中其中, j 為為b的的 jordan 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型nnrjjjj 21iinniiij 11其中其中, ji

24、為為jordan塊塊其中其中,i 是矩陣是矩陣b的特征值的特征值, 由由 b = p 1 j p30優(yōu)選課堂b k = (p 1 j p) (p 1 j p) (p 1 j p)= p 1 j k p迭代法迭代法 x(k+1) = bx(k) + f收斂收斂 0blim kk0jlim kk0lim kik (i = 1, 2, r)1| i (i = 1, 2, r)1|max1 iri 譜半徑譜半徑 (b) 131優(yōu)選課堂1005-1.2604e)b( j 例例 線性方程組線性方程組 ax = b, 分別取系數(shù)矩陣為分別取系數(shù)矩陣為 122111221a1 211111112a2試分析試分

25、析jacobi 迭代法和迭代法和 seidel 迭代法的斂散性迭代法的斂散性 022101220jb(1)32優(yōu)選課堂 200320220sb12)( sb (2) a2=2, -1, 1; 1, 1, 1; 1, 1, -2 02/12/11012/12/10jb11180. 1)( jb 33優(yōu)選課堂 2/1002/12/102/12/10sb12/1)( sb 兩種迭代法之間沒有直接聯(lián)系兩種迭代法之間沒有直接聯(lián)系對(duì)矩陣對(duì)矩陣a1,求求a1x = b 的的jacobi迭代法收斂迭代法收斂,而而gauss-seidel迭代法發(fā)散迭代法發(fā)散;對(duì)矩陣對(duì)矩陣a2,求求a2x = b 的的jacobi迭代法發(fā)散迭代法發(fā)散,而而gauss-seidel迭代法收斂迭代法收斂.34優(yōu)選課堂證證 由由 (k) = b (k-1),得得 | (k)| | b| | (k-1)| (k = 1, 2, 3, )