Perturbation theory and a posteriori error for linear systems

Intuition Beginner

You solved a linear system on a computer and got back a vector that you are calling the answer. Two honest questions follow. First: if the numbers you fed in were a little off — measured imperfectly, or rounded when stored — how far off can the true answer be? Second: now that you hold a computed answer in your hand, how can you check, after the fact, whether it is any good? The first question is perturbation theory. The second is a posteriori error estimation, which is just Latin for "checking after you have computed."

The two questions are joined by one number you already met in 43.01.02, the condition number of the matrix. It is the worst factor by which a small relative error in the data gets blown up in the answer. A condition number near one means a forgiving system: small input errors stay small. A condition number of a million means a barely-visible change in the data can swing the answer wildly, and no amount of careful computing can rescue you.

A natural instinct for checking your answer is to plug it back in. Take the computed answer, multiply by the matrix, and see how close you land to the right-hand side. The gap is called the residual. A tiny residual feels reassuring — it looks like the equation is almost satisfied. The hard lesson of this unit is that a tiny residual does not promise a tiny error when the condition number is large. The answer can be far from correct while the residual stays small, because the condition number stands between the two.

What you can trust from a small residual is something more modest and still useful: your computed answer exactly solves a problem close to the one you posed. Whether close-in-data means close-in-answer is, once again, the condition number's call.

Visual Beginner

The picture to hold is two different gaps. The residual lives on the right-hand-side, where you can see it: take your computed answer, push it through the matrix, and measure how far the result misses the target. The error lives on the answer side, where you cannot see it: it is the distance from your computed answer to the true one. The condition number is the exchange rate between them.

Read the table top to bottom. The residual is what you can measure; the error is what you actually care about. When the condition number is small the two are about the same size and the residual is a trustworthy report card. When the condition number is large the residual can be tiny while the error is enormous.

condition number	residual you can measure	true error you cannot see	residual a reliable report?
about $1$	small	small	yes
about $100$	small	up to $100$ times larger	weak
about $1000000$	small	up to a million times larger	no

The takeaway: measuring the residual is easy and the residual is genuine information, but to convert it into a statement about how wrong your answer is you must multiply by the condition number. A small residual alone is not a clean bill of health.

Worked example Beginner

Let us watch a small residual hide a large error. Take the system $Ax=b$ with $$ A = \begin{pmatrix} 1 & 1 \ 1 & 1.0001 \end{pmatrix}, \qquad b = \begin{pmatrix} 2 \ 2.0001 \end{pmatrix}. $$ The true answer is $x=(1,1)$, because the two rows give $x_1+x_2=2$ and $x_1+1.0001x_2=2.0001$, which together force $x_2=1$ and then $x_1=1$.

Now suppose a computation hands you the candidate answer $\tilde{x}=(2,0)$ instead. This is badly wrong: it misses the true answer $(1,1)$ by a full unit in each coordinate. Let us compute its residual anyway, by plugging it back in. The first row gives $1\times 2+1\times 0=2$, matching $b_1=2$ exactly. The second row gives $1\times 2+1.0001\times 0=2$, against $b_2=2.0001$.

So the residual is $$ r = b - A\tilde x = \begin{pmatrix} 2 \ 2.0001 \end{pmatrix} - \begin{pmatrix} 2 \ 2 \end{pmatrix} = \begin{pmatrix} 0 \ 0.0001 \end{pmatrix}. $$ The residual has size about $0.0001$ — tiny, one part in twenty thousand of the right-hand side. Yet the error in the answer is about $1.4$, the distance from $(2,0)$ to $(1,1)$. A residual of $0.0001$ sits beside an error of order one.

What this tells us: the residual was small, the error was huge, and the gap between them is the condition number of this matrix, which is roughly $40000$. The two rows of $A$ are almost the same line, so the system barely pins down where the answer is — a small miss on the right-hand side corresponds to a large move in the answer. The residual told the truth about the equation and lied about the answer.

Check your understanding Beginner

Formal definition Intermediate+

Let $A\in {\mathbb{F}}^{n\times n}$ with $\mathbb{F}=\mathbb{R}$ or $\mathbb{C}$ be invertible, let $b\in {\mathbb{F}}^n$ be nonzero, and let $x=A^{-1}b$ be the exact solution of the linear system $Ax=b$. Throughout, $\Vert \cdot \Vert$ is a fixed vector norm with its induced operator norm on matrices, and $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$ is the condition number of 43.01.02. Let $\tilde{x}$ denote a computed or otherwise approximate solution.

Residual. The residual of $\tilde{x}$ is the vector $$ r = b - A\tilde x. $$ It measures how nearly $\tilde{x}$ satisfies the equation, and it is computable from $A$, $b$, and $\tilde{x}$ alone — no knowledge of the true $x$ is needed. The error is $e=x-\tilde{x}$, which is not computable without $x$. The two are linked by $Ae=A(x-\tilde{x})=b-A\tilde{x}=r$, so $e=A^{-1}r$.

