Fixed point iteration: solving equations numerically

Fixed point iteration approximates a solution of an equation by repeatedly applying a function. Write the equation in the form

$$x=g(x),$$

choose a starting value $x_0$, then calculate

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

If the values converge to a limit $\alpha$, continuity of $g$ gives

$$\alpha=g(\alpha),$$

so $\alpha$ is a fixed point of $g$. It is therefore a solution of the original equation, provided the rearrangement has not introduced an invalid solution.

Prerequisites

You should be able to:

• rearrange algebraic equations;
• substitute into functions using a calculator;
• solve equations graphically and interpret intersections;
• differentiate elementary functions;
• round to decimal places and significant figures.

Review functions and notation, function graphs, and differentiation basics if needed.

From an equation to an iteration

An equation $f(x)=0$ must be rearranged into $x=g(x)$. The rearrangement is not unique, and different choices of $g$ can behave very differently.

For example,

$$x^3+x-1=0$$

can be written as either

$$x=1-x^3$$

or, since $x^3=1-x$,

$$x=\sqrt[3]{1-x}.$$

These give the iteration formulae

$$x_{n+1}=1-x_n^3 \qquad\text{and}\qquad x_{n+1}=\sqrt[3]{1-x_n}.$$

Both have the same fixed point, but neither is automatically guaranteed to converge from every starting value.

Worked example 1: generate successive approximations

Use

$$x_{n+1}=\sqrt{3x_n+4}, \qquad x_0=3,$$

to find $x_1$, $x_2$, $x_3$ and $x_4$.

Apply the formula repeatedly, using each new value as the next input:

$$\begin{aligned} x_1&=\sqrt{3(3)+4}=\sqrt{13}=3.605551\ldots,\\ x_2&=\sqrt{3(3.605551\ldots)+4}=3.849890\ldots,\\ x_3&=\sqrt{3(3.849890\ldots)+4}=3.943307\ldots,\\ x_4&=\sqrt{3(3.943307\ldots)+4}=3.978680\ldots. \end{aligned}$$

The values appear to approach $4$. Indeed, a fixed point satisfies

$$x=\sqrt{3x+4}.$$

Squaring gives

$$x^2-3x-4=0 \quad\Longrightarrow\quad (x-4)(x+1)=0.$$

The square root is non-negative, so $x=-1$ cannot satisfy the rearranged equation. The relevant fixed point is $x=4$.

Calculator practice: keep unrounded values in the calculator memory. Rounding every intermediate value can change later digits and may make convergence appear earlier than it really occurs.

Self-check 1

For

$$x_{n+1}=\ln(5+x_n), \qquad x_0=1,$$

calculate $x_1$, $x_2$ and $x_3$ to $5$ decimal places.

Answer

$$\begin{aligned} x_1&=\ln 6=1.79176,\\ x_2&=\ln(5+1.791759\ldots)=1.91571,\\ x_3&=\ln(5+1.915707\ldots)=1.93379. \end{aligned}$$

The display values are rounded, but each next calculation should use the full stored value.

Why iteration can converge

The fixed point equation $x=g(x)$ describes intersections of the curves

$$y=x \qquad\text{and}\qquad y=g(x).$$

Starting at $x_n$ on the horizontal axis, move vertically to $y=g(x)$ and then horizontally to $y=x$. This transfers the output $g(x_n)$ back into the input position $x_{n+1}$. Repeating these steps produces a cobweb diagram.

Near a fixed point $\alpha$, differentiation gives the approximation

$$g(x)-g(\alpha)\approx g'(\alpha)(x-\alpha).$$

Since $g(\alpha)=\alpha$, the errors $e_n=x_n-\alpha$ approximately satisfy

$$e_{n+1}\approx g'(\alpha)e_n.$$

Therefore:

• if $|g'(\alpha)|<1$, nearby errors shrink and the iteration usually converges;
• if $|g'(\alpha)|>1$, nearby errors grow and the fixed point is repelling;
• if $g'(\alpha)<0$, successive values tend to alternate across the root;
• if $0<g'(\alpha)<1$, successive values usually approach from one side;
• if $|g'(\alpha)|=1$, this test is inconclusive.

