Linear Systems Summary

Numerical Analysis · Axiom Academy

SUMMARY Linear Systems: Key Takeaways Essential concepts for solving Ax = b numerically Gaussian Elimination: Transforms Ax = b into upper triangular form Ux = c, then solves by back substitution. Use partial pivoting to ensure numerical stability. LU Decomposition: Factors A = LU once (O(n³)), then solves with any b in O(n²). Essential when solving with multiple right-hand sides. Cholesky (A = LLᵀ): For symmetric positive definite matrices only. Twice as fast as LU, half the storage, inherently stable without pivoting. Condition Number κ(A): Measures sensitivity of solution to input errors. Large κ(A) means small perturbations in b cause large changes in x. Rule of Thumb: You lose approximately log₁₀(κ) decimal digits of accuracy. If κ(A) ≈ 10⁸ with double precision, expect only 8 correct digits. Ill-conditioned signs: Nearly parallel rows/columns, matrix close to singular, very different row magnitudes. Jacobi: Uses only old iteration values. Embarrassingly parallel but slow. Formula: compute all x_i^(k+1) from x^(k) simultaneously. Gauss-Seidel: Uses new values immediately. Sequential but ~2× faster than Jacobi. Better memory efficiency. SOR: Adds relaxation parameter ω to Gauss-Seidel. Optimal ω can dramatically accelerate convergence for structured problems. Key Criterion: Iteration x^(k+1) = Gx^(k) + c converges ⟺ ρ(G) < 1 (spectral radius less than 1). Diagonal Dominance: |a_ii| > Σ|a_ij| guarantees Jacobi and Gauss-Seidel converge. Not necessary, but easy to check.

This is the written version of the interactive lesson above. See the full Numerical Analysis course.