A posteriori residual bound. From $e=A^{-1}r$ and $b=Ax$ one obtains the a posteriori relative error bound $$ \frac{|x - \tilde x|}{|x|} \le \kappa(A),\frac{|r|}{|b|}, $$ which converts a measured relative residual $\Vert r\Vert /\Vert b\Vert$ into a guaranteed relative error, scaled by the condition number. When $\kappa (A)$ is modest the residual is a faithful proxy for the error; when $\kappa (A)$ is large the same residual certifies far less.

Perturbation of the data. Suppose the data is perturbed: $A\mapsto A+\delta A$ and $b\mapsto b+\delta b$, and let $x+\delta x$ solve the perturbed system $(A+\delta A)(x+\delta x)=b+\delta b$. Provided $\kappa (A)\Vert \delta A\Vert /\Vert A\Vert <1$, the solution perturbation obeys the normwise perturbation bound $$ \frac{|\delta x|}{|x|} \le \frac{\kappa(A)}{1 - \kappa(A),|\delta A|/|A|}\left(\frac{|\delta A|}{|A|} + \frac{|\delta b|}{|b|}\right). $$ The leading factor is $\kappa (A)$; the denominator $1-\kappa (A)\Vert \delta A\Vert /\Vert A\Vert$ is a second-order correction that matters only when the perturbation of $A$ is large enough to threaten invertibility, that is, when $\kappa (A)\Vert \delta A\Vert /\Vert A\Vert$ approaches $1$.

Normwise backward error. The normwise backward error of $\tilde{x}$ is the size of the smallest data perturbation that makes $\tilde{x}$ exact, $$ \eta(\tilde x) = \min{\varepsilon : (A + \delta A)\tilde x = b + \delta b,\ |\delta A| \le \varepsilon|A|,\ |\delta b| \le \varepsilon|b|}. $$ The Rigal-Gaches theorem (proved at the Master tier) evaluates this minimum in closed form as $\eta (\tilde{x})=\Vert r\Vert /(\Vert A\Vert \Vert \tilde{x}\Vert +\Vert b\Vert )$. A solver is backward stable in the sense of 43.01.03 precisely when $\eta (\tilde{x})=O({ϵ}_{\mathrm{mach}})$.

Componentwise (Skeel) conditioning. When the entries of $A$ and $b$ vary over many orders of magnitude, a single norm flattens that structure and $\kappa (A)$ overstates the sensitivity. Measuring perturbations entrywise — $|\delta A|\le \epsilon |A|$ and $|\delta b|\le \epsilon |b|$, with absolute values and inequalities read componentwise — the governing quantity is the Skeel condition number $$ \mathrm{cond}(A, x) = \frac{\big|,|A^{-1}|,|A|,|x|,\big|\infty}{|x|\infty} \le \mathrm{cond}(A) = \big|,|A^{-1}|,|A|,\big|\infty, $$ which is invariant under row scaling of $A$ and can be far smaller than $\kappa\infty(A)$ for badly-scaled but otherwise benign systems.

Counterexamples to common slips

• A small residual is not a small error. The matrix and right-hand side of the Beginner worked example have $\tilde{x}=(2,0)$ with relative residual about $5\times 10^{-5}$ yet relative error about $1$; the gap is $\kappa (A)\approx 4\times 10^4$. The residual bounds the backward error, not the forward error.

• The residual depends on the measuring matrix. Scaling a single equation by a large factor inflates that component of $r$ without changing $\tilde{x}$ or the true error. Only the relative residual $\Vert r\Vert /(\Vert A\Vert \Vert \tilde{x}\Vert +\Vert b\Vert )$ — the backward error — is a scaling-aware report; the raw residual norm is not.

• Backward stability does not imply accuracy. A backward-stable solve guarantees $\eta (\tilde{x})=O({ϵ}_{\mathrm{mach}})$, hence a forward error of order $\kappa (A){ϵ}_{\mathrm{mach}}$. For an ill-conditioned $A$ this forward error can be large; the inaccuracy is charged to the conditioning of 43.01.02, not to the algorithm.

• Normwise and componentwise conditioning can disagree by orders of magnitude. A diagonal scaling can send ${\kappa }_{\infty }(A)$ to $10^8$ while $\mathrm{cond}(A,x)$ stays near $1$; the Skeel number, not $\kappa$, predicts the achievable accuracy after row equilibration.

Key theorem with proof Intermediate+

The signature result is the normwise perturbation bound: it isolates the condition number as the single amplification factor governing how the solution of $Ax=b$ responds to simultaneous perturbations of $A$ and $b$.

