Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.8

Elliptic Solvers: Jacobi, Gauss–Seidel & SOR

Solving Poisson's equation on a grid: the matrix structure, Jacobi, Gauss–Seidel, red-black ordering, SOR, convergence rates.

Written byClaude Sonnet

🌊
Why this matters for simulation: Stam's 'lin_solve' routine is Gauss–Seidel; the pressure solve is the bottleneck of every incompressible solver.

By the end of this lesson you can…

  • Write the five-point Poisson problem as a sparse system $A\mathbf u = \mathbf b$ and say why nobody forms $A^{-1}$.
  • Split $A = D - L - U$, derive the Jacobi and Gauss–Seidel iteration matrices, and derive $\rho_{\text{Jacobi}} = \cos\pi h$ from the Laplacian eigenvalues.
  • Explain red-black ordering and why it suits parallel hardware.
  • Use SOR with $\omega = 2/(1+\sin\pi h)$ and measure the scaling: $1/h^2$ sweeps for Jacobi and Gauss–Seidel, $1/h$ for optimal SOR.
  • Read an error field against a residual field and explain why smooth error dies slowly.
  • State the conjugate gradient iteration, and say what Stam's 20-sweep `lin_solve` leaves unconverged.
On this page
·
  1. The system behind the stencil
  2. Splitting: Jacobi and Gauss–Seidel
  3. Red-black ordering
  4. SOR and the optimal factor
  5. The lab: five solvers on one problem
  6. Counting: 1/h21/h^21/h2 against 1/h1/h1/h
  7. Error against residual, and the seed of multigrid
  8. Conjugate gradients
  9. Stam’s lin_solve
  10. Worked example: three radii on a 3×33\times33×3 grid
  11. The exercise
  12. Concept checks
  13. Problems
  14. Key Takeaways

10.4 Implicit Methods & Crank–Nicolson ended on a loose end. In 2D the implicit time step needs a matrix with five nonzeros per row, not three, and the Thomas algorithm no longer applies. Stam faces the same matrix twice per frame, for diffusion and for pressure, and solves it by sweeping the grid about twenty times. 9.6 Laplace's Equation: Rectangles & Disks already ran such sweeps on a plate: 23092309 for Jacobi, 11661166 for Gauss–Seidel, 9595 for SOR, at residual 10−610^{-6} on 4040 intervals. This lesson is the theory and practice behind those numbers: where they come from, why they grow with refinement, and what a solver that stops after twenty sweeps returns.

