Locating a root of f(x) = 0 by a change of sign of a continuous function

The situations where the change-of-sign test misleads: asymptotes, two roots close together, repeated roots

Rearranging f(x) = 0 into the form x = g(x)

Carrying out an iteration xₙ₊₁ = g(xₙ) and giving the iterates to a stated accuracy

Proving that a root is correct to a given number of decimal places

Staircase and cobweb diagrams

Deciding (qualitatively) whether an iteration converges or diverges

Putting every step together in a full multi-part question

1. If f is continuous on [a, b] and f(a) and f(b) have opposite signs, then f(x) = 0 has at least one root between a and b; this change-of-sign test, together with fixed-point iteration, lets you find roots of equations that have no algebraic solution.

2. The test misleads if f is not continuous on the interval (an asymptote), and it can miss roots if there are two (or a repeated root) inside the interval.

3. Iteration: rearrange f(x) = 0 as x = g(x), choose x₀, and compute x₁ = g(x₀), x₂ = g(x₁), … If the values settle down, they settle on a root.

4. Proving accuracy: to show α= 2.279 to 3 d.p., show that f changes sign between 2.2785 and 2.2795, then conclude.

5. Diagrams: a staircase approaches the root from one side; a cobweb spirals round it from alternate sides.

6. Convergence: near the root, if the curve y = g(x) is less steep than y = x, the iteration converges; if it is steeper, the iterates move away.

Equations such as x³ - 3x - 5 = 0, ln x + 2x - 4 = 0 or e^(x/2) = 3x - 1 have no algebraic solution you can write down, yet you may still be asked for a root to three decimal places. Numerical methods give you two tools: the change-of-sign test, which traps a root in an interval, and fixed-point iteration, which homes in on it.

A root of f(x) = 0 is a value of x where the graph of y = f(x) meets the x-axis. If the graph is continuous (an unbroken curve) between x = a and x = b, and it is below the axis at one end and above it at the other, it must cross the axis somewhere in between. You cannot get from one side of a line to the other without crossing it.

Polynomials, eˣ, sin x and cos x are continuous everywhere; ln x is continuous for x > 0;

1/(x-k) and tan x have breaks. Always think about whether the interval contains a break before you use the test.

WORKED EXAMPLE · QUESTION

f(x) = x³ - 3x - 5. Show that the equation f(x) = 0 has a root α in the interval [2.2, 2.3].

SOLUTION

Evaluate f at both ends: f(2.2) = 10.648 - 6.6 - 5 = -0.952 and f(2.3) = 12.167 - 6.9 - 5 = 0.267.

f(2.2) < 0 and f(2.3) > 0, so there is a change of sign, and f is continuous because it is a polynomial. There is a root α with 2.2 < α< 2.3.

The test has a condition (continuity) and a limitation (it counts crossings in pairs). Each gives a way to be misled.

A sign change with no root. If f has a vertical asymptote (or any break) inside the interval, f can jump from negative to positive without ever being zero. Typical culprits: fractions whose denominator is zero inside the interval, and tan x near π/2.

Roots with no sign change. If the interval contains two roots (or any even number), f goes down through the axis and back up, so f(a) and f(b) have the same sign. The same happens with a repeated root, where the curve only touches the axis.

The interval is too wide. A large interval may contain several roots, so a sign change tells you little. Sketch the curve first, or use smaller steps.

WORKED EXAMPLE · QUESTION

f(x) = (2x+1)/(x-3), x ≠3. A student finds f(2) and f(4) and concludes that f(x) = 0 has a root between 2 and 4. (a) Find f(2) and f(4). (b) Explain why the student's conclusion is wrong. (c) Find the root of f(x) = 0.

SOLUTION

(a) f(2) = 5 ÷(-1) and f(4) = 9 ÷1. f(2) = -5, f(4) = 9

(b) Check the condition the test depends on. f is not continuous on [2, 4]: the denominator is zero at x = 3, where the graph has a vertical asymptote. The sign changes by jumping across the asymptote, not by crossing the x-axis.

(c) A fraction is zero when its numerator is zero: 2x + 1 = 0. x = -½, which is not in [2, 4].

