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

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

2、,2,1)T. 現(xiàn)將(1.2)改寫為第3頁(yè)第3頁(yè)或?qū)憺閤=B0 x+f，其中第4頁(yè)第4頁(yè) 我們?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ù)利用這個(gè)計(jì)算程序，得到一向量序列和普通計(jì)算公式(迭代公式)第5頁(yè)第5頁(yè)簡(jiǎn)寫為 x(k+1)=B0 x(k) +f，其中k表示迭代次數(shù)(k=0,1,2,). 迭代到第10次有第6頁(yè)第6頁(yè)從此例看出，由迭代法產(chǎn)生向量序列x(k)逐

3、步迫近方程組準(zhǔn)確解是x*=(3,2,1)T. 即有 對(duì)于任何一個(gè)方程組x=Bx+f(由Ax=b變形得到等價(jià)方程組)，由迭代法產(chǎn)生向量序列x(k)是否一定逐步迫近方程組解x*呢？回答是不一定. 請(qǐng)同窗們考慮用迭代法解下述方程組但 x(k)并不是所有都收斂到解x*！第7頁(yè)第7頁(yè)對(duì)于給定方程組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)對(duì)于給定方程組x=Bx+f , 用公式(1.6)逐步代入求近似解辦法稱為迭代法(或稱為一階定常迭

4、代法，這里B與k無(wú)關(guān)). B稱為迭代矩陣. (2) 假如limx(k) (k)存在(記為x*), 稱此迭代法收斂, 顯然x*就是方程組解, 不然稱此迭代法發(fā)散.第8頁(yè)第8頁(yè) 由上述討論，需要研究x(k)收斂性. 引進(jìn)誤差向量 由(1.6)減去(1.5)式，得(k+1)=B(k) (k=0,1,2,)，遞推得 要考察x(k)收斂性，就要研究B在什么條件下有l(wèi)im(k)=0 (k)，亦即要研究B滿足什么條件時(shí)有Bk0(零矩陣) (k) . 第9頁(yè)第9頁(yè)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頁(yè)第10頁(yè) 定義3 設(shè)矩陣序列Ak=aij(k)Rnn及A=aijRnn,假如n2個(gè)數(shù)列極限存在，且有則稱矩陣序列Ak收斂于A ，記作例2 設(shè)有矩陣序列且設(shè)| |1，考察其極限.解 顯然，當(dāng)| |(2) 用反證法，假定B有一個(gè)特性值,滿足|1,則存在x0,使Bx=x,由此可得|Bkx|= |k|x|,當(dāng)k時(shí)Bkx不收斂于零向量. 由定理2可知(1)不成立，從而知| |1 ，即(2)成立. (1) limBk =0; (2) (B)1; (3)至少存在一個(gè)從屬矩陣范數(shù)| ，使|B|(3) 依據(jù)第5章定理18，對(duì)任意

6、 0，存在一個(gè)從屬范數(shù)| ，使|B|(B)+，由(2)有(B)0，可使|B|(1) 由(3) 給出矩陣范數(shù)|B|N 時(shí)有 證實(shí) 由第5章定理18，對(duì)一切k有另一方面對(duì)任意 0，記顯然有(B)N 時(shí)，由任意性即得定理結(jié)論.第15頁(yè)第15頁(yè)6.1.3 迭代法及其收斂性其中，A=(aij)Rnn為非奇異矩陣，下面研究如何建立解Ax=b迭代法. 設(shè)有線性方程組 Ax=b，其中，M為可選擇非奇異矩陣，且使Mx=d容易求解，普通選擇A某種近似，稱M為分裂矩陣. 將A分裂為 A=M-N. (1.9) 第16頁(yè)第16頁(yè) 于是，求解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頁(yè)第17頁(yè) 定理5(一階定常迭代法基本定理) 給定線性方程組(1.10)及一階定常迭代法(1.11)式，對(duì)任意選取初始向量x(0)，迭代法(1.11)式收斂充足必要條件是矩陣B譜半徑(B)1.由定理2知limBk=0，再由定理3，即得(B)1. 證實(shí) (=) 設(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è)對(duì)任意x(0)有l(wèi)imx(k)=x*, 其中x(k+1)=Bx(k)+f. 顯然, 極限x*是線性方程組(1.10)解, 且對(duì)任意x(0)有 (k)=x(k)-x*=Bk(0)0 (k) .第18頁(yè)第18頁(yè) 例3 考察線性方程組(1.2)給出迭代法(1.4)式收斂性. 解 先求迭代矩陣B0特性值. 由特性方程可得解得即(B0)1，這闡明用迭代法解此方程組不收斂.迭代法基本定理在理論上是主要，由于(B)|B|，下面利用矩陣B范數(shù)建立判別迭代法收斂充足條件.第20頁(yè)第20頁(yè) 定理6(迭代法收斂充足條件) 設(shè)有線性方程組x=

