Eigenvalues-and-Eigenvectors

矩阵特征值与特征向量的计算

3.1 幂法与反幂法

3.1.1 幂法

主要用于计算矩阵的按模为最大的特征值和对应的特征向量

假设对于$n\times n$实矩阵$A$有$n$个线性无瓜的特征向量$x_1,x_2,\cdots,x_n$其对应的特征值为$\lambda_1,\lambda_2,\cdots\lambda_n$，并且有以下关系$|\lambda_1|>|\lambda_2|\ge\cdots|\lambda_n|$,$\qquad x_i$为$\lambda_i$对应的特征向量

于是对于任意非零向量$u_0=\alpha_1x_1+\cdots+\alpha_nx_n$出发，($\alpha$不全为零，特征向量线性无关构成基)

有如下递推公式

$u_k = Au_{k-1} =A^ku_0 = \alpha_1A^kx_1+\cdots+\alpha_nA^kx_n \\ \qquad= \alpha_1\lambda_1^kx_1+\cdots+\alpha_n\lambda_n^kx_n \\\approx\alpha_1\lambda_1^kx_1(n\to+\infty)$

此迭代法即为幂法

• 计算特征向量

  当然实际中，为了避免迭代过程中$u_k$的模数过大，每次迭代需要对向量$u_k$归一化，即令其$\|\cdot\|_2$或$\|\cdot\|_\infty$ 为1，于是实际中的迭代公式如下：

  $y_{k-1} = \frac{u_{k-1}}{\|u_{k-1}\|} \\ u_k = Ay_{k-1}$

  当$(n\to+\infty) ,\lambda>0$时，$y_k\to\frac{\alpha_1 x_1}{\|\alpha_1 x_1\|}$,若$\lambda_1<0$,$y_k$各个分量的模有极限，即运行足够多次数时，$y_{k-1}$即可近似作为$\lambda_1$的特征向量

• 计算最大的特征值

  下面以上述使用2范数$\|\cdot\|_2$为例

  令$\lim\limits_{k\to+\infty}\beta_k = y_{k-1}^Tu_k = \frac{\alpha_1 x_1}{\|\alpha_1 x_1\|_2}A\frac{\alpha_1 x_1^T}{\|\alpha_1 x_1\|_2} = \frac{\alpha_1^2 x_1^Tx_1}{\|\alpha_1 x_1\|_2^2}\lambda_1 = \lambda_1$

  当迭代过程中$\beta_k$的相对误差足够小时，即可近似看做特征值

3.1.2 反幂法

若对于$n\times n$实非奇异矩阵$A$，$A$有$n$个线性无瓜的特征向量$x_1,x_2,\cdots,x_n$其对应的特征值为$\lambda_1,\lambda_2,\cdots\lambda_n$，并且有以下关系$|\lambda_1|\ge|\lambda_2|\ge\cdots\ge|\lambda_{n-1}|>|\lambda_n|$,

求得其最小的特征值与对应特征向量即为反幂法

因为矩阵非奇异，$Ax_i=\lambda_i x_i\Rightarrow A^{-1}x_i = \frac{1}{\lambda_i}x_i$

此时最小的特征值即成为了最大的特征值，使用对矩阵的逆矩阵使用幂法即可求得 模的倒数最大的特征值和对应的特征向量。也即求得该非奇异矩阵的最小的特征值

3.2 $Jacobi$方法

用于求实对称矩阵的全部特征值和特征向量

根据线性代数的知识可知对于任一一个实对称矩阵均可相似对角化，

于是对于实对称矩阵$A$，存在正交矩阵$U$，对角矩阵$D$使得，$U^TAU = D$, 而对角阵$D$的元素$\lambda_j$是矩阵$A$的特征值，且$U$的第$j$列即是对应$\lambda_j$的特征向量.

$Jacobi$方法就是用平面旋转矩阵对矩阵$A$做正交相似变换，化为对角矩阵，求得特征向量

现有如下正交矩阵$U_{pq}$，令$A_1 = U_{pq}^TAU_{pq}$， 可仅仅改变矩阵$A$的p行p列，q行q列而不改变特征值，并在一定的旋转角度下使得两对角元素$a_{pq} =a_{qp} = 0 ,cot2\phi = \frac{a_{pp}-a_{qq}}{2a_{pq}}$

$U_{p q}=\left[\begin{array}{ccccccccccc} 1 & & & \vdots & & & & & & & \\ & \ddots & & \vdots & & & & & & & \\ & & 1 & \vdots & & & & & & & \\ \cdots & \cdots & \cdots & \cos \varphi & \cdots & \cdots & \cdots & -\sin \varphi & \cdots & \cdots & \cdots \\ & & & \vdots & 1 & & & \vdots & & & \\ & & & \vdots & & \ddots & & \vdots & & & \\ & & & \vdots & & & 1 & \vdots & & & \\ \cdots & \cdots & \cdots & \sin \varphi & \cdots & \cdots & \cdots & \cos \varphi & \cdots & \cdots & \cdots \\ & & & \vdots & & & & \vdots & 1 & & \\ & & & \vdots & & & & \vdots & & \ddots & \\ & & & \vdots & & & & \vdots & & & 1 \end{array}\right] ，u_{pp}= cos\varphi=u_{qq}$

于是有迭代步骤如下：

1. 找到矩阵非主对角元素中按模最大的元素$a_{pq}$
2. 计算旋转角度$\phi$,使用对应旋转角度旋转矩阵$A$
3. 计算旋转后的矩阵$A_1$
4. 重复如上步骤，在若$\max\limits_{i<j}|a_{ij}^{(l)}|<\epsilon$, 停止计算，所求特征值近似为$A_l$

评价

有定理可知此方法一定是收敛的，即$\lim\limits_{k\to +\infty}\eta_k = \sum\limits_{i,j=1,i\not =j}^n(a_{ij}^{(k)})^2 = 0$ （但不证明）

收敛速度较快，数值稳定性较好，但是不能有效利用矩阵形状：稀疏矩阵，带状矩阵

可以发现并基本不会使得全部非对角元素全为零，但是每次迭代可以不断降低其他元素的影响，达到一定的精度

3.3 QR方法

重要一点，另出一篇来写

参考

[1] 颜庆津.数值分析[M].北京:北京航空航天大学出版社,2012.

[2] Timothy Sauer 数值分析[M]. 北京:机械工业出版社,2014.