Aitken Delta-Squared Acceleration

Use three sequence values to eliminate a leading geometric error without knowing its ratio.

Aitken Delta-Squared Acceleration

Concept Overview

The Aitken delta-squared process is a sequence acceleration method. It transforms a slowly converging sequence into one that converges faster. It uses three consecutive terms of the sequence to extrapolate the limit, based on the assumption that the error decays roughly geometrically. This requires computing the first and second forward differences, but notably does not require prior knowledge of the geometric decay ratio.

Worked Example

Consider the sequence s_n = 2 + (0.5)ⁿ + (0.5) * (0.25)ⁿ. We want to apply the Aitken delta-squared acceleration to estimate its limit from the values at n=2, 3, and 4.

For n=2, s₂ = 2 + (0.5)² + 0.5 * (0.25)² = 2 + 0.25 + 0.03125 = 2.28125.
For n=3, s₃ = 2 + (0.5)³ + 0.5 * (0.25)³ = 2 + 0.125 + 0.0078125 = 2.1328125.
For n=4, s₄ = 2 + (0.5)⁴ + 0.5 * (0.25)⁴ = 2 + 0.0625 + 0.001953125 = 2.064453125.
The first differences are Δs₂ = s₃ - s₂ = -0.1484375 and Δs₃ = s₄ - s₃ = -0.068359375.
The second difference is Δ²s₂ = Δs₃ - Δs₂ = 0.080078125.
The Aitken estimate is s₂ - (Δs₂)² / Δ²s₂ = 2.28125 - (-0.1484375)² / 0.080078125 = 2.0060975609756095.

The accelerated estimate 2.00609... is much closer to the true limit (2.0) than the original value s₂ = 2.28125. The error dropped from ~0.28 to ~0.006.

Experiment

Observe how Aitken acceleration removes a pure geometric error term in the Aitken Delta-Squared Acceleration module:

Select the Single mode sequence and set the Ratio to 0.5. Notice that the green accelerated sequence instantly jumps to the exact limit (2.0) because the error is purely geometric.
Change the sequence to Two modes with the same ratio. The accelerated sequence is no longer exact but still converges to the limit faster than the original sequence.
Change the Ratio to -0.5. The original sequence oscillates around the limit, but the accelerated method still effectively damps this oscillation and converges faster.
Change the Ratio to 1. The denominator of the Aitken correction becomes zero, making the estimate unavailable, which demonstrates that the sequence must actually be converging (or diverging with q ≠ 1) for the method to apply safely.

Limitations

While effective for many sequences, Aitken delta-squared acceleration has several limitations:

Zero Denominator: If the sequence values become constant or have a linear trend (e.g. q = 1), the second difference Δ²s_n becomes zero, and the method requires dividing by zero. The implementation catches this and reports the estimate as unavailable instead of dividing by zero.
Numerical Instability: For arbitrary noisy sequences or when near convergence, the first and second differences involve subtracting nearly equal numbers (near-cancellation). This can magnify floating-point errors, making the accelerated sequence wildly unstable.
Not Unconditional: The acceleration assumes the error terms behave geometrically. If the error terms decay logarithmically (e.g., 1/n), the method may not accelerate convergence at all and could even slow it down.

References

Detailed mathematical foundation and analysis of Aitken's Δ²-process can be found in the NIST Digital Library of Mathematical Functions, Section 3.9.

Aitken Delta-Squared Acceleration