6.2 收敛性分析

6.2.1 基本概念

首先给出向量序列收敛的定义

定义6.2 (向量序列的收敛) 设 $\left\{x^{(k)}\right\}_{k=1}^{\infty}$ 是 $\mathbb{R}^n$ (或 $\mathbb{C}^n$ ) 中的一个向量序列. 如果存在向量 $x = [x_1, x_2, \ldots, x_n]^\top \in \mathbb{R}^n$ (或 $\mathbb{C}^n$ ) 使得

其中 $x_{i}^{(k)}$ 表示 $x^{(k)}$ 的第 $i$ 个分量, 则称 $\{x^{(k)}\}$ (按分量) 收敛到 $x$ , 即 $x$ 是 $x^{(k)}$ 的极限, 记为

类似地, 我们可以给出矩阵序列收敛的定义.

定义6.3 (矩阵序列的收敛) 设 $\left\{A^{(k)} = \left[a_{ij}^{(k)}\right]\right\}_{k=0}^{\infty}$ 是 $\mathbb{R}^{m \times n}$ (或 $\mathbb{C}^{m \times n}$ ) 中的一个矩阵序列. 如果存在矩阵 $A = [a_{ij}] \in \mathbb{R}^{m \times n}$ (或 $\mathbb{C}^{m \times n}$ ) 使得

则称 $A^{(k)}$ 收敛到 $A$ , 即 $A$ 是 $A^{(k)}$ 的极限, 记为

关于向量序列和矩阵序列的收敛性, 我们有下面的基本判别方法 [144].

定理6.1 设向量序列 $\{x^{(k)}\}_{k=0}^{\infty} \subset \mathbb{R}^{n}$ (或 $\mathbb{C}^{n}$ ), 矩阵序列 $\left\{A^{(k)}=\left[a_{ij}^{(k)}\right]\right\}_{k=0}^{\infty} \subset \mathbb{R}^{m \times n}$ (或 $\mathbb{C}^{m \times n}$ ), 则

(1) $\lim_{k\to \infty}x^{(k)} = x\Longleftrightarrow \lim_{k\to \infty}\| x^{(k)} - x\| = 0,$ 其中 $\| \cdot \|$ 为任一向量范数;
(2) $\lim_{k\to \infty}A^{(k)} = A\Longleftrightarrow \lim_{k\to \infty}\| A^{(k)} - A\| = 0,$ 其中 $\| \cdot \|$ 为任一矩阵范数;
(3) $\lim_{k\to \infty}A^{(k)} = 0\Longleftrightarrow \lim_{k\to \infty}A^{(k)}x = 0,\forall x\in \mathbb{R}^n$ (或 $\mathbb{C}^n$)

由定理6.1和引理1.39，我们可以立即得到下面的结论

定理6.2 设矩阵 $A \in \mathbb{R}^{n \times n}$ (或 $\mathbb{C}^{n \times n}$ ), 则 $\lim_{k \to \infty} A^k = 0$ 当且仅当 $\rho(A) < 1$ . （板书）

证明. 充分性: 设 $\rho(A) < 1$ , 则由引理 1.39 可知, 存在某个矩阵范数 $\| \cdot \|$ 使得 $\| A \| < 1$ . 因此由 $0 \leq \| A^k \| \leq \| A \|^k \to 0 (k \to \infty)$ 可得

根据定理6.1,我们有 $\lim_{k\to \infty}A^k = 0.$

必要性：设 $\lim_{k\to \infty}A^k = 0$ ，则由定理6.1可知

所以由 $0 \leq \rho(A)^{k} = \rho(A^{k}) \leq \|A^{k}\|$ 可得

即 $\rho (A) < 1$

下面给出谱半径与范数之间的一个重要关系式, 有时也用来定义矩阵的谱半径.

定理6.3 设 $A \in \mathbb{R}^{n \times n}$ (或 $\mathbb{C}^{n \times n}$ ), 则对任意矩阵范数 $\|\cdot\|$ , 有

