Back to the on-screen lesson ·
The spectral radius as the exact condition and the exact rate, the splittings behind the classical methods, and why a norm is the wrong instrument.
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 form an iteration matrix from a splitting, decide convergence from its spectral radius, bound the error after a given number of steps, name the splitting behind each classical method, and find the parameters for which a relaxed iteration converges.
You have run Jacobi and Gauss-Seidel, and you know the contraction mapping theorem — that a map converges when it shrinks distances. An iterative solver is an affine map on vectors, so the theorem applies; what is new is that the right measure of shrinking is not a norm but the spectral radius.
A splitting writes $A = M - N$, giving the iteration $Mx_{k+1} = Nx_k + b$ and the iteration matrix $M^{-1}N$. The spectral radius $\rho(M)$ is the largest eigenvalue in absolute value. A matrix is strictly diagonally dominant when each diagonal entry exceeds the sum of the sizes of the rest of its row. Over-relaxation weights a step by a parameter $\omega$.
Every classical iterative solver is a splitting $A = M - N$ and an iteration $x_{k+1} = M^{-1}Nx_k + M^{-1}b$. Subtracting the fixed point gives $e_{k+1} = M^{-1}Ne_k$, so $e_k = (M^{-1}N)^{k}e_0$, and the whole question is what powers of a matrix do. The answer is exact:
> The iteration converges from every starting vector if and only if $\rho(M^{-1}N) < 1$, and the asymptotic rate is $\rho$ itself.
Not a norm: $\|M^{-1}N\| < 1$ in some norm is sufficient and not necessary, and a matrix with spectral radius $\tfrac12$ can have norm a thousand and grow for many steps before it turns round. The classical methods are choices of $M$: Jacobi takes the diagonal, Gauss-Seidel the lower triangle, SOR the lower triangle with a weight, Richardson a multiple of the identity. Each choice trades the cost of a step against the size of $\rho$, and the familiar sufficient conditions — strict diagonal dominance, symmetry with positive definiteness — are ways of proving $\rho < 1$ without computing it. Convergence is always linear: a fixed number of digits per step, for ever, which is the standing weakness of the whole family and what the next lesson improves on.
Another way: steps
Another way: example
For $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, Jacobi's iteration matrix is $\begin{pmatrix} 0 & -1/2 \\ -1/2 & 0 \end{pmatrix}$ with eigenvalues $\pm\tfrac12$, so $\rho = \tfrac12$: about $0.3$ of a decimal digit per step, and thirty-four steps for ten digits.
The norm of the iteration matrix is used in place of its spectral radius, and a convergent iteration is then declared divergent — or, worse, an iteration is watched for a few steps, seen to grow, and abandoned. A non-symmetric matrix with $\rho = \tfrac12$ can have every norm large, and its powers can grow for a long while before the eventual decay takes over. The spectral radius is a statement about the limit, and the transient before it is real and can be enormous.
Strict diagonal dominance: each $|a_{ii}|$ exceeds the sum of the rest of its row.
A condition on the matrix.
Then every absolute row sum of $D^{-1}(L + U)$ is below one, so $\|M^{-1}N\|_\infty < 1$ and hence $\rho < 1$.
A norm bounding the radius.
Sufficient, and not necessary: plenty of matrices without it converge perfectly well.
The usual direction.
The model problem from a discretised second derivative: Jacobi has $\rho \approx 1 - \tfrac{\pi^{2}h^{2}}{2}$.
Painfully close to one.
Gauss-Seidel squares it; optimal SOR gives $\rho \approx 1 - 2\pi h$.
The exponent of $h$ changes.
Iterations fall from $O(n^{2})$ to $O(n)$ — from a parameter, not from a new idea.
Worth the tuning.
The iteration matrix is $\begin{pmatrix} 0 & -2/3 \\ -2/3 & 0 \end{pmatrix}$.
Its eigenvalues are $\pm\tfrac23$, so $\rho = \tfrac23$.
Below one: convergent from every start, with the error multiplied by about two thirds each step — about one decimal digit every six steps.
Jacobi iteration is applied to $A = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}$. What is the spectral radius of its iteration matrix? Give a fraction.
Answer:
Write the Jacobi iteration matrix $M = -D^{-1}(L + U)$ for $A = \begin{pmatrix} 4 & 3 \\ 3 & 4 \end{pmatrix}$.
This task has no paper form; do it on a device.
An iteration has spectral radius $\dfrac{1}{4}$ and its starting error has norm at most $5$. Give the bound on the error after each of the first three steps, as fractions where they are not whole.
| Steps | Bound on the error | |
|---|---|---|
| After one step | 1 | |
| After two steps | 2 | |
| After three steps | 3 |
Every classical iterative method writes $A = M - N$ and iterates $Mx_{k+1} = Nx_k + b$. Match each method to its $M$.
| $M = D$: one division per unknown | $M = D + L$: a forward substitution each step | $M = D/\omega + L$: the same, with a weight to tune | $M = I/t$: no solve at all, just a product | |
|---|---|---|---|---|
| Jacobi | ||||
| Gauss-Seidel | ||||
| Successive over-relaxation | ||||
| Richardson |
For a consistently ordered matrix, Gauss-Seidel's spectral radius is the square of Jacobi's. Jacobi's is $\dfrac{1}{6}$. What is Gauss-Seidel's? Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Richardson iteration $x_{k+1} = x_k - t(Ax_k - b)$ is applied to a symmetric positive definite $A$ whose eigenvalues all lie between $1$ and $8$. For which positive $t$ does it converge from every start?
This task has no paper form; do it on a device.
You can form an iteration matrix and decide convergence and rate from its spectral radius. Say in your own words why a large norm does not stop an iteration converging.
8. Your turn: does Jacobi converge for $\begin{pmatrix} 3 & 2 \\ 2 & 3 \end{pmatrix}$?, step 3