教學(xué)第2章線性方程組的迭代法課件

第2章解線性方程組的迭代法n元線性方程組（2.1）或

Ax=b思路與解f(x)=0的不動(dòng)點(diǎn)迭代相似……,將Ax=b等價(jià)改寫為x=Mx+f,建立迭代x(k+1)=Mx(k)+f,從初值x(0)出發(fā)，得到序列{x(k)}.研究內(nèi)容：如何建立迭代格式？收斂速度？向量序列的收斂條件？誤差估計(jì)？（2.2）1科大研究生學(xué)位課程第2章解線性方程組的迭代法n元線性方程組（2.1）2.1迭代法的一般理論

為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要對Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，——向量和矩陣的范數(shù)。在一維數(shù)軸上，實(shí)軸上任意一點(diǎn)x到原點(diǎn)的距離用|x|表示。而任意兩點(diǎn)x1，x2之間距離用|x1-x2|表示。2科大研究生學(xué)位課程2.1迭代法的一般理論 為了研究線性方程組近似解的向量和矩陣的范數(shù)

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

表示。推廣到n維空間，則稱為向量范數(shù)。3科大研究生學(xué)位課程向量和矩陣的范數(shù) 而在二維平面上，平面上任意一點(diǎn)P(x,y)2.1.1向量和矩陣的范數(shù)向量的范數(shù)

定義2.2設(shè)‖‖是向量空間Rn上的實(shí)值函數(shù),且滿足條件:(1)非負(fù)性:對任何向量xRn

,‖x‖0,且‖x‖=0當(dāng)且僅當(dāng)x=0(2)齊次性:對任何向量x

Rn

和實(shí)數(shù),

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

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

4科大研究生學(xué)位課程2.1.1向量和矩陣的范數(shù)向量的范數(shù)定義2.2記x=(x1,x2,…,xn)T,常用的向量范數(shù)有:

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

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

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

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

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

,‖x‖=4.雖然不同范數(shù)的值可能不同，但它們間存在等價(jià)關(guān)系.定理(范數(shù)的等價(jià)性)對于Rn上的任何兩種范數(shù)‖‖和‖‖,存在正常數(shù)m,M,使得m‖x‖‖x‖

M‖x‖,xRn5科大研究生學(xué)位課程記x=(x1,x2,…,xn)T,常用的向量范數(shù)有常用的三種向量范數(shù)滿足如下等價(jià)關(guān)系

‖x‖‖x‖1

n‖x‖,xRn定義設(shè)向量序列

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

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

易見,

6科大研究生學(xué)位課程常用的三種向量范數(shù)滿足如下等價(jià)關(guān)系定義2.矩陣的范數(shù)

定義2.3設(shè)‖‖是以n階方陣為變量的實(shí)值函數(shù),且滿足條件:(1)非負(fù)性:‖A‖0,且‖A‖=0當(dāng)且僅當(dāng)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科大研究生學(xué)位課程2.矩陣的范數(shù)定義2.3設(shè)‖‖是以n階方陣為變

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

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

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

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

解

‖A‖1=4,‖A‖=5,‖A‖F(xiàn)8科大研究生學(xué)位課程矩陣的-范數(shù):‖A‖,也稱為行范數(shù).矩設(shè)‖‖是一種向量范數(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è)‖‖是一種算子范數(shù),則9科大研究生學(xué)位課程設(shè)‖‖是一種向量范數(shù),則定義稱之為由向量范數(shù)派生矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.設(shè)是矩陣A的特征值,x是對應(yīng)的特征向量,則有

Ax=x利用向量和矩陣范數(shù)的相容性,則得||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖設(shè)n階矩陣A的n個(gè)特征值為1,2,…,n,則稱為矩陣A的譜半徑.對矩陣的任何一種相容范數(shù)都有(A)‖A‖另外,>0,一種相容范數(shù),使‖A‖(A)+10科大研究生學(xué)位課程矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.任何兩種矩陣范數(shù)也具有等價(jià)性m‖A‖‖A‖

