《應(yīng)用數(shù)值分析》課件數(shù)值分析5.5線性方程組的數(shù)值解法

第5章線性方程組的數(shù)值解法對(duì)線性方程組要求尋找更經(jīng)濟(jì)、適用的數(shù)值解法.其中A為非奇異矩陣,當(dāng)A為低階稠密矩陣時(shí),選主元消去法(直接法)是有效的.但對(duì)于大型稀疏矩陣方程組(A的階數(shù)n很大

104，但零元素較多),方程組的階數(shù)很高,則運(yùn)算量將會(huì)很大并且大量占用計(jì)算機(jī)資源.利用迭代法求解是合適的.§5.5

雅可比迭代法和高斯-賽德?tīng)柕?/p>

將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德?tīng)柕ǎ沙诘?，而超松弛迭代法?yīng)用很廣泛。

則(1)式和(2)式同解,稱(chēng)(1)與(2)等價(jià).

例1求解方程組記為Ax=b，其中此方程組的精確解是x*=(3,2,1)T.現(xiàn)將(1.2)改寫(xiě)為迭代法的基本概念

下面舉簡(jiǎn)例，以便了解迭代法的思想.或?qū)憺閤=B0x+f，其中取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ì)算程序，得到一向量序列簡(jiǎn)寫(xiě)為x(k+1)=B0x(k)+f，其中k表示迭代次數(shù)(k=0,1,2,

).

迭代到第10次有一般的計(jì)算公式(迭代公式)

從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有

對(duì)于任何一個(gè)方程組x=Bx+f(由Ax=b變形得到的等價(jià)方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請(qǐng)考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！x*=(-3,-4)T

這種方式就稱(chēng)為迭代法.以上過(guò)程稱(chēng)為迭代過(guò)程.迭代法產(chǎn)生一個(gè)序列則稱(chēng)迭代法收斂,否則稱(chēng)為發(fā)散.(3)

如果對(duì)于任意其極限存在,即

對(duì)線性方程組(2),采用以下迭代步驟:

迭代法的基本思想是通過(guò)構(gòu)造迭代格式產(chǎn)生迭代序列，由迭代序列來(lái)逼近原方程組的解，因此，要解決的基本問(wèn)題有：1.如何構(gòu)造迭代格式

2.迭代序列是否收斂設(shè)線性方程組(1)的一般形式為Jacobi迭代G-S迭代SOR迭代法(4)5.5.1

Jacobi迭代法由(4)建立Jacobi迭代公式為(5)將(5)式轉(zhuǎn)化為矩陣形式矩陣形式為稱(chēng)(5)、(6)式為解線性方程組(1)的Jacobi迭代法(J法)(6)(5)用Jacobi迭代法求解方程組,誤差不超過(guò)1e-4解:例2依此類(lèi)推,得方程組滿(mǎn)足精度的解為x12迭代次數(shù)為12次x4=3.02411.94780.9205d=0.1573x5=3.00031.98401.0010d=0.0914x6=2.99382.00001.0038d=0.0175x7=2.99902.00261.0031d=0.0059x8=3.00022.00060.9998d=0.0040x9=3.00031.99990.9997d=7.3612e-004x10=3.00001.99990.9999d=2.8918e-004x11=3.00002.00001.0000d=1.7669e-004x12=3.00002.00001.0000d=3.0647e-0055.5.2Gauss-Seidel迭代法分析Jacobi迭代法(5)的迭代過(guò)程稱(chēng)(7)、(8)式為解線性方程組(1)的Gauss-Seidel迭代法(G-S法)

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

,i-1).

可看作雅可比迭代法的一種改進(jìn).高斯—塞德?tīng)柕矫康淮沃恍栌?jì)算一次矩陣與向量的乘法.G-S迭代法有一個(gè)明顯的優(yōu)點(diǎn)是：在計(jì)算時(shí)，只需一組工作單元，以便存放近似解.而J迭代法需要兩組工作單元，分別存放

和

.例3解:用Gauss-Seidel迭代法求解方程組,誤差不超過(guò)1e-4x1=2.50002.09091.2273d=3.4825x2=2.97732.02891.0041d=0.5305x3=3.00981.99680.9959d=0.0465x4=2.99981.99971.0002d=0.0112x5=2.99982.00011.0001d=3.9735e-004x6=3.00002.00001.0000d=1.9555e-004x7=3.00002.00001.0000d=1.1576e-005通過(guò)迭代,至第7步得到滿(mǎn)足精度的解x7Jacobi迭代法和Gauss-Seidel迭代法均為簡(jiǎn)單迭代法后面我們會(huì)看到，甚至有這樣的方程組，Jacobi迭代收斂，而Gauss-Seidel迭代卻是發(fā)散的.不能說(shuō)G-S法比J法更好.從例2和例3看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要快（達(dá)到同樣的精度所需迭代次數(shù)較少).但這個(gè)結(jié)論，在一定條件下才是對(duì)的.

練習(xí)

用Jacobi和Gauss-Seidel迭代法解方程組

Jacobi迭代