Theorem (normwise perturbation bound for $Ax=b$). Let $A\in {\mathbb{F}}^{n\times n}$ be invertible, $b\ne 0$, $x=A^{-1}b$. Let $\delta A,\delta b$ satisfy $\kappa (A)\Vert \delta A\Vert /\Vert A\Vert <1$, and let $x+\delta x$ solve $(A+\delta A)(x+\delta x)=b+\delta b$. Then $$ \frac{|\delta x|}{|x|} \le \frac{\kappa(A)}{1 - \kappa(A),|\delta A|/|A|}\left(\frac{|\delta A|}{|A|} + \frac{|\delta b|}{|b|}\right), $$ and to first order in the perturbations the bound reduces to $\Vert \delta x\Vert /\Vert x\Vert \le \kappa (A)(\Vert \delta A\Vert /\Vert A\Vert +\Vert \delta b\Vert /\Vert b\Vert )+O(\Vert \delta {\Vert }^2)$ ^{[Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.)]}.

Proof. Subtract $Ax=b$ from the perturbed equation $(A+\delta A)(x+\delta x)=b+\delta b$. The left side expands to $Ax+A\delta x+\delta Ax+\delta A\delta x$, so cancelling $Ax=b$ on both sides leaves $$ A,\delta x + \delta A,(x + \delta x) = \delta b, \qquad\text{hence}\qquad \delta x = A^{-1}\big(\delta b - \delta A,(x + \delta x)\big). $$ Take norms and apply submultiplicativity of the operator norm: $$ |\delta x| \le |A^{-1}|\big(|\delta b| + |\delta A|,|x| + |\delta A|,|\delta x|\big). $$ Collect the $\Vert \delta x\Vert$ terms on the left, using $\Vert A^{-1}\Vert \Vert \delta A\Vert =\kappa (A)\Vert \delta A\Vert /\Vert A\Vert$: $$ \Big(1 - \kappa(A)\tfrac{|\delta A|}{|A|}\Big)|\delta x| \le |A^{-1}|\big(|\delta b| + |\delta A|,|x|\big). $$ The hypothesis $\kappa (A)\Vert \delta A\Vert /\Vert A\Vert <1$ makes the left bracket positive. Divide both sides by it and by $\Vert x\Vert$. On the right, write $\Vert A^{-1}\Vert \Vert \delta A\Vert \Vert x\Vert /\Vert x\Vert =\kappa (A)\Vert \delta A\Vert /\Vert A\Vert$, and for the $\Vert \delta b\Vert$ term use $\Vert b\Vert =\Vert Ax\Vert \le \Vert A\Vert \Vert x\Vert$, so $1/\Vert x\Vert \le \Vert A\Vert /\Vert b\Vert$ and $\Vert A^{-1}\Vert \Vert \delta b\Vert /\Vert x\Vert \le \Vert A^{-1}\Vert \Vert A\Vert \Vert \delta b\Vert /\Vert b\Vert =\kappa (A)\Vert \delta b\Vert /\Vert b\Vert$. Assembling, $$ \frac{|\delta x|}{|x|} \le \frac{1}{1 - \kappa(A)|\delta A|/|A|},\kappa(A)\Big(\frac{|\delta A|}{|A|} + \frac{|\delta b|}{|b|}\Big), $$ the stated bound. Expanding the prefactor $(1-\kappa (A)\Vert \delta A\Vert /\Vert A\Vert {)}^{-1}=1+O(\Vert \delta A\Vert )$ recovers the first-order form. $\square$

Bridge. This theorem is the foundational reason the residual is a usable check on a computed solution: setting $\delta A=0$ and $\delta b=-r$ turns the perturbed system into the exact statement $A(x-\tilde{x})=r$, so the bound collapses to the a posteriori residual estimate $\Vert x-\tilde{x}\Vert /\Vert x\Vert \le \kappa (A)\Vert r\Vert /\Vert b\Vert$, and this is exactly the conditioning bound of 43.01.02 read off the computable residual rather than an abstract data perturbation. The result builds toward the backward-error theory of the Master tier, where the Rigal-Gaches identity reads the residual as the smallest data perturbation consistent with $\tilde{x}$; it appears again in iterative refinement, where the residual of one solve becomes the right-hand side of the next, so the same map $e=A^{-1}r$ drives the correction loop. The perturbation factor $\kappa (A)$ generalises the per-problem sensitivity of 43.01.02 to the full data $(A,b)$, and putting these together with the backward-error bound of 43.03.01 gives the forward error $\kappa (A){\rho }_n{ϵ}_{\mathrm{mach}}$ of a Gaussian-elimination solve: the central insight is that conditioning supplies the amplification and the solver supplies the residual, and the bridge is that their product is the accuracy delivered.

Exercises Intermediate+

Advanced results Master

