Skip to content

Iterative Techniques in Matrix Algebra

本章很多内容在数值代数中会更加详细

Norms of Vectors and Matrices

Eigenvalues and Eigenvectors

基本的线性代数概念，略。

The Jacobi and Gauss-Seidel Iterative Techniques

Jacobi & G-S

将 \(A\) 拆分为上三角、对角线、下三角三个部分：

\[ A = D-L-U \]

随后就有

\[ \begin{aligned} Ax &= b\\ (D - L - U)x&=b\\ Dx&= b + (L+U) x\\ \end{aligned} \]

将其改写为迭代形式，就是 Jacobi 迭代的迭代公式

\[ x^{(k+1)}= D^{-1}b - D^{-1}(L+U) x^{(k)} \]

Gauss-Seidel 迭代形式获得方式与 Jacobi 迭代类似，有

\[ (D - L)\cdot x^{(k+1)} = b + U \cdot x^{(k)} \]

由于非对焦矩阵（哪怕是下三角矩阵）求逆比较困难，因此实际应用的 Gauss-Seidel 的迭代形式为

\[ x^{(k+1)} = D^{-1}b + D^{-1}U \cdot x^{(k)} + D^{-1}L \cdot x^{(k+1)} \]

计算顺序上，Jacobi 迭代无所谓（可以并行计算 \(x^{(k+1)}\) 的每个分量），但是 Gauss-Seidel 迭代需要按照 \(x^{(k+1)}\) 分量下标从小到大的顺序计算。

Convergence Analysis

Equivalent Conditions of Convergence

以下条件等价：

  • \(A\) 是收敛矩阵
  • \(\lim\limits_{n\to \infty}\| A^n\| = 0\)
  • \(\rho(A) < 1\)
  • \(\forall x\), \(\lim\limits_{n\to \infty} A^n x = 0\)

留作习题证明略

\(A\) 是收敛矩阵即 \(\lim\limits_{n\to\infty} A^n=0\) \(\rho(A)\) 是 \(A\) 的谱半径，即 \(A\) 的所有特征值的模的最大值

证明矩阵收敛，有充分条件 \(\|A\|<1\)，但是这个条件并不必要。

Convergence of Iterative Methods

迭代法收敛的等价条件为迭代矩阵收敛，即对于迭代法 \(x^{(k+1)}=Tx^{(k)}+c\)，其收敛到 \(x=Tx+c\) 的唯一解当且仅当 \(\rho(T)<1\)。

留作习题证明略

Error Bounds of Iterative Methods

对于迭代法 \(x^{(k+1)}=Tx^{(k)}+c\)，\(x\) 是迭代法收敛到的唯一解，则有

\[ \begin{gathered} \|x-x^{(k)}\| \leqslant \|T\|^k\|x-x^{(0)}\|\\ \|x-x^{(k)}\| \leqslant \frac{\|T\|^k}{1-\|T\|}\|x^{(1)}-x^{(0)}\|\\ \end{gathered} \]

Sufficient Condition of Convergence (Jacobi & G-S)

如果 \(A\) 严格对角占优，那么用 Jacobi 迭代法和 Gauss-Seidel 迭代法解 \(Ax=b\) 都可以收敛。

留作习题证明略。通过证明 \(\rho (T)<1\)

Relaxation Techniques for Solving Linear Systems

将原始的 G-S 迭代视为

\[ x^{(k+1)} = x^{(k)} + \underbrace{D^{-1}Lx^{(k+1)} + D^{-1}(U-D) x^{(k)} + D^{-1}b}_{\text{修正项}} \]

第 \(k\) 次迭代的解加上修正项得到第 \(k+1\) 次迭代的解

现在我们给修正项乘上一个系数 \(\omega\) 后再进行修正，于是就有

\[ \begin{aligned} x^{(k+1)} &= x^{(k)} + \omega D^{-1}(Lx^{(k+1)} + (U-D) x^{(k)} + b)\\ &= (1-\omega) x^{(k)} + \omega D^{-1}(Lx^{(k+1)} + U x^{(k)} + b)\\ \end{aligned} \]

