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 *x*_{0} and iterating the function f on that point.

The proof is straight-foward by showing that
|x_{k + 1} − x_{k}| ≤ *c*^{k}|x_{1} − x_{0}|.

Given a continuous real-valued function f:**R**→**R** 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 *x*_{0} within that interval,
the iteration of *x*_{0} 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 *x*_{0} sufficiently close
to *x*^{*}, the sequence *x*_{k} = f(*x*_{k − 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*) = *x*^{2} 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.