Power Method

Mes11/15/21About 1 min

看一下費波那契數列 $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：

證明：