高斯-赛德尔迭代

高斯－赛德尔迭代（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) 

參見

• 雅可比法