Small Residuals With Large Solution Errors

Why a Small Residual Can Be Misleading

When an approximate solution nearly satisfies a linear system, its residual is small. That is useful information about how closely the approximate vector satisfies the equations, but it is not automatically a measure of how close that vector is to the true solution. The distinction matters most when the coefficient matrix is ill-conditioned: a small change in the equations can then produce a large change in the solution.

We work over \(\mathbb{R}\) with a finite-dimensional system \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is invertible. Thus the system has a unique solution \(\mathbf{x}\). For measuring size, use the vector infinity norm \(\|\mathbf{v}\|_{\infty}=\max_i |v_i|\) and its induced matrix norm \(\|\mathbf{A}\|_{\infty}=\max_i\sum_j|a_{ij}|\). This matrix norm satisfies \(\|\mathbf{A}\mathbf{v}\|_{\infty}\leq\|\mathbf{A}\|_{\infty}\|\mathbf{v}\|_{\infty}\).

These quantities answer different questions. The residual asks how well \(\widehat{\mathbf{x}}\) satisfies the given equations. The forward error asks how far \(\widehat{\mathbf{x}}\) is from the exact solution. The condition number describes how strongly the matrix can amplify changes. A small residual is evidence of accuracy only when the matrix’s amplification is also taken into account.

The Exact Link Between Residual and Error

Proof. By the definitions of the exact solution and residual, \(\mathbf{A}\mathbf{x}=\mathbf{b}\) and \(\mathbf{A}\widehat{\mathbf{x}}=\mathbf{b}-\mathbf{r}\). Subtract the second equation from the first to obtain \(\mathbf{A}(\mathbf{x}-\widehat{\mathbf{x}})=\mathbf{r}\). Since \(\mathbf{A}\) is invertible, multiply by \(\mathbf{A}^{-1}\) to get \(\mathbf{x}-\widehat{\mathbf{x}}=\mathbf{A}^{-1}\mathbf{r}\). \(\square\)

The identity says exactly how a residual becomes a solution error: the matrix \(\mathbf{A}^{-1}\) acts on the residual. A small residual in a direction that \(\mathbf{A}^{-1}\) amplifies strongly can therefore produce a much larger error. This is why comparing the size of the residual directly with the size of the error is not enough.

Proof. Since \(\mathbf{A}\) is invertible and \(\mathbf{x}\ne\mathbf{0}\), \(\mathbf{b}=\mathbf{A}\mathbf{x}\ne\mathbf{0}\), so both relative quantities are defined. The identity just proved and the induced norm inequality give \(\|\mathbf{x}-\widehat{\mathbf{x}}\|_{\infty}=\|\mathbf{A}^{-1}\mathbf{r}\|_{\infty}\leq\|\mathbf{A}^{-1}\|_{\infty}\|\mathbf{r}\|_{\infty}\). Also, \(\|\mathbf{b}\|_{\infty}=\|\mathbf{A}\mathbf{x}\|_{\infty}\leq\|\mathbf{A}\|_{\infty}\|\mathbf{x}\|_{\infty}\), so \(\|\mathbf{x}\|_{\infty}\geq\|\mathbf{b}\|_{\infty}/\|\mathbf{A}\|_{\infty}\). Dividing the first inequality by \(\|\mathbf{x}\|_{\infty}\) and using this lower bound yields \[ \frac{\|\mathbf{x}-\widehat{\mathbf{x}}\|_{\infty}}{\|\mathbf{x}\|_{\infty}} \leq \|\mathbf{A}^{-1}\|_{\infty}\|\mathbf{A}\|_{\infty} \frac{\|\mathbf{r}\|_{\infty}}{\|\mathbf{b}\|_{\infty}} = \kappa_{\infty}(\mathbf{A}) \frac{\|\mathbf{r}\|_{\infty}}{\|\mathbf{b}\|_{\infty}}. \] \(\square\)

This is an upper bound, not a promise that the error equals the bound or that every small residual causes a large error. It does show why the product of the condition number and relative residual matters. If the condition number is large, the bound may allow a substantial forward error even when the relative residual is tiny.

A Tiny Residual and a Large Forward Error

How Ill-Conditioning Makes the Example Possible

The two rows of the matrix in the example are nearly identical. If they were identical, the matrix would not be invertible; with a small positive \(\delta\), the system is invertible but very sensitive. The inverse contains the factor \(1/\delta\), which makes some small residuals produce much larger solution errors.

The examples demonstrate a possibility, not a rule that every approximate solution to an ill-conditioned system is inaccurate. They show that residual size alone cannot certify accuracy. The condition number indicates how much relative error may be consistent with a given relative residual; the actual error also depends on the direction of the residual.

Comparison with a Well-Conditioned System

Common Mistake: Treating Residual Size as Error Size

A tempting but incorrect conclusion is: “The residual has norm \(1/1{,}000{,}000\), so the solution error is at most \(1/1{,}000{,}000\).” In the first example the actual absolute forward error is \(\|(1,-1)^{\top}\|_{\infty}=1\), not at most \(1/1{,}000{,}000\). The incorrect calculation has silently treated multiplication by \(\mathbf{A}^{-1}\) as if it could not increase the residual.

The correction is to use the exact identity and the norm bound: \(\|\mathbf{x}-\widehat{\mathbf{x}}\|_{\infty}=\|\mathbf{A}^{-1}\mathbf{r}\|_{\infty}\leq\|\mathbf{A}^{-1}\|_{\infty}\|\mathbf{r}\|_{\infty}\). For the first example, \(\|\mathbf{A}^{-1}\|_{\infty}=(2+\delta)/\delta=2{,}000{,}001\). The resulting upper bound is \(2{,}000{,}001/1{,}000{,}000=2+\delta\), which does not incorrectly claim that the error is tiny.

When interpreting a computed solution, keep the quantities separate:

• A small absolute residual means the approximate vector nearly satisfies the equations in absolute terms.
• A small relative residual measures that discrepancy against the size of the right-hand side.
• A small forward error means the approximate vector is close to the true solution.
• A condition number helps assess whether a small relative residual can still accompany a substantial relative forward error.

The condition-number bound is useful as a warning and an estimate, not as a complete description of a particular error. A large bound says that accuracy is not guaranteed by the residual alone; it does not say the actual error must be large. A small bound, on the other hand, does certify a small relative forward error when its hypotheses hold.