Iterative methods (x = g(x))

Solving f(x) = 0 by rearranging it into x = g(x) and iterating x_(n+1) = g(x_n) from a starting value — why some rearrangements converge and others diverge, and reading staircase and cobweb diagrams.

Pure · Numerical methods

Iterative methods (x = g(x))

Why it works

A change of sign traps a root; an iteration hunts it down to many decimal places. The trick is to rewrite

f(x) = 0

in the form

x = g(x).

A solution of this is a value that comes out the same as it went in — a fixed point. The idea: guess a starting value

x_0

near the root, feed it through

g

to get

x_1 = g(x_0)

, feed that back to get

x_2 = g(x_1)

, and keep going:

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

If this sequence settles down to a limit

L

, then

L = g(L)

, so

L

is a root of the original equation. You stop when successive values agree to the accuracy you need.

The rearrangement matters — a lot. The same equation can be written

x = g(x)

in many ways, and they don't all work. From

x^3 - 2x - 5 = 0

$x^3 = 2x + 5 \Rightarrow x = \sqrt[3]{2x + 5}$ — this one converges.
$2x = x^3 - 5 \Rightarrow x = \dfrac{x^3 - 5}{2}$ — this one diverges, flying away

from the root.

What separates them is the steepness of

g

at the root: the iteration converges when $|g'(\text{root})| < 1$ and diverges when

|g'(\text{root})| > 1

. A gently sloped

g

pulls successive values inward; a steep one flings them out.

Staircase and cobweb diagrams show the iteration on the graph of

y = g(x)

together with the line

y = x

(the root is where they meet). From

x_n

you go vertically to the curve to find

g(x_n) = x_{n+1}

, then horizontally to the line

y = x

to carry that value back onto the

x

-axis as the next input — and repeat.

If $0 < g'(\text{root}) < 1$ the steps march in from one side: a staircase.
If $-1 < g'(\text{root}) < 0$ the steps alternate sides, spiralling in: a cobweb.

In practice: write the iteration formula, list successive values keeping plenty of decimals, stop when they agree to the required accuracy — then confirm the root with a sign change over a suitable interval, since the iteration only suggests the answer.