Gauss–Seidel, Jacobi and LU Calculator
Solve a system of linear equations by Gauss–Seidel or Jacobi iteration, with the diagonal-dominance test and the iteration table, or by LU decomposition (Doolittle or Crout) in exact fractions.
About the Gauss–Seidel, Jacobi and LU Calculator
Jacobi iteration solves each equation for its own unknown and updates all of them together from the previous round. Gauss–Seidel uses each new value as soon as it is found, so it usually converges about twice as fast. Both converge when A is diagonally dominant: in every row, the diagonal entry is at least as large (in size) as the others added together.
LU decomposition writes A = LU with L lower and U upper triangular; then Ax = b becomes Ly = b (solved from the top) and Ux = y (solved from the bottom). Doolittle's method puts 1s on L's diagonal, Crout's on U's.
The formula
Gauss–Seidel: xᵢ⁽ᵏ⁺¹⁾ = (bᵢ − Σⱼ<ᵢ aᵢⱼxⱼ⁽ᵏ⁺¹⁾ − Σⱼ>ᵢ aᵢⱼxⱼ⁽ᵏ⁾)/aᵢᵢ
Worked example
10x + y + z = 12, 2x + 10y + z = 13, 2x + 2y + 10z = 14
- Diagonally dominant, so start from (0, 0, 0)
- Round 1: x = 1.2, y = 1.06, z = 0.948
- It settles at x = y = z = 1
Questions people ask
Why doesn't my iteration converge?
If A isn't diagonally dominant, the iteration may run away. Reorder the equations so the largest coefficient in each row is on the diagonal.
When does LU decomposition fail?
If a zero appears on the diagonal during the factorisation (a zero pivot). Swapping the order of the equations usually fixes it.