Module 11: Eigenworld

11.1   The power method

Iterative application of \({\bf A}\):

• We saw earlier that iterative multiplication leads to convergence to one of the eigenvectors.

• We will see momentarily why this works, and to which eigenvector.

• Suppose \({\bf A}\) has eigenvectors \({\bf x}_1, {\bf x}_2, \ldots, {\bf x}_n\) with associated eigenvalues \(\lambda_1, \lambda_2, \ldots, \lambda_n\).
  • \(\lambda_i\) is the eigenvalue for \({\bf x}_i\).
  • In other words: \({\bf Ax}_i=\lambda_i {\bf x}_i\).

• Suppose also that $$ |\lambda_1| \geq |\lambda_2| \geq \ldots \geq |\lambda_n| $$ If not, we'll re-label the eigenvectors (that's our choice) so that it's true.

• Example:
  • We saw earlier that $$ {\bf A} \eql \mat{5 & -2\\ 0 & 1} $$ has two eigenvectors \((1,2)\) and \((1,0)\) with eigenvalues \(1\) and \(5\).
  • Here, we would label $$\eqb{ {\bf x}_1 & \eql & \vectwo{1}{0}\\ {\bf x}_2 & \eql & \vectwo{1}{2} }$$ with $$\eqb{ \lambda_1 & \eql & 5\\ \lambda_2 & \eql & 1\\ }$$

• It will turn out that iterative multiplication will lead to the eigenvector with the largest eigenvalue \(\lambda_1\).

• Recall our algorithm:

      u = some initial vector
      for k=0 ...
         v = A u
         u = v / |v|
      endfor
    

• Or, mathematically, $$\eqb{ {\bf u}^{(0)} & \eql & \mbox{ some initial vector }\\ {\bf v}^{(k)} & \eql & {\bf A} {\bf u}^{(k-1)} \\ {\bf u}^{(k)} & \eql & \frac{1}{|{\bf v}^{(k)}|} {\bf v}^{(k)} }$$

