数值分析学习笔记--矩阵的特征值和特征向量

特征值与特征向量的图解

如有疏漏，敬请指正。

幂法

在很多情况下，我们需要计算矩阵的按模最大特征值。幂法是计算按模最大特征值及其特征向量的数值方法。

任取初始向量$X^{(0)}$，进行迭代计算

$$X^{(k+1)}=AX^{(k)}$$

得到的迭代序列$\lbrace X^{(k)} \rbrace$，分析$X^{(k+1)}$与$X^{(k)}$之间的关系，就可以得到$A$的按模最大特征值及其特征向量的近似解。

在计算机运算的过程中，如果$X^{(k)}$的某个分量过大或者过小，都有可能导致运算失败。因此在实际计算中通常采用规范运算格式，规范运算可以按下面公式进行

$$\begin{cases} Y^{(k)}=X^{(k)}/||X^{(k)}||_\infty \\ X^{(k+1)}=AY^{(k)} \end{cases}$$

这样就可以保证$Y^{(k)}$的按模最大分量的值保持1或者-1。

规范运算的迭代序列一般有如下几种情况：

• 如果$\lbrace X^{(k)} \rbrace$收敛，那么$A$的按模最大特征值只有一个，且$\lambda_1>0$，对于充分大的$k$，按模最大分量$x_j^{(k)}$不变号，对应的$|y_j^{(k)}|=1, \lambda_1 \approx |x_j^{(k+1)}|$，即 $$\lambda_1 \approx \max_{1 \leq i \leq n} |x_i^{(k+1)}|=|x_j^{(k+1)}|$$ 相应的特征向量是$v_1 \approx Y^{(k)}$
• 如果$\lbrace X^{(2k)} \rbrace, \lbrace X^{(2k+1)} \rbrace$分别收敛于互为反号的向量，那么按模最大的特征值也仅有一个单实根，且$\lambda_1 <0$，即 $$\lambda_1 \approx -\max_{1 \leq i \leq n} |x_i^{(k)}|=-|x_j^{(k)}|$$ 相应的特征向量是$v_1 \approx Y^{(k)}$
• 如果$\lbrace X^{(2k)} \rbrace, \lbrace X^{(2k+1)} \rbrace$分别收敛于两个不同的向量，那么按模最大的特征值有两个，它们是互为反号的一对实根。再做一次非规范的运算$X^{(k+1)}=AX^{(k)}$，则有 $$\lambda_1 \approx \sqrt{x_i^{(k+1)}/y_i^{(k-1)}},\lambda_2=-\lambda_1$$ 特征向量分别为 $$\begin{cases} V_1=X^{(k+1)}+\lambda_1X^{(k)} \\ V_2=X^{(k+1)}-\lambda_1X^{(k)} \end{cases}$$
• 迭代序列没有一定的规律，需要另行讨论

通过原点位移的幂法可能会加速迭代。矩阵$B=A-pI$的特征值与矩阵$A$的特征值分别为$\lambda$与$\lambda-p$，通过计算矩阵$A-pI$的特征值得到矩阵$A$的特征值的方法称为原点位移法。

如果取得的$p$满足

$$\Big| \frac{\lambda_2-p}{\lambda_1-p} \Big| < \Big| \frac{\lambda_2}{\lambda_1} \Big|$$

那么对矩阵$B$的幂法，收敛会比$A$的幂法快。选取有效的$p$需要大致了解该矩阵的特征值分布。

反幂法

反幂法是计算按模最小特征值及其特征向量的数值方法。

不难证明，$A^{-1}$的按模最大特征值是$A$的按模最小特征值的倒数。使用幂法计算$A^{-1}$的按模最大特征值从而得到$A$的按模最小特征值的方法，称为反幂法。反幂法的规范迭代格式如下：

$$\begin{cases} Y^{(k)}=X^{(k)}/||X^{(k)}||_\infty \\ X^{(k+1)}=A^{-1}Y^{(k)} \end{cases}$$

在实务中，一般不会计算$A$的逆矩阵。而是求解线性方程组$AX^{(k+1)}=Y^{(k)}$，从而求得$X^{(k+1)}$，因此迭代格式可以改写如下：

$$\begin{cases} Y^{(k)}=X^{(k)}/||X^{(k)}||_\infty \\ AX^{(k+1)}=Y^{(k)} \end{cases}$$

如果想求解最接近$p$的特征值$\lambda_i$，那么可以用带原点位移的反幂法

$$\begin{cases} Y^{(k)}=X^{(k)}/||X^{(k)}||_\infty \\ (A-pI)X^{(k+1)}=Y^{(k)} \end{cases}$$

计算得到特征值$\mu$，那么$\lambda_i=p+\frac{1}{\mu}$，这是一个非常不错的性质。

QR方法初步

QR方法能够有效的计算中小型矩阵的特征值与特征向量。

对于n阶矩阵$Q$，若满足$QQ^T=I$，那么称$Q$为正交矩阵，具有如下性质：

• $|\det Q|=1$
• 若$Q_1,Q_2$为正交阵，那么$Q=Q_1Q_2$也是正交矩阵

如果A为n阶实矩阵，那么存在正交矩阵$Q$，上三角矩阵$R$，使得

$$A=QR$$

将$A$这样分解的过程被称为QR分解。

$A$为给定的n阶实矩阵，令$A_1=A$，对$A_1$作QR分解$A_1=Q_1R_1$。然后，对$A_2=R_1Q_1$作QR分解$A_2=Q_2R_2$，记$A_3=R_2Q_2$。一直进行下去，可以得到n阶矩阵序列$\lbrace A_k \rbrace$，满足：

• $\lbrace A_k \rbrace$为相似正交矩阵序列
• 记$A_k$的元素$(a_{ij}^{(k)})_{n \times n}$，若$A$满足一定的条件，则有 $$a_{ij}^{(k)} \to 0,k \to \infty, 1 \leq i < j \leq n$$ $$a_{ii}^{(k)} \to \lambda_i,k \to \infty,i=1,2, \cdots ,n$$ $\lambda_i$就是$A$的特征值。

利用矩阵的QR分解得到特征值的方法称为QR方法。有多种方法可以进行QR分解，例如施密特正交化与Householder变换。