A stronger textbook condition is useful when the root is only known to lie in an interval $I$. If $g$ maps $I$ into itself and

$$|g'(x)|\le k<1$$

for every $x\in I$, then the iteration converges to the unique fixed point in $I$ for every starting value in that interval.

Worked example 2: choose a convergent rearrangement

Consider

$$x^3+x-1=0.$$

Compare the rearrangements

$$g_1(x)=1-x^3 \qquad\text{and}\qquad g_2(x)=\sqrt[3]{1-x}.$$

The root is approximately $\alpha=0.6823$. Differentiate:

$$g_1'(x)=-3x^2,$$

so

$$|g_1'(\alpha)|\approx 3(0.6823)^2\approx1.40>1.$$

This rearrangement is locally divergent.

For the second rearrangement,

$$g_2'(x)=-\frac{1}{3(1-x)^{2/3}}.$$

At a fixed point, $1-\alpha=\alpha^3$, so

$$g_2'(\alpha)=-\frac{1}{3\alpha^2} \approx-0.716.$$

Thus $|g_2'(\alpha)|<1$, so nearby values converge and alternate across the root. With $x_0=0.7$:

$$\begin{array}{c|c} n & x_n \\\hline 0&0.700000\\ 1&0.669433\\ 2&0.691438\\ 3&0.675742\\ 4&0.687011 \end{array}$$

The alternation is visible. The convergence is not especially fast because $|g_2'(\alpha)|$ is closer to $1$ than to $0$.

Self-check 2

The equation $x^2+x-3=0$ is rearranged as

$$x=\frac{3}{x+1}.$$

Show that iteration is expected to converge to the positive root, but not to the negative root.

Answer

Here

$$g(x)=\frac{3}{x+1}, \qquad g'(x)=-\frac{3}{(x+1)^2}.$$

The roots are

$$\alpha=\frac{-1+\sqrt{13}}2\approx1.303, \qquad \beta=\frac{-1-\sqrt{13}}2\approx-2.303.$$

Therefore

$$|g'(\alpha)|\approx0.566<1, \qquad |g'(\beta)|\approx1.767>1.$$

The positive fixed point is attracting and the negative fixed point is repelling.

Giving a root to a stated accuracy

Seeing two displayed iterates agree is evidence, not automatically a proof, that the limiting root rounds to those digits. The exam question may supply a convergence assumption, ask only for an approximation, or require a sign-change check.

Worked example 3: iteration followed by verification

The equation

$$x^3+x-1=0$$

has a root near $0.7$. Using

$$x_{n+1}=\sqrt[3]{1-x_n}, \qquad x_0=0.7,$$

continued iteration gives

$$x_{20}=0.682350\ldots, \qquad x_{21}=0.682312\ldots.$$

These suggest $x=0.682$ to $3$ decimal places. To prove the rounding, test the boundaries of the rounding interval:

$$f(x)=x^3+x-1.$$

Then

$$f(0.6815)<0 \qquad\text{and}\qquad f(0.6825)>0.$$

Because $f$ is continuous, a root lies between $0.6815$ and $0.6825$, so it rounds to

$$\boxed{0.682\text{ to }3\text{ decimal places}}.$$

Also,

$$f'(x)=3x^2+1>0,$$

so $f$ is strictly increasing and the root is unique. This removes any ambiguity about which root has been located. See locating roots by a change of sign for the full justification.

A useful stopping rule

If a contraction bound $|g'(x)|\le k<1$ is known on a suitable interval, then the remaining error can be bounded by

$$|\alpha-x_n|\le \frac{k}{1-k}|x_n-x_{n-1}|.$$

This is stronger than merely checking whether two iterates have the same rounded form.

Worked example 4: bound the error

Suppose an iteration remains in an interval where $|g'(x)|\le0.2$, and

$$|x_8-x_7|=0.00012.$$

Then

$$|\alpha-x_8| \le\frac{0.2}{1-0.2}(0.00012) =0.00003.$$

