Normwise and componentwise backward error for an approximate linear-system solution

Let $n\ge 1$, let $p\in \mathbb{Q}$ with $p\ge 1$, let $A=(a_{ij})\in {\mathrm{GL}}_n(\mathbb{R})$, let $b=(b_i)\in {\mathbb{R}}^n$, and let $\widehat{x}\in {\mathbb{R}}^n$ be an approximate solution of the system $Ax=b$ with residual $r=b-A\widehat{x}$.

Normwise backward error. The normwise backward error of $\widehat{x}$ is

${\eta }_p(\widehat{x}):=\inf \{\epsilon \ge 0:\text{there are }\mathrm{\Delta }A\in M_n(\mathbb{R}),\mathrm{\Delta }b\in {\mathbb{R}}^n\text{ with }(A+\mathrm{\Delta }A)\widehat{x}=b+\mathrm{\Delta }b,\parallel \mathrm{\Delta }A{\parallel }_p\le \epsilon \parallel A{\parallel }_p,\parallel \mathrm{\Delta }b{\parallel }_p\le \epsilon \parallel b{\parallel }_p\},$

where $\parallel \cdot {\parallel }_p$ on matrices is the induced norm of The matrix norm induced by a published vector p-norm and on vectors the $p$-norm.

Componentwise backward error. The componentwise backward error of $\widehat{x}$ is

$\omega (\widehat{x}):=\inf \{\epsilon \ge 0:\text{there are }\mathrm{\Delta }A=(\mathrm{\Delta }{a}_{ij}),\mathrm{\Delta }b=(\mathrm{\Delta }{b}_i)\text{ with }(A+\mathrm{\Delta }A)\widehat{x}=b+\mathrm{\Delta }b,\mid \mathrm{\Delta }{a}_{ij}\mid \le \epsilon \mid a_{ij}\mid \text{ for all }i,j<n,\mid \mathrm{\Delta }{b}_i\mid \le \epsilon \mid b_i\mid \text{ for all }i<n\},$

with $\mathrm{\mid }\cdot \mathrm{\mid }$ the absolute value (Absolute value in an ordered field).

Both infima are over nonempty sets, so they are well defined. The single choice $\mathrm{\Delta }A:=-A$ and $\mathrm{\Delta }b:=-b$ always satisfies the defining relation, because $(A+\mathrm{\Delta }A)\widehat{x}=0=b+\mathrm{\Delta }b$. It is admissible with $\epsilon =1$ for both notions: normwise, $\parallel \mathrm{\Delta }A{\parallel }_p=\parallel A{\parallel }_p$ and $\parallel \mathrm{\Delta }b{\parallel }_p=\parallel b{\parallel }_p$; componentwise, $\mathrm{\mid }\mathrm{\Delta }{a}_{ij}\mathrm{\mid }=\mathrm{\mid }{a}_{ij}\mathrm{\mid }$ and $\mathrm{\mid }\mathrm{\Delta }{b}_i\mathrm{\mid }=\mathrm{\mid }{b}_i\mathrm{\mid }$. Hence each defining set is a nonempty subset of $[0,\mathrm{\infty })$ and therefore has an infimum.

In words: ${\eta }_p(\widehat{x})$ is the smallest factor by which the data $(A,b)$ must be perturbed, measured in the $p$-norm with the weights $\parallel A{\parallel }_p$ and $\parallel b{\parallel }_p$, for the computed answer $\widehat{x}$ to be exactly right; $\omega (\widehat{x})$ measures the same perturbation entrywise. The explicit residual formulas for both are Residual formulas for normwise and componentwise backward error.

• Backward error is about the data, not the answer. An approximate solution with small backward error is the exact solution of a nearby problem; the size of the forward error $\parallel x-\widehat{x}\parallel$ is governed separately by the condition number through Local conditioning times backward error controls forward error to first order.

• The two notions are not interchangeable. Componentwise admissibility controls every entry and preserves the zero pattern of the data, whereas normwise admissibility controls only the declared aggregate norms. Neither definition gives the same numerical tolerance as the other without dimension- and data-dependent comparison factors. Sparse matrices make the distinction especially visible: $\omega$ preserves their zero pattern but ${\eta }_p$ does not.