Make x the subject of the equation in a way that leaves x on the right as well. Any value that satisfies x = g(x) is then a root of f(x) = 0: the two equations are equivalent. Geometrically, the root is where the line y = x meets the curve y = g(x).

One equation has many rearrangements. Common moves:

isolate a power and take a root: x³ = 3x + 5 ⇒x = ∛(3x+5)

divide through by a power of x: x² = 3 + 5/x ⇒x = √(3 + 5/x)

isolate a linear term: 3x = x³ - 5 ⇒x = (x³ - 5)/3

undo an exponential or a logarithm: e^(x/2) = 3x - 1 ⇒x = 2ln(3x - 1)

In practice the target form is almost always given ("Show that the equation can be written as …"). Your job is to get there with every step visible.

WORKED EXAMPLE · QUESTION

Show that the equation x³ - 3x - 5 = 0 can be written as (a) x = ∛(3x+5); (b) x = √(3 + 5/x), x > 0.

SOLUTION

(a) Isolate x³, then take the cube root: x³ = 3x + 5 ⇒ x = ∛(3x+5)

(b) From x³ = 3x + 5, divide by x (allowed, as x ≠0): x² = 3 + 5/x. Taking the positive root as x > 0: x = √(3 + 5/x)

Both rearrangements have exactly the same positive root as the original cubic. Whether an iteration based on them actually finds it is a separate question, answered in the sections on diagrams and convergence.

Why does a limit have to be a root? If xₙ →α, then xₙ₊₁ →α too. Taking the limit of both sides of xₙ₊₁ = g(xₙ) (for continuous g) gives α= g(α), which is the rearranged equation. A good starting value comes from a sign-change interval or a sketch. The iteration is only useful if it converges.

Using your calculator

Type the starting value and press =. Then type the formula with Ans in place of x (for example ∛(3 Ans + 5)) and press = repeatedly. Each press gives the next iterate, and the calculator keeps full accuracy.

Write down each iterate to the accuracy asked (usually 4 d.p.), but never round and re-type: rounded values fed back in can change later digits.

Angles in an iteration with sin, cos or tan are in radians. Check your calculator mode before you start.

WORKED EXAMPLE · QUESTION

Use the iteration formula xₙ₊₁ = ∛(3xₙ + 5) with x₀ = 2 to find the values of x₁, x₂ and x₃, giving each to 4 decimal places.

SOLUTION

First iterate: x₁ = ∛(3 ×2 + 5) = ∛11 = 2.223980…

Feed back the unrounded value (Ans): x₂ = ∛(3 ×2.223980…+ 5) = 2.2684…, then x₃ = 2.2770… x₁ = 2.2240, x₂ = 2.2684, x₃ = 2.2770

The values are increasing towards the root α≈2.2790: each step closes most of the remaining gap. Writing x₁ as 2.224 (3 d.p.) instead of 2.2240 does not meet the "4 decimal places" instruction; trailing zeros count.

Iterates that agree to 3 d.p. strongly suggest the answer but do not prove it. The proof is a change of sign over the right interval.

"α= 2.279 correct to 3 d.p." means 2.2785 ≤α< 2.2795. So you evaluate f at the bounds 2.2785 and 2.2795, half a unit of the last decimal place either side. If f changes sign between the bounds (and f is continuous there), the root lies in [2.2785, 2.2795], and every number in that interval rounds to 2.279. For 2 d.p. the bounds are ±0.005; for 4 d.p., ±0.00005.

WORKED EXAMPLE · QUESTION

Show that α= 2.279, correct to 3 decimal places, where α is the root of x³ - 3x - 5 = 0 in [2.2, 2.3].

SOLUTION

Choose the interval [2.2785, 2.2795]. Evaluate f at both bounds: f(2.2785) = -0.00653 and f(2.2795) = 0.00606.

There is a change of sign and f is continuous, so 2.2785 < α< 2.2795. Hence α= 2.279 to 3 d.p.

The values of f at the bounds are tiny, so give them to at least 1 or 2 significant figures; "−0.0065 and 0.0061" is fine, "0.00 and 0.01" is not.

Draw y = g(x) and y = x on the same axes; the root is where they cross. From x₀ on the x-axis go vertically to the curve: the height there is g(x₀) = x₁. Then go horizontally to the line y = x: you are now directly above x₁ on the x-axis. Repeat: vertical to the curve, horizontal to the line.