• Consider a few iterations with this example:
  • Suppose we start with $$ {\bf A} \eql \mat{5 & -2\\ 0 & 1} \;\;\;\;\;\;\; {\bf u}^{(0)} \eql (1,1) $$
  • After one iteration: $$\eqb{ {\bf v}^{(1)} & \eql & {\bf A}{\bf u}^{(0)} & \eql & (3,1)\\ {\bf u}^{(1)} & \eql & \frac{1}{|{\bf v}^{(1)}|} {\bf v}^{(1)} & \eql & (0.949,0.316)\\ }$$
  • Then, the second iteration: $$\eqb{ {\bf v}^{(2)} & \eql & {\bf A}{\bf u}^{(1)} & \eql & (4.111,0.316)\\ {\bf u}^{(2)} & \eql & \frac{1}{|{\bf v}^{(2)}|} {\bf v}^{(2)} & \eql & (0.997,0.077)\\ }$$
  • Thus, we can see rapid convergence towards the eigenvector \((1,0\) in just a few iterations:

    

• Let's now analyze the iterations:
  • Recall the first iteration: $$\eqb{ {\bf v}^{(1)} & \eql & {\bf A} {\bf u}^{(0)} \\ {\bf u}^{(1)} & \eql & \frac{1}{|{\bf v}^{(1)}|} {\bf v}^{(1)} }$$
  • Second iteration: $$\eqb{ {\bf v}^{(2)} & \eql & {\bf A} {\bf u}^{(1)} \\ {\bf u}^{(2)} & \eql & \frac{1}{|{\bf v}^{(2)}|} {\bf v}^{(2)} }$$
  • Let's substitute for \({\bf u}^{(1)}\) from the first iteration: $$\eqb{ {\bf v}^{(2)} & \eql & {\bf A} \frac{1}{|{\bf v}^{(1)}|} {\bf v}^{(1)} \\ {\bf u}^{(2)} & \eql & \frac{{\bf A} {\bf A} {\bf u}^{(0)}}{ |{\bf v}^{(2)}| |{\bf v}^{(1)}|} }$$
  • Thus, \({\bf u}^{(3)}\) will have three multiplications of \({\bf A}\): $$\eqb{ {\bf u}^{(3)} & \eql & \frac{{\bf A}^3 {\bf u}^{(0)}}{ |{\bf v}^{(3)}||{\bf v}^{(2)}| |{\bf v}^{(1)}|} }$$

• Continuing, $$\eqb{ {\bf u}^{(k)} & \eql & \frac{{\bf A}^k {\bf u}^{(0)}}{ |{\bf v}^{(k)}|\ldots |{\bf v}^{(2)}| |{\bf v}^{(1)}|} }$$

• To simplify the expression, let's define $$ \nu_k \eql |{\bf v}^{(k)}|\ldots |{\bf v}^{(2)}| |{\bf v}^{(1)}| $$

• Then, $$ {\bf u}^{(k)} \eql \frac{1}{\nu_k}{\bf A}^k {\bf u}^{(0)} $$

• Next, suppose that \({\bf u}^{(0)}\) can be expressed as a linear combination of the eigenvectors: $$ {\bf u}^{(0)} \eql c_1 {\bf x}_1 + c_2 {\bf x}_2 + \ldots + c_n {\bf x}_n $$

• Let's substitute in the expression for \({\bf u}^{(k)}\): $$\eqb{ {\bf u}^{(k)} & \eql & \frac{1}{\nu_k}{\bf A}^k {\bf u}^{(0)} \\ & \eql & \frac{1}{\nu_k}{\bf A}^k (c_1 {\bf x}_1 + c_2 {\bf x}_2 + \ldots + c_n {\bf x}_n) \\ & \eql & \frac{1}{\nu_k} (c_1 {\bf A}^k {\bf x}_1 + c_2 {\bf A}^k {\bf x}_2 + \ldots + c_n {\bf A}^k{\bf x}_n) \\ }$$

• But for any eigenvector \({\bf x}_i\): $$ {\bf A}^k {\bf x}_i \eql \lambda_i^k {\bf x}_i $$

  In-Class Exercise 7: Show that this is true.

• Thus, substituting in the expression we derived for \({\bf u}^{(k)}\): $$\eqb{ {\bf u}^{(k)} & \eql & \frac{1}{\nu_k} (c_1 {\bf A}^k {\bf x}_1 + c_2 {\bf A}^k {\bf x}_2 + \ldots + c_n {\bf A}^k{\bf x}_n) \\ & \eql & \frac{1}{\nu_k} (c_1 \lambda_1^k {\bf x}_1 + c_2 \lambda_2^k {\bf x}_2 + \ldots + c_n \lambda_n^k{\bf x}_n) \\ & \eql & \frac{\lambda_1^k}{\nu_k} (c_1 {\bf x}_1 + c_2 (\frac{\lambda_2}{\lambda_1})^k {\bf x}_2 + \ldots + c_n (\frac{\lambda_n}{\lambda_1})^k{\bf x}_n) \\ }$$ where we've divided by \(\lambda_1^k\).

• Now consider what happens as \(k\rightarrow\infty\).

• First, notice that $$ (\frac{\lambda_i}{\lambda_1})^k \;\rightarrow \; 0 $$ for any \(i\neq 1\).

  In-Class Exercise 8: Why is this true?

• This means that $$ \lim_{k\rightarrow\infty} {\bf u}^{(k)} \eql \frac{c_1\lambda_1^k}{\nu_k} {\bf x}_1 $$

• That is, \({\bf u}^{(k)}\) converges to the direction of the eigenvector \({\bf x}_1\)

• By design (normalization) $$ |{\bf u}^{(k)}| \eql 1 $$ and so $$ \lim_{k\rightarrow\infty} {\bf u}^{(k)} \eql \alpha {\bf x}_1 $$ for some constant \(\alpha\).

• What we've shown is that the iterative process yields the eigenvector with the largest eigenvalue.

• We can also recover the eigenvalue corresponding to that eigenvector:
  • Suppose \({\bf x}\) is an eigenvector of \({\bf A}\): $$ {\bf Ax} \eql \lambda {\bf x} $$
  • Then, $$ {\bf Ax}\cdot {\bf x} \eql \lambda {\bf x} \cdot {\bf x} $$
  • And so, $$ \lambda \eql \frac{{\bf Ax}\cdot {\bf x}}{{\bf x} \cdot {\bf x}} $$

• In pseudocode:

      Algorithm: powerMethod (A)
      Input:  a matrix A
      1.   u = some initial vector
      2.   for k=0 ...
      3.      v = A u
      4.      u = v / |v|
      5.   endfor
      6.   λ = (A u · u) / (u · u) 
      7.   return λ, u