A well-defined sum can be hard to compute accurately
Adding a long list seems simpler than solving a system, but rounding occurs at every addition. Moreover, cancellation can make the result highly sensitive to perturbations in the input. These are different issues: one concerns the mathematical sum, the other the algorithm used to evaluate it.
For real numbers , put .
Definition 1.2.1
(Condition number of a sum)
When , the relative condition number of for componentwise relative perturbations is
If , a nonzero absolute perturbation has no finite relative error measured against , so is not defined.
Proposition 1.2.2
(Sensitivity of a sum to componentwise perturbations)
If for every and , then
For real inputs the bound is sharp.
Proof
(Triangle inequality and an aligned perturbation)
Since , the triangle inequality gives ; divide by for the relative form. Choosing makes every perturbation add in the same direction, so and equality holds.
Sequential addition in a standard model
Definition 1.2.3
(Rounding model and the constant )
Assume each floating-point addition in the computation satisfies
where is a unit roundoff bound. This relative model requires the operations to remain in its validity range; overflow, underflow and exceptional values need separate treatment. For put
Let be obtained by sequentially adding the represented inputs, and , and assume .
Theorem 1.2.4
(Error bound for sequential summation)
For ,
The model applies to the represented inputs; error introduced in representing the original data must be accounted for separately.
Proof
(Unrolling the recurrence)
For write with . Unrolling gives
Each product has factors. Because , each product differs from one by at most . Bernoulli's inequality for the exponent gives , so for we get and hence . Since increases with , every product differs from one by at most . Therefore
Proof X-ray
Where each hypothesis enters
The assumption is used once, to make positive in the Bernoulli step. The range assumption is used for every addition, since each needs its own factor . The key move is to replace a product of rounding factors by a single bound that does not depend on the signs of the . Because that bound is attached to each separately, the proof closes with , not with .
If , division yields
Thus even a small backward perturbation can produce a large relative forward error when the sum is ill-conditioned. Conversely, a large condition number is a worst-case warning, not a claim that every ordering or every rounding realization has a large error. The factor comes from the arithmetic model and the number of rounding steps; the factor comes from the input values and their cancellation. Improving the summation algorithm can reduce the first factor; it cannot change the sensitivity of the underlying sum to uncertain data.
Quick check
(Compute for .)
Solution · Answer
The sum is and the sum of magnitudes is , so .
Quick check
(What is for positive inputs with nonzero sum?)
Solution · Answer
It is , because when every is positive.
Ordering and examples
Worked example 1.2.5
(Cancellation and order of addition)
The exact sum of is . In an arithmetic where , left-to-right summation returns zero, whereas adding and first and then returns one, assuming those operations are representable. The exact order-dependent behavior depends on the format and rounding mode. Here , which is the warning that the order may matter.
Worked example 1.2.6
(A perturbation that attains the sensitivity bound)
Take , so , and . With choose . The perturbed sum is , so and . Equality holds, so no smaller constant than works for this input.
Worked example 1.2.7
(No cancellation, and an exactly zero sum)
If all inputs are nonnegative and at least one is positive, then . For the relative bound is , although the actual rounded result can still depend on order. Pairwise summation forms a balanced tree and often reduces the number of additions on a path from to about ; a corresponding proof must account for the actual tree and rounding model.
For the edge case we have , so is undefined. Yet exactly, so the absolute bound holds with room to spare. The absolute bound stays meaningful; only the relative statement is lost.
Counterexample mode
Small relative input perturbations may cause a large error in the answer
Claim: if the inputs are known to relative accuracy , their sum is known to relative accuracy close to . Consider and . Their sum is , while the sum of magnitudes is approximately . Hence is about . Perturb only by the relative amount : . The sum becomes , a relative change of . Exact arithmetic on uncertain input data cannot recover digits that those data do not determine. The claim holds only when is of moderate size.
Common mistake
(Compensated summation does not repair uncertain data)
Compensated summation tracks part of the rounding lost in previous steps and can improve accuracy, but the bound proved above is for ordinary sequential addition. It is not a proof of a particular compensated algorithm's error bound. Nor does it remove the factor : if the inputs themselves are uncertain, no accumulation order restores the missing digits.
Practice and solutions
Quick check
(Under the stated model, give the absolute error bound for summing four represented values.)
Solution · Answer
The bound is , assuming .
Quick check
(Why is the relative condition number not defined when the exact sum is zero?)
Solution · Answer
Its denominator is . An absolute error bound remains meaningful, but division by zero does not define a relative error.