高斯-赛德尔迭代

Template:Incomplete Template:NoteTA Template:Unreferenced 高斯－赛德尔迭代（Template:Lang）是数值线性代数中的一个迭代法，可用来求出线性方程组解的近似值。该方法以卡爾·弗里德里希·高斯和Template:Link-en命名。

算法

对于一个含有n个未知量及n个等式的如下线性方程组

$\begin{array}{cc}{a}_{11}\cdot x_1+a_{12}\cdot x_2+\dots +a_{1n}\cdot x_n& =b_1,\\ a_{21}\cdot x_1+a_{22}\cdot x_2+\dots +a_{2n}\cdot x_n& =b_2,\\ ⋮& =⋮\\ a_{n1}\cdot x_1+a_{n2}\cdot x_2+\dots +a_{nn}\cdot x_n& =b_n.\end{array}$

为了求这个方程组的解$\overrightarrow{x}$，我们使用迭代法。k用来计量迭代步数。给定该方程组解的一个近似值${\overrightarrow{x}}^k\in {ℝ}^n$。在求k+1步近似值时，我们利用第m个方程求解第m个未知量。在求解过程中，所有已解出的k+1步元素都被直接使用。这一点与雅可比法不同。对于每个元素可以使用如下公式

$x_m^{k+1}=\frac{1}{a_{mm}}(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),1\le m\le n.$

重复上述的求解过程，可以得到一个线性方程组解的近似值数列：${\overrightarrow{x}}^0,{\overrightarrow{x}}^1,{\overrightarrow{x}}^2,\dots$。在该方法收敛的前提下，此数列收敛于$\overrightarrow{x}$. 可以證明數列收斂若線性方程組係數矩陣為對稱正定矩陣(symmetric positive definite matrix)或對角優勢矩陣(diagonally dominant matrix)。

为了保证该方法可以进行，主对角线元素$a_{mm}$需非零。

矩阵分解

线性方程组的系数$a_{ij}(i,j=1,2,\dots ,n)$可以被写成矩阵形式 $A\in {ℝ}^{n\times n}$, 该矩阵的第i行第j列元素满足 $(A{)}_{i,j}=a_{ij}$。方程组的右边项可以被写成向量形式 $\overrightarrow{b}\in {ℝ}^n:(\overrightarrow{b}{)}_i=b_i$。 线性方程组因此可以被写成矩阵运算形式

$A\overrightarrow{x}=\overrightarrow{b}$

矩阵$A$可以分解成如下形式

$A=D+L+U$,

其中$D\in {ℝ}^{n\times n}$为一个对角矩阵满足$(D{)}_{i,i}=(A{)}_{i,i}$, $L,U$均为严格三角矩阵： $L$为严格下三角矩阵， $U$ 为严格上三角矩阵。

例子

$A=\left(\begin{array}{ccc}1& 2& 2\\ 3& 1& 4\\ 5& 3& 1\end{array}\right)$， $D=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$， $L=\left(\begin{array}{ccc}0& 0& 0\\ 3& 0& 0\\ 5& 3& 0\end{array}\right)$， $U=\left(\begin{array}{ccc}0& 2& 2\\ 0& 0& 4\\ 0& 0& 0\end{array}\right)$.

高斯－赛德尔迭代的每一步可以写成如下形式

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

此形式的导出

如上形式来自于高斯－赛德尔迭代的元素公式: 对于第m个未知量$({\overrightarrow{x}}^{k+1}{)}_m=x_m^{k+1}$, 我们可以得出 $(D{\overrightarrow{x}}^{k+1}{)}_m=(\overrightarrow{b}{)}_m-(L{\overrightarrow{x}}^{k+1}{)}_m-(U{\overrightarrow{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_{mm}\ne 0$, $(L{)}_{m,j}=0(\mathrm{\forall }j\ge m)$ 以及 $(U{)}_{m,j}=0(\mathrm{\forall }j\le m)$，因此可以得出 $x_m^{k+1}=\frac{1}{a_{mm}}(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)=\frac{1}{a_{mm}}(b_m-\sum _{j=1}^{m-1}{a}_{mj}{x}_j^{k+1}-\sum _{j=m+1}^n{a}_{mj}{x}_j^k)$.

算法

因为元素可以被重新赋值为在这个算法中计算得到的新值，所以只需要保存一个向量，而向量索引被省略。该算法如下：

输入: Template:Var, Template:Var
输出: $\varphi$

初始化一个的猜测结果$\varphi$

repeat until convergence（收敛）
    for Template:Var from 1 until Template:Var do
        $\sigma \leftarrow 0$
        for Template:Var from 1 until Template:Var do
            if Template:Var ≠ Template:Var then
                $\sigma \leftarrow \sigma +a_{ij}{\varphi }_j$
            end if
        end (Template:Var - loop)
        ${\varphi }_i\leftarrow \frac{1}{a_{ii}}(b_i-\sigma )$
    end (Template:Var-loop)
    check if convergence is reached（检查是否已收敛）
end (repeat)

參見

• 雅可比法