Are there ill-conditioned problems in infinite precision arithmetric? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:15:32Z http://mathoverflow.net/feeds/question/66679 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66679/are-there-ill-conditioned-problems-in-infinite-precision-arithmetric Are there ill-conditioned problems in infinite precision arithmetric? alext87 2011-06-01T18:40:12Z 2011-07-03T15:25:05Z <p>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. </p> <p>For instance it is common to call the following problem, an ill-conditioned problem:</p> <p>Finding the roots of a quadratic polynomial. The example is from Datta, BN Numerical Linear Algebra and Applications SIAM, Second edition (2010)</p> <p>$z^2-2z+1=0 \rightarrow z^2-2.0001z+1=0$</p> <p>since a relatively small change in the polynomial coefficients can cause a much larger perturbation in the polynomial roots. </p> <p>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.</p> <p>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. </p> <p>To help clarify the situation I have two closely related questions:</p> <ol> <li><p>Is ill-conditioning an issue in arbitrarily high precision?</p></li> <li><p>Is there an ill-conditioned problem which remains ill-conditioned even in infinite precision computing?</p></li> </ol> http://mathoverflow.net/questions/66679/are-there-ill-conditioned-problems-in-infinite-precision-arithmetric/66682#66682 Answer by Federico Poloni for Are there ill-conditioned problems in infinite precision arithmetric? Federico Poloni 2011-06-01T19:34:40Z 2011-06-01T21:16:26Z <p>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".</p> <p>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.</p> <p>Ill-conditioning <em>per se</em> 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 <em>algorithmic error</em> or <em>stability</em> of the algorithm.</p> http://mathoverflow.net/questions/66679/are-there-ill-conditioned-problems-in-infinite-precision-arithmetric/66698#66698 Answer by Brian Borchers for Are there ill-conditioned problems in infinite precision arithmetric? Brian Borchers 2011-06-02T00:44:46Z 2011-06-02T00:44:46Z <p>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. </p> <p>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. </p> http://mathoverflow.net/questions/66679/are-there-ill-conditioned-problems-in-infinite-precision-arithmetric/69385#69385 Answer by Derek O'Connor for Are there ill-conditioned problems in infinite precision arithmetric? Derek O'Connor 2011-07-03T08:55:21Z 2011-07-03T15:25:05Z <p>This was meant to be a comment on Federico Poloni's answer, but I don't see any <em>add-comment</em> button.</p> <p>Consider the two standard statistical calculations, <strong>sum</strong> and <strong>sum-of-squared-deviations</strong>:</p> <p>$s(x) = \sum_{i=1}^nx_i,\$ and $\ \ d(x) = \sum_{i=1}^n(x_i-s(x)/n)^2.$</p> <p>The 2-norm condition numbers of these mappings are</p> <p>$\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)}}$</p> <p>If $x = (m,m+1,m+2)$, then $s(x) = 3m+3$, and $d(x) = 2$, and we have:</p> <p>$\kappa_2(s(x)) \approx 1$, and $\kappa_2(d(x)) \approx m$, for large $m$.</p> <p>This means that $s(x)$ is well-conditioned for this data, while $d(x)$ is ill-conditioned for the same data.</p> <p>It is important to realize that it is the <em>problem and its input data</em> that are well- or ill-conditioned and not just the data.</p>