15 - Eigenvalues and Eigenvectors

Numerical method for finding Eigenvalues and Eigenvectors

Basic Definition

• For a matrix $A \in \mathbb{R}^{n \times n}$, if $Ax = \lambda x$ where:

  • $\lambda$ is a scalar
  • $x \neq 0$ (non-zero vector)

• Then:

  • $\lambda$ is called an eigenvalue of $A$
  • $x$ is called an eigenvector of $A$

Analogy: Think of a transformation matrix as a machine that stretches or rotates vectors. An eigenvector is a special vector that, when fed through the machine, only gets stretched or shrunk (not rotated). The eigenvalue tells you by how much it gets stretched.

Important Property: Scalar Multiplication

• Note: If $x$ is an eigenvector, then $\alpha x$ is also an eigenvector for any nonzero scalar $\alpha$
  • Proof: If $Ax = \lambda x$, then $A(\alpha x) = \alpha(Ax) = \alpha(\lambda x) = \lambda(\alpha x)$

Analogy: If you have a special direction that only gets stretched (not rotated), then any vector pointing in that same direction will also only get stretched. It's like finding a magic direction in space.

Applications

• Eigenvalues and eigenvectors are used in:
  • Physics
  • Analysis of vibration and stability
  • Analysis of ordinary differential equations and their algorithms
  • Machine learning (PCA, spectral methods)
  • Google's PageRank algorithm

Theorem: Symmetric Matrices

• This is a powerful result that simplifies many computations
• Symmetric matrices: $A = A^T$

Characteristic Polynomial

Derivation

• Suppose $\lambda$ is an eigenvalue of $A$ and $x$ is the associated eigenvector
• This means: There exists $x \neq 0$ such that $Ax = \lambda x$
• Rewriting:
  1. $\exists x \neq 0$ such that $Ax = \lambda x$
  2. Same as: $\exists x \neq 0$ such that $(A - \lambda I)x = 0$
  3. Same as: $A - \lambda I$ is singular
  4. Same as: $\det(A - \lambda I) = 0$

Definition

$\boxed{\det(A - \lambda I) \text{ is the characteristic polynomial}}$

• The roots of this polynomial are the eigenvalues of $A$

Analogy: Finding eigenvalues is like solving a detective mystery. The characteristic polynomial is your main clue - its solutions reveal all the eigenvalues hiding in the matrix.

Example 1: Finding Eigenvalues

Problem: Find eigenvalues of $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix}$

Solution:

$\det\left(\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} - \lambda \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\right) = \det\begin{bmatrix} 3-\lambda & -1 \\ -1 & 3-\lambda \end{bmatrix}$

$= (3-\lambda)^2 - 1$

$= \lambda^2 - 6\lambda + 8 = 0$

• Factor: $\lambda^2 - 6\lambda + 8 = (\lambda - 2)(\lambda - 4) = 0$
• Eigenvalues: $\lambda = 2$ and $\lambda = 4$

📄 CSS322_Doable_L15_Ex1.pdf

Properties of Characteristic Polynomial

• The characteristic polynomial of an $n \times n$ matrix is always of degree $n$
• Therefore, an $n \times n$ matrix has exactly $n$ eigenvalues
  • But they are not necessarily distinct!

Complications

1. Complex eigenvalues:
   • Even if $A$ is real, eigenvalues and eigenvectors may be complex
2. Irrational eigenvalues:
   • In general, eigenvalues are irrational numbers even if entries of $A$ are rational

Why We Can't Always Use Characteristic Polynomial

Fundamental Limitation

• Eigenvalues of matrices larger than 4×4 cannot be found in a finite number of steps
  • This is a corollary of the Abel-Ruffini theorem
  • Same issue as solving nonlinear equations
• Solving characteristic polynomial for eigenvalues is not useful for large matrices
  • Requires too many operations
  • Gives inaccurate results

Analogy: Using the characteristic polynomial for large matrices is like trying to find a specific grain of sand on a beach by examining each grain individually - theoretically possible but practically impossible.

