系列笔记为上科学计算课上随意记下的笔记，可能有一些凌乱，勉强凑合着看。以记录和梳理为主，证明较少。

关于特征值的求解主要有两种方法，一类是基于矩阵相乘的迭代幂法，另一类是基于正交相似变换的方法。

幂法

幂法是求解矩阵主特征值（按模最大的特征值）及其对应特征向量的经典迭代方法，尤其适用于大型稀疏矩阵。其核心思想是通过构造向量序列的迭代过程逼近主特征方向，但收敛速度受次大特征值与主特征值的模长比值影响较大，且只能求取最大或最小、或最接近某个值的一个特征值。

幂法的基本原理

设矩阵 $A\in {\mathbb{R}}^{n\times n}$ 有 $n$ 个线性无关的特征向量 $x_1,x_2,\dots ,x_n$，对应特征值为 ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$，且满足 $|{\lambda }_1|>|{\lambda }_2|\ge \cdots \ge |{\lambda }_n|$。任意初始向量 $v_0$ 可表示为：$v_0={\sum }_{i=1}^n{\alpha }_i{x}_i({\alpha }_1\ne 0)$. 通过迭代 $v_k=A{v}_{k-1}$，得：
$$v_k=A^k{v}_0=\sum _{i=1}^n{\alpha }_i{\lambda }_i^k{x}_i={\lambda }_1^k\left({\alpha }_1{x}_1+\sum _{i=2}^n{\alpha }_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{x}_i\right)$$
当 $k\to \infty$，${\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k\to 0$，故 $v_k$ 趋近于 ${\lambda }_1^k{\alpha }_1{x}_1$。通过归一化（如取最大分量）可提取主特征向量 $x_1$，而主特征值 ${\lambda }_1$ 通过相邻迭代向量分量的比值确定:
$$\underset{n\to \infty }{\lim }\frac{{\left(v_{k+1}\right)}_i}{{\left(v_k\right)}_i}={\lambda }_1$$

幂法在迭代过程中若不进行规范化处理，当主特征值$|{\lambda }_1|\ne 1$时，向量序列$v_k$的模长会以指数速度增长（$|{\lambda }_1|>1$）或衰减（$|{\lambda }_1|<1$），导致数值溢出或精度丢失。为解决这一问题，需引入规范化操作，核心策略是通过对每次迭代后的向量进行尺度缩放，使其保持合理的数值范围。
$$u_k=\frac{v_k}{\Vert v_k{\Vert }_{\infty }},v_{k+1}=A{u}_k=\frac{v_{k+1}}{\Vert v_k{\Vert }_{\infty }}$$
从而：
$$\begin{array}{rl}{u}_k& \to \frac{x_1}{\max (x_1)}\\ \max (v_k)& \to {\lambda }_1\end{array}$$

幂法的加速策略

幂法的收敛速度由比值 $r=|{\lambda }_2/{\lambda }_1|$ 决定。当 $r\approx 1$ 时收敛缓慢，需引入加速技术。

原点平移法

构造矩阵 $B=A-pI$，其特征值为 ${\mu }_i={\lambda }_i-p$。选择适当的平移量 $p$，使得 $|{\mu }_1|\gg |{\mu }_i|$（$i\ge 2$），从而加速收敛。例如，当 $A$ 的特征值为实数且满足 ${\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_n$，取 $p=({\lambda }_2+{\lambda }_n)/2$ 可最大化 $|{\mu }_1|/|{\mu }_i|$，显著提升收敛速度。

Rayleigh商加速

设$A$为实对称矩阵，对于任意非零向量，定义其Rayleigh商为：
$$R_A(x):=\frac{x^{T}Ax}{x^{T}x}$$
由于是实对称矩阵，其一定可以相似对角化，也就是有$n$个相互独立的特征向量。于是$x$可以写成：
$$x=\sum {\alpha }_i{v}_i$$
从而很好证明：
$$\begin{array}{rl}& 1.{\lambda }_n⩽\frac{(Ax,x)}{(x,x)}⩽{\lambda }_1(\text{对于任何非零 }x\in {\mathbb{R}}^n);\\ & 2.{\lambda }_1=\underset{x\in {\mathbb{R}}^n}{\max }\frac{(Ax,x)}{(x,x)};\\ & 3.{\lambda }_n=\underset{x\in {\mathbf{R}}^n}{\min }\frac{(Ax,x)}{(x,x)}.\end{array}$$
我们在采用幂法求特征值时，常常精度都是在$k$阶。我们采用Rayleigh商，可以证明：
$$R_A(u_k)={\lambda }_1+O\left((\frac{{\lambda }_2}{{\lambda }_1}{)}^{2k}\right)$$

Aitken加速

对线性收敛序列 { a k } \{a_k\} {ak​}，应用Aitken外推公式：
$$a_k^{\prime }=a_k-\frac{(a_{k+1}-a_k{)}^2}{a_{k+2}-2a_{k+1}+a_k}$$
可消除线性误差项，加速逼近极限值。此方法无需额外矩阵运算，适用于幂法迭代序列的加速。

反幂法

反幂法用于求解矩阵的最小模特征值 ${\lambda }_n$ 及对应特征向量，其核心是对 $A^{-1}$ 应用幂法。因 $A^{-1}$ 的特征值为 $1/{\lambda }_n\ge 1/{\lambda }_{n-1}\ge \cdots \ge 1/{\lambda }_1$，反幂法迭代格式为：
$$A{v}_k={\mu }_{k-1},{\mu }_k=\frac{v_k}{\Vert v_k\Vert }$$
每次迭代需解线性方程组 $A{v}_k={\mu }_{k-1}$，通常通过LU分解提高效率。

结合原点平移法，可计算接近某给定值 $p$ 的特征值：对 $B=A-pI$ 应用反幂法，若 $p\approx {\lambda }_j$，则 $B^{-1}$ 的主特征值为 $1/({\lambda }_j-p)$，从而快速逼近 ${\lambda }_j$ 及其特征向量。

QR算法

Householder方法以矩阵的正交相似变换为基础，可以用来求解矩阵全部的特征值和特征向量。

QR算法的核心是对矩阵进行QR分解：
$$A=:A_1=Q_1{R}_1$$
其中$Q_1,R_1$分别是正交矩阵和上三角矩阵。这个过程中有三种典型方法，分别是Householder方法，Schimidt正交化，Givens矩阵法。三种分解方法的时间复杂度从小到大依次为：
1.Householder方法 (2/3*n^3)
2.Gram-Schmidt正交化 (3/3*n^3)
3.Givens矩阵 (4/3*n^3)
复杂度分析来自知乎回答QR分解的三种实现方法（Gram schmidt等）各自有什么优势和劣势？ - vonZooming的回答 - 知乎，本人未验证。

但是，如果在进行QR分解前使用Householer方法将$A$正交相似化为Hessenberg矩阵，其QR分解的复杂度一下就降到了$O(n^2)$，大大加快了分解速度。

进行QR分解之后进行迭代：
$$A_k=Q_k{R}_k⟹A_{k+1}:=R_k{Q}_k=Q_{k+1}{R}_{k+1}$$
其中有着一些性质：
$$A_{k+1}=Q_k^T{A}_k{Q}_k={\tilde{Q}}_k^T{A}_1{\tilde{Q}}_k$$
其中${\tilde{Q}}_k:={\prod }_{i=1}^k{Q}_k$。此外还有：
$$A^k={\tilde{Q}}_k{\tilde{R}}_k$$
在这样不断迭代下，可以证明最终会收敛到$schur$标准型，于是特征值就可以从中直接读出。具体实现细节见下：

1. 正交变换：Householder变换与Givens变换

作用：通过正交变换（保持向量长度和夹角）对矩阵进行数值稳定的相似变换。

• Householder变换：

  • 反射变换，通过一个超平面反射将向量中的多个元素变为零。
  • 用途：批量零化矩阵的某一行或一列（例如将矩阵化为上Hessenberg形式）。
  • 公式：$H=I-2\frac{v{v}^T}{v^{T}v}$，其中 $v$ 为构造的反射向量。

• Givens变换：

  • 平面旋转，通过旋转消去特定位置的元素（如次对角线元素）。
  • 用途：逐次零化单个元素（例如QR分解中的上三角化）。
  • 公式：$G(i,j,\theta )$ 在 $(i,j)$ 平面的旋转矩阵。

联系：两者均为正交矩阵，用于保持矩阵特征值不变的前提下简化矩阵结构。

---

2. 上Hessenberg矩阵

定义：次对角线以下元素全为零（或接近零），形如：
$$A=\left[\begin{array}{cccc}\ast & \ast & \cdots & \ast \\ \ast & \ast & \cdots & \ast \\ 0& \ast & \ddots & ⋮\\ 0& 0& \cdots & \ast \end{array}\right]$$
构造方法：

• 对任意方阵 $A$，通过 Householder变换 进行相似变换（左乘 $H$ 和右乘 $H^T$），逐步将每列的次对角线以下元素零化。
  意义：
• 上Hessenberg矩阵保留了原矩阵的特征值，但结构更简单，使得后续QR算法的计算量从 $O(n^3)$ 降为 $O(n^2)$。

---

3. 实Schur分解

目标：将实矩阵 $A$ 分解为准上三角矩阵（实Schur形式）：
$$A=QT{Q}^T$$
其中 $Q$ 为正交矩阵，$T$ 为准上三角矩阵（对角块为1×1或2×2实块，对应实特征值或共轭复特征对）。
关键点：

• 若 $A$ 已为上Hessenberg矩阵，QR算法可高效逼近实Schur形式。
• 2×2对角块处理复数特征值，避免引入复数运算。

---

4. QR算法

核心思想：通过迭代将矩阵收敛到实Schur形式，从而提取特征值。
步骤：

1. 预处理：用Householder变换将 $A$ 化为上Hessenberg矩阵 $H$。
2. 迭代：
   • 对 $H$ 进行QR分解：$H=QR$（用Givens变换处理次对角线元素）。
   • 计算新矩阵：$H^{\prime }=RQ$（RQ乘积保持上Hessenberg结构）。
   • 重复直到收敛为准上三角矩阵（实Schur形式）。
     加速技巧：

• 位移策略（Wilkinson位移）：加速对角块收敛。
• 隐式QR算法：避免显式构造 $Q$，直接通过Givens旋转更新矩阵。