1.9.5 Failure of iterative methods (A-level only)

What you'll learn

How fixed-point iteration can diverge, oscillate or enter a repeating cycle.
How the derivative of an iteration function helps predict convergence or failure.
Why Newton–Raphson may fail or approach an unintended root.
How to demonstrate failure using calculations and graphical arguments.

Recap: fixed-point iteration

To solve an equation numerically, you can sometimes rearrange it into the form

x = g (x) .

Starting with an initial estimate $x_0$ , you repeatedly apply the iteration formula

x_{n+1}=g(x_n).

This produces a sequence $x0,x1,x2,…x_0,x_1,x_2,\ldots$ . If the sequence approaches a finite value $α\alpha$ , then taking limits gives

α=g(α).\alpha=g(\alpha).

Therefore, $α\alpha$ is a solution of the rearranged equation.

Definition

Fixed point

A fixed point of $g$ is a value $α\alpha$ satisfying $g(α)=αg(\alpha)=\alpha$ . On a graph, it is an intersection of the curves $y = g (x)$ and $y = x$ .

Key Idea

A solution is not a guarantee of convergence

Even if $x = g (x)$ has a fixed point, the iteration $x_{n+1}=g(x_n)$ does not necessarily approach it. Success depends on the rearrangement, the initial estimate and the behaviour of $g$ nearby.

Showing iteration graphically

A cobweb diagram shows successive iterations on the same axes as $y = g (x)$ and $y = x$ .

Starting from $x_0$ on the horizontal axis:

Move vertically to the curve $y = g (x)$ , reaching the height $g(x_0)=x_1$ .
Move horizontally to the line $y = x$ , transferring that height back to the horizontal coordinate $x_1$ .
Repeat the vertical and horizontal movements.

If the steps close in on an intersection, the iteration converges. If they move away or repeat without closing in, the method fails.

Cobweb diagrams comparing convergence, oscillating divergence and a repeating two-cycle

Why the derivative matters

Near a fixed point $α\alpha$ , the gradient of $y = g (x)$ controls how errors change.

Suppose the current approximation is close to $α\alpha$ , with error

en=xn−α.e_n=x_n-\alpha.

Using the local gradient of $g$ , the next error is approximately

en+1≈g′(α)en.e_{n+1}\approx g'(\alpha)e_n.

So the magnitude of the error is approximately multiplied by $∣g′(α)∣\lvert g'(\alpha)\rvert$ at each iteration.

If $∣g′(α)∣<1\lvert g'(\alpha)\rvert<1$ , errors become smaller, so iteration normally converges when the initial value is sufficiently close.
If $∣g′(α)∣>1\lvert g'(\alpha)\rvert>1$ , errors become larger, so iteration normally diverges.
If $∣g′(α)∣=1\lvert g'(\alpha)\rvert=1$ , this test is inconclusive. You must investigate the sequence or use another argument.

Definition

Convergence and divergence

An iteration converges if its terms approach a finite limit. It diverges if the terms do not approach a finite limit.

Tip

Positive and negative gradients

When $0<g′(α)<10<g'(\alpha)<1$ , terms usually approach from one side. When $−1<g′(α)<0-1<g'(\alpha)<0$ , they usually alternate across the fixed point while moving closer.

Example

Predicting failure from the derivative

Consider the iteration

x_{n+1}=2x_n-1.

