Back to the on-screen lesson ·
Separating a problem that is sensitive to its inputs from a method that loses digits it need not, and reading a condition number as a count of digits.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute a condition number, read it as a number of significant digits lost, decide whether a disappointing answer is the fault of the problem or of the method, and say what a small residual does and does not establish.
You have seen one expression computed two ways with wildly different accuracy, and you know the cure was algebraic. That example had a well-behaved answer and a bad route to it. This lesson names the other case, where the answer itself is the trouble.
A problem is well conditioned when a small relative change in the input makes a small relative change in the answer, and ill conditioned when it does not; the condition number is the worst ratio of the two. An algorithm is stable when the answer it returns is the exact answer to a slightly perturbed problem. The residual is what is left when the computed answer is substituted back into the equation; the error is the distance from the true answer.
Two different things can go wrong, and confusing them wastes effort on the one that cannot be fixed. Conditioning belongs to the problem. Perturb the input by a relative $\delta$ and ask how far the exact answer moves; the worst ratio is the condition number $\kappa$, and for a differentiable $f$ it is $\left|\dfrac{x f'(x)}{f(x)}\right|$. It is a fact about the mathematics, and no algorithm, precision or cleverness reduces it. Stability belongs to the method. A stable method returns the exact answer to a problem within a relative $\eta$ of the one you asked — a small backward error. Put the two together and you get the rule that governs everything here: forward error $\lesssim \kappa \times$ backward error. A stable method on an ill-conditioned problem still returns rubbish, and correctly so. Read $\kappa \approx 10^{j}$ as this problem costs $j$ significant digits. The residual is the measurable proxy for backward error, which is why a small residual establishes so much less than it appears to.
Another way: steps
Another way: example
Evaluating $\dfrac{1}{1 - x}$ near $x = 1$ has $\kappa = \dfrac{|x|}{|1 - x|}$, which is enormous: at $x = 0.9999$ it is about $10^{4}$, so four digits are gone before any arithmetic happens. That is the problem's fault, and computing it in quadruple precision buys back four digits rather than fixing anything.
A small residual says the equation is nearly satisfied; a small error says the answer is nearly right. They are the same statement only when the problem is well conditioned, and the whole of this subject's trouble lives in the gap between them. A solver that reports a residual near the rounding level has told you it is stable. Whether the answer is any good is a separate question, and the condition number is the only thing that answers it.
The lines $y = x$ and $y = 1.0001x - 0.0001$ cross at $(1, 1)$.
Write the problem down first.
Change the second line's slope in its fifth digit and the crossing point moves by a large fraction of itself.
The exact answer is sensitive.
So the problem is ill conditioned; a perfect solver in exact arithmetic would still give an answer you could not trust to many digits, because the inputs do not determine it to many digits.
No method can repair this.
The small root of $x^{2} - 10^{8}x + 1$ is $10^{-8}$, and it barely moves when the coefficients are nudged.
Well conditioned.
The textbook formula returns $0$ in double precision, so the relative error is $1$.
The method is unstable.
Using the product of the roots returns it in full. Since a rewrite fixed it, the problem was never the difficulty.
The test for instability.
A million is $10^{6}$, so the answer loses about six significant digits.
Inputs known to sixteen digits therefore determine the answer to about ten.
And a method that achieved ten has done everything that could be done, however wrong the answer looks.
Each of these computations returns an answer with about $10$ digits wrong. Match each to where the fault lies.
| An ill-conditioned problem: no method can do better | An unstable route to a well-determined quantity | An unstable choice inside the method, cured by swapping rows | Neither: a well-conditioned problem met by a stable method | |
|---|---|---|---|---|
| Crossing two lines that are almost parallel | ||||
| Subtracting two numbers that agree in $10$ digits | ||||
| Eliminating with a pivot far smaller than the entries below it | ||||
| Evaluating a polynomial by Horner's rule, far from its roots |
A computed solution $\hat{x}$ of a linear system leaves a residual $\lVert b - A\hat{x}\rVert$ of about $10^{-12}$, and the system's condition number is about $10^{2}$. What follows about the error $\lVert x - \hat{x}\rVert$?
Computing $f(x) = x - 16$ has relative condition number $\dfrac{|x|}{|x - 16|}$. Fill it in at the three points shown.
| Value of x | Condition number | |
|---|---|---|
| First point | 17 | |
| Second point | 18 | |
| Third point | 20 |
A computation with inputs known to $9$ digits has returned an answer you distrust. Put the five steps of diagnosing it into order.
Number the steps in order (write the number in the box):
Computing $f(x) = x - 15$ has relative condition number $\dfrac{|x|}{|x - 15|}$. For which positive $x$ is that condition number greater than $4$?
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A problem has condition number about $10^{4}$ and its input is known to $15$ correct significant digits. To how many correct significant digits is the answer determined, even by a perfect method?
Answer:
You can tell an ill-conditioned problem from an unstable method and say how many digits a condition number costs. Say in your own words why a small residual is not the same thing as a small error.
8. Your turn: how many digits does a condition number of a million cost?, step 3