Chap 7: Iterative Techniques in Matrix Algebra⚓︎

目标：同第 6 章，还是求解 \(A \bm{x} = \bm{b}\)。

上述思路的优势在于：

• 可以通过迭代次数来控制精度
• 迭代技术被实际运用于求解稀疏的(sparse) 线性方程组

接下来我们需要分析：

• 如何设计一个迭代方案
• 在何种条件下序列将会收敛
• 某个方法的收敛速度有多快
• 误差评估

Norms of Vectors and Matrices⚓︎

Vector Norms⚓︎

在 \(R^n\) 上的向量范数(vector norm) 是一个函数 \(\| \cdot \|\)。\(\forall \bm{x}, \bm{y} \in R^n, \alpha \in C\)，它将基于以下性质，从 \(R^n\) 映射到 \(R\)：

• 正定：\(\| \bm{x} \| \ge 0, \| \bm{x} \| = 0 \Leftrightarrow \bm{x} = \bm{0}\)
• 齐次(homogeneous)：\(\| \alpha \bm{x} \| = |\alpha| \cdot \| \bm{x} \|\)
• 三角不等式：\(\| \bm{x} + \bm{y}\| \le \| \bm{x} \| + \| \bm{y} \|\)

一些常用的范数：

• \(\| \bm{x} \|_1 = \sum\limits_{i=1}^n \|x_i\|\)
• \(\| \bm{x} \|_2 = \sqrt{\sum\limits_{i=1}^n |x_i|^2}\)（欧几里得范数）
• \(\| \bm{x} \|_p = \Big( \sum\limits_{i=1}^n |x_i|^p \Big)^{\frac{1}{p}}\)
• \(\| \bm{x} \|_\infty = \max\limits_{1 \le i \le n} |x_i|\)

注：\(\lim\limits_{p \rightarrow \infty} \| \bm{x} \|_p = \| \bm{x} \|_{\infty}\)

Matrix Norms⚓︎

对于所有规模为 \(n \times n\) 的矩阵，矩阵范数(matrix norms) 是一个实数值函数 \(\| \cdot \|\)。对于所有规模为 \(n \times n\) 的矩阵 \(A, B\) 以及所有的 \(\alpha \in C\)，满足：

• 正定：\(\| A \| \ge 0, \| A \| = 0 \Leftrightarrow A = O\)
• 齐次：\(\| \alpha A \| = |\alpha| \cdot \| A \|\)
• 三角不等式：\(\| A + B \| \le \| A \| + \| B \|\)
• 一致性(consistency)：\(\| AB \| \le \| A \| \cdot \| B \|\)

（下面两个小人的讨论未整理）

一些常用的范数：

• 弗罗贝尼乌斯范数(Frobenius norm)：\(\| A \|_F = \sqrt{\sum\limits_{i=1}^n \sum\limits_{j=1}^n |a_{ij}|^2}\)

• 自然范数(natural norm)

  • 算子范数(operator norm)（和向量范数 \(\| \cdot \|\) 关联）

    \[ \| A \|_p = \max\limits_{\bm{x} \ne \bm{0}} \dfrac{\| A \bm{x} \|_p}{\| \bm{x} \|_p} = \max\limits_{\| \bm{x} \|_p = 1} \| A\bm{x} \|_p \]

  • 谱范数(spectral norm)：\(\begin{cases} \| A \|_{\infty} = \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}| \\ \| A \|_1 = \max\limits_{1 \le j \le n} \sum\limits_{i=1}^n |a_{ij}| \\ \| A \|_2 = \sqrt{\lambda_{\max} (A^T A)}\end{cases}\)

    证明 \(\|A \|_{\infty} = \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}|\)

    1. 证明 \(\| A \|_{\infty} = \max\limits_{\| \bm{x} \|_{\infty} = 1} \| A \bm{x} \|_{\infty} \le \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}|\)

       \[ \| A \bm{x} \|_{\infty} = \max\limits_{1 \le i \le n} |(A \bm{x})_i| = \max\limits_{1 \le i \le n} |\sum\limits_{j=1}^n a_{ij} x_j| \le \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}| \cdot \max\limits_{1 \le i \le n} |x_j| \]

    2. 证明 \(\| A \|_{\infty} = \max\limits_{\| \bm{x} \|_{\infty} = 1} \| A\bm{x} \|_{\infty} \ge \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}|\)

       • 令第 \(p\) 行为最大行，即满足 \(\sum\limits_{j=1}^n |a_{pj}| = \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}|\)
       • 取一个特殊的单位向量 \(\bm{x}\) 使得 \(x_j = \begin{cases} 1, & \text{if } a_{pj} \ge 0 \\ -1, & \text{if } a_{pj} < 0 \end{cases}\)
       \[ \| A \bm{x} \|_{\infty} = \max\limits_{1 \le i \le n} \Big| \sum\limits_{j=1}^n a_{ij} x_j\Big| \ge \Big| \sum\limits_{j=1}^n a_{pj} x_j \Big| = \Big| \sum\limits_{j=1}^n |a_{pj}| \Big| = \max\limits_{1 \le i \le n} \sum\limits_{j=1}^n |a_{ij}| \]

