我们证明：对任意给定的 \(\varepsilon > 0\)，总可以人为构造一个矩阵范数，使得矩阵 \(A\) 在这个范数下的大小与谱半径 \(\rho(A)\) 任意接近。

由 Jordan 标准形定理，存在可逆矩阵 \(X\)，使得

其中 \(J\) 是由若干个 Jordan 块组成的分块对角矩阵：

每个 Jordan 块都可以写成

其中 \(\lambda_\ell\) 是 \(A\) 的一个特征值，因此

现在对每一个 Jordan 块 \(J_\ell\)，引入对角矩阵

其中 \(m_\ell\) 是该 Jordan 块的阶数，\(\delta > 0\) 是稍后要选取的小参数。

直接计算可得

也就是说，Jordan 块超对角线上的 1 被缩放成了 \(\delta\)。令

则

仍然是分块对角矩阵，并且每个 Jordan 块的对角元不变，超对角元都变成了 \(\delta\)。

现在在 \(\mathbb{R}^{n \times n}\) 上定义一个新的矩阵范数：

这里右边的 \(\|\cdot\|_\infty\) 是通常的诱导无穷范数。由于相似变换和可逆变换不会破坏范数结构，\(\|\cdot\|_*\) 的确是一个矩阵范数。

对 \(A\) 本身，有

而对任一 Jordan 块，其每一行元素绝对值之和至多为

因此整个矩阵满足

于是得到

最后只需取 \(0 < \delta < \varepsilon\)，就有

这就说明：对任意 \(\varepsilon > 0\)，都存在某个矩阵范数，使得 \(A\) 的范数不超过 \(\rho(A) + \varepsilon\)。定理得证。 \(\square\)

这个定理分为必要性和充分性两部分。

必要性：假设

任取 \(A\) 的一个特征值 \(\lambda\) 及其对应的非零特征向量 \(v\)，则

两边同时左乘 \(A^{k-1}\)，得到

由于 \(A^k \to 0\)，所以对任意向量都有 \(A^k v \to 0\)，于是

又因为 \(v \neq 0\)，这只能说明

从而必有

由于这对任意特征值都成立，所以

充分性：现在反过来假设

令

根据定理 5.1，存在某个矩阵范数 \(\|\cdot\|\)，使得

由矩阵范数的次可乘性，

因为 \(\|A\| < 1\)，所以

从而

矩阵范数趋于 0 等价于矩阵本身趋于零矩阵，因此

必要性和充分性都已证明，故

定理得证。 \(\square\)

先把迭代格式写成更适合分析的形式。由

逐次展开可得

接下来分别证明必要性和充分性。

必要性：假设该迭代对任意 \(g\) 和任意初值 \(x^{(0)}\) 都收敛。

首先，由“对任意 \(g\) 都收敛”，可知对任意给定的 \(g\)，极限

存在。对递推式取极限，得到

即

由于这里 \(g\) 是任意向量，上式说明线性方程组

对任意右端项都有解，因此 \(I - M\) 是满射。在线性有限维空间中，满射等价于可逆，所以 \(I - M\) 可逆，进而 \(1\) 不是 \(M\) 的特征值。

接着取特殊情形 \(g = 0\)。此时迭代变为

由假设，它对任意初值 \(x^{(0)}\) 都收敛。设其极限为 \(y\)，则由递推式取极限有

即

但前面已经证明 \(I - M\) 可逆，所以只能有

因此对任意初值 \(x^{(0)}\)，

这说明

再由定理 5.2，得到

充分性：现在假设

由定理 5.2 可知

又因为 \(\rho(M) < 1\)，所以 \(1\) 不可能是 \(M\) 的特征值，从而 \(I - M\) 可逆。记

则 \(x^*\) 满足不动点方程

定义误差向量

由迭代式和不动点方程相减，得到

于是

因为 \(M^k \to 0\)，所以

即

这说明迭代格式对任意 \(g\) 和任意初值 \(x^{(0)}\) 都收敛。

综上，

定理得证。 \(\square\)

设 \(x^*\) 是方程组 \(x = Mx + g\) 的准确解，即满足 \(x^* = Mx^* + g\)。

第一步：建立相邻迭代步之间的误差关系

