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

迭代法的收敛性质(1)

在研究迭代格式理论收敛性质之前，我们先给出范数的定义并在此基础上严格地定义迭代格式的收敛性．我们先定义向量范数严格度量近似解 $x^{(k)}$ 和精确解 $x^*$ 的距离。

定义3．1（向量范数）如果向量 $x \in \mathbf{R}^n$ 的实值函数 $\|x\|$ 满足条件
（1）正定性：$\|x\| \geqslant 0$（ $\|x\|=0$ 当且仅当 $x=0$ ）。
（2）齐次性：$\|\alpha x\|=|\alpha|\|x\|, \forall \alpha \in \mathbf{R}$ 。
（3）三角不等式：$\|x+y\| \leqslant\|x\|+\|y\|$ ，则称 $\|x\|$ 为 $\mathbf{R}^n$ 上的向量范数．

常用向量范数包括
向量1范数：$\|x\|_1=\sum_{i=1}^n\left|x_i\right|$ ．
向量2范数：$\|x\|_2=\left(\sum_{i=1}^n\left|x_i\right|^2\right)^{\frac{1}{2}}$ ．
向量 $\infty$ 范数：$\|x\|_{\infty}=\max _{1 \leqslant i \leqslant n}\left|x_i\right|$ ，其中 $x=\left(x_1, x_2, \cdots, x_n\right)^{\mathrm{T}}$ 。

不同范数之间存在如下等价关系。
定理 3.2 （向量范数的等价性）设 $\|\cdot\|_s$ 和 $\|\cdot\|_t$ 为 $\mathbf{R}^n$ 上向量的任意两种范数，则存在常数 $c_1, c_2>0$ ，使得对 $\forall x \in \mathbf{R}^n$ 有

$$
c_1\|x\|_s \leqslant\|x\|_t \leqslant c_2\|x\|_s .
$$

下面将向量范数的概念推广到矩阵．
定义 3.2 （矩阵范数）如果矩阵 $A \in \mathbf{R}^{m \times n}$ 的实值函数 $\|A\|$ 满足如下条件．
（1）正定性：$\|A\| \geqslant 0 ~(\|A\|=0$ 当且仅当 $A=O)$ 。
（2）齐次性：$\|\alpha A\|=|\alpha|\|A\|, \forall \alpha \in \mathbf{R}$ 。
（3）三角不等式：$\|A+B\| \leqslant\|A\|+\|B\|$ ．
（4）相容性：$\|A B\| \leqslant\|A\|\|B\|$ ，
则称 $\|A\|$ 为 $\mathbf{R}^{m \times n}$ 上的矩阵范数．
定理 3.3 设 $\|\cdot\|$ 是 $\mathbf{R}^{m \times n}$ 上的矩阵范数，则对 $\forall A \in \mathbf{R}^{m \times n}$ 有

$$
\rho(A) \leqslant\|A\|,
$$

其中 $\rho(A)=\max _{1 \leqslant i \leqslant n}\left|\lambda_i\right|$ 称为矩阵 $A$ 的谱半径，$\lambda_1, \lambda_2, \cdots, \lambda_n$ 是 $A$ 的特征值．
证明 设 $\lambda$ 为矩阵 $A$ 模最大的特征值，则存在非零向量 $x \in \mathbf{R}^n$ 满足 $A x=\lambda x$ 。由于 $x$ 为非零向量，存在向量 $y \in \mathbf{R}^n$ 使 $x y^{\mathrm{T}}$ 不是零矩阵。对于任意一种矩阵范数 $\|\cdot\|$ ，由范数定义可得

$$
\rho(A)\left\|x y^{\mathrm{T}}\right\|=\left\|\lambda x y^{\mathrm{T}}\right\|=\left\|A x y^{\mathrm{T}}\right\| \leqslant\|A\|\left\|x y^{\mathrm{T}}\right\|
$$

由 $\left\|x y^{\mathrm{T}}\right\| \neq 0$ 知 $\rho(A) \leqslant\|A\|$ ．
上述定理说明矩阵谱半径 $\rho(A)$ 是任意矩阵范数 $\|A\|$ 的下界。请思考矩阵谱半径 $\rho(\cdot)$ 是否满足矩阵范数的条件？

