Roots of Equations

Most equations cannot be solved exactly. These methods find a root to any accuracy you like — and, just as importantly, tell you when they are about to fail.

Locating a root

If $f$ is continuous on $[a,b]$ and $f(a)$ and $f(b)$ have opposite signs, then $f$ has a root somewhere between them.

Show that $f(x) = x^3 - x - 1$ has a root between 1 and 2.

$$f(1) = 1 - 1 - 1 = -1 \qquad f(2) = 8 - 2 - 1 = 5$$

The sign changes from negative to positive, and $f$ is a polynomial and therefore continuous, so a root lies in $(1,2)$.

Interval bisection

Halve the interval, keep the half where the sign still changes, repeat.

Starting from $(1, 2)$ with $f(x) = x^3 - x - 1$:

Each step halves the width, so after $n$ steps the interval is $\frac{b-a}{2^n}$ wide. From a width of 1, four bisections give $0.0625$ — enough to fix the root to one decimal place.

Linear interpolation

Instead of taking the midpoint, join $(a, f(a))$ and $(b, f(b))$ with a straight line and take where that line crosses the axis:

$$x \approx a + (b-a)\,\frac{|f(a)|}{|f(a)| + |f(b)|}$$

For our example:

$$x \approx 1 + 1 \times \frac{1}{1+5} = 1.167$$

This weights the estimate towards whichever end has the smaller function value — a better guess than the midpoint when the function is nearly straight, and a worse one when it curves sharply.

The Newton–Raphson method

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Geometrically: take the tangent at your current estimate and follow it to the $x$-axis. That crossing point is the next estimate.

Apply it to $f(x) = x^3 - x - 1$ starting from $x_0 = 1.5$.

$$f'(x) = 3x^2 - 1$$

$$f(1.5) = 0.875 \qquad f'(1.5) = 5.75$$

$$x_1 = 1.5 - \frac{0.875}{5.75} = 1.3478$$

$$x_2 = 1.3478 - \frac{0.1008}{4.4499} = 1.3252$$

$$x_3 = 1.3247$$

The true root is $1.32472\ldots$ — three steps for five significant figures, where bisection would have needed about fifteen.

Fixed-point iteration

Rearrange $f(x) = 0$ into the form $x = g(x)$, then iterate

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

From $x^3 - x - 1 = 0$ there are several rearrangements. Taking $x^3 = x+1$ gives

$$x = (x+1)^{1/3}$$

Starting at $x_0 = 1$:

$$x_1 = 2^{1/3} = 1.2599 \qquad x_2 = 1.3123 \qquad x_3 = 1.3223 \qquad x_4 = 1.3243$$

converging steadily to $1.3247$.

But the rearrangement $x = x^3 - 1$, from the same equation, diverges. Starting at $x_0 = 1.3$:

$$x_1 = 1.197 \qquad x_2 = 0.715 \qquad x_3 = -0.634 \qquad \ldots$$

running away from the root entirely.

Accuracy and failure

When does iteration converge?

$$\text{The iteration } x_{n+1} = g(x_n) \text{ converges near a root if } |g'(x)| < 1.$$

For $g(x) = (x+1)^{1/3}$: $g'(x) = \frac13(x+1)^{-2/3}$, which near $x = 1.32$ is about $0.19$. Since $0.19 < 1$, it converges ✓

For $g(x) = x^3 - 1$: $g'(x) = 3x^2$, which near the root is about $5.3$. Since $5.3 > 1$, it diverges ✓

Confirming an answer

To show a root is $1.32$ correct to 2 decimal places, evaluate $f$ at $1.315$ and $1.325$ and demonstrate a sign change between them. Those are the bounds that round to $1.32$.