此條目
不完整 。
請幫忙改善本條目,或到討論頁 去討論該條目的問題。
高斯-賽德爾疊代 (Gauss–Seidel method )是數值線性代數 中的一個疊代法 ,可用來求出線性方程組 解的近似值。該方法以卡爾·弗里德里希·高斯 和路德維希·賽德爾 命名。
對於一個含有n個未知量及n個等式的如下線性方程組
a
11
⋅
x
1
+
a
12
⋅
x
2
+
…
+
a
1
n
⋅
x
n
=
b
1
,
a
21
⋅
x
1
+
a
22
⋅
x
2
+
…
+
a
2
n
⋅
x
n
=
b
2
,
⋮
=
⋮
a
n
1
⋅
x
1
+
a
n
2
⋅
x
2
+
…
+
a
n
n
⋅
x
n
=
b
n
.
{\displaystyle {\begin{aligned}a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+\ldots +a_{1n}\cdot x_{n}&=b_{1},\\a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+\ldots +a_{2n}\cdot x_{n}&=b_{2},\\\vdots \qquad \qquad \qquad &=\vdots \\a_{n1}\cdot x_{1}+a_{n2}\cdot x_{2}+\ldots +a_{nn}\cdot x_{n}&=b_{n}.\end{aligned}}}
為了求這個方程組的解
x
→
{\displaystyle {\vec {x}}}
,我們使用疊代法 。k用來計量疊代步數。給定該方程組解的一個近似值
x
→
k
∈
R
n
{\displaystyle {\vec {x}}^{\,k}\in \mathbb {R} ^{n}}
。在求k+1步近似值時,我們利用第m個方程式求解第m個未知量。在求解過程中,所有已解出的k+1步元素都被直接使用。這一點與雅可比法 不同。對於每個元素可以使用如下公式
x
m
k
+
1
=
1
a
m
m
(
b
m
−
∑
j
=
1
m
−
1
a
m
j
⋅
x
j
k
+
1
−
∑
j
=
m
+
1
n
a
m
j
⋅
x
j
k
)
,
1
≤
m
≤
n
.
{\displaystyle x_{m}^{k+1}={\frac {1}{a_{mm}}}\left(b_{m}-\sum _{j=1}^{m-1}a_{mj}\cdot x_{j}^{k+1}-\sum _{j=m+1}^{n}a_{mj}\cdot x_{j}^{k}\right),\quad 1\leq m\leq n.}
重複上述的求解過程,可以得到一個線性方程組解的近似值數列:
x
→
0
,
x
→
1
,
x
→
2
,
…
{\displaystyle {\vec {x}}^{0},{\vec {x}}^{1},{\vec {x}}^{2},\ldots }
。在該方法收斂的前提下,此數列收斂 於
x
→
{\displaystyle {\vec {x}}}
. 可以證明數列收斂若線性方程組係數矩陣為對稱正定矩陣 (symmetric positive definite matrix)或對角優勢矩陣 (diagonally dominant matrix)。
為了保證該方法可以進行,主對角線 元素
a
m
m
{\displaystyle a_{mm}}
需非零。
線性方程組的係數
a
i
j
(
i
,
j
=
1
,
2
,
…
,
n
)
{\displaystyle a_{ij}\,(i,j=1,2,\ldots ,n)}
可以被寫成矩陣形式
A
∈
R
n
×
n
{\displaystyle A\in \mathbb {R} ^{n\times n}}
, 該矩陣的第i行第j列元素滿足
(
A
)
i
,
j
=
a
i
j
{\displaystyle (A)_{i,j}=a_{ij}}
。方程組的右邊項可以被寫成向量形式
b
→
∈
R
n
:
(
b
→
)
i
=
b
i
{\displaystyle {\vec {b}}\in \mathbb {R} ^{n}:\,({\vec {b}})_{i}=b_{i}}
。 線性方程組因此可以被寫成矩陣運算形式
A
x
→
=
b
→
{\displaystyle A{\vec {x}}={\vec {b}}}
矩陣
A
{\displaystyle A}
可以分解成如下形式
A
=
D
+
L
+
U
{\displaystyle A=D+L+U}
,
其中
D
∈
R
n
×
n
{\displaystyle D\in \mathbb {R} ^{n\times n}}
為一個對角矩陣 滿足
(
D
)
i
,
i
=
(
A
)
i
,
i
{\displaystyle (D)_{i,i}=(A)_{i,i}}
,
L
,
U
{\displaystyle L,\,U}
均為嚴格三角矩陣 :
L
{\displaystyle L}
為嚴格下三角矩陣,
U
{\displaystyle U}
為嚴格上三角矩陣。
例子
A
=
(
1
2
2
3
1
4
5
3
1
)
{\displaystyle A={\begin{pmatrix}1&2&2\\3&1&4\\5&3&1\end{pmatrix}}}
,
D
=
(
1
0
0
0
1
0
0
0
1
)
{\displaystyle D={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}}
,
L
=
(
0
0
0
3
0
0
5
3
0
)
{\displaystyle L={\begin{pmatrix}0&0&0\\3&0&0\\5&3&0\end{pmatrix}}}
,
U
=
(
0
2
2
0
0
4
0
0
0
)
{\displaystyle U={\begin{pmatrix}0&2&2\\0&0&4\\0&0&0\end{pmatrix}}}
.
高斯-賽德爾疊代的每一步可以寫成如下形式
D
x
→
k
+
1
=
b
→
−
L
x
→
k
+
1
−
U
x
→
k
{\displaystyle D{\vec {x}}^{\,k+1}={\vec {b}}-L{\vec {x}}^{\,k+1}-U{\vec {x}}^{\,k}}
.
此形式的導出
如上形式來自於高斯-賽德爾疊代的元素公式: 對於第m個未知量
(
x
→
k
+
1
)
m
=
x
m
k
+
1
{\displaystyle ({\vec {x}}^{\,k+1})_{m}=x_{m}^{k+1}}
, 我們可以得出
(
D
x
→
k
+
1
)
m
=
(
b
→
)
m
−
(
L
x
→
k
+
1
)
m
−
(
U
x
→
k
)
m
⇒
a
m
m
x
m
k
+
1
=
b
m
−
∑
j
=
1
n
(
L
)
m
,
j
x
j
k
+
1
−
∑
j
=
1
n
(
U
)
m
,
j
x
j
k
{\displaystyle (D{\vec {x}}^{\,k+1})_{m}=({\vec {b}})_{m}-(L{\vec {x}}^{\,k+1})_{m}-(U{\vec {x}}^{\,k})_{m}\Rightarrow a_{mm}x_{m}^{k+1}=b_{m}-\sum _{j=1}^{n}(L)_{m,j}x_{j}^{k+1}-\sum _{j=1}^{n}(U)_{m,j}x_{j}^{k}}
已知
a
m
m
≠
0
{\displaystyle a_{mm}\neq 0}
,
(
L
)
m
,
j
=
0
(
∀
j
≥
m
)
{\displaystyle (L)_{m,j}=0\,(\forall j\geq m)}
以及
(
U
)
m
,
j
=
0
(
∀
j
≤
m
)
{\displaystyle (U)_{m,j}=0\,(\forall j\leq m)}
,因此可以得出
x
m
k
+
1
=
1
a
m
m
(
b
m
−
∑
j
=
1
m
−
1
(
L
)
m
,
j
x
j
k
+
1
−
∑
j
=
m
+
1
n
(
U
)
m
,
j
x
j
k
)
=
1
a
m
m
(
b
m
−
∑
j
=
1
m
−
1
a
m
j
x
j
k
+
1
−
∑
j
=
m
+
1
n
a
m
j
x
j
k
)
{\displaystyle x_{m}^{\,k+1}={\frac {1}{a_{mm}}}\left(b_{m}-\sum _{j=1}^{m-1}(L)_{m,j}x_{j}^{\,k+1}-\sum _{j=m+1}^{n}(U)_{m,j}x_{j}^{\,k}\right)={\frac {1}{a_{mm}}}\left(b_{m}-\sum _{j=1}^{m-1}a_{mj}x_{j}^{\,k+1}-\sum _{j=m+1}^{n}a_{mj}x_{j}^{\,k}\right)}
.
因為元素可以被重新賦值為在這個算法中計算得到的新值,所以只需要保存一個向量,而向量索引被省略。該算法如下:
输入: A , b
输出:
ϕ
{\displaystyle \phi }
初始化一個的猜測結果
ϕ
{\displaystyle \phi }
repeat until convergence(收敛)
for i from 1 until n do
σ
←
0
{\displaystyle \sigma \leftarrow 0}
for j from 1 until n do
if j ≠ i then
σ
←
σ
+
a
i
j
ϕ
j
{\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}}
end if
end (j - loop)
ϕ
i
←
1
a
i
i
(
b
i
−
σ
)
{\displaystyle \phi _{i}\leftarrow {\frac {1}{a_{ii}}}(b_{i}-\sigma )}
end (i -loop)
check if convergence is reached(检查是否已收敛)
end (repeat)