1. 特征值近似的背景 在科学计算和工程应用中，精确地计算出所有特征值往往既有难度 且没有必要 。例如，对于 n × n ~n\times n~ n × n A ~\mathbf{A}~ A n > 5 ~n \gt 5~ n > 5 det ( A − λ I ) = 0 ~\det(\mathbf{A} - \lambda\mathbf{I}) = 0~ det ( A − λ I ) = 0 没有通用的解析解 幂法 （Power Method \textbf{Power Method} Power Method
2. 幂法：主特征值估算 如果一个矩阵 A ~\mathbf{A}~ A x 0 ~\mathbf{x}_0~ x 0 y k = A k x 0 ( k = 1 , 2 , 3 ⋯ ) \mathbf{y}_k = \mathbf{A}^k\mathbf{x}_0\,(\,k=1,2,3\cdots) y k = A k x 0 ( k = 1 , 2 , 3 ⋯ ) A ~\mathbf{A}~ A x 0 ~\mathbf{x}_0~ x 0
A = [ 1.8 0.8 0.2 1.2 ] , x 0 = [ − 0.5 1 ] \mathbf{A} = \begin{bmatrix}1.8 & 0.8 \\ 0.2 & 1.2\end{bmatrix},\quad \mathbf{x}_0 = \begin{bmatrix}-0.5 \\ 1\end{bmatrix} A = [ 1.8 0.2 0.8 1.2 ] , x 0 = [ − 0.5 1 ] 矩阵 A ~\mathbf{A}~ A λ 1 = 2 ~\lambda_1=2~ λ 1 = 2 λ 2 = 1 ~\lambda_2=1~~ λ 2 = 1 v 1 = [ 4 1 ] T , v 2 = [ − 1 1 ] T \mathbf{v}_1 = \begin{bmatrix}4 & 1\end{bmatrix}^T,\,\mathbf{v}_2=\begin{bmatrix}-1 & 1\end{bmatrix}^T v 1 = [ 4 1 ] T , v 2 = [ − 1 1 ] T
随着迭代次数的增加，新的向量 y k \mathbf{y}_k y k v 1 ~\mathbf{v}_1~ v 1 θ ~\theta~ θ 0 ~0~ 0 10 ~10~ 10 y 10 = [ 408.7 103.3 ] T ~\mathbf{y}_{10} = \begin{bmatrix}408.7 & 103.3\end{bmatrix}^T~ y 10 = [ 408.7 103.3 ] T y 10 ~\mathbf{y}_{10}~ y 10 y 9 ~\mathbf{y}_9~ y 9 最大分量
λ k = ( y 10 ) 1 ( y 9 ) 1 = 408.7 203.9 ≈ λ 1 = 2 \lambda_k = \frac{(\mathbf{y}_{10})_{1}}{(\mathbf{y}_{9})_{1}} = \frac{408.7}{203.9} \approx \lambda_1 = 2 λ k = ( y 9 ) 1 ( y 10 ) 1 = 203.9 408.7 ≈ λ 1 = 2 幂法正是基于这一现象，用于估算矩阵 A ~\mathbf{A}~ A λ 1 ~\lambda_1~ λ 1 v 1 ~\mathbf{v}_1~ v 1 x 0 ~\mathbf{x}_0~ x 0 A k x 0 ~\mathbf{A}^k\mathbf{x}_0~ A k x 0
3. 幂法的数学基础 假设 A ~\mathbf{A}~ A n × n ~n\times n~ n × n
A = V Λ V − 1 \mathbf{A} = \mathbf{V} \Lambda \mathbf{V}^{-1} A = V Λ V − 1 其中 V \mathbf{V} V Λ \Lambda Λ λ 1 , λ 2 , … , λ n \lambda_1, \lambda_2, \dots, \lambda_n λ 1 , λ 2 , … , λ n ∣ λ 1 ∣ > ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ |\lambda_1| > |\lambda_2| \geq \cdots \geq |\lambda_n| ∣ λ 1 ∣ > ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ x 0 ~\mathbf{x}_0~ x 0
x 0 = c 1 v 1 + c 2 v 2 + ⋯ + c n v n \mathbf{x}_0 = c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_n \mathbf{v}_n x 0 = c 1 v 1 + c 2 v 2 + ⋯ + c n v n 对 x 0 ~\mathbf{x}_0~ x 0 A ~\mathbf{A}~ A
A k x 0 = c 1 λ 1 k v 1 + c 2 λ 2 k v 2 + ⋯ + c n λ n k v n \mathbf{A}^k \mathbf{x}_0 = c_1 \lambda_1^k \mathbf{v}_1 + c_2 \lambda_2^k \mathbf{v}_2 + \cdots + c_n \lambda_n^k \mathbf{v}_n A k x 0 = c 1 λ 1 k v 1 + c 2 λ 2 k v 2 + ⋯ + c n λ n k v n 由于 ∣ λ 1 ∣ ≫ ∣ λ 2 ∣ , ∣ λ 3 ∣ , … |\lambda_1| \gg |\lambda_2|, |\lambda_3|, \dots ∣ λ 1 ∣ ≫ ∣ λ 2 ∣ , ∣ λ 3 ∣ , … k → ∞ ~k \to \infty~ k → ∞
A k x 0 ≈ c 1 λ 1 k v 1 \mathbf{A}^k \mathbf{x}_0 \approx c_1 \lambda_1^k \mathbf{v}_1 A k x 0 ≈ c 1 λ 1 k v 1 即， A k x 0 ~\mathbf{A}^k \mathbf{x}_0~ A k x 0 v 1 ~\mathbf{v}_1~ v 1 ∣ λ 1 ∣ k |\lambda_1|^k ∣ λ 1 ∣ k
4. 算法步骤 在前面的示例中，第 10 ~10~ 10 ( y 10 ) 1 = 408.7 ~(\mathbf{y}_{10})_1 = 408.7~ ( y 10 ) 1 = 408.7 ( y 9 ) 1 = 203.9 ~(\mathbf{y}_9)_1=203.9~ ( y 9 ) 1 = 203.9 迅速膨胀、甚至溢出
其实，我们只需要关心相邻两个向量之间的比值就可以近似得到主特征值 λ ~\lambda~ λ v ~\mathbf{v}~ v y k ~\mathbf{y}_k~ y k y k ~\mathbf{y}_k~ y k
我们这次用幂法的步骤重新迭代计算 A ~\mathbf{A}~ A 终止条件
A = [ 1.8 0.8 0.2 1.2 ] , x 0 = [ − 0.5 1 ] , ϵ = 10 − 3 \mathbf{A}=\begin{bmatrix}1.8 & 0.8 \\ 0.2 & 1.2\end{bmatrix},\quad\mathbf{x}_0=\begin{bmatrix}-0.5\\ 1\end{bmatrix},\quad \epsilon=10^{-3} A = [ 1.8 0.2 0.8 1.2 ] , x 0 = [ − 0.5 1 ] , ϵ = 1 0 − 3 借助 python ~\text{python}~ python
主特征值收敛于 2 ~2~ 2 [ 1 0.25 ] T \begin{bmatrix}1 & 0.25\end{bmatrix}^T [ 1 0.25 ] T
5. 幂法的收敛性 幂法的收敛速度决定了算法的运算效率，而收敛速度主要和下面三个因素有关：
6. 反幂法：任意特征值估算 反幂法 ( Inverse Power Method ) ~(\textbf{Inverse Power Method})~ ( Inverse Power Method ) α ~\alpha~ α B ~\mathbf{B}~ B A ~\mathbf{A}~ A λ 1 , λ 2 , ⋯ , λ n ~\lambda_1,\lambda_2,\cdots,\lambda_n~ λ 1 , λ 2 , ⋯ , λ n
A ∼ [ λ 1 0 ⋯ 0 0 λ 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ λ n ] , A − α I ∼ [ λ 1 − α 0 ⋯ 0 0 λ 2 − α ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ λ n − α ] \mathbf{A} \sim \begin{bmatrix}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n
\end{bmatrix},\quad \mathbf{A} - \alpha \mathbf{I} \sim \begin{bmatrix}
\lambda_1 - \alpha & 0 & \cdots & 0 \\
0 & \lambda_2 - \alpha & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n - \alpha
\end{bmatrix} A ∼ λ 1 0 ⋮ 0 0 λ 2 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ λ n , A − α I ∼ λ 1 − α 0 ⋮ 0 0 λ 2 − α ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ λ n − α 我们构造矩阵 B = A − α I ~\mathbf{B}=\mathbf{A} - \alpha\mathbf{I}~ B = A − α I B ~\mathbf{B}~ B λ 1 − α , λ 2 − α , ⋯ , λ n − α ~\lambda_1-\alpha,~\lambda_2-\alpha,~\cdots,~\lambda_n-\alpha~ λ 1 − α , λ 2 − α , ⋯ , λ n − α B − 1 = ( A − λ I ) − 1 ~\mathbf{B}^{-1}=(\mathbf{A} - \lambda\mathbf{I})^{-1}~ B − 1 = ( A − λ I ) − 1
λ 1 ′ = 1 λ 1 − α , λ 2 ′ = 1 λ 2 − α , ⋯ , λ n ′ = 1 λ n − α \lambda_1' = \frac{1}{\lambda_1-\alpha},\quad \lambda_2' = \frac{1}{\lambda_2-\alpha},\quad \cdots, \quad \lambda_n' = \frac{1}{\lambda_n-\alpha} λ 1 ′ = λ 1 − α 1 , λ 2 ′ = λ 2 − α 1 , ⋯ , λ n ′ = λ n − α 1 如果 α ~\alpha~ α λ i ~\lambda_i~ λ i ( λ i − α ) − 1 ~(\lambda_i-\alpha)^{-1}~ ( λ i − α ) − 1 B − 1 ~\mathbf{B}^{-1}~ B − 1 B − 1 ~\mathbf{B}^{-1}~ B − 1 x 0 ~\mathbf{x}_0~ x 0
y k = ( A − α I ) − 1 x k , ( k = 0 , 1 , 2 , ⋯ ) \mathbf{y}_k = (\mathbf{A} - \alpha\mathbf{I})^{-1}\mathbf{x}_k\,,\quad (k = 0, 1, 2,\cdots) y k = ( A − α I ) − 1 x k , ( k = 0 , 1 , 2 , ⋯ ) 要注意的是，在实际计算中并不会直接计算出逆矩阵 ( A − α I ) − 1 ~(\mathbf{A} - \alpha \mathbf{I})^{-1}~ ( A − α I ) − 1 x k ~\mathbf{x}_k~ x k y k ~\mathbf{y}_k~ y k 解线性方程组的方式来计算 y k ~\mathbf{y}_k~ y k
( A − α I ) y k = x k (\mathbf{A} - \alpha \mathbf{I})\,\mathbf{y}_k = \mathbf{x}_k ( A − α I ) y k = x k 后面迭代的步骤和幂法步骤完全一样，不过每次得到估计 λ k ′ ~\lambda_k'~ λ k ′
λ k = α + 1 λ k ′ \lambda_k = \alpha + \frac{1}{\lambda_k'} λ k = α + λ k ′ 1 下面我们通过一个具体示例来演示反幂法的具体步骤。
7. 反幂法实例分析 给定矩阵 A ~\mathbf{A}~ A α ~\alpha~ α x 0 ~\mathbf{x}_0~ x 0
A = [ 10 − 8 − 4 − 8 13 4 − 4 5 4 ] , α = 1.9 , x 0 = [ 1 1 1 ] \mathbf{A}=\begin{bmatrix}
10 & -8 & -4 \\
-8 & 13 & 4 \\
-4 & 5 & 4
\end{bmatrix},\quad \alpha = 1.9\, ,\quad \mathbf{x}_0 = \begin{bmatrix}1 \\ 1 \\ 1\end{bmatrix} A = 10 − 8 − 4 − 8 13 5 − 4 4 4 , α = 1.9 , x 0 = 1 1 1 迭代结束条件设置为相邻两个特征估计值的相对变化量 ϵ < 10 − 6 ~\epsilon < 10^{-6}~ ϵ < 1 0 − 6 1 ~1~ 1
重复上面的过程，直到满足结束条件，由于初始预估值 α ~\alpha~ α
