numerical methods

Consider a linear problem $$Ax = b \tag{1}$$ This problem is well conditioned if difference between $\textbf{exact}$ solution to this problem and $\textbf{exact}$ solution of a slighty perturbed problem $(A+\delta A)y = b+\delta b$ is small for any small perturbations $\delta A$, $\delta b$. If the problem is badly conditioned, then there exists some small perturbations $\delta A$, $\delta b$ such that difference between $x$ and $y$ is large.

Suppose, that the problem (1) is solved using some algorithm and denote the solution by $\hat{x}$. Usually $\hat{x}$ is not an exact solution to (1). A method used to solve (1) is called backward stable if for any $A$ and $b$ it computes a solution $\hat{x}$ with small backward error, that is $\hat{x}$ is an exact solution of some slightly perturbed problem $(A+\delta A)\hat{x} = b+\delta b$. For a problem (1), the backward error is closely related to norm of residuals $r = A\hat{x} - b$.

Forward error is defined as a distance between true solution $x$ to (1) and solution computed by given method $\hat{x}$. This forward error can be estimated as $$\text{forward error} \leq \text{condition number} \times \text{backward error} \tag{2}$$

The backward error and condition number are completely unrelated. It is possible to have small backward error for badly conditioned problem or large backward error for well conditioned problem. For example consider a problem $$\left[\begin{array}{cc}\epsilon & 1\\1 &\epsilon\end{array}\right]x = b$$ for some small $\epsilon$. This problem is well conditioned. However if this problem is solved using LU method without pivoting, then the backward error is large and computed solution is highly inaccurate.

If condition number is low and a stable algorithm is used (thus the backward error is also small), then we can be sure, that (1) is solved accurately. It is however possible, that an unstable algorithm applied to badly conditioned problem gives an accurate solution. It is always possible to estimate the forward error for a given problem (1) using aposteriori error analysis, which do not use (2).