Exercises — Newton-Raphson method for root finding

WHAT we do: apply the rule once. WHY: L1 just checks you can identify $f$, $f^{\prime }$, and plug in.

• $f(x)=x^2-5$, so $f^{\prime }(x)=2x$ (power rule from Derivatives — definition and rules).
• At $x_0=2$: $f(2)=4-5=-1$ (we are below the axis), $f^{\prime }(2)=4$ (slope rising). $x_1=2-\frac{-1}{4}=2+0.25=\mathrm{2.25.}$ Sanity: $\sqrt{5}\approx 2.2360$, so $2.25$ is closer than $2$. The height was negative, so we moved right (added) — the sign took care of the direction automatically.

WHY this matters: before iterating you must differentiate correctly; a wrong $f^{\prime }$ ruins everything.

• $\frac{d}{dx}\cos x=-\sin x$ and $\frac{d}{dx}(-2x)=-2$, so $f^{\prime }(x)=-\sin x-2$. $x_{n+1}=x_n-\frac{\cos x_n-2x_n}{-\sin x_n-2}.$

With the wrong plus sign: $x_1=2+\frac{-1}{4}=1.75$. But $\sqrt{5}\approx 2.236$, so we jumped from distance $0.236$ to distance $0.486$ — further away. The correct minus sign gave $2.25$ (distance $0.014$). The subtraction is what points you toward the root.

Set-up: $f^{\prime }(x)=3x^2$. Substituting straight into the update rule, $x_{n+1}=x_n-\frac{x_n^3-7}{3x_n^2}.$ WHY rearrange? Splitting the fraction turns "old guess minus a correction" into a self-contained recipe you can evaluate in one pass, and it exposes the structure of the step. Distribute the denominator over the numerator: $x_n-\frac{x_n^3}{3x_n^2}+\frac{7}{3x_n^2}=x_n-\frac{x_n}{3}+\frac{7}{3x_n^2}=\frac{2x_n}{3}+\frac{7}{3x_n^2}.$ What the form tells us: $\frac{2x_n}{3}$ keeps most of the old guess, and $\frac{7}{3x_n^2}$ is a pull toward the true root — exactly the "weighted average" flavour Newton takes on for root-finding.

• $x_0=2$: $x_1=\frac{4}{3}+\frac{7}{12}=1.33333+0.58333=\mathrm{1.91667.}$
• $x_1=1.91667$: $x_1^3=7.0408$, so $x_2=1.91667-\frac{7.0408-7}{3(1.91667{)}^2}$ $=1.91667-\frac{0.0408}{11.0208}=1.91667-0.003705=\mathrm{1.91293.}$ Check: $\sqrt[3]{7}=1.912931\dots$ — already 6 correct digits after two steps. Quadratic speed! With $\epsilon =10^{-6}$ we would stop at the very next step, since $|x_3-x_2|$ falls below it.

$f^{\prime }(x)=2x-3$.

• $x_0=3$: $f=9-9+2=2$, $f^{\prime }=3$. $x_1=3-\frac{2}{3}=\mathrm{2.33333.}$
• $x_1=2.33333$: $f=5.44444-7+2=0.44444$, $f^{\prime }=1.66667$. $x_2=2.33333-0.26667=\mathrm{2.06667.}$ The guesses fall toward $x=2$. WHY that root and not $x=1$? Newton is local: starting to the right of both roots, the tangent points you to the nearer root, which is $2$.

WHY this $f$: its root is $x=1/a$, and its derivative avoids re-dividing.

• $f(x)=x^{-1}-a$, $f^{\prime }(x)=-x^{-2}$. $x_{n+1}=x_n-\frac{x_n^{-1}-a}{-x_n^{-2}}=x_n+x_n^2\left(\frac{1}{x_n}-a\right)=x_n(2-a{x}_n).$ Only multiplications — beautiful.
• $a=3$, $x_0=0.3$: $x_1=0.3(2-0.9)=0.3\times 1.1=\mathrm{0.33.}$
• $x_1=0.33$: $x_2=0.33(2-0.99)=0.33\times 1.01=\mathrm{0.3333.}$ Check: $1/3=0.33333\dots$ — converging with no division used.

Update: $x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}$. With $\sqrt{2}=1.4142136$:

• $x_0=1.5$, $e_0=\mathrm{0.0857864.}$
• $x_1=0.75+0.6666667=1.4166667$, $e_1=\mathrm{0.0024531.}$
• $x_2=0.7083333+0.7058824=1.4142157$, $e_2=\mathrm{0.0000021.}$ Analysis: the theory says $e_{n+1}\approx \frac{f^{\prime \prime }}{2f^{\prime }}{e}_n^2=\frac{1}{2\sqrt{2}}{e}_n^2\approx 0.3536e_n^2$. Check: $0.3536\times e_0^2=0.3536\times 0.007359=0.002602$ vs actual $e_1=0.002453$ ✓. And $0.3536\times e_1^2=0.3536\times 6.018\times 10^{-6}=2.13\times 10^{-6}$ vs $e_2=2.1\times 10^{-6}$ ✓. The error genuinely squares — this is Taylor series convergence in the flesh.

