Bisection, Newton–Raphson and Fixed-Point Iteration: 04-BS-5, Undated paper, Q6

Question 6: Bisection, Newton–Raphson and Fixed-Point Iteration (20 marks: (a) 6, (b) 7, (c) 7)

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. The transcendental equation $f(x)=5^{x}+3x-10=0$ with a single real root bracketed by $a=1$ and $b=2$, and the two rearrangements into fixed-point form quoted in part (c).

Given data
Quantity	Value
Equation	$f(x)=5^{x}+3x-10=0$
Derivative	$f'(x)=5^{x}\ln 5 + 3$
Initial bracket	$a=1$, $b=2$
End values	$f(1)=-2$, $f(2)=21$
Fixed-point form (i)	$g(x)=\ln(10-3x)/\ln 5$
Fixed-point form (ii)	$g(x)=(10-5^{x})/3$

Find. Four bisection steps; two Newton–Raphson steps started from the bisection result; five fixed-point iterates of form (i) from $x_{0}=1$; and a justification of why form (i) converges.

Check: reading of the printed form (i). The only algebraically consistent reading is the one adopted here: taking base-5 logarithms of $5^{x}=10-3x$ gives $x\ln 5 = \ln(10-3x)$, i.e. $x = \ln(10-3x)/\ln 5$, which is the natural partner of the clearly printed form (ii) $x=(10-5^{x})/3$ and is also the form that actually converges — as the question asserts it does.

$f(x)=5^{x}+3x-10$ on the given bracket. The end values $f(1)=-2$ and $f(2)=21$ have opposite signs and $f$ is strictly increasing, so the root near $1.16383$ is the only one.

Approach. Establish that the root is unique from the sign of $f'$, then halve the bracket four times; feed the last midpoint into Newton–Raphson twice; finally iterate form (i) five times and test convergence with the contraction criterion $|g'(x^{*})| \lt 1$.

Confirm the bracket and the uniqueness of the root. $f(1)=5+3-10=-2$ and $f(2)=25+6-10=21$ have opposite signs, so a root lies in $(1,2)$ by the intermediate value theorem. Moreover $f'(x)=5^{x}\ln 5 + 3 \gt 0$ for every real $x$, so $f$ is strictly increasing and the root is unique — which is exactly what the question states.

Four bisection steps (part a). Each step evaluates $f$ at the midpoint and keeps the half-interval across which the sign changes:

Bisection on $[1,2]$
Step	Bracket	Midpoint $m$	$f(m)$	Sign	New bracket
$1$	$[1,\;2]$	$1.500000$	$+5.680340$	$+$	$[1,\;1.5]$
$2$	$[1,\;1.5]$	$1.250000$	$+1.226744$	$+$	$[1,\;1.25]$
$3$	$[1,\;1.25]$	$1.125000$	$-0.510777$	$-$	$[1.125,\;1.25]$
$4$	$[1.125,\;1.25]$	$1.187500$	$+0.323748$	$+$	$[1.125,\;1.1875]$

After four halvings the answer is the fourth midpoint, $$\boxed{\;x \approx 1.1875,\qquad \text{root} \in [1.125,\;1.1875]\;}$$ with a guaranteed error no worse than the remaining bracket width $0.0625$.

First Newton–Raphson step (part b). With $x_{0}=1.1875$, $f(x_{0}) = 0.3237480$ and $f'(x_{0}) = 5^{1.1875}\ln 5 + 3 = 13.881809$, $$x_{1} = x_{0} - \frac{f(x_{0})}{f'(x_{0})} = 1.1875 - \frac{0.3237480}{13.881809} = 1.1641782 .$$
Second Newton–Raphson step. Now $f(x_{1}) = 0.0047038$ and $f'(x_{1}) = 13.480932$, so $$x_{2} = 1.1641782 - \frac{0.0047038}{13.480932} = \boxed{\;1.1638293\;}$$ Two Newton steps have taken the residual from $3.2\times10^{-1}$ to $4.7\times10^{-3}$ and then to about $4\times10^{-6}$: the error is squaring at each step, which is the quadratic convergence Newton–Raphson delivers near a simple root. Continued iteration settles on $x^{*}=1.1638292$.

Five fixed-point iterations of form (i) (part c). With $g(x)=\ln(10-3x)/\ln 5$ and $x_{0}=1$, so that $g(1)=\ln 7/\ln 5$:

Fixed-point iteration $x_{k+1}=\ln(10-3x_{k})/\ln 5$
$k$	$x_{k}$	$10-3x_{k}$	$x_{k+1}$
$0$	$1.000000$	$7.000000$	$1.209062$
$1$	$1.209062$	$6.372814$	$1.150738$
$2$	$1.150738$	$6.547786$	$1.167567$
$3$	$1.167567$	$6.497299$	$1.162758$
$4$	$1.162758$	$6.511726$	$1.164136$

The fifth iterate is $$\boxed{\;x_{5} \approx 1.164136\;}$$ already within $3\times10^{-4}$ of the Newton value. The iterates alternate about the root, which is the signature of a negative derivative of $g$.

Explain the convergence. Differentiating form (i), $$g'(x) = \frac{1}{\ln 5}\cdot\frac{-3}{10-3x} \quad\Longrightarrow\quad \big|g'(x^{*})\big| = \frac{3}{\ln 5\,\big(10-3x^{*}\big)} = \frac{3}{1.60944 \times 6.50851} = 0.2864 .$$ Since $|g'| \approx 0.29 \lt 1$ throughout a neighbourhood of the root, $g$ is a contraction there and the fixed-point theorem guarantees convergence from any starting value in that neighbourhood, with the error shrinking by roughly a factor of $0.29$ per step (linear convergence). The negative sign explains the alternation. By contrast form (ii) has $g'(x) = -5^{x}\ln 5/3$, so $|g'(x^{*})| = 3.4917 \gt 1$: that arrangement is expansive at the root and the iteration diverges, which is why the question directs the candidate to form (i).

Final results — Question 6
Quantity	Result
(a) Bisection midpoints	$1.500000$, $1.250000$, $1.125000$, $1.187500$
(a) Answer after four bisections	$x \approx 1.1875$, root in $[1.125,\;1.1875]$
(b) Newton iterate $x_{1}$	$1.1641782$
(b) Newton iterate $x_{2}$	$1.1638293$
(c) Fixed-point iterates $x_{1}$–$x_{5}$	$1.209062$, $1.150738$, $1.167567$, $1.162758$, $1.164136$
(c) $\|g'\|$ at the root, form (i) / form (ii)	$0.2864$ (converges) / $3.4917$ (diverges)
Converged root	$x^{*} = 1.1638292$

Topic. Three classical root-finding schemes for a single nonlinear equation, and the criterion that decides whether a fixed-point rearrangement converges.

Key relations. Bisection error bound $|x_{n}-x^{*}| \le (b-a)/2^{n}$; the Newton–Raphson step $x_{n+1}=x_{n}-f(x_{n})/f'(x_{n})$; the fixed-point iteration $x_{n+1}=g(x_{n})$ with the contraction condition $|g'(x)| \le K \lt 1$ near the root.

Why this works. The three methods trade robustness against speed. Bisection needs only a sign change and cannot fail, but it buys exactly one bit per evaluation — four steps shrink a unit bracket to $0.0625$ and no further. Newton–Raphson replaces the curve by its tangent, so the error obeys $e_{n+1} \approx \tfrac{f''}{2f'}e_{n}^{2}$ and doubles the number of correct digits each step, which is why two steps from a mediocre start already give seven figures. Fixed-point iteration converges only if the map contracts distances, and $|g'|$ is precisely the local contraction factor: the same equation rearranged two ways gives $0.29$ one way and $3.49$ the other, so one arrangement converges linearly and the other flies apart. Using bisection to supply Newton with a good start, as this question does, is the standard hybrid strategy.

Common pitfall. Reporting the midpoint of the final bracket ($1.15625$) as the answer to four bisections instead of the fourth midpoint actually computed ($1.1875$); and rounding intermediate Newton values to three or four figures, which throws away exactly the digits the quadratic convergence is generating — hence the question's explicit instruction to carry several digits in part (b).

Source. Kreyszig, Advanced Engineering Mathematics, 10th ed., §19.2 (solution of equations by iteration: fixed-point, Newton, bisection); Burden and Faires, Numerical Analysis, 9th ed., §§2.1–2.3.

Question 6 of 7: Bisection, Newton–Raphson and Fixed-Point Iteration

Question 6: Bisection, Newton–Raphson and Fixed-Point Iteration (20 marks: (a) 6, (b) 7, (c) 7)