Are there ill-conditioned problems in infinite precision arithmetric? - MathOverflow

Are there ill-conditioned problems in infinite precision arithmetric?

2011-06-01T18:40:12Z

It is hoped that in the future with the advent of quantum computing that fundamental operations on a computer will have arbitrarily high precision. Moreover, that even with such high precision, computation times with be realistic. An important concept in Numerical Analysis is ill-conditioning.

For instance it is common to call the following problem, an ill-conditioned problem:

Finding the roots of a quadratic polynomial. The example is from Datta, BN Numerical Linear Algebra and Applications SIAM, Second edition (2010)

$ z^2-2z+1=0 \rightarrow z^2-2.0001z+1=0 $

since a relatively small change in the polynomial coefficients can cause a much larger perturbation in the polynomial roots.

However the ill-conditioning doesn't seem to be part of the problem because in arbitrarily high precision we have the quadratic formula allowing us to compute the roots. The ill-conditioning seems to be caused by working in finite precision which is not inherent to the problem.

Researchers often talk about the difference between an ill-conditioned problem and an ill-conditioned method of solving. This distinction seems to be entirely blurred to me.

To help clarify the situation I have two closely related questions:

Is ill-conditioning an issue in arbitrarily high precision?
Is there an ill-conditioned problem which remains ill-conditioned even in infinite precision computing?

Answer by Federico Poloni for Are there ill-conditioned problems in infinite precision arithmetric?

2011-06-01T19:34:40Z

Ill-conditioning isn't a concept that depends on the precision that you use to compute the solution. "A small change in the data turns into a large change of the solution" isn't a concept that involves actual computation. Think of it as "the map data $\mapsto$ solution has a large Lipschitz constant".

The error on the input data does not come only from finite precision representation: most data you put into a computer come from physical measurements or approximation processes, and often the error implied by these measurement/processes is way larger than one part in $10^{-16}$. How many physical constants do we know up to that precision, for instance? Ill-conditioning says that you need to provide your input data with a large precision, otherwise any solution you get will be rubbish, even in infinite precision arithmetic.

Ill-conditioning per se refers only on the sensitivity to input data and is independent of the actual method you use to compute a solution. The error introduced by using finite precision along the computation (highly depending on the algorithm, including order of summation and parenthesization) is often referred to as algorithmic error or stability of the algorithm.

Answer by Brian Borchers for Are there ill-conditioned problems in infinite precision arithmetric?

2011-06-02T00:44:46Z

It's worth pointing out that many inverse problems in the functional analytic setting go beyond ill-conditioning to ill-posedness. That is, a small change in the data (noise) can lead to an aribtrarily large change in the solution to the inverse problem.

In finite dimensions a linear system can be well or ill conditioned, but if the system isn't singular, then there will be a bound (the condition number) on how badly noise in the right hand side of the system of equations can grow in the solution. In the infinite dimensional setting there isn't necessarily even such a bound.

Answer by Derek O'Connor for Are there ill-conditioned problems in infinite precision arithmetric?

2011-07-03T08:55:21Z

This was meant to be a comment on Federico Poloni's answer, but I don't see any add-comment button.

Consider the two standard statistical calculations, sum and sum-of-squared-deviations:

$s(x) = \sum_{i=1}^nx_i,\ $ and $\ \ d(x) = \sum_{i=1}^n(x_i-s(x)/n)^2.$

The 2-norm condition numbers of these mappings are

$\kappa_2(s(x)) = \sqrt{n\frac{\sum x_i^2}{|\sum x_i|^2} },\ \ $ and $\ \ \kappa_2(d(x)) = \sqrt{\frac{\sum x_i^2}{d(x)}}$

If $x = (m,m+1,m+2)$, then $s(x) = 3m+3$, and $d(x) = 2$, and we have:

$\kappa_2(s(x)) \approx 1$, and $\kappa_2(d(x)) \approx m$, for large $m$.

This means that $s(x)$ is well-conditioned for this data, while $d(x)$ is ill-conditioned for the same data.

It is important to realize that it is the problem and its input data that are well- or ill-conditioned and not just the data.