M‖A‖,ARnn矩陣序列的收斂性也定義為11科大研究生學(xué)位課程任何兩種矩陣范數(shù)也具有等價(jià)性矩陣序列的收斂性12科大研究生學(xué)位課程12科大研究生學(xué)位課程把n元線性方程組（2.1）或

Ax=b改寫成等價(jià)的方程組或x=Mx+f2.1.2迭代格式的構(gòu)造

（2.2）13科大研究生學(xué)位課程把n元線性方程組（2.1）或Ax=b改寫成等價(jià)由此建立方程組的迭代格式

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科大研究生學(xué)位課程由此建立方程組的迭代格式

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,…可見,當(dāng)k時(shí),e(k)0MkO.對任意初始向量x(0),迭代法收斂(M)<1.定理2.4證:(必要性）若(M)<1,則存在>0,使得(M)+<1.則由定理2.2‖Mk‖‖M‖k((M)+)k0.若‖Mk‖0,k(M)=(Mk)‖Mk‖0,所以(M)<1.15科大研究生學(xué)位課程x(k+1)=Mx(k)+f

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

定理2.5-6

證由于

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*)于是有

‖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科大研究生學(xué)位課程若‖M‖<1,則對任意x(0),迭代所以上述定理只是收斂的充分條件,并不必要,如則‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F(xiàn)=1.17但(M)=0.8<1,所以迭代法是收斂的.由(2.10)式可見,‖M‖越小收斂越快,且當(dāng)‖x

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

(k)-x(k-1)‖<作為迭代終止的條件.17科大研究生學(xué)位課程所以上述定理只是收斂的充分條件,并不必要,如則‖M‖1,即若使‖x(k)–x*‖<,只需可以事先估計(jì)達(dá)到某一精度需要迭代多少步.線性方程組的迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(Sor)迭代法.18科大研究生學(xué)位課程

2.2．雅克比（Jacobi）迭代法若系數(shù)矩陣非奇異，且

(i=1,2,…,n)，將方程組改成19科大研究生學(xué)位課程2.2．雅克比（Jacobi）迭代法若系數(shù)矩陣非奇異，且然后寫成迭代格式（2.11）（2.11）式也可以簡單地寫為（2.11’）20科大研究生學(xué)位課程然后寫成迭代格式（2.11）（2.11）式也可以簡單地寫為（寫成矩陣形式：A=－L－UDBJacobi迭代陣(2.12)21科大研究生學(xué)位課程寫成矩陣形式：A=－L－UDBJacobi迭代陣(2.1算法2.1（Jacobi迭代法）：程序見P19。22科大研究生學(xué)位課程算法2.1（Jacobi迭代法）：程序見P19。22科大研究2.2.2Jacobi迭代法的收斂條件迭代格式收斂(B)<1

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

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

證

A=D-L-U=D(I-D-1(L+U))=因?yàn)锳是嚴(yán)格對角占優(yōu)矩陣,所以det(D)0,而且因此,(B)‖B‖<1,故=1不是B的特征值,det(I-B)0.所以,det(A)0.D(I-B)23科大研究生學(xué)位課程2.2.2Jacobi迭代法的收斂條件迭代格式收斂證明：③由條件知，A為列對角占優(yōu)陣，則AT為行對角占優(yōu)陣，有＃證畢①A為行對角占優(yōu)陣②A為列對角占優(yōu)陣24科大研究生學(xué)位課程證明：③由條件知，A為列對角占優(yōu)陣，則AT為行對角占優(yōu)陣，為了加快收斂速度，同時(shí)為了節(jié)省計(jì)算機(jī)的內(nèi)存，我們作如下的改進(jìn)：每算出一個(gè)分量的近似值，立即用到下一個(gè)分量的計(jì)算中去，即用迭代格式：

