列主元高斯消去法、Jacobi 迭代法、Gauss-Seidel 迭代法的比较

列主元高斯消去法、Jacobi 迭代法和Gauss-Seidel 迭代法都是常用的求解线性方程组的方法，它们各有优劣，下面分别介绍它们的特点。 1. 列主元高斯消去法 列主元高斯消去法是一种直接解法，通过高斯消元将线性方程组转化为上三角矩阵，再通过回带求解方程组的未知量。这种方法的优点是精度高，稳定性好，不会出现误差累积的情况。但是，它需要进行大量的矩阵运算，时间复杂度为 $O(n^3)$，并且在某些情况下可能会出现主元为零的情况，需要进行特殊处理。 2. Jacobi 迭代法 Jacobi 迭代法是一种迭代算法，通过将线性方程组拆分为对角线矩阵和非对角线矩阵两部分，反复迭代求解未知量，直到误差满足要求。这种方法的优点是简单易实现，容易理解，而且在一些情况下收敛速度比较快。但是，Jacobi 迭代法的收敛速度并不总是很快，需要对系数矩阵有一定的条件限制才能保证收敛。 3. Gauss-Seidel 迭代法 Gauss-Seidel 迭代法是一种改进型的迭代算法，它在 Jacobi 迭代法的基础上，使用新计算出的未知量代替原方程组中的未知量，从而加速收敛。这种方法的优点是比 Jacobi 迭代法收敛速度更快，而且一般情况下都能保证收敛。但是，Gauss-Seidel 迭代法的实现比 Jacobi 迭代法更为复杂，需要考虑矩阵的对称性和正定性等问题。 综上所述，列主元高斯消去法精度高，但计算复杂度高；Jacobi 迭代法简单易实现，但收敛速度不一定很快；Gauss-Seidel 迭代法收敛速度更快，但实现复杂。根据实际问题的具体情况，选择适合的方法进行求解。