Theorem 1 (a posteriori residual bound and its sharpness). For invertible $A$, nonzero $b$, exact solution $x=A^{-1}b$, and any $\tilde{x}$ with residual $r=b-A\tilde{x}$, $$ \frac{|x - \tilde x|}{|x|} \le \kappa(A),\frac{|r|}{|b|}, $$ and there exist $b$ and $\tilde{x}$ for which equality holds in the $2$-norm. The lower companion $\Vert x-\tilde{x}\Vert /\Vert x\Vert \ge \kappa (A{)}^{-1}\Vert r\Vert /\Vert b\Vert$ also holds, so the relative error and the relative residual agree to within a factor $\kappa (A)$ on both sides: the residual determines the error exactly when $\kappa (A)=1$ and becomes an unreliable proxy as $\kappa (A)$ grows ^{[Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.)]}.

Theorem 2 (Rigal-Gaches: the normwise backward error is the scaled residual). For invertible $A$, nonzero $b$, and any $\tilde{x}$, the normwise relative backward error $$ \eta(\tilde x) = \min{\varepsilon : (A + \delta A)\tilde x = b + \delta b,\ |\delta A|_2 \le \varepsilon|A|_2,\ |\delta b|_2 \le \varepsilon|b|_2} $$ equals the scaled residual $$ \eta(\tilde x) = \frac{|r|_2}{|A|_2,|\tilde x|2 + |b|2}, $$ attained by the rank-one optimal perturbation $\delta A* = \tfrac{\eta,|A|}{|\tilde x|},\tfrac{r}{|r|}\tfrac{\tilde x^*}{|\tilde x|}$and$\delta b* = -\tfrac{\eta,|b|}{|r|},r$.Thustheresidualisnotmerelyanerrorindicator:scaledby$|A|,|\tilde x| + |b|$,itis\ast exactly\ast thesmallestrelativedataperturbationforwhich$\tilde x$ is a true solution ^{[Rigal, J. L. & Gaches, J. — On the compatibility of a given solution with the data of a linear system]}.

Theorem 3 (Oettli-Prager: componentwise backward error). Fix entrywise tolerance matrices $E\ge 0$ and $f\ge 0$. There exist $\delta A,\delta b$ with $|\delta A|\le \epsilon E$, $|\delta b|\le \epsilon f$ (entrywise) and $(A+\delta A)\tilde{x}=b+\delta b$ if and only if $$ |r| \le \varepsilon,(E,|\tilde x| + f) \quad\text{(entrywise)}, \qquad\text{equivalently}\qquad \omega(\tilde x) = \max_i \frac{|r_i|}{(E,|\tilde x| + f)_i} $$ is the smallest such $\epsilon$. Taking $E=|A|$ and $f=|b|$ gives the componentwise relative backward error $\omega ={\max }_i|r_i|/(|A||\tilde{x}|+|b|{)}_i$, computable in $O(n^2)$, which is the componentwise analogue of Rigal-Gaches and the natural stopping test for iterative refinement ^{[Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.)]}.

Theorem 4 (iterative refinement: convergence and limiting accuracy). Let ${\hat{x}}_0$ be a computed solution of $Ax=b$ from a backward-stable solver, and iterate: compute $r_k=b-A{\hat{x}}_k$, solve $A{d}_k=r_k$ with the existing factors, set ${\hat{x}}_{k+1}={\hat{x}}_k+d_k$. If the residual is formed in precision ${ϵ}_r$ and the rest in working precision ${ϵ}_w$, and ${\kappa }_{\infty }(A){ϵ}_w$ is bounded below $1$, then the forward error contracts geometrically, $$ \frac{|x - \hat x_{k+1}|\infty}{|x|\infty} \lesssim (\kappa_\infty(A),\epsilon_w),\frac{|x - \hat x_k|\infty}{|x|\infty} + \mathrm{cond}(A,x),\epsilon_r, $$ so refinement converges to a limiting relative error of order $\mathrm{cond}(A,x){ϵ}_r$. With ${ϵ}_r={ϵ}_w$ (fixed-precision refinement), Skeel's theorem guarantees that a single step makes Gaussian elimination componentwise backward stable whenever $\mathrm{cond}(A,x){ϵ}_w$ is modest; with ${ϵ}_r$ at twice the working precision, refinement drives the forward error down to working-precision accuracy even for ill-conditioned $A$ ^{[Skeel, R. D. — Scaling for numerical stability in Gaussian elimination]}.

Synthesis. The whole chapter converges here: the conditioning of 43.01.02 and the backward error of 43.03.01 multiply, and this unit is where their product becomes an a posteriori statement about a solution actually in hand. The foundational reason a computed answer can be certified is the residual identity $A(x-\tilde{x})=r$, which is exactly the perturbation theorem with $\delta A=0$, $\delta b=-r$; the residual is the only computable handle on the error, and the condition number is the exact exchange rate, sharp on both sides by Theorem 1. The Rigal-Gaches and Oettli-Prager theorems are dual to that estimate: where the residual bound reads the error forward through $\kappa (A)$, they read the residual backward as the minimal data perturbation, and the central insight is that a small residual is always a small backward error and only a small forward error when conditioning permits.