由迭代格式 \(x^{(k+1)} = Mx^{(k)} + g\) 和 \(x^{(k)} = Mx^{(k-1)} + g\) 相减，得：

两边取范数，利用 \(\|M\| = q < 1\)，得：

递推可得：

第二步：建立误差与相邻迭代差的关系

利用三角不等式和 \(x^* = Mx^* + g\)，\(x^{(k+1)} = Mx^{(k)} + g\)，有：

移项整理得：

即：

第三步：推导误差的指数衰减界

利用第一步的结果递推：

综合第二步和第三步的结果，即得：

第四步：停机准则的推导

由 \(\|x^{(k)} - x^*\| \leq \frac{q}{1-q}\|x^{(k)} - x^{(k+1)}\|\)，要使 \(\|x^{(k)} - x^*\| < \varepsilon\)，只需：

即：

这就给出了实用的迭代停止准则。 \(\square\)

采用反证法。假设 \(A\) 是奇异矩阵，则存在非零向量 \(x \in \mathbb{R}^n\) 使得：

设 \(|x_k| = \max_{1 \leq i \leq n} |x_i| > 0\)，即 \(x_k\) 是 \(x\) 的绝对值最大分量。

考察 \(Ax = 0\) 的第 \(k\) 个方程：

即：

两边取绝对值：

由于 \(|x_j| \leq |x_k|\) 对所有 \(j\) 成立，所以：

因为 \(|x_k| > 0\)，两边除以 \(|x_k|\) 得：

这与 \(A\) 具有 严格对角占优（即 \(|a_{kk}| > \sum_{j \neq k} |a_{kj}|\)）矛盾！

因此假设不成立，\(A\) 必须是非奇异矩阵。\(\square\)

同样采用反证法。假设 \(A\) 奇异，则存在非零向量 \(x\) 使得 \(Ax = 0\)。

定义指标集：

即 \(S\) 是绝对值最大分量的指标集，\(T\) 是其余指标。

情况1：若 \(S\) 包含所有指标（即所有 \(|x_i|\) 相等）。

取 \(k \in S\)，由 \(Ax = 0\) 的第 \(k\) 个方程：

若 \(A\) 对角占优且至少有一行严格成立，设第 \(k_0\) 行严格对角占优，则对 \(k = k_0\)：

这导致 \(|a_{k_0 k_0}| \leq \sum_{j \neq k_0} |a_{k_0 j}|\) 的矛盾。

情况2：若 \(S\) 是 \(\{1, \ldots, n\}\) 的真子集（即存在严格更小的 \(|x_i|\)）。

由于 \(x \neq 0\)，不妨设 \(\|x\|_\infty = \max_i |x_i| = 1\)（通过缩放不改变 \(Ax = 0\) 的性质）。此时：

• 对 \(i \in S\)：\(|x_i| = 1\)
• 对 \(j \in T\)：\(|x_j| < 1\)

由于 \(A\) 是 不可约 的且 \(S, T\) 都非空，根据不可约矩阵的定义，必存在 \(i_0 \in S\) 和 \(j_0 \in T\) 使得 \(a_{i_0 j_0} \neq 0\)。

选取这样的 \(i_0 \in S\)，考察第 \(i_0\) 个方程：

两边取绝对值：

利用三角不等式分离两项：

对于第一项（\(j \in S, j \neq i_0\)）：由于 \(|x_j| \leq |x_{i_0}| = 1\)，有

对于第二项（\(j \in T\)）：由于 \(|x_j| < 1 = |x_{i_0}|\)，且存在 \(j_0 \in T\) 使得 \(a_{i_0 j_0} \neq 0\)，我们有严格不等式：

这是因为：对于使 \(a_{i_0 j} \neq 0\) 的 \(j\)（至少包含 \(j_0\)），有 \(|x_j| < 1\)，所以对应项满足 \(|a_{i_0 j}| \cdot |x_j| < |a_{i_0 j}|\)；对于使 \(a_{i_0 j} = 0\) 的 \(j\)，两边都为 0，不影响不等式。

综合两项估计：

这里严格不等式成立是因为第二项中至少有一项满足 \(|a_{i_0 j_0}| \cdot |x_{j_0}| < |a_{i_0 j_0}|\)（由于 \(a_{i_0 j_0} \neq 0\) 且 \(|x_{j_0}| < 1\)）。

