Properties of Arnoldi process for skew symmetric matrices

Question

alt text

Solution (incomplete)

alt text

涉及数学概念解释

本题虽短，却串起了数值线性代数中一条完整的脉络：从矩阵的结构性质（反对称性）出发，经过 Krylov 子空间方法（Arnoldi 过程）的代数结构（Hessenberg / 三对角），最终落到迭代求解器（CG）的几何性质（残差正交）。下面逐个澄清其中的概念。

反对称矩阵

实矩阵 $B$ 称为反对称（skew-symmetric）的，若 $B^{T} = - B$ 。它有几条直接而重要的推论：

对角元全为零（因为 $B_{i i} = - B_{i i}$ ）。
全体特征值要么为 $0$ ，要么是纯虚数，并以共轭对的形式出现。
对任意实向量 $x$ ，二次型恒为零。

最后一条是本题（a）的核心，单独强调一下：

关键事实：反对称矩阵的二次型为零

⟨ B x, x ⟩ = 0 \forall x \in R^{n} .

证明只需用实内积的对称性 $⟨ B x, x ⟩ = ⟨ x, B^{T} x ⟩$ ，再代入 $B^{T} = - B$ 得 $⟨ B x, x ⟩ = - ⟨ x, B x ⟩ = - ⟨ B x, x ⟩$ ，故其值为零。

实内积的对称性

在实向量空间中，标准内积满足 $⟨ u, v ⟩ = ⟨ v, u ⟩$ ，并且对线性算子有伴随关系 $⟨ M u, v ⟩ = ⟨ u, M^{T} v ⟩$ 。本题的所有推导（包括 (a) 中 $⟨ A x, x ⟩ = ⟨ x, x ⟩$ 的证明）都反复用到这条性质，把 $A = I + α B$ 里反对称部分 $α B$ 的贡献「抵消」掉，只留下单位阵 $I$ 的贡献。

数值域与 Rayleigh 商

表达式

\frac{⟨ A x, x ⟩}{⟨ x, x ⟩}

称为 $A$ 在 $x$ 处的 Rayleigh 商；当 $x$ 取遍所有非零向量时，它的取值集合就是 $A$ 的数值域（field of values）。本题（a）证明了对 $A = I + α B$ 而言这个商恒等于 $1$ ，意味着 $A$ 的数值域退化为单点 ${1}$ ——这正是「 $A$ 的对称部分等于 $I$ 」的另一种说法，也是后续 CG 能良好定义的根本原因。

Krylov 子空间与 Arnoldi 过程

给定矩阵 $A$ 、起始向量 $q_{1}$ ，第 $m$ 阶 Krylov 子空间为

K_{m} (A, q_{1}) = span {q_{1}, A q_{1}, A^{2} q_{1}, \dots, A^{m - 1} q_{1}} .

Arnoldi 过程就是对这组天然病态的基做 Gram–Schmidt 正交化，逐步生成一组标准正交基 $q_{1}, q_{2}, \dots$ ，其递推关系即解答中的式 (1)：

A q_{j} = \sum_{k = 1}^{j + 1} h_{k j} q_{k}, h_{k j} = ⟨ A q_{j}, q_{k} ⟩ .

为什么求和只到

$A q_{j}$ 至多落在 $K_{j + 1}$ 中，而 ${q_{1}, \dots, q_{j + 1}}$ 是它的标准正交基，所以展开式自然在 $k = j + 1$ 处截断。这一「上界为 $j + 1$ 」的事实，正是下面 Hessenberg 结构的来源。

上 Hessenberg 矩阵

把系数 $h_{k j}$ 排成矩阵 $H_{m} = (h_{k j})$ ，由于当 $k > j + 1$ 时 $h_{k j} = 0$ ， $H_{m}$ 在次对角线以下全为零——这种「几乎上三角、只多一条次对角线」的矩阵称为上 Hessenberg 矩阵。Arnoldi 过程的代数本质就是把 $A$ 在 Krylov 基下约化为 Hessenberg 形： $Q_{m}^{T} A Q_{m} = H_{m}$ 。

三对角化与 Lanczos 算法

本题（b）的关键在于：当 $A$ 的对称部分平凡时，Hessenberg 矩阵会进一步退化成三对角形式。对一般对称矩阵，Arnoldi 退化为 Lanczos 算法，得到对称三对角阵；而这里 $A = I + α B$ 非对称，却凭借 $B$ 的反对称性得到形如

H_{m} = (\begin{matrix} 1 & - η_{2} \\ η_{2} & 1 & - η_{3} \\ ⋱ & ⋱ & ⋱ \\ η_{m - 1} & 1 & - η_{m} \\ η_{m} & 1 \end{matrix})

的三对角（且反对称偏移）结构。其证明的核心是三个内积分别讨论：

对角元 $⟨ A q_{k}, q_{k} ⟩ = 1$ （由 (a) 直接给出）；
上、下次对角元 $⟨ A q_{k}, q_{k - 1} ⟩ = α ⟨ B q_{k}, q_{k - 1} ⟩$ 与 $⟨ A q_{k - 1}, q_{k} ⟩ = - α ⟨ B q_{k}, q_{k - 1} ⟩$ 大小相等、符号相反；
更远的元素 $⟨ A q_{k}, q_{j} ⟩ = 0 (j < k - 1)$ ，因为 $A q_{j} \in K_{j + 1} ⊥ q_{k}$ 。

三对角化省下了什么

三对角结构意味着每一步 Arnoldi 递推只需与前两个基向量正交化（短递推），存储与计算量从 $O (m)$ /步降为 $O (1)$ /步。这正是 Lanczos 类方法相对一般 Arnoldi 的根本优势。

共轭梯度法（CG）与残差正交性：© 的完整证明

共轭梯度法（Conjugate Gradient, CG）通常用于对称正定系统，其残差序列 $r_{0}, r_{1}, \dots$ 两两正交、搜索方向两两 $A$ -共轭，这正是它在精确算术下至多 $n$ 步收敛的原因。© 要解释的是：对非对称的 $A = I + α B$ ，由 CG 一类方法生成的残差依然两两正交。

要把这件事说严谨，关键是认清「CG 残差正交」的本质是 Galerkin（投影）条件，而不是某一组特定的迭代系数。下面给出完整证明，并指明 (b) 的三对角结构究竟在哪里起作用。

投影框架：残差就是 Arnoldi 向量

设初始残差 $r_{0} = b - A x_{0}$ ， $q_{1} = r_{0} / ‖ r_{0} ‖$ ，对 $A$ 运行 Arnoldi 过程得到标准正交基 $Q_{k} = [q_{1}, \dots, q_{k}]$ 与 Hessenberg 阵 $H_{k}$ ，满足矩阵形式的递推关系

A Q_{k} = Q_{k} H_{k} + h_{k + 1, k} q_{k + 1} e_{k}^{T} .

Galerkin / 全正交化（FOM）方法在仿射空间里取迭代解 $x_{k} = x_{0} + Q_{k} y_{k} \in x_{0} + K_{k} (A, r_{0})$ ，并要求残差与整个 Krylov 子空间正交： $Q_{k}^{T} r_{k} = 0$ 。把 $x_{k}$ 代入残差定义：

\begin{aligned} r_{k} & = b - A x_{k} = r_{0} - A Q_{k} y_{k} \\ = ‖ r_{0} ‖ q_{1} - Q_{k} H_{k} y_{k} - h_{k + 1, k} (e_{k}^{T} y_{k}) q_{k + 1} \\ = Q_{k} (‖ r_{0} ‖ e_{1} - H_{k} y_{k}) - h_{k + 1, k} (e_{k}^{T} y_{k}) q_{k + 1} . \end{aligned}

