數(shù)值分析線性方程組的迭代法

數(shù)值分析線性方程組的迭代法第1頁，共77頁，2023年，2月20日，星期六其中A為非奇異矩陣,當A為低階稠密矩陣時,第5章討論的選主元消去法是有效的.但對于大型稀疏矩陣方程組(A的階數(shù)n很大，但零元素較多),利用迭代法求解是合適的.本章將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應用很廣泛。下面舉簡例，以便了解迭代法的思想.對線性方程組Ax=b，(1.1)6.1引言第2頁，共77頁，2023年，2月20日，星期六

例1求解方程組記為Ax=b，其中方程組的精確解是x*=(3,2,1)T.現(xiàn)將改寫為第3頁，共77頁，2023年，2月20日，星期六或?qū)憺閤=B0x+f，其中第4頁，共77頁，2023年，2月20日，星期六我們?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)，反復利用這個計算程序，得到一向量序列和一般的計算公式(迭代公式)第5頁，共77頁，2023年，2月20日，星期六簡寫為x(k+1)=B0x(k)

+f，其中k表示迭代次數(shù)(k=0,1,2,).迭代到第10次有第6頁，共77頁，2023年，2月20日，星期六從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請同學們考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！第7頁，共77頁，2023年，2月20日，星期六對于給定方程組x=Bx+f，設(shè)有唯一解x*，則

x*=Bx*+f.(1.5)又設(shè)x(0)為任取的初始向量,按下述公式構(gòu)造向量序列

x(k+1)=Bx(k)+f,k=0,1,2,.(1.6)其中k表示迭代次數(shù).

