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:
- Find with
- Rewrite as (there are many choices of )
- Check on . If not, try another
- Iterate from any
- 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.