▶ Video The five-point matrix, Jacobi and Gauss-Seidel sweeps, the checkerboard ordering, the SOR factor, smooth error surviving, conjugate gradients, and twenty sweeps that stop shortcaptions only
Transcript
  1. At every interior node the five-point stencil gives one equation: four times the centre value minus its four neighbours equals h squared times the source. Stack the unknowns and this is A u equals b, with 4 on the diagonal and minus 1 at four neighbours. For N equal 40 that is 1521 unknowns and only 7449 nonzeros. The inverse is dense, so nobody forms it. An iteration touches only the stencil. The question is how many.
  2. Write A as D minus L minus U. Evaluate the right side at the old iterate and you have Jacobi. Use each new value the moment it exists and you have Gauss-Seidel. Either way the error is multiplied by a matrix each sweep, so what matters is its spectral radius. For Jacobi that is cosine of pi h, which is 0.99692 at N equal 40, and 2309 sweeps. For Gauss-Seidel it is the square, 0.99384, and 1166 sweeps, about half. Jacobi also multiplies the checkerboard error by nearly minus 1.
  3. Colour the nodes like a checkerboard. Every neighbour of a red node is black, so all the red nodes can be updated at once, and then all the black ones from the fresh reds. A lexicographic sweep is a recurrence. This is two fully parallel passes, which is why GPU solvers use it. Is it as fast? It keeps the factor cosine squared of pi h, 0.9938 at N equal 40. The counts differ, 1166 and 1268, but that is a difference in the start, not the end.
  4. Successive over-relaxation goes past the neighbour average by a factor omega between 1 and 2. Young's result, which the lab confirms, gives the best omega as 2 over 1 plus sine of pi h, and a factor of omega minus 1. The gap shrinks like h, not h squared. At N equal 40 the optimum is 1.8545, factor 0.8545. The curve drops steeply to the optimum and rises only slowly after it, so when unsure, overshoot. The minimum is flat, 95 sweeps at 1.85, 96 at the optimum.
  5. Now race them. Each solver starts from the same plate and runs to residual 10 to the minus 6. Jacobi takes 2309 sweeps, Gauss-Seidel 1166, red-black 1268. SOR at 1.85 takes 95, and conjugate gradients 84. The lab also measures the factor and compares it with the prediction. Jacobi and Gauss-Seidel match to four digits. SOR's measurement is low because 95 sweeps is a short run for a method with a transient.
  6. Now vary N. The number of sweeps against N, on log axes. SOR and conjugate gradients sit near slope 1. The Jacobi family sits at 1.75, not 2, so the counts rise by 3.5, 3.4 and 3.2 per doubling, not 4. The reason is in the logarithm: the rate itself falls by 4.09, 4.01 and 4.00 per doubling, exactly the one over h squared law, but with an absolute tolerance the number of decades to cover shrinks as the grid refines.
  7. Why do twenty sweeps not suffice? A sweep replaces a node by its neighbours' average. A node that sticks out is corrected at once, while a node near the average barely moves. So rough error dies fast and smooth error slowly. The residual is A times the error, small exactly for smooth error: a small residual is not a small error. Start from noise, with 49.4 percent of the error energy rough. After 20 sweeps Gauss-Seidel has smoothed it. Jacobi keeps a checkerboard tail, 2.2 percent, and SOR at 1.85 keeps 47.1 percent. It does not smooth at all.
  8. Relaxation uses only the current iterate. Conjugate gradients uses all the earlier ones. Each step is one product with A, a few dot products, and no omega to tune. The result worth knowing is the energy-norm bound, with the factor square root kappa minus 1 over square root kappa plus 1. That is about 1 minus pi h, so about 1 over h iterations. At N equal 40 the bound is 0.92439 and the measured contraction is 0.81644. Read the gap as pessimism, not contradiction. It needs 84 iterations, against SOR's 96.
  9. Stam's solver does a fixed 20 Gauss-Seidel sweeps, with no tolerance. From zero on our N equal 40 plate, they leave a residual of 6.67 times 10 to the minus 3, which is 2.67 percent of the start, and about 6670 times our tolerance. The largest error has fallen only from 0.9496 to 0.573, so 60 percent of the error remains. Twenty sweeps remove the rough, local part and hardly touch the smooth part. Incompressibility is restored locally, but not the large-scale pressure.
  10. To recap: Jacobi 2309 sweeps, Gauss-Seidel 1166, SOR 95, conjugate gradients 84. Sweeps grow like 1 over h squared for the Jacobi family, and like 1 over h for optimal SOR and CG. The catch is smooth error, which survives. Twenty sweeps leave 2.67 percent of the residual. The fix is multigrid, lesson 10.9, which is not yet written: relax with Gauss-Seidel, then correct the smooth remainder on a coarser grid. Before that, the staggered grid lesson builds the stencils whose product is this Laplacian.

The system behind the stencil

At every interior node of −∇2u=f-\nabla^2 u = f the five-point stencil says 4uC−uE−uW−uN−uS=h2fC4u_C - u_E - u_W - u_N - u_S = h^2 f_C, with known edge values moved to the right side. Stack the (N−1)2(N-1)^2 unknowns into u\mathbf u and this is Au=bA\mathbf u = \mathbf b: 44 on the diagonal, −1-1 at four neighbours, nothing else. For N=40N = 40 that is 15211521 unknowns and a matrix with 2 313 4412\,313\,441 entries, 74497449 of them nonzero. At N=1000N = 1000 there are 998 001998\,001 unknowns; a dense matrix needs about 88 terabytes, the five numbers per row need 4040 megabytes.