定義1(1)對于給定的方程組x=Bx+f,用公式(1.6)逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代法，這里B與k無關(guān)).B稱為迭代矩陣.(2)如果limx(k)(k→∞)存在(記為x*),稱此迭代法收斂,顯然x*就是方程組的解,否則稱此迭代法發(fā)散.第8頁，共77頁，2023年，2月20日，星期六由上述討論，需要研究{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滿足什么條件時有Bk→0(零向量)(k→∞).第9頁，共77頁，2023年，2月20日，星期六6.2基本迭代法其中，A=(aij)∈Rn×n為非奇異矩陣，下面研究任何建立Ax=b的各種迭代法.設(shè)線性方程組Ax=b，(2.1)其中，M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇A的某種近似，稱M為分裂矩陣.將A分裂為A=M-N.(2.2)第10頁，共77頁，2023年，2月20日，星期六于是，求解Ax=b轉(zhuǎn)化為求解Mx=Nx+b，即求解可構(gòu)造一階定常迭代法其中B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.稱B=I-M-1A為迭代法的迭代矩陣，選取M矩陣，就得到解Ax=b的各種迭代法.設(shè)aii0(i=1,2,,n)，并將A寫成三部分第11頁，共77頁，2023年，2月20日，星期六第12頁，共77頁，2023年，2月20日，星期六即A=D-L-U第13頁，共77頁，2023年，2月20日，星期六6.2.1雅可比(Jacobi)迭代法設(shè)aii0(i=1,2,,n)，選取M為A的對角元素部分,即選取M=D(對角陣)，A=D-N，由(2.3)式得到解方程組Ax=b的雅可比(Jacobi)迭代法.又稱簡單迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.稱J為解Ax=b的雅可比迭代法的迭代矩陣.第14頁，共77頁，2023年，2月20日，星期六于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩陣為第15頁，共77頁，2023年，2月20日，星期六下面給出雅可比迭代法(2.5)的分量計算公式,記由雅可比迭代法(2.5)有每一個分量寫出來為即當aii0時，有第16頁，共77頁，2023年，2月20日，星期六等價方程組其中

aii(i)0(i=1,2,,n)即由方程組Ax=b得到的第17頁，共77頁，2023年，2月20日，星期六建立的雅可比迭代格式為第18頁，共77頁，2023年，2月20日，星期六于是，解Ax=b的雅可比迭代法的計算公式為由(2.6)式可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.第19頁，共77頁，2023年，2月20日，星期六6.2.2高斯－賽德爾迭代法在Jacobi

迭代中，計算xi(k+1)(2in)時，使用xj(k+1)代替xj(k)(1ji-1)，即有建立迭代格式第20頁，共77頁，2023年，2月20日，星期六或縮寫為稱為高斯—塞德爾(Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩陣為BG=(D-L)-1U于是高斯—塞德爾迭代法可寫為矩陣形式第21頁，共77頁，2023年，2月20日，星期六這就是說，選取分裂矩陣M為A的下三角部分,即選取M=D-L(下三角陣)，A=M-N，由(2.3)式得到解Ax=b的高斯—塞德爾(Gauss—Seidel)迭代法.其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.稱矩陣G=(D-L)-1U為解Ax=b的高斯—塞德爾迭代法的迭代矩陣.第22頁，共77頁，2023年，2月20日，星期六由高斯—塞德爾迭代法(2.7)有每一個分量寫出來為即當aii0時，有(與前面一樣的式子)或第23頁，共77頁，2023年，2月20日，星期六于是，解Ax=b的高斯—塞德爾迭代法的計算公式為或第24頁，共77頁，2023年，2月20日，星期六

雅可比迭代法不使用變量的最新信息計算xi(k+1)，而由高斯—塞德爾迭代公式(2.8)可知，計算x(k+1)的第i個分量xi(k+1)時，利用了已經(jīng)計算出的最新分量xj(k+1)(j=1,2,,i-1).

可看作雅可比迭代法的一種改進.由(2.8)可知，高斯—塞德爾迭代公式每迭代一次只需計算一次矩陣與向量的乘法.

算法1(高斯—塞德爾迭代法)見書p239.第25頁，共77頁，2023年，2月20日，星期六

例2用高斯—塞德爾迭代法解例1的方程組(1.2).

解用高斯—塞德爾迭代公式：取x(0)=(0,0,0)T.迭代到第7次有第26頁，共77頁，2023年，2月20日，星期六由此例可知，用高斯—塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取x(0)=0)均收斂，而高斯—塞德爾迭代法比雅可比迭代法收斂較快(即取相同的x(0)，達到同樣精度所需迭代次數(shù)較少)，但這結(jié)論只當A滿足一定條件時才是對的.第27頁，共77頁，2023年，2月20日，星期六

例1用雅可比迭代法解方程組

解：Jacobi

迭代格式為第28頁，共77頁，2023年，2月20日，星期六kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T

計算結(jié)果如下：第29頁，共77頁，2023年，2月20日，星期六

解：Gauss-Seidel

迭代格式為

例2用Gauss—Seidel迭代法解上題.第30頁，共77頁，2023年，2月20日，星期六取x(0)=(0,0,0)T

計算結(jié)果如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3第31頁，共77頁，2023年，2月20日，星期六6.2.3解大型稀疏線性方程組的逐次超松弛法(SOR方法)我們?nèi)?gt;0為松弛因子，建立迭代格式如下即第32頁，共77頁，2023年，2月20日，星期六或改寫為其逐次超松弛迭代矩陣為逐次超松弛法可寫為矩陣形式稱為逐次超松弛迭代法，簡稱SOR方法.顯然，=1就是Gauss—Seidel迭代法.第33頁，共77頁，2023年，2月20日，星期六下面用矩陣方法推導，選取分裂矩陣M為帶參數(shù)的下三角矩陣從而得到解Ax=b的逐次超松弛迭代法(SuccessiveOverRelaxationMethod，簡稱SOR方法).其中>0為可選擇的松弛因子.于是，由(2.3)可構(gòu)造一個迭代法，其迭代矩陣為第34頁，共77頁，2023年，2月20日，星期六解Ax=b的SOR方法為.其中下面給出解Ax=b的SOR方法的分量計算公式.記由(2.10)式可得第35頁，共77頁，2023年，2月20日，星期六由此，得到解Ax=b的SOR方法的計算公式或第36頁，共77頁，2023年，2月20日，星期六(1)顯然，當=1時即為Gauss—Seidel迭代法.(2)SOR方法每迭代一次主要運算量是計算一次矩陣與向量的乘法.(3)當>1時，稱為超松弛法；當<1時，稱為低松弛法.(4)在計算機實現(xiàn)時可用控制迭代終止，或用控制迭代終止.第37頁，共77頁，2023年，2月20日，星期六