我们引入相容性的概念刻画向量范数与矩阵范数之间的关系．

定义 $3.3 \mathbf{R}^n$ 上向量范数 $\|x\|$ 和 $\mathbf{R}^{m \times n}$ 上矩阵范数 $\|A\|$ 若满足

$$
\|A x\| \leqslant\|A\|\|x\|, \quad \forall x \in \mathbf{R}^n, \quad A \in \mathbf{R}^{m \times n},
$$

则称上述矩阵范数与向量范数相容．
给定 $\mathbf{R}^n$ 上向量范数 $\|x\|$ ，可以定义其相应的诱导矩阵范数，诱导矩阵范数是所有与向量范数相容的矩阵范数中最小的．

定义 3.4 （矩阵的算子范数）设 $x \in \mathbf{R}^n$ 和 $A \in \mathbf{R}^{m \times n}$ ，给定 $\mathbf{R}^n$ 上一种向量范数 $\|\cdot\|$ ，则如下非负实值函数

$$
\|A\|=\max _{x \neq 0} \frac{\|A x\|}{\|x\|}
$$

满足矩阵范数的条件．上述非负实值函数称为向量范数诱导的矩阵范数即算子范数．

常用的矩阵范数包括
矩阵 $\infty$ 范数：$\|A\|_{\infty}=\max _{1 \leqslant i \leqslant n} \sum_{j=1}^n\left|a_{i j}\right|$ 。

矩阵 1 范数：$\|A\|_1=\max _{1 \leqslant j \leqslant n} \sum_{i=1}^m\left|a_{i j}\right|$ 。
矩阵 2 范数：$\|A\|_2=\sqrt{\rho\left(A^{\mathrm{T}} A\right)}$ ．
矩阵 F 范数：$\|A\|_{\mathrm{F}}=\sqrt{\sum_{i=1}^m \sum_{j=1}^n a_{i j}^2}$ ，
其中矩阵 $\infty$ 范数、1范数、2范数分别是向量 $\infty$ 范数、1范数、2范数的诱导范数．
基于矩阵范数，我们可以定义定量矩阵＂良态性＂大小的条件数．
定义3．5（矩阵条件数）设 $\operatorname{det} A \neq 0$ ，称

$$
\operatorname{cond}(A)=\|A\|\left\|A^{-1}\right\|
$$

为矩阵 $A$ 的条件数．
定义3．6 对于向量序列 $x^{(k)}=\left(x_1^{(k)}, x_2^{(k)}, \cdots, x_n^{(k)}\right)^{\mathrm{T}} \in \mathbf{R}^n$ ，如果存在 $x=\left(x_1, x_2, \cdots\right.$ ， $\left.x_n\right)^{\mathrm{T}} \in \mathbf{R}^n$ 满足

$$
\lim _{k \rightarrow \infty} x_i^{(k)}=x_i, \quad i=1,2, \cdots, n,
$$

则称向量序列 $\left\{x^{(k)}\right\}$ 收敛到 $x$ ，记为 $\lim _{k \rightarrow \infty} x^{(k)}=x$ ．

由上述定义知向量序列收敛性即向量逐分量收敛．
设 $x^{(k)}=\left(x_1^{(k)}, x_2^{(k)}, \cdots, x_n^{(k)}\right)^{\mathrm{T}}$ 和 $x=\left(x_1, x_2, \cdots, x_n\right)^{\mathrm{T}}$ ，如果向量序列 $\left\{x^{(k)}\right\}$ 收敛到 $x$ ，则有

$$
\begin{aligned}
\lim _{k \rightarrow \infty} x_i^{(k)}=x_i, i=1,2, \cdots, n & \Leftrightarrow \lim _{k \rightarrow \infty}\left|x_i^{(k)}-x_i\right|=0, i=1,2, \cdots, n \\
& \Leftrightarrow \lim _{k \rightarrow \infty} \max _{1 \leqslant i \leqslant n}\left|x_i^{(k)}-x_i\right|=0 \\
& \Leftrightarrow \lim _{k \rightarrow \infty}\left\|x^{(k)}-x\right\|_{\infty}=0
\end{aligned}
$$

