Mathematics 371 -- Numerical Analysis

September 26, 2001

An Aitken acceleration example.

The equation has a root of multiplicity

at (why?). If we use Newton-Raphson

iteration, by our results from class on Monday, we

get a linearly convergent sequence of approximations

to the root. Note the slow convergence:

> f:=x->exp(x)-x-1;

> x[0]:=1.0;

> for i to 10 do x[i]:=x[i-1]-f(x[i-1])/D(f)(x[i-1]); lprint(x[i]); end do:

.5819767070

.3190550411

.1679961724

.8634887054e-1

.4379570665e-1

.2205768918e-1

.1106936258e-1

.5544899275e-2

.2774905348e-2

.1387955274e-2

After 10 iterations, the error is still about . If we take this sequence

and compute the Aitken-accelerated sequence:

then the result is a sequence converging significantly faster to .

> for i from 0 to 8 do xhat[i]:=x[i] - (x[i+1]-x[i])^2/(x[i+2]-2*x[i+1]+x[i]); lprint(xhat[i]); end do:

-.126638558

-.359928426e-1

-.96910579e-2

-.25225356e-2

-.64411622e-3

-.16289730e-3

-.4083614e-4

-.1070063e-4

-.2912054e-5

Note that is the last term in the Aitken sequence that we can

construct from the information computed above -- would

require knowledge of .