35. Iterative Estimates for Eigenvalues¹

Dated: 18-06-2025

Eigenvalues¹ And Eigenvectors¹

\[AX = \lambda X\]

\[AX - \lambda X = 0\]

\[AX - \lambda IX = 0\]

\[(A-\lambda I)X = 0\]

To find the eigenvalues¹ we have to solve the equation

\[|A - \lambda I| = 0\]

Power Method

Let \(A\) be a diagonalizable matrix² with \(n\) linearly independent³ eigen vectors¹ \(\vec v_1, \ldots \vec v_n\) with corresponding eigen values¹ \(\lambda_1, \ldots, \lambda_n\) such that

\[|\lambda_1| > |\lambda_2| \ge \ldots \ge |\lambda_n|\]

Since \(\{\vec v_1, \ldots, \vec v_n\}\) is a basis for \(\mathbb R^n\), any vector⁴ \(\vec x\) can be written as

\[\vec x = c_1 \vec v_1 + c_2 \vec v_2 + \cdots + c_n \vec v_n\]

Multiply by \(A\) on both sides

\[Ax = A(c_1 v_1 + c_2 v_2 + \dots + c_n v_n)\]

\[= A(c_1 v_1) + A(c_2 v_2) + \dots + A(c_n v_n)\]

\[= c_1(Av_1) + c_2(Av_2) + \dots + c_n(Av_n)\]

\[= c_1(\lambda_1 v_1) + c_2(\lambda_2 v_2) + \dots + c_n(\lambda_n v_n)\]

Again, if we multiply by \(A\) on both sides, we get

\[A^2 x = c_1 (\lambda_1^2 v_1) + c_2 (\lambda_2^2 v_2) + \dots + c_n (\lambda_n^2 v_n)\]

Continuing this process, will give us

\[A^k x = c_1 (\lambda_1^k v_1) + c_2 (\lambda_2^k v_2) + \dots + c_n (\lambda_n^k v_n) \quad k \in \mathbb Z^+\]

\[\left(\frac{1}{\lambda_1}\right)^k A^k x = c_1 v_1 + c_2 \left(\frac{\lambda_2}{\lambda_1}\right)^k v_2 + \dots + c_n \left(\frac{\lambda_n}{\lambda_1}\right)^k v_n \quad k \in \mathbb Z^+\]

\[k \to \infty \implies (\lambda_1)^{-k} A^k x \to c_1 \vec v_1 \quad \because |\lambda_1| > |\lambda_2| \ge \ldots \ge |\lambda_n|\]

Procedure

Step 1

Choose the initial vector⁴ such that the largest element is unity.

Step 2

The normalized vector⁴ \(\vec v^{(0)}\) is pre multiplied by the matrix⁵ \(A\).

Step 3

The resultant vector⁴ is again normalized.

Step 4

This process of iteration is continued and the new normalized vector⁴ is repeatedly pre-multiplied by the matrix⁵ \(A\) until the required accuracy is obtained.

\[u^{(k)} = [A]\vec v^{(k -1)} = q_k \vec v^{(k)}\]

Here \(q_k\) is the desired largest eigen value¹ and \(\vec v^{(k)}\) is the corresponding eigen vector.¹

Steps for Finding the Eigenvalue¹ and the Eigenvector¹

1. Select an initial vector⁴ \(\vec x_0\) whose largest entry is \(1\).
2. For \(k \in \mathbb Z^+ \cup \{0\}\)
   1. Compute \(A_K\)
   2. Let \(\micro_k\) be an entry \(A x_k\) whose absolute value is as large as possible.
   3. Compute \(x_{k + 1} = \left(1 \micro_k\right) A x_k\)
3. For almost all choice of \(x_0\) the sequence \(\{\micro_k\}\) approaches the dominant eigen value¹ and sequence \(\{x_k\}\) approaches a dominant eigen vector.¹

Example

Find the first three iterations of the power method applied on the following matrices

\[ \begin{bmatrix} 1 & 1 & 0\\ 2 & 4 & 2\\ 0 & 1 & 2 \end{bmatrix} \text{ use } x_0 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \]

