对称矩阵特征值问题的Rayleigh商迭代算法

题目描述
Rayleigh商迭代算法是求解对称矩阵特征值问题的一种高效迭代方法，特别适用于计算特定特征值及其对应的特征向量。给定一个n×n实对称矩阵A，该算法通过迭代方式快速收敛到某个特征值λ和对应的特征向量v，满足Av = λv。与幂迭代法（只能求主特征值）不同，Rayleigh商迭代通过动态调整位移量，可收敛到任意特征值，且具有局部三次收敛速度。

解题过程

1. 算法原理
   • 设对称矩阵A的特征值为λ₁, λ₂, ..., λₙ，对应特征向量v₁, v₂, ..., vₙ。
   • 对于任意非零向量x，Rayleigh商定义为标量函数：

\[ R(x) = \frac{x^T A x}{x^T x} \]

 当x接近某特征向量vᵢ时，R(x)逼近对应特征值λᵢ。  

• 迭代核心：在每一步中，以当前Rayleigh商作为位移，求解线性系统以更新向量，逐步逼近特征对。

2. 初始化

   • 选择初始向量x₀（通常随机生成或启发式选择），要求‖x₀‖₂ = 1（单位范数）。
   • 计算初始Rayleigh商：σ₀ = x₀ᵀ A x₀。

3. 迭代步骤
   对于第k步迭代（k = 0, 1, 2, ...）：

   • 步骤1：求解线性系统
     构造位移矩阵(A - σₖI)，并求解：

\[ (A - \sigma_k I) y_{k+1} = x_k \]

 此处需解线性方程组，通常用LU分解或Cholesky分解（若A正定）加速。  

• 步骤2：归一化向量
  更新向量：

\[ x_{k+1} = \frac{y_{k+1}}{\|y_{k+1}\|_2} \]

 确保迭代向量保持单位范数。  

• 步骤3：更新Rayleigh商
  计算新的位移量：

\[ \sigma_{k+1} = x_{k+1}^T A x_{k+1} \]

 若A对称，σₖ₊₁即当前逼近的特征值。

4. 收敛判断

   • 检查残差：‖A xₖ₊₁ - σₖ₊₁ xₖ₊₁‖₂ < ε（ε为预设精度，如1e-10）。
   • 或检查相邻迭代步特征值差：|σₖ₊₁ - σₖ| < ε。
   • 若收敛，输出特征值λ = σₖ₊₁和特征向量v = xₖ₊₁；否则继续迭代。

5. 注意事项

   • 收敛性：若初始向量x₀接近某特征向量，算法局部三次收敛（比幂迭代的线性收敛快）。
   • 位移矩阵奇异性：当σₖ接近A的特征值时，(A - σₖI)可能接近奇异，需用稳定数值方法（如列主元分解）求解线性系统。
   • 多特征值计算：需结合降维技术（如收缩矩阵）避免重复计算同一特征对。

示例说明
设对称矩阵A = [2, 1; 1, 2]，特征值λ₁=3, λ₂=1。

• 初始向量x₀ = [0.707, 0.707]ᵀ（单位范化后）。
• 计算σ₀ = x₀ᵀ A x₀ = 3（恰为λ₁）。
• 解(A - 3I)y₁ = x₀，得y₁ = [-0.707, 0.707]ᵀ，归一化后x₁ = [-0.707, 0.707]ᵀ。
• 更新σ₁ = x₁ᵀ A x₁ = 1（收敛到λ₂）。
  此例展示算法如何通过调整位移快速切换特征值。