Aitken Acceleration

Fixed-point iteration with $0 < \lambda < 1$ (linear convergence) can be painfully slow when $\lambda$ is close to 1. Aitken acceleration is a technique that uses three consecutive iterates to construct a much better estimate of the root, dramatically reducing the number of steps needed. It does not change the underlying iteration; it simply extrapolates from the pattern of convergence.

---

The Acceleration Formula

Given three consecutive iterates $x_k$, $x_{k+1}$, $x_{k+2}$ from a fixed-point iteration, the Aitken accelerated estimate is:

$\hat{x}_{k+2} = x_k - \frac{(x_{k+1} - x_k)^2}{x_{k+2} - 2x_{k+1} + x_k}$

The denominator $x_{k+2} - 2x_{k+1} + x_k$ is the second finite difference of the sequence, measuring the curvature of the convergence path. When the sequence is converging linearly at rate $\lambda$, this formula extrapolates exactly to the fixed point.

Note

Aitken acceleration is typically applied every two steps. Starting from $x_0$, compute $x_1$ and $x_2$ with the standard iteration, then form $\hat{x}_2$. Use $\hat{x}_2$ as the new starting point, compute $x_3 = g(\hat{x}_2)$ and $x_4$, then form $\hat{x}_4$, and so on. Each accelerated estimate leaps far ahead of where the plain iteration would have reached.

---

Worked Example

Problem: Let $g(x) = x + \dfrac{1}{16}\left(\dfrac{1}{x} - 0.5\right)$ with $x_0 = 1.5$. Apply one round of Aitken acceleration.

Step 1 — Compute two standard iterates

$x_1 = g(x_0) = g(1.5) = 1.5 + \frac{1}{16}\!\left(\frac{1}{1.5} - 0.5\right) = 1.5 + \frac{1}{16}(0.6\overline{6} - 0.5) = 1.5 + 0.010417 = 1.510417$

$x_2 = g(x_1) = g(1.510417) = 1.510417 + \frac{1}{16}\!\left(\frac{1}{1.510417} - 0.5\right) \approx 1.520546$

Step 2 — Apply the Aitken formula

$\hat{x}_2 = x_0 - \frac{(x_1 - x_0)^2}{x_2 - 2x_1 + x_0}$

$= 1.5 - \frac{(1.510417 - 1.5)^2}{1.520546 - 2(1.510417) + 1.5}$

$= 1.5 - \frac{(0.010417)^2}{1.520546 - 3.020834 + 1.5}$

$= 1.5 - \frac{0.000108514}{-0.000288}$

$\approx 1.5 + 0.377604 = \boxed{1.877604}$

Step 3 — Continue from the accelerated value

The plain iteration from $x_0 = 1.5$ would require many more steps to reach this neighbourhood. Instead, treat $\hat{x}_2 = 1.877604$ as the new starting point:

$x_3 = g(\hat{x}_2) \approx 1.879641$

Then compute $x_4 = g(x_3)$ and apply the formula again to produce $\hat{x}_4$, which will be even closer to the true root $x^* = 2$.

Note

The plain iteration with this $g(x)$ has $\lambda$ close to 1 (very slow linear convergence). Each Aitken step skips the equivalent of many plain iterations, making the overall computation far more efficient even though the formula requires three evaluations per acceleration step.