Well-posed vs Well-conditioned

What's the difference between a well-posed (ill-posed) and well-conditioned (ill-conditioned) problem?

According to Wikipedia:

Even if a problem is well-posed, it may still be ill-conditioned, meaning that a small error in the initial data can result in much larger errors in the answers.

Solution 1:

According to the book Numerical Analysis in Modern Scientific Computing: An Introduction, 2nd edition, by Andreas Hohmann and Peter Deuflhard, second chapter on "Error Analysis":

Definition 2.2

The absolute norm-wise condition number of the problem $(f, x)$ is the smallest number $K_{abs} \geq 0$, such that

$$|f(\tilde{x}) - f(x)| \dot{\leq} K_{abs} \cdot |\tilde{x} - x|, \text{ for $\tilde{x} \mapsto x$}$$

The problem $(f, x)$ is said to be ill-posed whenever such a number ($K_{abs}$) does not exist, which is formally equivalent to $K_{abs} = \infty$.

Analogously, the relative norm-wise condition number of $(f, x)$ is the smallest number $K_{rel} \geq 0$, such that

$$\frac{|f(\tilde{x}) - f(x)|}{|f(x)|} \dot{\leq} K_{rel} \cdot \frac{|\tilde{x} - x|}{|x|}, \text{ for $\tilde{x} \mapsto x$}$$

Thus $K_{abs}$ and $K_{rel}$ describe the increase of the absolute and the relative errors, respectively.

A problem $(f, x)$ is said to be well-conditioned when its condition number is small and ill-conditioned when its large. Naturally, the meaning of "small" and "large" has to be considered separately for each problem.

Solution 2:

I think this could be explained in a good way by looking at an example.

Find roots of a polynomial

is well-posed.

However, for some polynomials, a very small coefficient perturbation can affect the roots dramatically, meaning lets say a root changes tens orders of magnitude more than coefficient change. This is actually (for many people) one of the most surprising results in mathematics. Most of the time, this will not be the case, however this still poses a difficult problem in numerical analysis.

Following example is from a Matlab blog post called "Wilkinson’s Polynomials"

Observe this polynomial

$$ w(x) = \prod_{i=1}^{20} (x - i) = (x-1)(x-2) \ldots (x-20)$$

It has roots $1, 2, \dots, 20$.

Now observe this family of polynomials

$$ w(x) - \alpha x^{19}, \alpha = \pm 2^{-k}, k=23, 24, \dots, 36 $$

The behavior of roots is illustrated in this picture (red is for negative coefficient perturbation, black for positive)

A summary and further info on this topic can be found here.