數(shù)值分析~第2章 線性方程組的迭代法yjs11

第2章解線性方程組的迭代法n元線性方程組

（2.1）

或

Ax=b思路與解f(x)=0的不動點迭代相似……,將Ax=b等價改寫為x=Mx+f,建立迭代x(k+1)=Mx(k)+f,從初值x(0)出發(fā)，得到序列{x(k)}.研究內(nèi)容：如何建立迭代格式？收斂速度？向量序列的收斂條件？誤差估計？

（2.2）

1數(shù)值分析第2章2.1迭代法的一般理論

為了研究線性方程組近似解的誤差估計和迭代法的收斂性，我們需要對Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，——向量和矩陣的范數(shù)。在一維數(shù)軸上，實軸上任意一點x到原點的距離用|x|表示。而任意兩點x1，x2之間距離用|x1-x2|表示。2數(shù)值分析第2章2.1.1向量和矩陣的范數(shù)

而在二維平面上，平面上任意一點P(x,y)到原點的距離用表示。而平面上任意兩點P1(x1,y1),P2(x2,y2)的距離用

表示。推廣到n維空間，則稱為向量范數(shù)。3數(shù)值分析第2章2.1.1

向量和矩陣的范數(shù)向量的范數(shù)

定義2.2設‖‖是向量空間Rn上的實值函數(shù),且滿足條件:

(1)非負性:對任何向量xRn

,‖x‖0,且‖x‖=0當且僅當x=0

(2)齊次性:對任何向量x

Rn

和實數(shù),

‖x‖=||‖x‖

(3)三角不等式:對任何向量x,yRn

‖x+y‖‖x‖+‖y‖則稱‖‖為空間Rn上的范數(shù),‖x‖為向量x的范數(shù).

4數(shù)值分析第2章記x=(x1,x2,…,xn)T,常用的向量范數(shù)有:

向量的1-范數(shù):‖x‖1=|x1|+|x2|+…+|xn|

向量的2-范數(shù):‖x‖2=

向量的-范數(shù):‖x‖=

例

設向量x=(2,-4,3,1)T,求向量范數(shù)‖x‖p,p=1,2,.

解

由定義‖x‖1=10,‖x‖2=

,‖x‖=4.

雖然不同范數(shù)的值可能不同，但它們間存在等價關系.定理

(范數(shù)的等價性)

對于Rn

上的任何兩種范數(shù)‖‖和‖‖,存在正常數(shù)m,M,使得

m

‖x‖‖x‖

M

‖x‖,xRn5數(shù)值分析第2章常用的三種向量范數(shù)滿足如下等價關系

‖x‖‖x‖1

n‖x‖,xRn定義

設向量序列

k=1,2,…,向量如果

則稱向量序列{x(k)}收斂于向量x*,記作

易見,

6數(shù)值分析第2章2.矩陣的范數(shù)

定義2.3設‖‖是以n階方陣為變量的實值函數(shù),且滿足條件:

(1)非負性:‖A‖0,且‖A‖=0當且僅當A=0

(2)齊次性:‖A‖=||‖A‖,R

(3)三角不等式:‖A+B‖‖A‖+‖B‖

(4)相容性:‖AB‖‖A‖‖B‖則稱‖A‖為矩陣A的范數(shù).

記A=(aij),常用的矩陣范數(shù)有:

矩陣的1-范數(shù):‖A‖1

,也稱矩陣的列范數(shù).

矩陣的2-范數(shù):‖A‖2

,也稱為譜范數(shù).7數(shù)值分析第2章

矩陣的-范數(shù):‖A‖

,也稱為行范數(shù).

矩陣的F-范數(shù):‖A‖F(xiàn)

例

設矩陣求矩陣A的范數(shù)‖A‖p,p=1,2,,F.

解

‖A‖1=4,‖A‖=5,‖A‖F(xiàn)8數(shù)值分析第2章設‖‖是一種向量范數(shù),則定義稱之為由向量范數(shù)派生的矩陣算子范數(shù).