于是得到：

这与第 \(i_0\) 行的对角占优条件 \(|a_{i_0 i_0}| \geq \sum_{j \neq i_0} |a_{i_0 j}|\) 矛盾！

说明：即使第 \(i_0\) 行是严格对角占优的行，上述推导仍然成立，因为严格不等式 \(|a_{i_0 i_0}| > \sum_{j \neq i_0} |a_{i_0 j}|\) 与推导结果 \(|a_{i_0 i_0}| < \sum_{j \neq i_0} |a_{i_0 j}|\) 更加矛盾。

综上，两种情况下都得到矛盾，因此 \(A\) 非奇异。\(\square\)

根据定理 5.3，只需证明在这些条件下，Jacobi 和 Gauss-Seidel 的迭代矩阵 \(M\) 满足 \(\rho(M) < 1\)。

先回忆两种迭代法的迭代矩阵：

• Jacobi：\(M_J = D^{-1}(D - A) = I - D^{-1}A\)，或等价地写为 \(B = D^{-1}(D-A)\)
• Gauss-Seidel：\(M_{GS} = (D - L)^{-1}U\)

其中 \(A = D - L - U\)，\(D\) 为对角部分，\(L\) 为严格下三角部分，\(U\) 为严格上三角部分。

第一部分：Jacobi 迭代法的收敛性

情形1：\(A\) 严格对角占优

对于 Jacobi 迭代矩阵 \(M_J = D^{-1}(D-A)\)，其元素为：

计算 \(M_J\) 的行和（无穷范数的定义）：

由于 \(A\) 严格对角占优，即 \(|a_{ii}| > \sum_{j \neq i} |a_{ij}|\)，所以：

这对所有 \(i = 1, 2, \ldots, n\) 成立，因此：

由谱半径与范数的关系 \(\rho(M_J) \leq \|M_J\|_\infty < 1\)，Jacobi 迭代收敛。

情形2：\(A\) 不可约对角占优

对于不可约对角占优矩阵，虽然某些行可能只满足弱对角占优（等号），但定理 5.2.2 已证明 \(A\) 非奇异。进一步可以证明（通过反证法和不可约性），此时仍有 \(\rho(M_J) < 1\)。

具体思路：假设 \(\rho(M_J) \geq 1\)，则存在特征值 \(\lambda\) 满足 \(|\lambda| \geq 1\) 和特征向量 \(x \neq 0\) 使得 \(M_J x = \lambda x\)。通过类似定理 5.2.2 的分析，利用不可约性和至少一行严格对角占优，可以导出矛盾。

第二部分：Gauss-Seidel 迭代法的收敛性

情形1：\(A\) 严格对角占优

对于 Gauss-Seidel 迭代矩阵 \(M_{GS} = (D - L)^{-1}U\)，我们需要证明 \(\|M_{GS}\|_\infty < 1\)（或直接用谱半径估计）。

设 \(y = M_{GS}x = (D - L)^{-1}Ux\)，即 \((D - L)y = Ux\)，写成方程组形式：

取 \(|y_k| = \|y\|_\infty = \max_i |y_i|\)。考察第 \(k\) 个方程：

取绝对值并利用 \(|y_j| \leq |y_k|\)（对 \(j < k\)）和 \(|x_j| \leq \|x\|_\infty\)：

即：

整理得：

由严格对角占优：\(|a_{kk}| - \sum_{j < k} |a_{kj}| > \sum_{j > k} |a_{kj}| \geq 0\)，所以：

由严格对角占优：

因此：

这说明 \(\|M_{GS}x\|_\infty < \|x\|_\infty\) 对所有 \(x \neq 0\) 成立，即 \(\|M_{GS}\|_\infty < 1\)，从而 \(\rho(M_{GS}) < 1\)。

情形2：\(A\) 不可约对角占优

类似地，利用不可约性和定理 5.2.2 的证明技巧，可以证明即使在对角占优（非严格）但不可约的情况下，仍有 \(\rho(M_{GS}) < 1\)。

