A b o u t   M e      |       P r o j e c t s     |       N o t e s       |       T h e   D a y    ︎ ︎

## Small Residuals Do Not Imply Small Errors

Consider the following linear system:
\begin{align} Ax= \begin{pmatrix} 0.913 & 0.659 \\ 0.457 & 0.330 \end{pmatrix} x= \begin{pmatrix} 0.254 \\ 0.127 \end{pmatrix}= b. \end{align}    Let the estimated solutions be hat{x}_1 and hat{x}_2, \begin{align} \hat{x}_1 = \begin{pmatrix} -0.0827 \\ 0.5 \end{pmatrix}, \quad \hat{x}_2 = \begin{pmatrix} 0.999 \\ -1.001 \end{pmatrix}, \end{align} and its residuals are \begin{align} \left\| r_1 \right\|_1 &= \left\| b-A\hat{x}_1 \right\|_1 =2.1\times 10^{-4} \\ \left\| r_2 \right\|_1 &= \left\| b-A\hat{x}_2 \right\|_1 =2.4\times 10^{-2}. \end{align}
Since ||r_1||<||r_2||, it seems that hat{x}_1 is the optimal solution. Considering the real solution, however, is x=(1-, 1)^t, it makes more sense that the optimal solution would be hat{x}_2.

This situation happens because A is close to singular. Therefore, when A is ill-conditioned, which means the condition number of A is large(>10^4), this can happen.

When A is close to singular, a line in the original space is almost suppresed to a point in the objective space. So, hat{x}_2 which is close to the optimal solution x in the original space may be mapped further than x.

︎Reference

 Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.

emoy.net