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

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

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

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

高斯-賽德?tīng)柕?/p>

超松弛迭代法

對(duì)線(xiàn)性方程組Ax=b，(1.1)6.1引言

例1

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

我們?nèi)稳〕跏贾?，例如取x(0)=(0,0,0)T.將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿(mǎn)足)，得到新的值x(1)=(x1(1),x2(1),x3(1))T

=(3.5,3,3)T

，再將x(1)分量代入(1.3)式右邊得到x(2)，反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列和一般的計(jì)算公式(迭代公式)簡(jiǎn)寫(xiě)為x(k+1)=B0x(k)

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

迭代到第10次有從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有對(duì)于任何一個(gè)方程組x=Bx+f(由Ax=b變形得到的等價(jià)方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請(qǐng)同學(xué)們考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！對(duì)于給定方程組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)對(duì)于給定的方程組x=Bx+f,用公式(1.6)逐步代入求近似解的方法稱(chēng)為迭代法(或稱(chēng)為一階定常迭代法，這里B與k無(wú)關(guān)).B稱(chēng)為迭代矩陣.(2)如果limx(k)(k→∞)存在(記為x*),稱(chēng)此迭代法收斂,顯然x*就是方程組的解,否則稱(chēng)此迭代法發(fā)散.

由上述討論，需要研究{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滿(mǎn)足什么條件時(shí)有Bk→0(零向量)(k→∞).6.2基本迭代法其中，A=(aij)∈Rn×n為非奇異矩陣，下面研究任何建立Ax=b的各種迭代法.

設(shè)線(xiàn)性方程組Ax=b，(2.1)其中，M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇A的某種近似，稱(chēng)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.稱(chēng)B=I-M-1A為迭代法的迭代矩陣，選取M矩陣，就得到解Ax=b的各種迭代法.

設(shè)aii0(i=1,2,,n)，并將A寫(xiě)成三部分即A=D-L-U6.2.1雅可比(Jacobi)迭代法

設(shè)aii0(i=1,2,,n)，選取M為A的對(duì)角元素部分,即選取M=D(對(duì)角陣)，A=D-N，由(2.3)式得到解方程組Ax=b的雅可比(Jacobi)迭代法.又稱(chēng)簡(jiǎn)單迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.稱(chēng)J為解Ax=b的雅可比迭代法的迭代矩陣.于是雅可比迭代法可寫(xiě)為矩陣形式其Jacobi迭代矩陣為下面給出雅可比迭代法(2.5)的分量計(jì)算公式,記由雅可比迭代法(2.5)有每一個(gè)分量寫(xiě)出來(lái)為即當(dāng)aii0時(shí)，有等價(jià)方程組其中

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

由(2.6)式可知，雅可比迭代法計(jì)算公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算過(guò)程中原始矩陣A始終不變.6.2.2高斯－賽德?tīng)柕ㄔ贘acobi

迭代中，計(jì)算xi(k+1)(2in)時(shí)，使用xj(k+1)代替xj(k)(1ji-1)，即有建立迭代格式或縮寫(xiě)為稱(chēng)為高斯—塞德?tīng)?Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩陣為BG=(D-L)-1U于是高斯—塞德?tīng)柕蓪?xiě)為矩陣形式

這就是說(shuō)，選取分裂矩陣M為A的下三角部分,即選取M=D-L(下三角陣)，A=M-N，由(2.3)式得到解Ax=b的高斯—塞德?tīng)?Gauss—Seidel)迭代法.其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.稱(chēng)矩陣G=(D-L)-1U為解Ax=b的高斯—塞德?tīng)柕ǖ牡仃?由高斯—塞德?tīng)柕?2.7)有每一個(gè)分量寫(xiě)出來(lái)為即當(dāng)aii0時(shí)，有(與前面一樣的式子)或于是，解Ax=b的高斯—塞德?tīng)柕ǖ挠?jì)算公式為或

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

可看作雅可比迭代法的一種改進(jìn).由(2.8)可知，高斯—塞德?tīng)柕矫康淮沃恍栌?jì)算一次矩陣與向量的乘法.

算法1(高斯—塞德?tīng)柕?見(jiàn)書(shū)p139.

例2

用高斯—塞德?tīng)柕ń饫?的方程組(1.2).

解用高斯—塞德?tīng)柕剑喝(0)=(0,0,0)T.迭代到第7次有

由此例可知，用高斯—塞德?tīng)柕?，雅可比迭代法解線(xiàn)性方程組(1.2)(且取x(0)=0)均收斂，而高斯—塞德?tīng)柕ū妊趴杀鹊ㄊ諗枯^快(即取相同的x(0)，達(dá)到同樣精度所需迭代次數(shù)較少)，但這結(jié)論只當(dāng)A滿(mǎn)足一定條件時(shí)才是對(duì)的.

例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

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

解：Gauss-Seidel

迭代格式為

例2

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

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

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

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

其逐次超松弛迭代矩陣為

逐次超松弛法可寫(xiě)為矩陣形式稱(chēng)為逐次超松弛迭代法，簡(jiǎn)稱(chēng)SOR方法.

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

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

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

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

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

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

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

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

定義2

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

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

例4

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

解顯然,當(dāng)|λ|<1時(shí),則有矩陣序列極限概念可以用矩陣算子范數(shù)來(lái)描述.

定理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)對(duì)任意選擇初始向量x(0)，迭代法(3.5)收斂的充要條件是矩陣B的譜半徑(B)<1.定理4是一階定常迭代法的基本理論.

定理3和定理4的結(jié)論和起來(lái)即為(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)的收斂性.

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

例6

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

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

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

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

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

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

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

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

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

.(1)

如果A的元素滿(mǎn)足稱(chēng)A為嚴(yán)格(按行)對(duì)角占優(yōu)陣.(2)

如果A的元素滿(mǎn)足且上式至少有一個(gè)不等式成立，稱(chēng)A為弱(按行)對(duì)角占優(yōu)陣.

定義4(可約與不可約矩陣)

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

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

A為可約矩陣意即A可經(jīng)過(guò)若干行列重排化為(3.6)或Ax=b可化為兩個(gè)低階方程組求解(如果A經(jīng)過(guò)兩行交換的同時(shí)進(jìn)行相應(yīng)兩列的交換，稱(chēng)對(duì)A進(jìn)行一次行列重排).

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

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

例7

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

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

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

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

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

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

迭代法均收斂.

(2)A為弱對(duì)角占優(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為對(duì)稱(chēng)正定矩陣，A=D-L-LT;

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

由定理3證明中可知，如果(B)<1且(B)越小時(shí)，迭代法收斂越快.現(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*滿(mǎn)足且設(shè)迭代法收斂，即