數(shù)值分析ppt第6章-解線性方程組的迭代法

第6章解線性方程組的迭代方法6.1引言6.2基本迭代法6.3迭代法的收斂性6.4*

分塊迭代法其中A為非奇異矩陣

選主元消去法:A為低階稠密矩陣迭代法:大型稀疏矩陣方程組(A的階數(shù)n很大，但零元素較多),迭代法:雅可比迭代法

高斯-賽德爾迭代法

超松弛迭代法

對線性方程組Ax=b，(1.1)6.1引言

例1

求解方程組記為Ax=b，其中方程組的精確解是x*=(3,2,1)T.現(xiàn)將改寫為或?qū)憺閤=B0x+f，其中

我們?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ù)利用這個計算程序，得到一向量序列和一般的計算公式(迭代公式)簡寫為x(k+1)=B0x(k)

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

迭代到第10次有從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請同學(xué)們考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！對于給定方程組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ā)散.

由上述討論，需要研究{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→∞).6.2基本迭代法其中，A=(aij)∈Rn×n為非奇異矩陣，下面研究任何建立Ax=b的各種迭代法.

設(shè)線性方程組Ax=b，(2.1)其中，M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇A的某種近似，稱M為分裂矩陣.

將A分裂為A=M-N.(2.2)

于是，求解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寫成三部分即A=D-L-U6.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的雅可比迭代法的迭代矩陣.于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩陣為下面給出雅可比迭代法(2.5)的分量計算公式,記由雅可比迭代法(2.5)有每一個分量寫出來為即當(dāng)aii0時，有等價方程組其中

aii(i)0(i=1,2,,n)即由方程組Ax=b得到的建立的雅可比迭代格式為于是，解Ax=b的雅可比迭代法的計算公式為

由(2.6)式可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.6.2.2高斯－賽德爾迭代法在Jacobi

迭代中，計算xi(k+1)(2in)時，使用xj(k+1)代替xj(k)(1ji-1)，即有建立迭代格式或縮寫為稱為高斯—塞德爾(Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩陣為BG=(D-L)-1U于是高斯—塞德爾迭代法可寫為矩陣形式

這就是說，選取分裂矩陣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的高斯—塞德爾迭代法的迭代矩陣.由高斯—塞德爾迭代法(2.7)有每一個分量寫出來為即當(dāng)aii0時，有(與前面一樣的式子)或于是，解Ax=b的高斯—塞德爾迭代法的計算公式為或

雅可比迭代法不使用變量的最新信息計算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(高斯—塞德爾迭代法)見書p139.

例2

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

解用高斯—塞德爾迭代公式：取x(0)=(0,0,0)T.迭代到第7次有

由此例可知，用高斯—塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取x(0)=0)均收斂，而高斯—塞德爾迭代法比雅可比迭代法收斂較快(即取相同的x(0)，達到同樣精度所需迭代次數(shù)較少)，但這結(jié)論只當(dāng)A滿足一定條件時才是對的.

例1

用雅可比迭代法解方程組

解：Jacobi

迭代格式為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é)果如下：

解：Gauss-Seidel

迭代格式為

例2

用Gauss—Seidel迭代法解上題.取x(0)=(0,0,0)T

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

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.36.2.3解大型稀疏線性方程組的逐次超松弛法(SOR方法)

我們?nèi)?gt;0為松弛因子，建立迭代格式如下即或改寫為

其逐次超松弛迭代矩陣為

逐次超松弛法可寫為矩陣形式稱為逐次超松弛迭代法，簡稱SOR方法.

顯然，=1就是Gauss—Seidel迭代法.

下面用矩陣方法推導(dǎo)，選取分裂矩陣M為帶參數(shù)的下三角矩陣從而得到解Ax=b的逐次超松弛迭代法(SuccessiveOverRelaxationMethod，簡稱SOR方法).其中>0為可選擇的松弛因子.

于是，由(2.3)可構(gòu)造一個迭代法，其迭代矩陣為

解Ax=b的SOR方法為.其中

