Root-Finding by Halley-Form Iteration and Fixed-Point Iteration: 04-BS-5, May 2013, Q6

Question 6: Root-Finding by Halley-Form Iteration and Fixed-Point Iteration (A) 10, (B) 10 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^5-16x^2-20$, initial guess $x_0=2.6$, and the stated iteration formula. (B) $F(x)=\ln(x+2)-x^2+7$, initial guess $x_0=2.95$.

Find. (A) $x_1,x_2$ to 7 digits. (B) $x_1,\dots,x_5$ to 7 digits.

Approach. (A) The given formula is algebraically Halley's method (multiply its numerator and denominator by $2f'$): $x_{i+1}=x_i-\dfrac{2f\,f'}{2f'^2-f\,f''}$; evaluate $f,f',f''$ and iterate twice. (B) Isolate the $x^2$ term to get a contracting $g(x)=\sqrt{\ln(x+2)+7}$ (the positive root, matching $x_0\approx2.95$), then iterate.

(A) Derivatives. $$f(x)=x^5-16x^2-20,\qquad f'(x)=5x^4-32x,\qquad f''(x)=20x^3-32$$
(A) First iteration from $x_0=2.6$. $$f(2.6)=-9.346240,\quad f'(2.6)=145.28800,\quad f''(2.6)=319.5200$$ $$x_1=2.6-\dfrac{-9.346240}{145.28800-\dfrac{(-9.346240)(319.5200)}{2(145.28800)}}=2.6-\dfrac{-9.346240}{155.5652}$$ $$\boxed{x_1=2.660079}$$
(A) Second iteration from $x_1$. $$f(x_1)=-0.0259611,\quad f'(x_1)=165.22787,\quad f''(x_1)=344.45556$$ $$x_2=x_1-\dfrac{-0.0259611}{165.22787-\dfrac{(-0.0259611)(344.45556)}{2(165.22787)}}=x_1-\dfrac{-0.0259611}{165.2549}$$ $$\boxed{x_2=2.660236}$$ (Check: $f(x_2)\approx-4\times10^{-10}$ — already at the root to 7-digit precision after two steps, reflecting Halley's cubic order of convergence.)
(B) Rearrange as a contracting fixed-point map. From $\ln(x+2)-x^2+7=0$, $$x^2=\ln(x+2)+7\ \Longrightarrow\ \boxed{x=g(x)=\sqrt{\ln(x+2)+7}}$$ (the positive square root, since the sought root is near $+2.95$; this isolation of the $x^2$ term keeps $|g'(x)|$ small near the root, unlike e.g. solving for $x$ inside the logarithm.)
(B) Iterate five times from $x_0=2.95$. $$x_1=\sqrt{\ln(4.95)+7}=\boxed{2.932471}$$ $$x_2=\sqrt{\ln(4.932471)+7}=\boxed{2.931866}$$ $$x_3=\boxed{2.931845},\qquad x_4=\boxed{2.931845},\qquad x_5=\boxed{2.931845}$$ The iterates settle to $x\approx2.931845$ by the fourth step (Check: $\ln(4.931845)-2.931845^2+7\approx-5\times10^{-9}$).

Quantity	Result
(A) $x_1$	$2.660079$
(A) $x_2$	$2.660236$
(B) $x_1,\dots,x_5$	$2.932471,\ 2.931866,\ 2.931845,\ 2.931845,\ 2.931845$
(B) converged root	$\approx2.931845$

Concept & Theory

Topic. Higher-order (Halley-type) root polishing and fixed-point (successive substitution) iteration.

Key relations. Halley's iteration $x_{i+1}=x_i-\dfrac{2ff'}{2f'^2-ff''}$ converges cubically; a fixed-point map $x=g(x)$ converges (linearly) near a root iff $|g'(\text{root})|\lt 1$.

Why this works. (A)'s given formula is Halley's method in disguise, using curvature ($f''$) to correct Newton's step — roughly tripling the number of correct digits per iteration, visible in how $x_2$ already satisfies $f(x_2)\approx0$ after only two steps. (B) succeeds because isolating $x^2$ (rather than, say, $x=e^{x^2-7}-2$) keeps $|g'(x)|\lt 1$ near the root.

Common pitfall. Rearranging a fixed-point equation the algebraically "obvious" way without checking $|g'(x_0)|\lt 1$ first — a different (equally valid-looking) rearrangement of the same equation can diverge even though the one chosen here converges in 3–4 iterations.

Source. Kreyszig, Advanced Engineering Mathematics, Ch. 19 (§19.2 Solution of Equations by Iteration).

Question 6 of 7: Root-Finding by Halley-Form Iteration and Fixed-Point Iteration

Question 6: Root-Finding by Halley-Form Iteration and Fixed-Point Iteration (A) 10, (B) 10 marks