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

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:

1. Is ill-conditioning an issue in arbitrarily high precision?

2. Is there an ill-conditioned problem which remains ill-conditioned even in infinite precision computing?

-
Is the connection between quantum computing and arbitrarily high precision operations obvious? – jc Jun 1 2011 at 19:17
Regarding your example, the first polynomial has a double root. This means that its coefficients lie on a very special lower dimensional set given by the vanishing of the discriminant. So in this case the problem is ill-conditioned because arbitrarily tiny perturbations exist that will take you off this set and change the character of the solution. So I don't see how any assumed level of precision enters the definition of ill-conditioning given for instance in en.wikipedia.org/wiki/Condition_number – jc Jun 1 2011 at 19:25
However, the problem of finding the roots of $z^2-2z+1=0$ can be computed exactly on a computer because the numbers $1$ and $2$ have exact representations as floating point numbers. Are there severely ill-conditioned problems which cause no concern when computing in finite precision? – alext87 Jun 2 2011 at 6:48
I don't believe in your first paragraph about quantum computing. – Zsbán Ambrus Jul 3 2011 at 12:49

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.

-
Federico's answer is good. I would just like to add that if a problem is ill-conditioned (in infinite precision arithmetic), then necessarily it will be algorithmically unstable (in finite precision arithmetic). The reason is that the initial data will need to be rounded to the nearest floating-point-representable number. Even if the algorithm commits no further errors, it will still have large error because of this initial rounding error. – David Harris Jun 1 2011 at 20:10
To support the point "arithmetic precision is not so much relevant with respect to errors in the data", I can add that in the last 20 years the precision used in scientific computation hasn't increased, despite the huge advances in computational power. In fact in some cases it has decreased, since GPU architectures often support only single precision. So, while 640k are not enough for anybody, apparently 16 digits are. – Federico Poloni Jun 1 2011 at 21:10
@Federico: GPU's are designed for graphics (i.e. games), not scientific computing. GPU manufacturers typically add double-precision support specifically to accommodate scientific computing. Current or forthcoming x86 chips will have extension for quad-precision. (And of course there are multiprecision libraries). – David Harris Jun 1 2011 at 21:41

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.

-

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.

-