THE GARDEN

Linear systems: direct and iterative methods

Updated 11 Oct 2026

• •

  System

  • •

    a linear system has the form $Ax=b$.

• •

  Elimination and factorization

  • •

    gaussian elimination uses row operations to reach upper-triangular form, followed by back substitution.

  • •

    partial pivoting swaps in a large available pivot to reduce unstable division; it does not fix an ill-conditioned problem.

  • •

    a zero pivot may require a row exchange and does not by itself prove there is no solution.

  • •

    Gauss–Jordan continues to reduced row-echelon form.

  • •

    LU factorization can be reused for multiple right-hand sides.

  • •

    Cholesky applies to symmetric positive-definite matrices.

  • •

    the Thomas algorithm efficiently solves tridiagonal systems.

• •

  Jacobi and Gauss–Seidel

  • •

    Jacobi updates each component using only the previous iterate.

  • •

    Gauss–Seidel uses newly computed components immediately.

  • •

    Strict row diagonal dominance -> sufficient convergence condition for these methods, not a necessary one.

• •

  Relaxation and conjugate gradient

  • •

    successive over-relaxation (SOR) adds a relaxation factor to an iterative update.

  • •

    Conjugate gradient -> designed for symmetric positive-definite systems.

  • •

    convergence depends on the iteration or system structure; a method name alone does not guarantee it.

• •

  Sparse systems and preconditioning

  • •

    sparse matrices contain mostly zeros and can be stored and processed efficiently.

  • •

    preconditioning changes the system to improve iterative convergence.

  • •

    finite-difference discretization of differential equations often produces sparse systems.

  • •

    Finite differences -> approximate a second derivative from neighboring grid values

  • •

    Grid application -> produces a banded system.

• •

  Matrix norm and condition

  • •

    Matrix norm -> measures a matrix’s size or action on vectors.

  • •

    the condition number estimates sensitivity of a solution to perturbations in data.

◌ Explore connections in Graph view