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

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

例1求解方程組記為Ax=b，其中方程組的精確解是x*=(3,2,1)T.現(xiàn)將改寫為第三頁，共七十七頁，編輯于2023年，星期三或?qū)憺閤=B0x+f，其中第四頁，共七十七頁，編輯于2023年，星期三我們?nèi)稳〕跏贾担缛(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ù)利用這個計(jì)算程序，得到一向量序列和一般的計(jì)算公式(迭代公式)第五頁，共七十七頁，編輯于2023年，星期三簡寫為x(k+1)=B0x(k)

+f，其中k表示迭代次數(shù)(k=0,1,2,).迭代到第10次有第六頁，共七十七頁，編輯于2023年，星期三從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請同學(xué)們考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！第七頁，共七十七頁，編輯于2023年，星期三對于給定方程組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ā)散.第八頁，共七十七頁，編輯于2023年，星期三由上述討論，需要研究{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滿足什么條件時有Bk→0(零向量)(k→∞).第九頁，共七十七頁，編輯于2023年，星期三6.2基本迭代法其中，A=(aij)∈Rn×n為非奇異矩陣，下面研究任何建立Ax=b的各種迭代法.設(shè)線性方程組Ax=b，(2.1)其中，M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇A的某種近似，稱M為分裂矩陣.將A分裂為A=M-N.(2.2)第十頁，共七十七頁，編輯于2023年，星期三于是，求解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寫成三部分第十一頁，共七十七頁，編輯于2023年，星期三第十二頁，共七十七頁，編輯于2023年，星期三即A=D-L-U第十三頁，共七十七頁，編輯于2023年，星期三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的雅可比迭代法的迭代矩陣.第十四頁，共七十七頁，編輯于2023年，星期三于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩陣為第十五頁，共七十七頁，編輯于2023年，星期三下面給出雅可比迭代法(2.5)的分量計(jì)算公式,記由雅可比迭代法(2.5)有每一個分量寫出來為即當(dāng)aii0時，有第十六頁，共七十七頁，編輯于2023年，星期三等價方程組其中

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

迭代中，計(jì)算xi(k+1)(2in)時，使用xj(k+1)代替xj(k)(1ji-1)，即有建立迭代格式第二十頁，共七十七頁，編輯于2023年，星期三或縮寫為稱為高斯—塞德爾(Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩陣為BG=(D-L)-1U于是高斯—塞德爾迭代法可寫為矩陣形式第二十一頁，共七十七頁，編輯于2023年，星期三這就是說，選取分裂矩陣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的高斯—塞德爾迭代法的迭代矩陣.第二十二頁，共七十七頁，編輯于2023年，星期三由高斯—塞德爾迭代法(2.7)有每一個分量寫出來為即當(dāng)aii0時，有(與前面一樣的式子)或第二十三頁，共七十七頁，編輯于2023年，星期三于是，解Ax=b的高斯—塞德爾迭代法的計(jì)算公式為或第二十四頁，共七十七頁，編輯于2023年，星期三

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

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

算法1(高斯—塞德爾迭代法)見書p239.第二十五頁，共七十七頁，編輯于2023年，星期三

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

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

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

解：Jacobi

迭代格式為第二十八頁，共七十七頁，編輯于2023年，星期三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

計(jì)算結(jié)果如下：第二十九頁，共七十七頁，編輯于2023年，星期三

解：Gauss-Seidel

迭代格式為

例2用Gauss—Seidel迭代法解上題.第三十頁，共七十七頁，編輯于2023年，星期三取x(0)=(0,0,0)T

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

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

SOR迭代法是Gauss—Seidel迭代法的一種修正，可由下述思想得到.設(shè)已知x(k)及已計(jì)算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.第三十八頁，共七十七頁，編輯于2023年，星期三6.3迭代法的收斂性6.3.1一階定常迭代法的基本定理其中，A=(aij)∈Rn×n為非奇異矩陣，記x*為(3.1)精確解，且設(shè)有等價的方程組設(shè)線性方程組Ax=b，(3.1)于是設(shè)有解Ax=b的一階定常迭代法第三十九頁，共七十七頁，編輯于2023年，星期三有意義的問題是：迭代矩陣B滿足什么條件時，由迭代法產(chǎn)生的向量序列{x(k)}收斂到x*.引進(jìn)誤差向量由(3.3)式減(3.2)得到誤差向量的遞推公式由6.1節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究迭代矩陣B滿足什么條件時，有.第四十頁，共七十七頁，編輯于2023年，星期三

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

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

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

解顯然,當(dāng)|λ|<1時,則有第四十一頁，共七十七頁，編輯于2023年，星期三矩陣序列極限概念可以用矩陣算子范數(shù)來描述.

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

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

定理2

證明作為練習(xí).第四十二頁，共七十七頁，編輯于2023年，星期三

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

證明由矩陣B的若當(dāng)標(biāo)準(zhǔn)形,存在非奇異矩陣P使其中若當(dāng)(Jordan)塊第四十三頁，共七十七頁，編輯于2023年，星期三且，顯然有其中第四十四頁，共七十七頁，編輯于2023年，星期三顯然有,Et,0=I,Et,k=0(當(dāng)k≥t)，(Et,1)k=

Et,k.由于Ji=λI+Et,1，因此下面考查Jik的情況.引進(jìn)記號第四十五頁，共七十七頁，編輯于2023年，星期三其中第四十六頁，共七十七頁，編輯于2023年，星期三

定理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.誤差向量第四十七頁，共七十七頁，編輯于2023年，星期三由設(shè)(B)<1，應(yīng)用定理3，有.于是對任意x(0)有，即.其中x(k+1)=Bx(k)+f.顯然，極限x*是方程組(3.4)的解，且對任意x(0)有

必要性.設(shè)對任何x(0)有由定理2知再由定理3，即得(B)<1.定理4是一階定常迭代法的基本理論.第四十八頁，共七十七頁，編輯于2023年，星期三定理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].第四十九頁，共七十七頁，編輯于2023年，星期三

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

解因?yàn)榉匠探M(1.2)的矩陣A及迭代矩陣J為解得即(J)<1.所以用Jacobi方法解方程組(1.2)是收斂的.得迭代矩陣J的特征方程為第五十頁，共七十七頁，編輯于2023年，星期三

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

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

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

