Back to the on-screen lesson ·
The power method's rate as a ratio of eigenvalues, how a shift and an inversion change which eigenvalue is found and how fast, and why the Rayleigh quotient is worth twice the digits of the vector it comes from.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive the power method's rate, compute it for a given spectrum, say which eigenvalue each variant finds and why, order the steps of a shifted inverse iteration, and explain the accuracy of the Rayleigh quotient.
You know eigenvalues and eigenvectors, and you have run the power method. You also know that a splitting method's rate is a ratio of quantities belonging to the matrix. The power method is the same story: its rate is a ratio of eigenvalues, and every improvement on it is a way of changing that ratio.
The dominant eigenvalue is the one largest in absolute value. A shift replaces $A$ by $A - \sigma I$, which subtracts $\sigma$ from every eigenvalue. Inverse iteration is the power method on the inverse. The Rayleigh quotient of a vector is $\dfrac{x^{\mathsf{T}}Ax}{x^{\mathsf{T}}x}$, the best scalar estimate of an eigenvalue that vector supports.
Expand the starting vector in eigenvectors. Applying $A$ multiplies the $j$th component by $\lambda_j$, so after $k$ steps the components are in the ratios $\lambda_j^{k}$; dividing by $\lambda_1^{k}$ leaves every other component carrying $(\lambda_j/\lambda_1)^{k}$. The power method therefore converges linearly at rate $\left|\dfrac{\lambda_2}{\lambda_1}\right|$ — slowly when the two largest are close, not at all when they are equal in size. That rate is a property of the spectrum, so the improvements change the spectrum instead. The eigenvalues of $A^{-1}$ are the reciprocals, so inverse iteration finds the smallest; the eigenvalues of $(A - \sigma I)^{-1}$ are $\dfrac{1}{\lambda_j - \sigma}$, so a shifted inverse iteration finds the eigenvalue nearest $\sigma$, and a good shift makes the ratio tiny. The inverse is never formed: $A - \sigma I$ is factorised once, outside the loop, and each step is two triangular solves. Finally, the eigenvalue is recovered from the Rayleigh quotient, and for a symmetric matrix it is accurate to $\epsilon^{2}$ when the vector is accurate to $\epsilon$, because the quotient is stationary at an eigenvector. Twice the digits for one extra product.
Another way: steps
Another way: picture
Think of the starting vector as a mixture and each step as turning up the volume on every eigen-direction by its own eigenvalue. The loudest drowns the rest out, and how fast it does so is the gap between the loudest and the second. A shift moves every eigenvalue along the line; an inversion turns the one nearest zero into the loudest of all. Putting the shift next to the eigenvalue you want makes it deafening in one step.
Inverse iteration looks ill-advised: $A - \sigma I$ is nearly singular by design, so the solve is ill conditioned, and the computed vector is badly wrong in the usual sense. It is wrong in a direction that does not matter. The error is overwhelmingly along the very eigenvector being sought, so a solution that is inaccurate as a solution is an excellent eigenvector — and the worse the conditioning, the better the direction. This is the one place in the course where ill conditioning is deliberately arranged, and it is worth knowing why it is safe.
Eigenvalues $10$ and $9$: the rate is $0.9$, about one digit every twenty-two steps.
A close pair.
Eigenvalues $10$ and $1$: the rate is $0.1$, one digit a step.
A wide gap.
Shift by $9.5$ and invert: the ratio becomes $\dfrac{|10 - 9.5|^{-1}}{|1 - 9.5|^{-1}}$ inverted — about $0.06$, from a shift and nothing else.
Changing the spectrum, not the method.
A symmetric matrix, eigenvector accurate to $10^{-4}$.
Four digits in the vector.
The Rayleigh quotient is accurate to about $10^{-8}$.
Eight in the eigenvalue.
The dominant eigenvalue is $6$; the next largest in size is $-3$.
The rate is $\left|\dfrac{-3}{6}\right| = \tfrac12$.
So about one binary digit a step — and the sign of the second eigenvalue is irrelevant, since only sizes decide which component dominates.
A matrix has eigenvalues $14$ and $3$ in size, with the rest smaller. By what factor does the power method's error shrink at each step? Give a fraction.
Answer:
The power method's error shrinks by a factor $\dfrac{1}{4}$ each step, starting from an error of $1$. Give the error after each of the first three steps, as fractions.
| Steps | Error | |
|---|---|---|
| After one step | 1 | |
| After two steps | 2 | |
| After three steps | 3 |
Apply $A = \begin{pmatrix} 6 & 1 \\ 1 & 6 \end{pmatrix}$ twice to the starting vector $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$, without normalising. Write the resulting column.
This task has no paper form; do it on a device.
Match each method to the eigenvalue it converges to.
| The eigenvalue largest in size | The eigenvalue smallest in size | The eigenvalue nearest the shift | All of them at once | |
|---|---|---|---|---|
| The power method on $A$ | ||||
| The power method on $A^{-1}$ | ||||
| The power method on $(A - \sigma I)^{-1}$ | ||||
| The QR algorithm |
For a symmetric matrix, an approximate eigenvector is accurate to about $10^{-6}$. The Rayleigh quotient $\dfrac{x^{\mathsf{T}}Ax}{x^{\mathsf{T}}x}$ is formed from it. To about what power of ten is the eigenvalue accurate?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put the five steps of inverse iteration with a shift into the order they depend on each other.
Number the steps in order (write the number in the box):
You can state and derive the rate of the power method and its variants. Say in your own words why a deliberately ill-conditioned solve is safe in inverse iteration.
8. Your turn: the rate of the power method with eigenvalues $6$, $-3$ and $1$, step 3