版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領
文檔簡介
第六章線性方程組迭代解法內容提要§6.1概論§6.2(I)Jacobi
迭代法
§6.2(II)Gauss-Seidel迭代法§6.3迭代法的收斂性§6.4
SOR法本章學習要點概
論引子迭代法的基本思想迭代法的主要步驟引子直接法得到的解是理論上準確的，但是我們可以看得出，它們的計算量都是n3數量級，存儲量為n2量級，這在n比較小的時候還比較合適（n<400），但是對于現在的很多實際問題，往往要我們求解很大的n的矩陣，而且這些矩陣(系數矩陣)往往是含有大量的0元素。對于這類的矩陣，再用直接法時就會耗費大量的時間和存儲單元。另一方面,實際計算結果精度有時無法保.主要原因是在多次消去、回代過程中四則運算的誤差積累與傳播無法控制.因此我們有必要引入一類新的方法：迭代法。返回節迭代法的基本思想迭代法是解線性方程組的一個重要的實用方法，特別適用于求解在實際中大量出現的，系數矩陣為稀疏陣的大型線性方程組。迭代法的基本思想是去構成一個向量序列{X(k)}，，并且X*就是要求解使其收斂至某個極限向量X*的方程組：AX=b的準確解。返回節迭代法的主要步驟解線性方程組迭代法的主要步驟是:
1.把所給的線性方程組AX=b化成如下形式的同解方程組（1),按迭X=BX+f2.給出初始向量代公式(k=0,1,2,…)（2)X(k+1)=BX(k)+f進行計算。nTn(0)
(0)(0)1
2(0)X
=
(x
,
x
),
x
?
R如果按上述迭代公式所得到的向量序列{X
(k)}收斂于某個向量X
*
,則X*
就是方程組
AX
=b
的解，并稱此迭代法收斂。否則，就叫不收斂或發散。式(1)、(2)中的矩陣B
，稱為迭代矩陣。研究
內容：
如何建立迭代格式？
向量序列的收斂條件？
收斂速度？
誤差估計？本章重要介紹三個迭代法，即：1）Jacobi迭代法,2）Gauss-Seidel
迭代法,3）超松弛迭代法（SOR法）及其收斂性。返回章§3.2(I)Jacobi迭代法數學問題的描述Jacobi迭代法的主要步驟數學問題的描述設有線性方程組AX
=b即aa
x
+
ax
+
a
x
+
+
a
x
=
bx
+
+
a
x
=
ban1
x1
+
an2
x2
+
+
ann
xn
=
bn21
1
22
2
2n
n
211n
n12
211
1（3）其中
A=(aij)nn
非奇異（|A|?0），且a
ii≠0
(i=1,2,…,n),
由式（3）得aii
xi(i
=
1,2,,
n)
（4）=
bi
-
aij
x
jj
?i返回引用若記00
002122
2n
n1
n2
nn
-
a1n
0
-
a12
0
-
aU
=
-
a
-
a
-
aL
=
aaa11D
=
（5）（6）則有A=D-L-U成立，而式（3-4）的矩陣形式為DX
=（L+U）X+b等式兩邊乘以D-1，得X=
D-1（L+U）X+
D-1b由此得到迭代公式X（k+1）=
D-1（L+U）X（k）+
D-1b（7）即(i
=
1,2,,
n)(k
=
0,1,2,)
（8）)
/
aa
x=
(b
-xii(
k
)j
?iij
ji(
k
+1)i這種迭代法，稱為Jacobi迭代法。返回節
...
...
...
...
an1x1
+an2
x2
+...+annxn
=bn
a21x1
+a22x2
+...+a2n
xn
=b2
a11x1
+a12x2
+...+a1n
xn
=b1aii
?0寫成矩陣形式：A
=-L-UDAx
=
b(D
-(L
+U
))x
=
bDx
=
(L
+U
)x
+
bx=
D-1
(L
+U
)x
+
D-1bBfJacobi
迭代陣kk+1x
=
D-1(L
+U)x
+D-1bJacobi
迭代法33a22aaa11D
=nn
210L
=-a31
n1-a
0-a32
0
-a
-an2
-an3
0232n
U
=0
-a12
-a13
-a1n
0
-a
-a
0
-a3n
03312132221233132J2naa-1a-1-1B
=D-1(L+U)
=a-10
0
-a1n-a
0
+
3n
11
n1
n2
n3
nn
-a
-a
0
-a
-a0
-a
-a
-a
0
0-a
-a
-a
0
1111112122222233333300nnnnnnaaaaaaaaaaaaaa
0-
a12-
a13-
a1
n--
a
23-
a
2
nB
J
=-31
-
a
32-
a
3
n
-
a
n
1-
a
n
2-
a
n3
0雅可比(Jacobi)迭代法每迭代一次主要近似計算一次矩陣乘向量；計算過程中,初始數據A始終不變;,需要兩J迭代矩陣
B
=
D-1
(
L
+
U
)
;(
k
)JB
X計算過程中涉及到的中間變量X
(K
)及X
(k
+1)組工作單元x(n), y(n)來存儲.Jacobi
迭代法的計算步驟(5步)為：①k=1；輸入最大迭代次數N，誤差ε以及迭代初值
X=（x1，x2，…
，xn）②(i
=
1,2,；,
n)yi
=
(bi
-
aij
x
j
)
/
aiij?i③
如果||Y-X||<ε，則輸出Y=（y1，y2，…
，yn）。④k=k+1，如果k>N，算法失敗。⑤置X=Y，即xi=yi
(i=1,2,…,n)，轉②；Jacobi迭代法的主要步驟例1=
62
3
4141
2
33
x2
-
x3
+
8
x4
=
152
x
-
x
+
10
x
-
x
10
x1
-
x2
+
2
x3求解
-
x
+
11x
-
x
+
3
x
=
25=
-11)
/
8)
/
1143412(
k
)31(
k
)2
(
k
+1)4(
k
)(
k
)(
k
+1)2
1(
k
)3(
k
)3(
k
)2(
k
+1)+
xx
=
(15
-
3
xx(
k
+1)
=
(-11
-
2
x(
k
)
+
x(
k
)
+
x(
k
)
)
/
10)
/
10-
3
x=
(25
+
x
+
xx-
2
x=
(6
+
xx解:Jacobi迭代公式為：選取X（0）=(0,0,0,0)T,迭代10次，結果見表1
返回引用kx1（k）x2（k）x3（k）x4（k）00.00000.00000.00000.000010.60002.2727-1.10001.875021.04731.7157-0.80520.885230.93262.0533-1.04931.130941.01521.9537-0.96810.973950.98902.0114-1.01031.021461.00321.9922-0.99450.994470.99812.0023-1.00201.003681.00061.9987-0.99900.998990.99972.0004-1.00041.0006101.00011.9998-1.99980.9998例3.1迭代結果表1返回引用法并沒有充分及時地利用這些信息,為此我們得到改進的格式,稱為高斯—塞德爾(Gauss–Seidel)迭代公式。i在計算迭代值
x(k
+1)
,
利用它前面已計算的值(
)
(
)
(
)而此時x,x
,,x
也已計算,但是Jacobi迭代k
+1k
+1
k
+11
2
i
-1Jacobi迭代法的改進對于Jacobi迭代法,它的每一步設定計算順序為x1
fi
x2
fi
fi
xnjxl(
j
=1,
2,
n;l
=1,,
k
)§3.2(II)Gauss-Seidel迭代法算法分析與描述實例求解算法分析與描述a
xxii(k
)ij
j(k
)ij
ji-
a
x=
(b
-
i
-1
n(k
+1)i)
/
a
(i
=
1,2,,
n)
(8)可寫成形如原Jacobi迭代公式(8)=
(b
-xa
x
)
/
aii
(i
=
1,2,,
n)(k
=
0,1,2,)
(
k
)ij
jj
?ii(
k
+1)ij=1
j=i
+1在Jacobi
迭代中，是用X(k)的全部分量來計算X(k+1)的全部分量的。i我們應該注意到，在計算新分量x
(k+1)時，分量x1(k+1),x2(k+1),…,xi-1(k+1)都已經算出。返回引用如果Jacobi
法收斂，則可期望X(k+1)比X(k)更好，在式(8)中右邊第1個求和號中，用X(k+1)的分量代替X(k)的分量，似乎更合理些。這對許多問題來說，不僅會加快收斂速度，更重要的是，在排程序時，不必另設一套單元來記存上一次的近似解。這就是逐個代換算法，又稱Gauss-Seidel迭代法。因此，我們就得到新的迭代公式：xn(k
)a
x
-=
(b
-
ij
j
iij=i
+1i
-1i
ij
jj=1(k
+1)(k
+1)ia
x
)
/
a
(i
=
1,2,,
n)（9)這就是Gauss-Seidel迭代公式．X(k+1)=BG
X(k)
+
fG（10）其中BG=(D-L)-1U，fG=(D-L)-1b，稱BG為G-S迭代矩陣。由于Gauss-Seidel迭代法逐次用計算出來的新值代替舊值，所以在收斂的條件下，它要比Jacobi迭代法收斂速度快。返回節Gauss-Seidel迭代公式的其矩陣形式為：實例求解
4(
k
+1)(
k
+1)1(
k
+1)2(
k
+1)3(15
-
3
x
(
k
+1)
+
x
(
k
+1)
)
/
82
3x(-11
-
2
x
(
k
+1)
+
x
(
k
+1)
+
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論