Small Residuals Do Not Imply Small Errors

Consider the following linear system: Ax=(0.9130.6590.4570.330)x=(0.2540.127)=b\begin{aligned} Ax &= \left(\begin{array}{cc} 0.913 & 0.659 \\ 0.457 & 0.330 \end{array}\right) x = \left(\begin{array}{c} 0.254 \\ 0.127 \end{array}\right) = b \end{aligned}

Let the estimated solutions be x1^\hat{x_1} and x2^\hat{x_2}, x1^=(0.08270.5),x2^=(0.9991.001)\begin{aligned} \hat{x_1} = \left(\begin{array}{c} -0.0827 \\ 0.5 \end{array}\right), \quad \hat{x_2} = \left(\begin{array}{c} 0.999 \\ -1.001 \end{array}\right) \end{aligned}

and its residuals are r11=bAx1^1=2.1×104r21=bAx2^1=2.4×102\begin{aligned} \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{aligned}

Since r1<r2\left\| r_1 \right\| < \left\| r_2 \right\|, it seems that x1^\hat{x_1} is the optimal solution. Considering the real solution, however, is x=(1,1)tx = (1, -1)^t, it makes more sense that the optimal solution would be x2^\hat{x_2}.

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


When AA is close to singular, a line in the original space is almost suppresed to a point in the objective space. So, x2^\hat{x_2} which is close to the optimal solution xx in the original space may be mapped further than xx.


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

© 2022. All rights reserved.