Well-conditioned problem and a stable algorithm?

Question

I am trying to figure out the difference between Well-conditioned problem and a Stable algorithm:
A well-conditioned problem is one in which rounding errors play very little role.
A stable algorithm is one in which rounding errors are guaranteed not to play a big role.

Which one is true?

Answer 1

I would formulate it slightly different :

• A well conditioned problem is a problem where a small change of the input cannot lead to a big change of the output.

• A stable algorithm is an algorithm that avoids that small errors are summing up to a big error. For every input, the result has an accuracy not much worse than the accuracy with which the single steps are done.

Note that not only rounding errors can play a role. Some algorithms are based on approximation-methods that give an error even in the case of exact calculation.

An example is Simpson's rule to calculate the integral. Even, if the method is done with exact values and each step is done exactly , the result is not exact.

Stable in this case means that we do not have a significant bigger error than the inevitable error.

Answer 2

Maybe it is useful to make it a little more quantitative. For the sake of simplicity, imagine that you want to compute the values of $f:\mathbb{R} \to \mathbb{R}$, using an $n$-steps algorithm. Taking first order approximations of the error, you can see that the final relative error can be written like

$$ \varepsilon_{f(x)} = Q_0(x) \varepsilon_x + \sum_{i=1}^n Q_i(x)\varepsilon_{r_i}, $$

where $\varepsilon_x$ is the relative error in the input and $\varepsilon_{r_i}$ are the rounding errors in each step of the algorithm. By the way, $Q_0(x)$ is the condition number given by $x f'(x)/f(x)$.

Well conditioned means that $Q_0$ is bounded, stable means that $Q_i, i = 0, \cdots, n$ are all bounded.