Banach fixed-point Theorem Explained with Worked Examples

If is a contraction on a complete metric space ( with ), then has exactly one fixed point , and the iteration converges to it from any start, with error .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Banach fixed-point theorem means

A contraction brings every pair of points closer by the factor . So the iterates form a Cauchy sequence, which converges because the space is complete, and the limit is a fixed point; uniqueness follows because two fixed points would be times as far apart as themselves. This is the theoretical basis of fixed-point iteration, and the convergence condition in fixed-point convergence is the case .

Example: has and fixed point 2. From : , and after 5 steps , with error , exactly the bound . For on , , so the iteration converges to , the root of ; the picture is in cobweb and staircase diagrams.

The theorem proves the existence and uniqueness of solutions of differential equations (Picard iteration) and of linear systems solved by Jacobi and Gauss–Seidel iterations. Faster methods such as Newton–Raphson have a contraction constant that tends to zero near the root; see quadratic convergence. Closed and bounded sets in finite dimensions are compact, as in the Heine–Borel theorem.

What is it used for?

A map that shrinks distances has exactly one fixed point, and repeated application finds it from any start.

How to use banach fixed-point theorem

  1. Show with on a closed set (for a function, ).
  2. Choose a start and iterate .
  3. The limit is the unique fixed point.
  4. Use to bound the error after steps.

Graph

The contraction cos x meets the line y = x at the fixed point 0.7391fixed point 0.739100.10.20.30.40.50.60.70.80.911.11.200.20.40.60.811.2The contraction cos x meets the line y = x at the fixed point 0.7391xyT(x) = cos xy = xGraph with x from 0 to 1.2 and y from 0 to 1.2. Shows the curve T(x) = cos x; the curve y = x; point fixed point 0.7391 at (0.7391, 0.7391).

Iterating cos starting anywhere in [0, 1] spirals in to the intersection.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: a linear contraction

For and , find the error bound after 5 steps and the actual error.

Worked example
Answer
0.06250.0625
  1. x₁
  2. Bound
  3. Actual

Example 2: cosine

For on , find the contraction constant.

Worked example
Answer
q=sin⁡1≈0.8415q=\sin1\approx0.8415
  1. T'

Example 3: the fixed point

Find the fixed point of .

Worked example
Answer
x∗=2x^{*}=2
  1. Solve

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

T(x) = x/3 + 2

k = 1/3, fixed point 3

x = x/3 + 2.

Iterates from 0

2, 2.6667

Approach 3.

Error bound n = 4

kⁿ/(1 − k) × |x₁ − x₀|

0.0370.

Steps for error < 0.001

⌈ln(0.001(1 − k)/|x₁ − x₀|)/ln k⌉

8.

Word problems

If d(Tx, Ty) ≤ q d(x, y) with q < 1 on a complete metric space, T has a unique fixed point x*, and d(xₙ, x*) ≤ qⁿ/(1 − q) d(x₁, x₀).

Fixed point

Solve x = x/3 + 2.

  1. (2/3)x = 2
  2. Check: ✓3

Second iterate

From x₀ = 0 find x₂ = T(T(0)).

  1. T(0) = 2
  2. T(2) = 2.6667
  3. Check: ✓2.6667

Error bound Higher

Find q⁴/(1 − q)·|x₁ − x₀| with q = 1/3.

  1. (1/81)/(2/3) × 2
  2. Check: ✓0.037

Steps needed Higher

Smallest n with error < 0.001.

  1. ln(0.000333)/ln(1/3)
  2. Check: 7.3 → 8 ✓8

Common mistakes

q ≥ 1

allowed ✗

need q < 1 ✓

Strict.

Incomplete space

any metric space ✗

complete required ✓

Else no fixed point.

Map outside the space

ignored ✗

T maps the space into itself ✓

Required.

Wrong bound

qⁿ|x₁ − x₀| ✗

divide by 1 − q ✓

Geometric tail.

Exam tips

  1. q < 1.
  2. Complete space.
  3. Unique fixed point.
  4. Error qⁿ/(1 − q).
  5. Any start works.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Fixed point of x/4 + 3 Foundation

4

2. x₁ from 0 for x/4 + 3 Foundation

3

3. Bound q = 0.5, n = 6, |x₁ − x₀| = 4 Foundation

0.125

4. Bound q = 0.1, n = 3, |x₁ − x₀| = 1 to 5 d.p. Higher

0.00111

5. Fixed point of x/2 + 5 Higher

10

6. n for q = 0.5, bound < 0.01 with |x₁ − x₀| = 1 Higher

8

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Banach fixed-point theorem
Contractions have a unique fixed point.
Contraction
d(Tx, Ty) ≤ q d(x, y).
Complete metric space
Cauchy sequences converge.
Fixed point
Tx* = x*.
A priori bound
Error before iterating.
Picard iteration
xₙ₊₁ = Txₙ.

Frequently asked questions

What is the Banach fixed-point theorem?

A contraction on a complete metric space has a unique fixed point.

How do I find it?

Iterate from any start.

What is the error bound?

d(xₙ, x*) ≤ qⁿ/(1 − q) d(x₁, x₀).

Where is it used?

Existence of ODE solutions.

Which page covers the contraction mapping theorem?

contraction mapping theorem.

Which page covers Riesz representation?

Riesz representation.

More in Analysis, algebra and topology and the formula sheets.