最后更新: 2026-06-15 06:32 查看: 7 次纠错评论(0) 课件开VIP

经典迭代法

3.2 经典迭代法

直接法理论上在有限步之内给出精确解，但在有限精度的计算机上执行时得到的结果也只是近似的。由于算法复杂度高，高斯消元法不适用于求解大规模线性方程组．本节将讨论如何设计适用于求解大规模线性方程组的迭代法．

此前求解非线性方程（组）的不动点迭代法框架提供了求解线性方程组的新思路。我们先看一个简单的例子。

例 3.3 设计求解如下线性方程组的迭代法：

$$
\left\{\begin{array}{l}
9 x_1-x_2-x_3=7, \\
-x_1+10 x_2-x_3=8, \\
-x_1-x_2+15 x_3=13,
\end{array}\right.
$$

其中线性方程组的精确解为 $x^*=(1,1,1)^{\mathrm{T}}$ 。
解 写出上述线性方程组的不动点形式

$$
\begin{gathered}
\left\{\begin{array}{l}
9 x_1=7+x_2+x_3 \\
10 x_2=8+x_1+x_3 \\
15 x_3=13+x_1+x_2
\end{array}\right. \\
\left\{\begin{array}{l}
x_1=\left(7+x_2+x_3\right) / 9 \\
x_2=\left(8+x_1+x_3\right) / 10 \\
x_3=\left(13+x_1+x_2\right) / 15
\end{array}\right.
\end{gathered}
$$

分别令等式左边第 $k+1$ 步迭代解向量和等式右边为第 $k$ 步迭代解向量，我们有如下雅可比（Jacobi）迭代格式：

$$
\left\{\begin{array}{l}
x_1^{(k+1)}=\left(7+x_2^{(k)}+x_3^{(k)}\right) / 9, \\
x_2^{(k+1)}=\left(8+x_1^{(k)}+x_3^{(k)}\right) / 10, \\
x_3^{(k+1)}=\left(13+x_1^{(k)}+x_2^{(k)}\right) / 15,
\end{array}\right.
$$

其中上标 $k$ 表示迭代步数，下标 $i$ 表示向量的第 $i$ 个分量．
给定初始值 $x^{(0)}=(0,0,0)^{\mathrm{T}}$ ，雅可比迭代格式的数值结果见表 3．1．

![图片](/uploads/2026-06/4c8b7e.jpg)
 
  对一般线性方程组

$$
\left\{\begin{array}{c}
a_{11} x_1+a_{12} x_2+\cdots+a_{1 n} x_n=b_1 \\
a_{21} x_1+a_{22} x_2+\cdots+a_{2 n} x_n=b_2 \\
\cdots \cdots \\
a_{n 1} x_1+a_{n 2} x_2+\cdots+a_{n n} x_n=b_n
\end{array}\right.
$$

其雅可比迭代格式为

$$
x_i^{(k+1)}=\frac{1}{a_{i i}}\left(b_i-\sum_{j=1}^{i-1} a_{i j} x_j^{(k)}-\sum_{j=i+1}^n a_{i j} x_j^{(k)}\right) \quad(i=1,2, \cdots, n),
$$

其中上标 $k$ 表示迭代步数，下标 $i$ 表示向量的第 $i$ 个分量．
在例3．3中，如果更新分量时考虑已经更新的其他分量，我们有如下高斯－赛德尔（Gauss－Seidel）迭代格式：

$$
\left\{\begin{array}{l}
x_1^{(k+1)}=\left(7+x_2^{(k)}+x_3^{(k)}\right) / 9, \\
x_2^{(k+1)}=\left(8+x_1^{(k+1)}+x_3^{(k)}\right) / 10, \\
x_3^{(k+1)}=\left(13+x_1^{(k+1)}+x_2^{(k+1)}\right) / 15 .
\end{array}\right.
$$

给定初始值 $x^{(0)}=(0,0,0)^{\mathrm{T}}$ ，例 3.3 的高斯－赛德尔迭代格式的数值结果见表 3．2．

![图片](/uploads/2026-06/e483d1.jpg)
 
 对一般线性方程组

$$
\left\{\begin{array}{c}
a_{11} x_1+a_{12} x_2+\cdots+a_{1 n} x_n=b_1, \\
a_{21} x_1+a_{22} x_2+\cdots+a_{2 n} x_n=b_2, \\
\cdots \cdots \\
a_{n 1} x_1+a_{n 2} x_2+\cdots+a_{n n} x_n=b_n,
\end{array}\right.
$$

其高斯－赛德尔迭代格式为

$$
x_i^{(k+1)}=\frac{1}{a_{i i}}\left(b_i-\sum_{j=1}^{i-1} a_{i j} x_j^{(k+1)}-\sum_{j=i+1}^n a_{i j} x_j^{(k)}\right) \quad(i=1,2, \cdots, n) .
$$

例 3.4 设计求解如下线性方程组的雅可比迭代格式和高斯－赛德尔迭代格式：

$$
\left\{\begin{aligned}
x_1+2 x_2-2 x_3 & =7, \\
x_1+x_2+x_3 & =8, \\
2 x_1+2 x_2+x_3 & =13 .
\end{aligned}\right.
$$

解 雅可比格式迭代为

$$
\left\{\begin{array}{l}
x_1^{(k+1)}=7-2 x_2^{(k)}+2 x_3^{(k)}, \\
x_2^{(k+1)}=8-x_1^{(k)}-x_3^{(k)}, \\
x_3^{(k+1)}=13-2 x_2^{(k)}-2 x_1^{(k)} .
\end{array}\right.
$$

高斯－赛德尔迭代格式为

$$
\left\{\begin{array}{l}
x_1^{(k+1)}=7-2 x_2^{(k)}+2 x_3^{(k)}, \\
x_2^{(k+1)}=8-x_1^{(k+1)}+x_3^{(k)}, \\
x_3^{(k+1)}=13-2 x_1^{(k+1)}-2 x_2^{(k+1)} .
\end{array}\right.
$$

给定初始值 $x^{(0)}=(0,0,0)^{\mathrm{T}}$ ，雅可比迭代格式和高斯－赛德尔迭代格式计算结果见表 3．3。

![图片](/uploads/2026-06/36d53a.jpg)
 
 注意到例 3.3 中高斯－赛德尔迭代法收敛速度比雅可比迭代法快，而例 3.4 中雅可比迭代法收敛而高斯－赛德尔迭代法不收敛。那么是否可以从理论上回答（1）什么迭代格式收敛和（2）什么迭代格式的收敛速度更快？下面我们将研究求解线性方程组迭代法的理论收敛性质。

用矩阵语言精确表述求解线性方程组的迭代法能够帮助我们深刻理解迭代法的本质。我们首先将例 3.3 中雅可比迭代格式写为如下等价矩阵形式：

$$
\begin{gathered}
\left\{\begin{array}{c}
9 x_1^{(k+1)}=\left(7+x_2^{(k)}+x_3^{(k)}\right), \\
10 x_2^{(k+1)}=\left(8+x_1^{(k)}+x_3^{(k)}\right), \\
15 x_3^{(k+1)}=\left(13+x_1^{(k)}+x_2^{(k)}\right)
\end{array} \Leftrightarrow\left(\begin{array}{ccc}
9 & 0 & 0 \\
0 & 10 & 0 \\
0 & 0 & 15
\end{array}\right)\left(\begin{array}{l}
x_1^{(k+1)} \\
x_2^{(k+1)} \\
x_3^{(k+1)}
\end{array}\right)=\left(\begin{array}{ccc}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}\right)\left(\begin{array}{l}
x_1^{(k)} \\
x_2^{(k)} \\
x_3^{(k)}
\end{array}\right)+\left(\begin{array}{c}
7 \\
8 \\
13
\end{array}\right),\right. \\
\left\{\begin{array}{l}
x_1^{(k+1)}=\left(7+x_2^{(k)}+x_3^{(k)}\right) / 9, \\
x_2^{(k+1)}=\left(8+x_1^{(k)}+x_3^{(k)}\right) / 10, \\
x_3^{(k+1)}=\left(13+x_1^{(k)}+x_2^{(k)}\right) / 15
\end{array} \Leftrightarrow\left(\begin{array}{l}
x_1^{(k+1)} \\
x_2^{(k+1)} \\
x_3^{(k+1)}
\end{array}\right)=\left(\begin{array}{ccc}
9 & 0 & 0 \\
0 & 10 & 0 \\
0 & 0 & 15
\end{array}\right)^{-1}\left[\left(\begin{array}{ccc}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}\right)\left(\begin{array}{l}
x_1^{(k)} \\
x_2^{(k)} \\
x_3^{(k)}
\end{array}\right)+\left(\begin{array}{c}
7 \\
8 \\
13
\end{array}\right)\right] .\right.
\end{gathered}
$$

记 $A=D-L-U$ ，线性方程组 $A x=b$ 可以写为 $(D-L-U) x=b$ ．迭代格式可以简洁写为如下等价矩阵形式：

$$
\begin{aligned}
& \left(\begin{array}{ccc}
9 & 0 & 0 \\
0 & 10 & 0 \\
0 & 0 & 15
\end{array}\right)\left(\begin{array}{l}
x_1^{(k+1)} \\
x_2^{(k+1)} \\
x_3^{(k+1)}
\end{array}\right)=\left(\begin{array}{lll}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}\right)\left(\begin{array}{l}
x_1^{(k)} \\
x_2^{(k)} \\
x_3^{(k)}
\end{array}\right)+\left(\begin{array}{c}
7 \\
8 \\
13
\end{array}\right) \Leftrightarrow D x^{(k+1)}=(L+U) x^{(k)}+b, \\
& \left(\begin{array}{l}
x_1^{(k+1)} \\
x_2^{(k+1)} \\
x_3^{(k+1)}
\end{array}\right)=\left(\begin{array}{lll}
9 & 0 & 0 \\
0 & 10 & 0 \\
0 & 0 & 15
\end{array}\right)^{-1}\left[\left(\begin{array}{lll}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}\right)\left(\begin{array}{l}
x_1^{(k)} \\
x_2^{(k)} \\
x_3^{(k)}
\end{array}\right)+\left(\begin{array}{c}
7 \\
8 \\
13
\end{array}\right)\right] \Leftrightarrow x^{(k+1)}=D^{-1}\left[(L+U) x^{(k)}+b\right] .
\end{aligned}
$$

记 $B=D^{-1}(L+U)$ 和 $f=D^{-1} b$ ，则雅可比迭代格式为 $x^{(k+1)}=\varphi\left(x^{(k)}\right) \triangleq B x^{(k)}+f$ ，其中 $B$ 为迭代矩阵。

对于一般线性方程组

其雅可比迭代格式为

![图片](/uploads/2026-06/745c80.jpg)
 
 上迭代格式写为如下等价矩阵形式
 
  ![图片](/uploads/2026-06/f9171b.jpg)
  
  则雅可比迭代格式可以简洁地写为如下矩阵形式：

$$
x^{(k+1)}=\varphi\left(x^{(k)}\right)=B x^{(k)}+f,
$$

其中迭代矩阵为 $B=D^{-1}(L+U)$ 和 $f=D^{-1} b$ 。
对于一般线性方程组，高斯－赛德尔迭代格式为

$$
x_i^{(k+1)}=\frac{1}{a_{i i}}\left(b_i-\sum_{j=1}^{i-1} a_{i j} x_j^{(k+1)}-\sum_{j=i+1}^n a_{i j} x_j^{(k)}\right) \quad(i=1,2, \cdots, n),
$$

或

$$
a_{i i} x_i^{(k+1)}=b_i-\sum_{j=1}^{i-1} a_{i j} x_j^{(k+1)}-\sum_{j=i+1}^n a_{i j} x_j^{(k)} \quad(i=1,2, \cdots, n) .
$$

高斯－赛德尔迭代格式可以写为如下等价矩阵形式：

![图片](/uploads/2026-06/a73b8c.jpg)
 
 高斯－赛德尔迭代格式可以简洁地写为如下矩阵形式：

$$
x^{(k+1)}=\varphi\left(x^{(k)}\right)=B x^{(k)}+f,
$$

其中迭代矩阵为 $B=(D-L)^{-1} U$ 和 $f=(D-L)^{-1} b$ ．
考虑一般矩阵分裂 $A=M-N$（ $M$ 非奇异），则线性方程组 $A x=b$ 的不动点形式如下：

$$
\begin{aligned}
A x=b & \Leftrightarrow(M-N) x=b \\
& \Leftrightarrow M x=N x+b \\
& \Leftrightarrow x=M^{-1} N x+M^{-1} b .
\end{aligned}
$$

基于上述不动点形式，我们有不动点迭代格式如下：

$$
\begin{equation*}
x^{(k+1)}=\varphi\left(x^{(k)}\right)=B x^{(k)}+f, \tag{3.1}
\end{equation*}
$$

其中 $B=M^{-1} N$ 和 $f=M^{-1} b$ 。当 $M=D$ 和 $N=L+U$ 时，上述一般不动点迭代格式 （3．1）退化为雅可比迭代格式．当 $M=D-L$ 和 $N=U$ 时，上述一般不动点迭代格式 （3．1）退化为高斯－赛德尔迭代格式．如果 $\lim _{k \rightarrow \infty} x^{(k)}=x^*$ ，则称此迭代格式收敛．$x^*$ 既是 $\varphi(x)=B x+f$ 的不动点满足

$$
\begin{equation*}
x^*=B x^*+f \text {, } \tag{3.2}
\end{equation*}
$$

也是线性方程组的解满足 $A x^*=b$ ．

我们用矩阵语言精确表述求解线性方程组的迭代法便于分析迭代法的理论收敛性质。记误差向量为

$$
\varepsilon^{(k+1)}=x^{(k+1)}-x^*
$$

从式（3．1）中减去式（3．2），得

$$
\varepsilon^{(k+1)}=B \varepsilon^{(k)}
$$

递推得

$$
\varepsilon^{(k+1)}=B \varepsilon^{(k)}=\cdots=B^{k+1} \varepsilon^{(0)}
$$

其中 $\varepsilon^{(0)}=x^{(0)}-x^*$ ．
由于 $\varepsilon^{(0)}=x^{(0)}-x^*$ 固定，如果 $\lim _{k \rightarrow \infty} B^k=O$ ，则 $\lim _{k \rightarrow \infty} \varepsilon^{(k)}=0$ ，即 $\lim _{k \rightarrow \infty} x^{(k)}=x^*$ 。因此研究向量序列 $\left\{x^{(k)}\right\}$ 收敛性只需要研究矩阵序列 $\left\{B^k\right\}$ 的收敛性．

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：高斯消元法

下一篇：迭代法的收敛性质(1)

本文对您是否有用？有用 (0) 无用 (0)