$f^{\prime }(x)=3x^2-2$; note $f^{\prime }=0$ at $x=\pm \sqrt{2/3}\approx \pm 0.8165$. Our start $0.9$ sits just past that flat spot.

• $x_0=0.9$: $f=0.729-1.8+2=0.929$, $f^{\prime }=2.43-2=0.43$ (tiny!). $x_1=0.9-\frac{0.929}{0.43}=0.9-2.161=-\mathrm{1.261.}$ What it looks like (see figure below): a nearly-horizontal tangent barely slopes down, so it hits the axis far away — the guess is hurled from $0.9$ to $-1.26$. This is the "small $f^{\prime }$" danger made visible.
• $x_1=-1.261$: $f=-2.005+2.522+2=2.517$, $f^{\prime }=4.770-2=2.770$. $x_2=-1.261-0.9086=-\mathrm{2.170.}$ It now homes in on the real root near $-1.77$.

$f^{\prime }(x)=2x-4=2(x-2)$. The update simplifies beautifully: $x_{n+1}=x_n-\frac{(x_n-2{)}^2}{2(x_n-2)}=x_n-\frac{x_n-2}{2}=\frac{x_n+2}{2}.$ So the error $e_n=x_n-2$ obeys $e_{n+1}=\frac{e_n}{2}$ — linear, not quadratic.

• $x_0=3$ ($e_0=1$) → $x_1=2.5$ ($e_1=0.5$) → $x_2=2.25$ ($e_2=0.25$) → $x_3=2.125$. WHY: the quadratic-convergence proof needs $f^{\prime }(\text{root})\ne 0$. At a double root the slope vanishes at the target, the "$f/f^{\prime }$" ratio behaves like $0/0$, and you lose the squaring bonus.

Turn "intersection" into "root": two curves meet where their difference is zero, so let $f(x)=e^{-x}-x$. Then $f^{\prime }(x)=-e^{-x}-1$. $x_{n+1}=x_n-\frac{e^{-x_n}-x_n}{-e^{-x_n}-1}.$

• $x_0=0.5$: $e^{-0.5}=0.606531$, $f=0.106531$, $f^{\prime }=-1.606531$. $x_1=0.5+0.066311=\mathrm{0.566311.}$
• $x_1=0.566311$: $e^{-0.566311}=0.567560$, $f=0.001249$, $f^{\prime }=-1.567560$. $x_2=0.566311+0.000797=\mathrm{0.567108.}$ Not done yet: $|x_2-x_1|=0.000797>10^{-6}$, so the tolerance test fails — we must take another step.
• $x_2=0.567108$: $e^{-0.567108}=0.567107$, $f=-1.0\times 10^{-6}$, $f^{\prime }=-1.567107$. $x_3=0.567108-0.00000064=\mathrm{0.567143.}$ Now $|x_3-x_2|=6.4\times 10^{-7}<10^{-6}$, so we stop at $x\approx 0.567143$. This special number (the value $w$ solving $w{e}^w=1$) is called the omega constant; the two curves cross exactly once, there.

Idea: $\ln 2$ is the number $x$ with $e^x=2$, i.e. the root of $f(x)=e^x-2$. Then $f^{\prime }(x)=e^x$. $x_{n+1}=x_n-\frac{e^{x_n}-2}{e^{x_n}}=x_n-1+2e^{-x_n}.$

• $x_0=0.7$: $e^{-0.7}=0.496585$. $x_1=0.7-1+0.993170=\mathrm{0.693170.}$
• $x_1=0.693170$: $e^{-0.693170}=0.499970$. $x_2=0.693170-1+0.999940=\mathrm{0.693110.}$ Not done yet: $|x_2-x_1|=0.000060>10^{-6}$, so we continue.
• $x_2=0.693110$: $e^{-0.693110}=0.500000$. $x_3=0.693110-1+1.000000=\mathrm{0.693147.}$ Here $|x_3-x_2|=3.7\times 10^{-5}$ is still $>10^{-6}$ — keep going.
• $x_3=0.693147$: $e^{-0.693147}=0.5000000$. $x_4=0.693147-1+1.0000000=\mathrm{0.6931472.}$ Now $|x_4-x_3|<10^{-6}$, so we stop at $x\approx 0.6931472$. Check: $\ln 2=0.6931472\dots$ — matched to 7 digits. Any $f$ with the right root works; a clean $f^{\prime }$ just makes the arithmetic pleasant.

Rewrite the update as a single function: $g(x)=x-\frac{f(x)}{f^{\prime }(x)}.$ A root $r$ satisfies $f(r)=0$, so $g(r)=r-0=r$ — it is a fixed point.

Now differentiate $g$, step by step. The term $x$ differentiates to $1$, so we only need $\frac{d}{dx}\left[\frac{f(x)}{f^{\prime }(x)}\right]$. This is a quotient, so we use the quotient rule ${\left(\frac{u}{v}\right)}^{\prime }=\frac{u^{\prime }v-u{v}^{\prime }}{v^2}$ from Derivatives — definition and rules, with $u=f(x)$ and $v=f^{\prime }(x)$:

