2.4.1 迭代法引论

对应教材 2.4.1、定理 2.7–2.9、习题 13–14；对应老师第 4 讲 §五、第 5 讲 §一–§三。 主线：把 $A\boldsymbol x=\boldsymbol b$ 拆成 $A=N-P$，得到 $\boldsymbol x^{(k+1)}=G\boldsymbol x^{(k)}+\boldsymbol d$；收敛性只看 $G$ 的谱半径。

2.4.1 分裂与迭代格式

设 $A$ 非奇异，且 $A=N-P$，其中 $N$ 可逆。原方程等价于 $$N\boldsymbol x=P\boldsymbol x+\boldsymbol b \quad\Longrightarrow\quad \boldsymbol x=N^{-1}P\boldsymbol x+N^{-1}\boldsymbol b.$$ 于是迭代格式 $$\boldsymbol x^{(k+1)}=G\boldsymbol x^{(k)}+\boldsymbol d, \qquad G=N^{-1}P,\quad \boldsymbol d=N^{-1}\boldsymbol b.$$ 实际计算不显式求 $N^{-1}$，而是每步解 $N\boldsymbol x^{(k+1)}=P\boldsymbol x^{(k)}+\boldsymbol b$。

误差方程：令 $\boldsymbol e_k=\boldsymbol x^{(k)}-\boldsymbol x^*$，则 $$\boldsymbol e_{k+1}=G\boldsymbol e_k \quad\Longrightarrow\quad \boldsymbol e_k=G^k\boldsymbol e_0.$$ 所以迭代收敛 $\iff$ 对任意初值 $G^k\boldsymbol e_0\to0$ $\iff$ $G$ 的谱半径 $\rho(G)\lt1$。

2.4.2 三个基本定理

定理 2.7（范数收敛等价）：若对某种范数 $\lVert\boldsymbol x^{(k)}-\boldsymbol x^*\rVert\to0$，则按分量也有 $\boldsymbol x^{(k)}\to\boldsymbol x^*$。这是有限维范数等价性的直接推论，用来把“范数收敛”与“分量收敛”互换。

定理 2.8（充要条件）：对任意初值 $\boldsymbol x^{(0)}$，迭代格式收敛的充要条件是 $$\rho(G)\lt1.$$

证明（老师第 5 讲的对角化解耦）：若 $G$ 可对角化，$G=T\Lambda T^{-1}$，则 $$\boldsymbol e_k=T\Lambda^kT^{-1}\boldsymbol e_0.$$ $\Lambda^k\to0$ $\iff$ 每个 $|\lambda_i|\lt1$。若 $G$ 不可对角化，用 Jordan 标准形：Jordan 块 $J=\lambda I+N$ 的 $k$ 次幂含 $\binom{k}{s}\lambda^{k-s}$，当 $|\lambda|\lt1$ 时仍趋于 0；反之若某个 $|\lambda|\ge1$，取对应特征向量作初值误差，$\boldsymbol e_k$ 不趋于 0。$\blacksquare$

定理 2.9（充分条件与误差估计）：若存在某种矩阵范数使 $\lVert G\rVert\lt1$，则

1. 方程组 $(I-G)\boldsymbol x=\boldsymbol d$ 的解存在且唯一；
2. 对任意初值，迭代收敛；
3. 有先验估计 $$\lVert\boldsymbol x^{(k)}-\boldsymbol x^*\rVert \le \frac{\lVert G\rVert^k}{1-\lVert G\rVert}\lVert\boldsymbol x^{(1)}-\boldsymbol x^{(0)}\rVert,$$ 和后验估计 $$\lVert\boldsymbol x^{(k)}-\boldsymbol x^*\rVert \le \frac{\lVert G\rVert}{1-\lVert G\rVert}\lVert\boldsymbol x^{(k)}-\boldsymbol x^{(k-1)}\rVert.$$

证明要点：$\lVert G\rVert\lt1$ $\Rightarrow$ $I-G$ 可逆（Neumann 级数 $\sum G^k$ 收敛），且 $$\boldsymbol x^{(k)}-\boldsymbol x^*=\sum_{j=k}^{\infty}(\boldsymbol x^{(j)}-\boldsymbol x^{(j+1)}) =\sum_{j=k}^{\infty}G^j(\boldsymbol x^{(0)}-\boldsymbol x^{(1)}),$$ 取范数即得先验估计；后验估计同理，把 $\boldsymbol x^{(k)}-\boldsymbol x^*$ 写成 $\sum_{j\ge k}G^{j-k}(\boldsymbol x^{(k)}-\boldsymbol x^{(k+1)})$。$\blacksquare$

两条判据的分工：

• $\rho(G)\lt1$ 是充要条件，但大规模问题算不出特征值；
• $\lVert G\rVert\lt1$ 是充分条件，容易手算（$\lVert G\rVert_1$、$\lVert G\rVert_\infty$）；
• $\rho(G)\le\lVert G\rVert$，所以范数判据更保守；$\lVert G\rVert\ge1$ 时迭代仍可能收敛。

2.4.3 习题（教材习题 13–14）