(板书)

证明. 由谱半径与范数之间的关系可知

另一方面, 对任意 $\varepsilon > 0$ , 构造矩阵

则 $\rho(A_{\varepsilon}) < 1$ ，故 $\lim_{k \to \infty} A_{\varepsilon}^{k} = 0$ 。因此存在正整数 $N$ ，使得当 $k > N$ 时，有 $\|A_{\varepsilon}^{k}\| < 1$ ，即

所以

即对任意 $\varepsilon > 0$ ，存在正整数 $N$ ，使得当 $k > N$ 时，有

根据极限定义可知, $\left\| A^k\right\| ^{\frac{1}{k}}\to \rho (A)$

下面给出基本迭代法收敛的定义.

定义6.4 考虑基本迭代法(6.3)，如果对任意的初始向量 $x^{(0)}$ ，都有

则称基本迭代法 (6.3) 是收敛的, 否则就称其为发散的.

基于矩阵分裂的迭代法, 其收敛性取决于迭代矩阵的谱半径.

下面考虑基本迭代法 (6.3) 的收敛性. 首先给出一个迭代法收敛的充分条件.

引理6.4 若存在算子范数 $\| \cdot \|$ , 使得 $\| G \| < 1$ , 则迭代法 (6.3) 收敛.

(板书)

证明. 由 $x^{(k + 1)} = Gx^{(k)} + g$ 和 $x_{*} = Gx_{*} + g$ 可得

故

依此类推, 可得

由于 $\| G\| < 1$ ，当 $k\to \infty$ 时，上式右端 $\rightarrow 0$ ，即 $\left\| x^{(k + 1)} - x_{*}\right\| \to 0.$ 因此迭代法收敛.

事实上, 由习题1.10可知, 引理6.4条件中的算子范数可以改为任意矩阵范数
我们记 $e^{(k)} \triangleq x^{(k)} - x_{*}$ 为第 $k$ 步迭代解 $x^{(k)}$ 的误差向量.

定理 6.5 (基本收敛性定理) 对任意初始向量 $x^{(0)}$ , 迭代法 (6.3) 收敛的充要条件是 $\rho(G) < 1$ . (板书)

证明. 必要性: 用反证法, 假设 $\rho(G) \geq 1$ . 设 $\lambda$ 为 $G$ 的模最大的特征值, 即 $|\lambda| = \rho(G) \geq 1$ . 令 $x \neq 0$ 为其对应的特征向量. 取迭代初始向量 $x^{(0)} = x_{*} + x$ , 则

不可能收敛到0,即方法不收敛.故假设不成立，因此 $\rho (G) < 1$

充分性: 若 $\rho(G) < 1$ , 则由引理 1.39 可知, 存在一个算子范数 $\|\cdot\|_{\varepsilon}$ , 使得 $\|G\|_{\varepsilon} < 1$ . 再由引理 6.4 可知, 方法收敛. $\square$

定义6.5 设 $G$ 是迭代矩阵, 则迭代法 (6.3) 的平均收敛速度定义为

渐进收敛速度定义为

平均收敛速度与迭代步数和所用的范数有关, 但渐进收敛速度只依赖于迭代矩阵的谱半径.

数值分析中关于收敛速度的定义：

设点列 $\{\varepsilon_k\}_{k=1}^{\infty}$ 收敛, 且 $\lim_{k \to \infty} \varepsilon_k = 0$ . 若存在一个有界常数 $0 < c < \infty$ , 使得

则称点列 $\{\varepsilon_k\}$ 是 $p$ 次 (渐进) 收敛的. 若 $1 < p < 2$ 或 $p = 1$ 且 $c = 0$ , 则称点列是超线性收敛的.

定理6.6 考虑迭代法 (6.3). 如果存在某个算子范数 $\| \cdot \|$ 使得 $\| G\| = q < 1$ ，则

