6.4 加速方法

当迭代解 $x^{(0)}, x^{(1)}, x^{(2)}, \ldots, x^{(k)}$ 已经计算出来后，我们可以对其进行组合，得到一个新的近似解，这样就可以对原方法进行加速。

6.4.1 外推技术

设原迭代格式为

由 $x^{(k)}$ 和 $x^{(k + 1)}$ 加权组合后可得新的近似解

其中 $\omega$ 是参数. 这种加速方法就称为外推方法

如果原迭代格式是 Gauss-Seidel 迭代, 虽然 SOR 与外推方法 (6.17) 都是通过加权进行加速,但格式是不一样的: 前者是在单个分量计算出来后就进行加权, 而后者则是当所有分量都计算出来后才加权.

为了使得迭代格式(6.17)尽可能快地收敛, 需要选择 $\omega$ 使得其迭代矩阵 $G_{\omega} \triangleq (1 - \omega)I + \omega G$ 的谱半径尽可能地小. 假设 $G$ 的特征值都是实数, 且最大特征值和最小特征值分别为 $\lambda_1$ 和 $\lambda_n$ . 于是

定理6.28 设 $G$ 的特征值都是实数, 其最大和最小特征值分别为 $\lambda_{1}$ 和 $\lambda_{n}$ , 且 $1 \notin [\lambda_{n}, \lambda_{1}]$ , 则

此时

其中 $d$ 是1到 $[\lambda_n,\lambda_1]$ 的距离，即当 $\lambda_{n}\leq \lambda_{1} < 1$ 时, $d = 1 - \lambda_1$ ，当 $\lambda_{1}\geq \lambda_{n} > 1$ 时, $d = \lambda_{n} - 1$

(板书)

证明. 易知 $|1 - \omega + \omega \lambda_1| = |1 - \omega + \omega \lambda_n|$ 当且仅当 $\lambda_1 = \lambda_n$ 或 $\omega = 0$ 或 $\omega = \omega_* = \frac{2}{2 - (\lambda_1 + \lambda_n)}$ .

若 $\lambda_1 = \lambda_n$ ，则当 $\omega = \frac{1}{1 - \lambda_1} = \omega_*$ 时 $\rho(G_{\omega_*})$ 达到最小值0.

下面假定 $\lambda_1 \neq \lambda_n$ . 先考虑 $\lambda_1 < 1$ 的情形. 此时有

通过函数图像可知, 当 $\omega = \omega_{*}$ 时取最小值. 此时

对于 $\lambda_{n} > 1$ 的情形，可以进行类似的讨论

由定理6.28可知， $\rho(G_{\omega_*)} = 1 - |\omega_*|d,$ 且当 $\omega_* \neq 1$ 时，外推送代(6.17)比原迭代法收敛要更快一些.

最优参数依赖于原迭代矩阵 $G$ 的特征值, 因此实用性不强. 在实际应用时可以估计特征值所在的区间 $[\alpha, \beta]$ , 然后用 $\alpha, \beta$ 来代替 $\lambda_{n}$ 和 $\lambda_{1}$ .

JOR方法

对Jacobi迭代进行外推加速, 则可得JOR(Jacobi over-relaxation)方法:

定理6.29 设 $A$ 对称正定. 若

则JOR方法收敛

6.4.2 Chebyshev多项式加速

本节对外推技巧进行推广.

假定通过迭代格式 (6.16) 已经计算出 $x^{(0)}, x^{(1)}, \ldots, x^{(k)}$ , 下面考虑如何将这些近似解进行组合, 以便得到更精确的近似解.

记 $\varepsilon_{k} = x^{(k)} - x_{*}$ 为第 $k$ 步迭代解的误差, 则有

设 $\tilde{x}^{(k)}$ 为 $x^{(0)}, x^{(1)}, \ldots, x^{(k)}$ 的一个线性组合，即

其中 $\alpha_{i}$ 为待定系数，且满足 $\sum_{i = 0}^{k}\alpha_{i} = 1.$ 于是