2.3高斯――賽得爾(Gauss-Seidel)迭代法逐一寫出來即為25科大研究生學(xué)位課程2.3高斯――賽得爾(Gauss-S…………只存一組向量即可。寫成矩陣形式：BGauss-Seidel迭代陣2.3高斯――賽得爾(Gauss-Seidel)迭代法(2.14)(2.16)26科大研究生學(xué)位課程…………只存一組向量即可。寫成矩陣形程序見P23。算法2.2（Gauss-Seidel迭代法）：27科大研究生學(xué)位課程程序見P23。算法2.2（Gauss-Seidel迭代法）：

例用雅可比迭代法解方程組解：雅可比迭代格式為28科大研究生學(xué)位課程例用雅可比迭代法解方程組解：雅28科大研究生學(xué)位課kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取計(jì)算如下29科大研究生學(xué)位課程kx1(k)x2(k)x3(k)10.720.830.84

解：Gauss-Seidel

迭代格式為

例用Gauss—Seidel迭代法解上題。30科大研究生學(xué)位課程Gauss-Seidel迭代格式為例用Gaus取x(0)=(0,0,0)T

計(jì)算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.331科大研究生學(xué)位課程kx1(k)x2(k)x3(k)10.720.9021.12.3.2收斂條件我們看一下Gauss-Seidel迭代法收斂的充分條件定理：若A滿足下列條件之一，則Seidel

i迭代收斂。①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)=032科大研究生學(xué)位課程2.3.2收斂條件我們看一下Gauss-Seidel迭若||1,則矩陣(D-L)-U是嚴(yán)格對角占優(yōu)矩陣,這與det((D-L)-U)=0矛盾,所以||<1,于是(B)<1.注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，Gauss-Seidel法也可能不收斂。33科大研究生學(xué)位課程若||1,則矩陣(D-L)-U是2.4逐次超松弛迭代法記則可以看作在前一步上加一個(gè)修正量。若在修正量前乘以一個(gè)因子，有對Gauss－Seidel迭代格式(2.22)34科大研究生學(xué)位課程2.4逐次超松弛迭代法記則可以看作在前一步上加一個(gè)修正量。故SOR的迭代格式（2.23）SOR的迭代矩陣35科大研究生學(xué)位課程故SOR的迭代格式（2.23）SOR的迭代矩陣35科大研究生用分量形式討論，設(shè)加速（迭代公式）是松馳因子(0<<2),當(dāng)0<<1時(shí)叫低松弛，>1時(shí)叫超松弛，=1時(shí)，就是Gauss-Seidel迭代法。36科大研究生學(xué)位課程用分量形式討論，設(shè)加速（迭代公式）是松馳因子(0<<2)程序見P28。算法2.3（SOR迭代法）：37科大研究生學(xué)位課程程序見P28。算法2.3（SOR迭代法）：37科大研究生學(xué)位例用SOR方法解線性方程組解SOR方法迭代公式為方程組的精確解是x*=(2,1,-1)T.取x(0)=(0,0,0)T,=1.46,計(jì)算結(jié)果如下:38科大研究生學(xué)位課程例用SOR方法解線性方程組解SOR方法迭代公式為方程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從結(jié)果可見,迭代20次時(shí)已獲得精確到小數(shù)點(diǎn)后五位的近似解.如果取=1.25,則需要迭代56次才能得到具有同樣精度的近似解;如果取=1,則需迭代110次以上.39科大研究生學(xué)位課程kx1(k)x2(k)x3(k)0000從結(jié)果可見2.4.2SOR迭代法的收斂條件迭代格式收斂(B)<1

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

SOR方法收斂的必要條件是0<<2.證設(shè)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<<240科大研究生學(xué)位課程2.4.2SOR迭代法的收斂條件迭代格式

定理2.11設(shè)A是對稱正定矩陣,則當(dāng)0<<2時(shí),解方程組Ax=b的SOR方法收斂.

