# Computing Eigenvalues

### Big Idea
For large matrices, finding eigenvalues by calculating the roots of the characteristic polynomial ($C_A(x) = \det(A - xI)$) is *impractical* because no general analytical solution exists for polynomials of degree five or higher. Instead, we use efficient *numerical algorithms*, such as the *power method* and *inverse iteration*, to approximate eigenvalues.

## Power Method
The *power method* is a numerical technique used to find the *dominant eigenvalue* $\lambda_1$ and its corresponding eigenvector $\mathbf{v}_1$.

:::info
**Definition** Let $A$ be a square matrix. An eigenvalue $\lambda$ of $A$ is called a **dominant eigenvalue** if $\lambda$ has (algebraic) multiplicity 1 and $| \lambda | > | \mu |$ for all other eigenvalues $\mu$.
:::

:::danger
**Theorem** If $\lambda_1$ is the dominant eigenvalue and the initial vector $\mathbf{x}_0$ has a nonzero component in the direction of $\mathbf{v}_1$, the sequence $A^k \mathbf{x}_0$ will converge toward a multiple of the dominant eigenvector $\mathbf{v}_1$ as $k \to \infty$.
:::

### Normalized Power Iteration
:::info
**Algorithm (Normalized Power Iteration)**
Let $\mathbf{x}_0$ be the first approximation to a dominant eigenvector. Define
$$
\mathbf{x}_{k+1} := \frac{A \mathbf{x}_k}{\|A \mathbf{x}_k\|}, \quad k > 0
$$

Then
$$
\langle \mathbf{x}_k, A \mathbf{x}_k \rangle \to \lambda_1, \quad \mathbf{x}_k \to \mathbf{v}_1\quad \text{as } k \to \infty
$$

where $\mathbf{v}_1$ is the dominant eigenvector.
:::

:::warning
**Example (Normalized Power Iteration)**
Let $A = \begin{bmatrix} 1 & 1 \\ 2 & 0 \end{bmatrix}$ and the initial vector be $\mathbf{x}_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$.

* The exact eigenpairs of $A$ are: $$\lambda_1 = 2, \quad \mathbf{v}_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \quad \text{(Dominant)} \quad \text{and} \quad \lambda_2 = -1, \quad \mathbf{v}_2 = \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ -2 \end{bmatrix}$$ Since $|\lambda_1| = 2 > |\lambda_2| = 1$, $\lambda_1$ is the dominant eigenvalue, and the power method should converge to $\mathbf{v}_1$.
* **Power Iteration Steps:** We apply the recursive formula $\mathbf{x}_{k+1} := \frac{A \mathbf{x}_k}{\|A \mathbf{x}_k\|}$:
* $k=0$: $\mathbf{x}_1 = \frac{A \mathbf{x}_0}{\|A \mathbf{x}_0\|} = \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ 2 \end{bmatrix}$
* $k=1$: $\mathbf{x}_2 = \frac{A \mathbf{x}_1}{\|A \mathbf{x}_1\|} = \frac{1}{\sqrt{13}} \begin{bmatrix} 3 \\ 2 \end{bmatrix}$
* $k=2$: $\mathbf{x}_3 = \frac{A \mathbf{x}_2}{\|A \mathbf{x}_2\|} = \frac{1}{\sqrt{61}} \begin{bmatrix} 5 \\ 6 \end{bmatrix}$
* **Approximation and Convergence:** After 3 steps, the approximations are:$$\mathbf{v}_1 \approx \mathbf{x}_3 = \frac{1}{\sqrt{61}} \begin{bmatrix} 5 \\ 6 \end{bmatrix} \quad \text{and} \quad \lambda_1 \approx \langle \mathbf{x}_3, A \mathbf{x}_3 \rangle = \frac{115}{61} \approx 1.885$$
* The initial vector $\mathbf{x}_0$ is expressed as a linear combination of the eigenvectors:$$\mathbf{x}_0 = c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2$$ Applying the matrix $A^k$ separates the terms:$$\begin{align*} A^k \mathbf{x}_0 &= c_1 \lambda_1^k \mathbf{v}_1 + c_2 \lambda_2^k \mathbf{v}_2 \\ &= c_1 2^k \mathbf{v}_1 + c_2 (-1)^k \mathbf{v}_2 \end{align*}$$ As $k \to \infty$, the first term dominates because $|2^k|$ grows faster than $|(-1)^k|$. Therefore, the normalized sequence converges to the dominant eigenvector:$$\lim_{k \to \infty} \frac{A^k \mathbf{x}_0}{\|A^k \mathbf{x}_0\|} = \mathbf{v}_1$$
:::

