【概述】

幂法（Power Method）主要用于近似计算矩阵的主特征值和主特征向量，即绝对值最大的特征值与其对应的特征向量，其是一种迭代方法，适用于大型稀疏矩阵

【原理】

向量序列的构造

对于 $n$ 阶矩阵 $A$，任取一初始的 $n$ 维向量 $\mathbf{x}_0$，构造一个 $n$ 维向量序列：

$\mathbf{x}_0,\quad \mathbf{x}_1=A\mathbf{x}_0, \quad \mathbf{x}_2=A\mathbf{x}_1, \quad \cdots, \quad \mathbf{x}_k=A\mathbf{x}_{k-1}$

假设 $A$ 有 $n$ 个特征值 $\lambda_i,i=1,2,\cdots,n$，按绝对值大小排列：

$|\lambda_1| \geq |\lambda_2| \geq \cdots \geq |\lambda_n|$

对应的 $n$ 个线性无关的特征向量为：

$\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_n$

这 $n$ 个特征向量构成 $n$ 维空间的一组基

那么可将初始向量 $\mathbf{x}_0$ 表示为 $\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_n$ 的线性组合，即：

$\mathbf{x}_0 = a_1\mathbf{u}_1+a_2\mathbf{u}_2+\cdots+a_n\mathbf{u}_n$

则有：

$\begin{gather*} \mathbf{x}_1 = A\mathbf{x}_0 = a_1A\mathbf{u}_1+a_2A\mathbf{u}_2+\cdots+a_nA\mathbf{u}_n \\ \mathbf{x}_2 = A\mathbf{x}_1 = A^2\mathbf{x}_0 = a_1A^2\mathbf{u}_1+a_2A^2\mathbf{u}_2+\cdots+a_nA^2\mathbf{u}_n \\ \vdots \\ \mathbf{x}_k = A\mathbf{x}_{k-1} = A^{k}\mathbf{x}_0= a_1A^k\mathbf{u}_1+a_2A^k\mathbf{u}_2+\cdots+a_nA^k\mathbf{u}_n \\ \end{gather*}$

进一步，有：

$\begin{align*} \mathbf{x}_k &= A\mathbf{x}_{k-1} \\ &= A^{k}\mathbf{x}_0 \\ &= a_1A^k\mathbf{u}_1+a_2A^k\mathbf{u}_2+\cdots+a_nA^k\mathbf{u}_n \\ &= a_1\lambda_1^k \mathbf{u}_1 + a_2\lambda_2^k \mathbf{u}_2 + \cdots + a_n\lambda_n^k \mathbf{u}_n \end{align*}$

单根情况

当矩阵 $A$ 的主特征值 $\lambda_1$ 是特征方程的单根时，由 $\mathbf{x}_k=a_1\lambda_1^k \mathbf{u}_1 + a_2\lambda_2^k \mathbf{u}_2 + \cdots + a_n\lambda_n^k \mathbf{u}_n$ 可得：

$\mathbf{x}_k = a_1 \lambda_1^k\Big[ \mathbf{u}_1+\frac{a_2}{a_1}(\frac{\lambda_2}{\lambda_1})^k\mathbf{u}_2+\cdots + \frac{a_n}{a_1}(\frac{\lambda_n}{\lambda_1})^k\mathbf{u}_n \Big]$

由于 $|\lambda_1|>|\lambda_j|,j=2,3,\cdots,n$，当 $k\rightarrow \infty$ 时，有：

$\mathbf{x}_k = a_1\lambda_1^k[\mathbf{u}_1+\varepsilon_k]$

其中，$\varepsilon_k$ 是当 $k\rightarrow \infty$ 时的无穷小量，即有：

$\mathbf{x}_k = a_1\lambda_1^k\mathbf{u}_1,\quad k\rightarrow \infty$

那么，当 $k$ 充分大时，有：

$\begin{gather*} \mathbf{x}_k \approx a_1\lambda_1^k\mathbf{u}_1 \\ \mathbf{x}_{k+1} \approx a_1\lambda_1^{k+1}\mathbf{u}_1 \end{gather*}$

于是主特征值可以表示为：

$\lambda_1 \approx \frac{x_{k+1,j}}{x_{kj}}$

