Numerical Linear Algebra Stability: Forward, Backward, and Mixed Errors
In the realm of numerical linear algebra, the goal is to find an accurate solution to a mathematical problem using an algorithm. However, because computers use finite precision, the result produced by an algorithm—denoted as y*—rarely matches the exact theoretical solution y. These discrepancies primarily arise from round-off error (the result of approximating real numbers with a finite number of digits) and truncation error (the result of approximating an infinite process with a finite one).
To determine if an algorithm is reliable, mathematicians use the concept of stability. Stability is not a single definition but a framework used to quantify how errors propagate through a calculation.
Defining Forward and Backward Error
To analyze stability, we first define the problem as a function f that maps input data x to a solution y. When we run a numerical algorithm, we get a result y*. The difference between this result and the true solution is known as the forward error, expressed as Δy = y* − y.
Conversely, the backward error (Δx) asks a different question: "What input would have produced this exact result?" It is defined as the smallest change to the input data such that f(x + Δx) = y*. Essentially, the backward error identifies the problem the algorithm actually solved rather than the one it was intended to solve.
While absolute errors are useful, practitioners often use the relative error (|Δx| / |x|) to provide a more meaningful context regarding the scale of the input data.
The Role of the Condition Number
Forward and backward errors are not independent; they are linked by the condition number of the problem. The condition number measures how sensitive the solution is to small changes in the input. Specifically, the magnitude of the forward error is, at most, the product of the condition number and the magnitude of the backward error.
Types of Numerical Stability
Backward Stability
An algorithm is considered backward stable if the backward error remains small for all possible inputs. In this context, "small" typically means the error is of the same order as, or only slightly larger than, the unit round-off (the smallest difference between two representable numbers in a floating-point system).
Forward Stability
An algorithm is forward stable if its forward error, when divided by the condition number of the problem, is small. In simpler terms, a forward stable algorithm produces a result with a magnitude of error similar to that of a backward stable algorithm.
Mixed Stability
Mixed stability is a more general concept that blends both forward and backward perspectives. An algorithm is stable in this sense if it solves a nearby problem approximately. This means there exists a Δx such that both the backward error (Δx) and the difference between the result and the solution to that nearby problem (f(x + Δx) − y*) are both small.
Because mixed stability is a broader requirement, any algorithm that is backward stable is automatically stable in the mixed sense.
Key Facts
- Forward Error: The difference between the computed result and the true solution (Δy = y* − y).
- Backward Error: The smallest change to the input (Δx) that makes the computed result the exact solution.
- Condition Number: The factor that relates backward error to forward error.
- Backward Stability: Occurs when the backward error is consistently small (near the unit round-off).
- Mixed Stability: A general state where an algorithm solves a nearby problem approximately.
Stability Comparison Summary
| Stability Type | Primary Focus | Requirement for Stability |
|---|---|---|
| Backward | Input Perturbation | Backward error Δx is small for all inputs. |
| Forward | Output Accuracy | Forward error divided by condition number is small. |
| Mixed | Hybrid Approach | Both Δx and f(x + Δx) − y* are small. |
Frequently Asked Questions
What is the difference between round-off and truncation error?
Round-off error occurs because computers cannot represent all real numbers exactly, leading to small precision losses. Truncation error occurs when a mathematical process (like an infinite series) is cut short or approximated by a finite number of steps.
Why is the condition number important?
The condition number tells us how much an error in the input (backward error) will be amplified in the final output (forward error). A high condition number indicates an "ill-conditioned" problem where small input changes lead to large output changes.
Is a backward stable algorithm always forward stable?
Yes, because a backward stable algorithm ensures the backward error is small, and the forward error is bounded by the product of that small backward error and the condition number, matching the criteria for forward stability.
What does it mean for an algorithm to solve a "nearby problem"?
It means that while the algorithm didn't solve the exact problem you gave it (x), it solved a problem with slightly different data (x + Δx) almost perfectly, where the difference Δx is negligible.