Thus $x_8$ is within $3\times10^{-5}$ of the root. This guarantees $4$ decimal places unless $x_8$ lies unusually close to a rounding boundary, which can be checked directly.

Common misconceptions

Treating $x_n$ as a power

The subscript labels the position in the sequence:

$$x_3\ne x^3.$$

In $x_{n+1}=g(x_n)$, the next term is obtained by substituting the current term into $g$.

Solving the recurrence instead of iterating

Most A-level questions expect repeated numerical substitution. You do not need a formula for $x_n$ in terms of $n$.

Assuming every rearrangement converges

Algebraic equivalence preserves fixed points, but it does not preserve convergence. Inspect $|g'(x)|$ near the required root or calculate enough terms to recognise divergence, oscillation, or a cycle.

Rounding at every step

Keep the calculator’s full precision and round only the values you report. Early rounding feeds an artificial input into every later step.

Forgetting the domain

Square roots, logarithms and denominators restrict the allowed inputs. For example, $x_{n+1}=\ln(x_n-2)$ requires $x_n>2$ at every step.

Believing equal displayed values prove convergence

A sequence can converge slowly, enter a cycle, or agree temporarily after rounding. Use the derivative test, a supplied convergence statement, an error bound, or a sign-change verification as appropriate.

Exam-style mixed example

The equation

$$e^{-x}=x$$

has one positive solution.

1. Write down a fixed point iteration.
2. Starting with $x_0=0.5$, calculate $x_1$, $x_2$ and $x_3$.
3. Explain why the iteration converges near the root.
4. State the root to $3$ decimal places.

Solution

1. The equation already gives

   $$\boxed{x_{n+1}=e^{-x_n}}.$$

2. Repeated substitution gives

   $$\begin{aligned} x_1&=e^{-0.5}=0.606531\ldots,\\ x_2&=e^{-0.606531\ldots}=0.545239\ldots,\\ x_3&=e^{-0.545239\ldots}=0.579703\ldots. \end{aligned}$$

   The values alternate because $g'(x)=-e^{-x}<0$.

3. At a fixed point $\alpha$, $e^{-\alpha}=\alpha$. Hence

   $$|g'(\alpha)|=e^{-\alpha}=\alpha.$$

   The positive root is approximately $0.567$, so $|g'(\alpha)|<1$. The fixed point is attracting.

4. Continuing the iteration gives values approaching $0.567143\ldots$, so

   $$\boxed{x=0.567\text{ to }3\text{ decimal places}}.$$

Final self-check

Let

$$x_{n+1}=\frac12\left(x_n+\frac{5}{x_n}\right), \qquad x_0=2.$$

1. Calculate $x_1$, $x_2$ and $x_3$.
2. Find the positive fixed point.
3. Find $g'(x)$ and explain why convergence becomes very fast near that fixed point.

Answer

The iterations are

$$\begin{aligned} x_1&=\frac12\left(2+\frac52\right)=2.25,\\ x_2&=\frac12\left(2.25+\frac{5}{2.25}\right)=2.236111\ldots,\\ x_3&=\frac12\left(2.236111\ldots+\frac{5}{2.236111\ldots}\right) =2.236067978\ldots. \end{aligned}$$

At a fixed point,

$$x=\frac12\left(x+\frac5x\right) \quad\Longrightarrow\quad x^2=5.$$

The positive fixed point is $\sqrt5$.

Here

$$g'(x)=\frac12\left(1-\frac5{x^2}\right),$$

so

$$g'(\sqrt5)=0.$$

The first-order error term vanishes at the root, which explains the particularly rapid convergence.

What to remember

For a fixed point iteration:

1. rearrange the equation as $x=g(x)$;
2. write $x_{n+1}=g(x_n)$ clearly;
3. substitute the given $x_0$ repeatedly using full calculator precision;
4. expect local convergence when $|g'(\alpha)|<1$;
5. check domain restrictions and reject invalid solutions;
6. justify a stated accuracy when the question requires proof.

Next, study when numerical iteration fails and compare this method with the Newton-Raphson method. The trapezium rule applies numerical approximation to integration rather than root finding.