Skip to the content of the web site.

3.2 The Banach Fixed-point Theorem

Introduction Theory HOWTO Examples Questions Matlab Maple

Introduction

To determine when it is guaranteed that a sequence of iterates converges, the Banach fixed-point theorem (or contraction mapping theorem, as it is also called) gives sufficient conditions for convergence.

Background

References

Theory

A function is said to be a contraction mapping if |f(x) − f(y)| ≤ c|x − y| for some value of |c| < 1. The term contraction indicates that the function brings points closer together, or it contracts the distance between points. It can be shown that any contraction mapping must be continuous.

The Banach fixed-point theorem states that a contraction mapping f has exactly one fixed point and that fixed point may be found by starting with any point x0 and iterating the function f on that point.

The proof is straight-foward by showing that |xk + 1 − xk| ≤ ck|x1 − x0|.

Given a continuous real-valued function f:RR and a point x* such that |f(1)(x*)| < 1, then there is an interval [a, b] around the point x* such that for all initial points x0 within that interval, the iteration of x0 must converge to x*. The function f is a contraction mapping on [a, b].

HOWTO

If a point x* satisfies x* = f(x*) for some function f and given a an approximation x0 sufficiently close to x*, the sequence xk = f(xk − 1) will converge to x* if |f(1)(x*)| < 1.

Examples

1. The functions sin(x) and tan(x) both have fixed points at x = 0; however, in both cases the derivative at that point is 1 and therefore the Banach fixed-point theorem gives no information about whether or not a sequence of points will converge. In the first case, we have very slow convergence; while in the second, we have divergence. Starting with 0.5

  • sin: 0.5, 0.47942554, 0.46126956, 0.44508534, 0.43053491, 0.41735696, 0.40534570, 0.39433647, ...
  • tan: 0.5, 0.54630249, 0.60802930, 0.69598953, 0.83545573, 1.1054835, 1.9917015, -2.2338448, ...

2. The function f(x) = 3cos(x) has three fixed points near the values x = -2.9381004, -2.6631789, 1.1701210 The derivatives at these three points are approximately 1.3811148, 0.60627225, and -2.7623934, respectively, and therefore, regardless of the initial value (except, of course, the three fixed points), an iteration of this function will only converge to the central value.

Questions

1. What are the fixed points of f(x) = x2 and given an approximation close enough to these fixed points, will an interation converge? (0, 1; yes, no)

2. Approximate the fixed point of sin(x)/x. (.8767262154)

3. What are the fixed points of the function f(x) = 1 + 1/x and which are attractive? ( -0.6180339880, 1.618033988; not attractive, attractive)

Matlab

We may iterate a function as follows in Matlab:

x = 0.5;
for i=1:100
    x = 3*cos(x);
end
x

You may replace the 3*cos(x) with whatever function you wish to iterate.

Maple

We may iterate a function as follows in Maple:

f := x -> 3*cos(x);
x[0] := 0.5;
for i from 0 to 100 do
    x[i + 1] := f(x[i]);
end do;

You may replace the 3*cos(x) with whatever function you wish to iterate.