Solution methods of linear equations with examples

A system $[A]\{x\}=\{b\}$ is solved by direct or iterative methods.

Direct methods

They give the exact answer (apart from round-off) after a fixed number of operations.

• Gauss elimination: reduce $A$ to upper triangular form, then back-substitute.
• LU decomposition / Cholesky ($A=LL^T$ for symmetric positive definite matrices): factor once, then solve for several right-hand sides.
• Gauss-Jordan and matrix inverse.

Example: $2x+y=5,\ x+3y=10$. Eliminating, $R_2\to R_2-\tfrac12R_1$ gives $2.5y=7.5$, so $y=3$, $x=1$.

Iterative methods

Start from a guess and improve it until the change is small. They suit large sparse systems.

• Jacobi: $x_i^{(k+1)}=\dfrac{1}{a_{ii}}\Big(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\Big)$
• Gauss-Seidel: same but uses new values immediately.
• SOR: Gauss-Seidel with relaxation factor $\omega$.
• Conjugate gradient: minimises $\tfrac12x^TAx-b^Tx$ for symmetric positive definite $A$.

Example (Gauss-Seidel): $4x+y=9,\ x+3y=7$, start $(0,0)$.

• Iteration 1: $x=9/4=2.25$, $y=(7-2.25)/3=1.583$.
• Iteration 2: $x=(9-1.583)/4=1.854$, $y=(7-1.854)/3=1.715$.

The values move to the exact solution $x=20/11=1.818$, $y=19/11=1.727$.

Comparison