Power Method

Algorithm

Given: $A \in \mathbb{R}^{n \times n}$

1. Choose $x^{(0)}$ := arbitrary nonzero vector
2. For $k = 0, 1, 2, \ldots$:

$\boxed{x^{(k+1)} = Ax^{(k)}}$

Analogy: The power method is like repeatedly applying a filter. Each time you apply it, the dominant feature (largest eigenvalue) becomes more and more apparent, while other features fade away.

Properties of Power Method

• Power method computes $A^k x^{(0)}$

Examples

• Converges: If $A$ has eigenvalues $-10, 5, 5$

  • Power method converges to eigenvector of $-10$
  • Because $|-10| = 10$ is unique maximum

• Does NOT converge: If $A$ has eigenvalues $-10, 10, 1, -2$

  • Two eigenvalues with equal maximum absolute value: $|-10| = |10| = 10$
  • No unique maximum

Partial Proof of Power Method Convergence

Setup

• Let $A \in \mathbb{R}^{n \times n}$
• Assumption: We can express $x^{(0)}$ as a linear combination of all eigenvectors of $A$
  • (This is not possible for all matrices)
• Let $v_1, \ldots, v_n$ be the $n$ eigenvectors
• Let $\lambda_1, \ldots, \lambda_n$ be the $n$ corresponding eigenvalues
  • i.e., $Av_i = \lambda_i v_i$
  • $\lambda_1$ has unique maximum absolute value

Derivation

Express initial vector:
$x^{(0)} = \sum_{j=1}^{n} \alpha_j v_j$

Apply power method:
$x^{(k)} = A^k x^{(0)} = A^k \sum_{j=1}^{n} \alpha_j v_j = \sum_{j=1}^{n} \alpha_j A^k v_j$
$= \sum_{j=1}^{n} \alpha_j A^{k-1}(Av_j) = \sum_{j=1}^{n} \alpha_j A^{k-1}(\lambda_j v_j)$
Continue expanding:
$x^{(k)} = \sum_{j=1}^{n} \lambda_j \alpha_j A^{k-1} v_j = \sum_{j=1}^{n} \lambda_j \alpha_j A^{k-2}(Av_j)$
$= \sum_{j=1}^{n} \lambda_j \alpha_j A^{k-2}(\lambda_j v_j) = \sum_{j=1}^{n} \lambda_j^2 \alpha_j A^{k-2} v_j$
Eventually:
$x^{(k)} = \sum_{j=1}^{n} \lambda_j^k \alpha_j v_j$
Factor out $\lambda_1^k$:
$x^{(k)} = \lambda_1^k \left(\alpha_1 v_1 + \sum_{j=2}^{n} \left(\frac{\lambda_j}{\lambda_1}\right)^k \alpha_j v_j\right)$

Key Observation

• For $j > 1$: $\left|\frac{\lambda_j}{\lambda_1}\right| < 1$ (since $\lambda_1$ has maximum absolute value)
• Therefore: $\left(\frac{\lambda_j}{\lambda_1}\right)^k \to 0$ as $k \to \infty$ for all $j > 1$

Conclusion

$\boxed{x^{(k)} \to \lambda_1^k \alpha_1 v_1 \text{ as } k \to \infty}$

• This is a multiple of the eigenvector $v_1$ associated with the eigenvalue with unique maximum absolute value

Example 2: Power Method

Problem: Perform power method on $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix}$ with $x^{(0)} = [1, 0]^T$
Solution:
$x^{(1)} = Ax^{(0)} = \begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 3 \\ -1 \end{bmatrix}$
$x^{(2)} = Ax^{(1)} = \begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} \begin{bmatrix} 3 \\ -1 \end{bmatrix} = \begin{bmatrix} 10 \\ -6 \end{bmatrix}$
$x^{(3)} = Ax^{(2)} = \begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} \begin{bmatrix} 10 \\ -6 \end{bmatrix} = \begin{bmatrix} 36 \\ -28 \end{bmatrix}$
$\vdots$
$x^{(10)} = \begin{bmatrix} 524800 \\ -523776 \end{bmatrix}$