SOR迭代法是Gauss—Seidel迭代法的一種修正，可由下述思想得到.設(shè)已知x(k)及已計算x(k+1)的分量xj(k+1)(j=1,2,,i-1).(1)首先用Gauss—Seidel迭代法定義輔助量,(2)再由與加權(quán)平均定義，即將(2.13)代入(2.14)得到解Ax=b的SOR迭代(2.11)式.例3用SOR迭代法解方程組.見書p242.第38頁，共77頁，2023年，2月20日，星期六6.3迭代法的收斂性6.3.1一階定常迭代法的基本定理其中，A=(aij)∈Rn×n為非奇異矩陣，記x*為(3.1)精確解，且設(shè)有等價的方程組設(shè)線性方程組Ax=b，(3.1)于是設(shè)有解Ax=b的一階定常迭代法第39頁，共77頁，2023年，2月20日，星期六有意義的問題是：迭代矩陣B滿足什么條件時，由迭代法產(chǎn)生的向量序列{x(k)}收斂到x*.引進誤差向量由(3.3)式減(3.2)得到誤差向量的遞推公式由6.1節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究迭代矩陣B滿足什么條件時，有.第40頁，共77頁，2023年，2月20日，星期六

定義2設(shè)有矩陣序列Ak=(aij(k))∈Rn×n

及A=(aij)∈Rn×n，如果n2個數(shù)列極限存在且有則{Ak}稱收斂于A，記為lim(k→∞).

例4設(shè)有矩陣序列{Ak},其中Ak=Bk,而且設(shè)|λ|<1，考查矩陣序列極限.

解顯然,當|λ|<1時,則有第41頁，共77頁，2023年，2月20日，星期六矩陣序列極限概念可以用矩陣算子范數(shù)來描述.

定理1其中||·||為矩陣的任意一種算子范數(shù).

證明顯然有再由矩陣范數(shù)的等價性,則定理對其它算子范數(shù)亦對.

定理2

證明作為練習.第42頁，共77頁，2023年，2月20日，星期六

定理3設(shè)B=(bij)∈Rn×n，則limBk=0(k→∞)(零矩陣)的充分必要條件是矩陣B的譜半徑(B)<1.

證明由矩陣B的若當標準形,存在非奇異矩陣P使其中若當(Jordan)塊第43頁，共77頁，2023年，2月20日，星期六且，顯然有其中第44頁，共77頁，2023年，2月20日，星期六顯然有,Et,0=I,Et,k=0(當k≥t)，(Et,1)k=

Et,k.由于Ji=λI+Et,1，因此下面考查Jik的情況.引進記號第45頁，共77頁，2023年，2月20日，星期六其中第46頁，共77頁，2023年，2月20日，星期六

定理4(迭代法基本定理)設(shè)有方程組x=Bx+f.(3.4)及一階定常迭代法x(k+1)=Bx(k)+f.(3.5)對任意選擇初始向量x(0)，迭代法(3.5)收斂的充要條件是矩陣B的譜半徑(B)<1.

證明

充分性.設(shè)(B)<1，易知Ax=f(其中A=I-B)有唯一解，記為x*，則x*=Bx*+f.誤差向量第47頁，共77頁，2023年，2月20日，星期六由設(shè)(B)<1，應用定理3，有.于是對任意x(0)有，即.其中x(k+1)=Bx(k)+f.顯然，極限x*是方程組(3.4)的解，且對任意x(0)有

必要性.設(shè)對任何x(0)有由定理2知再由定理3，即得(B)<1.定理4是一階定常迭代法的基本理論.第48頁，共77頁，2023年，2月20日，星期六定理3和定理4的結(jié)論和起來即為(1)迭代法x(k+1)=Bx(k)+f

