GuideLinear systemsintermediate

Linear systems: error, residual and conditioning

Direct versus iterative methods for Ax=b, the difference between error and residual, the residual stopping criterion and why the condition number decides whether it is reliable.

Direct versus iterative

You can solve $Ax=b$ with direct methods (Cramer, Gauss-Jordan), which reach the solution in finitely many operations, or with iterative methods, which produce better approximations step by step. For large, sparse or ill-conditioned matrices, iterative methods often cost less and let you stop once the desired precision is reached.

Error, residual and stopping

The error compares the approximation with the exact solution x*; the residual measures how much the equation fails. The error is unknown, so we stop by the residual.

e^{(k)}=x^*-x^{(k)},\qquad r^{(k)}=b-Ax^{(k)},\qquad r^{(k)}=Ae^{(k)}

ExampleIll-conditioned matrix

The system with $A=\bigl(\begin{smallmatrix}2 & 6\\ 2 & 6.0001\end{smallmatrix}\bigr)$ and $b=(8,\,8.0001)^T$ has solution $x=(1,1)^T$ . A tiny perturbation changes the solution drastically.

Subtracting 0.0001 in the second row, the solution becomes:
$\tilde x=[4,\ 0]^{t}\quad\text{(muy distinta de } [1,1]^t)$

Explained by the huge condition number:

\mathcal{K}(A)\approx 4.0001\cdot 10^{5}

The stationary iterative scheme

Iterative methods start from a splitting $A=M-N$ with $M$ easy to invert (diagonal, triangular…). $Ax=b$ is turned into an equivalent fixed point:

Mx^{(k+1)}=Nx^{(k)}+b\ \Longleftrightarrow\ x^{(k+1)}=Hx^{(k)}+q,\qquad H=M^{-1}N,\ q=M^{-1}b

H is the iteration matrix. The method is stationary if H is constant throughout. Different choices of M give Jacobi, Gauss-Seidel and SOR.