矩陣的算子范數(shù)滿足

‖Ax‖‖A‖‖x‖,xRn把滿足上式的矩陣范數(shù)稱為與向量范數(shù)相容的矩陣范數(shù).

對于p=1,2,,矩陣范數(shù)‖A‖p是由向量范數(shù)‖x‖p派生的矩陣算子范數(shù),所以‖A‖p是與‖x‖p相容的矩陣范數(shù).但‖A‖F(xiàn)不是一種算子范數(shù),卻與‖x‖2是相容的.設‖‖是一種算子范數(shù),則9數(shù)值分析第2章矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.設是矩陣A的特征值,x是對應的特征向量,則有

Ax=x利用向量和矩陣范數(shù)的相容性,則得

||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖設n階矩陣A的n個特征值為1,2,…,n,則稱

為矩陣A的譜半徑.

定理2.1對矩陣的任何一種相容范數(shù)都有

(A)‖A‖另外,定理2.2：對

>0,一種相容范數(shù),使‖A‖(A)+.10數(shù)值分析第2章

任何兩種矩陣范數(shù)也具有等價性

m‖A‖‖A‖

M‖A‖,ARnn

矩陣序列的收斂性也定義為

證若‖Ak‖0,則k(A)=(Ak)‖Ak‖0,所以(A)<1.

若(A)<1,則存在>0,使得(A)+<1.則定理設A是一n*n的矩陣,則

的充分必要條件是(A)<1.‖Ak‖‖A‖k

((A)+)k

0.（定理2.2）11數(shù)值分析第2章12數(shù)值分析第2章把n元線性方程組

（2.1）

或

Ax=b改寫成等價的方程組

或x=Mx+f2.1.2迭代格式的構造

（2.2）

13數(shù)值分析第2章由此建立方程組的迭代格式

x(k+1)=Mx(k)+f,k=0,1,2,…(2.5)其中M稱為迭代矩陣。

對任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2,…,

如果向量序列{x(k)}收斂于x*,由(2.5)式可得

x*=Mx*+f

從而x*是方程組x=Mx+f

的解,也就是方程組Ax=b的解.對迭代格式(2.5),定義誤差向量

e(k)=x(k)-x*,則迭代法收斂就是e(k)0.由于

x(k+1)=Mx(k)+f

k=0,1,2,…

x*=Mx*+f

k=0,1,2,…14數(shù)值分析第2章

x(k+1)=Mx(k)+f

k=0,1,2,…

x*=Mx*+f

k=0,1,2,…所以

e(k+1)=Me(k),

k=0,1,2,…遞推可得

e(k)=Mke(0),

k=0,1,2,…可見,當k時,e(k)0Mk

O.

