Bisection and Newton’s Method, calculus lesson

The equation $x^2 = 2$ has a root that no finite decimal can write down, and an equation like $\cos x = x$ has no formula for its root at all. Still, a calculator gives $\sqrt{2} \approx 1.41421356$ instantly. Behind that number is an iteration, a rule that turns one guess into a better one. Here are the two classic rules, one that cannot fail once a root is trapped and one that is far faster when it works.

Key terms

Bracketing

Definition An interval $[a, b]$ with $a < b$ brackets a root of $f$ if $f$ is continuous on $[a, b]$ and $f(a)$ and $f(b)$ have opposite signs, that is

f(a) \, f(b) < 0.

A bracketing method keeps a bracket at every step and shrinks it.

In plain words You have trapped the root between two numbers, one where $f$ is negative and one where it is positive.

Example For $f(x) = x^2 - 2$ we have $f(1) = -1 < 0$ and $f(2) = 2 > 0$ , so $[1, 2]$ brackets a root, namely $\sqrt{2}$ .

Continuity and sign change

Definition This is the intermediate value theorem applied to roots. If $f$ is continuous on $[a, b]$ and $f(a) \, f(b) < 0$ , then there is at least one $r$ in $(a, b)$ with $f(r) = 0$ . Without continuity the conclusion can fail, and a sign change can also come from a vertical asymptote rather than a root.

In plain words A continuous graph cannot get from below the axis to above it without crossing. Continuity is what makes a bracket trustworthy.

Example The function $f(x) = \frac{1}{x}$ has $f(-1) = -1$ and $f(1) = 1$ , opposite signs, yet it has no root in $[-1, 1]$ . The theorem does not apply because $f$ is not continuous at $0$ . By contrast $g(x) = \cos x - x$ is continuous with

g(0) = 1 > 0 \quad \text{and} \quad g(1) = \cos 1 - 1 \approx -0.46 < 0,

so $g$ has a root in $(0, 1)$ .

Bisection and its error bound

Definition Let $f$ be continuous on $[a, b]$ with $f(a) \, f(b) < 0$ . The bisection method starts from the bracket $[a_0, b_0] = [a, b]$ . At step $n$ it computes the midpoint $c_n = \frac{a_n + b_n}{2}$ . If $f(c_n) = 0$ it stops. Otherwise it keeps whichever half, $[a_n, c_n]$ or $[c_n, b_n]$ , still has a sign change, and calls it $[a_{n+1}, b_{n+1}]$ . The brackets are nested, the bracket $[a_n, b_n]$ has length $\frac{b - a}{2^n}$ , and there is a root $r$ of $f$ that lies in every bracket. Since $c_n$ is the midpoint of a bracket containing $r$ ,

\lvert c_n - r \rvert \le \frac{b - a}{2^{n+1}}, \qquad n = 0, 1, 2, \dots

In plain words Each step cuts the bracket in half, so each step buys one more correct binary digit. It is slow but it is guaranteed, and you know the error in advance.

Example For $f(x) = x^2 - 2$ on $[1, 2]$ the first steps are these.

$n$	$a_n$	$b_n$	$c_n$	sign of $f(c_n)$
$0$	$1$	$2$	$1.5$	$+$
$1$	$1$	$1.5$	$1.25$	$-$
$2$	$1.25$	$1.5$	$1.375$	$-$
$3$	$1.375$	$1.5$	$1.4375$	$+$
$4$	$1.375$	$1.4375$	$1.40625$	$-$

To guarantee $\lvert c_n - \sqrt{2} \rvert \le 10^{-6}$ you need

\frac{1}{2^{n+1}} \le 10^{-6}, \quad \text{that is} \quad 2^{n+1} \ge 10^6.

Since $2^{19} = 524288$ and $2^{20} = 1048576$ , the first $n$ that works is $n = 19$ .

Newton iteration and the tangent construction

Definition Let $f$ be differentiable at the current guess $x_n$ with $f'(x_n) \neq 0$ . The tangent line to the graph at $(x_n, f(x_n))$ is $y = f(x_n) + f'(x_n)(x - x_n)$ . Setting $y = 0$ and solving for $x$ gives the next guess

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

Newton’s method repeats this step from a starting value $x_0$ .

In plain words Replace the curve by its tangent line, see where the line hits the axis, and use that point as the new guess. Near a root the curve and its tangent are almost the same, so the new guess is much better.

Example For $f(x) = x^2 - 2$ the rule becomes

x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n}.

Starting at $x_0 = 1$ gives this table.

$n$	$x_n$	$x_n - \sqrt{2}$
$0$	$1$	$-0.414$
$1$	$1.5$	$8.6 \times 10^{-2}$
$2$	$1.416666\ldots$	$2.5 \times 10^{-3}$
$3$	$1.414215686\ldots$	$2.1 \times 10^{-6}$
$4$	$1.414213562374\ldots$	$1.6 \times 10^{-12}$

Four steps reach the accuracy that bisection needs about 40 steps for.

Initial guess

Definition The initial guess $x_0$ is the starting value of the iteration. Newton’s method has no bracket, so whether the iterates converge, and to which root, depends on $x_0$ . A common practice is to locate a root roughly first, for example by a plot or a few bisection steps, and then start Newton’s method close to it.

In plain words Newton’s method is only as good as where you start. Start close and it flies, start far and it may wander off.