9、Bx+f， A=(aij)Rnn，及一階定常迭代法 x(k+1)=Bx(k)+f.假如有B某種算子范數(shù)|B|=q1，則(1) 迭代法收斂，即對(duì)任取x(0)有 limx(k)=x*，且 x*=Bx*+f.第21頁(yè)第21頁(yè) 證實(shí) 由基本定理知，結(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頁(yè)第22頁(yè)注意，定理6只給出迭代法(1.11)式收斂充足性，即使條件|B|1對(duì)任何慣用范數(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頁(yè)第23頁(yè)下面考察迭代法(1.11)式收斂速度. 假定迭代法(1.11)式是收斂, 即(B)1, 由(k)=Bk(0), (0)=x(0)-x*, 得于是依據(jù)矩陣從屬范數(shù)定義，有第24頁(yè)第24頁(yè)因此|Bk|是迭代k次后誤差向量(k)范數(shù)與初始誤差向量(0)范數(shù)之比最大值. 這樣，迭代k次后，平均每次迭代誤差向量范數(shù)壓縮率可當(dāng)作是|Bk|1/k，若要求迭代k次后有其中1，可取=10-s. 由于(B)1, 故|

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

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

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

14、第36頁(yè)第36頁(yè)或縮寫為稱為高斯-塞德爾(Gauss-Seidel)迭代法.其Gauss-Seidel迭代矩陣為G = (D-L)-1U于是高斯-塞德爾迭代法可寫為矩陣形式第37頁(yè)第37頁(yè) 這就是說(shuō)，選取分裂矩陣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頁(yè)第38頁(yè)由高斯-塞德爾迭代法(2.4)有每一個(gè)分量寫出來(lái)為即當(dāng)aii0時(shí)，有(與前面同樣式子)或第

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

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

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

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

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

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

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

22、可逆，這與(*) 式矛盾，因此|1, 從而 (G)0, 則(1) 解線性方程組Ax=bJacobi迭代法收斂充足條件是A及2D-A均為正定矩陣, 其中D=(a11,ann).(2) 解線性方程組Ax=bGauss-Seidel 迭代法收斂充足條件是A正定.假如線性方程組系數(shù)矩陣A對(duì)稱正定，則有下列收斂定理.定理證實(shí)可見(jiàn)文獻(xiàn)2，其中第(2)部分為下面定理12一部分. 定理表明若A對(duì)稱正定，則高斯-塞德爾法一定收斂，但雅可比法不一定收斂.第59頁(yè)第59頁(yè)我們這里給出(2)證實(shí). 證 由于A對(duì)稱，則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頁(yè)第60頁(yè)因此|1, 從而(G)1, 故Gauss-Seidel迭代法收斂. 令 -(Ly, y)=a+ib，則由復(fù)向量?jī)?nèi)積性質(zhì)有第61頁(yè)第61頁(yè) 例8 在線性方程組Ax=b中，證實(shí)當(dāng)-1/2a1時(shí)高斯-塞德爾法收斂，而雅可比法只在-1/2a1/2時(shí)才收斂. 證實(shí) 由于當(dāng)-1/2a1，雅可比不收斂，此時(shí)2D-A不是正定. 對(duì)雅可比法迭代矩陣當(dāng)(J)=|2a|1，即|a|0為可選擇松弛因子. 于是, 由(1.11)可結(jié)

24、構(gòu)一個(gè)迭代法, 其迭代矩陣為第67頁(yè)第67頁(yè) 解Ax=bSOR辦法為.其中 下面給出解Ax=bSOR辦法分量計(jì)算公式. 記由(3.1)式可得或第68頁(yè)第68頁(yè)由此，得到解Ax=bSOR辦法計(jì)算公式或第69頁(yè)第69頁(yè) (1) 顯然，當(dāng)=1時(shí)即為GaussSeidel 迭代法. (2) SOR辦法每迭代一次主要運(yùn)算量是計(jì)算一次矩陣與向量乘法. (3) 當(dāng)1時(shí)，稱為超松弛法；當(dāng)1時(shí)，稱為低松弛法. (4) 在計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用控制迭代終止，或用控制迭代終止.第70頁(yè)第70頁(yè) SOR迭代法是GaussSeidel 迭代法一個(gè)修正,可由下述思想得到. 設(shè)已知x(k)及已計(jì)算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頁(yè)第71頁(yè) 例9 用SOR辦法解線性方程組Ax=b 解 取初始向量x(0)=0，迭代公式為它準(zhǔn)確解為x*=(-1, -1, -1, -1 )T.第72頁(yè)第72頁(yè)取=1.3，第11次迭代結(jié)果為滿足誤差迭代次數(shù)k1.01.11.21.31.41.51.61.71.81.922171211(至少迭代次數(shù))1417233353109對(duì)取其它值，迭代次數(shù)如表. 從此例看