线性方程组的迭代解法

• 简单迭代法
  • 迭代公式
    • 已知线性方程组 $A\boldsymbol x = \boldsymbol b$。
    • 第一种迭代格式：
      • 原方程组化为 $\boldsymbol x = (I - A)\boldsymbol x + \boldsymbol b$，则迭代公式为 $\boldsymbol x^{(k+1)} = (I - A) \boldsymbol x^{(k)} + \boldsymbol b$。
    • 第二种迭代格式（雅可比迭代法）：
      • 对于第 $i$ 个方程，将 $x_i$ 用其他未知数表示：$x_i = \displaystyle\sum_{j\ne i} \left(-\dfrac{a_{ij}}{a_{ii}}\right) x_j + \dfrac{b_i}{a_{ii}}=\displaystyle\sum_{j=1}^n g_{ij}x_j +f_i$。
      • 矩阵形式为 $\boldsymbol x^{(k+1)} = G\boldsymbol x^{(k)}+\boldsymbol f, G = D^{-1}(D - A), \boldsymbol f = D^{-1}\boldsymbol b$。
  • 收敛条件
    • 假设两种迭代格式均记作为 $\boldsymbol x^{(k+1)} = M\boldsymbol x^{(k)}+ \boldsymbol n$。
    • 收敛充要条件：$\rho(M) < 1$。
    • 三种充分条件：
      • $\mu = \| M \|_\infty < 1$，则简单迭代法必定收敛。$\| \boldsymbol x^{(k)} - \boldsymbol \alpha \|_\infty \le \dfrac{\mu^k}{1-\mu} \| \boldsymbol x^{(1)} - \boldsymbol x^{(0)} \|_\infty$。
      • $\nu = \| M \|_1 < 1$，则简单迭代法必定收敛。$\| \boldsymbol x^{(k)} - \boldsymbol \alpha \|_1 \le \dfrac{\nu^k}{1-\nu} \| \boldsymbol x^{(1)} - \boldsymbol x^{(0)} \|_1$。
      • $p = \| M \|_F < 1$，则简单迭代法必定收敛。$\| \boldsymbol x^{(k)} - \boldsymbol \alpha \|_2 \le \dfrac{p^k}{1-p} \| \boldsymbol x^{(1)} - \boldsymbol x^{(0)} \|_2$。
    • 以上充分条件的统一表述：$\| M \| < 1$ 时，简单迭代法必定收敛。
    • 另外的误差估计公式：$\|\boldsymbol x^{(k)} - \boldsymbol \alpha\| \le \dfrac{\|M\|}{1 - \|M\|}\|\boldsymbol x^{(k)} - \boldsymbol x^{(k-1)}\|$。
    • 适用于雅可比迭代法的收敛充分条件：
      • 如果矩阵 $A$ 不可以通过仅交换行和列的合同变换得到形式 $\begin{bmatrix} A & B\\ 0 &D\end{bmatrix}$，则其不可约。
      • 如果矩阵 $A$ 的对角线元素满足 $|a_{ii}| \ge \displaystyle\sum_{j\ne i} |a_{ij}|$，则其对角占优。
      • 如果原方程组 $A\boldsymbol x = \boldsymbol b$ 中 $A$ 不可约，则雅可比迭代法收敛。