This is exactly the conditioning-times-stability decomposition of 43.01.03, now closed into a loop by iterative refinement, where the residual of one solve becomes the data of the next and the same map $A^{-1}$ contracts the error by $\kappa (A){ϵ}_{\mathrm{mach}}$ per step until the precision floor is hit. The normwise theory generalises to the componentwise Skeel conditioning that survives badly-scaled data, which is dual to the row-equilibration that restores normwise sanity. Putting these together, the perturbation bound supplies the worst case the data forces, the backward error supplies what the solver achieved, and refinement supplies the mechanism that recovers the accuracy conditioning still allows; this builds toward every solver downstream, and appears again in least squares and the iterative methods, and the bridge to the rest of numerical linear algebra is that each is judged by precisely this residual-and-condition-number ledger.

Full proof set Master

Proposition 1 (a posteriori residual bound, both-sided). Let $A$ be invertible, $b\ne 0$, $x=A^{-1}b$, and $r=b-A\tilde{x}$. Then $\kappa (A{)}^{-1}\Vert r\Vert /\Vert b\Vert \le \Vert x-\tilde{x}\Vert /\Vert x\Vert \le \kappa (A)\Vert r\Vert /\Vert b\Vert$, and the upper bound is attained in the $2$-norm.

Proof. The residual identity is $A(x-\tilde{x})=b-A\tilde{x}=r$, so $x-\tilde{x}=A^{-1}r$ and $r=A(x-\tilde{x})$. For the upper bound, $\Vert x-\tilde{x}\Vert =\Vert A^{-1}r\Vert \le \Vert A^{-1}\Vert \Vert r\Vert$ and $\Vert b\Vert =\Vert Ax\Vert \le \Vert A\Vert \Vert x\Vert$, hence $\Vert x-\tilde{x}\Vert /\Vert x\Vert \le \Vert A^{-1}\Vert \Vert r\Vert \cdot \Vert A\Vert /\Vert b\Vert =\kappa (A)\Vert r\Vert /\Vert b\Vert$. For the lower bound, $\Vert r\Vert =\Vert A(x-\tilde{x})\Vert \le \Vert A\Vert \Vert x-\tilde{x}\Vert$ and $\Vert x\Vert =\Vert A^{-1}b\Vert \le \Vert A^{-1}\Vert \Vert b\Vert$, so $\Vert r\Vert /\Vert b\Vert \le \Vert A\Vert \Vert x-\tilde{x}\Vert \cdot \Vert A^{-1}\Vert /\Vert x\Vert =\kappa (A)\Vert x-\tilde{x}\Vert /\Vert x\Vert$, which rearranges to the stated lower bound. For attainment in the $2$-norm, take the SVD $A=U\Sigma V^{\ast }$; choose $x-\tilde{x}=v_n$ (the last right singular vector), so $r=A{v}_n={\sigma }_n{u}_n$ with $\Vert r{\Vert }_2={\sigma }_n$, and choose $b={\sigma }_1{u}_1$ so $x=A^{-1}b={\sigma }_1\cdot {\sigma }_1^{-1}{v}_1=v_1$ with $\Vert x{\Vert }_2=1$ and $\Vert b{\Vert }_2={\sigma }_1$. Then $\Vert x-\tilde{x}{\Vert }_2/\Vert x{\Vert }_2=1$ and ${\kappa }_2(A)\Vert r{\Vert }_2/\Vert b{\Vert }_2=({\sigma }_1/{\sigma }_n)({\sigma }_n/{\sigma }_1)=1$, so equality holds. $\square$

Proposition 2 (normwise perturbation bound). Let $A$ be invertible, $b\ne 0$, $x=A^{-1}b$, and let $(A+\delta A)(x+\delta x)=b+\delta b$ with $\kappa (A)\Vert \delta A\Vert /\Vert A\Vert <1$. Then $\Vert \delta x\Vert /\Vert x\Vert \le \frac{\kappa (A)}{1-\kappa (A)\Vert \delta A\Vert /\Vert A\Vert }(\Vert \delta A\Vert /\Vert A\Vert +\Vert \delta b\Vert /\Vert b\Vert )$.

