Power method

Power 迭代法目錄:

1. 基本概念

   Power iteration; inverse power method; shifted inver power method

2. 找第二大的 eigenvalue

   deflation

3. Rayleigh Quotient 迭代及其收斂性

   Power method with Rayleigh Quotient

基本 Power method

求一個方陣最大(in magnitude) 的 eigenvalue.

給定 $A$ 為一個 $n\times n$ 方陣. 我們做以下兩個假設

1. 它的 eigenvalues 滿足 $$ |\lambda_1| > |\lambda_2| \ge |\lambda_3| \cdots |\lambda_n|. $$
2. 相對應的 eigenvectors, $\{v_1, , v_2, , \cdots, v_n\}$, 會構成 $R^n$ 的一組基底.

則若我們任意取一個 $n\times 1$ 向量 $u$, 它能被寫成 (根據假設 2) $$ u =\sum^{n}_{i=1} c_iv_i. $$

我們將兩邊乘以 $A$ 得到

$$ Au = \sum^{n}_{i=1} c_i\lambda_i v_i, $$

並且如果我們一直乘以 $A$, 共乘 $k$ 次, 則有 $$ \tag{1} A^ku =\sum^{n}_{i=1} c_i\lambda^k_i v_i. $$

因為 $|\lambda_1|$ 比其他的都大 (根據假設 1), 我們可以得到當 $k$ 夠大時 $$ \tag{2} \frac{1}{\lambda^k_1}A^ku = c_1 v_1 + \sum^{n}_{i=2} c_i\left(\frac{\lambda_i}{\lambda_1}\right)^k v_i \to c_1 v_1. $$

因此我們知道, 如果我們一開始隨機選取一個向量, 並且將之以 $A$ 矩陣一直乘它, 乘出來的這個向量應該會越來越接近第一個 eigenvector, 藉此我們也可以得到最大的 eigenvalue.

另外我們也知道, 收斂速度 (rate of convergence) 會是 $\frac{\lambda_2}{\lambda_1}$.

Remark:

1. 可以看到 (2) 式有個特別的地方是等號左邊我們把他除以 $\lambda^k_1$, 這樣等號右邊就會趨近於 $c_1v_1$.
2. 如果真的照 (1) 式的做法, 任意取一個 $u$ 然後矩陣一直乘會發生什麼事呢?

   如果 $\lambda>1$ 那 $\lambda^k\to\infty$, 如果 $\lambda<1$ 那 $\lambda^k\to 0$.

3. 因此, 實際執行 (1) 是不可行的. 而 (2) 也不可行, 因為 $\lambda_1$ 就是我們要找的東西, 所以無法除以 $\lambda_1^k$.
4. 實際執行 power iteration 時, 會將每次迭代所得到的向量 normalize, 這樣就可以避免爆掉或趨近於零的狀況. 而最簡單的 normalization 就是讓每次得到的向量為單位長.

作法:

Input: A Output: (取絕對值後)最大的 eigenvalue $\lambda_1$ 以及 $v_1$

1. 隨機選取一個向量 $u$, 並使 $\|u\|=1$
2. 計算 $v = Au$, 並令 $\lambda=\|v\|$
3. 另 $u=v/\lambda$ 並重複步驟 2 直到 $\lambda$ 收斂為止

Pseudo code:

Input: matrix A
Output: lambda1, u

u = random(size(A,1),1)
u = u/norm(u)

Tol=10**(-10)
max_iter = 1000

lambda0=1
diff=1

iter=0

while diff > Tol
    v = A*u
    lambda1 = norm(v)
    u = v/lambda1
    
    diff = abs(lambda1-lambda0)    
    lambda0 = lambda1
    
    iter =iter+1
    if iter > max_iter || diff < Tol
        break
    end
end

Note: 不過這樣得到的 lambda1 會是 $|\lambda_1|$, 要拿到 $\lambda_1$ 需要再乘一次矩陣.

事實上我們的目標只是不要讓向量爆掉或趨近於零, 所以可以簡單的把某個位置的值固定住, 比如說我們強迫 $v_1$ 的第一個位置等於 $1$, 這樣就沒問題了.

Pseudo code:

while diff > Tol
    v = A*u
    lambda1 = v(1)
    u = v/lambda1
end

Remark:

1. 當然, 如果 $v_1$ 這個 eigenvector 本來他第一個位置就是 $0$ 那這招就不行了. 不過我們可以固定其他位置啊!
2. 理論上, 由於 $v_1$ 不是零向量, 因此一定有個位置非零, 可以被固定住. 不過通常就隨機選個位置固定住就好.
3. 這樣做的好處有兩個: a. 取向量某一個位置的值遠比算向量的 norm 要快很多. b. 這樣拿到的 eigenvalue 就是 $\lambda_1$, 沒有絕對值.

若要找第二大的 eigenvalue 可以利用 deflation: Power method with deflation.

Inverse power method

求一個方陣最小(in magnitude) 的 eigenvalue.

Observation:

如果 $\lambda$ 滿足 $Av = \lambda v$, 則 $A^{-1}v = \frac{1}{\lambda} v$.

因此, 如果我們想要找一個矩陣 $A$ 它(絕對值)最小的 eigenvalue, $\lambda_n$, 那我們就需要對 $A^{-1}$ 做 power method. 也就是計算 $(A^{-1})^k u$. 這樣我們可以找到 $\frac{1}{\lambda_n}$, 將之反過來就得到最小的 eigenvalue.

這裡需注意兩件事:

1. 必須先確定最小的 eigenvalue 不是 $0$, 也就是這矩陣 non-singular, 不然 inverse power method 也無法做.
2. $A^{-1}u$ 是解線性系統, 不是乘以 $A^{-1}$ 矩陣.

Inverse power method 的 rate of convergence 是 $\frac{\lambda_{n}}{\lambda_{n-1}}$.

Shift-inverse power method

求一個方陣最靠近某個數字 $c$ 的 eigenvalue.

Observation:

如果 $\lambda$ 滿足 $Av = \lambda v$, 則 $(A-cI)v = (\lambda-c) v$. 因此 $$ (A-cI)^{-1}v = \frac{1}{\lambda-c} v. $$ 也就是說, $(A-cI)^{-1}$ 這矩陣最大的 eigenvalue, 會是使得 $\frac{1}{\lambda-c}$ 最大的那個, 我們可以據此反推 $A$ 矩陣其最靠近 $c$ 的那個 eigenvalue.

因此, 若我們想要找矩陣 $A$ 它最靠近某個數字 $c$ 的 eigenvalue, 那我們就需要對 $(A-cI)^{-1}$ 做 power method. 也就是計算 $((A-cI)^{-1})^k u$.