Example The function $f(x) = \arctan x$ has the single root $0$ , and its Newton step is

x_{n+1} = x_n - (1 + x_n^2) \arctan x_n.

From $x_0 = 1$ the iterates are about $-0.571$ , $0.117$ , $-0.001$ and then essentially $0$ . From $x_0 = 1.5$ they are about $-1.694$ , $2.321$ , $-5.114$ , $32.3$ , growing without bound.

Derivative zero

Definition The Newton step needs $f'(x_n) \neq 0$ . If $f'(x_n) = 0$ the tangent line is horizontal and, unless $f(x_n) = 0$ , never meets the axis, so $x_{n+1}$ is undefined. If $f'(x_n)$ is merely close to zero, the step $\frac{f(x_n)}{f'(x_n)}$ is huge and throws the next guess far away. At a root $r$ with $f'(r) = 0$ (a multiple root) the method usually still converges from nearby starting values, but only linearly.

In plain words A flat tangent points nowhere useful. Avoid starting near a turning point of the graph.

Example For $f(x) = x^2 - 2$ with $x_0 = 0$ we get $f'(0) = 0$ and the formula would divide by zero. With $x_0 = 0.01$ the next guess is

x_1 = 0.01 - \frac{0.0001 - 2}{0.02} \approx 100.0,

very far from $\sqrt{2}$ .

Cycles and divergence

Definition Newton’s iterates need not converge. They can form a cycle, meaning that for some period $p \ge 2$ we have $x_{n+p} = x_n$ for all $n$ while the values are not all equal. They can also diverge, either with $\lvert x_n \rvert \to \infty$ or by wandering without settling down.

In plain words The tangent can send you back and forth between the same two points forever, or keep pushing you farther away.

Example Take $f(x) = x^3 - 2x + 2$ , so $f'(x) = 3x^2 - 2$ . From $x_0 = 0$ ,

x_1 = 0 - \frac{2}{-2} = 1, \qquad x_2 = 1 - \frac{1}{1} = 0,

so the iterates cycle $0, 1, 0, 1, \dots$ and never approach the real root near $-1.77$ . For divergence take $f(x) = \sqrt[3]{x}$ , where the step simplifies to $x_{n+1} = x_n - 3x_n = -2x_n$ . Every nonzero start doubles in size and flips sign at each step.

Local convergence conditions

Definition Suppose $f''$ is continuous on an open interval containing a root $r$ , with $f(r) = 0$ and $f'(r) \neq 0$ . Choose $\delta > 0$ so small that $J = [r - \delta, r + \delta]$ lies in that interval, $f'$ has no zero on $J$ , and

C \delta < 1, \qquad \text{where } C = \frac{\max_{J} \lvert f'' \rvert}{2 \min_{J} \lvert f' \rvert}.

Such a $\delta$ always exists, because $C$ stays bounded as $\delta$ shrinks. Then for every $x_0$ in $J$ the Newton iterates are defined, stay in $J$ , converge to $r$ , and satisfy

\lvert x_{n+1} - r \rvert \le C \lvert x_n - r \rvert^2.

This is called quadratic convergence. The estimate comes from Taylor’s formula, which gives

x_{n+1} - r = \frac{f''(\xi_n)}{2 f'(x_n)} (x_n - r)^2

for some $\xi_n$ between $x_n$ and $r$ . The condition $C\delta < 1$ makes each error at most $C\delta$ times the previous one, so the iterates never leave $J$ . The word local matters. The theorem promises nothing for starting values far from $r$ .

In plain words Close enough to a simple root, the error gets squared at each step, so the number of correct digits roughly doubles every time.

Example In the $\sqrt{2}$ table the errors go $2.5 \times 10^{-3}$ , then $2.1 \times 10^{-6}$ , then $1.6 \times 10^{-12}$ . Each is about $0.35$ times the square of the previous one, which fits

C \approx \frac{f''(r)}{2f'(r)} = \frac{2}{2 \cdot 2\sqrt{2}} \approx 0.354.

Check yourself

How many bisection steps on $[0, 1]$ guarantee that the midpoint is within $10^{-3}$ of a root?

Show the answer

You need $\frac{1}{2^{n+1}} \le 10^{-3}$ , so $2^{n+1} \ge 1000$ . Since $2^{10} = 1024$ , the smallest choice is $n + 1 = 10$ , that is $n = 9$ .

Write the Newton step for $f(x) = x^3 - 5$ and do one step from $x_0 = 2$ .

Show the answer

The step is

x_{n+1} = x_n - \frac{x_n^3 - 5}{3x_n^2}.

From $x_0 = 2$ it gives $x_1 = 2 - \frac{3}{12} = 1.75$ . The true root is $\sqrt[3]{5} \approx 1.70998$ .

Why does Newton’s method fail for $f(x) = x^2 + 1$ from any real starting value?

Show the answer

The function has no real root, since $x^2 + 1 \ge 1$ . The iterates can never converge to a real number $r$ with $f(r) = 0$ . They jump around, and from $x_0 = 0$ the step is not even defined because $f'(0) = 0$ .

Bisection and Newton’s Method

Key terms

Bracketing

Continuity and sign change

Bisection and its error bound

Newton iteration and the tangent construction

Initial guess

Derivative zero

Cycles and divergence

Local convergence conditions

Check yourself

How this lesson connects

Builds on