• Notice: Values are growing extremely large! (Overflow problem)
  📄 CSS322_Doable_L15_Ex2.pdf

Problem: Overflow/Underflow

• Issue: $x^{(k)}$ can become very large or very small
• Typical problem with power method: It either overflows or underflows

Solution: Normalization

$\boxed{\text{Rescale } x^{(k)} \text{ each iteration}}$

Normalized Power Method

Algorithm

For $k = 0, 1, 2, \ldots$:

1. $\tilde{x}^{(k)} = Ax^{(k)}$
2. $f^{(k)} = \|\tilde{x}^{(k)}\|_2$
3. $x^{(k+1)} = \tilde{x}^{(k)} / f^{(k)}$

Analogy: Normalization is like a pressure release valve. After each iteration, we scale the vector back to a manageable size, keeping only the direction information (which is what matters for eigenvectors).

Example 3: Normalized Power Method

Problem: Perform normalized power method on $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix}$
Solution:

Iteration 0:
$\tilde{x}^{(0)} = Ax^{(0)} = \begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 3 \\ -1 \end{bmatrix}$
$f^{(0)} = \|\tilde{x}^{(0)}\|_2 = 3.1623$
$x^{(1)} = \tilde{x}^{(0)} / f^{(0)} = \begin{bmatrix} 3 \\ -1 \end{bmatrix} / 3.1623 = \begin{bmatrix} 0.9487 \\ -0.3162 \end{bmatrix}$
Iteration 1:
$\tilde{x}^{(1)} = Ax^{(1)} = \begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} \begin{bmatrix} 0.9487 \\ -0.3162 \end{bmatrix} = \begin{bmatrix} 3.1623 \\ -1.8974 \end{bmatrix}$
$f^{(1)} = \|\tilde{x}^{(1)}\|_2 = 3.6878$
$x^{(2)} = \tilde{x}^{(1)} / f^{(1)} = \begin{bmatrix} 0.8575 \\ -0.5145 \end{bmatrix}$
$\vdots$
$x^{(7)} = \begin{bmatrix} 0.7126 \\ -0.7016 \end{bmatrix}$

• No overflow now! Values stay bounded

📄 CSS322_Doable_L15_Ex3.pdf

Another Problem with Power Method

Non-Convergence Case

• If there are two or more eigenvalues with largest absolute value, the power method will not converge
  • Example: $|\lambda_1| = |\lambda_2|$ where both are maximum

Example of Bad Case

$A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$

• Eigenvalues: $\pm 1$ (both have absolute value 1)
• Eigenvectors: $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ and $\begin{bmatrix} 1 \\ -1 \end{bmatrix}$

Using $x^{(0)} = [3, 4]^T$:

• $x^{(1)} = [4, 3]^T$
• $x^{(2)} = [3, 4]^T$
• $x^{(3)} = [4, 3]^T$
• Oscillates forever, does not converge!
  • Not making progress อะไรเลย

Analogy: This is like trying to find the tallest person in a room where two people have exactly the same height. The method keeps switching back and forth between them.

Obtaining the Eigenvalue

The Problem

• Power method gives us an eigenvector
• But what is the eigenvalue for this eigenvector?

Solution: Rayleigh Quotient

Find eigenvalue $\lambda$ by solving:
$\min_{\lambda} \|Ax^{(k)} - \lambda x^{(k)}\|_2$

(Why not solve $\lambda x^{(k)} = Ax^{(k)}$ instead? Because $x^{(k)}$ is not a true eigenvector, just an approximation of an eigenvector. Overdetermined system)

Formula

By the method of normal equations:
$\boxed{\lambda = \frac{(x^{(k)})^T Ax^{(k)}}{(x^{(k)})^T x^{(k)}}}$

