Fixed-point Convergence Explained with Worked Examples

The iteration converges to a fixed point (started close enough) if , and diverges if . The error is multiplied by about at each step.

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 Fixed-point convergence means

For , the fixed point is and : the iteration converges, with errors alternating in sign and shrinking by a factor of 0.67 per step. For , and the error halves (the contraction mapping theorem). For , the fixed point is 1 but , so any other start moves away from it.

By the mean value theorem, (the mean value theorem), which gives the rule. If the convergence is faster than linear: this is what happens in Newton's method, , where at a simple root (Newton's quadratic convergence, Newton–Raphson).

Staircase and cobweb diagrams show the behaviour graphically (cobweb and staircase diagrams). The method is described in fixed-point iteration, and the global theory in Banach's fixed point theorem. Derivatives of trigonometric functions are in the derivative of sine.

What is it used for?

A fixed-point iteration converges when the slope of the iteration function at the fixed point is less than 1 in size.

How to use fixed-point convergence

  1. Find the fixed point (solve ).
  2. Compute .
  3. If , the iteration converges locally at a rate .
  4. If , it diverges.

Graph

g(x) = cos x crosses y = x at 0.739 with slope −0.67fixed point 0.739100.20.40.60.811.21.400.20.40.60.81g(x) = cos x crosses y = x at 0.739 with slope −0.67xyg(x) = cos xy = xGraph with x from 0 to 1.5 and y from 0 to 1.1. Shows the curve g(x) = cos x; the curve y = x; point fixed point 0.7391 at (0.7391, 0.7391).

Iterates spiral in to the crossing point.

Worked examples

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

Example 1: g = cos x

Find at .

Worked example
Answer
−0.6736-0.6736
  1. Formula

Example 2: g = x/2 + 1

Find .

Worked example
Answer
0.50.5
  1. Formula

Example 3: g = 2x − 1

Find at the fixed point 1.

Worked example
Answer
2 (diverges)2\ (\text{diverges})
  1. Formula

Special cases

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

g = cos x from 1

x₁ = 0.5403, x₂ = 0.8576

Cobweb spiral.

Rate

|g′(x*)| = sin(0.739085) ≈ 0.6736

Linear convergence factor.

Fixed point

x* ≈ 0.739085

Solves cos x = x.

Convergence test

converges if |g′(x*)| < 1

Otherwise diverges.

Word problems

Fixed-point iteration xₙ₊₁ = g(xₙ) converges to a fixed point x* when |g′(x*)| < 1. The error shrinks by about |g′(x*)| each step (linear convergence).

Two iterations

Iterate g = cos x from x₀ = 1. Find x₂ to 4 decimal places.

  1. x₁cos 1 = 0.5403
  2. x₂cos 0.5403
  3. Check: 0.8576 ✓0.8576.

Third iteration

Find x₃.

  1. x₃cos 0.8576
  2. Check: 0.6543 ✓0.6543.

Rate Higher

Find the convergence factor |g′(x*)| at x* = 0.739085.

  1. g′ = −sin xsin 0.739085
  2. Check: 0.6736 ✓0.6736.

Divergence Higher

g(x) = 2x has fixed point 0. Is it attracting?

  1. |g′|2 > 1
  2. Check: not attracting ✓It diverges.

Common mistakes

Using |g| instead of |g′|

check |g(x*)| < 1 ✗

check |g′(x*)| < 1 ✓

The derivative controls the rate.

Stopping after one step

x₁ is the answer ✗

iterate until stable ✓

Check successive values.

Wrong rearrangement

any rearrangement converges ✗

some diverge ✓

Test |g′| < 1.

Degrees

cos in degrees ✗

radians ✓

Use radians.

Exam tips

  1. |g′(x*)| < 1.
  2. Linear convergence.
  3. Radians.
  4. Try another rearrangement.
  5. Cobweb diagrams help.

Practice questions

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

1. cos(0.5) to 4 d.p. Foundation

0.8776

2. cos(0.8776) to 4 d.p. Foundation

0.6390

3. sin(0.739085) to 4 d.p. Foundation

0.6736

4. |g′| for g = x/2 Higher

0.5

5. |g′| for g = 3x Higher

3

6. 0.6736² to 4 d.p. (error after two steps ratio) Higher

0.4537

Practice generator

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

Solve: …

Key terms

Fixed point
x with g(x) = x.
Iteration
Repeated application of g.
Attracting
Nearby points move closer.
Convergence factor
Cobweb diagram
Picture of the iteration.
Rearrangement
Rewriting f(x) = 0 as x = g(x).

Frequently asked questions

When does fixed-point iteration converge?

When |g′| < 1 near the fixed point.

How fast?

Linearly, with factor |g′(x*)|.

What is the fixed point of cos x?

About 0.739085.

What if |g′| > 1?

The iteration diverges.

Which page covers Newton’s method?

Newton’s method.

Which page covers cobweb diagrams?

cobweb and staircase diagrams.

More in Numerical methods and optimisation and the formula sheets.