Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 68 ยท Linear Algebra and Numerical Methods

LU Decomposition and Iterative Solvers (Jacobi, Gauss-Seidel, SOR)

Factor a matrix as A = LU, solve many right-hand sides cheaply, and compare direct solving with the Jacobi, Gauss-Seidel and SOR iterations, including convergence conditions, in Python.

There are two big families of methods for solving A x = b.

  • Direct methods do a fixed amount of work and return the answer (up to round-off). Gaussian elimination and its organized form, LU decomposition, belong here.
  • Iterative methods start from a guess and improve it step by step until the change is tiny. Jacobi, Gauss-Seidel and SOR belong here. They shine on huge, sparse systems such as the finite-difference grids behind heat-flow and PDE solvers.

This lesson builds each method in a few lines and measures how they behave.

LU decomposition

Gaussian elimination turns A into an upper-triangular matrix U by subtracting multiples of rows. If you save the multipliers you used, they form a unit lower-triangular matrix L (ones on the diagonal), and then

Text
A = L U

That is the LU decomposition. To solve A x = b:

  1. Solve L y = b by forward substitution (top row first).
  2. Solve U x = y by back substitution (bottom row first).

Why bother when elimination already solves the system? Because the expensive part, the factorization (about 2n^3/3 operations), depends only on A. Each additional right-hand side costs just O(n^2) for the two triangular solves. Engineers solve the same structure with many loads, time steps or sensor vectors, so factor once and reuse.

Other things you get for free:

  • det(A) = det(L) det(U) = product of U's diagonal (times -1 for each row swap).
  • The inverse: solve for each column of the identity.
  • With partial pivoting (swapping rows to keep the pivot large) you get P A = L U, where P is a permutation matrix. Real libraries always pivot; without it a zero pivot breaks the method and a tiny pivot ruins accuracy.
Python LU decomposition from scratch, with and without pivoting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why iterate?

For a dense 1000 x 1000 system, LU is perfect. For a 3-D heat model with a million grid points, the matrix has a million rows but only about seven non-zero entries per row. Factoring it fills in zeros and needs gigabytes. Iterative methods only ever multiply by A, which is cheap for sparse matrices, and they can stop as soon as the answer is accurate enough.

All three methods below split A = D + L + U, where D is the diagonal and L, U are the strictly lower and upper parts (not the LU factors). Each equation i is solved for x_i:

x_i = (b_i - sum over j != i of a_ij x_j) / a_ii

  • Jacobi uses only the old vector on the right-hand side: x_new_i = (b_i - sum_{j != i} a_ij x_old_j) / a_ii. All components can be updated in parallel.
  • Gauss-Seidel uses each new value as soon as it is computed: components 1..i-1 are new, i+1..n are still old. It usually converges about twice as fast.
  • SOR (successive over-relaxation) takes the Gauss-Seidel value and pushes past it: x_new_i = (1 - w) x_old_i + w x_GS_i with a relaxation factor 1 < w < 2. A good w can cut the iteration count by an order of magnitude; w = 1 is plain Gauss-Seidel.

When do they converge? A sufficient condition is strict diagonal dominance: |a_ii| > sum over j != i of |a_ij| in every row. Gauss-Seidel also converges for symmetric positive-definite matrices. The exact condition is that the spectral radius (largest absolute eigenvalue) of the iteration matrix is below 1; the smaller it is, the faster the convergence.

Python Jacobi, Gauss-Seidel and SOR side by side

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On the Poisson matrix the numbers tell the usual story: Gauss-Seidel needs about half the iterations of Jacobi, and SOR with a well-chosen w needs a small fraction of either. The spectral radius is close to 1, which is why the plain methods are slow on fine grids; real solvers use conjugate gradients or multigrid, which build on the same ideas.

Choosing a method

Situation Reasonable choice
Small or medium dense system LU with pivoting (np.linalg.solve)
Same matrix, many right-hand sides Factor once, reuse the LU
Huge sparse system Iterative method (Gauss-Seidel/SOR for teaching; conjugate gradient or multigrid in practice)
Matrix not diagonally dominant Check the spectral radius first, or use a direct method
Need maximum parallelism Jacobi (each component independent)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In A = LU, what do the entries of L below the diagonal store?

    Each multiplier subtracted from a row during elimination becomes an entry of the unit lower-triangular factor L.
  2. 2. Why is LU decomposition useful for many right-hand sides?

    The O(n^3) factorization depends only on A. Each new b needs only a forward and a back substitution.
  3. 3. Which condition guarantees that Jacobi and Gauss-Seidel converge?

    If |a_ii| exceeds the sum of the other absolute entries in every row, both methods converge from any starting guess.
  4. 4. How does Gauss-Seidel differ from Jacobi?

    Jacobi uses only the previous iterate; Gauss-Seidel uses the freshest values available, which usually speeds up convergence.
  5. 5. What does the relaxation factor w = 1 give in SOR?

    SOR blends the old value with the Gauss-Seidel value using weight w. With w = 1 it is exactly Gauss-Seidel.

Summary

  • A = LU records elimination: forward substitution with L, back substitution with U; pivoting gives PA = LU.
  • Factor once, solve many times; determinant and inverse come from the same factors.
  • Jacobi updates from old values, Gauss-Seidel from the newest ones, SOR over-relaxes Gauss-Seidel with 1 < w < 2.
  • Strict diagonal dominance guarantees convergence; the spectral radius of the iteration matrix sets the speed.
  • Direct methods suit dense systems; iterative ones suit huge sparse systems.

Next: Eigenvalues and Eigenvectors in Engineering.