Back to the on-screen lesson ·
The question a computed answer is exactly right for, why that is the error a method can be held to, and the inequality that turns it into a forward error.
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 define and compute a backward error, read one off a residual, say which familiar computations are backward stable and which are not, and derive the bound that makes forward error the product of conditioning and backward error.
You can compute the condition number of a problem, and you know it settles how much the exact answer moves when the data does. That was the problem's half of the account. This lesson is the method's half, and the two multiply.
The forward error is how far the computed answer is from the true one. The backward error is how far the data must move for the computed answer to be exactly right. The residual is what is left when the computed answer is substituted back into the equation — often the easiest way to measure a backward error. A method is backward stable when its backward error is about the size of one rounding error, and unstable when it is not.
Forward error is what anyone wants and nobody can measure: computing it needs the answer that was being asked for. Backward error replaces it with a question that can be answered — for which data is this output exactly correct? — and that turns out to be the more useful question anyway. A method is backward stable when the data never has to move by more than about a rounding error $u$, and the point of the definition is what it leaves out: it says nothing about accuracy. Floating-point addition is backward stable, because $fl(x + y) = x(1 + \delta) + y(1 + \delta)$ is the exact sum of two slightly different inputs; and adding $10^{16}$ to $1$ still loses the $1$ entirely, because the problem of adding them is ill conditioned in the sense that matters. Together the two halves give the one inequality this whole unit is about:
$$\text{relative forward error} \;\lesssim\; \kappa \times \text{backward error}.$$
Both factors are needed, and each is somebody's responsibility: the backward error is the method's, and $\kappa$ is the problem's. A residual is how a backward error is usually measured in practice — for $Ax = b$, the computed $\tilde{x}$ exactly solves $Ax = b - r$ where $r = b - A\tilde{x}$, so a small residual is a small backward error. It is not a small forward error, and the difference between those two sentences is where most of the trouble in this subject lives.
Another way: steps
Another way: example
A routine returns $\tilde{x} = 2.1$ for $5x = 10$. It is the exact solution of $5x = 10.5$, so the backward error is a half in the right-hand side, or five per cent relatively. Nothing about the true solution was needed to say so.
A small residual is read as a correct answer, and it is not one. It says the equation is nearly satisfied; a correct answer says the unknown is nearly right. The two agree only when the problem is well conditioned, and a linear system with $\kappa = 10^{8}$ will hand back a residual at the level of rounding with half the digits of the solution wrong. Conditioning belongs to the problem and stability to the algorithm. A stable method on an ill-conditioned problem returns a wrong answer and is not at fault; a good answer from an unstable method on a well-conditioned problem is luck. Only the two together say anything about the digits.
$\tilde{x}$ is returned for $Ax = b$; form $r = b - A\tilde{x}$.
One matrix-vector product.
$\tilde{x}$ solves $Ax = b - r$ exactly, so the backward error in $b$ is $\|r\|/\|b\|$.
A statement about the data.
With $\|r\|/\|b\| = 10^{-15}$ and $\kappa(A) = 10^{9}$, the solution may still be wrong in its seventh digit.
The residual did not promise otherwise.
$x = \dfrac{-b + \sqrt{b^{2} - 4ac}}{2a}$ with $b = 10^{8}$, $a = c = 1$: the numerator subtracts nearly equal numbers.
The small root.
The computed root is the exact root of no nearby quadratic: not backward stable.
The method is at fault.
$x = \dfrac{2c}{-b - \sqrt{b^{2} - 4ac}}$ is the same number, computed with an addition instead, and is backward stable.
Same problem, better method.
$\tilde{x} = 3$ solves $4x = 12$ exactly.
So the right-hand side moved from $11$ to $12$: a change of $1$.
Relatively that is $\tfrac{1}{11}$, about nine per cent — an enormous backward error, which is the right verdict on a method that returned $3$ when the answer was $2.75$.
A routine is asked for $f(x)$ and returns $\tilde{y}$. What is the **backward error** of that answer?
Match each computation to what is true of its backward error.
| Backward stable, with backward error one unit of roundoff | Backward stable, with backward error growing with the number of terms | Not backward stable: the answer is exact for no nearby problem | Backward stable in practice, with a growth factor in the bound | |
|---|---|---|---|---|
| One floating-point addition | ||||
| Summing a list of $n$ numbers in order | ||||
| The textbook quadratic formula, with $b^{2}$ far larger than $4ac$ | ||||
| Gaussian elimination with partial pivoting |
Three routines are asked to solve $7x = 49$ and return $7$, $8$ and $5$. For each, give the right-hand side it solves exactly.
| What it returned | Right-hand side it solves exactly | |
|---|---|---|
| First routine | 7 | |
| Second routine | 8 | |
| Third routine | 5 |
Put the five steps of a backward error argument into the order they depend on each other.
Number the steps in order (write the number in the box):
A root finder returns $\tilde{x}$ for a polynomial whose constant term is $42$, and $p(\tilde{x}) = \dfrac{1}{6}$. Taking the backward error into the constant term alone, what is its relative size? Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Build the argument that a backward stable method has relative forward error about $\kappa$ times its backward error.
This task has no paper form; do it on a device.
You can measure a backward error from a residual and state the inequality relating it to the forward error. Say in your own words why a small residual is not the same as a correct answer.
8. Your turn: the backward error of $\tilde{x} = 3$ for $4x = 11$, step 3