这就是松弛迭代的迭代公式了。如果令残差 \(r^{(k)}=Lx^{(k+1)} + (U-D) x^{(k)} + b\)，则有

\[ x^{(k+1)} = x^{(k)} + \omega D^{-1}r^{(k)} \]

如果不考虑上标，会发现残差 \(r^{(k)}\) 就是残差原始含义 \(b-Ax\)。这也就提供了看待松弛迭代法的另一种视角：松弛迭代法是在原始的 G-S 迭代法的基础上，对残差进行了松弛。

对于不同的 \(\omega\)，松弛迭代法 (Relaxation Methods) 具有不同的名字：

  • \(0<\omega<1\)：低松弛迭代法 (Under-Relaxation Methods)
  • \(\omega=1\)：G-S 迭代法
  • \(\omega>1\)：超松弛迭代法 (Successive Over-Relaxation Methods)

Convergence of Relaxation Methods

如果要求松弛迭代公式中的迭代矩阵，则需要对公式做一些变换，那么就可以得到

\[ \begin{aligned} & x^{(k+1)} = (1-\omega) x^{(k)} + \omega D^{-1}(Lx^{(k+1)} + U x^{(k)} + b)\\ \iff & x^{(k+1)} = \underbrace{(D-\omega L)^{-1}[(1-\omega)D+\omega U]}_{T_\omega}x^{(k)}+\underbrace{(D-\omega L)^{-1}\omega}_{c_\omega}b\\ \end{aligned} \]

分析这个 \(T_\omega\) 就可以判断松弛迭代的收敛性。给出以下定理：

Kahan

如果 \(A\) 的对角元都非零，那么 \(T_\omega\) 的谱半径 \(\rho(T_\omega)\geqslant |\omega-1|\)

对角元肯定得都非零，否则 \(D\) 以及 \(D-\omega L\) 就不可逆了

Kahan 定理有推论：松弛迭代法收敛的必要条件是 \(0<\omega<2\)。这个必要条件再加上一个条件就能构成一个充分条件：

Ostrowski-Reich (Sufficient Condition)

如果 \(A\) 是正定矩阵，那么对于任意的 \(\omega\in(0,2)\)，松弛迭代法都可以收敛。

三对角矩阵是实际应用中常见的矩阵，对于 \(A\) 是三对角矩阵的情况会有更加解析的结论，可以给出最优的 \(\omega\)。

Convergence of Relaxation Methods for Tridiagonal Matrices

如果 \(A\) 是三对角矩阵，那么设对其应用 G-S 迭代和 Jacobi 迭代的迭代矩阵分别为 \(T_g\) 和 \(T_j\)，那么有

\[ \rho(T_g) = [\rho(T_j)]^2<1 \]

此时松弛迭代法的最优的 \(\omega\) 是

\[ \omega = \frac{2}{1+\sqrt{1-\rho(T_j)^2}} \]

在这样的 \(\omega\) 选择下，有 \(\rho(T_\omega)=\omega - 1\)。

Error Bounds and Iterative Refinement

Condition Number

在 \(Ax=b\) 中，设 \(x\) 和 \(b\) 是精确的。考虑扰动 \(b\) 产生误差 \(\delta b\)，分析最后得到的解 \(x+\delta x\) 中的误差 \(\delta x\)。有

\[ A(x+\delta x) = b + \delta b \]

分析可得

\[ \frac{\|\delta x\|}{\|x\|} \leqslant \|A\|\cdot\|A^{-1}\|\cdot\frac{\|\delta b\|}{\|b\|} \]

Proof

根据 \(A(x+\delta x) = b + \delta b\) 和 \(Ax=b\) 有

\[ A\delta x = \delta b \]

估计 \(x\) 的范数，有

\[ \|b\|=\|Ax\|\leqslant \|A\|\cdot\|x\| \Rightarrow \|x\|\geqslant \frac{\|b\|}{\|A\|} \]