• This is called the Rayleigh quotient
• The denominator may be omitted if $x^{(k)}$ is normalized

Analogy: The Rayleigh quotient is like measuring the "stretching factor" - it compares how much the vector got stretched after transformation versus its original size.

Example 4: Computing Eigenvalue

Problem: Find eigenvalue for $x^{(7)} = \begin{bmatrix} 0.7126 \\ -0.7016 \end{bmatrix}$ from Example 3

Solution:

$\lambda = \frac{(x^{(k)})^T Ax^{(k)}}{(x^{(k)})^T x^{(k)}}$

$= \frac{\begin{bmatrix} 0.7126 & -0.7016 \end{bmatrix} \begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} \begin{bmatrix} 0.7126 \\ -0.7016 \end{bmatrix}}{\begin{bmatrix} 0.7126 & -0.7016 \end{bmatrix} \begin{bmatrix} 0.7126 \\ -0.7016 \end{bmatrix}}$

$= 3.9999 \approx 4$

• This matches the eigenvalue we found in Example 1!

📄 CSS322_Doable_L15_Ex4.pdf

Summary

Key Concepts

1. Eigenvalues & Eigenvectors: $Ax = \lambda x$
2. Characteristic Polynomial: $\det(A - \lambda I) = 0$
3. Power Method: Iteratively multiply $x^{(k+1)} = Ax^{(k)}$
4. Normalized Power Method: Scale at each step to prevent overflow
5. Rayleigh Quotient: Extract eigenvalue from eigenvector

When Power Method Works

✅ Matrix has unique eigenvalue with maximum absolute value
✅ Initial vector has component in direction of dominant eigenvector

When Power Method Fails

❌ Multiple eigenvalues with same maximum absolute value
❌ Need all eigenvalues (power method only finds one)
❌ Large matrices (use advanced methods like QR algorithm instead)

Inverse Power Method

Algorithm

Given: $A \in \mathbb{R}^{n \times n}$

1. Choose $x^{(0)}$ := arbitrary nonzero vector
2. For $k = 0, 1, 2, \ldots$:
   $\boxed{x^{(k+1)} = A^{-1} x^{(k)} \text{ (plus normalization)}}$

อันนี้ก็แค่ Apply Power Method กับ $A^{-1}$ ดังนั้นถ้าได้ออกมา (converges) ก็จะเป็น Eigenvector ของ $A^{-1}$

แล้ว Relationship ระหว่าง Eigen ของ $A^{-1}$ กับ $A$ เฉย ๆ เป็นไงล่ะ

Analogy: If the regular power method is like repeatedly amplifying a signal to find the strongest frequency, the inverse power method is like using noise-canceling to eliminate the strongest signals and find the weakest one instead.

Understanding Inverse Power Method

• Inverse power method is essentially the power method applied to $A^{-1}$
• It returns the eigenvector of $A^{-1}$ corresponding to the eigenvalue with maximum absolute value
• Question: Any relationship with eigenvector of $A$?

• i.e., if $\lambda$ is an eigenvalue of $A$, then $1/\lambda$ is an eigenvalue of $A^{-1}$

Proof

Suppose $(\lambda, x)$ is an eigenpair of $A$:
$Ax = \lambda x$
Multiply both sides by $A^{-1}$:
$A^{-1}(Ax) = A^{-1}(\lambda x)$
$x = \lambda A^{-1}x$
Divide both sides by $\lambda$:
$\left(\frac{1}{\lambda}\right)x = A^{-1}x$
Therefore, $(1/\lambda, x)$ is an eigenpair of $A^{-1}$.

Convergence of Inverse Power Method

• Inverse power method converges to the eigenvector corresponding to the eigenvalue with smallest absolute value of $A$

Examples

Example 1 - Converges:

• If $A$ has eigenvalues: $-10, -10, -2, 4, 4$
• Inverse power method converges to eigenvector of $-2$
• Because $|-2| = 2$ is the unique minimum

Example 2 - Does NOT Converge:

