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$.


Avatar
Te-Sheng Lin (林得勝)
Associate Professor

The focus of my research is concerned with the development of analytical and computational tools, and further to communicate with scientists from other disciplines to solve engineering problems in practice.