上述等价关系说明，向量序列 $\left\{x^{(k)}\right\}$ 收敛到 $x$ 等价于数列序列 $\left\{\left\|x^{(k)}-x\right\|_{\infty}\right\}$ 收敛到 0 ．进一步由范数等价性知向量序列 $\left\{x^{(k)}\right\}$ 收敛到 $x$ 等价于数列序列 $\left\{\left\|x^{(k)}-x\right\|\right\}$ 收敛到 0 ，其中矩阵范数为任意矩阵范数。

定义3．7 设矩阵序列 $A^{(k)}=\left(a_{i j}^{(k)}\right) \in \mathbf{R}^{m \times n}$ ，如果存在 $A=\left(a_{i j}\right) \in \mathbf{R}^{m \times n}$ 使

$$
\lim _{k \rightarrow \infty} a_{i j}^{(k)}=a_{i j}, \quad i=1,2, \cdots, m, \quad j=1,2, \cdots, n,
$$

则称矩阵序列 $\left\{A^{(k)}\right\}$ 收敛于 $A$ ，记为 $\lim _{k \rightarrow \infty} A^{(k)}=A$ ．
由 3.2 节讨论知，研究向量序列 $\left\{x^{(k)}\right\}$ 的收敛性只需要研究矩阵序列 $\left\{B^k\right\}$ 的收敛性。

我们先从数值上探索两个特殊矩阵序列 $\left\{B^k\right\}$ 的收敛性．

例 3.5 考察如下矩阵序列的收敛性．

$$
\begin{aligned}
& \Lambda=\left(\begin{array}{ll}
\lambda & \\
& \lambda
\end{array}\right), \Lambda^2=\left(\begin{array}{cc}
\lambda^2 & \\
& \lambda^2
\end{array}\right), \cdots, \Lambda^k=\left(\begin{array}{cc}
\lambda^k & \\
& \lambda^k
\end{array}\right), \\
& \Phi=\left(\begin{array}{ll}
\lambda & 1 \\
& \lambda
\end{array}\right), \Phi^2=\left(\begin{array}{cc}
\lambda^2 & 2 \lambda \\
& \lambda^2
\end{array}\right), \cdots, \Phi^k=\left(\begin{array}{cc}
\lambda^k & k \lambda^{k-1} \\
& \lambda^k
\end{array}\right) .
\end{aligned}
$$

当 $|\lambda|<1$ 时， $\lim _{k \rightarrow \infty} \Lambda^k=O$ 和 $\lim _{k \rightarrow \infty} \Phi^k=O$ ．
定理 3.4 设 $B \in \mathbf{R}^{n \times n}$ ，则 $\lim _{k \rightarrow \infty} B^k=O$ 的充分必要条件是矩阵谱半径 $\rho(B)<1$ ．
证明 对于任意方阵存在如下若尔当（Jordan）分解

$$
B=P J P^{-1},
$$

其中 $P$ 为非奇异矩阵，$J$ 为如下若尔当标准形

$$
J=\left(\begin{array}{llll}
J_1 & & & \\
& J_2 & & \\
& & \ddots & \\
& & & J_r
\end{array}\right),
$$

$J_i$ 为若尔当块

$$
J_i=\left(\begin{array}{cccc}
\lambda_i & 1 & & \\
& \lambda_i & \ddots & \\
& & \ddots & 1 \\
& & & \lambda_i
\end{array}\right)_{n_i \times n_i},
$$

且 $\sum_{i=1}^r n_i=n$ ．基于若尔当分解，我们有

$$
B^k=P J^k P^{-1},
$$

其中

$$
J^k=\left(\begin{array}{llll}
J_1^k & & & \\
& J_2^k & & \\
& & \ddots & \\
& & & J_r^k
\end{array}\right) .
$$

于是 $\lim _{k \rightarrow \infty} B^k=O \Leftrightarrow \lim _{k \rightarrow \infty} J_i^k=O(i=1, \cdots, r)$ ．
下面考察 $J_i^k$ 的情况．引入记号

$$
E_{t, k}=\left(\begin{array}{ll}
O & I \\
O & O
\end{array}\right)^{t-k} \in \mathbf{R}^{t \times t}
$$