其中 $p_k(t) = \sum_{i=0}^k \alpha_i t^i$ 为 $k$ 次多项式, 且满足 $p_k(1) = 1$ .

我们希望通过适当选取参数 $\alpha_{i}$ , 使得 $\tilde{x}^{(k)} - x_{*}$ 尽可能地小, 即使得 $\tilde{x}^{(k)}$ 收敛到 $x_{*}$ 速度远远快于 $x^{(k)}$ 收敛到 $x_{*}$ 速度. 这种加速方法就称为多项式加速或半迭代法 (semi-iterative method).

例6.4 设 $p_n(t)$ 为 $G$ 的特征多项式, 令 $\tilde{p}_n(t) \triangleq p_n(t) / p_n(1)$ , 则 $\tilde{p}_n(1) = 1$ 且 $\tilde{p}_n(G) = 0$ , 所以选取 $\alpha_i$ 为 $\tilde{p}_n$ 的系数, 则 $\tilde{x}^{(n)} - x_* = 0$ . 但这种选取方法不实用, 原因是:

(1) $\tilde{p}_n(t)$ 的系数并不知道；

(2) 我们通常希望收敛所需的迭代步数 $\ll n$ .

下面讨论参数 $\alpha_{i}$ 的较实用的选取方法.由(6.19)可知

因此我们需要求解下面的极小化问题

其中 $\mathbb{P}_k$ 表示所有次数不超过 $k$ 的多项式组成的集合. 一般来说, 这个问题是非常困难的. 但在一些特殊情况下, 我们可以给出其 (近似) 最优解.

假设迭代矩阵 $G$ 是对称矩阵，即 $G$ 存在特征值分解

其中 $\Lambda$ 是对角矩阵, 且对角线元素都是实的, $Q$ 是正交矩阵. 于是有

其中 $\lambda_1, \lambda_n$ 分别表示 $G$ 的最大和最小特征值. 这是带归一化条件的多项式最佳一致逼近问题 (与零的偏差最小). 该问题的解与著名的 Chebyshev 多项式有关.

由于所有算子范数 $\| p_k(G)\|$ 的下确界是 $\rho (p_k(G))$ ，因此，一种较实用的选取方法是使得 $p_k(G)$ 的谱半径尽可能地小.

Chebyshev多项式

Chebyshev多项式是一类很重要的正交多项式, 在函数逼近, 函数插值, 数值积分等方面都有着重要的应用.

Chebyshev多项式 $T_{k}(t)$ 可以通过下面的递归方式来定义：

也可以直接由下面的式子定义

其中 $\cosh$ 为双曲余弦, 即 $\cosh(t) = \frac{e^t + e^{-t}}{2}$ .

引理6.30 Chebyshev多项式具有下面的性质：

(1) $T_{k}(1) = 1$

(2) $T_{k}(t)$ 的首项系数为 $2^{k - 1}$ ;
(3) $T_{k}(-t) = (-1)^{k}T_{k}(t)$ , 即 $T_{2k}(t)$ 只含偶次项, $T_{2k+1}(t)$ 只含奇次项;
(4) 当 $|t| \leq 1$ 时 $|T_{k}(t)| \leq 1$ ; 当 $|t| > 1$ 时 $|T_{k}(t)| > 1$ ;
(5) $T_{k}(t) = 0$ 的解为 $t_i = \cos \frac{(2i - 1)\pi}{2k}, i = 1, \ldots, k;$
(6) $T_{k}(t)$ 有 $n - 1$ 个极值点: $t_{i} = \cos \frac{k\pi}{n}, i = 1,2,\ldots,k - 1$ ;

下面的结论表明, 在所有首项系数为 1 的 $k$ 次多项式中, $p_k(t) = \frac{1}{2^{k-1}} T_k(t)$ 在 $[-1,1]$ 上与零的偏差是最小的 (在无穷范数意义下).

定理6.31 设 $p_k(t) = \frac{1}{2^{k-1}} T_k(t)$ , 则