Eigenvalues and Eigenvectors⚓︎

矩阵 \(A\) 的谱半径(spectral radius) \(\rho(A) = \max{| \lambda |}\)，其中 \(\lambda\) 是 \(A\) 的特征值。

若 \(\forall i, j = 1, 2, \dots, n\)，有 \(\lim\limits_{k \rightarrow \infty} (A^k)_{ij} = 0\)，那么称规模为 \(n \times n\) 的矩阵 \(A\) 是收敛的。

Iterative Techniques for Solving Linear Systems⚓︎

Jacobi Iterative Method⚓︎

对于线性方程组 \(\begin{cases}a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \\ \dots \\ a_{n1}x_1 + a_{n2}x_2 + \dots + a_{nn}x_n = b_n\end{cases}\)，当 \(a_{ii} \ne 0\) 时，可以解得：

用矩阵形式表示上述线形方程组，并转化为以下形式：

那么：

所以对于第 \(k\) 次高斯消元而言，\(\bm{x}^{(k)} = T_j \bm{x}^{(k-1)} + \bm{c_j}\)，其中 \(T_j\) 被称为雅可比迭代矩阵(Jacobi iterative matrix)。

Step 1  Set k = 1;
Step 2  while (k <= N_max) do step 3-6
        Step 3  for i = 1, ..., n
                    Set X_i = (b_i - sum(j=1, j!=i, j<=n, a_ij X0_j)) / a_ii;  // compute x_k
        Step 4  if norm(X - X_0)_infty = max(1<=i<=n, X_i - X0_i) < TOL then Output(X[]);
                STOP;    // successful
        Step 5  for i = 1, ..., n  Set X0[] = X[];  // update X0
        Step 6  Set k++;
Step 7  Output (Maximum number of iterations exceeded);
        STOP.    // unsuccessful

Gauss-Seidel Iterative Method⚓︎

观察线性方程组的解：

用矩阵形式表述为：

其中 \(T_g\) 为高斯 - 赛德尔迭代矩阵(Gauss-Seidel iterative matrix)。

Convergence of Iterative Method⚓︎

现在我们来考察迭代法 \(\bm{x}^{(k)} = T\bm{x}^{(k-1)} + \bm{c}\) 的收敛性。

下面一串式子有待理解和整理：

根据上述递推式，可以得到 \(\bm{e^{(k)}} = T^k \bm{e^{(0)}}\)，因此

• 充分条件：\(\|T\| < 1\ \Rightarrow\ \|T\|^k \rightarrow 0\ \text{as}\ k \rightarrow \infty\)
• 必要条件：\(\bm{e^{(k)}} \rightarrow \bm{0}\ \text{as}\ k \rightarrow \infty\ \Rightarrow T^k \rightarrow O\)

Relaxation Methods⚓︎

接下来我们从另一个角度审视高斯 - 赛德尔方法：

令 \(x_i^{(k)} = x_i^{(k-1)} + \textcolor{red}{\omega} \dfrac{r_i^{(k)}}{a_{ii}}\)。对于正数 \(\omega\) 的某种选择，我们能够减少残差向量的范数，并且得到更快的收敛。这样的方法称为松弛法(relaxation methods)。

• \(0 < \omega < 1\)：欠松弛法 (under-relaxation methods)
• \(\omega = 1\)：高斯 - 赛德尔方法
• \(\omega > 1\)：逐次超松弛法 (successive over-relaxation methods, SOR)

用矩阵形式可以表述为：

显然，矩阵 \(T_\omega\) 的表示过于复杂。幸运的是，我们还有以下更为简单的表示方法。

讨论

题目解答

给定 \(A = \begin{bmatrix}2 & 1 \\ 1 & 2\end{bmatrix}, \bm{b} = \begin{bmatrix}1 \\ 2\end{bmatrix}\)，以及迭代法 \(\bm{x^{(k)}} = \bm{x^{(k-1)}} + \omega (A\bm{x^{k-1}} - \bm{b})\)，那么：

• 当 \(\omega\) 取什么值时，该方法会收敛？
• 当 \(\omega\) 取什么值时，该方法的收敛速度最快？

考虑 \(T = I + \omega A\) 的特征值，解得 \(\lambda_1 = 1 + \omega, \lambda_2 = 1 + 3 \omega\)

• 要使该方法收敛，需满足 \(\rho(T) < 1 \quad \Rightarrow -\dfrac{2}{3} < \omega < 0\)
• 现在考虑 \(\rho(T) = \max\{|1 + \omega|, |1 + 3\omega|\}\) 在何时取最小值——可以画图研究：

发现当 \(\omega = -\dfrac{1}{2}\) 时取值最小。

评论区