證設(shè)是B的任一特征值,y是對應(yīng)的特征向量,則[(1-)D+U]y=(D-L)y于是(1-)(Dy,y)+(Uy,y)=[(Dy,y)-(Ly,y)]由于A=D-L-U是對稱正定的,所以D是正定矩陣,且L=UT.若記(Ly,y)=+i,則有(Dy,y)=>041科大研究生學(xué)位課程定理2.11設(shè)A是對稱正定矩陣,則當(dāng)0<<2時(shí)(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly,y)=-i0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以當(dāng)0<<2時(shí),有(-+)2-(-)2=(2-)(2-)=(2-)(2-)<0所以||2<1,因此(B)<1,即S0R方法收斂.42科大研究生學(xué)位課程(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly

推論2.1

A是對稱正定矩陣,Jacobi迭代法收斂的充要條件是2D-A也對稱正定。

證設(shè)是Jacobi迭代矩陣B的任一特征值,y是對應(yīng)的特征向量,則(L+U)y=Dy于是(Ly,y)+(Uy,y)=(Dy,y)可得=2/當(dāng)A對稱正定時(shí),即2-<0時(shí),||<12+>0而((2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,當(dāng)A對稱正定時(shí),Jacobi迭代法收斂2D-A正定.43科大研究生學(xué)位課程推論2.1A是對稱正定矩陣,Jacobi迭代法收

SOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取=*,使(B)達(dá)到最小,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.4<<1.6.44科大研究生學(xué)位課程SOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.第2章解線性方程組的迭代法n元線性方程組（2.1）或

Ax=b思路與解f(x)=0的不動(dòng)點(diǎn)迭代相似……,將Ax=b等價(jià)改寫為x=Mx+f,建立迭代x(k+1)=Mx(k)+f,從初值x(0)出發(fā)，得到序列{x(k)}.研究內(nèi)容：如何建立迭代格式？收斂速度？向量序列的收斂條件？誤差估計(jì)？（2.2）45科大研究生學(xué)位課程第2章解線性方程組的迭代法n元線性方程組（2.1）2.1迭代法的一般理論

為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要對Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，——向量和矩陣的范數(shù)。在一維數(shù)軸上，實(shí)軸上任意一點(diǎn)x到原點(diǎn)的距離用|x|表示。而任意兩點(diǎn)x1，x2之間距離用|x1-x2|表示。46科大研究生學(xué)位課程2.1迭代法的一般理論 為了研究線性方程組近似解的向量和矩陣的范數(shù)

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

表示。推廣到n維空間，則稱為向量范數(shù)。47科大研究生學(xué)位課程向量和矩陣的范數(shù) 而在二維平面上，平面上任意一點(diǎn)P(x,y)2.1.1向量和矩陣的范數(shù)向量的范數(shù)

定義2.2設(shè)‖‖是向量空間Rn上的實(shí)值函數(shù),且滿足條件:(1)非負(fù)性:對任何向量xRn

,‖x‖0,且‖x‖=0當(dāng)且僅當(dāng)x=0(2)齊次性:對任何向量x

Rn

和實(shí)數(shù),

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

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

48科大研究生學(xué)位課程2.1.1向量和矩陣的范數(shù)向量的范數(shù)定義2.2記x=(x1,x2,…,xn)T,常用的向量范數(shù)有:

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

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

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

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

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

,‖x‖=4.雖然不同范數(shù)的值可能不同，但它們間存在等價(jià)關(guān)系.定理(范數(shù)的等價(jià)性)對于Rn上的任何兩種范數(shù)‖‖和‖‖,存在正常數(shù)m,M,使得m‖x‖‖x‖

M‖x‖,xRn49科大研究生學(xué)位課程記x=(x1,x2,…,xn)T,常用的向量范數(shù)有常用的三種向量范數(shù)滿足如下等價(jià)關(guān)系

‖x‖‖x‖1

n‖x‖,xRn定義設(shè)向量序列

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

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

易見,

50科大研究生學(xué)位課程常用的三種向量范數(shù)滿足如下等價(jià)關(guān)系定義2.矩陣的范數(shù)

定義2.3設(shè)‖‖是以n階方陣為變量的實(shí)值函數(shù),且滿足條件:(1)非負(fù)性:‖A‖0,且‖A‖=0當(dāng)且僅當(dāng)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ù).51科大研究生學(xué)位課程2.矩陣的范數(shù)定義2.3設(shè)‖‖是以n階方陣為變

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

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

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

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

解

‖A‖1=4,‖A‖=5,‖A‖F(xiàn)52科大研究生學(xué)位課程矩陣的-范數(shù):‖A‖,也稱為行范數(shù).矩設(shè)‖‖是一種向量范數(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è)‖‖是一種算子范數(shù),則53科大研究生學(xué)位課程設(shè)‖‖是一種向量范數(shù),則定義稱之為由向量范數(shù)派生矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.設(shè)是矩陣A的特征值,x是對應(yīng)的特征向量,則有

Ax=x利用向量和矩陣范數(shù)的相容性,則得||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖設(shè)n階矩陣A的n個(gè)特征值為1,2,…,n,則稱為矩陣A的譜半徑.對矩陣的任何一種相容范數(shù)都有(A)‖A‖另外,>0,一種相容范數(shù),使‖A‖(A)+54科大研究生學(xué)位課程矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.任何兩種矩陣范數(shù)也具有等價(jià)性m‖A‖‖A‖

M‖A‖,ARnn矩陣序列的收斂性也定義為55科大研究生學(xué)位課程任何兩種矩陣范數(shù)也具有等價(jià)性矩陣序列的收斂性56科大研究生學(xué)位課程12科大研究生學(xué)位課程把n元線性方程組（2.1）或

Ax=b改寫成等價(jià)的方程組或x=Mx+f2.1.2迭代格式的構(gòu)造

（2.2）57科大研究生學(xué)位課程把n元線性方程組（2.1）或Ax=b改寫成等價(jià)由此建立方程組的迭代格式

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,…58科大研究生學(xué)位課程由此建立方程組的迭代格式

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,…可見,當(dāng)k時(shí),e(k)0MkO.對任意初始向量x(0),迭代法收斂(M)<1.定理2.4證:(必要性）若(M)<1,則存在>0,使得(M)+<1.則由定理2.2‖Mk‖‖M‖k((M)+)k0.若‖Mk‖0,k(M)=(Mk)‖Mk‖0,所以(M)<1.59科大研究生學(xué)位課程x(k+1)=Mx(k)+f

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

定理2.5-6

證由于

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*)于是有

‖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*‖60科大研究生學(xué)位課程若‖M‖<1,則對任意x(0),迭代所以上述定理只是收斂的充分條件,并不必要,如則‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F(xiàn)=1.17但(M)=0.8<1,所以迭代法是收斂的.由(2.10)式可見,‖M‖越小收斂越快,且當(dāng)‖x

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

(k)-x(k-1)‖<作為迭代終止的條件.61科大研究生學(xué)位課程所以上述定理只是收斂的充分條件,并不必要,如則‖M‖1,即若使‖x(k)–x*‖<,只需可以事先估計(jì)達(dá)到某一精度需要迭代多少步.線性方程組的迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(Sor)迭代法.62科大研究生學(xué)位課程

2.2．雅克比（Jacobi）迭代法若系數(shù)矩陣非奇異，且

(i=1,2,…,n)，將方程組改成63科大研究生學(xué)位課程2.2．雅克比（Jacobi）迭代法若系數(shù)矩陣非奇異，且然后寫成迭代格式（2.11）（2.11）式也可以簡單地寫為（2.11’）64科大研究生學(xué)位課程然后寫成迭代格式（2.11）（2.11）式也可以簡單地寫為（寫成矩陣形式：A=－L－UDBJacobi迭代陣(2.12)65科大研究生學(xué)位課程寫成矩陣形式：A=－L－UDBJacobi迭代陣(2.1算法2.1（Jacobi迭代法）：程序見P19。66科大研究生學(xué)位課程算法2.1（Jacobi迭代法）：程序見P19。22科大研究2.2.2Jacobi迭代法的收斂條件迭代格式收斂(B)<1

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

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

證

A=D-L-U=D(I-D-1(L+U))=因?yàn)锳是嚴(yán)格對角占優(yōu)矩陣,所以det(D)0,而且因此,(B)‖B‖<1,故=1不是B的特征值,det(I-B)0.所以,det(A)0.D(I-B)67科大研究生學(xué)位課程2.2.2Jacobi迭代法的收斂條件迭代格式收斂證明：③由條件知，A為列對角占優(yōu)陣，則AT為行對角占優(yōu)陣，有＃證畢①A為行對角占優(yōu)陣②A為列對角占優(yōu)陣68科大研究生學(xué)位課程證明：③由條件知，A為列對角占優(yōu)陣，則AT為行對角占優(yōu)陣，為了加快收斂速度，同時(shí)為了節(jié)省計(jì)算機(jī)的內(nèi)存，我們作如下的改進(jìn)：每算出一個(gè)分量的近似值，立即用到下一個(gè)分量的計(jì)算中去，即用迭代格式：

2.3高斯――賽得爾(Gauss-Seidel)迭代法逐一寫出來即為69科大研究生學(xué)位課程2.3高斯――賽得爾(Gauss-S…………只存一組向量即可。寫成矩陣形式：BGauss-Seidel迭代陣2.3高斯――賽得爾(Gauss-Seidel)迭代法(2.14)(2.16)70科大研究生學(xué)位課程…………只存一組向量即可。寫成矩陣形程序見P23。算法2.2（Gauss-Seidel迭代法）：71科大研究生學(xué)位課程程序見P23。算法2.2（Gauss-Seidel迭代法）：

例用雅可比迭代法解方程組解：雅可比迭代格式為72科大研究生學(xué)位課程例用雅可比迭代法解方程組解：雅28科大研究生學(xué)位課kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取計(jì)算如下73科大研究生學(xué)位課程kx1(k)x2(k)x3(k)10.720.830.84

解：Gauss-Seidel

迭代格式為

例用Gauss—Seidel迭代法解上題。74科大研究生學(xué)位課程Gauss-Seidel迭代格式為例用Gaus取x(0)=(0,0,0)T

計(jì)算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.375科大研究生學(xué)位課程kx1(k)x2(k)x3(k)10.720.9021.12.3.2收斂條件我們看一下Gauss-Seidel迭代法收斂的充分條件定理：若A滿足下列條件之一，則Seidel

i迭代收斂。①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)=076科大研究生學(xué)位課程2.3.2收斂條件我們看一下Gauss-Seidel迭若||1,則矩陣(D-L)-U是嚴(yán)格對角占優(yōu)矩陣,這與det((D-L)-U)=0矛盾,所以||<1,于是(B)<1.注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，Gauss-Seidel法也可能不收斂。77科大研究生學(xué)位課程若||1,則矩陣(D-L)-U是2.4逐次超松弛迭代法記則可以看作在前一步上加一個(gè)修正量。若在修正量前乘以一個(gè)因子，有對Gauss－Seidel迭代格式(2.22)78科大研究生學(xué)位課程2.4逐次超松弛迭代法記則可以看作在前一步上加一個(gè)修正量。故SOR的迭代格式（2.23）SOR的迭代矩陣79科大研究生學(xué)位課程故SOR的迭代格式（2.23）SOR的迭代矩陣35科大研究生用分量形式討論，設(shè)加速（迭代公式）是松馳因子(0<<2),當(dāng)0<<1時(shí)叫低松弛，>1時(shí)叫超松弛，=1時(shí)，就是Gauss-Seidel迭代法。80科大研究生學(xué)位課程用分量形式討論，設(shè)加速（迭代公式）是松馳因子(0<<2)程序見P28。算法2.3（SOR迭代法）：81科大研究生學(xué)位課程程序見P28。算法2.3（SOR迭代法）