Power Method

看一下費波那契數列

F_{n} = F_{n - 1} + F_{n - 2}

，這個數列長

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .}

，我們可以透過矩陣來重寫這個數列：

在這個例子裏面，我們觀察到 eigenvector、eigenvalue 跟長期的外顯行為有關。

看第二個例子，假設這邊有四個網頁，然後我們常像這樣去瀏覽她：

那麼就會有一個機率矩陣：

假設

A \in R^{n \times n}

有 dominant eigenvalue。給定 initial guess

\vec{x}

且製造一個數列長這樣：

我們希望這個數列能很好的幫助我們去逼近 dominant eigenvalue。

這裡我們可以看到 Power Method 會產生一個很大的數字在矩陣前方，這個數字可以透過歸一化之類的方法來消除掉，我們這邊透過 scale down 的方法來做一次，在每步迭代前都先除上自己 norm：

證明：