(1) $\| x^{(k)} - x_{*}\| \leq q^{k}\| x^{(0)} - x_{*}\|$
(2) $\| x^{(k)} - x_{*}\| \leq \frac{q}{1 - q}\| x^{(k)} - x^{(k - 1)}\|$
(3) $\| x^{(k)} - x_{*}\| \leq \frac{q^{k}}{1 - q}\| x^{(1)} - x^{(0)}\|$

(板书)

证明. (1) 由 $x^{(k)} = Gx^{(k-1)} + g$ 和 $x_{*} = Gx_{*} + g$ 可得

因此有

反复利用结论 $(\ref{eq:2})$ 即可得 $\| x^{(k)} - x_{*}\| \leq q^{k}\| x^{(0)} - x_{*}\|$

(2) 由 $x^{(k + 1)} = Gx^{(k)} + g$ 和 $x_{*} = Gx_{*} + g$ 可得

因此有

根据 $(\ref{eq:1})$ ，我们有 $\| x^{(k + 1)} - x_{*}\| \leq q\| x^{(k)} - x_{*}\|$ .所以

结合 $(\ref{eq:1})$ 可得

(3) 反复利用 $(\ref{eq:1})$ 即可得

所以

一般来说，好的迭代法应该满足[30]：

(1) $\rho (G)$ 很小；
(2) 以 $M$ 为系数矩阵的线性方程组比较容易求解

6.2.2 不可约对角占优矩阵

这里我们考虑 $A$ 是严格对角占优或不可约对角占优情形

定理6.7 设 $A \in \mathbb{R}^{n \times n}$ , 若 $A$ 严格对角占优, 则 Jacobi 迭代法和 G-S 迭代法都收敛, 且

(板书)

证明. 首先证明 $\| G_{\mathrm{J}} \|_{\infty} < 1$ . 由于 $A$ 严格行对角占优, 故 $\sum_{j \neq i} |a_{ij}| / |a_{ii}| < 1$ . 所以

下面证明 $\| G_{\mathrm{GS}}\|_{\infty}\leq \| G_{\mathrm{J}}\|_{\infty}$ ，只需证明 $|G_{\mathrm{GS}}|e\leq |G_{\mathrm{J}}|e$ 即可，其中 $e = [1,1,\dots ,1]^{\mathsf{T}}$

令 $\tilde{L} = D^{-1}L$ 和 $\tilde{U} = D^{-1}U$ . 则 $\tilde{L}$ 是严格下三角矩阵, 故 $\tilde{L}^n = 0$ , 所以

于是

由 $A$ 的严格行对角占优性可知 $1 - \sum_{j\neq i}\frac{|a_{ij}|}{|a_{ii}|} >0,$ 即 $(I - |\tilde{L}| - |\tilde{U}|)e > 0.$ 两边同乘 $|\tilde{L} |\geq 0$ 可得

即 $|\tilde{U}|e \leq (I - |\tilde{L}|)(|\tilde{L}| + |\tilde{U}|)e.$ 两边同乘 $(I - |\tilde{L}|)^{-1} \geq 0$ 可得

又 $|\tilde{L}| + |\tilde{U}| = |D^{-1}(L + U)| = |G_{\mathrm{J}}|$ , 由 (6.9) 可知 $|G_{\mathrm{GS}}|e \leq |G_{\mathrm{J}}|e$ , 即定理结论成立.

当 $A$ 是严格列对角占优时, 该结论也成立.

定理6.8 设 $A \in \mathbb{R}^{n \times n}$ , 若 $A$ 不可约对角占优, 则 Jacobi 迭代法和 G-S 迭代法都收敛. 进一步, 若 $A$ 是非负矩阵, 则

(留作课外自习, 需利用非负矩阵的相关知识, 可参见 [139])

思考：若 $A\in \mathbb{R}^{n\times n}$ 严格对角占优且非负,则是否有结论 $\rho (G_{\mathrm{GS}})\leq \rho (G_{\mathrm{J}})?$