So nobody forms A−1A^{-1}. It is dense (a source at one node moves every node, the Green’s function of 9.6 Laplace's Equation: Rectangles & Disks), and banded elimination costs about N4N^4 in 2D (from memory). An iteration touches only the stencil, about five operations per unknown: many cheap approximate solves instead of one expensive exact one. The question is how many.

The eigenvectors of AA are the sampled sines sin⁡(pπx)sin⁡(qπy)\sin(p\pi x)\sin(q\pi y), with the eigenvalues of 10.1 Finite Differences: Discretizing Derivatives:

λpq=4−2cos⁡pπh−2cos⁡qπh,p,q=1,…,N−1.\lambda_{pq} = 4 - 2\cos p\pi h - 2\cos q\pi h, \qquad p, q = 1, \dots, N-1 .

At N=40N = 40 the smallest is 0.012330.01233 (the smooth hump), the largest 7.98777.9877 (the checkerboard), and the condition number κ=(1+cos⁡πh)/(1−cos⁡πh)\kappa = (1+\cos\pi h)/(1-\cos\pi h) is 647.8647.8.

Stopping rule. The residual is the largest change one Jacobi sweep would still make, max⁡∣14(uE+uW+uN+uS+h2f)−uC∣=max⁡∣b−Au∣/4\max\lvert\tfrac14(u_E+u_W+u_N+u_S+h^2f) - u_C\rvert = \max\lvert\mathbf b - A\mathbf u\rvert/4. We stop below 10−610^{-6}, absolute: the Laplace lesson’s definition, so shared numbers agree. Unless stated, the problem is that plate (top edge 11, others 00, interior starting at zero).

Splitting: Jacobi and Gauss–Seidel

Write A=D−L−UA = D - L - U with DD the diagonal (4I4I) and LL, UU the negated strictly lower and upper parts. Then Au=bA\mathbf u = \mathbf b reads Du=(L+U)u+bD\mathbf u = (L+U)\mathbf u + \mathbf b. Evaluate the right side at the old iterate:

uk+1=BJ uk+D−1b,BJ=D−1(L+U)=I−14A.\mathbf u^{k+1} = B_J\,\mathbf u^k + D^{-1}\mathbf b, \qquad B_J = D^{-1}(L+U) = I - \tfrac14 A .

That is Jacobi. Gauss–Seidel uses each new value the moment it exists: a node’s west and south neighbours are already new, so (D−L)uk+1=Uuk+b(D-L)\mathbf u^{k+1} = U\mathbf u^k + \mathbf b and BGS=(D−L)−1UB_{GS} = (D-L)^{-1}U. Subtracting the exact solution from either update gives ek+1=Bek\mathbf e^{k+1} = B\mathbf e^k, so ek=Bke0\mathbf e^k = B^k\mathbf e^0. The error shrinks from every start exactly when the spectral radius ρ(B)\rho(B) is below 11, and in the long run by ρ\rho per sweep; a factor 10−610^{-6} takes about 13.8/(−ln⁡ρ)13.8/(-\ln\rho) sweeps.

For Jacobi the eigenvalues are free: BJ=I−A/4B_J = I - A/4 shares AA‘s eigenvectors and has eigenvalues 12(cos⁡pπh+cos⁡qπh)\tfrac12(\cos p\pi h + \cos q\pi h). The largest is at p=q=1p = q = 1, the smallest at the checkerboard:

ρJ=cos⁡πh≈1−π2h22,checkerboard factor −cos⁡πh.\rho_J = \cos\pi h \approx 1 - \frac{\pi^2h^2}{2}, \qquad \text{checkerboard factor } -\cos\pi h .

At N=40N = 40, ρJ=0.99692\rho_J = 0.99692 and 1/(1−ρJ)=3241/(1-\rho_J) = 324, the factor by which Jacobi’s residual under-reports its error. Note the second statement: Jacobi multiplies the most oscillatory error by nearly −1-1 and almost never removes it. For Gauss–Seidel the standard result (Young, lexicographic order; from memory) is ρGS=ρJ2\rho_{GS} = \rho_J^2: about half the sweeps. Red-black ordering gives a proof.

Red-black ordering

Colour the nodes like a checkerboard, red where i+ji + j is even. Every neighbour of a red node is black and vice versa, so all red nodes can be updated at once (none reads another red node), then all black nodes from the fresh reds. A lexicographic sweep is a recurrence; a red-black sweep is two fully parallel passes, which is why GPU solvers use it.

Is it as fast? In red-black order the Jacobi matrix is (0PQ0)\begin{pmatrix}0 & P\\ Q & 0\end{pmatrix}, with PP averaging black neighbours into red nodes and QQ the reverse. A red-black sweep sets rnew=Pb\mathbf r^{\text{new}} = P\mathbf b, then bnew=Qrnew=QPb\mathbf b^{\text{new}} = Q\mathbf r^{\text{new}} = QP\mathbf b. The square of the block matrix is diag⁡(PQ,QP)\operatorname{diag}(PQ, QP), so the eigenvalues of QPQP are the squares of Jacobi’s: ρ=cos⁡2πh\rho = \cos^2\pi h. At N=40N = 40 both orderings contract by 0.99380.9938 per sweep (measured below), though the counts differ, 11661166 lexicographic and 12681268 red-black: a difference in the start, not the end.

SOR and the optimal factor

Successive over-relaxation goes further than the neighbour average: u←u+ω(average−u)u \leftarrow u + \omega(\text{average} - u) with 1<ω<21 \lt \omega \lt 2 (ω=1\omega = 1 is Gauss–Seidel). Young’s result for the model problem (from memory; the lab tests it) is that with μ=cos⁡πh\mu = \cos\pi h the SOR eigenvalues satisfy (λ+ω−1)2=λω2μ2(\lambda + \omega - 1)^2 = \lambda\omega^2\mu^2. The roots merge at the best ω\omega, and beyond it become a complex pair of modulus ω−1\omega - 1:

ωopt=21+sin⁡πh,ρSOR=ωopt−1≈1−2πh.\omega_{\text{opt}} = \frac{2}{1+\sin\pi h}, \qquad \rho_{SOR} = \omega_{\text{opt}} - 1 \approx 1 - 2\pi h .

The gap shrinks like hh, not h2h^2. At N=40N = 40, ωopt=1.8545\omega_{\text{opt}} = 1.8545 and ρ=0.8545\rho = 0.8545. Sweeps to residual 10−610^{-6} on the plate:

ω\omegapredicted factorsweeps
1.001.00 (Gauss–Seidel)0.993840.9938411661166
1.501.500.981420.98142393393
1.701.700.963810.96381210210
1.851.850.885610.885619595
1.85451.8545 (optimal)0.854500.854509696
1.901.900.900000.90000159159
1.951.950.950000.95000262262

The curve drops steeply to the optimum and rises only linearly after it, so when unsure, overshoot. The minimum is flat (9595 at 1.851.85, which is just below the optimum and on the formula’s root branch, against 9696 at it). At the optimum, 9696 exceeds the asymptotic estimate 13.8/0.157=8813.8/0.157 = 88, because near it the iteration is nearly defective and has a long transient: SOR’s residual at sweep 55 is 0.3320.332, above its start. The formula needs a square with Dirichlet data; on odd domains the best ω\omega is unknown, one reason to want CG.

The lab: five solvers on one problem

◆ Interactive Race Jacobi, Gauss-Seidel, red-black GS, SOR and conjugate gradients on one Poisson problem, and watch the error and residual fields

Loading simulation…

Each solver runs from the same start to residual 10−610^{-6}. The readout gives iterations to tolerance, the predicted factor, and the measured factor, the geometric mean of the residual ratio over the last half of the run. At N=40N = 40 on the plate: Jacobi 23092309 (predicted 0.996920.99692, measured 0.996910.99691), Gauss–Seidel 11661166 (0.993840.99384, 0.993850.99385), red-black 12681268 (0.993840.99384, 0.993840.99384), SOR at 1.851.85 9595 (0.885610.88561, 0.831530.83153), CG 8484 (bound 0.924390.92439, measured 0.816440.81644). SOR’s measurement is low because 9595 sweeps is a short run for a method with a transient: to residual 10−1210^{-12} it reads 0.882940.88294.

Counting: 1/h21/h^2 against 1/h1/h

The button measure scaling runs N=10,20,40,80N = 10, 20, 40, 80 on the plate, SOR at its own ωopt\omega_{\text{opt}}, and prints the slope of log count against log NN:

solverN=10N = 10202040408080slope
Jacobi19719768768723092309744974491.751.75
Gauss–Seidel10210235035011661166374537451.731.73
red-black GS10610637237212681268417441741.771.77
SOR, ωopt\omega_{\text{opt}}2626494996961871870.950.95
CG2222434384841641640.970.97

SOR and CG sit near slope 11. The Jacobi family sits at 1.751.75, not 22, with per-doubling ratios 3.53.5, 3.43.4, 3.23.2. The count is L/(−ln⁡ρ)L/(-\ln\rho) with L=ln⁡(rslow/10−6)L = \ln(r_{\text{slow}}/10^{-6}), and rslowr_{\text{slow}}, the slowest mode’s initial residual, is (1−ρ)(1-\rho) times its error and so falls like h2h^2: with an absolute tolerance LL drops by ln⁡4\ln 4 per doubling. The rate itself is clean: Jacobi’s measured gap −ln⁡(factor)-\ln(\text{factor}) is 0.050690.05069, 0.012390.01239, 0.0030900.003090, 0.0007720.000772, falling by 4.094.09, 4.014.01, 4.004.00 per doubling, and Gauss–Seidel’s is about twice that (1.981.98 to 2.002.00). Counts follow the 1/h21/h^2 law of the rate up to a logarithm.

Error against residual, and the seed of multigrid

Mode (p,q)(p,q) of the error is multiplied each sweep by its own eigenvalue of BB. The mechanism is local: the update replaces a node by its neighbours’ average, so a node that sticks out (rough error) is corrected at once, while a node already near the average (smooth error) barely moves. The change a sweep makes, the residual, is AeA\mathbf e, small exactly for smooth e\mathbf e. A small residual is not a small error.

The lab’s random start shows it. Take the source-and-sink problem at N=40N = 40 with noise in the interior. The error energy in rough sine modes (pp or qq above N/2N/2) starts at 49.4%49.4\%:

afterJacobiGauss–Seidelred-blackSOR at 1.851.85CG
55 iterations6.5%6.5\%below 0.05%0.05\%below 0.05%0.05\%50.7%50.7\%0.1%0.1\%
2020 iterations2.2%2.2\%below 0.05%0.05\%below 0.05%0.05\%47.1%47.1\%below 0.05%0.05\%

Gauss–Seidel flattens the rough part in five sweeps. Jacobi keeps a tail (1.6%1.6\% at sweep 200200) of near-checkerboard modes with factor near −1-1, so its residual is 0.2940.294 at sweep 2020 against Gauss–Seidel’s 0.006360.00636 (start 1.681.68). SOR at 1.851.85 does not smooth at all: fast on smooth modes, nearly blind to rough ones. What remains is the lowest hump: the cosine between the error and sin⁡πxsin⁡πy\sin\pi x\sin\pi y rises for Gauss–Seidel from 0.2490.249 to 0.5000.500 at sweep 2020 and 0.9320.932 at sweep 200200.

Conjugate gradients

Relaxation uses only the current iterate; conjugate gradients (CG) uses all earlier ones. For a symmetric positive definite AA, with r=b−Au\mathbf r = \mathbf b - A\mathbf u and direction p0=r0\mathbf p_0 = \mathbf r_0:

αk=rkTrkpkTApk,uk+1=uk+αkpk,rk+1=rk−αkApk,βk=rk+1Trk+1rkTrk,pk+1=rk+1+βkpk.\alpha_k = \frac{\mathbf r_k^T\mathbf r_k}{\mathbf p_k^TA\mathbf p_k}, \quad \mathbf u_{k+1} = \mathbf u_k + \alpha_k\mathbf p_k, \quad \mathbf r_{k+1} = \mathbf r_k - \alpha_kA\mathbf p_k, \quad \beta_k = \frac{\mathbf r_{k+1}^T\mathbf r_{k+1}}{\mathbf r_k^T\mathbf r_k}, \quad \mathbf p_{k+1} = \mathbf r_{k+1} + \beta_k\mathbf p_k .

A step is one product ApA\mathbf p (a stencil pass like a sweep), a few dot products, and no ω\omega. The directions make each step the best over everything tried so far. The result worth knowing (from memory, not derived) is the energy-norm bound

∥ek∥A≤2(κ−1κ+1)k∥e0∥A.\lVert\mathbf e_k\rVert_A \le 2\left(\frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\right)^{k}\lVert\mathbf e_0\rVert_A .

Jacobi’s factor is 1−O(1/κ)1 - O(1/\kappa), CG’s 1−O(1/κ)1 - O(1/\sqrt\kappa). Here κ=cot⁡2(πh/2)≈4/(π2h2)\kappa = \cot^2(\pi h/2) \approx 4/(\pi^2h^2), so κ≈2/(πh)\sqrt\kappa \approx 2/(\pi h) and the factor is about 1−πh1 - \pi h: about 1/h1/h iterations with nothing to tune. At N=40N = 40 the bound factor is 0.924390.92439 and the measured residual contraction 0.816440.81644; the bound is a worst case for another norm, and a run to 10−1210^{-12} measures 0.759840.75984, so read the gap as pessimism, not contradiction. The counts: 8484 iterations against SOR’s 9696 at its optimal ω\omega, slope 0.970.97. CG needs only a symmetric positive definite matrix, and with a multigrid preconditioner (from memory) it is a production pressure solver.

Stam’s lin_solve

Stam’s routine does a fixed 2020 Gauss–Seidel sweeps, no tolerance: xij←(xij0+a(xi−1,j+xi+1,j+xi,j−1+xi,j+1))/cx_{ij} \leftarrow \big(x^0_{ij} + a(x_{i-1,j} + x_{i+1,j} + x_{i,j-1} + x_{i,j+1})\big)/c. For diffusion (11.11 Stam's Stable Fluids, Step by Step) a=r=νΔt/h2a = r = \nu\Delta t/h^2, c=1+4rc = 1 + 4r, and Jacobi’s factor is 4r1+4rcos⁡πh\tfrac{4r}{1+4r}\cos\pi h, below 11 by 1/(1+4r)1/(1+4r) at any grid size, so 2020 sweeps are plenty for small rr (Problem 2). For pressure, a=1a = 1, c=4c = 4: our Poisson problem with the slow factor and a start of p=0p = 0. Twenty Gauss–Seidel sweeps from zero on our N=40N = 40 plate leave:

  • a residual of 6.67×10−36.67\times10^{-3}, 2.67%2.67\% of the start (0.250.25) and about 66706670 times our tolerance;
  • a largest error of 0.5730.573 against 0.94960.9496 at the start: 60%60\% of the error remains.

This is the 2020-sweep picture of 11.10 The Projection Method for Incompressible Flow, where the cylinder’s influence had barely spread. The mechanism is the table above: 2020 sweeps remove the rough, local part of the residual (divergence one cell can see) and hardly touch the smooth part, so incompressibility is restored locally while the large-scale pressure that steers the stream around the body is not built. Games accept it because the viewer sees swirls, not mass budgets; the price, measured in 11.11 Stam's Stable Fluids, Step by Step, is that finer grids kept less vorticity.

Worked example: three radii on a 3×33\times3 grid

For N=4N = 4 (h=14h = \tfrac14, nine unknowns) the formulas give ρJ=cos⁡(π/4)=0.7071\rho_J = \cos(\pi/4) = 0.7071, ρGS=0.5\rho_{GS} = 0.5, ωopt=2/(1+sin⁡(π/4))=1.1716\omega_{\text{opt}} = 2/(1+\sin(\pi/4)) = 1.1716 and ρSOR=0.1716\rho_{SOR} = 0.1716. The playground builds the matrix and finds the three spectral radii numerically.

🐍 PythonSpectral radii of the real iteration matrices, N = 4
⌘/Ctrl + Enter

The exercise

Implement Jacobi and Gauss–Seidel on the plate and measure what the theory predicts.

🧪 Coding exerciseExercise: Jacobi and Gauss-Seidel, and their scaling
⌘/Ctrl + Enter

The counts for N=8,16,32N = 8, 16, 32 are 131,461,1569131, 461, 1569 (Jacobi) and 68,236,79468, 236, 794 (Gauss–Seidel). They grow by 3.53.5, 3.43.4 per doubling in both cases, while the rate ratios are 4.064.06, 4.034.03 (Jacobi) and 4.084.08, 4.024.02 (Gauss–Seidel): the approach to 44 is in the rate.

Concept checks

✅ Concept check

Jacobi needs $2309$ sweeps on the $40$-interval plate. Roughly how many does optimal SOR need there?

✅ Concept check

Why can every red node of a red-black sweep be updated simultaneously?

✅ Concept check

After $20$ Gauss–Seidel sweeps from zero on the plate, the residual is $6.67\times10^{-3}$ and the largest error has fallen from $0.9496$ to $0.573$. What does this say about stopping at $20$ sweeps?

✅ Concept checkselect all that apply

Select all that are true of conjugate gradients on the model problem.

Problems

✏️ Pen & paperThree radii on a three-node rod●○○

The 1D problem with n=3n = 3 interior nodes (h=14h = \tfrac14) has A=tridiag⁡(−1,2,−1)A = \operatorname{tridiag}(-1, 2, -1). Find ρJ\rho_J, ρGS\rho_{GS}, ωopt\omega_{\text{opt}}, ρSOR\rho_{SOR}, and the sweeps to cut the error by 10−610^{-6} for each.

Show worked solution

BJ=I−A/2B_J = I - A/2 has eigenvalues cos⁡(kπ/4)\cos(k\pi/4): 0.70710.7071, 00, −0.7071-0.7071. So ρJ=0.7071\rho_J = 0.7071, ρGS=0.5\rho_{GS} = 0.5, ωopt=1.1716\omega_{\text{opt}} = 1.1716, ρSOR=0.1716\rho_{SOR} = 0.1716. Sweeps 13.82/(−ln⁡ρ)13.82/(-\ln\rho): 39.939.9, 19.919.9, 7.87.8, about 4040, 2020, 88.

✏️ Pen & paperHow many sweeps does a diffusion solve need?●●○

For (1+4r)uC−r(uE+uW+uN+uS)=bC(1 + 4r)u_C - r(u_E + u_W + u_N + u_S) = b_C, show that Jacobi has ρ=4r1+4rcos⁡πh\rho = \tfrac{4r}{1+4r}\cos\pi h. For N=40N = 40, r=1r = 1, find the reduction from 2020 Jacobi sweeps, and the largest rr for which 2020 Gauss–Seidel sweeps reach 10−610^{-6}.

Show worked solution

uCnew=4r1+4r⋅uE+uW+uN+uS4+…u_C^{\text{new}} = \frac{4r}{1+4r}\cdot\frac{u_E+u_W+u_N+u_S}{4} + \dots, and the neighbour average has largest eigenvalue magnitude cos⁡πh\cos\pi h. At r=1r = 1: 0.8×0.996917=0.797530.8\times0.996917 = 0.79753, and 0.7975320=0.01080.79753^{20} = 0.0108. Gauss–Seidel gives ρJ40≤10−6\rho_J^{40} \le 10^{-6}, so ρJ≤0.70795\rho_J \le 0.70795, 4r1+4r≤0.71013\frac{4r}{1+4r} \le 0.71013, 4r≤2.4504r \le 2.450, r≤0.612r \le 0.612.

✏️ Pen & paperA million unknowns●●○

For N=1000N = 1000, estimate the sweeps to reduce the slowest error by 10−610^{-6} for Jacobi and for optimal SOR.

Show worked solution

−ln⁡cos⁡πh=4.935×10−6-\ln\cos\pi h = 4.935\times10^{-6}, so Jacobi needs 13.82/4.935×10−6=2.80×10613.82/4.935\times10^{-6} = 2.80\times10^6 sweeps. ωopt=1.99374\omega_{\text{opt}} = 1.99374, ρ=0.99374\rho = 0.99374, −ln⁡ρ=6.283×10−3-\ln\rho = 6.283\times10^{-3}: about 21992199 sweeps, 12701270 times fewer. At about 5×1065\times10^6 operations a sweep that is 101010^{10} against 1.4×10131.4\times10^{13}.

Key Takeaways

  • The five-point Poisson problem is a sparse system: 15211521 unknowns and 74497449 nonzeros at N=40N = 40. We iterate because the inverse is dense.
  • A=D−L−UA = D - L - U gives ek+1=Bek\mathbf e^{k+1} = B\mathbf e^k. Jacobi’s ρ=cos⁡πh\rho = \cos\pi h follows from the Laplacian eigenvalues; Gauss–Seidel’s cos⁡2πh\cos^2\pi h and SOR’s ωopt−1\omega_{\text{opt}} - 1 are from memory, and the lab confirms them.
  • Red-black ordering makes each half-sweep parallel and keeps cos⁡2πh\cos^2\pi h.
  • On the plate at N=40N = 40, residual 10−610^{-6}: Jacobi 23092309, Gauss–Seidel 11661166, red-black 12681268, SOR at 1.851.85 9595, CG 8484. The rate quarters per doubling of NN; counts show slope 1.751.75 for the Jacobi family and about 11 for SOR and CG.
  • Relaxation kills rough error fast and smooth error slowly, and a small residual is not a small error. Jacobi leaves checkerboard error and SOR leaves all rough error; Gauss–Seidel smooths.
  • CG needs about 1/h1/h iterations with no parameter.
  • Twenty Gauss–Seidel sweeps from zero leave 2.67%2.67\% of the residual and 60%60\% of the error on the plate: a local fix, not the global solution.
  • Next: 10.11 2D Grids, Boundary Conditions & Staggered (MAC) Grids builds the divergence and gradient stencils whose product is this Laplacian, with its wall rows; the multigrid lesson (10.9 Multigrid) attacks the smooth error.
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.

Where this leads

These later lessons build directly on this one: