MATH/APPM 4650
Class notes, February 4
Convergence acceleration
Most of today's notes including all examples will be on the board, but here are the basic concepts.
Aitken's method
If a sequence xn is known to converge linearly, then its formula must look something like
xn ≈ p + q rn
for some C less than 1 in absolute value.
The graph looks like
or 
However we often don't care about q or r, just the limit p.
If we suspect a sequence is converging linearly, we can take any three known points xn, xn+1, xn+2 and solve for p, q, and r. (Three equations for three unknowns.)
Then the solution would be
χn = xn - (xn+1 - xn)^2 / (xn+2 - 2 xn+1 + xn)
However the sequence is almost never exactly decaying exponentially, so this formula will not be perfect. Hence we just get an approximation for every n which we hope will be better.
This formula is called Aitken's method.
- Aitken's formula is good to use if you already have a given sequence. If you are generating the terms yourself, it's probably better to use Steffensen's method (below).
- Observe that you have to subtract numbers that are probably close to each other, then divide by numbers that are probably small. Once your approximation starts getting good, Aitken's method is very susceptible to roundoff error.
- Observe again we try to write the formula in the form "our current guess plus a hopefully small correction" to minimize the effects of roundoff.
- Aitken's method will not necessarily make a linearly convergent sequence superlinear. It may just be linear with a smaller asymptotic error constant.
- If the sequence is not linearly convergent, Aitken's method may not help at all.
Steffensen's method
If you are actually generating the sequence yourself using xn+1 = g(xn) yourself, Aitken's method wastes some effort. You need to first generate all the values using the iteration, then also generate the new sequence χ using Aitken's formula for each n.
But if you think χn is a better approximation than xn, why not just use that to generate new values?
This is Steffensen's method.
- x = xn given.
- y = g(xn).
- z = g(y).
- xn+1 = x - (y - x)2/(z - 2y + x).
Observe that each iteration requires two function evaluations, which will slow us down a bit.
Steffensen's method is the same as replacing the iteration xn+1 = g(xn) with the iteration
xn+1 = h(xn), where h is the function
h(x) = x - [g(x) - x]2 / [g(g(x)) - 2 g(x) + x].
You can compute that h(p) = p, h'(p) = 0, and h''(p) = g'(p)g''(p)/(g'(p)-1).
So if the original sequence was linearly convergent, then the new sequence will be quadratically convergent.
If the original sequence was quadratically convergent, the new sequence will be cubically convergent.
Because Steffensen's method is so fast, and relies so heavily on cancelation from dividing by small numbers, it is very susceptible to roundoff error.
Generally there is a "sweet spot" in the number of iterations, where Steffensen's method gives a good answer and then starts to give bad answers due to roundoff error.
Loosely speaking, your computations should be in many more digits than the tolerance you need. (Three or four times as much or so.)