收斂limBk=O；(2)迭代法x(k+1)=Bx(k)+f

收斂(B)<1.

推論設(shè)Ax=b，其中A=D-L-U為非奇異矩陣且D非奇異矩陣，則有(1)Jacobi迭代法收斂(J)<1,其中J=D-1(L+U).(2)G-S迭代法收斂(G)<1,其中G=(D-L)-1U.(3)SOR迭代法收斂(Lω)<1,其中Lω=(D-ωL)-1[(1-ω)D+ωU].第49頁，共77頁，2023年，2月20日，星期六

例5考察用Jacobi方法解方程組(1.2)的收斂性.

解因為方程組(1.2)的矩陣A及迭代矩陣J為解得即(J)<1.所以用Jacobi方法解方程組(1.2)是收斂的.得迭代矩陣J的特征方程為第50頁，共77頁，2023年，2月20日，星期六

例6考察用迭代法解方程組的收斂性.其中

解方程組的迭代矩陣B的特征方程為矩陣B的特征值為即(B)>1.這說明用迭代法解此方程組不收斂.迭代法的基本定理在理論上是重要的，根據(jù)譜半徑的性質(zhì)(B)≤||B||，下面利用矩陣B的范數(shù)建立判別迭代法收斂的充分條件.第51頁，共77頁，2023年，2月20日，星期六

定理5(迭代法收斂的充分條件)設(shè)有方程組x=Bx+f，B=(bij)∈Rn×n，及一階定常迭代法x(k+1)=Bx(k)+f.如果有B的某種算子范數(shù)||B||=q<1，則(1)迭代法收斂，即對任取x(0)有第52頁，共77頁，2023年，2月20日，星期六

證明

(1)由基本定理4結(jié)論(1)是顯然的.

(2)顯然有關(guān)系式x*-x(k+1)=B(x*-x(k))

及x(k+1)

–x(k)=B(x(k)

–x(k-1)).于是有(a)||x(k+1)

–x(k)||≤q||x(k)

–x(k-1)||;(b)||x*-x(k+1)||≤q||x*-x(k)||.反復利用(b)即得(2).

(3)考查||x(k+1)

–x(k)||=||x*–x(k)–(x*–x(k+1))||≥||x*–x(k)||–||x*–x(k+1)||≥(1–q)||x*–x(k)||,第53頁，共77頁，2023年，2月20日，星期六即得

(4)利用(3)的結(jié)果反復利用(a)，則得到(4).即第54頁，共77頁，2023年，2月20日，星期六6.3.2關(guān)于解某些特殊方程組迭代法的收斂性在科學及工程計算中，要求解方程組Ax=b，其矩陣A常常具有某些特性.例如，A具有對角占優(yōu)性質(zhì)或A為不可約陣，或A是對稱正定陣，下面討論用基本迭代法解這些方程組的收斂性.第55頁，共77頁，2023年，2月20日，星期六

定義3(對角占優(yōu)陣)設(shè)A=(aij)n×n

.(1)如果A的元素滿足稱A為嚴格(按行)對角占優(yōu)陣.(2)如果A的元素滿足且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.第56頁，共77頁，2023年，2月20日，星期六

定義4(可約與不可約矩陣)設(shè)A=(aij)n×n

(n≥2)，如果存在置換陣P使其中A11為r階方陣，A22為n-r階方陣(1≤r≤n)，則稱A為可約矩陣.否則，如果不存在這樣置換陣P使(3.6)式成立，則稱A為不可約矩陣.

A為可約矩陣意即A可經(jīng)過若干行列重排化為(3.6)或Ax=b可化為兩個低階方程組求解(如果A經(jīng)過兩行交換的同時進行相應兩列的交換，稱對A進行一次行列重排).第57頁，共77頁，2023年，2月20日，星期六

事實上，由Ax=b可化為PTAP(PTx)=PTb.于是，求解Ax=b化為求解且記,其中yi,di為r維向量.由上式第2個方程組求出y2,再代入第1個方程組求出y1.