上述定理中的结论对一般矩阵并不成立：对某些矩阵，Jacobi迭代法收敛，但G-S迭代法却不一定收敛，见思考题6.23.

关于SOR迭代法，我们有下面的结论

定理6.9 设 $A \in \mathbb{R}^{n \times n}$ , 若 $A$ 严格对角占优且 $0 < \omega \leq 1$ , 则SOR迭代法收敛.

(板书)

证明. 反证法. 假设SOR迭代法不收敛, 即 $\rho(G_{\mathrm{SOR}}) \geq 1$ . 因此 $G_{\mathrm{SOR}}$ 存在特征值 $\lambda$ , 满足 $|\lambda| \geq 1$ . 由 $\operatorname*{det}(\lambda I - G_{\mathrm{SOR}}) = 0$ 可知

又 $\operatorname{det}\left((D - \omega L)^{-1}\right) \neq 0$ ，所以

由 $0 < \omega \leq 1$ 和 $|\lambda| \geq 1$ 可知, $\lambda + \omega - 1 \neq 0$ . 所以 $\operatorname{det}(\tilde{G}) = 0$ , 其中

令 $\lambda = a + \mathbf{i}b$ ，其中 $a,b\in \mathbb{R}$ .则根据 $0 < \omega \leq 1$ 和 $|\lambda |\geq 1$ ，可得

所以

又 $A$ 是严格对角占优的, 所以由 (6.10) 和 (6.11) 可知, $\tilde{G}$ 也严格对角占优. 这意味着 $\operatorname*{det}(\tilde{G}) \neq 0$ , 矛盾.

定理6.10 设 $A \in \mathbb{R}^{n \times n}$ , 若 $A$ 不可约对角占优且 $0 < \omega \leq 1$ , 则SOR迭代法收敛.

(留作课外自习)

6.2.3 对称正定矩阵

首先给出Richardson迭代法的收敛性

定理6.11 设 $A \in \mathbb{R}^{n \times n}$ 是对称正定矩阵, $\lambda_{1}$ 和 $\lambda_{n}$ 分别是 $A$ 的最大和最小特征值, 则Richardson迭代法收敛当且仅当

另外, Richardson 迭代法的最优参数为

即当 $\omega = \omega_{*}$ 时，迭代矩阵的谱半径达到最小，并且有

(留作练习)

下面考虑 Jacobi, Gauss-Seidel 和 SOR 的收敛性, 先介绍两个引理.

引理6.12 设 $A \in \mathbb{C}^{n \times n}$ 是Hermite的, 矩阵分裂 $A = M - N$ , 其中 $M$ 非奇异, 则 $M^{*} + N$ 也是Hermite的, 且对任意 $x \in \mathbb{C}^{n}$ 有

其中 $\tilde{x} = M^{-1}Nx,u = x - \tilde{x}$

(板书)

证明. 由于 $A$ 是Hermite的, 所以 $M^{*} + N = M^{*} + M - A$ 也是Hermite的.

由于 $\tilde{x} = M^{-1}Nx$ ，所以 $M\tilde{x} = Nx$ ，因此

由 $M^{*} + N$ 的对称性可知 $M = M^{*} + N - N^{*}$ 又 $(Nx)^{*} = (M\tilde{x})^{*}$ ，所以

引理6.13 设 $A \in \mathbb{R}^{n \times n}$ 对称, 矩阵分裂 $A = M - N$ 满足 $M^{\top} + N$ 正定, 则 $\rho(M^{-1}N) < 1$ 当且仅当 $A$ 是正定的. (板书)

证明. 充分性. 设 $\lambda \in \mathbb{C}$ 是 $M^{-1}N$ 的一个特征值, 对应的特征向量为 $x \neq 0$ , 即

我们首先说明 $\lambda \neq 1$ 假设 $\lambda = 1$ ，则可得 $Mx = Nx$ ，即 $Ax = 0$ .由于 $A$ 非奇异，所以 $x = 0$ ，矛盾.