Staircase: the path climbs (or descends) in steps on one side of the root. The iterates approach the root from one direction only. This happens when g is increasing near the root.

Cobweb: the path spirals round the crossing point. The iterates land alternately above and below the root. This happens when g is decreasing near the root.

WORKED EXAMPLE · QUESTION

The equation ln x + 2x - 4 = 0 has a single root α. (a) Show that α lies between 1.7 and 1.8. (b) Show that the equation can be written as x = 2 - ½ln x. (c) Using xₙ₊₁ = 2 - ½ln xₙ with x₀ = 1, find x₁, x₂, x₃ and x₄ to 4 decimal places, and state whether a staircase or a cobweb diagram would show these iterates.

SOLUTION

(a) Let f(x) = ln x + 2x - 4, continuous for x > 0. f(1.7) = -0.0694 < 0 and f(1.8) = 0.188 > 0: change of sign and f continuous. 1.7 < α< 1.8

(b) Isolate the 2x term and divide by 2: 2x = 4 - ln x ⇒ x = 2 - ½ln x

(c) ln 1 = 0 makes the first step exact. x₁ = 2.0000, x₂ = 1.6534, x₃ = 1.7486, x₄ = 1.7206 The iterates are alternately above and below α (2.0000 > α, 1.6534 < α, 1.7486 > α, …), so the diagram is a cobweb.

Different rearrangements of the same equation behave differently. What matters is how steep the curve y = g(x) is near the root, compared with the line y = x, which has gradient 1.

Less steep than y = x (gradient between −1 and 1): each step moves the iterate closer to the root, so the iteration converges (as long as x₀ is close enough). The flatter the curve, the faster it converges.

Steeper than y = x (gradient greater than 1, or less than −1): each step throws the iterate further away, so it diverges from that root, as a staircase going outwards or a cobweb unwinding.

With P3 differentiation you can check this: work out g′(x) near the root and see whether its size is less than 1. For ∛(3x+5) the gradient at the root is about 0.19; for (x³-5)/3 it is x² ≈5.2. A diverging iteration can also wander off to a different root, or stop working because g is undefined (a negative number inside a log or a square root). A good answer describes what actually happens to the numbers.

WORKED EXAMPLE · QUESTION

The equation ln x + 2x - 4 = 0 from worked example 6, with root α≈1.727, can also be written as x = e⁴⁻²ˣ. (a) Show this. (b) Use xₙ₊₁ = e^(4-2xₙ) with x₀ = 1.7 to find x₁, x₂ and x₃ to 4 decimal places. (c) Explain why this iteration cannot be used to find α.

SOLUTION

(a) Isolate ln x, then exponentiate: ln x = 4 - 2x ⇒ x = e⁴⁻²ˣ

(b) x₁ = e^(0.6) = 1.8221, then x₂ = e^(4-2(1.8221…)) = 1.4273, then x₃ = 3.1439. x₁ = 1.8221, x₂ = 1.4273, x₃ = 3.1439

(c) The iterates jump from one side of α to the other and get further from α each time (x₀ is 0.027 from α, x₃ is more than 1.4 away).

The sequence diverges: the curve y = e⁴⁻²ˣ is much steeper than y = x near the root (its gradient there is -2α≈-3.45), giving an unwinding cobweb.

Compare x = 2 - ½ln x, whose gradient near the root is -1/2α ≈-0.29: a gentle slope, hence the converging cobweb in worked example 6.

The last example strings every skill on this page together, at the length of a full question. Notice how each part feeds the next: the sign change gives an interval, the interval gives a starting value, the iteration gives an approximate value, and a second sign change proves it.

WORKED EXAMPLE · QUESTION

f(x) = e^(x/2) - 3x + 1. The equation f(x) = 0 has two roots, α and β, where α< β.

(a) Show that β lies in the interval [5, 6].

(b) Show that f(x) = 0 can be written as x = 2ln(3x - 1), x > ⅓.

(c) Use the iteration formula xₙ₊₁ = 2ln(3xₙ - 1) with x₀ = 5 to find x₁, x₂ and x₃, giving your answers to 4 decimal places.

(d) Show that β= 5.470 correct to 3 decimal places.