Solution

\(1^{st}\) Iteration

\[ u_1 = A x_0 = \begin{bmatrix} 1 & 1 & 0\\ 2 & 4 & 2\\ 0 & 1 & 2\\ \end{bmatrix} \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} = \begin{bmatrix} 0 + 0 + 0\\ 0 + 0 + 2\\ 0 + 0 + 2\\ \end{bmatrix} = \begin{bmatrix} 0\\ 2\\ 2 \end{bmatrix} \]

Now we normalize⁴ the resultant vector⁴ to get

\[ u_1 = \begin{bmatrix} 0 \\ 2 \\ 2 \\ \end{bmatrix} = 2 \begin{bmatrix} 0 \\ 1 \\ 1 \\ \end{bmatrix} = q_1 x_1 \]

\(2^{nd}\) Iteration

\[ u_2 = A x_1 = \begin{bmatrix} 1 & 1 & 0\\ 2 & 4 & 2\\ 0 & 1 & 2\\ \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 0 + 1 + 0\\ 0 + 4 + 2\\ 0 + 1 + 2\\ \end{bmatrix} = \begin{bmatrix} 1\\ 6\\ 3 \end{bmatrix} \]

Now we normalize⁴ the resultant vector⁴ to get

\[ u_2 = \begin{bmatrix} 1 \\ 6 \\ 3 \\ \end{bmatrix} = 6 \begin{bmatrix} \frac 1 6 \\ 1 \\ \frac 1 2 \\ \end{bmatrix} = q_2 x_2 \]

\(3^{rd}\) Iteration

\[ u_3 = A x_2 = \begin{bmatrix} 1 & 1 & 0\\ 2 & 4 & 2\\ 0 & 1 & 2\\ \end{bmatrix} \begin{bmatrix} \frac 1 6\\ 1\\ \frac 1 2 \end{bmatrix} = \begin{bmatrix} \frac 1 6 + 1 + 0\\ \frac 1 3 + 4 + 2\\ 0 + 1 + 2\\ \end{bmatrix} = \begin{bmatrix} \frac 7 {16}\\ \frac {16} 3\\ 2 \end{bmatrix} \]

Now we normalize⁴ the resultant vector⁴ to get

\[ u_3 = \begin{bmatrix} \frac 7 6 \\ \frac {16} 3 \\ 2 \\ \end{bmatrix} = \frac {16} 3 \begin{bmatrix} \frac 7 {32} \\ 1 \\ \frac 3 8 \\ \end{bmatrix} = q_3 x_3 \]

Hence the largest eigenvalue¹ after \(3\) iterations is \(\frac {16} 3\) .

The corresponding eigenvector¹ is

\[ \begin{bmatrix} \frac 7 {32} \\ 1 \\ \frac 7 8 \\ \end{bmatrix} \]

The Inverse Power Method

1. Select an initial estimate sufficiently close to \(\lambda\).
2. Select an initial vector⁴ \(\vec x_0\) whose large entry is \(1\).
3. For \(k \in \mathbb Z^+ \cup \{0\}\)
   1. Solve \((A - \alpha I)y_k = x_k\)
   2. Let \(\micro_k\) be an entry in \(y_k\) whose absolute value is as large as possible.
   3. Compute \(v_k = \alpha + \left(\frac 1 {\micro_k}\right)\)
   4. Compute \(x_{k + 1} = \left(\frac 1 {\micro_k}\right) y_k\)
4. For almost all the choice of \(x_0\), the sequence \(\{v_k\}\) approaches the eigenvalue¹ \(\lambda\) of \(A\), and the sequence \(\{x_k\}\) approaches a corresponding eigenvector.¹

References

Read more about notations and symbols.

---

1. Read more about eigen values and vectors. ↩↩↩↩↩↩↩↩↩↩↩↩↩↩↩↩

2. Read more about diagonalizable matrix. ↩

3. Read more about linear independency. ↩

4. Read more about vectors. ↩↩↩↩↩↩↩↩↩↩↩↩↩

5. Read more about matrices. ↩↩