Conditioning of a linear system

Let’s connect the forward and backward errors when solving a linear system.

Assume that $Ax=b$ and $(A+E)\tilde{x}=b+e$ where $\tilde{x}$ is the solution produced by some numerical algorithm.

$E$ and $e$ are the backward errors.

The forward error $\tilde{x}-x$ can be bounded using:

$$\frac{\Vert \tilde{x}-x\Vert }{\Vert x\Vert }\le \frac{\kappa (A)}{1-\kappa (A)\frac{\Vert E\Vert }{\Vert A\Vert }}\left(\frac{\Vert E\Vert }{\Vert A\Vert }+\frac{\Vert e\Vert }{\Vert b\Vert }\right)$$

• $x$ stands for the output now, when it was an input before.
• $\kappa (A)=\Vert A{\Vert }_2\Vert A^{-1}{\Vert }_2$ is the condition number of matrix $A$.
• This result assumes that $\kappa (A)\frac{\Vert E\Vert }{\Vert A\Vert }$ is small compared to 1.

Illustration of the condition number of matrix

The condition number $\kappa (A)$ cannot be changed. Only the backward errors $\Vert E\Vert$ and $\Vert e\Vert$ can be controlled. A good algorithm has a backward error on the order of $u$.

Stable algorithm: an algorithm where $\Vert E\Vert$ and $\Vert e\Vert$ can be controlled. Typically, stable algorithms achieve $\Vert E\Vert \in O(u)$ and $\Vert e\Vert \in O(u)$ where $u$ is the unit roundoff error.

Stability of the LU factorization, Sensitivity analysis, Forward and backward error, Floating point arithmetic and unit roundoff error