高斯－赛德尔迭代（**'）是数值线性代数中的一个迭代法，可用来求出线性方程组解的近似值。该方法以卡爾·弗里德里希·高斯和命名。
算法
对于一个含有n个未知量及n个等式的如下线性方程组
\begin{align}
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{align}
为了求这个方程组的解\vec{x}，我们使用迭代法。k用来计量迭代步数。给定该方程组解的一个近似值\vec{x}^{\,k}\in\mathbb{R}^{n}。在求k+1步近似值时，我们利用第m个方程求解第m个未知量。在求解过程中，所有已解出的k+1步元素都被直接使用。这一点与雅可比法不同。对于每个元素可以使用如下公式
x^{k+1}_m = \frac{1}{a_{mm}}\left(b_m - \sum_{j=1}^{m-1} a_{mj}\cdot x^{k+1}_j - \sum_{j=m+1}^n a_{mj}\cdot x^{k}_j\right),
\quad 1\leq m\leq n.
重复上述的求解过程，可以得到一个线性方程组解的近似值数列：\vec{x}^{0},\vec{x}^{1},\vec{x}^{2},\ldots。在该方法收敛的前提下，此数列收敛于\vec{x}. 可以證明數列收斂若線性方程組係數矩陣為對稱正定矩陣(symmetric positive definite matrix)或對角優勢矩陣(diagonally dominant matrix)。
为了保证该方法可以进行，主对角线元素a_{mm}需非零。
矩阵分解
线性方程组的系数a_{ij}\, (i,j=1,2,\ldots,n)可以被写成矩阵形式 A\in \mathbb{R}^{n\times n}, 该矩阵的第i行第j列元素满足 (A)_{i,j}=a_{ij}。方程组的右边项可以被写成向量形式 \vec{b}\in\mathbb{R}^{n}:\, (\vec{b})_i=b_i。 线性方程组因此可以被写成矩阵运算形式
A\vec{x} = \vec{b}
矩阵A可以分解成如下形式
A=D+L+U,
其中D\in\mathbb{R}^{n\times n}为一个对角矩阵满足(D)_{i,i}=(A)_{i,i}, L,\,U均为严格三角矩阵： L为严格下三角矩阵， U 为严格上三角矩阵。
例子
A = \begin{pmatrix} 1 & 2 & 2 \\ 3 & 1 & 4 \\ 5 & 3 & 1 \end{pmatrix}， D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}， L = \begin{pmatrix} 0 & 0 & 0 \\ 3 & 0 & 0 \\ 5 & 3 & 0 \end{pmatrix}， U = \begin{pmatrix} 0 & 2 & 2 \\ 0 & 0 & 4 \\ 0 & 0 & 0 \end{pmatrix}.
高斯－赛德尔迭代的每一步可以写成如下形式
D\vec{x}^{\,k+1} = \vec{b} - L\vec{x}^{\,k+1} - U\vec{x}^{\,k} .
:
算法
因为元素可以被重新赋值为在这个算法中计算得到的新值，所以只需要保存一个向量，而向量索引被省略。该算法如下：
输入: ,
输出: \phi
初始化一个的猜测结果\phi
repeat until convergence（收敛）
for from 1 until do
\sigma \leftarrow 0
for from 1 until do
if ≠ then
\sigma \leftarrow \sigma + a_{ij} \phi_j
end if
end ( - loop)
\phi_i \leftarrow \frac 1 {a_{ii}} (b_i - \sigma)
end (-loop)
check if convergence is reached（检查是否已收敛）
end (repeat)
參見
*雅可比法
评论 (0)