Proof. Subtracting $Ax=b$ from the perturbed equation gives $A\delta x+\delta A(x+\delta x)=\delta b$, so $\delta x=A^{-1}(\delta b-\delta A(x+\delta x))$. Taking norms with submultiplicativity, $\Vert \delta x\Vert \le \Vert A^{-1}\Vert (\Vert \delta b\Vert +\Vert \delta A\Vert \Vert x\Vert +\Vert \delta A\Vert \Vert \delta x\Vert )$. Moving the $\Vert \delta x\Vert$ term and writing $\Vert A^{-1}\Vert \Vert \delta A\Vert =\kappa (A)\Vert \delta A\Vert /\Vert A\Vert$, $(1-\kappa (A)\Vert \delta A\Vert /\Vert A\Vert )\Vert \delta x\Vert \le \Vert A^{-1}\Vert (\Vert \delta b\Vert +\Vert \delta A\Vert \Vert x\Vert )$. The coefficient on the left is positive by hypothesis. Divide by it and by $\Vert x\Vert$; on the right, $\Vert A^{-1}\Vert \Vert \delta A\Vert \Vert x\Vert /\Vert x\Vert =\kappa (A)\Vert \delta A\Vert /\Vert A\Vert$, and $\Vert A^{-1}\Vert \Vert \delta b\Vert /\Vert x\Vert \le \kappa (A)\Vert \delta b\Vert /\Vert b\Vert$ via $1/\Vert x\Vert \le \Vert A\Vert /\Vert b\Vert$. The result follows. $\square$

Proposition 3 (Rigal-Gaches normwise backward error). For invertible $A$, nonzero $b$, and any $\tilde{x}\ne 0$ with $r=b-A\tilde{x}$, the normwise relative backward error in the $2$-norm is $\eta (\tilde{x})=\Vert r{\Vert }_2/(\Vert A{\Vert }_2\Vert \tilde{x}{\Vert }_2+\Vert b{\Vert }_2)$.

Proof. Lower bound. Suppose $(A+\delta A)\tilde{x}=b+\delta b$ with $\Vert \delta A{\Vert }_2\le \epsilon \Vert A{\Vert }_2$ and $\Vert \delta b{\Vert }_2\le \epsilon \Vert b{\Vert }_2$. Then $r=b-A\tilde{x}=\delta A\tilde{x}-\delta b$, so $\Vert r{\Vert }_2\le \Vert \delta A{\Vert }_2\Vert \tilde{x}{\Vert }_2+\Vert \delta b{\Vert }_2\le \epsilon (\Vert A{\Vert }_2\Vert \tilde{x}{\Vert }_2+\Vert b{\Vert }_2)$, giving $\epsilon \ge \Vert r{\Vert }_2/(\Vert A{\Vert }_2\Vert \tilde{x}{\Vert }_2+\Vert b{\Vert }_2)$. Hence $\eta (\tilde{x})\ge \Vert r{\Vert }_2/(\Vert A{\Vert }_2\Vert \tilde{x}{\Vert }_2+\Vert b{\Vert }_2)$. Upper bound (attainment). Set $\eta =\Vert r{\Vert }_2/(\Vert A{\Vert }_2\Vert \tilde{x}{\Vert }_2+\Vert b{\Vert }_2)$ and define $$ \delta A_* = \frac{\eta,|A|_2}{|\tilde x|_2},\frac{r,\tilde x^}{|r|_2,|\tilde x|2}, \qquad \delta b = -\frac{\eta,|b|_2}{|r|2},r. $$ Then $|\delta A|_2 = \eta|A|_2$(arank-onematrix$uv^$has$2$-norm$|u||v|$)and$|\delta b_*|_2 = \eta|b|2$,sotheperturbationsmeetthetolerancewithequality.Compute$\delta A,\tilde x = \tfrac{\eta|A|_2}{|\tilde x|_2},r,(\tilde x^\tilde x)/(|r|_2|\tilde x|_2) = \tfrac{\eta|A|_2|\tilde x|2}{|r|2},r$,and$\delta A*,\tilde x - \delta b* = \tfrac{\eta(|A|2|\tilde x|2 + |b|2)}{|r|2},r = r$bythedefinitionof$\eta$.Therefore$(A + \delta A*)\tilde x = A\tilde x + \delta A*\tilde x = A\tilde x + r + \delta b* = b + \delta b*$,so$\tilde x$isexactfortheperturbeddataatlevel$\eta$.Thetwoboundscoincide.$\square$

Proposition 4 (Oettli-Prager componentwise criterion). Fix $E\ge 0$, $f\ge 0$ entrywise. There exist $\delta A,\delta b$ with $|\delta A|\le \epsilon E$, $|\delta b|\le \epsilon f$, and $(A+\delta A)\tilde{x}=b+\delta b$ if and only if $|r|\le \epsilon (E|\tilde{x}|+f)$ entrywise; the least such $\epsilon$ is $\omega ={\max }_i|r_i|/(E|\tilde{x}|+f{)}_i$ (with the convention $0/0=0$ and $\rho /0=\infty$ for $\rho >0$).