• $u^{\prime }=f^{\prime }(x)$ (derivative of $f$),
• $v^{\prime }=f^{\prime \prime }(x)$ (derivative of $f^{\prime }$ is the second derivative),
• $v^2=f^{\prime }(x{)}^2$.

Putting the pieces in:

Definitions first: let $e_n=x_n-r$ be the current error and $e_{n+1}=x_{n+1}-r$ the next one; $r$ is the true root, so $f(r)=0$.

Step 1 — Taylor-expand $f$ about $x_n$, evaluated at the true root $r$ (from Taylor series): $0=f(r)=f(x_n)+f^{\prime }(x_n)(r-x_n)+\frac{1}{2}{f}^{\prime \prime }(\xi )(r-x_n{)}^2.$ WHY: we know $f(r)=0$ exactly; Taylor's theorem makes the remainder term with $\xi$ (some point between $x_n$ and $r$) exact, not approximate — that is what lets us pin down the error precisely.

Step 2 — substitute $r-x_n=-e_n$ and divide the whole line by $f^{\prime }(x_n)$ (allowed since a simple root has $f^{\prime }(x_n)\ne 0$ nearby): $0=\frac{f(x_n)}{f^{\prime }(x_n)}-e_n+\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2.$ WHY divide by $f^{\prime }(x_n)$: it manufactures the exact term $\frac{f(x_n)}{f^{\prime }(x_n)}$ that appears in the Newton step, so we can trade it for a difference of iterates in the next line.

Step 3 — recognise the Newton step and convert to errors. The update $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$ rearranges to $\frac{f(x_n)}{f^{\prime }(x_n)}=x_n-x_{n+1}$. Using $e_n=x_n-r$ and $e_{n+1}=x_{n+1}-r$, $x_n-x_{n+1}=(x_n-r)-(x_{n+1}-r)=e_n-e_{n+1}.$ Substitute this for $\frac{f(x_n)}{f^{\prime }(x_n)}$ in Step 2: $0=(e_n-e_{n+1})-e_n+\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2.$ WHY: every term is now expressed in the errors we care about, so the algebra collapses cleanly.

Step 4 — cancel and solve for $e_{n+1}$. The $e_n$ and $-e_n$ cancel: $0=-e_{n+1}+\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2\Rightarrow \boxed{e_{n+1}=\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2.}$ The next error is a constant times the square of the current error — quadratic convergence, proven. Since $\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}$ stays bounded near a simple root, halving the error once roughly doubles the correct-digit count on the following step.

The problem: Newton is fast but unbracketed — a small $f^{\prime }$ or bad guess can hurl $x_{n+1}$ outside any region of interest (recall L3.2 and the cycling example in the parent note). The fix — keep a bracket $[a,b]$ with $f(a)f(b)<0$ (a sign change guarantees a root inside, by the intermediate value idea behind Bisection method). Each iteration:

1. Propose the Newton step $x_{\text{new}}=x_n-f(x_n)/f^{\prime }(x_n)$.
2. Reject test (precise): reject the Newton step and use bisection instead if either
   • $x_{\text{new}}\notin [a,b]$ (the step left the bracket), or
   • $|f^{\prime }(x_n)|<\delta$ for a fixed small slope threshold, e.g. $\delta =10^{-8}$ (the tangent is too flat to trust). A common alternative test is to reject if the step fails to shrink the bracket by at least half, i.e. $|x_{\text{new}}-x_n|>\frac{1}{2}|b-a|$.
   When rejected, take the guaranteed-safe bisection step $x_{\text{new}}=\frac{a+b}{2}$ (always inside).
3. Update the bracket: replace whichever of $a,b$ shares $f$'s sign with $x_{\text{new}}$. WHY it works: you get Newton's quadratic speed whenever the guess is good, and bisection's guaranteed (if slow) progress whenever Newton misbehaves — never worse than halving the bracket.

$f^{\prime }(x)=\frac{1}{1+x^2}$, so the update is $x_{n+1}=x_n-(1+x_n^2)\arctan x_n.$ WHY this can explode: for large $x$, $\arctan x\to \frac{\pi }{2}$ while $(1+x^2)$ grows, so the subtracted term overshoots massively — $|x_{n+1}|>|x_n|$, spiralling outward. Critical point: the boundary between converge and diverge is where the step exactly flips the sign with equal magnitude, $x_{n+1}=-x_n$: $-x=x-(1+x^2)\arctan x\Rightarrow 2x=(1+x^2)\arctan x.$ Solving numerically gives $x^{\ast }\approx 1.3917$. Start with $|x_0|<1.3917$ and Newton converges to $0$; start with $|x_0|>1.3917$ and it diverges (each step is bigger than the last). Exactly at $x^{\ast }$ it cycles $x^{\ast }\to -x^{\ast }\to x^{\ast }\to \cdots$ forever. The figure below shows the narrow red band of good starting guesses.