From Data Perturbation to Solution Error
Suppose a nonsingular matrix \(\mathbf{A}\) represents a linear system \(\mathbf{A}\mathbf{x}=\mathbf{b}\). If the data vector \(\mathbf{b}\) changes slightly, the solution may also change. The key question is not only how large the change in the solution is, but how large it is relative to the original solution. A condition number gives a bound on how much a relative change in the right-hand side can be amplified into relative solution error.
We work over \(\mathbb{R}\) with a nonsingular matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\). Fix a vector norm \(\|\cdot\|\), and use its induced matrix norm, defined by \(\|\mathbf{A}\|=\sup_{\mathbf{v}\ne\mathbf{0}}\|\mathbf{A}\mathbf{v}\|/\|\mathbf{v}\|\). This norm satisfies \(\|\mathbf{A}\mathbf{v}\|\leq\|\mathbf{A}\|\|\mathbf{v}\|\) and is submultiplicative: \(\|\mathbf{A}\mathbf{B}\|\leq\|\mathbf{A}\|\|\mathbf{B}\|\) whenever the product is defined.
Let \(\mathbf{x}\) be the exact solution for \(\mathbf{b}\), and let \(\widehat{\mathbf{x}}\) be the exact solution for the perturbed right-hand side. Thus \(\mathbf{A}\mathbf{x}=\mathbf{b}\) and \(\mathbf{A}\widehat{\mathbf{x}}=\mathbf{b}+\delta\mathbf{b}\). The hat indicates the solution to the changed data; it does not imply that this solution was computed using floating-point arithmetic. Subtracting the two equations shows that the solution change \(\delta\mathbf{x}=\widehat{\mathbf{x}}-\mathbf{x}\) satisfies \(\mathbf{A}\delta\mathbf{x}=\delta\mathbf{b}\). This identity is the starting point for the bound.
Proof. Subtracting \(\mathbf{A}\mathbf{x}=\mathbf{b}\) from \(\mathbf{A}\widehat{\mathbf{x}}=\mathbf{b}+\delta\mathbf{b}\) gives \(\mathbf{A}(\widehat{\mathbf{x}}-\mathbf{x})=\delta\mathbf{b}\). Since \(\mathbf{A}\) is nonsingular, \(\widehat{\mathbf{x}}-\mathbf{x}=\mathbf{A}^{-1}\delta\mathbf{b}\), so the induced-norm inequality gives \(\|\widehat{\mathbf{x}}-\mathbf{x}\|\leq\|\mathbf{A}^{-1}\|\|\delta\mathbf{b}\|\). Also, \(\mathbf{b}=\mathbf{A}\mathbf{x}\) implies \(\|\mathbf{b}\|\leq\|\mathbf{A}\|\|\mathbf{x}\|\). Because \(\mathbf{b}\ne\mathbf{0}\) and \(\mathbf{A}\) is nonsingular, \(\mathbf{x}\ne\mathbf{0}\); dividing and combining these inequalities yields \[ \frac{\|\widehat{\mathbf{x}}-\mathbf{x}\|}{\|\mathbf{x}\|} \leq \|\mathbf{A}^{-1}\|\|\mathbf{A}\|\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|} = \kappa(\mathbf{A})\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|}. \] \(\square\)
The estimate says that the relative solution error is at most the relative data error multiplied by \(\kappa(\mathbf{A})\). It is an upper bound, not a promise that every perturbation is amplified by that factor. Its hypotheses matter: the system matrix must be square and nonsingular, the original right-hand side must be nonzero for the relative data error to be defined, and the same norm must be used consistently.
What the Bound Measures
The condition number is always at least \(1\) for a nonsingular matrix in an induced norm. This helps interpret it as a possible amplification factor rather than a measure that can make relative errors smaller in every direction.
Proof. Since \(\mathbf{A}\mathbf{A}^{-1}=\mathbf{I}\), submultiplicativity gives \(1=\|\mathbf{I}\|=\|\mathbf{A}\mathbf{A}^{-1}\|\leq\|\mathbf{A}\|\|\mathbf{A}^{-1}\|=\kappa(\mathbf{A})\). Here \(\|\mathbf{I}\|=1\) because an induced matrix norm gives \(\|\mathbf{I}\mathbf{v}\|/\|\mathbf{v}\|=1\) for every nonzero \(\mathbf{v}\). \(\square\)
A value of \(\kappa(\mathbf{A})\) near \(1\) makes the bound restrictive: a small relative perturbation in \(\mathbf{b}\) must produce a comparably small relative change in the solution. A large value allows substantial amplification. It does not say that a particular perturbation will cause large error; its effect also depends on the direction of \(\delta\mathbf{b}\) and on \(\mathbf{b}\).
For one useful norm, \(\|\mathbf{v}\|_{\infty}=\max_i|v_i|\). Its induced matrix norm is the largest absolute row sum, \(\|\mathbf{A}\|_{\infty}=\max_i\sum_j|a_{ij}|\). The examples below use this norm, so every condition number and relative error is computed in the same measurement.
Worked Example: A Bound Attained Exactly
Use the infinity norm for \[ \mathbf{A}=\begin{bmatrix}2&1\\1&1\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}3\\2\end{bmatrix},\qquad \delta\mathbf{b}=\begin{bmatrix}\tfrac{1}{10}\\-\tfrac{1}{10}\end{bmatrix}. \] First, \(\mathbf{x}=\begin{bmatrix}1\\1\end{bmatrix}\), since \(\mathbf{A}\mathbf{x}=\begin{bmatrix}2+1\\1+1\end{bmatrix}=\begin{bmatrix}3\\2\end{bmatrix}=\mathbf{b}\).
The inverse is \(\mathbf{A}^{-1}=\begin{bmatrix}1&-1\\-1&2\end{bmatrix}\), as multiplication gives \[ \mathbf{A}\mathbf{A}^{-1} = \begin{bmatrix}2-1&-2+2\\1-1&-1+2\end{bmatrix} = \begin{bmatrix}1&0\\0&1\end{bmatrix}. \] Therefore \[ \delta\mathbf{x}=\mathbf{A}^{-1}\delta\mathbf{b} = \begin{bmatrix}\tfrac{1}{10}+\tfrac{1}{10}\\-\tfrac{1}{10}-\tfrac{2}{10}\end{bmatrix} = \begin{bmatrix}\tfrac{1}{5}\\-\tfrac{3}{10}\end{bmatrix}, \qquad \widehat{\mathbf{x}}=\mathbf{x}+\delta\mathbf{x} = \begin{bmatrix}\tfrac{6}{5}\\\tfrac{7}{10}\end{bmatrix}. \] Check the perturbed system: \[ \mathbf{A}\widehat{\mathbf{x}} = \begin{bmatrix}\tfrac{12}{5}+\tfrac{7}{10}\\\tfrac{6}{5}+\tfrac{7}{10}\end{bmatrix} = \begin{bmatrix}\tfrac{31}{10}\\\tfrac{19}{10}\end{bmatrix} = \mathbf{b}+\delta\mathbf{b}. \]
The largest absolute row sums of \(\mathbf{A}\) and \(\mathbf{A}^{-1}\) are both \(3\), so \(\kappa_{\infty}(\mathbf{A})=3\cdot3=9\). Also, \(\|\mathbf{x}\|_{\infty}=1\), \(\|\delta\mathbf{x}\|_{\infty}=\tfrac{3}{10}\), \(\|\mathbf{b}\|_{\infty}=3\), and \(\|\delta\mathbf{b}\|_{\infty}=\tfrac{1}{10}\). Thus the relative solution error is \(\tfrac{3}{10}\), while the bound is \(9\cdot(\tfrac{1}{10}/3)=\tfrac{3}{10}\). Equality holds in this example.
Worked Example: A Bound That Is Not Tight
Take \[ \mathbf{A}=\begin{bmatrix}1&0\\0&10\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}1\\0\end{bmatrix},\qquad \delta\mathbf{b}=\begin{bmatrix}0\\\tfrac{1}{10}\end{bmatrix}. \] Then \(\mathbf{x}=\begin{bmatrix}1\\0\end{bmatrix}\), because \(\mathbf{A}\mathbf{x}=\mathbf{b}\). The perturbed solution is \(\widehat{\mathbf{x}}=\begin{bmatrix}1\\\tfrac{1}{100}\end{bmatrix}\), since \[ \mathbf{A}\widehat{\mathbf{x}} = \begin{bmatrix}1\\\tfrac{10}{100}\end{bmatrix} = \begin{bmatrix}1\\\tfrac{1}{10}\end{bmatrix} = \mathbf{b}+\delta\mathbf{b}. \] The solution change is \(\delta\mathbf{x}=\begin{bmatrix}0\\\tfrac{1}{100}\end{bmatrix}\), and direct multiplication checks it: \(\mathbf{A}\delta\mathbf{x}=\begin{bmatrix}0\\\tfrac{1}{10}\end{bmatrix}=\delta\mathbf{b}\).
Here \(\|\mathbf{A}\|_{\infty}=10\) and \(\|\mathbf{A}^{-1}\|_{\infty}=1\), giving \(\kappa_{\infty}(\mathbf{A})=10\). The relative data perturbation is \(\tfrac{1}{10}\), while the relative solution error is \(\tfrac{1}{100}\). The theorem gives an upper bound of \(10\cdot\tfrac{1}{10}=1\). The actual error is much smaller: in this example the perturbation acts in a direction where the inverse scales it down.
Worked Example: Small Data Error Can Reach the Bound
Let \[ \mathbf{A}=\begin{bmatrix}1&0\\0&100\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}0\\100\end{bmatrix},\qquad \delta\mathbf{b}=\begin{bmatrix}\tfrac{1}{10}\\0\end{bmatrix}. \] The original solution is \(\mathbf{x}=\begin{bmatrix}0\\1\end{bmatrix}\), since \(\mathbf{A}\mathbf{x}=\mathbf{b}\). The change is \[ \delta\mathbf{x}=\mathbf{A}^{-1}\delta\mathbf{b} = \begin{bmatrix}1&0\\0&\tfrac{1}{100}\end{bmatrix} \begin{bmatrix}\tfrac{1}{10}\\0\end{bmatrix} = \begin{bmatrix}\tfrac{1}{10}\\0\end{bmatrix}, \] so \(\widehat{\mathbf{x}}=\begin{bmatrix}\tfrac{1}{10}\\1\end{bmatrix}\). Checking gives \(\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}\tfrac{1}{10}\\100\end{bmatrix}=\mathbf{b}+\delta\mathbf{b}\), and \(\mathbf{A}\delta\mathbf{x}=\delta\mathbf{b}\).
The infinity norms give \(\|\mathbf{A}\|_{\infty}=100\), \(\|\mathbf{A}^{-1}\|_{\infty}=1\), and \(\kappa_{\infty}(\mathbf{A})=100\). The relative data error is \(\tfrac{1}{10}/100=\tfrac{1}{1000}\), while the relative solution error is \(\tfrac{1}{10}/1=\tfrac{1}{10}\). The bound is \(100\cdot\tfrac{1}{1000}=\tfrac{1}{10}\), exactly the observed error. Here a small relative change in the data is amplified by the full condition-number factor.
A Second Way to Measure the Perturbation
Sometimes the perturbed right-hand side is the available reference, so the data change is measured relative to \(\mathbf{b}+\delta\mathbf{b}\) rather than \(\mathbf{b}\). Write \(\rho=\|\delta\mathbf{b}\|/\|\mathbf{b}+\delta\mathbf{b}\|\), assuming \(\mathbf{b}+\delta\mathbf{b}\ne\mathbf{0}\). Then the error measured relative to the perturbed solution has the direct bound \[ \frac{\|\widehat{\mathbf{x}}-\mathbf{x}\|}{\|\widehat{\mathbf{x}}\|} \leq \kappa(\mathbf{A})\rho. \] Indeed, the numerator is at most \(\|\mathbf{A}^{-1}\|\|\delta\mathbf{b}\|\), while \(\|\mathbf{b}+\delta\mathbf{b}\|=\|\mathbf{A}\widehat{\mathbf{x}}\|\leq\|\mathbf{A}\|\|\widehat{\mathbf{x}}\|\). Dividing these inequalities gives the displayed estimate. This version uses a different denominator on both relative errors; it should not be confused with the theorem's bound relative to the original data and original solution.
Common Mistake: Losing a Matrix-Norm Factor
From \(\delta\mathbf{x}=\mathbf{A}^{-1}\delta\mathbf{b}\), it is correct that \(\|\delta\mathbf{x}\|\leq\|\mathbf{A}^{-1}\|\|\delta\mathbf{b}\|\). A common incorrect next step is to divide by \(\|\mathbf{x}\|\) and then replace \(\|\mathbf{x}\|\) by \(\|\mathbf{b}\|\), claiming \[ \frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \leq \|\mathbf{A}^{-1}\|\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|}. \] That replacement is not justified: \(\|\mathbf{x}\|\) is not generally at least \(\|\mathbf{b}\|\). In the first worked example, this incorrect expression equals \(3\cdot(\tfrac{1}{10}/3)=\tfrac{1}{10}\), even though the actual relative solution error is \(\tfrac{3}{10}\). The valid comparison is \(\|\mathbf{b}\|=\|\mathbf{A}\mathbf{x}\|\leq\|\mathbf{A}\|\|\mathbf{x}\|\). It contributes the missing factor \(\|\mathbf{A}\|\), producing \(\kappa(\mathbf{A})=\|\mathbf{A}\|\|\mathbf{A}^{-1}\|\).
The bound is useful because it separates the effect of the data change from the sensitivity of the system matrix. It also provides a guarantee, not a prediction for every perturbation: examples can fall well below the bound or attain it. The condition number alone does not determine the actual error without knowing the perturbation and the original right-hand side.
Check Your Understanding
Use the stated hypotheses and keep the norm used for each relative error consistent.
- Starting from the two system equations, derive the equation satisfied by \(\widehat{\mathbf{x}}-\mathbf{x}\).
- Why is nonsingularity needed to express the solution change using \(\mathbf{A}^{-1}\)?
- For \(\mathbf{A}=\begin{bmatrix}1&0\\0&5\end{bmatrix}\) in the infinity norm, compute \(\kappa_{\infty}(\mathbf{A})\).
- In the relative solution-error theorem, why must the original right-hand side be nonzero?
- Explain why the condition-number bound need not be attained for every right-hand-side perturbation.