显然有 $E_{t, 0}=I, E_{t, 1}^k=E_{t, k}(k \leqslant t-1), E_{t, k}=O(k \geqslant t)$ ．由于 $J_i=\lambda_i I+E_{t, 1}$ ，则

$$
\begin{aligned}
J_i^k & =\left(\lambda_i I+E_{t, 1}\right)^k=\sum_{j=0}^k \mathrm{C}_k^j \lambda_i^{k-j} E_{t, 1}^j=\sum_{j=0}^{t-1} \mathrm{C}_k^j \lambda_i^{k-j} E_{t, 1}^j \\
& =\left(\begin{array}{ccccc}
\lambda_i^k & \mathrm{C}_k^1 \lambda_i^{k-1} & \mathrm{C}_k^2 \lambda_i^{k-2} & \cdots & \mathrm{C}_k^{t-1} \lambda_i^{k-(t-1)} \\
& \lambda_i^k & \mathrm{C}_k^1 \lambda_i^{k-1} & & \mathrm{C}_k^{t-2} \lambda_i^{k-(t-2)} \\
& & \ddots & \ddots & \vdots \\
& & & \ddots & \mathrm{C}_k^1 \lambda_i^{k-1} \\
& & & & \lambda_i^k
\end{array}\right)_{t \times t}
\end{aligned}
$$

其中 $\mathrm{C}_k^j=\frac{k!}{j!(k-j)!}=\frac{k(k-1) \cdots(k-j+1)}{j!}$ ．
因为 $\lim _{k \rightarrow \infty} \mathrm{C}_k^j \lambda_i^{k-j}=0 \Leftrightarrow\left|\lambda_i\right|<1$ ，所以

$$
\left|\lambda_i\right|<1(i=1, \cdots, r) \Leftrightarrow \lim _{k \rightarrow \infty} J_i^k=O(i=1, \cdots, r) \Leftrightarrow \lim _{k \rightarrow \infty} B^k=O .
$$

充分必要条件得证．
由一般矩阵分裂 $A=M-N$（其中 $M$ 非奇异），我们有线性方程组 $A x=b$ 的如下不动点形式

$$
x=B x+f
$$

其中 $B=M^{-1} N$ 和 $f=M^{-1} b$ ．线性方程组 $A x=b$ 的解即迭代格式 $\varphi(x)=B x+f$ 的不动点．基于不动点形式，我们有求解线性方程组的迭代格式如下：

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

下面我们建立上述迭代格式收敛性的理论保障。
定理 3.5 对任意选取的初始值 $x^{(0)}$ ，迭代格式

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

收敛的充分必要条件是迭代矩阵 $B$ 的谱半径 $\rho(B)<1$ ．
证明 充分性：由于 $\rho(B)<1$ ，则 $A=I-B$ 非奇异，即 $A x=f$（其中 $A=I-B$ 为系数矩阵）存在唯一解 $x^*$ 且满足

$$
\begin{equation*}
x^*=B x^*+f . \tag{3.4}
\end{equation*}
$$

式（3．3）减去式（3．4）得

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

其中 $\varepsilon^{(k+1)}=x^{(k+1)}-x^*$ 和 $\varepsilon^{(k)}=x^{(k)}-x^*$ ．
进一步递推得

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

其中 $\varepsilon^{(0)}=x^{(0)}-x^*$ ．
因为谱半径 $\rho(B)<1$ ，由定理 3.4 有 $\lim _{k \rightarrow \infty} B^k=O$ ．故对任意向量范数及其从属的矩阵范数有

$$
\left\|x^{(k+1)}-x^*\right\|=\left\|\varepsilon^{(k+1)}\right\|=\left\|B^{k+1} \varepsilon^{(0)}\right\| \leqslant\left\|B^{k+1}\right\|\left\|\varepsilon^{(0)}\right\| .
$$

由于 $\lim _{k \rightarrow \infty} B^{k+1}=O$ ，则对任意 $\varepsilon^{(0)}$ 有 $\lim _{k \rightarrow \infty} x^{(k+1)}=x^*$ ．
必要性：设对于任意 $x^{(0)}$ 有

$$
\lim _{k \rightarrow \infty} x^{(k+1)}=x^*
$$