Proof. Necessity. If such perturbations exist, then $r=b-A\tilde{x}=\delta A\tilde{x}-\delta b$, so componentwise $|r_i|=|{\sum }_j\delta A_{ij}{\tilde{x}}_j-\delta b_i|\le {\sum }_j|\delta A_{ij}||{\tilde{x}}_j|+|\delta b_i|\le \epsilon {\sum }_j{E}_{ij}|{\tilde{x}}_j|+\epsilon f_i=\epsilon (E|\tilde{x}|+f{)}_i$, which is the stated entrywise inequality. Sufficiency. Suppose $|r_i|\le \epsilon (E|\tilde{x}|+f{)}_i$ for every $i$. For each $i$ with $(E|\tilde{x}|+f{)}_i>0$, distribute $r_i$ proportionally: set $\delta A_{ij}=\epsilon E_{ij}\mathrm{sgn}({\tilde{x}}_j)t_i$ and $\delta b_i=-\epsilon f_i{t}_i$, where $t_i=r_i/(E|\tilde{x}|+f{)}_i\in [-1,1]$. Then $|\delta A_{ij}|=\epsilon E_{ij}|t_i|\le \epsilon E_{ij}$ and $|\delta b_i|=\epsilon f_i|t_i|\le \epsilon f_i$, and $(\delta A\tilde{x}-\delta b{)}_i=\epsilon t_i({\sum }_j{E}_{ij}|{\tilde{x}}_j|+f_i)=\epsilon t_i(E|\tilde{x}|+f{)}_i=r_i$, so $(A+\delta A)\tilde{x}=A\tilde{x}+r=b+\delta b$ with $\delta b_i=\epsilon f_i{t}_i$ chosen to absorb the bookkeeping; the construction realises the required identity. The least admissible $\epsilon$ is the smallest one for which $|r_i|\le \epsilon (E|\tilde{x}|+f{)}_i$ holds in every row, namely $\omega ={\max }_i|r_i|/(E|\tilde{x}|+f{)}_i$. $\square$

Connections Master

• Conditioning and condition numbers 43.01.02 supplies the amplification factor $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$ that this unit converts into a computable a posteriori guarantee. That unit proves the right-hand-side perturbation bound $\Vert \delta x\Vert /\Vert x\Vert \le \kappa (A)\Vert \delta b\Vert /\Vert b\Vert$ and the closed form ${\kappa }_2(A)={\sigma }_1/{\sigma }_n$; this unit completes it by perturbing $A$ as well, deriving the residual estimate $\Vert x-\tilde{x}\Vert /\Vert x\Vert \le \kappa (A)\Vert r\Vert /\Vert b\Vert$, and is the solver-level payoff of the abstract conditioning theory built there.

• Gaussian elimination, LU factorization, and its stability 43.03.01 provides the backward-error half of the ledger: GEPP returns $\tilde{x}$ with $(A+\Delta A)\tilde{x}=b$, $\Vert \Delta A\Vert =O({\rho }_n{ϵ}_{\mathrm{mach}}\Vert A\Vert )$, which is exactly a normwise backward error of order ${\rho }_n{ϵ}_{\mathrm{mach}}$. Feeding that backward error into this unit's perturbation bound yields the forward error $\kappa (A){\rho }_n{ϵ}_{\mathrm{mach}}$; the LU factors are also what make iterative refinement cheap, since the correction solve $Ad=r$ reuses the existing factorization at $O(n^2)$ cost.

• Backward stability and backward-error analysis 43.01.03 is the framework this unit instantiates at the linear-system level: the Rigal-Gaches identity $\eta (\tilde{x})=\Vert r\Vert /(\Vert A\Vert \Vert \tilde{x}\Vert +\Vert b\Vert )$ is the concrete computation of the backward error that unit defines abstractly, and the fundamental theorem "forward error $\le$ condition number $\times$ backward error" of that unit is realised here as the residual bound. That unit owns the definition of backward stability; this unit owns its a posteriori certificate for $Ax=b$.

• Cholesky factorization and the symmetric positive-definite solve 43.03.02 inherits this unit's perturbation and residual theory verbatim: a Cholesky solve of an SPD system is backward stable with an a priori growth bound, so its forward error is again $\kappa (A){ϵ}_{\mathrm{mach}}$, and the same residual estimate and iterative-refinement loop certify and improve its solutions. The conditioning $\kappa (A)={\kappa }_2(A)$ of an SPD matrix is the ratio of extreme eigenvalues, sharpening the residual bound in that symmetric setting.

• Least squares: normal equations vs QR vs SVD 43.04.01 extends this unit's perturbation analysis from the square solve to the overdetermined case, where the conditioning acquires a second term — the residual angle — and the normal-equations route squares $\kappa (A)$. The residual and backward-error language built here is the prototype that the least-squares perturbation theorem generalises, which is why normal equations are abandoned in favour of QR and SVD when $\kappa (A)$ is large.

