高斯-賽德爾疊代

高斯－賽德爾迭代（Gauss–Seidel method）是數值線性代數中的一個迭代法，可用來求出線性方程組解的近似值。該方法以卡爾·弗里德里希·高斯和路德維希·賽德爾（英語：Philipp Ludwig von Seidel）命名。

算法

對於一個含有n個未知量及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}}}$

為了求這個方程組的解${\displaystyle {\vec {x}}}$，我們使用迭代法。k用來計量迭代步數。給定該方程組解的一個近似值${\displaystyle {\vec {x}}^{\,k}\in \mathbb {R} ^{n}}$。在求k+1步近似值時，我們利用第m個方程求解第m個未知量。在求解過程中，所有已解出的k+1步元素都被直接使用。這一點與雅可比法不同。對於每個元素可以使用如下公式

${\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.}$

重複上述的求解過程，可以得到一個線性方程組解的近似值數列：${\displaystyle {\vec {x}}^{0},{\vec {x}}^{1},{\vec {x}}^{2},\ldots }$。在該方法收斂的前提下，此數列收斂於${\displaystyle {\vec {x}}}$. 可以證明數列收斂若線性方程組係數矩陣為對稱正定矩陣(symmetric positive definite matrix)或對角優勢矩陣(diagonally dominant matrix)。

為了保證該方法可以進行，主對角線元素${\displaystyle a_{mm}}$需非零。

矩陣分解

線性方程組的係數${\displaystyle a_{ij}\,(i,j=1,2,\ldots ,n)}$可以被寫成矩陣形式 ${\displaystyle A\in \mathbb {R} ^{n\times n}}$, 該矩陣的第i行第j列元素滿足 ${\displaystyle (A)_{i,j}=a_{ij}}$。方程組的右邊項可以被寫成向量形式 ${\displaystyle {\vec {b}}\in \mathbb {R} ^{n}:\,({\vec {b}})_{i}=b_{i}}$。 線性方程組因此可以被寫成矩陣運算形式

${\displaystyle A{\vec {x}}={\vec {b}}}$

矩陣${\displaystyle A}$可以分解成如下形式

${\displaystyle A=D+L+U}$,

其中${\displaystyle D\in \mathbb {R} ^{n\times n}}$為一個對角矩陣滿足${\displaystyle (D)_{i,i}=(A)_{i,i}}$, ${\displaystyle L,\,U}$均為嚴格三角矩陣： ${\displaystyle L}$為嚴格下三角矩陣， ${\displaystyle U}$ 為嚴格上三角矩陣。

例子

${\displaystyle A={\begin{pmatrix}1&2&2\\3&1&4\\5&3&1\end{pmatrix}}}$， ${\displaystyle D={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}}$， ${\displaystyle L={\begin{pmatrix}0&0&0\\3&0&0\\5&3&0\end{pmatrix}}}$， ${\displaystyle U={\begin{pmatrix}0&2&2\\0&0&4\\0&0&0\end{pmatrix}}}$.

高斯－賽德爾迭代的每一步可以寫成如下形式

${\displaystyle D{\vec {x}}^{\,k+1}={\vec {b}}-L{\vec {x}}^{\,k+1}-U{\vec {x}}^{\,k}}$.

此形式的導出

如上形式來自於高斯－賽德爾迭代的元素公式: 對於第m個未知量${\displaystyle ({\vec {x}}^{\,k+1})_{m}=x_{m}^{k+1}}$, 我們可以得出 ${\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}}$ 已知${\displaystyle a_{mm}\neq 0}$, ${\displaystyle (L)_{m,j}=0\,(\forall j\geq m)}$ 以及 ${\displaystyle (U)_{m,j}=0\,(\forall j\leq m)}$，因此可以得出 ${\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
        ${\displaystyle \sigma \leftarrow 0}$
        for j from 1 until n do
            if j ≠ i then
                ${\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}}$
            end if
        end (j - loop)
        ${\displaystyle \phi _{i}\leftarrow {\frac {1}{a_{ii}}}(b_{i}-\sigma )}$
    end (i-loop)
    check if convergence is reached（检查是否已收敛）
end (repeat)

參見

• 雅可比法