Back to the on-screen lesson ·
Solving a linear system by repeated sweeps rather than elimination, and the diagonal dominance that decides whether the sweeps close in or run away.
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 run Jacobi and Gauss-Seidel sweeps, say what distinguishes them, state the condition under which sweeping converges and why the starting point does not appear in it, and estimate how the error falls per sweep.
You know that a fixed-point iteration converges when the map contracts, and you know that elimination costs about $n^{3}$ operations. This lesson applies the first fact to a linear system, because for a large sparse matrix the second is unaffordable.
A sweep is one pass updating every unknown. A matrix is strictly diagonally dominant when each diagonal entry exceeds, in size, the sum of the sizes of the others in its row. The spectral radius of the iteration matrix is the largest size of its eigenvalues, and it is the rate at which the error decays. Over-relaxation takes a step further than the update suggests, by a chosen weight.
Rearrange each equation for the unknown on its own diagonal and sweep. Jacobi computes every new value from the previous iterate, so a sweep can be done all at once. Gauss-Seidel uses each new value the moment it exists, which typically about doubles the rate and makes the sweep sequential. Written as a fixed point, a sweep is $x_{k+1} = Mx_k + c$ and the error obeys $e_{k+1} = Me_k$, so the iteration converges exactly when the spectral radius of $M$ is below one, from any starting point — the opposite of Newton's method, where the start decides everything. The condition that can be checked by eye is strict diagonal dominance, which is sufficient and not necessary. Why bother, when elimination gives the exact answer in finitely many steps? Because a sweep costs one pass over the non-zero entries. For a sparse matrix of a hundred thousand unknowns that is cheap and $n^{3}$ is not — and elimination fills in the zeros, so it costs the storage as well as the time.
Another way: steps
Another way: example
$4x + y = 9$, $x + 4y = 6$ has solution $(2, 1)$. Jacobi from $(0,0)$ gives $(2.25, 1.5)$, then $(1.875, 0.9375)$, then $(2.0156, 1.0312)$ — closing by about a factor of four each sweep. Gauss-Seidel gives $(2.25, 0.9375)$ after one sweep, already closer than Jacobi's second.
Because Jacobi and Gauss-Seidel look like Newton's method — a start, a rule, a sequence — it is natural to assume that a better starting guess is what makes them work. It is not. The error obeys a linear map, so its behaviour is the same at every distance: a contracting iteration converges from anywhere, and an expanding one diverges from everywhere except the solution itself. A good starting guess buys sweeps, never convergence.
For $4x + y$, $x + 4y$ the iteration matrix has entries $-\tfrac14$ off the diagonal and zero on it.
Eigenvalues $\pm\tfrac14$.
So each sweep multiplies the error by about a quarter: about $0.6$ of a decimal digit per sweep.
Ten sweeps, six digits.
Change the diagonal to $1.1$ and the factor becomes about $0.9$: the same six digits now take about a hundred and thirty sweeps.
Dominance sets the cost.
A matrix from a grid has about five non-zero entries per row, whatever its size.
A sweep costs about $5n$.
Elimination on the same matrix fills the zeros in, and costs $n^{3}$ time and $n^{2}$ storage.
Often impossible, not merely slow.
So for $n = 10^{6}$, a thousand sweeps is cheap and one elimination is out of the question.
This is why iterative solvers exist.
First row: $|3| > |1|$, which holds.
Second row: $|5| > |2|$, which also holds.
So yes, and Jacobi converges on it from any starting point, without any eigenvalue being computed.
Solve $4x + y = -6$ and $x + 4y = 6$ by Jacobi iteration from $x = 0$, $y = 0$. Give the first two iterates, as fractions where they are not whole numbers.
| Value of x | Value of y | |
|---|---|---|
| After one sweep | ||
| After two sweeps |
A Jacobi iteration is run $26$ sweeps on a square system. What decides whether the iterates approach the solution?
Run one Gauss-Seidel sweep on $4x + y = 6$, $x + 4y = 9$ from $x = 0$, $y = 0$, and give the result as the row $(x, y)$.
This task has no paper form; do it on a device.
The same $630 \times 630$ sparse system is attacked four ways. Match each method to what distinguishes it.
| Every update uses only the previous iterate, so a sweep is fully parallel | Each update uses the newest values available, so a sweep is sequential | A Gauss-Seidel step taken further, by a weight chosen to speed up convergence | Not an iteration: the exact answer after a fixed, finite amount of work | |
|---|---|---|---|---|
| Jacobi iteration | ||||
| Gauss-Seidel iteration | ||||
| Successive over-relaxation | ||||
| Gaussian elimination |
In the system $dx + y = e$ and $x + dy = f$, the diagonal entry $d$ is free. For which $d$ is the matrix strictly diagonally dominant, so that Jacobi iteration is guaranteed to converge?
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For the system $4x + y = e$, $x + 4y = f$ the Jacobi iteration multiplies the error by about $\dfrac14$ each sweep. Starting from an error of $4$, what is it after $3$ sweeps? Give a fraction.
Answer:
You can carry out both kinds of sweep and test a matrix for diagonal dominance. Say in your own words why a better starting guess cannot make a divergent iteration converge.
8. Your turn: is $\begin{pmatrix} 3 & 1 \\ 2 & 5 \end{pmatrix}$ strictly diagonally dominant?, step 3