其中，$x_{k+1,j}$ 和 $x_{kj}$ 分别是 $\mathbf{x}_k$ 和 $\mathbf{x}_{k+1}$ 的第 $j$ 个分量，即此时主特征值可以看作是 $\mathbf{x}_{k+1}$ 和 $\mathbf{x}_k$ 的某个分量的比值

重根情况

当矩阵 $A$ 的主特征值是特征方程的重根，即

$|\lambda_1|=|\lambda_2|=\cdots=|\lambda_m|>|\lambda_{m+1}|\geq \cdots \geq |\lambda_n|$

时，由 $\mathbf{x}_k=a_1\lambda_1^k \mathbf{u}_1 + a_2\lambda_2^k \mathbf{u}_2 + \cdots + a_n\lambda_n^k \mathbf{u}_n$ 可得：

$\mathbf{x}_k = \lambda_1^k\Big[ a_1 \mathbf{u}_1+a_2\mathbf{u}_2 +\cdots+ a_m\mathbf{u}_m+a_{m+1}(\frac{\lambda_{m+1}}{\lambda_1})^k\mathbf{u_{m+1}}+\cdots + a_n(\frac{\lambda_n}{\lambda_1})^k\mathbf{u}_n \Big]$

由于 $|\lambda_1|=|\lambda_2|=\cdots=|\lambda_m|>|\lambda_{m+1}|\geq|\lambda_j|,j=m+2,m+3,\cdots,n$，当 $k\rightarrow \infty$ 时，有：

$\mathbf{x}_k = \lambda_1^k[a_1\mathbf{u}_1+a_2\mathbf{u}_2+\cdots+a_m\mathbf{u}_m+\varepsilon_k]$

其中，$\varepsilon_k$ 是当 $k\rightarrow \infty$ 时的无穷小量，即有：

$\mathbf{x}_k = \lambda_1^k[a_1\mathbf{u}_1+a_2\mathbf{u}_2+\cdots+a_m\mathbf{u}_m],\quad k\rightarrow \infty$

那么，当 $k$ 充分大时，有：

$\begin{gather*} \mathbf{x}_k \approx \lambda_1^k[a_1\mathbf{u}_1+a_2\mathbf{u}_2+\cdots+a_m\mathbf{u}_m] \\ \mathbf{x}_{k+1} \approx \lambda_1^{k+1}[a_1\mathbf{u}_1+a_2\mathbf{u}_2+\cdots+a_m\mathbf{u}_m] \end{gather*}$

于是主特征值可以表示为：

$\lambda_1 \approx \frac{x_{k+1,j}}{x_{kj}}$

规范化

综上所述，无论最大特征值是单根还是重根，幂法均有效

在以上定义中，随着不断的迭代，如果 $|\lambda_1|>1$，则 $\mathbf{x}_k$ 会无限增大，反之，如果 $|\lambda_1|<1$，则 $\mathbf{x}_k$ 会趋于 $0$，这样在计算机的运行中会出现造成溢出错误

因此通常会在每次迭代时进行规范化，将向量除以其无穷范数，即各向量分量的绝对值的最大值，因此可得到如下的迭代形式：

$\begin{gather*} \mathbf{y}_{k} = A\mathbf{x}_{k-1} \\ \mathbf{x}_{k} = \frac{\mathbf{y}_{k}}{\Vert \mathbf{y}_{k} \Vert_{\infty}} \end{gather*}$

【算法流程】

输入：目标矩阵 $A$，初始精度 $\varepsilon$

输出：主特征值 $\lambda$，主特征向量 $\mathbf{v}$

算法流程：

Step 1：令 $k=1$，选择初始向量 $\mathbf{x}_0$

Step 2：迭代并规范化向量

$\begin{gather*} \mathbf{y}_{k} = A\mathbf{x}_{k-1} \\ \mathbf{x}_{k} = \frac{\mathbf{y}_{k}}{\Vert \mathbf{y}_{k} \Vert_{\infty}} \end{gather*}$

Step 3：当 $\Vert \mathbf{x}_{k+1}-\mathbf{x}_k \Vert < \varepsilon$ 时，令 $\mathbf{v}=\mathbf{x}_k$，停止迭代

Step 4：令 $k=k+1$，进行迭代