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

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

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

雅可比迭代法和高斯-賽德爾迭代法

將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應(yīng)用很廣泛。

則(1)式和(2)式同解,稱(1)與(2)等價.

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

下面舉簡例，以便了解迭代法的思想.或?qū)憺閤=B0x+f，其中取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*呢？回答是不一定.請考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！x*=(-3,-4)T

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

如果對于任意其極限存在,即

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

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

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

Jacobi迭代法由(4)建立Jacobi迭代公式為(5)將(5)式轉(zhuǎn)化為矩陣形式矩陣形式為稱(5)、(6)式為解線性方程組(1)的Jacobi迭代法(J法)(6)(5)用Jacobi迭代法求解方程組,誤差不超過1e-4解:例2依此類推,得方程組滿足精度的解為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)的迭代過程稱(7)、(8)式為解線性方程組(1)的Gauss-Seidel迭代法(G-S法)

雅可比迭代法不使用變量的最新信息計算xi(k+1)，而由高斯-塞德爾迭代公式可知，計算x(k+1)的第i個分量xi(k+1)時，利用了已經(jīng)計算出的最新分量xj(k+1)(j=1,2,

,i-1).

可看作雅可比迭代法的一種改進.高斯—塞德爾迭代公式每迭代一次只需計算一次矩陣與向量的乘法.G-S迭代法有一個明顯的優(yōu)點是：在計算時，只需一組工作單元，以便存放近似解.而J迭代法需要兩組工作單元，分別存放

和

.例3解:用Gauss-Seidel迭代法求解方程組,誤差不超過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通過迭代,至第7步得到滿足精度的解x7Jacobi迭代法和Gauss-Seidel迭代法均為簡單迭代法后面我們會看到，甚至有這樣的方程組，Jacobi迭代收斂，而Gauss-Seidel迭代卻是發(fā)散的.不能說G-S法比J法更好.從例2和例3看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要快（達(dá)到同樣的精度所需迭代次數(shù)較少).但這個結(jié)論，在一定條件下才是對的.

練習(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計算結(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為非奇異矩陣,且對角矩陣D也奇異，則

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

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

(2)解線性方程組的高斯-塞德爾迭代法收斂的充要條件是

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

(3)雅可比迭代法收斂的充分條件是||J||<1.(4)高斯-塞德爾迭代法收斂的充分條件是||G||<1.

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

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

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

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

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

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

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

例5已知方程組判斷雅可比迭代法和高斯—塞德爾法的斂散性？

解

因為系數(shù)矩陣A的順序主子式所以A是正定矩陣.也是正定矩陣，故Jacobi迭代法收斂.

再由A是對稱正定矩陣，故

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

例6

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

證明

因為當(dāng)-1/2<a<1時，得A的順序主子式

對雅可比法迭代矩陣故只在

(J)=|2a|<1，即|a|<1/2時雅可比法收斂.當(dāng)a=0.8時,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ā)散該例說明G-S法發(fā)散時而J法卻收斂！例9

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