<style> *{ /*transition: 1s;*/ } </style> ### Power Method ##### - approximating eigenvalues by iterating --- #### ● What is Power Method? ---- A way to approch a **eigenvector**  ▲ green vector try to approch blue eigenvector ---- $A \in \mathbb{R}^{n\times n}$ ,is **diagnalizable** and the **eigenvalue** of $A$ should be $$\lambda_1 > \lambda_2 \geq \lambda_3 \geq \dots \geq \lambda_n$$ ---- pick a random $\vec{x_0} \in \mathbb{R}^n$ and we do $\vec{x_{i+1}} = \frac{A\vec{x_i}}{|A\vec{x_i}|}$ $\vdots$ when the number of iteration is large $\vec{x_i}$ would converge to a **eigenvector** corresponding to the $\lambda_1$ --- #### ● Why it works? ---- for $A$ is **diagnalizable** the **eigenvectors** of $A$ $\{\vec{v_1}, \vec{v_2}, \dots ,\vec{v_n}\}$ forms a **basis** of $\mathbb{R}^n$ so the random vector $\vec{x_0}$ can be represent as $$\vec{x_0} = c_1\vec{v_1} + c_2\vec{v_2} + \dots + c_n\vec{v_n}$$ ---- what about $\vec{x_0} \in span(\{\vec{v_2}, \vec{v_3},\dots,\vec{v_n}\})$ ? ---- $$\begin{aligned} A\vec{x_0} &= A(c_1\vec{v_1} + c_2\vec{v_2} + \dots + c_n\vec{v_n})\\ &= c_1A\vec{v_1} + c_2A\vec{v_2} + \dots + c_nA\vec{v_n}\\ &=c_1\lambda_1\vec{v_1} + c_2\lambda_2\vec{v_2} + \dots + c_n\lambda_n\vec{v_n} \end{aligned}$$ $$ A^2\vec{x_0} = c_1\lambda_1^2\vec{v_1} + c_2\lambda_2^2\vec{v_2} + \dots + c_n\lambda_n^2\vec{v_n}\\ \vdots $$ $$ A^i\vec{x_0} = c_1\lambda_1^i\vec{v_1} + c_2\lambda_2^i\vec{v_2} + \dots + c_n\lambda_n^i\vec{v_n} $$ ---- $$\begin{aligned} A^i\vec{x_0} &= c_1\lambda_1^i\vec{v_1} + c_2\lambda_2^i\vec{v_2} + \dots + c_n\lambda_n^i\vec{v_n}\\ &=\lambda_1^i[c_1\vec{v_1} + c_2(\frac{\lambda_2}{\lambda_1})^i\vec{v_2} + \dots + c_n(\frac{\lambda_n}{\lambda_1})^i\vec{v_n}] \end{aligned}$$ it converges to $\lambda^i_1c_1\vec{v_1}$ --- #### ● The advantage of it ---- -- Simple -- Fast --- #### ● The disadvantage of it ---- -- Too many restrictions --- #### ● Other method to get the eigenvector ---- - Inverse power method - Power method with shift - Inverse power method with shift - QR-iteration . . . ---- the **QR-iteration** ---- $A \in \mathbb{R}^{n\times n}$ just keep doing **QR-decomposition** to $A$ $$\begin{aligned} A &= Q_1R_1\\ A_1 &= R_1Q_1 \end{aligned}$$ $$\begin{aligned} A_1 &= Q_2R_2\\ A_2 &= R_2Q_2 \end{aligned}\\ \vdots$$ ---- we collect the $Q_i$s during the process when the number of iteration getting large $Q_iQ_{i-1}\cdots Q_2Q_1 = \begin{bmatrix} | & | & & | \\ \vec{v_1} & \vec{v_2} & \cdots & \vec{v_n}\\ | & | & & | \\ \end{bmatrix}$ where the $\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}$ , are the eigenvectors of $A$ ---- Moreover，when the $i$ is getting large $A$ will converge to $\begin{bmatrix} \lambda_1 & & & &\\ & \lambda_2 & & &\\ & & \ddots & &\\ & & & & \lambda_n\\ \end{bmatrix}$ where $\lambda_1, \lambda_2, \dots, \lambda_n$ are the eigenvalues of $A$. --- #### ● Why we needs these algorithms？ --- #### ● What can we use the eigenvector do？ ---- -- diagnalize -- solve systems of difference equations . . . --- #### ● The Google PageRank Algorithm ---- before PageRank Algorithm, some search engine find the "best" website by the frequence of some keywords ----  ---- PageRank Algorithm find the "best" website by the "linkage" between every websites  ---- matrix represent of this network | | | | -------- | -------- | | | $\begin{bmatrix}0 & 1 & \frac{1}{3} & \frac{1}{3} & 1\\\frac{1}{2} & 0 & \frac{1}{3} & \frac{1}{3} & 0\\ 0 & 0 & 0 & \frac{1}{3} & 0\\\frac{1}{2} & 0 & 0 & 0 & 0\\0 & 0 & \frac{1}{3} & 0 & 0\end{bmatrix}$| ---- $\begin{bmatrix} 0 & 1 & \frac{1}{3} & \frac{1}{3} & 1\\ \frac{1}{2} & 0 & \frac{1}{3} & \frac{1}{3} & 0\\ 0 & 0 & 0 & \frac{1}{3} & 0\\ \frac{1}{2} & 0 & 0 & 0 & 0\\ 0 & 0 & \frac{1}{3} & 0 & 0 \end{bmatrix} \begin{bmatrix} |\\ \vec{v}\\ |\\ \end{bmatrix}= \begin{bmatrix} |\\ \vec{v}\\ |\\ \end{bmatrix}$ ---- $\begin{bmatrix} |\\ \vec{v}\\ |\\ \end{bmatrix}= \begin{bmatrix} ?\\ ?\\ \vdots\\ ?\\ \end{bmatrix}$ --- #### ● Summary