Linear Systems

Jacobi Iteration

Solve a diagonally dominant linear system iteratively: update all unknowns simultaneously using values from the previous iteration. Example: 4x+y=9; x+4y=6; converges to x=2, y=1.

Convergence is guaranteed for strictly diagonally dominant systems.

jacobi-iteration The Jacobi method isolates each variable on the diagonal and updates all unknowns simultaneously from the previous iterate: x_{k+1} = (b1 - a12·y_k) / a11 y_{k+1} = (b2 - a21·x_k) / a22

Example

Use previous iterates to approximate the solution.

highlighted = computed this step

Step 1 — Set up

Set up the Jacobi system.

4x+y=9x+4y=64 x+y= 9 \quad x+ 4 y= 6

Step 2 — Iteration 1

Jacobi iteration 1: use only the previous x and y.

kxy00019432\begin{array}{ccc}\text{k} & \text{x} & \text{y} \\ 0 & 0 & 0 \\ \hlmath{1} & \hlmath{\frac{9}{4}} & \hlmath{\frac{3}{2}}\end{array}

Step 3 — Iteration 2

Jacobi iteration 2: use only the previous x and y.

kxy0001943221581516\begin{array}{ccc}\text{k} & \text{x} & \text{y} \\ 0 & 0 & 0 \\ 1 & \frac{9}{4} & \frac{3}{2} \\ \hlmath{2} & \hlmath{\frac{15}{8}} & \hlmath{\frac{15}{16}}\end{array}

Step 4 — Iteration 3

Jacobi iteration 3: use only the previous x and y.

kxy00019432215815163129643332\begin{array}{ccc}\text{k} & \text{x} & \text{y} \\ 0 & 0 & 0 \\ 1 & \frac{9}{4} & \frac{3}{2} \\ 2 & \frac{15}{8} & \frac{15}{16} \\ \hlmath{3} & \hlmath{\frac{129}{64}} & \hlmath{\frac{33}{32}}\end{array}

Step 5 — Result

Compare the last Jacobi iterate with the true solution.

kxy00019432215815163129643332x→2, y→1\begin{array}{ccc}\text{k} & \text{x} & \text{y} \\ 0 & 0 & 0 \\ 1 & \frac{9}{4} & \frac{3}{2} \\ 2 & \frac{15}{8} & \frac{15}{16} \\ 3 & \frac{129}{64} & \frac{33}{32}\end{array} \quad x\to \hl{2} ,\ y\to \hl{1}