首先给出方程组： $$ \begin{cases} 2x_1+x_2+x_3=5\\ x_1+2x_2+x_3=8\\ x_1+x_2+2x_3=7 \end{cases} $$ ### 列主元高斯消去法 列主元高斯消去法的步骤如下： 1. 将系数矩阵增广，得到增广矩阵 $A^{'}$； 2. 对于 $A^{'}$ 中每一列，选取绝对值最大的元素作为主元素，将其所在行交换到当前处理的行； 3. 以第一行为基准，将第一列中下面的元素消成 $0$，同时记录下消元系数； 4. 以第二行为基准，将第二列中下面的元素消成 $0$，同时记录下消元系数； 5. 以第三行为基准，将第三列中下面的元素消成 $0$，同时记录下消元系数； 6. 消元完成后，回代求解。 可以得到增广矩阵： $$ A^{'}=\left[\begin{matrix} 2 & 1 & 1 & 5\\ 1 & 2 & 1 & 8\\ 1 & 1 & 2 & 7 \end{matrix}\right] $$ 按照第 $1$ 列，第 $2$ 行选择主元素，将第 $2$ 行与第 $1$ 行交换，得到： $$ A^{'}=\left[\begin{matrix} 2 & 1 & 1 & 5\\ 1 & 2 & 1 & 8\\ 1 & 1 & 2 & 7 \end{matrix}\right]\xrightarrow{R_2\leftrightarrow R_1}\left[\begin{matrix} 2 & 1 & 1 & 5\\ 1 & 2 & 1 & 8\\ 1 & 1 & 2 & 7 \end{matrix}\right] $$ 以第一行为基准，将第一列中下面的元素消成 $0$，同时记录下消元系数： $$ \left[\begin{matrix} 2 & 1 & 1 & 5\\ 1 & 2 & 1 & 8\\ 1 & 1 & 2 & 7 \end{matrix}\right]\xrightarrow{\substack{R_2-R_1\times0.5\\R_3-R_1\times0.5}}\left[\begin{matrix} 2 & 1 & 1 & 5\\ 0 & \frac{3}{2} & \frac{1}{2} & \frac{7}{2}\\ 0 & \frac{1}{2} & \frac{3}{2} & \frac{3}{2} \end{matrix}\right] $$ 以第二行为基准，将第二列中下面的元素消成 $0$，同时记录下消元系数： $$ \left[\begin{matrix} 2 & 1 & 1 & 5\\ 0 & \frac{3}{2} & \frac{1}{2} & \frac{7}{2}\\ 0 & \frac{1}{2} & \frac{3}{2} & \frac{3}{2} \end{matrix}\right]\xrightarrow{\substack{R_3-R_2\times\frac{1}{3}}} \left[\begin{matrix} 2 & 1 & 1 & 5\\ 0 & \frac{3}{2} & \frac{1}{2} & \frac{7}{2}\\ 0 & 0 & 1 & 1 \end{matrix}\right] $$ 消元完成后，回代求解： $$ \begin{cases} x_1=1\\ x_2=2\\ x_3=1 \end{cases} $$ 因此，方程组的解为 $x_1=1,x_2=2,x_3=1$。 矩阵 $L$ 和 $U$ 可以通过消元系数得到： $$ L=\left[\begin{matrix} 1 & 0 & 0\\ \frac{1}{2} & 1 & 0\\ \frac{1}{2} & \frac{1}{3} & 1 \end{matrix}\right], U=\left[\begin{matrix} 2 & 1 & 1\\ 0 & \frac{3}{2} & \frac{1}{2}\\ 0 & 0 & 1 \end{matrix}\right] $$ ### Jacobi 迭代法 Jacobi 迭代法的步骤如下： 1. 将系数矩阵 $A$ 拆分成两部分：$A=D-L-U$，其中 $D$ 为 $A$ 的对角线部分，$L$ 为 $A$ 的下三角部分，$U$ 为 $A$ 的上三角部分； 2. 将方程组改写为 $Dx=(L+U)x+b$； 3. 取任意 $x^{(0)}$ 作为初始值； 4. 迭代计算 $x^{(k+1)}=D^{-1}(L+U)x^{(k)}+D^{-1}b$，直到满足精度要求。 将系数矩阵拆分，得到： $$ D=\left[\begin{matrix} 2 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & 2 \end{matrix}\right], L=\left[\begin{matrix} 0 & -1 & -1\\ -1 & 0 & -1\\ -1 & -1 & 0 \end{matrix}\right], U=\left[\begin{matrix} 0 & -1 & -1\\ -1 & 0 & -1\\ -1 & -1 & 0 \end{matrix}\right] $$ 将方程组改写为 $Dx=(L+U)x+b$，得到： $$ \left[\begin{matrix} 2 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & 2 \end{matrix}\right]x=\left[\begin{matrix} 0 & -1 & -1\\ -1 & 0 & -1\\ -1 & -1 & 0 \end{matrix}\right]x+\left[\begin{matrix} 5\\ 8\\ 7 \end{matrix}\right] $$ 取任意 $x^{(0)}$ 作为初始值，比如 $x^{(0)}=\left[\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]$，迭代计算 $x^{(k+1)}=D^{-1}(L+U)x^{(k)}+D^{-1}b$，直到满足精度要求。 迭代过程如下： $$ \begin{aligned} x^{(1)} &= \left[\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]+\frac{1}{2}\left[\begin{matrix} -0 & -1 & -1\\ -1 & -0 & -1\\ -1 & -1 & -0 \end{matrix}\right]\left[\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]+\frac{1}{2}\left[\begin{matrix} 5\\ 8\\ 7 \end{matrix}\right]\\ &=\left[\begin{matrix} \frac{5}{2}\\ 4\\ \frac{7}{2} \end{matrix}\right]\\ x^{(2)} &= \left[\begin{matrix} \frac{5}{2}\\ 4\\ \frac{7}{2} \end{matrix}\right]+\frac{1}{2}\left[\begin{matrix} -0 & -1 & -1\\ -1 & -0 & -1\\ -1 & -1 & -0 \end{matrix}\right]\left[\begin{matrix} \frac{5}{2}\\ 4\\ \frac{7}{2} \end{matrix}\right]+\frac{1}{2}\left[\begin{matrix} 5\\ 8\\ 7 \end{matrix}\right]\\ &=\left[\begin{matrix} 1\\ 2\\ 1 \end{matrix}\right] \end{aligned} $$ 因此，方程组的解为 $x_1=1,x_2=2,x_3=1$。 ### Gauss-Seidel 迭代法 Gauss-Seidel 迭代法的步骤如下： 1. 将系数矩阵 $A$ 拆分成两部分：$A=D-L-U$，其中 $D$ 为 $A$ 的对角线部分，$L$ 为 $A$ 的下三角部分，$U$ 为 $A$ 的上三角部分； 2. 将方程组改写为 $(D-L)x=Ux+b$； 3. 取任意 $x^{(0)}$ 作为初始值； 4. 迭代计算 $x^{(k+1)}=(D-L)^{-1}Ux^{(k)}+(D-L)^{-1}b$，直到满足精度要求。 将系数矩阵拆分，得到： $$ D=\left[\begin{matrix} 2 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & 2 \end{matrix}\right], L=\left[\begin{matrix} 0 & -1 & -1\\ 0 & 0 & -1\\ 0 & 0 & 0 \end{matrix}\right], U=\left[\begin{matrix} 0 & 0 & 0\\ -1 & 0 & 0\\ -1 & -1 & 0 \end{matrix}\right] $$ 将方程组改写为 $(D-L)x=Ux+b$，得到： $$ \left[\begin{matrix} 2 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & 2 \end{matrix}\right]x=\left[\begin{matrix} 0 & -1 & -1\\ 0 & 0 & -1\\ 0 & 0 & 0 \end{matrix}\right]x+\left[\begin{matrix} 5\\ 8\\ 7 \end{matrix}\right] $$ 取任意 $x^{(0)}$ 作为初始值，比如 $x^{(0)}=\left[\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]$，迭代计算 $x^{(k+1)}=(D-L)^{-1}Ux^{(k)}+(D-L)^{-1}b$，直到满足精度要求。 迭代过程如下： $$ \begin{aligned} x^{(1)} &= \left[\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]+\left[\begin{matrix} 0 & 0 & 0\\ \frac{1}{2} & 0 & 0\\ \frac{1}{2} & \frac{1}{3} & 0 \end{matrix}\right]\left[\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]+\left[\begin{matrix} 5\\ 8\\ 7 \end{matrix}\right]\\ &=\left[\begin{matrix} \frac{5}{2}\\ 4\\ \frac{7}{2} \end{matrix}\right]\\ x^{(2)} &= \left[\begin{matrix} \frac{5}{2}\\ 4\\ \frac{7}{2} \end{matrix}\right]+\left[\begin{matrix} 0 & 0 & 0\\ \frac{1}{2} & 0 & 0\\ \frac{1}{2} & \frac{1}{3} & 0 \end{matrix}\right]\left[\begin{matrix} \frac{5}{2}\\ 4\\ \frac{7}{2} \end{matrix}\right]+\left[\begin{matrix} 5\\ 8\\ 7 \end{matrix}\right]\\ &=\left[\begin{matrix} 1\\ 2\\ 1 \end{matrix}\right] \end{aligned} $$ 因此，方程组的解为 $x_1=1,x_2=2,x_3=1$。