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?
Best Answer
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.