(e) A student tries instead xₙ₊₁ = ⅓(e^(xₙ/2) + 1) with x₀ = 5.5. Find x₁ and x₂ to 4 decimal places and explain why this iteration will not find β.

SOLUTION

(a) f(5) = e^(2.5) - 14 = -1.82 < 0 and f(6) = e³ - 17 = 3.09 > 0. Change of sign and f is continuous, so 5 < β< 6.

(b) Isolate the exponential, then take logarithms: e^(x/2) = 3x - 1 ⇒x/2 = ln(3x - 1) ⇒ x = 2ln(3x - 1) (needs 3x - 1 > 0, i.e. x > ⅓).

(c) Iterate with Ans: x₁ = 2ln 14 = 5.2781, then x₂ = 5.3939, x₃ = 5.4402. x₁ = 5.2781, x₂ = 5.3939, x₃ = 5.4402

(d) Bounds 5.4695 and 5.4705: f(5.4695) = -0.00261 < 0 and f(5.4705) = 0.00210 > 0. Change of sign, f continuous, so 5.4695 < β< 5.4705. β= 5.470 to 3 d.p.

(e) x₁ = 5.5475, x₂ = 5.6730 x₀ = 5.5 is already above β≈5.470, and the iterates are increasing, moving away from β: the sequence diverges from β (a staircase going outwards), because near β the curve y = ⅓(e^(x/2) + 1) is much steeper than y = x (gradient about 2.57).

The iterates in (c) increased steadily towards β: a converging staircase, since 2ln(3x - 1) is increasing but shallow near β (gradient about 0.39). The formula in (e) is not useless: from a small start such as x₀ = 0 it converges to the other root, α≈0.8409, where its curve is shallow.

P1 Curve sketching and intersections

The number of roots of an equation such as e^(x/2) = 3x - 1 is the number of times two graphs cross; a quick sketch tells you how many roots to look for and roughly where.

P3 Exponentials, logarithms, trigonometry and differentiation

Most equations on this page mix eˣ, ln x or trigonometric functions with powers of x, which is exactly why they cannot be solved algebraically; the rearrangements use the laws of logarithms and inverse functions. Setting dy/dx = 0 for curves such as y = x² - 4sin x often produces an equation that needs iteration, and g′(x) near the root tells you whether an iteration will converge.

P2 The trapezium rule, and IAL Physics

The trapezium rule is the other numerical method in the course: it estimates an area that cannot be found exactly. In physics, equations from models that cannot be rearranged for the unknown are solved numerically in the same spirit.

1. Show that √5 lies between 2.2 and 2.3 using a change of sign.

2. tan 1.5 ≈14.1 and tan 1.7 ≈-7.7. Does tan x = 0 have a root between 1.5 and 1.7?

3. An iteration gives 2.31, 2.27, 2.29, 2.28, 2.285, … Staircase or cobweb?

4. Which two values of x would you test to show that a root is 0.74 correct to 2 decimal places?

5. Why can x = (x³-5)/3 not be used to find the root 2.279 of x³ - 3x - 5 = 0?

6. Using xₙ₊₁ = ∛(3xₙ + 5) with x₀ = 1, find x₁ and x₂ and say what kind of diagram they give.

1. Let f(x) = x² - 5. f(2.2) = -0.16 < 0 and f(2.3) = 0.29 > 0. f is continuous and changes sign, so the positive root of x² = 5, which is √5, lies between 2.2 and 2.3.

2. No. tan x has a vertical asymptote at x = π/2 ≈1.571, inside the interval, so it is not continuous there. The sign change comes from the asymptote; the roots of tan x = 0 are 0, π, 2π, …

3. Cobweb: the values land alternately above and below the limit (about 2.28), so they converge from alternate sides.

4. 0.735 and 0.745: half a unit of the second decimal place either side of 0.74.

5. Near the root the curve y = (x³-5)/3 has gradient x² ≈5.2, much steeper than y = x, so each iteration moves further from the root: the sequence diverges whatever starting value near the root you choose (except the root itself).

6. x₁ = ∛8 = 2 exactly, and x₂ = ∛11 = 2.2240 (4 d.p.). Both are below the root 2.279 and increasing, as g is increasing near the root, so the diagram is a converging staircase.