AITKEN’S Δ² three slow terms predict where the sequence is heading
A linearly-converging sequence crawls toward its limit by a nearly constant ratio each step. Aitken’s Δ² process reads that ratio off three consecutive terms and extrapolates straight to where they are heading — producing a new sequence that converges much faster, from the same slow data. It squeezes accuracy out of terms you already have, no extra function evaluations.
THE TECHNIQUE x - (dx)^2 / (d^2 x)
Take three terms of the slow x = 1 + 1/x sequence heading for φ — 1, 2, 1.5 — and apply x₀ − (Δx)²/(Δ²x). The accelerated value lands far closer to φ than the raw third term. Compare: live demo
HISTORY & CREDIT Alexander Aitken, 1926
“Acceleration always helps.” — no. Aitken’s Δ² assumes linear convergence with a single dominant ratio; on a sequence that already converges quadratically, or one with several competing modes, it can help little or even degrade the estimate. It is a targeted tool, not a universal speed-up. cited
1926 · Alexander Aitken — “On Bernoulli’s numerical solution of algebraic equations”: the Δ² extrapolation (Aitken, the famous mental calculator). 1955 · Daniel Shanks — generalises it to the Shanks transformation (higher-order sequence acceleration). kin · Steffensen’s method wraps Δ² around a fixed-point iteration (dart 172) to make it converge quadratically without a derivative.
The name Δ² is literal: Δx = x₁−x₀ is the first difference, Δ²x = x₂−2x₁+x₀ the second; the correction is the first difference squared over the second — a discrete curvature. Aitken 1926
RECOMMEND FOR I-13 the accelerated estimate, computed
Aitken’s extrapolation of three slow terms runs on the canonical compiler:
$ i13 run aitken.i13 # accelerate x=1+1/x sequence toward phi=1.618
x0 = 1 x1 = 2 x2 = 1.5 -- three raw terms (x2 error ~ 0.118)
aitken = 1.6666666666666665 -- x0 - (dx)^2/(d^2 x): far closer to phi
Recommend: Aitken’s Δ² is LIT and a free accuracy boost for I-13 — verified that from the three slow terms 1, 2, 1.5 of the φ iteration (raw error ~0.12) it extrapolates to 1.6667 (error ~0.05), by x₀ − (Δx)²/(Δ²x) in native f64. Wrapped around fixed-point iteration (172) it becomes Steffensen’s method — quadratic convergence with no derivative, ideal for a language whose derivatives are hand-coded. It costs three stored terms and one formula; the honest caveat is that it assumes linear convergence.