令 $\tilde{x} = M^{-1}Nx = \lambda x, u = x - \tilde{x} = (1 - \lambda)x.$ 则由引理6.12可得

由于 $A$ 和 $M^{\mathsf{T}} + N$ 都是正定矩阵, 所以上式右端为正, 故 $|\lambda| < 1$ . 因此 $\rho(M^{-1}N) < 1$ .

必要性. 反证法. 假设 $A$ 不是正定的. 由于 $\rho(M^{-1}N) < 1$ , 所以 $A = M(I - M^{-1}N)$ 非奇异, 因此存在 $x^{(0)} \in \mathbb{R}^n$ , 使得

以 $x^{(0)}$ 为初始点，构造迭代序列

由 $\rho (M^{-1}N) < 1$ 可知

令 $u^{(k)} = x^{(k - 1)} - x^{(k)}$ ，则由引理6.12可得

由于 $M^{\mathsf{T}} + N$ 对称正定, 上式右端非负, 所以

依此类推, 可得

这与 (6.12) 矛盾. 因此 $A$ 一定是正定的

我们首先给出SOR迭代法收敛的一个必要条件

定理6.14 对于SOR迭代法,有 $\rho (G_{\mathrm{SOR}})\geq |1 - \omega |$ ,故SOR迭代法收敛的必要条件是 $0 < \omega < 2$ （板书）

证明.SOR的迭代矩阵为

所以 $G_{\mathrm{SOR}}$ 的行列式为

设 $G_{\mathrm{SOR}}$ 的特征为 $\lambda_1,\lambda_2,\ldots ,\lambda_n$ ，则

故至少有一个特征值的模不小于 $|1 - \omega|$ , 即 $\rho(G_{\mathrm{SOR}}) \geq |1 - \omega|$ .

若SOR收敛,则 $\rho (G_{\mathrm{SOR}}) < 1$ ，因此 $|1 - \omega | < 1$ ，即 $0 < \omega < 2$

定理6.15 设 $A \in \mathbb{R}^{n \times n}$ 对称正定

(1) 若 $2D - A$ 正定, 则 Jacobi 迭代法收敛.
(2) 若 $0 < \omega < 2$ ，则SOR迭代法和SSOR迭代法收敛
(3) G-S 迭代法收敛.

(留作课外自习, 直接利用前面的引理即可)

定理6.16 设 $A \in \mathbb{R}^{n \times n}$ 对称, 且 $D$ 正定

(1) 若 Jacobi 迭代法收敛, 则 $A$ 和 $2D - A$ 都正定;
(2) 若存在 $\omega \in (0, 2)$ 使得 SOR (或 SSOR) 迭代法收敛, 则 $A$ 正定;
(3) 若 G-S 迭代法收敛, 则 $A$ 正定.

(板书, 只证明 (1), (2) 和 (3) 利用引理 6.13 即可)

证明. 设 Jacobi 迭代收敛. 由于 $A$ 对称, $D$ 对称正定, 所以 $D^{-1}A = D^{-\frac{1}{2}}\left(D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\right)D^{\frac{1}{2}}$ 的特征值都是实数. 又

由 $\rho (G_{\mathrm{J}}) < 1$ 可知 $\lambda \left(D^{-1}A\right) > 0$ ，即 $\lambda \left(D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\right) > 0,$ 所以 $\lambda (A) > 0,$ 故 $A$ 正定.

下面证明 $2D - A$ 的正定性. 根据 $\rho(G_{\mathbf{J}}) < 1$ 可知

所以

又 $2D - A$ 与 $D^{-\frac{1}{2}}(2D - A)D^{-\frac{1}{2}}$ 合同, 而

即 $D^{-\frac{1}{2}}(2D - A)D^{-\frac{1}{2}}$ 与 $2I - D^{-1}A$ 有相同的特征值, 所以 $2D - A$ 的特征值也都是正数, 即 $2D - A$ 正定. $\square$