综合上述分析，在对角占优或不可约对角占优条件下，Jacobi 和 Gauss-Seidel 迭代矩阵的谱半径都小于 1，因此两种迭代法必定收敛。\(\square\)

需要证明两个方向：

(1) \(Ax^* = b \Rightarrow x^*\) 是 \(\phi(x)\) 的唯一极小值点

设 \(x^*\) 满足 \(Ax^* = b\)，对任意 \(x \in \mathbb{R}^n\)，令 \(e = x - x^*\)，则：

由于 \(A\) 对称，有 \((x^*)^TAe = e^TAx^*\)，又因 \(Ax^* = b\)，故 \(e^TAx^* = e^Tb = b^Te\)。代入得：

即：

由于 \(A\) 正定，对任意 \(e \neq 0\) 有 \(e^TAe > 0\)，因此：

这说明 \(x^*\) 是 \(\phi(x)\) 的 严格 极小值点，且是唯一的。

(2) \(x^*\) 是 \(\phi(x)\) 的极小值点 \(\Rightarrow Ax^* = b\)

计算 \(\phi(x)\) 的梯度。对 \(\phi(x) = \frac{1}{2}x^TAx - b^Tx\)，由于 \(A\) 对称：

若 \(x^*\) 是极小值点，则必须满足驻点条件（极值的必要条件）：

即 \(Ax^* = b\)。

此外，\(\phi(x)\) 的 Hessian 矩阵为：

由于 \(A\) 正定，Hessian 在所有点处都正定，因此驻点 \(x^*\) 确实是极小值点（极值的充分条件）。

综上，\(Ax^* = b\) 与 \(x^*\) 是 \(\phi(x)\) 的唯一极小值点 等价。\(\square\)

利用定义 6.1 中的记号 \(B(x, y) = \langle x, Ay \rangle\) 和 \(\|x\|_A = B(x,x)^{1/2}\)，可以给出更紧凑的推导。

设 \(x^*\) 满足 \(Ax^* = b\)。对任意 \(y \in \mathbb{R}^n\)，计算 \(\phi(x^* + y)\)：

其中利用了 \(B\) 的双线性性和对称性（\(B(x^*, y) = B(y, x^*)\)）。

注意到 \(B(x^*, y) = \langle x^*, Ay \rangle = \langle Ax^*, y \rangle = \langle b, y \rangle\)，两项相消：

即：

等号成立当且仅当 \(\|y\|_A = 0\)，由 \(A\) 正定知 \(y = 0\)。因此 \(x^*\) 是 \(\phi\) 的严格唯一极小值点。

反方向：若 \(x^*\) 是极小值点，对任意 \(y \neq 0\) 和 \(t \in \mathbb{R}\)，函数

