Iterative methods for linear equations

Iterative methods start from an assumed solution and improve it repeatedly until the change is within tolerance. They are used for large sparse systems $[A]\{x\}=\{b\}$ and need diagonal dominance (or symmetry and positive definiteness) for convergence.

1. Jacobi method: every unknown is computed using values of the previous iteration only.

$$x_i^{(k+1)}=\frac{1}{a_{ii}}\Big(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\Big)$$

2. Gauss-Seidel method: newly computed values are used immediately in the same iteration:

$$x_i^{(k+1)}=\frac{1}{a_{ii}}\Big(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\Big)$$

It converges about twice as fast as Jacobi. 3. Successive over-relaxation (SOR): $x_i^{new}=(1-\omega)x_i^{old}+\omega\,x_i^{GS}$ with $1<\omega<2$ to speed up convergence. 4. Conjugate gradient method: for symmetric positive definite matrices; minimises the quadratic energy along conjugate directions and converges in at most $n$ steps.