Solving Linear Systems

Summary

This path solves linear algebraic systems $Ax=b$ with $A\in {\mathbb{R}}^{n\times n}$ . Direct methods factor or triangularize $A$ ; iterative methods build a sequence $x^{(k)}\to x$ .

Prerequisites

• Matrix–vector products and elementary row operations
• Norms and the idea of residual $r=b-Ax$

Linear Maps (Not Affine Lines)

A map $T$ is linear when

for all vectors $u,v$ and scalars $c$ .^[1]

In particular, $T(x)=ax+b$ with $b\ne 0$ is affine, not linear, because $T(0)=b\ne 0$ . Linear systems in this path are of the form $Ax=b$ , where the unknown enters linearly through the matrix $A$ . (The system is still called linear when $b\ne 0$ .)

Learning Order

1. Direct Methods - Triangular System — forward/back substitution
2. Gaussian Elimination — triangularization + back substitution
3. LU Factorization — $A=LU$ or $PA=LU$
4. Iterative Methods — fixed-point form $x^{(k+1)}=T{x}^{(k)}+c$
5. Gauss-Jacobi Method
6. Gauss-Seidel Method
7. Sufficient Convergence Condition for Gauss-Jacobi

Topic Map

• Numerical Methods/Linear Systems/Solving Linear Systems
  • LU Factorization
  • Gaussian Elimination
  • Gauss-Jacobi Method
  • Gauss-Seidel Method
  • Direct Methods - Triangular System
  • Iterative Methods
  • Sufficient Convergence Condition for Gauss-Jacobi

Direct vs Iterative

Always check the residual $\parallel b-Ax\parallel$ after computing $x$ .

Connections

• Roots of nonlinear systems often linearize to $J\mathrm{\Delta }x=-F$
• Least squares solves normal equations $A^{\mathrm{\top }}A\hat{a}=A^{\mathrm{\top }}y$ (prefer QR in practice)
• Theory: Linear Algebra

References