Convergence of Newton's Method and Bisection: 23-Chem-B3 Simulation, Modelling, and Optimization, December 2014, Q6

Question 6: Convergence of Newton's Method and Bisection (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A function with a single root $\alpha$; along the axis the marked points are ordered $B,\ A,\ C,\ \alpha,\ D$. The curve rises to a maximum at $A$ (so $f'(A)=0$) and then descends through $\alpha$; thus $f\gt0$ at $B$, $A$ and $C$, while $f\lt0$ at $D$.

Find. Whether each iteration reaches the root $\alpha$.

Figure 3 — Reproduced sketch for Q6: single root α; f rises to a maximum at A and falls through α. f(B),f(A),f(C) > 0 and f(D) < 0.

Approach. For Newton, apply $x_{{n+1}} = x_n - f(x_n)/f'(x_n)$ and check the direction of the first step; for bisection, check whether the starting interval brackets the root (opposite signs at its ends).

(a) Newton from $x=A$. $A$ is the maximum, so $f'(A)=0$: the tangent is horizontal and the update $x_{{n+1}} = A - f(A)/0$ is undefined (it shoots to $\pm\infty$). Newton fails / diverges — the root is not reached.
(b) Newton from $x=B$. $B$ lies on the rising branch to the left of the maximum, where $f(B)\gt0$ and $f'(B)\gt0$. The step is $-f(B)/f'(B) \lt 0$, moving the iterate left, away from $\alpha$ (which lies to the right). The iteration diverges — the root is not reached.
(c) Bisection on $\overline{{AD}}$. $f(A)\gt0$ and $f(D)\lt0$ have opposite signs, so the interval brackets $\alpha$ (the only root inside). Bisection converges to $\alpha$.
(d) Bisection on $\overline{{BD}}$. $f(B)\gt0$ and $f(D)\lt0$ again have opposite signs, and $\alpha$ is the single sign change inside $\overline{{BD}}$. Bisection converges to $\alpha$.

Method & start	Reaches $\alpha$?	Reason
(a) Newton, $x=A$	No	$f'(A)=0$ (maximum) — step undefined
(b) Newton, $x=B$	No	Steps away from $\alpha$ (wrong side of the peak)
(c) Bisection, $\overline{{AD}}$	Yes	$f(A)\gt0,\ f(D)\lt0$ — brackets the root
(d) Bisection, $\overline{{BD}}$	Yes	$f(B)\gt0,\ f(D)\lt0$ — brackets the root

Concept & Theory

Topic. Open vs. bracketing root-finding methods: local convergence of Newton–Raphson vs. guaranteed convergence of bisection.

Key relations. Newton: $x_{{n+1}} = x_n - f(x_n)/f'(x_n)$ (quadratic convergence near a simple root, but fragile). Bisection: repeatedly halve $[a,b]$ with $f(a)f(b)\lt0$; the bracket guarantees a root by the Intermediate Value Theorem.

Why this works. Newton is only reliable when started in the root's basin of attraction with a non-zero derivative that points toward the root. A stationary point ($A$) breaks it outright, and starting on the far side of a hump ($B$) sends the tangent away from $\alpha$. Bisection asks only for a sign change, which both $\overline{{AD}}$ and $\overline{{BD}}$ provide, so it cannot fail here (though it converges only linearly).

Common pitfall. Assuming Newton always beats bisection. Speed is worthless without convergence; a good practical scheme brackets first (bisection) and switches to Newton once safely near the root.

Source. Chapra & Canale, Numerical Methods for Engineers, ch. 5–6 (bracketing methods and Newton–Raphson, pitfalls of open methods).

Question 6 of 7: Convergence of Newton's Method and Bisection

Question 6: Convergence of Newton's Method and Bisection (20 marks)