解線性方程組的迭代法市公開課獲獎?wù)n件

1、第6章 解線性方程組迭代辦法6.1 迭代法基本概念6.2 雅可比迭代法與高斯-賽德爾迭代法6.3 超松弛迭代法6.4* 共軛迭代法第1頁第1頁其中A為非奇異矩陣, 當A為低階稠密矩陣時, 第5章討論選主元消去法是有效. 但對于大型稀疏矩陣方程組(A階數(shù)n很大104，但零元素較多), 利用迭代法求解是適當. 本章將簡介迭代法一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應(yīng)用很廣泛。 下面舉簡例，以便理解迭代法思想. 對線性方程組 Ax=b， (1.1) 6.1 迭代法基本概念6.1.1 引 言第2頁第2頁 例1 求解方程組記為Ax=b，其中此方程組準確解是x*=(3

2、,2,1)T. 現(xiàn)將(1.2)改寫為第3頁第3頁或?qū)憺閤=B0 x+f，其中第4頁第4頁 我們?nèi)稳〕跏贾?，比如取x(0)=(0, 0, 0)T. 將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組解，但普通不滿足)，得到新值x(1)=(x1(1), x2(1), x3(1)T=(3.5, 3, 3)T ，再將x(1)分量代入(1.3)式右邊得到 x(2)，重復(fù)利用這個計算程序，得到一向量序列和普通計算公式(迭代公式)第5頁第5頁簡寫為 x(k+1)=B0 x(k) +f，其中k表示迭代次數(shù)(k=0,1,2,). 迭代到第10次有第6頁第6頁從此例看出，由迭代法產(chǎn)生向量序列x(k)逐

3、步迫近方程組準確解是x*=(3,2,1)T. 即有 對于任何一個方程組x=Bx+f(由Ax=b變形得到等價方程組)，由迭代法產(chǎn)生向量序列x(k)是否一定逐步迫近方程組解x*呢？回答是不一定. 請同窗們考慮用迭代法解下述方程組但 x(k)并不是所有都收斂到解x*！第7頁第7頁對于給定方程組x=Bx+f，設(shè)有唯一解x*，則 x*=Bx*+f .(1.5)又設(shè)x(0)為任取初始向量, 按下述公式結(jié)構(gòu)向量序列 x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)其中k表示迭代次數(shù). 定義1 (1)對于給定方程組x=Bx+f , 用公式(1.6)逐步代入求近似解辦法稱為迭代法(或稱為一階定常迭

4、代法，這里B與k無關(guān)). B稱為迭代矩陣. (2) 假如limx(k) (k)存在(記為x*), 稱此迭代法收斂, 顯然x*就是方程組解, 不然稱此迭代法發(fā)散.第8頁第8頁 由上述討論，需要研究x(k)收斂性. 引進誤差向量 由(1.6)減去(1.5)式，得(k+1)=B(k) (k=0,1,2,)，遞推得 要考察x(k)收斂性，就要研究B在什么條件下有l(wèi)im(k)=0 (k)，亦即要研究B滿足什么條件時有Bk0(零矩陣) (k) . 第9頁第9頁6.1.2 向量序列與矩陣序列極限 定義2 設(shè)向量序列x(k)Rn, x(k)= (x1(k),xn(k)T,假如存在x= (x1, x2, , x

5、n)TRn，使則稱向量序列x(k)收斂于x ，記作顯然，其中為任一向量范數(shù).第10頁第10頁 定義3 設(shè)矩陣序列Ak=aij(k)Rnn及A=aijRnn,假如n2個數(shù)列極限存在，且有則稱矩陣序列Ak收斂于A ，記作例2 設(shè)有矩陣序列且設(shè)| |1，考察其極限.解 顯然，當| |(2) 用反證法，假定B有一個特性值,滿足|1,則存在x0,使Bx=x,由此可得|Bkx|= |k|x|,當k時Bkx不收斂于零向量. 由定理2可知(1)不成立，從而知| |1 ，即(2)成立. (1) limBk =0; (2) (B)1; (3)至少存在一個從屬矩陣范數(shù)| ，使|B|(3) 依據(jù)第5章定理18，對任意

6、 0，存在一個從屬范數(shù)| ，使|B|(B)+，由(2)有(B)0，可使|B|(1) 由(3) 給出矩陣范數(shù)|B|N 時有 證實 由第5章定理18，對一切k有另一方面對任意 0，記顯然有(B)N 時，由任意性即得定理結(jié)論.第15頁第15頁6.1.3 迭代法及其收斂性其中，A=(aij)Rnn為非奇異矩陣，下面研究如何建立解Ax=b迭代法. 設(shè)有線性方程組 Ax=b，其中，M為可選擇非奇異矩陣，且使Mx=d容易求解，普通選擇A某種近似，稱M為分裂矩陣. 將A分裂為 A=M-N. (1.9) 第16頁第16頁 于是，求解Ax=b轉(zhuǎn)化為求解Mx=Nx+b ，即求解從而可結(jié)構(gòu)一階定常迭代法：其中 B=M

7、-1N=M-1(M-A)=I-M-1A ， f=M-1b. 稱 B=I-M-1A為迭代法迭代矩陣，選取M矩陣，就得到解Ax=b各種迭代法. 下面給出迭代法(1.11)式收斂充足必要條件.也就是求解線性方程組 x=Bx+f. (1.10) 第17頁第17頁 定理5(一階定常迭代法基本定理) 給定線性方程組(1.10)及一階定常迭代法(1.11)式，對任意選取初始向量x(0)，迭代法(1.11)式收斂充足必要條件是矩陣B譜半徑(B)1.由定理2知limBk=0，再由定理3，即得(B)1. 證實 (=) 設(shè)(B)1，易知Ax=f(其中A=I-B)有唯一解，記為x*，則 x*=Bx*+f.誤差向量 (

8、k)=x(k)-x*=Bk(0), (0)=x(0)-x* .由設(shè)(B) 設(shè)對任意x(0)有l(wèi)imx(k)=x*, 其中x(k+1)=Bx(k)+f. 顯然, 極限x*是線性方程組(1.10)解, 且對任意x(0)有 (k)=x(k)-x*=Bk(0)0 (k) .第18頁第18頁 例3 考察線性方程組(1.2)給出迭代法(1.4)式收斂性. 解 先求迭代矩陣B0特性值. 由特性方程可得解得即(B0)1，這闡明用迭代法解此方程組不收斂.迭代法基本定理在理論上是主要，由于(B)|B|，下面利用矩陣B范數(shù)建立判別迭代法收斂充足條件.第20頁第20頁 定理6(迭代法收斂充足條件) 設(shè)有線性方程組x=

9、Bx+f， A=(aij)Rnn，及一階定常迭代法 x(k+1)=Bx(k)+f.假如有B某種算子范數(shù)|B|=q1，則(1) 迭代法收斂，即對任取x(0)有 limx(k)=x*，且 x*=Bx*+f.第21頁第21頁 證實 由基本定理知，結(jié)論(1)是顯然.(2) 顯然相關(guān)系式x*-x(k+1)=B(x*-x(k)及 x(k+1)-x(k)=B(x(k)-x(k-1).于是有重復(fù)利用即得(2). (4) 重復(fù)利用，則得到(4).(3) 考察即有第22頁第22頁注意，定理6只給出迭代法(1.11)式收斂充足性，即使條件|B|1對任何慣用范數(shù)均不成立，迭代序列仍也許收斂. 例5 迭代法x(k+1)

10、=Bx(k)+f ，其中顯然|B|=1.1, |B|1=1.2, |B|2=1.043, |B|F=(1.54)1/2,但由于(B)=0.91，故由此迭代法產(chǎn)生迭代序列x(k)是收斂.第23頁第23頁下面考察迭代法(1.11)式收斂速度. 假定迭代法(1.11)式是收斂, 即(B)1, 由(k)=Bk(0), (0)=x(0)-x*, 得于是依據(jù)矩陣從屬范數(shù)定義，有第24頁第24頁因此|Bk|是迭代k次后誤差向量(k)范數(shù)與初始誤差向量(0)范數(shù)之比最大值. 這樣，迭代k次后，平均每次迭代誤差向量范數(shù)壓縮率可當作是|Bk|1/k，若要求迭代k次后有其中1，可取=10-s. 由于(B)1, 故|

11、Bk|1/k1, 由|Bk|1/k1/k兩邊取對數(shù)得即它表明迭代次數(shù)k與-ln|Bk|1/k成反比.即第25頁第25頁 定義4 迭代法(1.11)式平均收斂速度定義為平均收斂速度Rk(B)依賴于迭代次數(shù)及所取范數(shù)，給計算分析帶來不便，由定理4可知lim|Bk|1/k=(B)，因此lim Rk(B)=-ln(B). 定義5 迭代法(1.11)式漸近收斂速度定義為R(B)與迭代次數(shù)及矩陣B取何種范數(shù)無關(guān)，它反應(yīng)了迭代次數(shù)趨于無窮時迭代法漸近性質(zhì)，當(B)越小-ln(B)越大，迭代法收斂越快，可用作為迭代法(1.11)式所需迭代次數(shù)預(yù)計.第26頁第26頁比如在例1中迭代法(1.4)式迭代矩陣B0譜半

12、徑(B0)=0.3592. 若要求則由(1.13)式知于是有即取k=12即可達到要求.第27頁第27頁6.2 雅可比迭代法與高斯-塞德爾迭代法6.2.1 雅可比迭代法將線性方程組(1.1)中系數(shù)矩陣A分成三部分第28頁第28頁即A=D-L-U第29頁第29頁 設(shè)aii0 (i=1,2,n)，選取M為A對角元素部分,即選取M=D(對角陣)，A=D-N，由(1.11)式得到解方程組Ax=b雅可比(Jacobi)迭代法. 又稱簡樸迭代法.其中B=I-D-1A=D-1(L+U)J, f=D-1b. 稱J為解Ax=b雅可比迭代法迭代矩陣.第30頁第30頁于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩

13、陣為第31頁第31頁下面給出雅可比迭代法(2.2)分量計算公式, 記由雅可比迭代法(2.2)有每一個分量寫出來為即當aii0時，有第32頁第32頁等價方程組其中 aii0 (i=1,2,n)即由方程組Ax=b得到第33頁第33頁建立雅可比迭代格式為第34頁第34頁于是，解Ax=b雅可比迭代法計算公式為 由(2.3)式可知，雅可比迭代法計算公式簡樸，每迭代一次只需計算一次矩陣和向量乘法且計算過程中原始矩陣A始終不變. 第35頁第35頁6.2.2 高斯-塞德爾迭代法在 Jacobi 迭代中，計算 xi(k+1)(2 i n)時，使用xj(k+1)代替xj(k) (1 j i-1)，即有建立迭代格式

14、第36頁第36頁或縮寫為稱為高斯-塞德爾(Gauss-Seidel)迭代法.其Gauss-Seidel迭代矩陣為G = (D-L)-1U于是高斯-塞德爾迭代法可寫為矩陣形式第37頁第37頁 這就是說，選取分裂矩陣M為A下三角部分,即選取M= D-L(下三角陣)，A=M-N，由(2.3)式得到解Ax=b高斯-塞德爾(Gauss-Seidel)迭代法.其中B=I-(D-L)-1A= (D-L)-1UG, f=(D-L)-1b. 稱矩陣G=(D-L)-1U為解Ax=b高斯-塞德爾迭代法迭代矩陣.第38頁第38頁由高斯-塞德爾迭代法(2.4)有每一個分量寫出來為即當aii0時，有(與前面同樣式子)或第

15、39頁第39頁于是，解Ax=b高斯-塞德爾迭代法計算公式為或第40頁第40頁 雅可比迭代法不使用變量最新信息計算xi(k+1)，而由高斯-塞德爾迭代公式(2.6)可知，計算x(k+1)第 i個分量xi(k+1)時，利用了已經(jīng)計算出最新分量xj(k+1) (j=1,2,i-1). 可看作雅可比迭代法一個改進. 由(2.6)可知，高斯塞德爾迭代公式每迭代一次只需計算一次矩陣與向量乘法.第41頁第41頁算法(高斯-塞德爾迭代法) 設(shè)Ax=b, 其中ARnn為非奇異矩陣，且aii 0(i=1,2, ,n)，本算法用高斯-塞德爾迭代法解Ax=b，數(shù)組x(n)開始存儲x(0)，后存儲x(k)，N0為最大迭

16、代次數(shù).迭代一次，這個算法需要運算次數(shù)至多與矩陣A非零元素個數(shù)同樣多.2. 對于k=1,2, ,N0， 對于i=1,2, ,n1. xi0.0 (i=1,2, ,n)第42頁第42頁 例6 用高斯-塞德爾迭代法解線性方程組(1.2). 解 用高斯-塞德爾迭代公式：取x(0)=(0, 0, 0)T.迭代到第7次有第43頁第43頁 由此例可知，用高斯-塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取x(0)=0)均收斂，而高斯-塞德爾迭代法比雅可比迭代法收斂較快(即取相同x(0)，達到同樣精度所需迭代次數(shù)較少)，但這結(jié)論只當A滿足一定條件時才是正確. 第44頁第44頁 例1 用雅可比迭代法解

17、方程組 解： Jacobi 迭代格式為第45頁第45頁kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15111.0999931.1999931.299991121.0999981.1999981.299997取 x(0)=(0,0,0)T 計算結(jié)果下列：第46頁第46頁 解：Gauss-Seidel 迭代格式為 例2 用Gauss-Seidel 迭代法解上題.第47頁第47頁取 x(0)=(0,0,0)T 計算結(jié)果下列：kx1(k) x2(k)x3(k)10.720.9021.164481.0999981.1999991.3第48頁第48頁6.2.3 雅可比

18、迭代與高斯-塞德爾迭代收斂性由定理5可馬上得到下列結(jié)論. 定理7 設(shè)Ax=b，其中A=D-L-U為非奇異矩陣,且對角矩陣D也奇異，則(1) 解線性方程組雅可比迭代法收斂充要條件是(J)1，其中J=D-1(L+U).(2) 解線性方程組高斯-塞德爾迭代法收斂充要條件是(G)1，其中G=(D-L)-1U.由定理6還可得到雅可比迭代法收斂充足條件是|J|1. 高斯-塞德爾迭代法收斂充足條件是|G|1. 第49頁第49頁在科學及工程計算中，要求解線性方程組Ax=b,其矩陣A經(jīng)常含有一些特性. 比如，A含有對角占優(yōu)性質(zhì)或A為不可約矩陣，或A是對稱正定矩陣等，下面討論解這些方程組收斂性.第50頁第50頁

19、定義6(對角占優(yōu)陣) 設(shè)A=(aij)nn . (1) 假如A元素滿足稱A為嚴格(按行)對角占優(yōu)陣. (2) 假如A元素滿足且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.第51頁第51頁 定義7(可約與不可約矩陣) 設(shè)A=(aij)nn (n2)，假如存在置換陣P使其中A11為r階方陣，A22為n-r階方陣(1rn)，則稱A為可約矩陣. 不然，假如不存在這樣置換陣P使(2.7)式成立，則稱A為不可約矩陣. A為可約矩陣意即A可通過若干行列重排化為(2.7)或Ax=b可化為兩個低階方程組求解(假如A通過兩行互換同時進行相應(yīng)兩列互換，稱對A進行一次行列重排).第52頁第52頁 事實上，由

20、Ax=b可化為PTAP(PTx)=PTb. 于是，求解Ax=b化為求解且記 ,其中yi, di為r維向量.由上式第2個方程組求出y2,再代入第1個方程組求出y1. 顯然，假如A所有元素都非零，則A為不可約陣.第53頁第53頁 例7 設(shè)有矩陣則A, B都是不可約矩陣.第54頁第54頁 定理8(對角占優(yōu)定理) 假如A=(aij)nn為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣. 證實 只就A為嚴格對角占優(yōu)矩陣證實此定理. 采用反證法，假設(shè)det(A)=0，則Ax=0有非零解，記為x=(x1, x2,xn)T，則 . 由齊次方程組第k個方程及條件則有即這與假設(shè)矛盾，故det(A)0

21、.第55頁第55頁 定理9 設(shè)方程組Ax=b，假如(1) A為嚴格對角占優(yōu)陣，則解Ax=bJacobi迭代法, Gauss-Seidel 迭代法均收斂.(2) A為弱對角占優(yōu)陣，且A為不可約矩陣, 則解Ax=bJacobi迭代法, Gauss-Seidel 迭代法均收斂. 證實 只證(1)，(2)作為練習.由于A是嚴格對角占優(yōu)陣，因此aii0(i=1,n).則|J|1，因此 Jacobi 迭代法收斂.Jacobi迭代陣第56頁第56頁 下面證實GaussSeidel 迭代法收斂.由G=(D-L)-1U，得下面證實|1. 若不然, 即|1, 則由于因此第57頁第57頁即矩陣是嚴格對角占優(yōu)矩陣，故

22、可逆，這與(*) 式矛盾，因此|1, 從而 (G)0, 則(1) 解線性方程組Ax=bJacobi迭代法收斂充足條件是A及2D-A均為正定矩陣, 其中D=(a11,ann).(2) 解線性方程組Ax=bGauss-Seidel 迭代法收斂充足條件是A正定.假如線性方程組系數(shù)矩陣A對稱正定，則有下列收斂定理.定理證實可見文獻2，其中第(2)部分為下面定理12一部分. 定理表明若A對稱正定，則高斯-塞德爾法一定收斂，但雅可比法不一定收斂.第59頁第59頁我們這里給出(2)證實. 證 由于A對稱，則A=D-L-LT，G=(D-L)-1LT，設(shè)為迭代矩陣G =(D-L)-1LT特性值，y為G 相應(yīng)特性

23、(復(fù))向量，即有 (D-L)-1LTy=y，LTy=(D-L)y，則內(nèi)積 (LTy, y)=(D-L)y, y).從而解得 由于A正定，因此D也正定，故記(Dy, y)=0.第60頁第60頁因此|1, 從而(G)1, 故Gauss-Seidel迭代法收斂. 令 -(Ly, y)=a+ib，則由復(fù)向量內(nèi)積性質(zhì)有第61頁第61頁 例8 在線性方程組Ax=b中，證實當-1/2a1時高斯-塞德爾法收斂，而雅可比法只在-1/2a1/2時才收斂. 證實 由于當-1/2a1，雅可比不收斂，此時2D-A不是正定. 對雅可比法迭代矩陣當(J)=|2a|1，即|a|0為可選擇松弛因子. 于是, 由(1.11)可結(jié)

24、構(gòu)一個迭代法, 其迭代矩陣為第67頁第67頁 解Ax=bSOR辦法為.其中 下面給出解Ax=bSOR辦法分量計算公式. 記由(3.1)式可得或第68頁第68頁由此，得到解Ax=bSOR辦法計算公式或第69頁第69頁 (1) 顯然，當=1時即為GaussSeidel 迭代法. (2) SOR辦法每迭代一次主要運算量是計算一次矩陣與向量乘法. (3) 當1時，稱為超松弛法；當1時，稱為低松弛法. (4) 在計算機實現(xiàn)時可用控制迭代終止，或用控制迭代終止.第70頁第70頁 SOR迭代法是GaussSeidel 迭代法一個修正,可由下述思想得到. 設(shè)已知x(k)及已計算x(k+1)分量xj(k+1) (j=1,2,i-1). (1) 首先用GaussSeidel 迭代法定義輔助量 , (2) 再由 與 加權(quán)平均定義 ，即將(3.4)代入(3.5)得到解Ax=bSOR迭代(3.2)式.第71頁第71頁 例9 用SOR辦法解線性方程組Ax=b 解 取初始向量x(0)=0，迭代公式為它準確解為x*=(-1, -1, -1, -1 )T.第72頁第72頁取=1.3，第11次迭代結(jié)果為滿足誤差迭代次數(shù)k1.01.11.21.31.41.51.61.71.81.922171211(至少迭代次數(shù))1417233353109對取其它值，迭代次數(shù)如表. 從此例看