Root finding by bisection then Halley's iteration: 04-BS-5, May 2015, Q6

Question 6: Root finding by bisection then Halley's iteration (a) 8 marks; (b) 12 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. $f(x)=6^x-30x+10$; a root lies in $[2.0,3.0]$ since $f(2)=-14\lt0$ and $f(3)=136\gt0$.

Find. (a) bisect 3 times (5 sig. figs.); (b) apply the given second-order (Halley) iteration twice from (a)'s result (7 sig. figs.).

Approach. Standard bisection (halve the sign-changing bracket) followed by Halley's method, which uses $f,f',f''$ for cubic convergence.

Bisection 1. Midpoint $x_1=(2.0+3.0)/2=2.5000$: $f(2.5)=6^{2.5}-75+10=+23.182\gt0\ \Rightarrow$ root in $[2.0,2.5]$.
Bisection 2. $x_2=(2.0+2.5)/2=2.2500$: $f(2.25)=6^{2.25}-67.5+10=-1.1570\lt0\ \Rightarrow$ root in $[2.25,2.5]$.
Bisection 3. $x_3=(2.25+2.5)/2=2.3750$: $f(2.375)=6^{2.375}-71.25+10=+9.2370\gt0\ \Rightarrow$ root in $[2.25,2.375]$. $$\boxed{x\approx2.3750\quad\text{(after 3 bisections; bracket }[2.25,2.375]\text{)}}$$
Halley iteration 1 (part b), from $x_0=2.375$. $f(x_0)=9.23703$, $f'(x_0)=6^{x_0}\ln6-30=96.2958$, $f''(x_0)=6^{x_0}(\ln6)^2=226.2917$: $$x_1=2.375-\dfrac{9.23703}{96.2958-\dfrac{(9.23703)(226.2917)}{2(96.2958)}}=2.266892$$
Halley iteration 2. $f(x_1)=0.067640$, $f'(x_1)=74.05535$, $f''(x_1)=186.44215$: $$\boxed{x_2=2.266892-\dfrac{0.067640}{74.05535-\dfrac{(0.067640)(186.44215)}{2(74.05535)}}=2.265977}$$ (the true root is $2.2659774\ldots$, in agreement with all 7 quoted digits.)

Final results — Question 6
Stage	Approximation
Bisection $x_1,x_2,x_3$	$2.5000,\ 2.2500,\ 2.3750$
Halley iteration 1	$2.266892$
Halley iteration 2	$2.265977$

Topic: Bracketing (bisection) followed by a higher-order open method (Halley's iteration).

Key relations: bisection halves $[a,b]$ each step ($\sim1$ bit of accuracy per iteration, always converges); Halley's method, $x_{n+1}=x_n-\dfrac{f}{f'-ff''/(2f')}$, is cubically convergent near a simple root — markedly faster than plain Newton once close enough to start.

Why this works: bisection guarantees a shrinking bracket by the Intermediate Value Theorem regardless of starting quality, making it ideal for the first coarse steps; switching to Halley's method once inside a small bracket exploits local smoothness ($f\in C^2$) for much faster convergence, tripling the number of correct digits each iteration instead of doubling (Newton) or adding one bit (bisection).

Common pitfall: carrying too few significant digits partway through bisection (compounding rounding error before switching methods); mixing up $f^{(1)}$ and $f^{(2)}$ in the denominator of the Halley formula.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., §19.2 (Solution of Equations by Iteration).

Question 6 of 7: Root finding by bisection then Halley's iteration

Question 6: Root finding by bisection then Halley's iteration (a) 8 marks; (b) 12 marks