分治法计算对称矩阵特征值
题目描述
给定一个n×n的实对称矩阵A，要求计算其所有特征值。对称矩阵的特征值都是实数，并且存在完整的正交特征向量系。分治法是一种高效算法，特别适用于求解对称三对角矩阵的特征值问题，它通过递归地将大问题分解为小问题来求解。
解题过程
- 问题转化
若矩阵A是一般对称矩阵，首先通过Householder变换将其化为对称三对角矩阵T（即除主对角线和相邻次对角线外元素均为0）。因为相似变换不改变特征值，所以求A的特征值转化为求T的特征值。设T为：
\[ T = \begin{bmatrix} \alpha_1 & \beta_1 & & \\ \beta_1 & \alpha_2 & \beta_2 & \\ & \ddots & \ddots & \ddots \\ & & \beta_{n-2} & \alpha_{n-1} & \beta_{n-1} \\ & & & \beta_{n-1} & \alpha_n \end{bmatrix} \]
- 分治策略
将T从中间位置k（通常取k=⌊n/2⌋）分割为四个子块：
\[ T = \begin{bmatrix} T_1 & \beta_k e_k e_1^T \\ \beta_k e_1 e_k^T & T_2 \end{bmatrix} \]
其中：
- \(T_1\)是k×k的对称三对角矩阵（左上角）。
- \(T_2\)是(n-k)×(n-k)的对称三对角矩阵（右下角）。
- 分割点处的次对角线元素为β_k，e_k和e_1是标准基向量。
通过减去秩1修正项，T可写为：
\[ T = \begin{bmatrix} T_1 & 0 \\ 0 & T_2 \end{bmatrix} + \beta_k v v^T, \quad v = \begin{bmatrix} e_k \\ e_1 \end{bmatrix} \]
这里v是n维向量，前k个元素中第k个为1，后n-k个元素中第1个为1，其余为0。
- 递归求解子问题
递归地对T1和T2应用分治法，得到它们的特征值分解：
\[ T_1 = Q_1 \Lambda_1 Q_1^T, \quad T_2 = Q_2 \Lambda_2 Q_2^T \]
其中Λ1和Λ2是对角矩阵，包含子矩阵的特征值。令：
\[ D = \begin{bmatrix} \Lambda_1 & 0 \\ 0 & \Lambda_2 \end{bmatrix}, \quad Q = \begin{bmatrix} Q_1 & 0 \\ 0 & Q_2 \end{bmatrix} \]
则T可表示为：
\[ T = Q D Q^T + \beta_k v v^T \]
- 秩1修正的特征值问题
原问题转化为求矩阵\(D + \beta_k u u^T\)的特征值，其中\(u = Q^T v\)。因为D是对角矩阵，问题简化为对角矩阵加秩1修正的特征值计算。其特征值λ满足以下特征方程：
\[ f(\lambda) = 1 + \beta_k \sum_{i=1}^n \frac{u_i^2}{d_i - \lambda} = 0 \]
其中d_i是D的对角元（即T1和T2的特征值），u_i是向量u的分量。
-
求解特征方程
通过牛顿迭代法等数值方法求解f(λ)=0。由于f(λ)在d_i处有极点，特征值分布在d_i之间的区间内。需在每个区间内搜索根，利用f(λ)的单调性保证迭代收敛。 -
递归终止与合并
当子矩阵大小为1×1时，特征值即为该元素，直接返回。递归合并所有子问题的特征值，得到T的全部特征值。 -
复杂度分析
分治法的计算复杂度为O(n log n)（忽略常数因子），优于直接QR算法的O(n³)。
总结
分治法通过递归分解、子问题求解、秩1修正合并，高效计算出对称三对角矩阵的特征值，是数值线性代数中求解特征值问题的核心算法之一。