• If $A$ has eigenvalues: $-20, 1, -1$
• Inverse power method does not converge
• Because $|1| = |-1| = 1$ (two eigenvalues with same minimum absolute value)

Efficient Implementation of Inverse Power Method

The Challenge

• How to compute $x^{(k+1)} = A^{-1}x^{(k)}$ efficiently?

The Solution

$\boxed{\text{Factor } A = P^T LU \text{ (GEPP) once, then reuse factors}}$
Important: Don't form $A^{-1}$ explicitly!

Computational Cost

• Initial factorization: $2n^3/3 + O(n^2)$ arithmetic operations
• Per iteration: $2n^2 + O(n)$ arithmetic operations

Implementation Steps

1. Factor $A = P^T LU$ using GEPP (once at the beginning)
2. Each iteration: Solve $Ax^{(k+1)} = x^{(k)}$ using the factors
   • Forward substitution with $L$
   • Backward substitution with $U$
3. Normalize the result

Analogy: It's like building a factory assembly line once (factorization), then using it repeatedly to manufacture products (solve systems). You don't rebuild the entire factory each time you need a product!

Example 5: Inverse Power Method

Problem: Apply inverse power method to $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix}$ with $x^{(0)} = [1, 0]^T$
Solution:

Step 1: Factorize $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} = P^T LU$ by GEPP

Step 2: Use factors to solve $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} x^{(1)} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$
Result (before normalization):
$x^{(1)} = \begin{bmatrix} 0.3750 \\ 0.1250 \end{bmatrix}$
Step 3: Normalize by dividing by 2-norm:
$x^{(1)} = \begin{bmatrix} 0.9487 \\ 0.3162 \end{bmatrix}$
Iteration 2:

Reuse factors to solve $\begin{bmatrix} 3 & -1 \\ -1 & 3 \end{bmatrix} x^{(2)} = x^{(1)} = \begin{bmatrix} 0.9487 \\ 0.3162 \end{bmatrix}$

Result (before normalization):
$x^{(2)} = \begin{bmatrix} 0.3953 \\ 0.2372 \end{bmatrix}$
After normalization:
$x^{(2)} = \begin{bmatrix} 0.8575 \\ 0.5145 \end{bmatrix}$
Continue iterations...
$x^{(7)} = \begin{bmatrix} 0.7126 \\ 0.7016 \end{bmatrix} \text{ (after normalization)}$
📄 CSS322_Doable_L15_Ex5.pdf

Inverse Shifted Power Method

Algorithm

Given: $A \in \mathbb{R}^{n \times n}$

1. Choose $x^{(0)}$ := arbitrary nonzero vector
2. For $k = 0, 1, 2, \ldots$:
   $\boxed{x^{(k+1)} = (A - \sigma I)^{-1} x^{(k)} \text{ (plus normalization)}}$

• $\sigma$ is a scalar that is chosen in advance (the "shift")

Analogy: Regular inverse power method is like finding the quietest sound in a room. Shifted inverse power method is like first changing your perspective (shifting), then finding what's quietest from that new viewpoint. This lets you target specific frequencies!

Proof

Suppose $(\lambda, x)$ is an eigenpair of $A$:
$Ax = \lambda x$
Subtract $\sigma x$ from both sides:
$(A - \sigma I)x = (\lambda - \sigma)x$
Multiply both sides by $(A - \sigma I)^{-1}$:
$x = (\lambda - \sigma)(A - \sigma I)^{-1}x$
Divide by $(\lambda - \sigma)$:
$\left(\frac{1}{\lambda - \sigma}\right)x = (A - \sigma I)^{-1}x$
Therefore, $(1/(\lambda - \sigma), x)$ is an eigenpair of $(A - \sigma I)^{-1}$.

Convergence of Inverse Shifted Power Method

How It Works

• The method finds the eigenvalue of $A$ that is closest to $\sigma$
• This is because $\frac{1}{\lambda - \sigma}$ is largest when $|\lambda - \sigma|$ is smallest