Historical & philosophical context Master

The separation of the sensitivity of a problem from the errors of an algorithm was forced into the open by the first large linear solves on stored-program computers. Alan Turing's Rounding-off errors in matrix processes (1948) introduced a matrix condition number precisely to explain why some systems lost accuracy regardless of the arithmetic, and John von Neumann and Herman Goldstine's 1947 analysis of matrix inversion studied the propagation of rounding through elimination. The perturbation bound $\Vert \delta x\Vert /\Vert x\Vert \le \kappa (A)(\Vert \delta A\Vert /\Vert A\Vert +\Vert \delta b\Vert /\Vert b\Vert )$, in the form used today, was consolidated by the numerical-analysis school of the 1950s and 1960s and given its definitive textbook treatment by James Wilkinson.

The a posteriori side — what one can certify about a solution already computed — has two landmark results. Jean-Louis Rigal and Jean Gaches, in On the compatibility of a given solution with the data of a linear system (Journal of the ACM 14, 1967, 543–548), proved that the normwise backward error of an approximate solution is exactly the scaled residual $\Vert r\Vert /(\Vert A\Vert \Vert \tilde{x}\Vert +\Vert b\Vert )$ ^{[Rigal, J. L. & Gaches, J. — On the compatibility of a given solution with the data of a linear system]}, turning the residual from an informal indicator into a sharp optimality statement. Werner Oettli and William Prager gave the componentwise analogue in 1964. The componentwise conditioning that survives badly-scaled data is due to Robert Skeel, whose Scaling for numerical stability in Gaussian elimination (Journal of the ACM 26, 1979, 494–526) ^{[Skeel, R. D. — Scaling for numerical stability in Gaussian elimination]} introduced the condition number $\mathrm{cond}(A,x)=\Vert |A^{-1}||A||x|\Vert /\Vert x\Vert$ and proved that a single step of fixed-precision iterative refinement makes Gaussian elimination componentwise backward stable when that number is modest. Iterative refinement itself traces to Wilkinson's Rounding Errors in Algebraic Processes (Prentice-Hall, 1963) ^{[Wilkinson, J. H. — Rounding Errors in Algebraic Processes]}, and the comprehensive modern synthesis of normwise and componentwise perturbation theory, backward error, and refinement is Nicholas Higham's Accuracy and Stability of Numerical Algorithms (SIAM, 1996; 2nd ed. 2002).

Bibliography Master

@article{turing1948rounding,
  author  = {Turing, Alan M.},
  title   = {Rounding-off Errors in Matrix Processes},
  journal = {The Quarterly Journal of Mechanics and Applied Mathematics},
  volume  = {1},
  number  = {1},
  year    = {1948},
  pages   = {287--308}
}

@article{rigalgaches1967,
  author  = {Rigal, Jean-Louis and Gaches, Jean},
  title   = {On the Compatibility of a Given Solution with the Data of a Linear System},
  journal = {Journal of the ACM},
  volume  = {14},
  number  = {3},
  year    = {1967},
  pages   = {543--548}
}

@article{oettliprager1964,
  author  = {Oettli, Werner and Prager, William},
  title   = {Compatibility of Approximate Solution of Linear Equations with Given Error Bounds for Coefficients and Right-hand Sides},
  journal = {Numerische Mathematik},
  volume  = {6},
  number  = {1},
  year    = {1964},
  pages   = {405--409}
}

@article{skeel1979scaling,
  author  = {Skeel, Robert D.},
  title   = {Scaling for Numerical Stability in Gaussian Elimination},
  journal = {Journal of the ACM},
  volume  = {26},
  number  = {3},
  year    = {1979},
  pages   = {494--526}
}

@book{wilkinson1963rounding,
  author    = {Wilkinson, James H.},
  title     = {Rounding Errors in Algebraic Processes},
  publisher = {Prentice-Hall},
  year      = {1963}
}

@book{higham2002accuracy,
  author    = {Higham, Nicholas J.},
  title     = {Accuracy and Stability of Numerical Algorithms},
  edition   = {2},
  publisher = {Society for Industrial and Applied Mathematics},
  year      = {2002}
}

@book{trefethenbau1997,
  author    = {Trefethen, Lloyd N. and Bau, David},
  title     = {Numerical Linear Algebra},
  publisher = {Society for Industrial and Applied Mathematics},
  year      = {1997}
}

@book{golubvanloan2013,
  author    = {Golub, Gene H. and Van Loan, Charles F.},
  title     = {Matrix Computations},
  edition   = {4},
  publisher = {Johns Hopkins University Press},
  year      = {2013}
}

@book{demmel1997applied,
  author    = {Demmel, James W.},
  title     = {Applied Numerical Linear Algebra},
  publisher = {Society for Industrial and Applied Mathematics},
  year      = {1997}
}