Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Fixed-point iteration rewrites as and then repeats . If the sequence settles down, its limit satisfies , which is a root of .

Convergence theorem

Let solve and let be continuously differentiable on an interval containing . If

then converges for any starting value . Each step shrinks the error by about a factor , so a smaller means faster convergence.

To get : take , or any upper bound of it that is still below 1.

Method

Steps:

  1. Find with
  2. Rewrite as (there are many choices of )
  3. Check on . If not, try another
  4. Iterate from any
  5. Stop when , with

Worked example

Solve to 2 decimal places (true roots 0.381966 and 2.618034).

Solution:

  • , , so take
  • choose , then on , so it converges
  • , so stop when
  • from : , , , ,
  • , so

If is used, the values grow (3, 3.333, 4.037, 5.766, ...) and the method diverges.

Choice of g matters

For :

  • has everywhere, so it converges
  • has near the root 0.6823, so convergence is not guaranteed

A faster scheme with a built-in choice of is the Newton-Raphson Method.