Examples

Example 1 - Converges:

• Eigenvalues: $-10, -10, 1, 1, 6$ with $\sigma = 5$
• Distances from $\sigma = 5$:
  • $|-10 - 5| = 15$
  • $|1 - 5| = 4$
  • $|6 - 5| = 1$ ← smallest (unique)
• Method converges to eigenvector of $6$

Example 2 - Does NOT Converge:

• Eigenvalues: $-20, 1, 5, 7$ with $\sigma = 6$
• Distances from $\sigma = 6$:
  • $|-20 - 6| = 26$
  • $|1 - 6| = 5$
  • $|5 - 6| = 1$ ← tied
  • $|7 - 6| = 1$ ← tied
• Method does not converge (two eigenvalues equidistant from $\sigma$)

Analogy: Imagine you're in a city (the complex plane of eigenvalues) and you pick a landmark ($\sigma$). The shifted inverse power method will guide you to the unique nearest building. But if two buildings are equally close, you'll keep wandering between them!

Example 6: Inverse Shifted Power Method

Problem: Perform inverse shifted power method on $\begin{bmatrix} 4 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 5 \end{bmatrix}$ using $\sigma = 3.5$
Solution:

Step 1: Compute $A - \sigma I$
$A - \sigma I = \begin{bmatrix} 4 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 5 \end{bmatrix} - \begin{bmatrix} 3.5 & 0 & 0 \\ 0 & 3.5 & 0 \\ 0 & 0 & 3.5 \end{bmatrix} = \begin{bmatrix} 0.5 & 1 & 2 \\ 1 & -1.5 & 0 \\ 2 & 0 & 1.5 \end{bmatrix}$
Step 2: Choose starting point
$x^{(0)} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$
Step 3: Factorize $A - \sigma I = P^T LU$ by GEPP

Step 4: Solve $(A - \sigma I)x^{(1)} = x^{(0)}$ using factors
After normalization:
$x^{(1)} = \begin{bmatrix} -0.1735 \\ -0.6361 \\ 0.7518 \end{bmatrix}$
Step 5: Reuse factors to solve $(A - \sigma I)x^{(2)} = x^{(1)}$
After normalization:
$x^{(2)} = \begin{bmatrix} 0.5894 \\ 0.6273 \\ -0.5090 \end{bmatrix}$
And so on...

QR Iteration

Basic QR Iteration Algorithm

1. $M^{(0)} = A$
2. For $k = 0, 1, 2, \ldots$:
   • Factor: $M^{(k)} = Q^{(k)}R^{(k)}$ (Compute $Q^{(k)}$ and $R^{(k)}$ by QR factorization)
   • Define: $M^{(k+1)} := R^{(k)}Q^{(k)}$ (Compute $M^{(k+1)}$ from known $Q^{(k)}$ and $R^{(k)}$)

Analogy: QR iteration is like repeatedly shuffling a deck of cards using a specific technique. Each shuffle (QR factorization followed by reverse multiplication) gradually sorts the eigenvalues into diagonal positions, like how repeated shuffles might eventually separate cards by suit.

Example 7: QR Iteration

10 - Linear Least Squares

Problem: Perform two steps of basic QR iteration on $A = \begin{bmatrix} 4 & -1 \\ -1 & 6 \end{bmatrix}$

Solution:

Iteration 0

Step 1: Set $M^{(0)} = A$

Step 2: Compute QR factorization of $M^{(0)}$ using Householder transformation:

$Q^{(0)} = \begin{bmatrix} -0.9701 & 0.2425 \\ 0.2425 & 0.9701 \end{bmatrix}, \quad R^{(0)} = \begin{bmatrix} -4.1231 & 2.4254 \\ 0 & 5.5783 \end{bmatrix}$

Step 3: Compute $M^{(1)} = R^{(0)}Q^{(0)}$:

