Root-Finding — Bisection, Modified Newton, and Fixed-Point Iteration: 04-BS-5, December 2018, Q6

Question 6: Root-Finding — Bisection, Modified Newton, and Fixed-Point Iteration (A(a): 6 marks; A(b): 7 marks; B: 7 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) $f(x)=x^2+3x-9$, a sign change on $[1,2]$; the iterative correction formula shown (Halley's method, an extension of Newton's method using $f''$). (B) $g(x)=x^3-6x^2+9x-3$, with a root known to lie near $x_0=1.6$.

Find. (A)(a) The bisection approximation after 4 halvings. (A)(b) One Halley step from that result. (B) Six fixed-point iterates $x_1,\dots,x_6$ from $x_0=1.6$, using a rearrangement $x=F(x)$ that converges.

Approach. (A) Standard interval-halving, tracking the sign of $f$ at the midpoint; then a single Halley correction using $f,f',f''$ at the bisection result. (B) Rearrange the cubic so the $x^2$ term is isolated, giving $x=\sqrt{(x^3+9x-3)/6}$, and confirm $|F'(x)|\lt1$ near the target root before iterating (Kreyszig/Chapra's convergence criterion for fixed-point iteration).

(A)(a) Bisection, four steps. $f(1)=1+3-9=-5\lt0$, $f(2)=4+6-9=1\gt0$, so a root lies in $(1,2)$. $$\begin{array}{l} \text{Step 1: }m_1=1.5,\ f(1.5)=-2.25\lt0\Rightarrow\text{root in }(1.5,2)\\ \text{Step 2: }m_2=1.75,\ f(1.75)=-0.6875\lt0\Rightarrow\text{root in }(1.75,2)\\ \text{Step 3: }m_3=1.875,\ f(1.875)=0.140625\gt0\Rightarrow\text{root in }(1.75,1.875)\\ \text{Step 4: }m_4=1.8125,\ f(1.8125)=-0.27734375\lt0\Rightarrow\text{root in }(1.8125,1.875) \end{array}$$ $$\boxed{x\approx m_4=1.8125000}$$
(A)(b) One Halley step from $x_0=1.8125000$. With $f'(x)=2x+3$, $f''(x)=2$: $$f(x_0)=1.8125^2+3(1.8125)-9=-0.27734375,\quad f'(x_0)=2(1.8125)+3=6.625,\quad f''(x_0)=2$$ $$x_1=x_0-\frac{f(x_0)}{f'(x_0)-\dfrac{f(x_0)f''(x_0)}{2f'(x_0)}}=1.8125000-\frac{-0.27734375}{6.625-\dfrac{(-0.27734375)(2)}{2(6.625)}}$$ $$\boxed{x_1\approx1.8541003}$$ The exact root is $x=\dfrac{-3+\sqrt{45}}{2}=1.8541020$, so a single Halley (cubically-convergent) step from a coarse bisection estimate already lands within $1.6\times10^{-6}$ — illustrating why the hybrid bisection-then-higher-order-correction strategy is standard practice.
(B) Choose a convergent rearrangement. Isolating the $x^2$ term in $x^3-6x^2+9x-3=0$: $6x^2=x^3+9x-3\ \Rightarrow\ x^2=(x^3+9x-3)/6\ \Rightarrow$ $$\boxed{F(x)=\sqrt{\dfrac{x^3+9x-3}{6}}}$$ Near the target root ($\approx1.6527$), $F'(x)=\dfrac{3x^2+9}{12\sqrt{(x^3+9x-3)/6}}$ evaluates to $|F'|\approx0.867\lt1$, so the fixed-point map is a contraction there (convergent, though slowly, since $|F'|$ is close to $1$).
Iterate six times from $x_0=1.6$. $$\begin{array}{ll} x_1=F(1.6)=1.6070677 & x_2=F(x_1)=1.6131816\\ x_3=F(x_2)=1.6184718 & x_4=F(x_3)=1.6230503\\ x_5=F(x_4)=1.6270137 & x_6=F(x_5)=\boxed{1.6304453} \end{array}$$ The true root is $1.6527036$; after six iterations the error has shrunk from $0.0527$ (at $x_0$) to $0.0223$ (at $x_6$), consistent with linear convergence at ratio $|F'|\approx0.867$ — more iterations would be needed to reach 7-significant-figure accuracy, but the exam only asks for six.

Quantity	Result
Bisection result (4 steps)	$x\approx1.8125000$
Halley step result	$x\approx1.8541003$ (true root $1.8541020$)
Fixed-point rearrangement	$F(x)=\sqrt{(x^3+9x-3)/6}$, $\|F'(\text{root})\|\approx0.867$
Fixed-point result (6 iterations)	$x_6\approx1.6304453$ (true root $1.6527036$)

Topic: Bracketing (bisection) vs. open (Halley/Newton, fixed-point) root-finding methods, and their convergence orders.

Key relations: bisection halves the bracket every step (linear, guaranteed); Halley's method $x_{n+1}=x_n-\dfrac{f}{f'-\dfrac{ff''}{2f'}}$ is cubically convergent near a simple root; fixed-point iteration $x_{n+1}=F(x_n)$ converges linearly iff $|F'(x^*)|\lt1$ at the root $x^*$.

Why this works: bisection never fails to converge (given a sign change) but is slow, which is exactly why the exam pairs it with one fast Halley correction — a coarse-but-safe bracketing method supplies a good enough starting point for a high-order method to finish the job in a single step. For the cubic in (B), only the rearrangement that isolates the quadratic term happens to satisfy the contraction condition near the target root; other algebraically valid rearrangements of the same equation can have $|F'|\gt1$ and diverge, which is why the convergence criterion must be checked before iterating, not assumed.

Common pitfall: picking an $x=F(x)$ rearrangement without checking $|F'(x^*)|\lt1$ first (a plausible-looking rearrangement can diverge); losing sign-tracking discipline in bisection (updating the wrong endpoint); forgetting that Halley's method needs $f''$, not just $f'$, distinguishing it from plain Newton.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch. 19.2 (Solution of Equations by Iteration); Chapra & Canale, Numerical Methods for Engineers, 7th ed., Ch. 5–6.

Question 6 of 7: Root-Finding — Bisection, Modified Newton, and Fixed-Point Iteration

Question 6: Root-Finding — Bisection, Modified Newton, and Fixed-Point Iteration (A(a): 6 marks; A(b): 7 marks; B: 7 marks)