證明

(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)||.反復(fù)利用(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)||,第五十三頁，共七十七頁，編輯于2023年，星期三即得

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

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

.(1)如果A的元素滿足稱A為嚴(yán)格(按行)對角占優(yōu)陣.(2)如果A的元素滿足且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.第五十六頁，共七十七頁，編輯于2023年，星期三

定義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)過兩行交換的同時進(jìn)行相應(yīng)兩列的交換，稱對A進(jìn)行一次行列重排).第五十七頁，共七十七頁，編輯于2023年，星期三

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

顯然，如果A所有元素都非零，則A為不可約陣.第五十八頁，共七十七頁，編輯于2023年，星期三

例7設(shè)有矩陣則A,B都是不可約矩陣.第五十九頁，共七十七頁，編輯于2023年，星期三

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

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

由齊次方程組第k個方程則有即這與假設(shè)矛盾，故det(A)≠0.第六十頁，共七十七頁，編輯于2023年，星期三

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

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

迭代法均收斂.

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

因?yàn)锳是嚴(yán)格對角占優(yōu)陣，所以aii≠0(i=1,,n).則||J||<1，所以Jacobi迭代法收斂.Jacobi迭代陣第六十一頁，共七十七頁，編輯于2023年，星期三下面證明Gauss—Seidel迭代法收斂.由G=(D-L)-1U，得下面證明||<1.若不然,即||1,則由于所以第六十二頁，共七十七頁，編輯于2023年，星期三即矩陣是嚴(yán)格對角占優(yōu)矩陣，故可逆，這與(*)

式矛盾，所以||<1,從而(G)<1，即Gauss—Seidel迭代法收斂.第六十三頁，共七十七頁，編輯于2023年，星期三定理若A為正定矩陣，則方程組Ax=b的Gauss-Seidel迭代法收斂.證因?yàn)锳=D-L-LT，G=(D-L)-1LT，設(shè)為G

的特征值，y為對應(yīng)的特征(復(fù))向量，即

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

因?yàn)锳正定，所以D正定，故(Dy,y)=>0.第六十四頁，共七十七頁，編輯于2023年，星期三所以||<1,從而(G)<1,故Gauss-Seidel迭代法收斂.令-(Ly,y)=a+ib，則由復(fù)向量內(nèi)積的性質(zhì)有下面研究對于解方程組Ax=b的SOR方法中松弛因子ω在什么范圍內(nèi)取值，SOR方法才可能收斂.第六十五頁，共七十七頁，編輯于2023年，星期三定理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.第六十六頁，共七十七頁，編輯于2023年，星期三

定理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即可.第六十七頁，共七十七頁，編輯于2023年，星期三事實(shí)上，設(shè)y為對應(yīng)的Lω的特征向量，即亦即有內(nèi)積則

因?yàn)锳正定，所以D正定，記(Dy,y)=>0.令-(Ly,y)=a+ib，則由復(fù)向量內(nèi)積的性質(zhì)有第六十八頁，共七十七頁，編輯于2023年，星期三當(dāng)0<<2時，有(分子減分母)即L的任一特征值滿足||<1,故SOR迭代法收斂.第六十九頁，共七十七頁，編輯于2023年，星期三

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