Recipe

Run the Jacobi method to a stopping tolerance

Use when: you have a square system A\mathbf{x}=\mathbf{b} with every diagonal entry a_{ii}\ne0 and a stated tolerance \varepsilon

Goal: an approximate solution vector whose change from the previous sweep is under \varepsilon, built entirely from sweeps that each depend only on the sweep before it

Taught in The Jacobi method

1. 1

   Check that a_{ii}\ne0 for every row i. If a diagonal entry is zero, reorder the equations (swap rows). Do this until every diagonal position is nonzero, before doing anything else.

   Example

   For 4x_1+x_2-x_3=6,\ 2x_1+6x_2+x_3=14,\ x_1-x_2+5x_3=-1: the diagonal entries are 4, 6, 5. All are nonzero, so no reordering is needed.

   ⚡ Shortcut

   Before running a single sweep, check whether the matrix is diagonally dominant. Does \lvert a_{ii}\rvert exceed the sum of the absolute values of every OTHER entry in row i, for every row? For this system: row 1, 4>|1|+|-1|=2 ✓; row 2, 6>|2|+|1|=3 ✓; row 3, 5>|1|+|-1|=2 ✓. Every row passes. So Section 5 (this course's own precise statement) GUARANTEES Jacobi converges from any starting guess, before a single sweep is run. This check costs nothing beyond reading the matrix's own entries. Failing it doesn't prove divergence -- it only means this particular shortcut can't promise convergence (Section 5 explains exactly why).

   Why: the update formula for x_i divides by a_{ii}. A zero there makes the formula undefined. Even a very small (but nonzero) entry risks the same round-off amplification Chapter 7, Section 1 already warned a tiny pivot causes.

2. 2

   For each i from 1 to n, compute x_i^{(k+1)}=\dfrac{1}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right). Read every x_j on the right-hand side from \mathbf{x}^{(k)} -- the iterate BEFORE this sweep started, never a value computed earlier in this same sweep.

   Example

   From \mathbf{x}^{(0)}=(0,0,0): x_1^{(1)}=\frac{1}{4}(6-0+0)=1.5, x_2^{(1)}=\frac{1}{6}(14-2(0)-0)=\frac{14}{6}\approx2.333, x_3^{(1)}=\frac{1}{5}(-1-0+0)=-0.2. Every one of these three computations used only \mathbf{x}^{(0)}'s entries, never each other.

   Why: this formula is exactly Section 2's own rearrangement of equation i, evaluated at the current guess. It makes the next guess at least consistent with equation i, even though the other equations' own guesses haven't caught up yet.

3. 3

   Collect x_1^{(k+1)},\ldots,x_n^{(k+1)} into \mathbf{x}^{(k+1)} only once ALL of them have been computed from Step 2. Never overwrite an entry of the working guess mid-sweep.

   Example

   \mathbf{x}^{(1)}=(1.5,\ 2.333,\ -0.2) becomes the guess for sweep 2 only after all three of x_1^{(1)}, x_2^{(1)}, x_3^{(1)} from Step 2 are known. None of them was used to help compute either of the other two.

   Why: this is the entire content of "Jacobi" as opposed to any other method. Section 3 builds a DIFFERENT method from the identical formula in Step 2, entirely by skipping this step's own restriction.

4. 4

   Compute \lVert\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\rVert_\infty, the largest single-component change. If it's below \varepsilon, stop -- \mathbf{x}^{(k+1)} is the answer. Otherwise, go back to Step 2 with \mathbf{x}^{(k+1)} as the new current iterate.

   Example

   Continuing from \mathbf{x}^{(1)}=(1.5,\,2.333,\,-0.2): Step 2 gives \mathbf{x}^{(2)}=(0.867,\,1.867,\,-0.033), so \lVert\mathbf{x}^{(2)}-\mathbf{x}^{(1)}\rVert_\infty=\max(0.633,\,0.467,\,0.167)=0.633. That is still above a tolerance of \varepsilon=0.2, so sweep again: \mathbf{x}^{(3)}=(1.025,\,2.05,\,0), giving \lVert\mathbf{x}^{(3)}-\mathbf{x}^{(2)}\rVert_\infty=\max(0.158,\,0.183,\,0.033)=0.183<0.2. Stop.

   Why: this is the only place the recipe checks whether it's actually done. Skipping it -- running a fixed number of sweeps chosen by guesswork -- either wastes sweeps past the point they were needed, or stops before the tolerance is really met.