左乘 $Q_{k}^{T}$ 并利用 $Q_{k}^{T} Q_{k} = I$ 、 $Q_{k}^{T} q_{k + 1} = 0$ ，Galerkin 条件 $Q_{k}^{T} r_{k} = 0$ 等价于

H_{k} y_{k} = ‖ r_{0} ‖ e_{1} .

只要 $H_{k}$ 可逆， $y_{k}$ 唯一确定，代回上式第一项消失，于是

残差是某个 Arnoldi 向量的标量倍

r_{k} = - h_{k + 1, k} (e_{k}^{T} y_{k}) q_{k + 1} = γ_{k} q_{k + 1}, γ_{k} \in R .

由于 ${q_{j}}$ 标准正交，立刻得到对任意 $i \neq j$ ，

⟨ r_{i}, r_{j} ⟩ = γ_{i} γ_{j} ⟨ q_{i + 1}, q_{j + 1} ⟩ = 0.

这就证明了残差两两正交。注意这一步只用到 ${q_{j}}$ 的标准正交性，对任意矩阵的 FOM 都成立——它是投影方法的普遍性质。

(b) 在哪里起作用：把长递推压缩成 CG 的短递推

上面的论证对一般非对称 $A$ 都给出正交残差，但代价是每一步要对全部已有基向量做正交化（长递推），这就是 GMRES/FOM 的形态，而非 CG。(b) 的三对角结构正是把它变回 CG 的关键：

$H_{k}$ 三对角 $\Rightarrow$ 求解 $H_{k} y_{k} = ‖ r_{0} ‖ e_{1}$ 与更新 $x_{k}, r_{k}$ 都可由相邻两三步的耦合短递推完成，无需保存全部 $q_{j}$ 。这正是共轭梯度法「残差更新 + 共轭方向更新」两条短递推的来源。
换言之，对称矩阵的 Lanczos 把 Arnoldi 压成对称三对角、从而得到经典 CG；而这里 $A = I + α B$ 虽不对称，(b) 证明它的 Arnoldi 约化同样是三对角（且 $H_{k} - I$ 反对称），于是同一套短递推、同样的残差正交性得以保留。

一个赠送的严谨细节：FOM 永不中断

上述推导要求每一步 $H_{k}$ 可逆。由 (b)， $H_{k}$ 的对角元全为 $1$ 、次对角与上次对角互为相反数，故 $H_{k} = I_{k} + S_{k}$ ，其中 $S_{k}$ 是实反对称三对角阵。反对称阵特征值为纯虚数，所以 $H_{k}$ 的特征值形如 $1 + i μ (μ \in R)$ ，恒不为零， $H_{k}$ 始终可逆。因此该投影方法在每一步都良定义、不会因 $H_{k}$ 奇异而中断——这与 (a) 中「数值域退化为单点 ${1}$ 」是同一件事的不同侧影。

一句话总结

残差正交 $=$ Galerkin 投影条件 $\Rightarrow r_{k} ∥ q_{k + 1}$ （标准正交）；而 (b) 的三对角性把全正交化压缩为 CG 的短递推，(b) 的反对称偏移又保证 $H_{k}$ 处处可逆、迭代不中断。三者合起来，才使「形如 CG 的方法用于非对称的 $A = I + α B$ 仍产出正交残差」成为严谨结论。

一点诚实的提醒

这里的「CG」指的是由 Arnoldi/Lanczos 三项递推导出的 Galerkin（FOM 型）共轭梯度法，其残差正交性来自投影条件。若把对称正定情形的系数公式 $α_{k} = ⟨ r_{k}, r_{k} ⟩ / ⟨ p_{k}, A p_{k} ⟩$ 原封不动地搬到非对称的 $A$ 上，数值实验表明残差未必正交（甚至可能发散）。换言之，使「残差正交」成立的，是 (b) 所保证的三对角投影结构，而非某条特定的标量更新公式。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。