高斯-赛德尔迭代

高斯-赛德尔迭代Gauss–Seidel method)是数值线性代数中的一个迭代法,可用来求出线性方程组解的近似值。该方法以卡尔·弗里德里希·高斯路德维希·赛德尔英语Philipp Ludwig von Seidel命名。

算法

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

 

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

 

重复上述的求解过程,可以得到一个线性方程组解的近似值数列: 。在该方法收敛的前提下,此数列收敛 . 可以证明数列收敛若线性方程组系数矩阵为对称正定矩阵(symmetric positive definite matrix)或对角优势矩阵(diagonally dominant matrix)。

为了保证该方法可以进行,主对角线元素 需非零。

矩阵分解

线性方程组的系数 可以被写成矩阵形式  , 该矩阵的第i行第j列元素满足  。方程组的右边项可以被写成向量形式  。 线性方程组因此可以被写成矩阵运算形式

 

矩阵 可以分解成如下形式

 ,

其中 为一个对角矩阵满足 ,  均为严格三角矩阵 为严格下三角矩阵,   为严格上三角矩阵。

例子

    .

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

 .

算法

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

输入: A, b
输出:  

初始化一个的猜测结果 

repeat until convergence(收敛)
    for i from 1 until n do
         
        for j from 1 until n do
            if ji then
                 
            end if
        end (j - loop)
         
    end (i-loop)
    check if convergence is reached(检查是否已收敛)
end (repeat)

参见