--- title: Power Method 講稿 tags: LA-Tea --- 什麼是 power method? 簡單來說就是一種計算特徵向量的方法。當我們計算得越多次，出來的答案就會越接近我們要找的特徵向量。 接下來我們來看，要使用 power method 需要有什麼條件... 注意最大的特徵值是唯一的。 --- 我們來仔細看看 power method 有哪些優缺點 首先它的優點： 他很簡潔，過程只有兩個步驟矩陣乘法然後縮短長度，計算所花費的時間很短。 不過他的缺點也很明顯， 只能找最大的特徵值對應的特徵向量 收斂速度取決於... --- 還有哪些找特徵向量的方法? 其實還有很多基於 power method 改良的方法像是 inverse power method . . . 那我麼這邊稍微講一下QR-iteration是怎麼做的，因為真的很神奇 --- 為什麼我們需要這些演算法? 有學過線性代數的應該都還記得，一般要求特徵向量的方法。我們要先假設特徵值為$\lambda$，然後去解特徵多項式的根，之後還要假設特徵向量的每一個元素$x, y, z, \dots$，很麻煩，總不能叫電腦去模擬以上的這些過程， 應該說電腦也能夠去模擬這些過程但是速度太慢，甚至解不出來。 因此有一個逼近的迭代的算法就顯得很重要，畢竟電腦最擅長的就是做這種單一、且要重複很多次的事情。 --- PageRank Algorithm 這是一個計算搜尋網頁優先程度的算法，是google最早、也是最有名的一個搜尋演算法。現在當然不止有這個算法。 在PageRank出現之前，或是說PageRank還沒廣泛應用之前，有些搜尋引擎會依照某個關鍵字出現的頻率，去排序網頁的優先順序。 這明顯不是一個好的方法 而PageRank排序的依據是各個網頁之間的連結 or 轉移到其他網頁的機率 來評價他的優先程度。 --- 就以這張圖為例，一個圈代表著一個網頁，每個網頁都會指向某些網頁 (解釋那個矩陣) 一開始我們給每一個網頁一樣的評分都是1/5，之後我們將這個向量乘上矩陣A，計算第一次投票的後的評分，之後再拿這個向量再做一次投票，也就是再乘一次矩陣A，就這樣一直乘直到投票結果收斂，也就是得到的向量乘上A之後不會改變時。 那我們就找到了這最終的投票結果。 --- 那可以發現其實這個過程和power method的原理其實是一樣的，我們要找的向量其實就是特徵直為1的那個特徵向量， 矩陣很大怎麼辦(sparse matrix可以更快計算) 從以上的例子和google的成功 線性代數有非常大的實質用處，希望同學們聽完這次的報告(present)能夠對線性代數有更大的興趣。 --- Question: 請舉出一個 power method 的限制