下面給出解Ax=b的SOR方法的分量計算公式.記由(2.10)式可得由此，得到解Ax=b的SOR方法的計算公式或(1)顯然，當(dāng)=1時即為Gauss—Seidel迭代法.(2)SOR方法每迭代一次主要運算量是計算一次矩陣與向量的乘法.(3)當(dāng)>1時，稱為超松弛法；當(dāng)<1時，稱為低松弛法.(4)在計算機實現(xiàn)時可用控制迭代終止，或用控制迭代終止.

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迭代法解方程組.見書p195.6.3迭代法的收斂性6.3.1一階定常迭代法的基本定理其中，A=(aij)∈Rn×n為非奇異矩陣，記x*為(3.1)精確解，且設(shè)有等價的方程組

設(shè)線性方程組Ax=b，(3.1)于是設(shè)有解Ax=b的一階定常迭代法有意義的問題是：迭代矩陣B滿足什么條件時，由迭代法產(chǎn)生的向量序列{x(k)}收斂到x*.

引進誤差向量由(3.3)式減(3.2)得到誤差向量的遞推公式由6.1節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究迭代矩陣B滿足什么條件時，有.

定義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時,則有矩陣序列極限概念可以用矩陣算子范數(shù)來描述.

定理1

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

定理2

定理3

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

定理4(迭代法基本定理)

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

定理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].

例5

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

解因為方程組(1.2)的矩陣A及迭代矩陣J為解得即(J)<1.所以用Jacobi方法解方程組(1.2)是收斂的.得迭代矩陣J的特征方程為

例6

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

解方程組的迭代矩陣B的特征方程為矩陣B的特征值為即(B)>1.這說明用迭代法解此方程組不收斂.

迭代法的基本定理在理論上是重要的，根據(jù)譜半徑的性質(zhì)(B)≤||B||，下面利用矩陣B的范數(shù)建立判別迭代法收斂的充分條件.思考：A為n階實對稱矩陣時，應(yīng)如何處理.

定理5(迭代法收斂的充分條件)

設(shè)有方程組x=Bx+f，B=(bij)∈Rn×n，及一階定常迭代法x(k+1)=Bx(k)+f.如果有B的某種算子范數(shù)||B||=q<1

，則(1)迭代法收斂，即對任取x(0)有6.3.2關(guān)于解某些特殊方程組迭代法的收斂性

在科學(xué)及工程計算中，要求解方程組Ax=b，其矩陣A常常具有某些特性.例如，A具有對角占優(yōu)性質(zhì)或A為不可約陣，或A是對稱正定陣，下面討論用基本迭代法解這些方程組的收斂性.

定義3(對角占優(yōu)陣)

設(shè)A=(aij)n×n

.(1)

如果A的元素滿足稱A為嚴格(按行)對角占優(yōu)陣.(2)

如果A的元素滿足且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.

定義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)過兩行交換的同時進行相應(yīng)兩列的交換，稱對A進行一次行列重排).

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

顯然，如果A所有元素都非零，則A為不可約陣.

例7

設(shè)有矩陣則A,B都是不可約矩陣.

定理6(對角占優(yōu)定理)

如果A=(aij)n×n為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣.嚴格對角占優(yōu)矩陣:如果A的每個對角元的絕對值

都比所在行的非對角元的絕對值的和要大不可約:不能化成兩個方陣其他位置為0的矩陣

定理7設(shè)方程組Ax=b，如果

(1)A為嚴格對角占優(yōu)陣，則解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收斂.

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

迭代法均收斂.定理若A為正定矩陣，則方程組Ax=b的Gauss-Seidel迭代法收斂.定理8(SOR方法收斂的必要條件)

設(shè)解方程組Ax=b的SOR迭代法收斂，則0<<2.定理9(SOR方法收斂的充分條件)

設(shè)有方程組Ax=b，如果：

(1)A為對稱正定矩陣，A=D-L-LT;

(2)0<<2.則解方程組Ax=b的SOR迭代法收斂.

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

(k=0,1,)，

由基本定理有0<(B)<1，且誤差向量ε(k)=x(k)-x*滿足且設(shè)迭代法收斂，即