Back to the on-screen lesson ·
Correct digits as precision minus $\log_{10}\kappa$: what a computation can possibly deliver, why the lost digits are not in the code, and the three things that change the answer.
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 predict the correct digits a backward stable computation can deliver from the condition number and the precision, read the result as a line with an intercept and a slope, decide between better data, a reformulation and a wider format, and run the calculation backwards to size the precision a demanded accuracy needs.
You have the two halves of the account: a condition number belonging to the problem, and a backward error belonging to the method. You also know that their product bounds the forward error. This lesson does the arithmetic of that product in decimal digits, which is the form in which it gets used.
The unit roundoff $\varepsilon$ is the relative precision of the arithmetic: about $10^{-16}$ in double precision, $10^{-7}$ in single, $10^{-34}$ in quadruple. Attainable accuracy is the best relative error any backward stable method can reach on a problem, namely about $\kappa\varepsilon$. Reformulating a problem means replacing it by one with the same answer and a smaller condition number.
Put the two halves together and take logarithms. A backward stable method has relative forward error about $\kappa\varepsilon$, so with $\kappa = 10^{k}$ and $\varepsilon = 10^{-P}$ the error is about $10^{k - P}$ — which is to say about $P - k$ correct decimal digits:
$$\text{correct digits} \;\approx\; \text{digits the format supplies} \;-\; \log_{10}\kappa.$$
It is a subtraction, and everything useful follows from that. Precision is an intercept and conditioning is a slope: buying a wider format moves every answer up by a fixed amount and leaves the rate of loss untouched. A negative result is a real result — it means no digit of the output is meaningful — and it is reached without choosing an algorithm, which is what makes the calculation worth doing first rather than last. When the number comes out too small there are exactly three moves: improve the data, reformulate the problem so that $\kappa$ is smaller, or compute in a wider format. Writing a cleverer algorithm is not among them, because every algorithm for the problem faces the same $\kappa$ and a backward stable one already attains the bound. Run the other way, the same subtraction is a design rule: to keep $d$ digits through a condition number of $10^{k}$, start with $d + k$.
Another way: steps
Another way: example
$\kappa = 10^{10}$ in double precision leaves about six correct digits. The same problem in single precision leaves none at all, and in quadruple precision leaves twenty-four. The problem did not change; only the intercept did.
The lost digits are hunted for in the code. They are not there. A method that is already backward stable has no accuracy left to recover, and the hours spent rearranging its arithmetic will produce an answer exactly as wrong as before. The other half of the mistake is to read a stable, plausible, repeatable output as evidence of correctness: an ill-conditioned problem gives the same wrong answer every time, and reproducibility is not accuracy.
A linear system with $\kappa_2(A) = 10^{12}$, solved by a backward stable factorisation in double precision.
Twelve digits of conditioning.
$16 - 12 = 4$: about four correct digits in the solution.
The subtraction.
The residual will be at the level of $10^{-16}$ regardless, which tells you the solver worked and nothing about the four digits.
Backward small, forward bounded.
Summing an alternating series with terms up to $10^{8}$ and a sum of order $1$: $\kappa \approx 10^{8}$.
Cancellation as conditioning.
Double precision leaves eight digits; single precision leaves none.
The subtraction again.
Rewriting the series so the terms do not cancel changes $\kappa$ itself — a different problem with the same answer.
The lever that works.
Single precision supplies about $7$ decimal digits.
The condition number costs $6$ of them.
So about one digit survives — and the first thing to do is not to open the code but to ask whether the problem can be posed differently.
A backward stable method runs in double precision, where $\varepsilon \approx 10^{-16}$, on a problem with condition number $10^{12}$. About how many correct decimal digits should the answer have?
Answer:
A backward stable method is run on a problem with condition number $10^{5}$ in three formats, supplying about $7$, $16$ and $34$ decimal digits. Give the correct digits to expect in each.
| Digits supplied | Correct digits expected | |
|---|---|---|
| Single precision | 7 | |
| Double precision | 16 | |
| Quadruple precision | 34 |
In double precision a backward stable method is run on three problems with condition numbers $10^{2}$, $10^{4}$ and $10^{6}$. Plot the correct digits against the exponent of the condition number.
Plot your answer on the grid:
Match each symptom to the thing that will actually fix it.
| Rewrite the method: it is unstable | Reformulate the problem or improve the data | Compute in a wider format | Nothing: this is the best the problem allows | |
|---|---|---|---|---|
| Large residual, well-conditioned problem | ||||
| Tiny residual, answer badly wrong | ||||
| Too few digits, condition number moderate and known | ||||
| Relative error about $\kappa\varepsilon$ |
An answer is wanted to $7$ correct decimal digits, on a problem with condition number $10^{14}$, using a backward stable method. How many digits must the arithmetic supply, and how many more is that than double precision provides?
The arithmetic must supply about n digits, which is m more than double precision gives.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A problem has condition number $10^{19}$ and the data is exact only to the last stored digit. The computation runs in double precision. What should be done?
You can count the digits a problem allows and name the three things that change that count. Say in your own words why a cleverer algorithm is not one of them.
8. Your turn: digits available with $\kappa = 10^{6}$ in single precision, step 3