Gauss-Seidel迭代解：

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é)果如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3

Jacobi迭代Gauss-Seidel迭代5.5.3迭代法的收斂性設(shè)解線性方程組的迭代格式(10)(11)將(10)與(11)相減,得因此迭代法收斂的充要條件可轉(zhuǎn)變?yōu)閯t定理(迭代法收斂的充要條件)

迭代格式收斂的充要條件為(12)

設(shè)Ax=b，其中A=D+L+U為非奇異矩陣,且對(duì)角矩陣D也奇異，則

(1)解線性方程組的雅可比迭代法收斂的充要條件是

(J)<1，其中J=-D-1(L+U).

(2)解線性方程組的高斯-塞德?tīng)柕ㄊ諗康某湟獥l件是

(G)<1，其中G=-(D+L)-1U.

(3)雅可比迭代法收斂的充分條件是||J||<1.(4)高斯-塞德?tīng)柕ㄊ諗康某浞謼l件是||G||<1.

由定理5.5.1和定理5.5.2可知解：方程組的迭代格式為取，問(wèn)雅可比迭代法是否收斂？若收斂，需要迭代多少次，才能保證各分量的誤差絕對(duì)值小于10-6？例4：用雅可比方法解下列方程組迭代陣所以要保證各分量的誤差絕對(duì)值小于10-6，需要迭代14次

求迭代矩陣的譜半徑，需要求迭代矩陣的特征值，對(duì)高階矩陣是比較麻煩的。利用定理5.5.1去判別比較方便一些。但在科學(xué)及工程計(jì)算中，要求解的線性方程組Ax=b,其矩陣A常常具有某些特性.例如，A具有對(duì)角占優(yōu)性質(zhì)或A是對(duì)稱(chēng)正定矩陣等，根據(jù)這些矩陣的性質(zhì)，可以比較方便地判別這些迭代法的收斂性。兩種特殊情況1.A為嚴(yán)格(按行)對(duì)角占優(yōu)陣2.A是對(duì)稱(chēng)正定矩陣

定義5.5.3(對(duì)角占優(yōu)陣)設(shè)A=(aij)n×n.如果A的元素滿(mǎn)足稱(chēng)A為嚴(yán)格(按行)對(duì)角占優(yōu)陣.矩陣A的每一行對(duì)角元素的絕對(duì)值都嚴(yán)格大于非對(duì)角元素絕對(duì)值之和

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

如果A=(aij)n×n為嚴(yán)格對(duì)角占優(yōu)矩陣，則A為非奇異矩陣.

定理5.5.4設(shè)方程組Ax=b，如果A為嚴(yán)格對(duì)角占優(yōu)陣，則解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收斂.證:(1)對(duì)于Jacobi迭代法,其迭代矩陣為根據(jù)定理5.5.1Jacobi迭代法收斂(2)對(duì)于G—S迭代法,其迭代矩陣為不能使用定理5.5.1,而用定理5.5.2.即從而因此由于可得矛盾由定理5.5.2知G—S迭代法收斂。定理5.5.5設(shè)矩陣A對(duì)稱(chēng),且所有對(duì)角元素aii>0,則解線性方程組Ax=b的Jacobi迭代法收斂的充要條件是A及2D-A均為正定矩陣,其中D=(a11,…,ann).(2)解線性方程組Ax=b的Gauss-Seidel迭代法收斂的充分條件是A正定.

如果線性方程組系數(shù)矩陣A對(duì)稱(chēng)正定，則有以下的收斂定理.

例5已知方程組判斷雅可比迭代法和高斯—塞德?tīng)柗ǖ臄可⑿裕?/p>

解

因?yàn)橄禂?shù)矩陣A的順序主子式所以A是正定矩陣.也是正定矩陣，故Jacobi迭代法收斂.

再由A是對(duì)稱(chēng)正定矩陣，故

Gauss—Seidel迭代法也收斂.又由于

例6

在線性方程組Ax=b中，證明：當(dāng)-1/2<a<1時(shí)高斯-塞德?tīng)柗ㄊ諗?，而雅可比法只?1/2<a<1/2時(shí)才收斂.即A正定，所以當(dāng)-1/2<a<1時(shí)高斯-賽德?tīng)柗ㄊ諗?

證明

因?yàn)楫?dāng)-1/2<a<1時(shí)，得A的順序主子式

對(duì)雅可比法迭代矩陣故只在

(J)=|2a|<1，即|a|<1/2時(shí)雅可比法收斂.當(dāng)a=0.8時(shí),G-S法收斂，

(J)=1.6>1，J法不收斂.Ax=b，例8判別下列方程組用J法和G-S法求解是否收斂因此不能用定理5.5.1，只能用定理5.5.2判斷(1)Jacobi法的迭代矩陣解:即Jacobi迭代法收斂(2)Gauss-Seidel法的迭代矩陣同樣用定理5.5.2判斷即Gauss-Seidel迭代法發(fā)散該例說(shuō)明G-S法發(fā)散時(shí)而J法卻收斂！例9

討論用Jacobi迭代法和Gauss-Seidel迭代法求解方程組