線性方程組的解法.ppt

1、線性方程組的解法,解線性方程組的迭代法 Iterative Methods for Linear Systems Jacobi迭代和Gauss-Seidel迭代 迭代法的矩陣表示 Matrix form of the Iterative Methods,線性方程組的解法在計(jì)算數(shù)學(xué)中占有極其重要的地位。 線性方程組的解法大致分為迭代法與直接法兩大類,雅可比(Jacobi)迭代法,舉例說明雅可比迭代法的基本思路,例4.1,特點(diǎn):系數(shù)矩陣主對角元均不為零,取迭代初值x1(0) =0， x2(0) =0， x3(0) =0,將方程改寫成如下等價(jià)形式,據(jù)此建立迭代公式,x(0) 0 0 0,x(1) 0

2、.7778 0.8000 0.8667,x(2) 0.9630 0.9644 0.9778,x(3) 0.9929 0.9935 0.9952,x(4) 0.9987 0.9988 0.9991,x1* 1.0000，x2* 1.0000，x3* 1.0000,準(zhǔn)確解,可以看出，迭代每前進(jìn)一步，結(jié)果就逼近準(zhǔn)確解一步 迭代過程收斂,矩陣形式:,以上這種迭代方法稱雅可比(Jacobi)迭代法。 基本思想：將方程組的求解問題轉(zhuǎn)化為重復(fù)計(jì)算一組彼此獨(dú)立的線性表達(dá)式。,(i = 1,2, ,n; k=0,1,2, ),(i = 1,2, ,n),設(shè)有方程組,將第i個(gè)方程的第i個(gè)變量xi分離出來，據(jù)此建立

3、分量形式的雅可比迭代公式,如果,用矩陣形式來表示雅可比迭代公式,設(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 其中,于是 (U+D+L)X = b 得 X D (U+L)X +Db 據(jù)此得矩陣形式的雅可比迭代公式 X(k+1)D(U+L)X(k) +Db 記 BD (U+L)， f Db 有 B：迭代矩陣,任取 X(0), 迭代計(jì)算產(chǎn)生向量序列:,若,則迭代過程收斂。x* 是方程組 Ax = b 的解,X(1), X(2), X(

4、k),迭代法適用于解大型稀疏方程組,(萬階以上的方程組,系數(shù)矩陣中零元素占很大比例,而非零元按某種模式分布),背景: 電路分析、邊值問題的數(shù)值解和數(shù)學(xué)物理方程,問題: (1)如何構(gòu)造迭代格式？ (2)迭代格式是否收斂？ (3)收斂速度如何？ (4)如何進(jìn)行誤差估計(jì)？,高斯塞德爾Gauss-Seidel迭代法,Gauss-Seidel迭代法是通過對Jacobi迭代法稍加改進(jìn)得到的。 Jacobi迭代法的每一步迭代新值 x(k+1)=x1(k+1),x2(k+1) , ,xn(k+1)T 都是用前一步的舊值 x(k)=x1(k),x2(k) , ,xn(k)T 的全部分量計(jì)算出來的。那么在計(jì)算第i

5、個(gè)分量xi(k+1) 時(shí)，已經(jīng)計(jì)算出 x1(k+1),x2(k+1) , ,xi-1(k+1) (i-1)個(gè)分量，這些分量新值沒用在計(jì)算xi(k+1) 上。將這些,(i = 1,2,n),(i = 1,2,n; k =0,1,2,),將這些分量利用起來，有可能得到一個(gè)收斂更快的迭代公式。 具體作法：將分量形式的雅可比迭代公式右端前(i-1)個(gè)分量的上標(biāo)為k換成k+1，即,分量形式的高斯-塞德爾迭代公式。,用矩陣形式來表示高斯-塞德爾迭代公式,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(

6、k)+ (D+L) b 記 B(D+L)， f (D+L) b 則,矩陣形式的高斯-塞德爾迭代公式。 B：迭代矩陣,例,例,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)=(b(i)-s)/A(i,i); er=max(abs(x(i)-y(i),er); end x=y;x end,0.7778 0.800

7、0 0.8667 0.9630 0.9644 0.9719 0.9929 0.9935 0.9952 0.9987 0.9988 0.9991 0.9998 0.9998 0.9998 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000,Gauss-Seidel迭代算法,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

8、)=(b(i)-s)/A(i,i); er=max(abs(x(i)-t),er); end x end,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.0000,從計(jì)算結(jié)果可以明顯看出，Gauss-Seidel迭代法比Jacobi迭代法效果好。 一般而言， Gauss-Seidel迭代法收斂速度比Jacobi迭代法快，但這兩種迭代法的收斂范圍并不完全重合，而只是部分相交，有的時(shí)候Jacobi迭代法可能比Gauss-Seidel迭代法收斂速度更

