CS205A Lecture 7 Eigenproblems; Algorithms

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第七讲,这一讲主要介绍了计算特征值的方法。

首先回顾我们的问题条件:

幂迭代(Power Iteration)

注意到所有的特征向量张成$\mathbb R^n $,所以对于任意向量$\vec v$,我们有

因此

这里假设特征值互不相同,那么

所以当$k\to \infty $时,

于是产生如下算法:

幂迭代(power iteration)

  1. 选择$\vec v_1 \in \mathbb R^n$为任意非零向量。

  2. 迭代直至收敛:

显然,如果$|\lambda_1 |>1$,那么

这样就会产生计算问题。注意到对于特征向量,我们只在意其方向,所以产生了如下算法:

正规化幂迭代(normalized power iteration)

  1. 选择$\vec v_1 \in \mathbb R^n​$为任意非零向量。

  2. 迭代直至收敛:

注意,该算法返回模最大的特征值。

反向迭代(Inverse Iteration)

这里假设$A$可逆,那么如果

我们有

因此$A^{-1}$的特征值满足

所以利用上述事实找到$\frac 1 {\lambda_n }​$,即模最小的特征值,算法如下:

反向幂迭代(inverse power iteration)

  1. 选择$\vec v_1 \in \mathbb R^n$为任意非零向量。
  2. 迭代直至收敛:
    • 求解$\vec w_k​$:$A\vec w_k =\vec v_{k-1}​$
    • 正规化:$\vec v_k =\frac{\vec w_k }
      {\Arrowvert \vec w_k \Arrowvert}​$

利用$LU$分解,可以将提升上述算法的效率:

  1. 分解$A=LU$
  2. 选择$\vec v_1 \in \mathbb R^n​$为任意非零向量。
  3. 迭代直至收敛:
    • 用forward substitution求解$\vec y_k$:$L\vec y_k =\vec v_{k-1}$
    • 用back substitution求解$\vec w_k$:$U \vec w_k =\vec y_k$
    • 正规化:$\vec v_k =\frac{\vec w_k }{\Arrowvert \vec w_k \Arrowvert}$

注意,该算法返回模最小的特征值。

平移(Shifting)

首先回顾恒等式:

所以收敛速度主要由$\Big (\frac{\lambda_2} {\lambda_1}\Big )$控制,如果这个比值接近$1$,那么收敛速度会大大减慢,但是注意到我们有

所以我们可以计算$A-\sigma​$的特征值

如果

那么我们可以通过计算$A-\sigma​$的特征值来更快得到$A​$的特征值,但由于$\lambda_i ​$未知,所以$\sigma​$的选择很困难。

接着用来另一种角度看待特征值问题,实际上我们是在找$\lambda ​$,使得

所以对于$\vec v_0$,我们去猜测$\vec v_0​$对应的特征值,即找到

那么求梯度并令其为$0​$可得

上述量被称为瑞利商(Rayleigh quotient),有了这个量,我们可以认为$A-\lambda I_n​$的最小特征值接近于$0​$,于是用反幂法可以高效求解该特征值,于是产生了如下算法:

瑞利商迭代(Rayleigh quotient iteration)

  1. 选择$\vec v_1 \in \mathbb R^n$为任意非零向量或者猜测一个特征向量。

  2. 迭代直至收敛:

    • 计算对当且特征值的估计:

    • 求解$\vec w_k$:$(A-\sigma_k I_n) \vec w_k =\vec v_{k-1}$

    • 正规化:$\vec v_k =\frac{\vec w_k}{\Arrowvert \vec w_k \Arrowvert}​$

注意上述方法有一个缺点,因为$A-\sigma_k I_n$会改变,所以无法使用$LU$分解提升运行速度。

找到多个特征值

之前的算法都是介绍如何找到一个特征值,但是实际问题中往往要求解多个特征值,这一部分将介绍这点。

收缩法(Deflation)

考虑power iteration的过程,假设$\lambda_1 ​$为模最大的特征值,其对应的特征向量为$\vec x_1​$,选择的初值为$\vec v​$,注意到

如果

那么

所以

因此无论迭代多少次,都无法求出$\lambda_1 ​$,但是可以求出$\lambda_2​$,这就提醒我们可以通过投影的方法逐步求出每个特征值,于是产生如下算法:

  • 对$l=1,2,…$

    • 选择$\vec v_1 \in \mathbb R^n$为任意非零向量。

    • 迭代直至收敛:

      • 减去特征值上的投影:

      • 计算$\vec w_k =A\vec u_k$

      • 正规化:$\vec v_k =\frac{\vec w_k}{\Arrowvert \vec w_k \Arrowvert}$

    • 将迭代的结果加入$\vec x_i$的集合中。

注意到如果$A$非对称,那么其特征向量不正交,上述算法会失效,此时就要使用别的算法。

现在假设

记$H$是Householder矩阵,使得

注意到相似变换不会影响特征值,而$H$是对称正交矩阵,所以我们考虑

右乘$\vec e_1​$,可得

所以$HAH^T \vec e_1​$的第一列是$\lambda_1 \vec e_1 ​$,即

其中$B\in \mathbb R^{(n-1)\times (n-1)}$并且其特征值为$\lambda_2,…,\lambda_n$,所以可以对$B$使用power iteration,但算法依然是一次只计算一个特征值,后续将介绍如何一次计算多个特征值的算法。

$QR$迭代

依然利用相似矩阵不改变特征值,特别地,取相似矩阵为正交阵,那么

那么该选择什么样的$Q$呢?考虑$QR$分解:

那么

这就产生如下算法:

  1. 选择$A_1= A$
  2. 对$k=1,2,…$
    • 分解$A_k =Q_kR_k$
    • 令$A_{k+1}=R_k Q_k$

由之前的推导可得$A_k$的特征值和$A$相同,如果上述算法收敛,那么

所以

为方便讨论,这里假设$A_{\infty }$和$Q_{\infty }$各自的特征值互不相同。

现在任取$Q_{\infty }$的特征值$\lambda $以及对应的特征向量$\vec x​$,我们有

如果

那么$\vec x​$是矩阵$A_{\infty}​$属于特征值$0​$的特征向量。

如果

$A_{\infty}\vec x$是矩阵$R_{\infty}$属于$\lambda$的特征向量,即

无论哪种情形,都有$\vec x ​$是$A_{\infty}​$的特征向量,所以$R_{\infty }​$的特征向量都是$A_{\infty }​$的特征向量,同理可得$A_{\infty }​$的特征向量都是$R_{\infty }​$的特征向量,即两者的特征向量相同。

现在任取$Q_{\infty }$的特征向量$\vec x$,由正交性可得

我们取$+1$对应的特征向量,所以

假设该向量对应于$A$的特征值为$\lambda$,即

因此

所以$R_{\infty}$的特征值和$A_{\infty }$的特征值相同,注意到$R_{\infty } $为上三角矩阵,所以其特征值为对角线元素,因此我们只要计算$R_{\infty } $的对角元即可。

本文标题:CS205A Lecture 7 Eigenproblems; Algorithms

文章作者:Doraemonzzz

发布时间:2019年03月31日 - 00:26:00

最后更新:2019年04月03日 - 01:09:18

原始链接:http://doraemonzzz.com/2019/03/31/CS205A Lecture 7 Eigenproblems II; Algorithms/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。