Power method with Rayleigh Quotient

Power 迭代法目錄:

1. 基本概念

   Power iteration; inverse power method; shifted inver power method

2. 找第二大的 eigenvalue

   deflation

3. Rayleigh Quotient 迭代及其收斂性

   Power method with Rayleigh Quotient

假設

1. $A$ 是一個對稱矩陣

演算法: Power method with Rayleigh Quotient

Iterate until convergence: $$ \tag{1} \begin{align} \hat{x}^{(k+1)} &= Ax^{(k)}\\
\lambda^{(k+1)} &= x^{(k)T}\hat{x}^{(k+1)}\\
x^{(k+1)} &= \hat{x}^{(k+1)}/|\hat{x}^{(k+1)}|_2 \end{align} $$

收斂性證明

由於 $A$ 是個對稱矩陣, 因此存在一組 orthonormal 的 eigenvectors $\{v_1, \cdots, v_n\}$, 使得 $v_i^Tv_j=0$ if $i\ne j$, and $v_i^Tv_i=0$.

任意給定初始值 $x^{(0)}\ne 0$, 他可以被 eigenvectors 組出來, 因此我們有 $$ x^{(0)} = \alpha_1 v_1 + \sum^n_{i=2} \alpha_i v_i, $$ 並且 $$ \tag{2}A^kx^{(0)} = \lambda_1^k\left[\alpha_1 v_1 + \sum^n_{i=2} \alpha_i \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]. $$ 另一方面, 從迭代式 (1) 可以看出我們一直不斷地把得到的向量 normalize, 使其為單位長, 因此我們必定有 $$ x^{(k)} = \frac{A^kx^{(0)}}{|A^kx^{(0)}|_2}. $$ 將 (2) 代入得到 $$ \tag{3} \begin{align} x^{(k)} &= \frac{\lambda_1^k\left[\alpha_1v_1 + \sum^n_{i=2}\alpha_i \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]}{\sqrt{\lambda_1^{2k}\left[\alpha_1v_1 + \sum^n_{i=2}\alpha_i \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]^T\left[\alpha_1v_1 + \sum^n_{i=2}\alpha_i \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]}} \\
&= \frac{\left[\alpha_1v_1 + \sum^n_{i=2}\alpha_i \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]}{\sqrt{\alpha^2_1 + \sum^n_{i=2}\alpha^2_i \left(\frac{\lambda_i}{\lambda_1}\right)^{2k}}}\\
&=\frac{\left[v_1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right) \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]}{\sqrt{1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right)^2 \left(\frac{\lambda_i}{\lambda_1}\right)^{2k}}}, \end{align} $$ 其中我們用到了 $\{v_1, \cdots, v_n\}$ 是 orthonormal basis 這個事實.

接著我們可以算 eigenvalue, 將 (3) 代入: $$ \begin{align} \lambda^{(k+1)} &= x^{(k)T}\hat{x}^{(k+1)} = x^{(k)T}(Ax^{(k)}) \\
&= \frac{\left[v_1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right) \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]^T\left[\lambda_1v_1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right) \lambda_i\left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]}{1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right)^2 \left(\frac{\lambda_i}{\lambda_1}\right)^{2k}} \\
&= \lambda_1 \frac{\left[v_1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right) \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right]^T\left[v_1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right) \left(\frac{\lambda_i}{\lambda_1}\right)^{k+1}v_i\right]}{1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right)^2 \left(\frac{\lambda_i}{\lambda_1}\right)^{2k}} \\
&= \lambda_1 \frac{\left[1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right)^2 \left(\frac{\lambda_i}{\lambda_1}\right)^{2k+1}\right]}{1 + \sum^n_{i=2}\left(\frac{\alpha_i}{\alpha_1}\right)^2 \left(\frac{\lambda_i}{\lambda_1}\right)^{2k}} \\
&= \lambda_1 \frac{\left[1 + O \left(\epsilon^{2k+1}\right)\right]}{1 + O \left(\epsilon^{2k}\right)} \\
&= \lambda_1 + O\left(\epsilon^{2k}\right), \end{align} $$ where $\epsilon=|\lambda_2/\lambda_1|$.

因此這個迭代式, power method with Rayleigh quotient for symmetric matrix, 會是線性收斂, 並且其 rate of convergence 是 $\left(\frac{\lambda_2}{\lambda_1}\right)^2$.

Final remark

若使用基本的 power 迭代, 就是每次將得到得向量單位化, 如以下方式:

Pseudo code:

while diff > Tol
    v = A*u
    lambda = norm(v)
    u = v/lambda
end

如果 $A$ 是個對稱矩陣, 會發現這個迭代式其收斂性為 $\left(\frac{\lambda_2}{\lambda_1}\right)^2$.

這是因爲, 若 $Au=\lambda u$, $$ \|v\|_2 = \|Au\|_2 = \sqrt{(Au)^T(Au)} = |\lambda|. $$ 利用跟上面類似的推導手法即可證明收斂性為 $\left(\frac{\lambda_2}{\lambda_1}\right)^2$.