其中 $x^{(k+1)}=B x^{(k)}+f . x^*$ 是线性方程组 $x=B x+f$ 的解，且对任意 $x^{(0)}$ 有

$$
\lim _{k \rightarrow \infty} \varepsilon^{(k+1)}=\lim _{k \rightarrow \infty}\left(x^{(k+1)}-x^*\right)=\lim _{k \rightarrow \infty} B^{k+1}\left(x^{(0)}-x^*\right)=0 .
$$

取 $\varepsilon^{(0)}$ 为单位向量 $e_j$ ，其第 $j$ 个分量为 1 ，其他分量为零。由 $\lim _{k \rightarrow \infty} B^{k+1} e_j=0$ 可知 $B^{k+1}$ 第 $j$ 列各元素极限为零。取遍 $j=1,2, \cdots, n$ 可知 $B^{k+1}$ 所有元素极限为零，即 $\lim _{k \rightarrow \infty} B^{k+1}=O$ ．由定理3．5即得 $\rho(B)<1$ ．

由于需要计算特征值，迭代矩阵谱半径 $\rho(B)<1$ 的条件通常不易检验．由定理 3.4 知，我们可以通过计算相对容易的范数（如 $\|B\|_1,\|B\|_{\infty}$ 和 $\|B\|_{\mathrm{F}}$ ）估计谱半径上界，从而有如下迭代格式的充分条件。

定理 3.6 设与向量范数 $\|x\|$ 相容的矩阵范数 $\|B\|<1$ ．则迭代格式 $x^{(k+1)}=B x^{(k)}+ f$ 收敛且

$$
\begin{gathered}
\left\|x^{(k)}-x^*\right\| \leqslant \frac{\|B\|}{1-\|B\|}\left\|x^{(k)}-x^{(k-1)}\right\| \\
\left\|x^{(k)}-x^*\right\| \leqslant \frac{\|B\|}{1-\|B\|}\left\|x^{(1)}-x^{(0)}\right\|
\end{gathered}
$$

证明 由定理3．4知 $\rho(B) \leqslant\|B\|<1$ ，从而由定理3．5知迭代格式收敛，即

$$
\begin{aligned}
& \lim _{k \rightarrow \infty} x^{(k+1)}=x^* . \\
& x^{(k)}=\varphi\left(x^{(k-1)}\right)=B x^{(k-1)}+f \text { 和 } x^*=B x^*+f \text { 两式相减 } \\
& x^{(k)}-x^*=B\left(x^{(k-1)}-x^*\right)=B\left(x^{(k-1)}-x^{(k)}\right)+B\left(x^{(k)}-x^*\right) .
\end{aligned}
$$

由三角不等式有

$$
\left\|x^{(k)}-x^*\right\| \leqslant\left\|B\left(x^{(k-1)}-x^{(k)}\right)\right\|+\left\|B\left(x^{(k)}-x^*\right)\right\| .
$$

进一步整理得

$$
\left\|x^{(k)}-x^*\right\| \leqslant \frac{\|B\|}{1-\|B\|}\left\|x^{(k)}-x^{(k-1)}\right\| .
$$

反复递推得

$$
\left\|x^{(k)}-x^*\right\| \leqslant \frac{\|B\|^k}{1-\|B\|}\left\|x^{(1)}-x^{(0)}\right\|
$$

由定理3．5知，雅可比迭代格式和高斯－赛德尔迭代格式收敛的充分必要条件是迭代矩阵 $B$ 的谱半径 $\rho(B)<1$ ，即 $\rho\left(D^{-1}(L+U)\right)<1$ 和 $\rho\left((D-L)^{-1} U\right)<1$ ，其中 $D, L$和 $U$ 分别是系数矩阵的对角部分、严格下三角部分和严格上三角部分。我们通常需要从系数矩阵出发构造迭代矩阵，然后计算迭代矩阵谱半径判断迭代格式收敛性。而当系数矩阵具有某些特殊结构时（严格对角占优矩阵和对称正定矩阵），我们可以不构造迭代矩阵直接判断雅可比迭代格式和高斯－赛德尔迭代格式的收敛性．

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：经典迭代法

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

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