• 赛德尔迭代法
  • 迭代公式
    • 赛德尔迭代法的每一次迭代中，$x_i^{(k)}$ 迭代公式会使用 $x_{1\sim i-1}^{(k)}$。
    • $x_i^{(k+1)} = \displaystyle\sum_{j=1}^{i-1} m_{ij} x_j^{(k+1)} + \sum_{j=i}^{n} m_{ij} x_j^{(k)} + n_{i}$，适用于两种迭代格式。
    • 矩阵形式：$\boldsymbol x^{(k+1)} = M_1 \boldsymbol x^{(k+1)} + M_2 \boldsymbol x^{(k)} + \boldsymbol n, M = M_1 + M_2$，其中 $M$ 与简单迭代法中的相同。
  • 收敛条件
    • 赛德尔迭代法相当于迭代矩阵为 $(I-M_1)^{-1}M_2$ 的简单迭代法，收敛充要条件为 $\rho((I-M_1)^{-1}M_2) < 1$。
    • 三种充分条件（即 $M=M_1+M_2$）：
      • $\mu = \| M \|_\infty < 1$，则简单迭代法必定收敛。
        • $\| \boldsymbol x^{(k)} - \boldsymbol \alpha \|_\infty \le \dfrac{(\mu^*)^k}{1-\mu^*} \| \boldsymbol x^{(1)} - \boldsymbol x^{(0)} \|_\infty$
        • $\mu^* = \displaystyle\max_{i=1}^n \dfrac{\mu_i}{1 - r_i}$，$r_i = \displaystyle\sum_{j=1}^{i-1} |m_{ij}|$，$\mu_i = \displaystyle\sum_{j=i}^n |m_{ij}|$
      • $\nu = \| M \|_1 < 1$，则简单迭代法必定收敛。
        • $\| \boldsymbol x^{(k)} - \boldsymbol \alpha \|_1 \le \dfrac{\rho^k}{(1-s)(1-\rho)} \| \boldsymbol x^{(1)} - \boldsymbol x^{(0)} \|_1$
        • $\rho = \displaystyle\max_{j=1}^n \dfrac{t_j}{1 - s_j}$，$s = \displaystyle\max_{j=1}^n s_j$，$t_j = \displaystyle\sum_{i=1}^{j} |m_{ij}|$，$s_j = \displaystyle\sum_{i=j+1}^n |m_{ij}|$
      • $p = \| M \|_F < 1$，则简单迭代法必定收敛。
        • $\| \boldsymbol x^{(k)} - \boldsymbol \alpha \|_2^2 \le \dfrac{\rho^k}{(1-s)(1-\rho)} \| \boldsymbol x^{(1)} - \boldsymbol x^{(0)} \|_2^2$
        • $\rho = \displaystyle\max_{j=1}^n \dfrac{t_j}{1 - s_j}$，$s = \displaystyle\max_{j=1}^n s_j$，$t_j = \displaystyle\sum_{i=1}^{j} \theta_i$，$s_j = \displaystyle\sum_{i=j+1}^n \theta_i$，$\theta_i = \displaystyle\sum_{j=1}^n m_{ij}^2$
    • 若 $A\boldsymbol x = \boldsymbol b$ 中 $A$ 对称正定，则赛德尔迭代法收敛。
    • 若 $A$ 不可约且对角占优，则赛德尔迭代法收敛。
• 松弛迭代法
  • 定义
    • 记方程组的残差表示为 $R_i^{(k)} = b_i - \displaystyle\sum_{j=1}^n a_{ij} x_i^{(k)}$。
    • 记 $r_i^{(k)} = \dfrac{R_i^{(k)}}{a_{ii}} = \dfrac{b_i}{a_{ii}} - \displaystyle\sum_{j=1}^n \dfrac{a_{ij}}{a_{ii}} x_i^{(k)}$。
    • 松弛迭代法通过对指定的 $x_i^{(k)}$ 增加一定比例的 $r_i^{(k)}$ 来迭代。
    • 一般形式为 $x_i^{(k+1)} = x_i^{(k)} + \tilde w r_i^{(k)}$。
  • 迭代公式
    • 按 $|r_i|$ 最大值松弛迭代法
      • 第 $k$ 次迭代得到 $\boldsymbol x^{(k)},\boldsymbol r^{(k)}$，选取 $l=\displaystyle\arg\max_{i=1}^n |r_i^{(k)}|$。
      • 令 $x_l^{(k+1)} = x_l^{(k)}+r_l^{(k)}$，其他 $x_i^{(k+1)}=x_i^{(k)}$。
    • 简单迭代方式的逐次松弛法
      • 第 $k$ 次迭代得到 $\boldsymbol x^{(k)},\boldsymbol r^{(k)}$。
      • $x_i^{(k+1)} = x_i^{(k)} + \dfrac{\tilde w}{a_{ii}}\left(b_i - \displaystyle\sum_{j=1}^n a_{ij} x_j^{(k)} \right)$
    • 赛德尔迭代方式的逐次松弛法
      • 第 $k$ 次迭代得到 $\boldsymbol x^{(k)},\boldsymbol r^{(k)}$。
      • $x_i^{(k+1)} = x_i^{(k)} + \dfrac{\tilde w}{a_{ii}}\left(b_i - \displaystyle\sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \displaystyle\sum_{j=i}^n a_{ij} x_j^{(k)}\right)$
  • 收敛条件
    • 松弛迭代法收敛的必要条件为 $0 < \tilde w < 2$。
    • 若 $A\boldsymbol x = \boldsymbol b$ 中 $A$ 对称正定，且 $0 < \tilde w < 2$，则松弛迭代法收敛。
    • 若 $A$ 不可约且对角占优，且 $0<\tilde w \le 1$，则松弛迭代法收敛。