Back to the on-screen lesson ·
Why conjugate gradients needs the square root of the condition number of iterations, the three bounds that all hold at once, and what a preconditioner is actually changing.
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 estimate a Krylov method's iteration count from the conditioning, say what each method requires of the matrix, describe what one step does, state what preconditioning does and does not change, and use the bound that comes from clustered eigenvalues.
You know that a splitting method converges linearly at a rate set by the spectral radius of its iteration matrix, and that the rate approaches one as the matrix becomes ill conditioned. This lesson is the family of methods that replaced them, and the improvement is a change of exponent rather than of constant.
The Krylov subspace of order $k$ is spanned by $r_0, Ar_0, \ldots, A^{k-1}r_0$. A short recurrence builds each new direction from the last two, so the storage does not grow. Conjugate gradients minimises the error in the energy norm over that subspace; GMRES minimises the residual for a general matrix. A preconditioner $M$ replaces the system by $M^{-1}Ax = M^{-1}b$.
A Krylov method touches the matrix only through matrix-vector products, so a sparse matrix costs no more than its non-zero entries. After $k$ products the approximation lives in the Krylov subspace $\mathrm{span}\{r_0, Ar_0, \ldots, A^{k-1}r_0\}$, and the method takes the best element of it by some measure. For a symmetric positive definite matrix that is conjugate gradients, whose error bound falls by about $\dfrac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}$ per step — so the iterations for a fixed accuracy go as $\sqrt{\kappa}$, where a splitting method needs $\kappa$. For a condition number of $10^{6}$ that is a thousand steps against a million. Two other bounds hold at once and are sometimes far better: the method is exact after $n$ steps in exact arithmetic, and after only as many steps as the matrix has distinct eigenvalues — because the error after $k$ steps is $p(A)e_0$ for a polynomial the method gets to choose. That last bound is what preconditioning is really exploiting. Replacing $A$ by $M^{-1}A$ for a cheaply invertible $M$ that resembles $A$ leaves the solution unchanged and improves the spectrum, either by shrinking $\kappa$ or by clustering the eigenvalues; the craft is entirely in the compromise between cheap to solve with and resembles $A$, which pull in opposite directions.
Another way: steps
Another way: picture
Plot the eigenvalues on a line. A splitting method's rate is decided by how close the extreme ones are to the ends of the interval it works in; conjugate gradients is choosing a polynomial that must equal one at the origin and be small at every eigenvalue. A spread-out spectrum makes that polynomial work hard — and it has Chebyshev's answer, which is where the square root comes from. A spectrum in three tight clusters is easy: a cubic with a root in each cluster is small everywhere it needs to be.
The $n$-step termination property is quoted as though it were how the method is used. It is not: for a matrix of a million rows, a million steps is not a finite algorithm in any useful sense, and rounding error destroys the exact orthogonality the property depends on long before then. Conjugate gradients is used as an iterative method, stopped when the residual is small enough, and the bound that describes real runs is the $\sqrt{\kappa}$ one or the clustering one. The second mistake is preconditioning without counting: a preconditioner that halves the iterations and triples the cost of a step has made the run slower.
A discretised second derivative on a grid of $n$ points: $\kappa \approx n^{2}$.
Badly conditioned by construction.
A splitting method needs $O(n^{2})$ iterations; conjugate gradients needs $O(n)$.
The square root.
With a good preconditioner the count can be made nearly independent of $n$ altogether.
Where the research went.
A matrix with eigenvalues at $1$ and at $10^{6}$, each repeated many times: $\kappa = 10^{6}$.
The bound suggests a thousand steps.
But there are two distinct eigenvalues, so conjugate gradients is exact in two.
The spectrum, not the ratio.
$\sqrt{10^{4}} = 100$ iterations.
After preconditioning, $\sqrt{10^{2}} = 10$.
A factor of ten in steps — worth having if solving with the preconditioner costs less than nine times the old step.
Conjugate gradients is applied to a symmetric positive definite system with $\kappa_2(A) = 729$. About how many iterations does it need for a fixed accuracy?
Answer:
Conjugate gradients needs about $\sqrt{\kappa}$ iterations. Give the count for $\kappa = 36$, $144$ and $324$.
| Condition number | Iterations | |
|---|---|---|
| $\kappa = 36$ | 36 | |
| $\kappa = 144$ | 144 | |
| $\kappa = 324$ | 324 |
Match each iterative method to what it requires of the matrix.
| Symmetric and positive definite; three vectors of storage | Symmetric, possibly indefinite; still a short recurrence | Any invertible matrix; storage grows with the iterations | A spectral radius below one, usually from diagonal dominance | |
|---|---|---|---|---|
| Conjugate gradients | ||||
| MINRES | ||||
| GMRES | ||||
| Jacobi |
Put the five things one step of a Krylov method does into the order they depend on each other.
Number the steps in order (write the number in the box):
A symmetric positive definite matrix of size $625$ has only $4$ **distinct** eigenvalues, though each is repeated many times. In exact arithmetic, how many conjugate gradient steps are needed at most?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Select every statement that is true of preconditioning a linear system.
This task has no paper form; do it on a device.
You can estimate the work a Krylov method needs and say what preconditioning changes. Say in your own words why the $n$-step termination property is not how the method is used.
8. Your turn: iterations for $\kappa = 10^{4}$, and what a preconditioner bringing it to $10^{2}$ saves, step 3