在 \(t = 0\) 处取极小，故 \(g'(0) = B(x^*, y) - \langle b, y \rangle = \langle Ax^* - b, y \rangle = 0\)。由 \(y\) 的任意性得 \(Ax^* = b\)。\(\square\)

由迭代公式 \(x^{(k)} = x^{(k-1)} + \alpha^{(k-1)} r^{(k-1)}\)，残差的递推关系为：

对两边左乘 \([r^{(k-1)}]^T\)：

将最优步长公式 \(\alpha^{(k-1)} = \dfrac{\langle r^{(k-1)}, r^{(k-1)} \rangle}{\langle r^{(k-1)}, Ar^{(k-1)} \rangle}\) 代入：

由于最速下降法中 \(p^{(k)} = r^{(k)}\)，因此 \(\langle p^{(k-1)}, p^{(k)} \rangle = 0\)。

几何解释：最优步长 \(\alpha^{(k-1)}\) 使 \(\phi(x^{(k-1)} + \alpha r^{(k-1)})\) 沿方向 \(r^{(k-1)}\) 取极小值，极小条件即为 \(\frac{d}{d\alpha}\phi\big|_{\alpha=\alpha^{(k-1)}} = 0\)，等价于新的梯度（即 \(-r^{(k)}\)）与当前搜索方向 \(r^{(k-1)}\) 正交。 \(\square\)

由于 \(A\) 是对称正定矩阵，存在正交矩阵 \(Q\) 使得 \(A = Q\Lambda Q^T\)，其中 \(\Lambda = \operatorname{diag}(\lambda_1, \ldots, \lambda_n)\)。

对任意多项式 \(P(t)\)，有 \(P(A) = QP(\Lambda)Q^T\)，其中 \(P(\Lambda) = \operatorname{diag}(P(\lambda_1), \ldots, P(\lambda_n))\)。

令 \(y = Q^Tx\)，计算 \(A\)-范数的平方：

其中利用了 \(P(A)\) 的对称性（因为 \(A\) 对称）和 \(Q^TQ = I\)。

由于 \(P(\lambda_i)^2 \leq \max_{1 \leq j \leq n} P(\lambda_j)^2\)，有：

两边开方即得：

\(\square\)

基础步骤（\(n=2\) 时）：

由算法定义，\(d^{(0)} = r^{(0)}\)。对于第 1 步的残差：

对于方向的 \(A\)-共轭性：

归纳假设：设对于 \(n = m \geq 2\)，已构造的残差向量 \(\{r^{(k)}\}_{k=0}^{m-1}\) 构成正交系，方向向量 \(\{d^{(k)}\}_{k=0}^{m-1}\) 构成 \(A\)-正交系，即对于 \(k = 0, 1, \ldots, m-1\) 有：

归纳步骤（证明第 \(m+1\) 步的性质）：

需要证明两个性质： 1. \(\langle r^{(m+1)}, r^{(k)} \rangle = 0\) 对所有 \(k = 0, 1, \ldots, m\) 成立 2. \(B(d^{(m+1)}, d^{(k)}) = 0\) 对所有 \(k = 0, 1, \ldots, m\) 成立

性质 1：残差向量的正交性

由残差更新公式 \(r^{(m+1)} = r^{(m)} - \alpha^{(m)} Ad^{(m)}\)，对任意 \(k \leq m\)：

情况 (i)：当 \(k = m\) 时

由归纳假设 \(\langle r^{(m)}, r^{(m)} \rangle = \|r^{(m)}\|_2^2\)，且 \(d^{(m)} = r^{(m)} + \beta^{(m-1)} d^{(m-1)}\)，因此：

情况 (ii)：当 \(k \leq m-1\) 时

由归纳假设 \(\langle r^{(m)}, r^{(k)} \rangle = 0\)，因此只需证明 \(\langle Ad^{(m)}, r^{(k)} \rangle = 0\)。

利用方向更新公式 \(r^{(k)} = d^{(k)} - \beta^{(k-1)} d^{(k-1)}\)（对于 \(k \geq 1\)，且 \(r^{(0)} = d^{(0)}\)），以及归纳假设 \(B(d^{(m)}, d^{(k)}) = 0\) 对所有 \(k \leq m-1\) 成立：

因此 \(\langle r^{(m+1)}, r^{(k)} \rangle = 0\) 对所有 \(k = 0, 1, \ldots, m\) 成立。

性质 2：搜索方向的 \(A\)-共轭性

利用方向构造公式 \(d^{(m+1)} = r^{(m+1)} + \beta^{(m)} d^{(m)}\)，对任意 \(k \leq m\)：

情况 (i)：当 \(k = m\) 时

由 \(\beta^{(m)}\) 的定义 \(\beta^{(m)} = -\dfrac{B(r^{(m+1)}, d^{(m)})}{B(d^{(m)}, d^{(m)})}\)，直接可得：

情况 (ii)：当 \(k \leq m-1\) 时

由归纳假设 \(B(d^{(m)}, d^{(k)}) = 0\)，因此只需证明 \(\langle r^{(m+1)}, Ad^{(k)} \rangle = 0\)。

利用残差更新关系 \(Ad^{(k)} = \dfrac{1}{\alpha^{(k)}}(r^{(k)} - r^{(k+1)})\)（由 \(r^{(k+1)} = r^{(k)} - \alpha^{(k)} Ad^{(k)}\) 变形得到）：

因此 \(B(d^{(m+1)}, d^{(k)}) = 0\) 对所有 \(k = 0, 1, \ldots, m\) 成立。

综上，由数学归纳法，共轭梯度法产生的残差向量序列 \(\{r^{(k)}\}\) 互相正交，搜索方向序列 \(\{d^{(k)}\}\) 互相 \(A\)-共轭。定理得证。 \(\square\)