Back to the on-screen lesson ·
Aitken's method as a model fitted to three terms, the superlinear convergence it buys for a linear sequence, and the same argument carried to step sizes as Richardson extrapolation.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive and apply Aitken's formula, say what it assumes and what follows when the assumption fails, name the sequences it cannot help, and recognise Richardson extrapolation as the same argument in a step size.
You know what linear convergence is: the error multiplied by a constant factor every step. That constant is the thing this lesson exploits — it can be measured from the sequence itself, and once it is known the limit can be guessed at rather than waited for.
The forward difference is $\Delta x_n = x_{n+1} - x_n$ and the second difference is $\Delta^{2}x_n = x_{n+2} - 2x_{n+1} + x_n$. Extrapolation means fitting an assumed shape to computed values and reading off the value the shape predicts in the limit. Aitken's $\Delta^{2}$ method does that for a sequence; Richardson extrapolation does it for a family indexed by a step size; Steffensen's method applies Aitken inside a fixed-point iteration.
Suppose the errors shrink by a constant factor: $x_{n+1} - L = \rho(x_n - L)$. That is two unknowns, $L$ and $\rho$, and three consecutive terms give two equations. Dividing one by the other eliminates $L$ and leaves $\rho$ as a ratio of gaps — measurable, because a difference of terms cancels the limit. Substituting back gives Aitken's formula
$$\hat{x} = x_n - \frac{(\Delta x_n)^{2}}{\Delta^{2}x_n}.$$
On a sequence that satisfies the assumption exactly it returns $L$ exactly, from three terms; on a linearly convergent sequence it returns a value whose error is $o(|e_n|)$, so the accelerated sequence converges superlinearly. Everything the method promises comes from the assumption, and so does everything that goes wrong with it. A quadratically convergent sequence has no constant ratio — the ratio tends to zero — so there is nothing to remove and nothing is gained. A sequence whose ratio wanders can drive $\Delta^{2}x_n$ near zero, and dividing by it produces a value worse than any term it used. Richardson extrapolation is the same argument with the shape $A(h) = A + ch^{p}$ in place of a constant ratio: evaluate at $h$ and $h/2$, eliminate $c$, and get $\dfrac{2^{p}A(h/2) - A(h)}{2^{p} - 1}$, one order better for the cost of some arithmetic.
Another way: steps
Another way: example
$x_0 = 1$, $x_1 = 0.5$, $x_2 = 0.25$: $\Delta x_0 = -0.5$, $\Delta^{2}x_0 = 0.25$, so $\hat{x} = 1 - \dfrac{0.25}{0.25} = 0$. The sequence is exactly geometric with limit $0$, and three terms found it.
Acceleration is treated as a free improvement to be applied to anything. It is not free and it is not universal: it is the fitting of a model, and a model fitted to data that does not have its shape gives an answer with no standing at all. The failure is quiet — the accelerated value looks like a number of the right size — so the discipline is to apply the formula repeatedly and watch whether the accelerated sequence settles. If it does not, the assumption was wrong, and the plain sequence was the better of the two.
$g(x) = \cos x$ from $x_0 = 1$ gives $0.5403$, $0.8576$, $0.6543$ — linear with $|\rho| \approx 0.67$.
Oscillating and slow.
Aitken on those three: about $0.7314$, against the fixed point $0.7391$.
Closer than any of the three.
Feeding the accelerated values back into $g$ is Steffensen's method, which converges quadratically without a derivative.
The idea used twice.
Newton's errors $10^{-1}, 10^{-2}, 10^{-4}$: the ratios are $0.1$ then $0.01$.
No constant ratio.
Aitken fits a model with a fixed $\rho$ to data that has none, and its output is no better than $x_2$ already was.
The assumption is simply false.
$\Delta x_0 = -2$ and $\Delta^{2}x_0 = 1 - 4 + 4 = 1$.
$\hat{x} = 4 - \dfrac{4}{1} = 0$.
Exactly right: the sequence is $4 \times 2^{-n}$, geometric with limit $0$, and the assumption held perfectly.
A sequence converges linearly with ratio $\dfrac{1}{2}$: each error is $\dfrac{1}{2}$ of the one before. By what factor is the gap $x_{n+1} - x_n$ larger than the gap $x_{n+2} - x_{n+1}$?
Answer:
A sequence begins $x_0 = 8$, $x_1 = \frac{29}{4}$, $x_2 = \frac{113}{16}$. Give the first difference $x_1 - x_0$, the second difference $x_2 - 2x_1 + x_0$, and the value Aitken's formula $x_0 - \dfrac{(x_1 - x_0)^{2}}{x_2 - 2x_1 + x_0}$ returns. Give fractions where the values are not whole.
| Quantity | Value | |
|---|---|---|
| First difference | $x_1 - x_0$ | |
| Second difference | $x_2 - 2x_1 + x_0$ | |
| What Aitken's formula returns | the extrapolated value |
Put the five steps of deriving Aitken's formula into the order they depend on each other.
Number the steps in order (write the number in the box):
Match each sequence to what Aitken's method does to it.
| Converges superlinearly afterwards: the intended gain | Returns the limit exactly, from three terms | Gains essentially nothing: there is no constant ratio to remove | Can return a value worse than the terms it used | |
|---|---|---|---|---|
| A linearly convergent sequence | ||||
| The limit plus an exactly geometric error | ||||
| A quadratically convergent sequence | ||||
| A sequence whose ratio of errors wanders |
An approximation satisfies $A(h) = A + ch^{3} + \cdots$. Two values are known: $A(h) = 3$ and $A(h/2) = 9$. What does one Richardson extrapolation give? Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Select every statement that is true of Aitken's method.
This task has no paper form; do it on a device.
You can derive and apply Aitken's method and state its assumption. Say in your own words why it gains nothing on a quadratically convergent sequence.
8. Your turn: Aitken on $x_0 = 4$, $x_1 = 2$, $x_2 = 1$, step 3