顯然，如果A所有元素都非零，則A為不可約陣.第58頁，共77頁，2023年，2月20日，星期六

例7設(shè)有矩陣則A,B都是不可約矩陣.第59頁，共77頁，2023年，2月20日，星期六

定理6(對角占優(yōu)定理)如果A=(aij)n×n為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣.

證明只就A為嚴格對角占優(yōu)矩陣證明此定理.采用反證法，如果det(A)=0，則Ax=b有非零解，記為x=(x1,x2,,xn)T，則.

由齊次方程組第k個方程則有即這與假設(shè)矛盾，故det(A)≠0.第60頁，共77頁，2023年，2月20日，星期六

定理7設(shè)方程組Ax=b，如果(1)A為嚴格對角占優(yōu)陣，則解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收斂.(2)A為弱對角占優(yōu)陣，且A為不可約矩陣,則解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收斂.

證明只證(1)，(2)作為練習.

因為A是嚴格對角占優(yōu)陣，所以aii≠0(i=1,,n).則||J||<1，所以Jacobi迭代法收斂.Jacobi迭代陣第61頁，共77頁，2023年，2月20日，星期六下面證明Gauss—Seidel迭代法收斂.由G=(D-L)-1U，得下面證明||<1.若不然,即||1,則由于所以第62頁，共77頁，2023年，2月20日，星期六即矩陣是嚴格對角占優(yōu)矩陣，故可逆，這與(*)

式矛盾，所以||<1,從而(G)<1，即Gauss—Seidel迭代法收斂.第63頁，共77頁，2023年，2月20日，星期六定理若A為正定矩陣，則方程組Ax=b的Gauss-Seidel迭代法收斂.證因為A=D-L-LT，G=(D-L)-1LT，設(shè)為G

的特征值，y為對應的特征(復)向量，即

(D-L)-1LTy=y，LTy=(D-L)y，則內(nèi)積(LTy,y)=((D-L)y,y).從而

因為A正定，所以D正定，故(Dy,y)=>0.第64頁，共77頁，2023年，2月20日，星期六所以||<1,從而(G)<1,故Gauss-Seidel迭代法收斂.令-(Ly,y)=a+ib，則由復向量內(nèi)積的性質(zhì)有下面研究對于解方程組Ax=b的SOR方法中松弛因子ω在什么范圍內(nèi)取值，SOR方法才可能收斂.第65頁，共77頁，2023年，2月20日，星期六定理8(SOR方法收斂的必要條件)設(shè)解方程組Ax=b的SOR迭代法收斂，則0<<2.

證

A=D-L-U，L=(D-L)-1[(1-)D+U],由于SOR迭代法收斂，則(L)<1.設(shè)迭代矩陣L的特征值為i

(i=1,,n)，則有det(L)<|12n|<[(B

)]n<1.于是所以|1-|<1，即0<<2.第66頁，共77頁，2023年，2月20日，星期六

定理8說明解Ax=b的SOR迭代法，只有在(0,2)范圍內(nèi)取松弛因子，才可能收斂.定理9(SOR方法收斂的充分條件)設(shè)有方程組Ax=b，如果：(1)A為對稱正定矩陣，A=D-L-LT;(2)0<<2.則解方程組Ax=b的SOR迭代法收斂.

證在上述假定下，設(shè)迭代矩陣L的任一特征值為，只要證明||<1即可.第67頁，共77頁，2023年，2月20日，星期六事實上，設(shè)y為對應的Lω的特征向量，即亦即有內(nèi)積則

因為A正定，所以D正定，記(Dy,y)=>0.令-(Ly,y)=a+ib，則由復向量內(nèi)積的性質(zhì)有第68頁，共77頁，2023年，2月20日，星期六當0<<2時，有(分子減分母)即L的任一特征值滿足||<1,故SOR迭代法收斂.第69頁，共77頁，2023年，2月20日，星期六

由定理3證明中可知，如果(B)<1且(B)越小時，迭代法收斂越快.現(xiàn)設(shè)有方程組下面討論迭代法的收斂速度.x=Bx+