其中 $\tilde{\mathbb{P}}_k$ 表示所有首项系数为1的 $k$ 次多项式组成的集合，即

这里的范数 $\| \cdot \|_{\infty}$ 是 $C[-1,1]$ 上的无穷范数，即 $\| f\|_{\infty} = \max_{x\in [-1,1]}|f(x)|$ ， $f(x)\in C[-1,1]$

该性质可用于计算首项系数非零的 $n$ 次多项式在 $[-1,1]$ 上的 $n - 1$ 次最佳一致逼近多项式. 利用这个性质, 我们可以采用 Chebyshev 多项式的零点作为节点进行多项式插值, 以使得插值的总体误差达到最小化.

Chebyshev 另一个重要性质是下面的最小最大性质.

定理6.32 设 $\eta \in \mathbb{R}$ 满足 $|\eta| > 1$ ，则下面的最小最大问题

的唯一解为

通过简单的仿射变换, 该定理的结论可以推广到一般区间.

定理6.33 设 $\alpha, \beta, \eta \in \mathbb{R}$ 满足 $\alpha < \beta$ 且 $|\eta| \notin [\alpha, \beta]$ . 则下面的最小最大问题

的唯一解为

其中 $\mathbb{P}_k$ 表示所有次数不超过 $k$ 的实系数多项式组成的集合.

Chebyshev加速方法

考虑迭代格式(6.16)，我们假定：

(1) 迭代矩阵 $G$ 的特征值都是实数;
(2) 迭代矩阵谱半径 $\rho = \rho (G) < 1$ , 故 $\lambda (G)\in [-\rho ,\rho ]\subset (-1,1)$ .

于是最小最大问题(6.21)就转化为

由于 $1 \neq [-\rho, \rho]$ , 根据定理 6.33, 上述问题的解为

下面考虑 $\tilde{x}^{(k)}$ 的计算. 我们无需先计算出 $x^{(0)}, x^{(1)}, \ldots, x^{(k)}$ , 然后再通过线性组合 (6.18) 来计算 $\tilde{x}^{(k)}$ . 事实上, 我们可以通过 Chebyshev 多项式的三项递推公式 (6.22), 由 $\tilde{x}^{(k-1)}$ 和 $\tilde{x}^{(k-2)}$ 直接计算出 $\tilde{x}^{(k)}$ . 这样做的另一个好处是无需存储所有的 $\tilde{x}^{(i)}$ . 下面给出具体的推导公式.

令 $\mu_{k} = \frac{1}{T_{k}(1 / \rho)}$ 即 $T_{k}(1 / \rho) = \frac{1}{\mu_{k}}.$ 由三项递推公式(6.22)可得

所以

整理后可得

其中

由此, 我们可以得到迭代格式 (6.16) 的 Chebyshev 加速方法

算法6.9.Chebyshev加速方法

1: Set $\mu_0 = 1$ , $\mu_1 = \rho = \rho(G)$ , $\tilde{x}^{(0)} = x^{(0)}$ , $k = 1$
2: compute $\tilde{x}^{(1)} = Gx^{(0)} + g$

3: while not converge do
4: $k = k + 1$

5: $\mu_{k} = \left(\frac{2}{\rho}\cdot \frac{1}{\mu_{k - 1}} -\frac{1}{\mu_{k - 2}}\right)^{-1}$

6: $\tilde{x}^{(k)} = \frac{2\mu_k}{\mu_{k - 1}}\cdot \frac{G}{\rho}\tilde{x}^{(k - 1)} - \frac{\mu_k}{\mu_{k - 2}}\tilde{x}^{(k - 2)} + \frac{2\mu_k}{\mu_{k - 1}\rho}\cdot g$
7: end while

该方法的每步迭代中只有一次矩阵向量乘积, 故方法每个迭代步的整体运算量与原迭代格式的每个迭代步的运算量基本相当.
设 $\lambda (G)\in [\alpha ,\beta ]$ ，且 $-1 < \alpha \leq \beta < 1,$ 则我们也可以构造出相应的Chebyshev加速方法