【线性代数】对称矩阵特征值估算

ducati · 2024-04-09 15:52:00 · 科技·工程

前置知识

相似变换与特征值
最优化与 Lagrange 乘子法

概述

给定实对称矩阵 A，估计 A 的所有特征值。我们将：

首先证明，A 可正交对角化，即 A = Q\Lambda_0 Q^T。
接着，通过消元得到 \Lambda_1，满足 A = P\Lambda_1 P^T。
最后，根据 \Lambda_0 \simeq \Lambda_1，结合 Sylvester 惯性定理，完成特征值的估算。

Part 1：实对称矩阵必可对角化

令二次型 f(x) = x^TAx = x \cdot Ax，其中 x \in \mathbb{R}^n；令 g(x) = x \cdot x，即 x 模长的平方。

考虑最优化问题

\text{minimize} \ f(x) \\ \text{s.t.} \ g(x) = 1

设 v 为任一最优解，由 Lagrange 乘子法有

\nabla_v f(v) - \lambda g(v) = 0

即

v \cdot A\text{d}v + \text{d}v \cdot Av - \lambda(v \cdot \text{d}v + \text{d}v \cdot v) = 0

Lemma 1：\forall x, y \in \mathbb{R}^n，x \cdot Ay = y \cdot Ax。

Proof：

\begin{aligned} x \cdot Ay &= x^TAy \\ &= x^TA^Ty \\ &= (Ax)^T y \\ &= ((Ax)^Ty)^T \\ &= y^T (Ax) \\ &= y \cdot Ax\end{aligned}

由 Lemma 1，得

2\text{d}v \cdot (Av - \lambda v) = 0

因此 \boldsymbol{\lambda} 即为特征值。

Lemma 2：v 的正交补空间 \mathcal{S} 是 A 不变的。

Proof：

设 v \cdot x = 0，则 \begin{aligned} v \cdot Ax &= x \cdot Av \\ &= \lambda(x \cdot v) \\ &= 0\end{aligned}
即 x \in \mathcal{S} \implies Ax \in \mathcal{S}。

令 \{b_1, b_2,\cdots,b_{n-1}\} 为 \mathcal{S} 的正交基底，则 M = \begin{bmatrix} b_1 &b_2 &\cdots &b_{n-1} &v \end{bmatrix} 是正交矩阵，即

M^{-1} = M^T

因此，A' = M^{-1}AM = M^TAM 仍对称。

删去 A' 的第 n 行及第 n 列，再在 M 下继续寻找特征值即可。

执行上述操作 n 次，可得 n 个线性无关的特征向量，以完成 A 的对角化。

值得一提的是，由于这些特征向量两两垂直，相似变换的过渡矩阵是正交矩阵，这也被称作正交对角化。更进一步的，实方阵能被正交对角化，当且仅当它是实对称矩阵。

因此，我们有 A = Q\Lambda Q^T，其中 \Lambda 是对角矩阵，Q 是正交矩阵。

众所周知的，相似变换的本质是替换坐标系——同一个线性变换在不同坐标系下有不同的表现，而相似变换便架起了它们之间的桥梁。同时，正交坐标系是美妙的，对角矩阵也是美妙的，而实对称矩阵恰好可以借助这个美妙的定理，在某个美妙的正交坐标系下，等价为一个美妙的对角矩阵。这个对角矩阵不仅与原矩阵相似，也与原矩阵全等。

Part 2: 实对称矩阵的消元

给定实对称矩阵 A，我们的目标是，通过消元快速找到 P, \Lambda 满足 \Lambda = PAP^T。

有很多的方式可以做到这一点，下面给出我自己的方法。

考虑枚举 i = 1, 2, \cdots, n，同时维护 j，满足 A 的前 i 行，前 i 列恰有 A_{11}, A_{22}, \cdots, A_{jj} 非 0。

每当 i \leftarrow i + 1 后：
- 借助 A_{11}, A_{22}, \cdots, A_{jj} 对第 i 行和第 i 列同时进行消元，保证初等行变换与列变换对应的矩阵互为转置。
- 消元完成后，设第 i 行首个非零元素为 A_{ik}，则第 i 列首个非零元素为 A_{ki}。若 k \le i，则将第 k 行加上第 i 行，将第 k 列加上第 i 列；再将第 k 行与第 j + 1 行交换，将第 k 列与第 j + 1 列交换。最后，我们将 j 加一，再将 i 改回 j，并回到流程的开头。特别的，若 k > i 或 k 不存在，则直接回到开头。

最后，我们便消得了对角矩阵 \Lambda。根据消元过程，容易算得满足 \Lambda = PAP^T 的 P。

Part 3: 特征值的估算

Theorem(Sylvester's law of inertia)：两个相同大小的实对称方阵具有相同数量的正、负和零特征值当且仅当它们全等。

根据 Part 1, 2，现有 A = Q\Lambda_0 Q^T = P\Lambda_1 P^T，显然 \Lambda_0 \cong \Lambda_1。即：

那么，如何估算所有特征值呢？不难发现，A 的 \ge k 的特征值数量，即为 A - kI 的正特征值数量。因此，在精度要求并不太高的时候，估算实对称矩阵特征值的任务，便可在多项式复杂度内完成了。