### Rayleigh Quotient
If $\mathbf{x}$ is an exact eigenvector of $A$ with eigenvalue $\lambda$, then $\mathbf{x}^T A \mathbf{x} = \lambda (\mathbf{x}^T \mathbf{x})$. This allows us to define the *Rayleigh quotient*:
$$
\frac{\mathbf{x}^T A \mathbf{x}}{ \mathbf{x}^T \mathbf{x} }
$$

:::info
**Algorithm**
Let $\mathbf{x}_0$ be the first approximation to a dominant eigenvector. Then
$$
\lambda_k = \frac{\mathbf{x}_k^T A \mathbf{x}_k}{ \mathbf{x}_k^T \mathbf{x}_k }
$$

converges to the dominant eigenvalue $\lambda$.
:::

## Inverse Iteration
The *inverse iteration* method is a variation of the power method used to find eigenvalues other than the dominant one.

:::info
**Definition**
The smallest eigenvalue of $A$ (in magnitude) corresponds to the largest eigenvalue of the inverse matrix, $A^{-1}$. Therefore, applying the *power method* to $A^{-1}$ finds the smallest eigenvalue of $A$. At each step, this requires solving a system and normalizing:
$$
A \mathbf{y}_{k+1} = \mathbf{x}_k \quad \implies \quad \mathbf{x}_{k+1} = \frac{\mathbf{y}_{k+1}}{\| \mathbf{y}_{k+1} \|_{\infty}}
$$
:::

:::warning
**Example**
Use inverse iteration to approximate the smallest eigenvalue and its corresponding eigenvector for the matrix $A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}$, starting with $\mathbf{x}_0 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$.