對任意初始向量x(0),迭代法收斂(M)<1.定理2.4證:(必要性）

若(M)<1,則存在>0,使得(M)+<1.則由定理2.2若‖Mk‖0,k(M)=(Mk)‖M

k‖0,所以(M)<1.2.1.3迭代的收斂性‖Mk‖‖M‖k

((M)+)k0.15數(shù)值分析第2章

若‖M‖=q<1,則對任意x(0),迭代(2.5)式收斂,而且

定理2.5-6證:先證式(2.10).考慮x(k+1)=Mx(k)+f,x(k)=Mx(k-1)+f,x*=Mx*+f所以

x(k+1)-x(k)=M(x

(k)-x(k-1)),x(k+1)–x*=M(x

(k)–x*)取范數(shù)，得

‖x(k+1)-x(k)‖‖M‖‖x

(k)-x(k-1)‖,‖x(k+1)–x*‖‖M‖‖x

(k)–x*‖‖x(k+1)-x(k)‖=‖(x

(k+1)–x*)-(x(k)–x*)‖‖x

(k)–x*‖-‖x(k+1)–x*‖

(1-‖M‖)‖x(k)–x*‖因此16數(shù)值分析第2章上述定理只是收斂的充分條件,并不必要,如則‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F(xiàn)=1.17但(M)=0.8<1,所以迭代法是收斂的.由(2.10)式可見,‖M‖越小收斂越快,且當‖x

(k)-x(k-1)‖很時,‖x(k)–x*‖就很小,實際上用‖x

(k)-x(k-1)‖<作為迭代終止的條件.若使‖x(k)–x*‖<,只需即可以事先估計達到某一精度需要迭代多少步.17數(shù)值分析第2章2.2．雅克比（Jacobi）迭代法若系數(shù)矩陣非奇異，且

(i=1,2,…,n)，將方程組改成18數(shù)值分析第2章然后寫成迭代格式（2.11）（2.11）式也可以簡單地寫為（2.11’）19數(shù)值分析第2章寫成矩陣形式：A=－L－UDBJacobi迭代陣(2.12)20數(shù)值分析第2章算法2.1（Jacobi迭代法）：程序見P19。舉例2.11.輸入矩陣A=(aij),b=(b1,…,bn),初始向量x(0)=(x1(0),…,xn(0)),精度要求ε，最大的迭代次數(shù)N，置k=0;

2.對i=1,2,…,n,計算3.若‖x(k+1)-x(k)‖<ε,則停算，輸出x(k+1)為近似解；否則，轉4

4.若k<N,置k:=k+1,轉步2；否則，停算，輸出迭代失敗信息.

21數(shù)值分析第2章2.2.2Jacobi迭代法的收斂條件迭代格式收斂(B)<1

。若‖B‖<1迭代法收斂.定理2.7：若系數(shù)矩陣A滿足下列條件之一，則Jacobi迭代收斂。①A為行對角占優(yōu)陣②A為列對角占優(yōu)陣③A滿足對于Jacobi迭代，我們有一些保證收斂的充分條件.

引理若A是嚴格對角占優(yōu)矩陣,則det(A)0.

證

A=D-L-U=D(I-D-1(L+U))=

因為A是嚴格對角占優(yōu)矩陣,所以det(D)0,而且因此,(B)‖B‖<1,故=1不是B的特征值,det(I-B)0.所以,det(A)0.D(I-B)22數(shù)值分析第2章證明：③

由條件知，A為列對角占優(yōu)陣，則AT為行對角占優(yōu)陣，有＃證畢①A為行對角占優(yōu)陣②A為列對角占優(yōu)陣23數(shù)值分析第2章例設線性方程組Ax=b的系數(shù)矩陣其中a為參數(shù)，問a為何值時，Jacobi迭代法收斂？所以，Jacobi迭代迭代矩陣為求BJ的特征根24數(shù)值分析第2章若用充分條件顯然，充分條件比充要條件弱。25數(shù)值分析第2章為了加快收斂速度，同時為了節(jié)省計算機的內(nèi)存，我們作如下的改進：每算出一個分量的近似值，立即用到下一個分量的計算中去，即用迭代格式：

2.3高斯――賽得爾(Gauss-Seidel)迭代法逐一寫出來即為26數(shù)值分析第2章…………只存一組向量即可。寫成矩陣形式：BGauss-Seidel

迭代陣(2.14)(2.16)27數(shù)值分析第2章程序見P23。算法2.2（Gauss-Seidel迭代法）：1.輸入矩陣A=(aij),b=(b1,…,bn),初始向量x(0)=(x1(0),…,xn(0)),精度要求ε，最大的迭代次數(shù)N，置k=0;

2.計算對i=2,…,n-1,計算3.若‖x(k+1)-x(k)‖<ε,則停算，輸出x(k+1)為近似解；否則，轉4

4.若k<N,置k:=k+1,轉步2；否則，停算，輸出迭代失敗信息.

28數(shù)值分析第2章

例

用雅可比迭代法解方程組解：雅可比迭代格式為29數(shù)值分析第2章kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取計算如下30數(shù)值分析第2章

解：Gauss-Seidel迭代格式

例

用Gauss—Seidel迭代法解上題。31數(shù)值分析第2章取x(0)=(0,0,0)T

計算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.332數(shù)值分析第2章2.3.2Gauss-Seidel迭代法收斂條件考察Gauss-Seidel迭代法收斂的充分條件定理：若A滿足下列條件之一，則Seideli迭代收斂。①A為行或列對角占優(yōu)陣②A對稱正定陣（證略書上定理2.9）迭代格式收斂(B)<1

。若‖B‖<1迭代法收斂.

det(I-B)=det(I-(D-L)-1U)證明：=det((D-L)-1)det((D-L)-U)=0所以有det((D-L)-U)=0若||1,

則矩陣(D-L)-U

是嚴格對角占優(yōu)矩陣,這與det((D-L)-U)=0矛盾,所以||<1,于是(B)<1.33數(shù)值分析第2章注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時，Jacobi法可能不收斂；而Jacobi法收斂時，Gauss-Seidel法也可能不收斂。例設線性方程組Ax=b的系數(shù)矩陣判斷解Ax=b的Jacobi迭代法和G-S迭代法的收斂性。解：易見A是嚴格對角占優(yōu)矩陣，故J法和G-S法收斂。34數(shù)值分析第2章1、Jacobi迭代的迭代矩陣特征值為2、Gauss－Siedel迭代例已知方程組的系數(shù)矩陣判斷解Ax=b的Jacobi迭代法和G-S迭代法的收斂性。35數(shù)值分析第2章2.4逐次超松弛迭代法記則可以看作在前一步上加一個修正量。若在修正量前乘以一個因子，有對Gauss－Seidel迭代格式有(2.22)故SOR(SuccessiveOverRelaxation)的迭代格式（2.23）36數(shù)值分析第2章SOR的迭代矩陣用分量形式討論，設松弛（2.24）是松馳因子(0<<2),當0<<1時叫低松弛，>1時叫超松弛，=1時，就是Gauss-Seidel迭代法。37數(shù)值分析第2章程序見P28。算法2.3（SOR迭代法）1.輸入矩陣A=(aij),b=(b1,…,bn),初始向量x(0)=(x1(0),…,xn(0)),精度要求ε，最大的迭代次數(shù)N，參數(shù)ω；置k=0;

2.計算對i=2,…,n-1,計算3.若‖x(k+1)-x(k)‖<ε,則停算，輸出x(k+1)為近似解；否則，轉4

4.若k<N,置k:=k+1,轉步2；否則，停算，輸出迭代失敗信息.

38數(shù)值分析第2章

例用SOR方法解線性方程組解SOR方法迭代公式(2.24)為方程組的精確解是x*=(2,1,-1)T.取x(0)=(0,0,0)T,=1.46,計算結果如下:39數(shù)值分析第2章kx1(k)x2(k)x3(k)0123…2003.652.321669102.5661399……1.999998700.88458820.42309390.6948261……1.00000130-0.2021098-0.22243214-0.4952594……-1.0000034

從結果可見,迭代20次時已獲得精確到小數(shù)點后五位的近似解.如果取=1.25,則需要迭代56次才能得到具有同樣精度的近似解;如果取=1,則需迭代110次以上.40數(shù)值分析第2章2.4.2SOR迭代法的收斂條件迭代格式收斂(B)<1

。若‖B‖<1迭代法收斂.對于SOR迭代，我們有一些收斂的結果.定理2.10

SOR方法收斂的必要條件是0<<2.證設SOR方法收斂,則(B)<1,所以|det(B)|=|12…n|<1而

det(B)=det[(D-L)-1((1-)D+U)]=det[(I-D-1L)-1]det[(1-)I+D-1U)]=(1-)n于是

|1-|<1,或0<<241數(shù)值分析第2章

定理2.11

設A是對稱正定矩陣,則當0<<2時,解方程組Ax=b的SOR方法收斂.

證設是B的任一特征值,y是對應的特征向量(復向量),則[(1-)D+U]y=

(D-L)y于是作內(nèi)積，有(1-)(Dy,