推论6.17 设 $A \in \mathbb{R}^{n \times n}$ 对称且 $D$ 正定, 则

(1) Jacobi 收敛的充要条件是 $A$ 和 $2D - A$ 都正定;
(2) G-S 收敛的充要条件是 $A$ 正定;
(3)SOR收敛的充要条件是 $A$ 正定且 $\omega \in (0,2)$

6.2.4 相容次序矩阵*

针对一类特殊的矩阵, Jacobi 迭代矩阵和 SOR 迭代矩阵的特征值之间存在一种特殊的关系式, 根据这个关系式, 在某些场合下就可以确定 SOR 的最优参数的取值.

定义6.6设 $A\in \mathbb{R}^{n\times n}$ 的对角线元素全不为零,记 $\tilde{L} = D^{-1}L,\tilde{U} = D^{-1}U$ ，即 $A = D(I - \tilde{L} -\tilde{U})$ 若矩阵 $G(\alpha)\triangleq \alpha \tilde{L} +\frac{1}{\alpha}\tilde{U}$ 的特征值与 $\alpha$ 无关 $(\alpha \neq 0)$ ，则称 $A$ 是相容次序矩阵 (consistentlyordered matrix).

下面我们讨论一类特殊的相容次序矩阵. 首先给出一个引理

引理6.18 设 $B \in \mathbb{R}^{n \times n}$ 具有下面的结构

令 $B_{L}$ 和 $B_{U}$ 分别表示 $B$ 的下三角和上三角部分, 则

(1) 若 $\mu$ 是 $B$ 的特征值, 则 $-\mu$ 也是 $B$ 的特征值;
(2) $B(\alpha)$ 的特征值与 $\alpha$ 无关, 其中

(板书)

证明. (1) 若 $[x, y]$ 是 $B$ 的对应于 $\mu$ 的特征向量, 则 $[x, -y]$ 是 $B$ 对应于 $-\mu$ 的特征向量.

(2) 由于 $\alpha \neq 0$ , 我们有

故引理结论成立.

该结论对复矩阵也成立.
由引理6.18中结论(2)可知， $B(\alpha) + \beta I$ 的特征值也与 $\alpha$ 无关,其中 $\beta$ 为任意常数

定义6.7 设 $A \in \mathbb{R}^{n \times n}$ , 如果存在一个置换矩阵 $P$ , 使得

其中 $D_{1}, D_{2}$ 为对角矩阵, 则称 $A$ 具有性质 $\mathbf{A}$ .

性质A意味着指标集 $\mathbb{Z}_n = \{1,2,\dots ,n\}$ 可以分成两个互不相交的子集之和，在同一个子集内的未知量相互独立，因此在迭代更新时可以并行计算. (也就是说, $\mathbb{Z}_n = \mathcal{S}\cup \mathcal{T},\mathcal{S}\cap \mathcal{T} = \emptyset$ 当 $i\neq j$ 且 $i,j\in S$ 或 $i,j\in T$ 时，有 $a_{ij} = 0.$ )
相容次序矩阵和性质A有不同的定义方式，我们这里采用的是Demmel(1997)[30]中的定义.其他定义可参见Varga(1962,2000)[139]或Young(1971)[141].事实上，根据Axelsson(1994)[6, page 239]中的说法，Yong(1950)[140]也是按照定义6.6和定义6.7来定义相容次序矩阵和性质A的.

根据引理6.18, 我们可以直接得到下面的结论

定理 6.19 设 $A$ 的对角线元素全不为零, 若 $A$ 具有性质 A, 则存在置换矩阵 $P$ , 使得 $P A P^{\top}$ 是相容次序矩阵.

如果矩阵 $A$ 本身就具有(6.7)的形式, 则 $A$ 就是相容次序矩阵
事实上, (6.7) 可推广到分块三对角矩阵情形, 见下面的例子.

例6.1 设 $D_{i}$ 是非奇异的对角矩阵, 则任意块三对角矩阵