Solving Equations by Iteration

An equation with no tidy answer

The equation $x^2-4x+1=0$x² − 4x + 1 = 0 has roots $2-\sqrt{3}$2 − √3 and $2+\sqrt{3}$2 + √3, which the quadratic formula gives. Many equations have no such formula: in $m=20\ln \left(\frac{720}{m}\right)$m = 20 ln(720/m), m appears both outside and inside a logarithm, and no rearrangement leaves it alone on one side. Iteration finds a root as a decimal, to any accuracy wanted, by repeating one simple calculation. The quadratic is a good place to learn it, because its answer can be checked.

Rearrange into x = g(x)

Rearrange the equation until a single x stands alone on one side. Move the 4x across: $4x=x^2+1$4x = x² + 1. Divide by 4: $x=\frac{x^2+1}{4}$x = (x² + 1)/4.

The right side is called g(x), so the equation now reads x = g(x) with $g\left(x\right)=\frac{x^2+1}{4}$g(x) = (x² + 1)/4. Nothing has been solved yet: there is still an x on the right. But the equation now says something useful. A root is a number that g leaves unchanged.

A root is where y = g(x) meets y = x

Draw y = g(x) and the straight line y = x. Where they cross, the height of the curve equals the height of the line, so g(x) = x. That value of x is a root of $x^2-4x+1=0$x² − 4x + 1 = 0.

A number that g sends to itself is called a fixed point of g. Put $2-\sqrt{3}\approx 0.2679$2 − √3 ≈ 0.2679 into g and 0.2679 comes back out.

The gold curve is $y=\frac{x^2+1}{4}$y = (x² + 1)/4 and the dashed line is y = x. They cross at $x\approx 0.2679$x ≈ 0.2679, where the input to g equals its output.

Feed each answer back in

Start from a rough guess, $x_0=1$x₀ = 1, and put it into the right side: $x_1=\frac{1^2+1}{4}=\frac{2}{4}=0.5$x₁ = (1² + 1)/4 = 2/4 = 0.5. Then put $x_1$x₁ in: $x_2=\frac{0.5^2+1}{4}=\frac{1.25}{4}=0.3125$x₂ = (0.5² + 1)/4 = 1.25/4 = 0.3125.

Keep going, each output becoming the next input, and keep every digit the calculator gives: $x_3=0.2744$x₃ = 0.2744, $x_4=0.2688$x₄ = 0.2688, $x_5=0.2681$x₅ = 0.2681, $x_6=0.26796$x₆ = 0.26796 and $x_7=0.26795$x₇ = 0.26795. The values settle toward $2-\sqrt{3}=0.267949\dots$2 − √3 = 0.267949…

The rule is written $x_{n+1}=\frac{x_n^2+1}{4}$xₙ₊₁ = (xₙ² + 1)/4. Square the old value, add 1, and divide the whole of that by 4.

The staircase

The same steps can be drawn. Start at $x_0=1$x₀ = 1 on the x-axis and go vertically to the curve: the height there is g(1) = 0.5, which is $x_1$x₁. Go horizontally to the line y = x: on that line the height and the x-coordinate are equal, so the point reached is above $x_1=0.5$x₁ = 0.5. Go vertically to the curve again, reaching the height g(0.5) = 0.3125, which is $x_2$x₂, and horizontally to the line.

Vertically to the curve, horizontally to the line, and repeat. The path is a staircase that closes in on the crossing point.

From $x_0=1$x₀ = 1: up to the curve at height 0.5, across to the line, down to the curve at 0.3125, across to the line, and down to 0.2744. Each step is shorter than the one before, and the staircase closes in on the crossing.

How fast it closes in

Compare each value with the root 0.267949. The errors are 0.732, 0.232, 0.0446, 0.0065, 0.00088 and 0.00012. After the first few steps each error is about 0.13 times the one before.

That number is the gradient of the curve at the root. $g\left(x\right)=\frac{x^2+1}{4}$g(x) = (x² + 1)/4 has gradient $g^{\prime }\left(x\right)=\frac{x}{2}$g'(x) = x/2, and at x = 0.2679 that is 0.134. Near the root the curve is almost a straight line of gradient 0.134, so each step lands about 0.134 times as far from the root as the step before.

When to stop

Stop when successive values agree to the accuracy asked for, and not when one value happens to round correctly. To 4 decimal places, $x_6=0.26796$x₆ = 0.26796 and $x_7=0.26795$x₇ = 0.26795 both round to 0.2680, but $x_8=0.267949$x₈ = 0.267949 rounds to 0.2679. Two values agreeing is a sign, not a proof.

The proof is a change of sign. $f\left(x\right)=x^2-4x+1$f(x) = x² − 4x + 1 is continuous, f(0.26785) = 0.00034 is positive and f(0.26795) = −0.0000028 is negative, so a root lies between 0.26785 and 0.26795, and every number there rounds to 0.2679.

The other root runs away

The curve $y=\frac{x^2+1}{4}$y = (x² + 1)/4 crosses y = x a second time, at $2+\sqrt{3}\approx 3.7321$2 + √3 ≈ 3.7321. Start just above it, at $x_0=3.9$x₀ = 3.9, and the values are 4.0525, 4.3557, 4.9930 and 6.4825: each lands further from 3.7321 than the one before. Start just below, at 3.7, and they fall away: 3.6725, 3.6218, 3.5294, heading down to the other root, 0.2679.