* The inverse iteration finds the eigenvector corresponding to the eigenvalue closest to zero (the smallest in magnitude) by applying the power method to $A^{-1}$. Instead of computing $A^{-1}$, we solve $A\mathbf{y}_{k+1} = \mathbf{x}_k$ at each step using the LU decomposition of $A$:$$A = LU = \begin{bmatrix} 1 & 0 \\ \frac{1}{3} & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 0 & \frac{8}{3} \end{bmatrix}$$
* **Iteration 1 ($k=0$):** Solve $A\mathbf{y}_1 = \mathbf{x}_0$. This is equivalent to solving $L\mathbf{z} = \mathbf{x}_0$ and then $U\mathbf{y}_1 = \mathbf{z}$. The operation $L^{-1}\mathbf{x}_0$ is performed by premultiplying $\mathbf{x}_0$ by the lower triangular inverse $L^{-1} = \begin{bmatrix} 1 & 0 \\ -\frac{1}{3} & 1 \end{bmatrix}$: $$\begin{aligned}
U\mathbf{y}_1 &= L^{-1}\mathbf{x}_0 \\
\begin{bmatrix} 3 & 1 \\ 0 & \frac{8}{3} \end{bmatrix} \mathbf{y}_1 &= \begin{bmatrix} 1 & 0 \\ -\frac{1}{3} & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}
\end{aligned}$$ Backward substitution yields $\mathbf{y}_1 = \begin{bmatrix} -\frac{1}{8} \\ \frac{3}{8} \end{bmatrix}$. Normalize using the maximum norm, $\|\mathbf{y}_1\|_\infty = \frac{3}{8}$: $$\mathbf{x}_1 = \frac{\mathbf{y}_1}{\|\mathbf{y}_1\|_\infty} = \begin{bmatrix} -\frac{1}{3} \\ 1 \end{bmatrix}$$
* **Iteration 2 ($k=1$):** Solve $A\mathbf{y}_2 = \mathbf{x}_1$. $$\begin{aligned}
\begin{bmatrix} 3 & 1 \\ 0 & \frac{8}{3} \end{bmatrix} \mathbf{y}_2 &= \begin{bmatrix} 1 & 0 \\ -\frac{1}{3} & 1 \end{bmatrix} \begin{bmatrix} -\frac{1}{3} \\ 1 \end{bmatrix} = \begin{bmatrix} -\frac{1}{3} \\ \frac{10}{9} \end{bmatrix}
\end{aligned}$$Backward substitution yields $\mathbf{y}_2 = \begin{bmatrix} -\frac{1}{4} \\ \frac{5}{12} \end{bmatrix}$. Normalize using $\|\mathbf{y}_2\|_\infty = \frac{5}{12}$:$$\mathbf{x}_2 = \frac{\mathbf{y}_2}{\|\mathbf{y}_2\|_\infty} = \begin{bmatrix} -\frac{3}{5} \\ 1 \end{bmatrix}$$
* **Approximation and Exact Solution:** After two iterations, the approximations are:$$\mathbf{v}_2 \approx \mathbf{x}_2 = \begin{bmatrix} -0.6 \\ 1 \end{bmatrix}, \quad \lambda_2 \approx \frac{\mathbf{x}_2^T A \mathbf{x}_2}{\mathbf{x}_2^T \mathbf{x}_2} = \frac{50}{33} \approx 1.515$$ The exact eigenpairs of $A$ (from $C_A(\lambda) = (\lambda-4)(\lambda-2)$) are:
* Dominant: $\lambda_1 = 4$, $\mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$
* Smallest: $\lambda_2 = 2$, $\mathbf{v}_2 = \begin{bmatrix} -1 \\ 1 \end{bmatrix}$
The inverse iteration is successfully converging toward the smallest eigenvector $\mathbf{v}_2$.
:::

#### Shifted Inverse Iteration
More generally, the power method can be applied to the shifted and inverted matrix, $(A - sI)^{-1}$, to find the eigenvalue $\lambda_j$ that is closest to a desired shift value $s \in \mathbb{C}$.

The eigenvalues of $(A - sI)^{-1}$ are $\frac{1}{\lambda_i - s}$. The dominant eigenvalue of $(A - sI)^{-1}$ is the one corresponding to the smallest value of $|\lambda_i - s|$, meaning $\lambda_i$ is closest to $s$.

:::success
**Exercise**
1. In the power iteration algorithm, we divide by $\|A \mathbf{x}_k\|_\infty$ in each step to:
* a. make the algorithm run faster
* b. prevent the entries of the vectors $\mathbf{x}_k$ from becoming too large/small
* c. produce a more accurate result
2. The power iteration algorithm (without normalization) computes a recursive sequence $\mathbf{x}_{k+1} = A \mathbf{x}_k$, where $\mathbf{x}_k$ converges to:
* a. the largest (in absolute value $|\lambda|$) eigenvalue of $A$
* b. an eigenvector corresponding to the largest (in absolute value $|\lambda|$) eigenvalue of $A$
* c. the smallest (in absolute value $|\lambda|$) eigenvalue of $A$
* d. an eigenvector corresponding to the smallest (in absolute value $|\lambda|$) eigenvalue of $A$
3. Let $A$ be a $2 \times 2$ matrix with eigenvalues $\lambda_1 = 1$ and $\lambda_2 = \tfrac{1}{2}$ and corresponding eigenvectors $\mathbf{v}_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ and $\mathbf{v}_2 = \begin{bmatrix} -1 \\ 1 \end{bmatrix}$. If we choose $\mathbf{x}_0 = \begin{bmatrix} 1 \\ 5 \end{bmatrix}$, then the sequence $\mathbf{x}_{k+1} = A \mathbf{x}_k$ converges to what?
4. Explain how to find the largest (in absolute value) eigenvalue of $A$ using the power method.
5. Explain how to find the eigenvalue of $A$ that is closest to 2 using the power method.
:::