Overview

fixed-point iteration


Show Summary Details

Quick Reference

To find a root of an equation f(x)=0 by the method of fixed-point iteration, the equation is first rewritten in the form x=g(x). Starting with an initial approximation x0 to the root, the values x1, x2, x3,…are calculated using xn+1=g(xn). The method is said to converge if these values tend to a limit α. If they do, then α=g(α) and so α is a root of the original equation.

A root of x=g(x) occurs where the graph y=g(x) meets the line y=x. It can be shown that, if |g′(x)| < 1 in an interval containing both the root and the value x0, the method will converge, but not if |g′(x)|>1. This can be illustrated in figures such as those shown which are for cases in which g′(x) is positive. For example, the equation x3x−1=0 has a root between 1 and 2, so take x0=1.5. The equation can be written in the form x=g(x) in several ways, such as (i) x=x3−1 or (ii) x=(x+1)1/3. In case (i), g′(x)=3x2, which does not satisfy |g′(x)| < 1 near x0. In case (ii), g′(x)=⅓(x+1)−2/3 and g′(1.5) ≈ 0.2, so it is likely that with this formulation the method converges.

Subjects: Mathematics.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.