The gradient explains it. At 3.7321, $g^{\prime }\left(x\right)=\frac{x}{2}=1.87$g'(x) = x/2 = 1.87, more than 1. Near that root each error is multiplied by about 1.87, so every step makes it bigger.

Near the second root, 3.7321, the gold curve is steeper than the dashed line y = x. From $x_0=3.9$x₀ = 3.9 the staircase climbs away from the crossing, each step longer than the one before.

Another rearrangement

The same equation can be rearranged differently. Divide $x^2-4x+1=0$x² − 4x + 1 = 0 by x: $x-4+\frac{1}{x}=0$x − 4 + 1/x = 0, so $x=4-\frac{1}{x}$x = 4 − 1/x. Its gradient is $\frac{1}{x^2}$1/x², which is 0.072 at 3.7321, much less than 1.

From $x_0=4$x₀ = 4: $x_1=4-\frac{1}{4}=3.75$x₁ = 4 − 1/4 = 3.75, $x_2=4-\frac{1}{3.75}=3.7333$x₂ = 4 − 1/3.75 = 3.7333, $x_3=3.73214$x₃ = 3.73214 and $x_4=3.73206$x₄ = 3.73206, closing in on 3.7321 quickly. Started from 1, this rearrangement also reaches 3.7321, not 0.2679: near 0.2679 its gradient is $\frac{1}{0.2679^2}\approx 13.9$1/0.2679² ≈ 13.9, so that root pushes the values away.

So the test, for any rearrangement x = g(x), is the size of g' near the root. When −1 < g'(x) < 1 there, values that start close enough close in. When g' is bigger than 1 or less than −1, they move away, and another rearrangement is needed.

Closing in from both sides

When g' is negative near the root, the values fall on alternate sides of it. Equal temperatures for a cooling cup and a warming tank lead to $m=20\ln \left(\frac{720}{m}\right)$m = 20 ln(720/m), whose gradient $-\frac{20}{m}$−20/m is about −0.38 near the root. From $m_0=50$m₀ = 50 the values are 53.34, 52.05, 52.54, 52.35, 52.42 and 52.40: above, below, above, below, each nearer than the last.

Drawn, the path is not a staircase but a square spiral, winding in on the crossing.

The gold curve is $20\ln \left(\frac{720}{m}\right)$20 ln(720/m), falling as m rises, and the dashed line marks where the output equals the input. From 50 the path goes up to 53.34, back to 52.05, up to 52.54: a spiral, on alternate sides of the root at 52.4.

The square root of 2, and a rearrangement that never settles

For $x^2=2$x² = 2, one rearrangement is $x=\frac{x+\frac{2}{x}}{2}$x = (x + 2/x)/2. From 1: $\frac{1+2}{2}=\frac{3}{2}$(1 + 2)/2 = 3/2, then $\frac{\frac{3}{2}+\frac{4}{3}}{2}=\frac{17}{12}\approx 1.41667$(3/2 + 4/3)/2 = 17/12 ≈ 1.41667, then 1.414216, close to $\sqrt{2}=1.414214$√2 = 1.414214. Check $\frac{17}{12}$17/12: 17 × 17 = 289 and 2 × 144 = 288, so ${\left(\frac{17}{12}\right)}^2=\frac{289}{144}$(17/12)² = 289/144 is just over 2.

Written as $x=\frac{2}{x}$x = 2/x instead, the same equation goes nowhere. From 1 it gives 2, and from 2 it gives 1 again, forever. Here $g^{\prime }\left(x\right)=-\frac{2}{x^2}$g'(x) = −2/x², which is exactly −1 at $\sqrt{2}$√2, so the values neither close in nor move away. When values jump about like this, try another rearrangement.

The usual mistakes

Dividing only the last term. In $x_{n+1}=\frac{x_n^2+1}{4}$xₙ₊₁ = (xₙ² + 1)/4 the division line runs under the whole bracket: from 2, the next value is $\frac{4+1}{4}=1.25$(4 + 1)/4 = 1.25, not $4+\frac{1}{4}=4.25$4 + 1/4 = 4.25.

Forgetting to square. The formula squares the previous value first: $\frac{2+1}{4}=0.75$(2 + 1)/4 = 0.75 leaves out the square.

Giving $x_1$x₁ when $x_2$x₂ is asked for. $x_2$x₂ puts $x_1$x₁ back through the same formula a second time.

Doubling instead of iterating. The output goes back in as the new input; adding it to itself is not the iteration.

Stopping at the first value that rounds correctly, before two successive values agree.

Two applications

In the first application below, a tank must hold $4m^3$4 m³ and use $13m^2$13 m² of steel, which leads to $x^3-13x+16=0$x³ − 13x + 16 = 0 with two positive roots. One rearrangement closes in on the smaller and runs away from the larger, and the gradient test explains why.

In the second, a loan is repaid in three equal payments, and x = 1 + r, one plus the rate of interest, satisfies a cubic. Its rearrangement has a gradient of about 0.35 near the root, so each step is about a third of the one before.