第 37B 章 位移结构与快速算法¶
前置：Toeplitz 矩阵 (Ch37A) · 矩阵分解 (Ch10) · 矩阵分析 (Ch14)
本章脉络：从精确结构到近似结构 \(\to\) 位移算子 (Displacement Operators) 的定义 \(\to\) 位移秩 (Displacement Rank) 的概念 \(\to\) 类 Toeplitz (Toeplitz-like) 与类 Hankel 矩阵 \(\to\) 核心技术：Schur 算法（逐层消元与生成元） \(\to\) 逆矩阵的位移结构 \(\to\) 广义 Levinson 算法 \(\to\) 应用：雷达信号处理中的超快速求逆、大规模卡尔曼滤波中的方差更新、编码理论
延伸：位移结构是处理“接近结构化”矩阵的统一语言；它证明了即便一个矩阵不是严格的 Toeplitz，只要它的位移秩足够低，我们仍能以近乎线性的复杂度对其进行分解与求逆
在 Ch37A 中，我们研究了具有精确平移不变性的矩阵。然而，现实中许多矩阵（如 Toeplitz 阵的逆，或者带有小扰动的循环阵）并不具备这种完美的对角线性质，但它们依然保留了某种“结构特征”。位移结构（Displacement Structure）通过定义特定的差分算子，量化了矩阵与理想结构的偏离程度。本章将介绍如何利用这一深度代数特征实现比传统 \(O(n^3)\) 更快数量级的超快速算法。
37B.1 位移算子与位移秩¶
定义 37B.1 (位移算子)
设 \(Z\) 为下移位矩阵。对于 \(n \times n\) 矩阵 \(A\)，定义其 Stein 位移 为： $\(\nabla_{Z, Z^T}(A) = A - Z A Z^T\)$ 若该差分矩阵的秩为 \(r\)，则称 \(A\) 的位移秩为 \(r\)。
结构化矩阵的界定
- 严格的 Toeplitz 矩阵的位移秩通常不超过 2。
- 凡是位移秩 \(r \ll n\) 的矩阵，统称为类 Toeplitz 矩阵。
37B.2 Schur 算法与生成元¶
生成元表示
若 \(\operatorname{rank}(\nabla A) = r\)，则 \(A\) 可以被表示为两组向量 \(\{g_i, h_i\}\)（称为生成元）的组合。这意味着我们只需存储 \(O(rn)\) 个元素即可完整描述矩阵。
算法 37B.1 (Schur 消元算法)
Schur 算法允许直接在生成元上进行消元，而无需显式写出完整的 \(n \times n\) 矩阵。每一步消元都对应于一次分数线性变换（Fractional Linear Transformation），总复杂度为 \(O(rn^2)\)。
37B.3 逆矩阵的结构保持¶
定理 37B.1 (位移秩的不变性)
若矩阵 \(A\) 的位移秩为 \(r\)，则其逆矩阵 \(A^{-1}\) 关于对应算子的位移秩也必为 \(r\)。 意义：这一结论解释了为什么 Toeplitz 阵的逆虽然不是 Toeplitz，但仍然可以被极其快速地求解。
练习题¶
1. [基础] 验证单位阵 \(I\) 关于算子 \(\nabla(A) = A - ZAZ^T\) 的位移秩。
参考答案
计算步骤： 1. \(ZIZ^T = ZZ^T\)。 2. 对于 \(n \times n\) 阵，\(ZZ^T = \operatorname{diag}(0, 1, 1, \ldots, 1)\)（因为最后一行被移出，第一行补 0）。 3. \(\nabla(I) = I - ZZ^T = \operatorname{diag}(1, 0, 0, \ldots, 0)\)。 结论：其秩为 1。单位阵是位移秩最简单的矩阵之一。
2. [生成元] 若 \(\nabla A = \mathbf{g}\mathbf{h}^T\)，写出 \(A\) 的显式恢复公式。
参考答案
推导： 利用级数展开：\(A = \sum_{k=0}^{n-1} Z^k (\mathbf{g}\mathbf{h}^T) (Z^T)^k\)。 这意味着 \(A\) 可以写成一列由移位向量构成的低秩外积之和。
3. [位移秩判定] 若 \(A\) 是 \(n \times n\) Toeplitz 阵，证明其位移秩 \(\le 2\)。
参考答案
证明： 观察 \(A - ZAZ^T\) 的元素。除了第一行和第一列，内部元素 \((A)_{i,j} - (A)_{i-1,j-1}\) 由于对角线性质全为 0。 差分矩阵只在边缘有值，其秩显然不超过 2。
4. [计算] 设 \(A\) 为类 Toeplitz 矩阵，\(r=2, n=1000\)。求逆的复杂度约为多少？
参考答案
估算： 使用广义 Schur 算法或 Levinson 算法，复杂度为 \(O(r n^2)\)。 计算：\(2 \cdot (1000)^2 = 2 \times 10^6\)。 对比 \(O(n^3)\)：\(10^9\)。计算效率提升了约 500 倍。
5. [性质] 什么是位移算子的“互易性”？
参考答案
指的是若 \(\nabla_{F, G}(A) = 0\)，则 \(\nabla_{G^*, F^*}(A^{-1}) = 0\) 的对应关系。它保证了结构在求逆运算下的对偶性。
6. [生成元缩减] 为什么在 Schur 算法中需要定期进行生成元的正交化？
参考答案
由于数值计算中的舍入误差，生成元向量组可能会逐渐失去其代数秩的精确性。通过 QR 分解或 SVD 重新压缩生成元，可以保持位移结构的“紧凑性”，提高算法稳定性。
7. [应用] 简述位移结构在快速卡尔曼滤波中的作用。
参考答案
在处理具有稳态特征的平稳随机过程时，状态转移阵和协方差阵具有类 Toeplitz 结构。利用位移结构，可以将卡尔曼增益的更新从 \(O(n^3)\) 降为 \(O(n^2)\)，实现实时高维滤波。
8. [Toeplitz-like] 两个位移秩分别为 \(r_1, r_2\) 的矩阵之和，其位移秩最大是多少？
参考答案
结论：\(r_1 + r_2\)。秩在加法下满足次加性。
9. [极限] 当 \(n \to \infty\) 时，类 Toeplitz 阵的求逆是否有 \(O(n \log^2 n)\) 的算法？
参考答案
是的。 利用位移结构与 Fast Fourier Transform (FFT) 的结合（通过超级 Schur 算法或分治法），可以将复杂度进一步降低到近线性级别。
10. [应用] 什么是 Gohberg-Semencul 公式？
参考答案
这是一个将 Toeplitz 矩阵的逆显式写为两个三角 Toeplitz 矩阵之积的公式。它是位移理论中最著名的闭式解结果，揭示了求逆操作如何将对角结构转化为卷积结构。
本章小结¶
位移结构是处理“准结构化”数据的现代利器：
- 从精确到近似：它打破了必须严格相等的限制，通过“位移秩”定义了矩阵与理想模板之间的代数距离，极大扩展了快速算法的应用范围。
- 生成元的魔法：通过将庞大的矩阵压缩为少量的生成元向量，位移理论实现了数据存储与计算复杂度的指数级跨越。
- 结构的遗传性：位移秩在求逆和 Schur 补运算下的稳定性，为建立统一的结构化数值代数体系提供了坚实的理论基础。