9、快。甚至可以舉出Jacobi迭代法收斂而Gauss-Seidel迭代法發(fā)散的例子。,Gauss-Seidel迭代法和Jacobi迭代法的異同： Jacobi迭代法：公式簡單，每次只需做矩陣和向量的 一次乘法；特別適合于并行計(jì)算； 不足之處：需存放X(k)和X(k+1)兩個(gè)存儲空間。 Gauss-Seidel迭代法：只需一個(gè)向量存儲空間，一旦計(jì)算出了xj(k+1)立即存入xj(k)的位置，可節(jié)約一套存儲單元 ；有時(shí)起到加速收斂的作用。 是一種典型的串行算法，每次迭代中必須依次計(jì)算解的各個(gè)分量。,超松馳(SOR)迭代法,超松馳迭代法是迭代方法的一種加速方法，其計(jì)算公式 簡單，但需要選擇合適的松馳因

10、子，以保證迭代過程有較快的收斂速度。 設(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)的殘余誤差，引進(jìn)如下形式的加速迭代公式,X(k+1) X(k)+w(b AX) w稱作松馳因子。其分量形式為 選擇適當(dāng)?shù)乃神Y因子，可期望獲得較快的收斂速度。如果在計(jì)算分量xi(k+1) 時(shí)，考慮利用已經(jīng)計(jì)算出來的分量x1(k+1),x2(k+1) , ,xi-1(k+1) ，又可得到一個(gè)新的迭代公式 特別當(dāng)aii0時(shí)，將上面迭代公式應(yīng)用于方程組,

11、(i=1,2, n),由此得下列超松馳(SOR)迭代公式,(i=1,2, n; k = 0,1,2,3, ),當(dāng)w1時(shí)，稱超松馳法；當(dāng)w1時(shí)，稱低松馳法；當(dāng)w1時(shí)，就是Gauss-Seidel迭代公式。 所以超松馳(SOR)迭代法可以看成是Gauss-Seidel迭代法的加速，而Gauss-Seidel迭代法是超松馳方法的特例。,定理4.8 若A是對稱正定矩陣,則當(dāng)0w2時(shí)SOR迭代法解方程組 Ax = b 是收斂的,定理4.9 若A是嚴(yán)格對角占優(yōu)矩陣,則當(dāng)0w1時(shí)SOR迭代法解方程組 Ax = b 是收斂的,例4.3 用SOR方法解方程組(w=1.4),w=input(input: w:=)

12、; A=2 -1 0;-1 2 -1;0 -1 2; b=1;0;1.8; x=1;1;1; er=1;k=0; while er0.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); end end k,k=10 x= 1.1999 1.3999 1.5999,=1.2,只需k=6,塊迭代法簡介 設(shè) ARnn, xRn, bRn 將方程組A x = b中系數(shù)矩陣A分塊,其中, Ai

13、iRnini, AijRninj , xiRni, biRni,將A分解, A = DB LB UB,Jacobi塊迭代 DB x(k+1) = (LB + UB)x(k) + b,i=1,2, r,(2)Gauss-Seidel塊迭代 DB x(k+1) = LB x(k+1)+ UBx(k) + b,i=1,2, r,迭代法的收斂性 Convergence of iterative method 迭代矩陣譜半徑 Spectral radius 對角占優(yōu)矩陣 diagonally dominant matrix,原始方程: Ax = b,迭代格式: x(k+1) = Bx(k) + f,定理

14、4.1(迭代法基本定理) 迭代法 x(k+1) = Bx(k) + f收斂的充要條件是 (B) 1,迭代法有著算法簡單，程序設(shè)計(jì)容易以及可節(jié)省計(jì)算機(jī)存貯單元等優(yōu)點(diǎn)。但是迭代法也存在著收斂性和收斂速度等方面的問題。因此弄清楚迭代法在什么樣的條件下收斂是至關(guān)重要的。,證 對任何 n 階矩陣B都存在非奇矩陣P使 B = P 1 J P 其中, J 為B的 Jordan 標(biāo)準(zhǔn)型,其中, Ji 為Jordan塊,其中,i 是矩陣B的特征值, 由 B = P 1 J P,B k = (P 1 J P) (P 1 J P) (P 1 J P)= P 1 J k P,迭代法 x(k+1) = Bx(k) +

15、f收斂 ,(i = 1, 2, r),例 線性方程組 Ax = b, 分別取系數(shù)矩陣為,試分析Jacobi 迭代法和 Seidel 迭代法的斂散性,(1),(2) A2=2, -1, 1; 1, 1, 1; 1, 1, -2,兩種迭代法之間沒有直接聯(lián)系 對矩陣A1,求A1x = b 的Jacobi迭代法收斂,而Gauss-Seidel迭代法發(fā)散; 對矩陣A2,求A2x = b 的Jacobi迭代法發(fā)散,而Gauss-Seidel迭代法收斂.,證 由(k) = B (k-1),得 | (k)| | B| | (k-1)| (k = 1, 2, 3, ),所以,定理4.2(迭代收斂的充分條件)設(shè)有迭代公式 x(k+1) =Bx(k) +f，如果|B|1, 則對任意初始向量x(0)和任意f，迭代公式收斂。,| (k)| | B|k | (0)|,| B| 1,定義4.1 A=(aij)nn, 如果 則稱A為嚴(yán)格對角占優(yōu)陣.,例4.1,定理4.3 若A