NLA MT25, Power method
-
[[Course - Numerical Linear Algebra MT25]]U
- The analysis of the power method is covered here:
- [[Notes - Numerical Analysis HT24, Power method]]U
Flashcards
@Describe the steps in the shifted inverse power method for computing the eigenvalue and eigenvector of $A \in \mathbb R^{n \times n}$ closest to a prescribed value $s \in \mathbb C$.
- Select arbitrary $y \in \mathbb R^n$
- Set $x _ 0 = y/ \vert \vert y \vert \vert $
- Then, for $k = 0, 1, \ldots$
- Compute $y _ k = (A - s I)^{-1} x _ k$
- Set $x _ {k+1} = y _ k / \vert \vert y _ k \vert \vert $
Then $x _ {k} \to \pm v _ 1$ and $\hat \lambda = x^\top A x$ gives an estimate for the eigenvalue.
(A justification of why this works is in ∆power-method-analysis).
The shifted inverse power method for computing the eigenvalue of $A \in \mathbb R^{n \times n}$ closest to a prescribed value $s \in \mathbb C$ can be described as follows:
- Select arbitrary $y \in \mathbb R^n$
- Set $x _ 0 = y/ \vert \vert y \vert \vert $
- Then, for $k = 0, 1, \ldots$
- Compute $y _ k = (A - s I)^{-1} x _ k$
- Set $x _ {k+1} = y _ k / \vert \vert y _ k \vert \vert $
Then $x _ {k} \to \pm v _ 1$ and $\hat \lambda = x^\top A x$ gives an estimate for the eigenvalue. This improves the rate of convergence to
\[\frac{1/(\lambda _ {\sigma(n-1)} - s)}{1/(\lambda _ {\sigma(n)} - s)} = \frac{\lambda _ {\sigma(n)} - s}{\lambda _ {\sigma(n-1)} - s}\]
where $\sigma$ is a permutation such that $ \vert \lambda _ {\sigma(1)} - s \vert > \vert \lambda _ {\sigma(2)} - s \vert \ge \cdots \ge \vert \lambda _ {\sigma(n)} - s \vert $.
What is the downside of this method?
- Compute $y _ k = (A - s I)^{-1} x _ k$
- Set $x _ {k+1} = y _ k / \vert \vert y _ k \vert \vert $
You have to invert a matrix at every step, which costs $O(n^3)$.
The shifted inverse power method for computing the eigenvalue of $A \in \mathbb R^{n \times n}$ closest to a prescribed value $s \in \mathbb C$ can be described as follows:
- Select arbitrary $y \in \mathbb R^n$
- Set $x _ 0 = y/ \vert \vert y \vert \vert $
- Then, for $k = 0, 1, \ldots$
- Compute $y _ k = (A - s I)^{-1} x _ k$
- Set $x _ {k+1} = y _ k / \vert \vert y _ k \vert \vert $
Then $x _ {k} \to \pm v _ 1$ and $\hat \lambda = x^\top A x$ gives an estimate for the eigenvalue. @State how the Rayleigh quotient iteration modifies this, the corresponding convergence rate, and how this improves further when $A$ is symmetric.
- Compute $y _ k = (A - s I)^{-1} x _ k$
- Set $x _ {k+1} = y _ k / \vert \vert y _ k \vert \vert $
The Rayleigh quotient iteration changes the shift at each iteration to $s _ k = x _ k^\top A x _ k$.
This gives quadratic convergence
\[\vert \vert Ax^{k+1} - \lambda^{k+1} x^{k+1} \vert \vert = O( \vert \vert Ax^k - \lambda^k x^k \vert \vert ^2)\]and when $A$ is symmetric, we have cubic convergence.