Find the fixed point by solving $α=2α−1\alpha=2\alpha-1$ , giving $α=1\alpha=1$ .
Here $g (x) = 2 x - 1$ , so $g^{'} (x) = 2$ and therefore $∣g′(1)∣=2>1\lvert g'(1)\rvert=2>1$ .
Starting with $x_0=1.1$ gives
$x1=1.2,x2=1.4,x3=1.8,x4=2.6.x_1=1.2,\qquad x_2=1.4,\qquad x_3=1.8,\qquad x_4=2.6.$
The terms move progressively farther from 1, confirming divergence.

Common Mistake

Checking the derivative at the wrong place

For local convergence, evaluate $g^{'} (x)$ at or near the fixed point, not automatically at the initial value. A condition holding at one unrelated point does not determine the whole sequence.

Ways fixed-point iteration can fail

Divergence without oscillation

If the gradient near the fixed point is positive and greater than 1, successive terms may remain on the same side of the fixed point while moving farther away.

The terms might grow without bound, but divergence does not have to mean “tends to infinity”. It simply means that there is no finite limit.

Oscillating divergence

If $g′(α)<−1g'(\alpha)<-1$ , the negative gradient tends to move successive values to opposite sides of the fixed point. Because its magnitude exceeds 1, the distance from the fixed point increases.

Example

Showing oscillating divergence

Consider $x_{n+1}=3-2x_n$ with $x_0=1.1$ .

The fixed point satisfies $α=3−2α\alpha=3-2\alpha$ , so $α=1\alpha=1$ .
Since $g^{'} (x) = - 2$ , the negative sign predicts alternation and $∣g′(1)∣=2>1\lvert g'(1)\rvert=2>1$ predicts increasing errors.
Iterating gives
$x1=0.8,x2=1.4,x3=0.2,x4=2.6.x_1=0.8,\qquad x_2=1.4,\qquad x_3=0.2,\qquad x_4=2.6.$
The terms alternate below and above 1, while their distances from 1 increase. The iteration therefore fails by oscillating divergence.

A repeating cycle

An iteration can repeat a set of values instead of approaching a fixed point. A two-cycle occurs when two distinct values $a$ and $b$ satisfy

\quad\text{and}\quad g(b)=a.

Example

Identifying a two-cycle

Use $x_{n+1}=2-x_n$ with $x_0=0.6$ .

Calculate $x_1=2-0.6=1.4$ .
Calculate $x_2=2-1.4=0.6$ , returning to the initial value.
The sequence is
$1.4,…0.6,\ 1.4,\ 0.6,\ 1.4,\ldots$
It never approaches the fixed point 1, so it is a two-cycle. Here $g^{'} (x) = - 1$ , illustrating why the derivative test is inconclusive when its magnitude equals 1.

Leaving the permitted domain

An iteration may produce a value for which the next calculation is undefined. This can happen with square roots, logarithms or division by an expression that becomes zero.

For example, in $xn+1=2−xnx_{n+1}=\sqrt{2-x_n}$ , every input must satisfy $xn≤2x_n\leq2$ . Starting with $x_0=3$ immediately requires $−1\sqrt{-1}$ , which has no real value.

Common Mistake

Rearrangements can change the usable domain

Different rearrangements of the same equation can impose different restrictions or lead to different convergence behaviour. Always check that each generated value lies in the domain of $g$ .

Failure of Newton–Raphson iteration

For an equation $f (x) = 0$ , Newton–Raphson uses

xn+1=xn−f(xn)f′(xn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

Geometrically, $x_{n+1}$ is the point where the tangent to $y = f (x)$ at $x_n$ crosses the horizontal axis.

Newton–Raphson can fail when:

$f'(x_n)=0$ , because the formula would involve division by zero.
$f'(x_n)$ is very small, producing a very large jump.
The iterates enter a repeating cycle.
The starting value sends the sequence away from the required root.
Several roots exist and the method converges to a different one.

Example

Newton–Raphson breaking at a stationary point

Let $f(x)=x^3-1$ and choose $x_0=0$ .

Differentiate to obtain $f'(x)=3x^2$ .
At the initial value, $f (0) = - 1$ but $f^{'} (0) = 0$ .
The first Newton–Raphson calculation would be
$x1=0−−10,x_1=0-\frac{-1}{0},$
which is undefined. The method cannot proceed from this starting value, even though the equation has the root $x = 1$ .

Common Mistake

Assuming repeated decimals prove convergence

A calculator display may show several identical rounded values even when the exact sequence has not converged. State numerical evidence alongside a derivative condition, an error comparison or a clear graphical argument where possible.

Choosing a response when iteration fails

Failure of one method or rearrangement does not mean the equation has no solution. You may be able to:

choose a different starting value;
rearrange the equation to obtain a different $g (x)$ ;
use Newton–Raphson instead of fixed-point iteration, or vice versa;
use a sign-change method on an interval where the function is continuous.

The important mathematical point is to justify what happens, using successive values, gradients, domain restrictions or a graph.

Exam technique

In the exam

Write down several successive iterates accurately and look for movement towards a limit, growth, alternation or repetition.
For $x_{n+1}=g(x_n)$ , find the relevant fixed point and check $∣g′(α)∣\lvert g'(\alpha)\rvert$ ; explain what the result predicts.
For Newton–Raphson, check for zero or very small derivatives and state clearly whether the method is undefined, divergent, cyclic or approaching the wrong root.
Do not merely write “it fails”: provide numerical or graphical evidence and name the type of failure.

Self review

Check yourself

Why does $∣g′(α)∣>1\lvert g'(\alpha)\rvert>1$ usually make a fixed point locally repelling?
How can you recognise a two-cycle from a list of iterates?
Give two reasons why Newton–Raphson might fail even though a real root exists.

What you'll learn

How fixed-point iteration can diverge, oscillate or enter a repeating cycle.
How the derivative of an iteration function helps predict convergence or failure.
Why Newton–Raphson may fail or approach an unintended root.
How to demonstrate failure using calculations and graphical arguments.

Recap: fixed-point iteration

To solve an equation numerically, you can sometimes rearrange it into the form

x = g (x) .

Starting with an initial estimate $x_0$ , you repeatedly apply the iteration formula

x_{n+1}=g(x_n).

This produces a sequence $x0,x1,x2,…x_0,x_1,x_2,\ldots$ . If the sequence approaches a finite value $α\alpha$ , then taking limits gives

α=g(α).\alpha=g(\alpha).

Therefore, $α\alpha$ is a solution of the rearranged equation.

Definition

Fixed point

A fixed point of $g$ is a value $α\alpha$ satisfying $g(α)=αg(\alpha)=\alpha$ . On a graph, it is an intersection of the curves $y = g (x)$ and $y = x$ .

Key Idea

A solution is not a guarantee of convergence

Even if $x = g (x)$ has a fixed point, the iteration $x_{n+1}=g(x_n)$ does not necessarily approach it. Success depends on the rearrangement, the initial estimate and the behaviour of $g$ nearby.

Showing iteration graphically

A cobweb diagram shows successive iterations on the same axes as $y = g (x)$ and $y = x$ .

Starting from $x_0$ on the horizontal axis:

Move vertically to the curve $y = g (x)$ , reaching the height $g(x_0)=x_1$ .
Move horizontally to the line $y = x$ , transferring that height back to the horizontal coordinate $x_1$ .
Repeat the vertical and horizontal movements.

If the steps close in on an intersection, the iteration converges. If they move away or repeat without closing in, the method fails.

Cobweb diagrams comparing convergence, oscillating divergence and a repeating two-cycle

Why the derivative matters

Near a fixed point $α\alpha$ , the gradient of $y = g (x)$ controls how errors change.

Suppose the current approximation is close to $α\alpha$ , with error

en=xn−α.e_n=x_n-\alpha.

Using the local gradient of $g$ , the next error is approximately

en+1≈g′(α)en.e_{n+1}\approx g'(\alpha)e_n.

So the magnitude of the error is approximately multiplied by $∣g′(α)∣\lvert g'(\alpha)\rvert$ at each iteration.

If $∣g′(α)∣<1\lvert g'(\alpha)\rvert<1$ , errors become smaller, so iteration normally converges when the initial value is sufficiently close.
If $∣g′(α)∣>1\lvert g'(\alpha)\rvert>1$ , errors become larger, so iteration normally diverges.
If $∣g′(α)∣=1\lvert g'(\alpha)\rvert=1$ , this test is inconclusive. You must investigate the sequence or use another argument.

Definition

Convergence and divergence

An iteration converges if its terms approach a finite limit. It diverges if the terms do not approach a finite limit.

Tip

Positive and negative gradients

When $0<g′(α)<10<g'(\alpha)<1$ , terms usually approach from one side. When $−1<g′(α)<0-1<g'(\alpha)<0$ , they usually alternate across the fixed point while moving closer.

Example

Predicting failure from the derivative

Consider the iteration

x_{n+1}=2x_n-1.

Find the fixed point by solving $α=2α−1\alpha=2\alpha-1$ , giving $α=1\alpha=1$ .
Here $g (x) = 2 x - 1$ , so $g^{'} (x) = 2$ and therefore $∣g′(1)∣=2>1\lvert g'(1)\rvert=2>1$ .
Starting with $x_0=1.1$ gives
$x1=1.2,x2=1.4,x3=1.8,x4=2.6.x_1=1.2,\qquad x_2=1.4,\qquad x_3=1.8,\qquad x_4=2.6.$
The terms move progressively farther from 1, confirming divergence.

Common Mistake

Checking the derivative at the wrong place

For local convergence, evaluate $g^{'} (x)$ at or near the fixed point, not automatically at the initial value. A condition holding at one unrelated point does not determine the whole sequence.

Ways fixed-point iteration can fail

Divergence without oscillation

If the gradient near the fixed point is positive and greater than 1, successive terms may remain on the same side of the fixed point while moving farther away.

The terms might grow without bound, but divergence does not have to mean “tends to infinity”. It simply means that there is no finite limit.

Oscillating divergence

Example

Showing oscillating divergence

Consider $x_{n+1}=3-2x_n$ with $x_0=1.1$ .

The fixed point satisfies $α=3−2α\alpha=3-2\alpha$ , so $α=1\alpha=1$ .
Since $g^{'} (x) = - 2$ , the negative sign predicts alternation and $∣g′(1)∣=2>1\lvert g'(1)\rvert=2>1$ predicts increasing errors.
Iterating gives
$x1=0.8,x2=1.4,x3=0.2,x4=2.6.x_1=0.8,\qquad x_2=1.4,\qquad x_3=0.2,\qquad x_4=2.6.$
The terms alternate below and above 1, while their distances from 1 increase. The iteration therefore fails by oscillating divergence.

A repeating cycle

An iteration can repeat a set of values instead of approaching a fixed point. A two-cycle occurs when two distinct values $a$ and $b$ satisfy

\quad\text{and}\quad g(b)=a.

Example

Identifying a two-cycle

Use $x_{n+1}=2-x_n$ with $x_0=0.6$ .

Calculate $x_1=2-0.6=1.4$ .
Calculate $x_2=2-1.4=0.6$ , returning to the initial value.
The sequence is
$1.4,…0.6,\ 1.4,\ 0.6,\ 1.4,\ldots$
It never approaches the fixed point 1, so it is a two-cycle. Here $g^{'} (x) = - 1$ , illustrating why the derivative test is inconclusive when its magnitude equals 1.

Leaving the permitted domain

An iteration may produce a value for which the next calculation is undefined. This can happen with square roots, logarithms or division by an expression that becomes zero.

For example, in $xn+1=2−xnx_{n+1}=\sqrt{2-x_n}$ , every input must satisfy $xn≤2x_n\leq2$ . Starting with $x_0=3$ immediately requires $−1\sqrt{-1}$ , which has no real value.

Common Mistake

Rearrangements can change the usable domain

Different rearrangements of the same equation can impose different restrictions or lead to different convergence behaviour. Always check that each generated value lies in the domain of $g$ .

Failure of Newton–Raphson iteration

For an equation $f (x) = 0$ , Newton–Raphson uses

xn+1=xn−f(xn)f′(xn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

Geometrically, $x_{n+1}$ is the point where the tangent to $y = f (x)$ at $x_n$ crosses the horizontal axis.

Newton–Raphson can fail when:

$f'(x_n)=0$ , because the formula would involve division by zero.
$f'(x_n)$ is very small, producing a very large jump.
The iterates enter a repeating cycle.
The starting value sends the sequence away from the required root.
Several roots exist and the method converges to a different one.

Example

Newton–Raphson breaking at a stationary point

Let $f(x)=x^3-1$ and choose $x_0=0$ .

Differentiate to obtain $f'(x)=3x^2$ .
At the initial value, $f (0) = - 1$ but $f^{'} (0) = 0$ .
The first Newton–Raphson calculation would be
$x1=0−−10,x_1=0-\frac{-1}{0},$
which is undefined. The method cannot proceed from this starting value, even though the equation has the root $x = 1$ .

Common Mistake

Assuming repeated decimals prove convergence

Choosing a response when iteration fails

Failure of one method or rearrangement does not mean the equation has no solution. You may be able to:

choose a different starting value;
rearrange the equation to obtain a different $g (x)$ ;
use Newton–Raphson instead of fixed-point iteration, or vice versa;
use a sign-change method on an interval where the function is continuous.

The important mathematical point is to justify what happens, using successive values, gradients, domain restrictions or a graph.

Exam technique

In the exam

Write down several successive iterates accurately and look for movement towards a limit, growth, alternation or repetition.
For $x_{n+1}=g(x_n)$ , find the relevant fixed point and check $∣g′(α)∣\lvert g'(\alpha)\rvert$ ; explain what the result predicts.
For Newton–Raphson, check for zero or very small derivatives and state clearly whether the method is undefined, divergent, cyclic or approaching the wrong root.
Do not merely write “it fails”: provide numerical or graphical evidence and name the type of failure.

Self review

Check yourself

Why does $∣g′(α)∣>1\lvert g'(\alpha)\rvert>1$ usually make a fixed point locally repelling?
How can you recognise a two-cycle from a list of iterates?
Give two reasons why Newton–Raphson might fail even though a real root exists.

What you'll learn

Recap: fixed-point iteration

Showing iteration graphically

Why the derivative matters

Ways fixed-point iteration can fail

Divergence without oscillation

Oscillating divergence

A repeating cycle

Leaving the permitted domain

Failure of Newton–Raphson iteration

Choosing a response when iteration fails

Review 1.9.5 Failure of iterative methods (A-level only) by teaching Genie

1.9.5 Failure of iterative methods (A-level only)

What you'll learn

Recap: fixed-point iteration

Showing iteration graphically

Why the derivative matters

Ways fixed-point iteration can fail

Divergence without oscillation

Oscillating divergence

A repeating cycle

Leaving the permitted domain

Failure of Newton–Raphson iteration

Choosing a response when iteration fails

Review 1.9.5 Failure of iterative methods (A-level only) by teaching Genie

1.9.5 Failure of iterative methods (A-level only)

What you'll learn

Recap: fixed-point iteration

Showing iteration graphically

Why the derivative matters

Ways fixed-point iteration can fail

Divergence without oscillation

Oscillating divergence

A repeating cycle

Leaving the permitted domain

Failure of Newton–Raphson iteration

Choosing a response when iteration fails

Review 1.9.5 Failure of iterative methods (A-level only) by teaching Genie

1.9.5 Failure of iterative methods (A-level only) Revision Guide

1.9.5 Failure of iterative methods (A-level only)

What you'll learn

Recap: fixed-point iteration

Showing iteration graphically

Why the derivative matters

Ways fixed-point iteration can fail

Divergence without oscillation

Oscillating divergence

A repeating cycle

Leaving the permitted domain

Failure of Newton–Raphson iteration

Choosing a response when iteration fails

Review 1.9.5 Failure of iterative methods (A-level only) by teaching Genie

1.9.5 Failure of iterative methods (A-level only) Revision Guide