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

Question 6: Root-Finding — Newton, Fixed-Point, and Bisection (A: 9 marks; B: 7 marks; C: 4 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^3-26x^2+173x-325$, $x_0=3.0$. (B) $f(x)=\ln(x+2)-x^2+6x-5$, $x_0=1.0$. (C) $f(x)=2\cos(x/2)-x-1$, bracket $[0.80,0.84]$.

Find. (A) Three Newton iterates and, from the resulting root, the remaining two roots of the cubic. (B) A convergent fixed-point form and six iterates. (C) Four bisection iterates.

Approach. (A) Standard Newton update $x_{n+1}=x_n-f(x_n)/f'(x_n)$, then deflate the cubic by the found root and solve the resulting quadratic. (B) Test candidate rearrangements' derivatives at the root; pick the one with $|g'(x^\ast)|\lt1$. (C) Standard interval-halving with sign tracking.

1. (A) Newton's method, three iterations. $f'(x)=3x^2-52x+173$. $$x_0=3.0000000,\ f(x_0)=-13.0000000,\ f'(x_0)=44.0000000\ \Rightarrow\ x_1=3.2954545$$ $$x_1=3.2954545,\ f(x_1)=-1.4581964,\ f'(x_1)=34.2164256\ \Rightarrow\ x_2=3.3380714$$ $$x_2=3.3380714,\ f(x_2)=-0.0291881,\ f'(x_2)=32.8484493\ \Rightarrow\ \boxed{x_3=3.3389600}$$
2. Deflate the cubic. Dividing $x^3-26x^2+173x-325$ synthetically by $(x-3.3389600)$ gives the depressed quadratic $x^2+bx+c$ with $b=-26+3.3389600=-22.6610400$ and $c=173+3.3389600\,b=97.3389588$ (remainder $\approx-1.3\times10^{-5}$, confirming $x_3$ is an accurate root). Solving $x^2-22.6610400x+97.3389588=0$ by the quadratic formula, $$\boxed{x=16.9023231\ \text{and}\ x=5.7587170}$$
3. (B) Choose a convergent fixed-point form. Rearranging $\ln(x+2)-x^2+6x-5=0$ as $x=g(x)=\dfrac{x^2-\ln(x+2)+5}{6}$ gives $$g'(x)=\frac{2x-\frac{1}{x+2}}{6}$$ Near the root ($x^\ast\approx0.7605$), $g'(x^\ast)\approx0.193121$, and $|g'(x^\ast)|\lt1$, so this form converges (contraction mapping). By contrast, the alternative $x=\sqrt{\ln(x+2)+6x-5}$ has $g'(x^\ast)\approx4.183000\gt1$ at the same root and would diverge — it is rejected.
4. Iterate six times from $x_0=1.0$. $$x_0=1.0000000\to x_1=0.8168980\to x_2=0.7719477\to x_3=0.7627255$$ $$\to x_4=0.7609221\to x_5=0.7605730\to \boxed{x_6=0.7605055}$$ The iterates are converging monotonically toward the true root $\approx0.7604893$, consistent with the small $|g'(x^\ast)|\approx0.19$ (fast linear convergence).
5. (C) Bisection, four iterations. $f(\alpha)=f(0.80)=0.0421220\gt0$, $f(\beta)=f(0.84)=-0.0138221\lt0$ (root bracketed).

After four bisections, $\boxed{x\approx0.8325000}$, with the bracket narrowed to $[0.8300000,0.8325000]$ (width $0.0025$, $1/16$ of the original $0.04$).