要求所使用的矩阵范数和向量范数相容，一般情况下直接取矩阵范数为向量范数的诱导范数

于是就有

\[ \frac{\|\delta x\|}{\|x\|} \leqslant \frac{\|A^{-1}\delta b\|}{\|b\|}\|A\|\leqslant \|A\|\cdot\|A^{-1}\|\cdot\frac{\|\delta b\|}{\|b\|} \]

考虑扰动 \(A\) 产生误差 \(\delta A\)，分析最后得到的解 \(x+\delta x\) 中的误差 \(\delta x\)，有

\[ (A+\delta A)(x+\delta x) = b \]

可以分析得到

\[ \frac{\|\delta x\|}{\|x\|} \leqslant \frac{\|A\|\cdot\|A^{-1}\|\cdot\frac{\|\delta A\|}{\|A\|}}{1-\|A\|\cdot\|A^{-1}\|\cdot\frac{\|\delta A\|}{\|A\|}} \]

留作习题证明略

分析过程中会用到一个定理，在这里写一下。

\(I\pm B\)

如果 \(B\) 对某种诱导范数满足 \(\|B\|<1\)，那么有

  • \(I\pm B\) 可逆
  • \(\|(I\pm B)^{-1}\| \leqslant \dfrac{1}{1-\|B\|}\)

注意到，\(\|A\|\cdot\|A^{-1}\|\) 是一个很重要的常数，它被称为 \(A\) 的条件数，记为 \(\kappa(A)\)，用来衡量病态性。\(\kappa(A)\) 越大，说明矩阵越病态。经典的病态矩阵是 Hilbert 矩阵。

综合研究对 \(A\) 的扰动和对 \(b\) 的扰动，有

\[ (A+\delta A)(x+\delta x) = b + \delta b \]

其误差分析结果为

\[ \frac{\|\delta x\|}{\|x\|} \leqslant \frac{\kappa(A)}{1-\kappa(A)\frac{\|\delta A\|}{\|A\|}}\left(\frac{\|\delta A\|}{\|A\|}+\frac{\|\delta b\|}{\|b\|}\right) \]

留作习题证明略

\(\kappa(A)\) 具有如下性质：

  • \(A\) 对称，则 \(\kappa(A)_2=\frac{\lambda_{\max}}{\lambda_{\min}}\)

    2- 范数的诱导范数的意义下

  • 对于任意 \(p\) 范数的诱导范数，有 \(\kappa(A)_p\geqslant 1\)
  • \(\kappa (\alpha A)=\kappa(A)\), \(\forall \alpha\in \mathbb{R}\)
  • 如果 \(A\) 是正交矩阵 (\(AA^{\top}=I\))，那么有 \(\kappa (A)_2=1\)
  • 对于任意正交矩阵 \(P\)，有 \(\kappa (PA)_2=\kappa (AP)_2=\kappa (A)_2\)

Iterative Refinement

迭代优化的整体思想就是用 \(Ad=r\) 解得的 \(d\) 来改善 \(x\)。

Theorem

设 \(x^*\) 是对 \(Ax+b\) 的解 \(x\) 的近似，\(A\) 可逆，\(r=b-Ax^*\) 为残差，则对于任意的诱导范数有

\[ \|x-x^*\|\leqslant \|r\|\cdot \|A^{-1}\| \]

如果 \(x\neq 0\) 并且 \(b\neq 0\)，那么有

\[ \frac{\|x-x^*\|}{\|x\|}\leqslant \kappa(A)\frac{\|r\|}{\|b\|} \]

于是可以这样迭代优化一个已经求得的近似解 \(x_1\)：

  • 求解 \(Ad_1=r_1\)，得到 \(d_1\)
  • 计算 \(x_2=x_1+d_1\)
  • 重复这个过程

注意到，如果 \(d_1\) 精确，那么就有

\[ x_2=x_1+A^{-1}(b-Ax_1)=A^{-1}b \]

那 \(x_2\) 也就是精确的了。