$M^{(1)} = \begin{bmatrix} -4.1231 & 2.4254 \\ 0 & 5.5783 \end{bmatrix} \begin{bmatrix} -0.9701 & 0.2425 \\ 0.2425 & 0.9701 \end{bmatrix}$

$= \begin{bmatrix} 4.5882 & 1.3529 \\ 1.3529 & 5.4118 \end{bmatrix}$

Iteration 1

Step 1: Perform QR factorization on $M^{(1)}$:

$Q^{(1)} = \begin{bmatrix} -0.9592 & -0.2828 \\ -0.2828 & 0.9592 \end{bmatrix}, \quad R^{(1)} = \begin{bmatrix} -4.7836 & -2.8283 \\ 0 & 4.8081 \end{bmatrix}$

Step 2: Compute $M^{(2)} = R^{(1)}Q^{(1)}$:

$M^{(2)} = \begin{bmatrix} -4.7836 & -2.8283 \\ 0 & 4.8081 \end{bmatrix} \begin{bmatrix} -0.9592 & -0.2828 \\ -0.2828 & 0.9592 \end{bmatrix}$

$= \begin{bmatrix} 5.3882 & -1.3599 \\ -1.3599 & 4.6118 \end{bmatrix}$

Notice: Off-diagonal elements are getting smaller! The matrix is gradually becoming diagonal.
📄 CSS322_Doable_L15_Ex7.pdf

QR Iteration: Properties and Issues

Convergence

• Under many assumptions, $M^{(k)}$ converges to a diagonal matrix
• The diagonal entries are the eigenvalues of $A$

Issues with Basic QR Iteration

Problem 1: Computational Cost

• As written, each iteration requires $O(n^3)$ arithmetic operations
• This is impractical for large matrices

Problem 2: Slow/Non-Convergence

• Convergence is slow or nonexistent if any two eigenvalues have close magnitudes
• Similar to the issues with power methods

Advanced Solutions (Not Covered)

• There are complex ways to fix these problems:
  • Can reduce each iteration to $O(n)$ operations
  • Use shifts and deflation strategies
  • Hessenberg reduction preprocessing
  • These techniques are beyond the scope of this course

Analogy: Basic QR iteration is like using a hand saw to cut wood - it works but is very slow. Advanced QR methods are like using a chainsaw with a laser guide - much faster and more precise. However, the chainsaw is also much more complex to operate!

Summary: Methods for Finding Eigenvalues/Eigenvectors

Power Method

✅ Finds: Eigenvalue with largest absolute value
❌ Limitation: Only one eigenvalue/eigenvector
❌ Fails if: Multiple eigenvalues have same max absolute value

Inverse Power Method

✅ Finds: Eigenvalue with smallest absolute value
❌ Limitation: Only one eigenvalue/eigenvector
❌ Fails if: Multiple eigenvalues have same min absolute value
💡 Implementation: Use LU factorization, don't compute $A^{-1}$ explicitly

Inverse Shifted Power Method

✅ Finds: Eigenvalue closest to shift $\sigma$
✅ Advantage: Can target specific eigenvalues
❌ Fails if: Multiple eigenvalues equidistant from $\sigma$
💡 Strategy: Good initial guess of $\sigma$ critical for success

QR Iteration

✅ Finds: All eigenvalues simultaneously
✅ Advantage: Most general method
❌ Limitation: Expensive ($O(n^3)$ per iteration in basic form)
❌ Challenge: Can be slow if eigenvalues are close
💡 Advanced versions: Can reduce to $O(n)$ per iteration

Comparison Table

Key Takeaways

1. Don't compute matrix inverses explicitly - always use factorizations
2. Uniqueness matters - all iterative methods fail when multiple eigenvalues have the same target property
3. Normalization prevents overflow - always normalize vectors in iterative methods
4. Shifts provide control - shifting allows targeting specific eigenvalues
5. Trade-offs exist - simple methods (power, inverse power) are cheap but limited; general methods (QR) are expensive but comprehensive
6. Practical implementations are much more sophisticated than basic algorithms shown here