Right-hand-side perturbations in Ax = b are amplified by the condition number

Let $n\ge 1$, let $p\in \mathbb{Q}$ with $p\ge 1$, let $A\in {\mathrm{GL}}_n(\mathbb{R})$, let $b,\delta b\in {\mathbb{R}}^n$ with $b\mathrm{\ne }0$, let $x=A^{-1}b$, and let $\delta x\in {\mathbb{R}}^n$ satisfy $A(x+\delta x)=b+\delta b$. Then

$\frac{\parallel \delta x{\parallel }_p}{\parallel x{\parallel }_p}\le {\kappa }_p(A)\frac{\parallel \delta b{\parallel }_p}{\parallel b{\parallel }_p}\mathrm{.}$

In words: the relative perturbation of the solution is at most the condition number ${\kappa }_p(A)$ of The condition number kappa_p(A) = ||A||_p ||A^{-1}||_p of a nonsingular linear system times the relative perturbation of the right-hand side.

• The bound is sharp at $p=2$. The constant ${\kappa }_2(A)$ is optimal, but the two equalities in the proof are attained on different singular directions: choose $x$ along a right singular vector for the largest singular value of $A$, so $b=Ax$ has norm ${\sigma }_{\max }\parallel x{\parallel }_2$, and choose $\delta b$ along a left singular vector for the smallest singular value, so $\parallel A^{-1}\delta b{\parallel }_2={\sigma }_{\min }^{}\parallel \delta b{\parallel }_2$. Then the bound is attained with coefficient ${\sigma }_{\max }\mathrm{/}{\sigma }_{\min }={\kappa }_2(A)$.