Newton's Method

Set-up. $f(x)=x^2-5$ is a polynomial, so it is differentiable everywhere, and $f'(x)=2x$, which is non-zero for every $x\ne0$. Since $f(2)=-1<0$ and $f(3)=4>0$, the IVT guarantees a root in $(2,3)$; $x_0=2$ is a legitimate starting point.

Simplify the iteration.

$x_{n+1}=x_n-\frac{x_n^2-5}{2x_n}=\frac{2x_n^2-\left(x_n^2-5\right)}{2x_n}=\frac{x_n^2+5}{2x_n}=\frac{1}{2}\left(x_n+\frac{5}{x_n}\right).$

Iterate.

x_1&=\frac12\left(2+\frac{5}{2}\right)=\frac12\left(2+2.5\right)=\frac{9}{4}=2.2500000000\\ x_2&=\frac12\left(2.25+\frac{5}{2.25}\right)=\frac12\left(2.25+2.2222222222\right)=\frac{161}{72}=2.2361111111\\ x_3&=\frac12\left(2.2361111111+\frac{5}{2.2361111111}\right)=\frac12\left(2.2361111111+2.2360248447\right)=\frac{51841}{23184}=2.2360679779 \end{aligned}$$ **Check.** $\sqrt5=2.2360679775$, so the errors are $$e_1=1.39\times10^{-2},\qquad e_2=4.31\times10^{-5},\qquad e_3=4.16\times10^{-10}.$$ Independent verification: $x_3^2=\left(\frac{51841}{23184}\right)^2=5.0000000019$, which is $5$ to $8$ decimal places, confirming $x_3$ is right. **Answer:** $x_1=2.25$, $x_2=2.2361111111$, $x_3=2.2360679779$. With $e_3=4.16\times10^{-10}$ the three steps have nailed $8$ decimals: $\sqrt5\approx2.23606798$. (Do *not* advertise $2.236067978$ as the $9$-decimal value: $\sqrt5=2.23606797749\ldots$ rounds to $2.236067977$ at $9$ places, and an error of $4\times10^{-10}$ is not yet enough to settle that digit.)

Set-up. $f(x)=x^3-7$, $f'(x)=3x^2$. $f'$ vanishes only at $x=0$, and our iterates stay near $2$, so every step is defined. ($f(1)=-6<0$, $f(2)=1>0$, so by the IVT there is a root in $(1,2)$; also $f'>0$ for $x\ne0$, so that real root is unique.)

Simplify.

$x_{n+1}=x_n-\frac{x_n^3-7}{3x_n^2}=\frac{3x_n^3-x_n^3+7}{3x_n^2}=\frac{2x_n^3+7}{3x_n^2}=\frac{2}{3}x_n+\frac{7}{3x_n^2}.$

Iterate from $x_0=2$.

x_1&=\frac{2(8)+7}{3(4)}=\frac{23}{12}=1.9166666667\\ x_2&=\frac{2\left(\frac{23}{12}\right)^3+7}{3\left(\frac{23}{12}\right)^2} =\frac{2(7.0410879630)+7}{3(3.6736111111)}=\frac{21.0821759259}{11.0208333333}=1.9129384583\\ x_3&=\frac{2(7.0000798705)+7}{3(3.6593335453)}=1.9129311828 \end{aligned}$$ (For $x_2$ the intermediate values are $\left(\frac{23}{12}\right)^2=\frac{529}{144}=3.6736111111$ and $\left(\frac{23}{12}\right)^3=\frac{12167}{1728}=7.0410879630$.) **Accuracy.** The true value is $7^{1/3}=1.9129311828$ (more precisely $1.91293118277239$). Errors: $$|x_1-r|=3.74\times10^{-3},\qquad |x_2-r|=7.28\times10^{-6},\qquad |x_3-r|=2.8\times10^{-11}.$$ Measuring correct digits by $-\log_{10}|x_n-r|$, that is $2.4\to5.1\to10.6$: the count doubles each step, which is exactly quadratic convergence. Independent check: $1.9129311828^3=7.000000000$ to $9$ decimal places. **Answer:** $x_1=1.9166666667$, $x_2=1.9129384583$, $x_3=1.9129311828$; $7^{1/3}\approx1.9129311828$.

(a) Assume $f$ is differentiable at $x_n$. The tangent line to $y=f(x)$ at the point $\left(x_n,f(x_n)\right)$ has slope $f'(x_n)$, so its equation is

$L(x)=f(x_n)+f'(x_n)\left(x-x_n\right).$

Newton's idea: instead of solving $f(x)=0$ (hard), solve $L(x)=0$ (easy) and call the answer $x_{n+1}$:

f(x_n)+f'(x_n)\left(x_{n+1}-x_n\right)&=0\\ f'(x_n)\left(x_{n+1}-x_n\right)&=-f(x_n)\\ x_{n+1}-x_n&=-\frac{f(x_n)}{f'(x_n)}\\ x_{n+1}&=x_n-\frac{f(x_n)}{f'(x_n)}. \end{aligned}$$ The division in the third line is exactly where the hypothesis is used. **(b)** We need $f'(x_n)\ne0$ at every iterate (and $f$ differentiable there). Geometrically, if $f'(x_n)=0$ the tangent line at $x_n$ is **horizontal**: it is either the $x$-axis itself or a line parallel to it, so it has no unique $x$-intercept and $x_{n+1}$ is undefined. Concretely, $f(x)=x^2-1$ with $x_0=0$ gives $f'(0)=0$ and the method stops immediately. Even $f'(x_n)$ merely *small* is dangerous: the near-horizontal tangent meets the axis very far away, so $x_{n+1}$ is thrown a long distance from $x_n$. **(c)** With $f(x)=mx+b$ we have $f'(x)=m\ne0$ for all $x$, so from any $x_0$, $$x_1=x_0-\frac{mx_0+b}{m}=x_0-x_0-\frac{b}{m}=-\frac{b}{m},$$ which is exactly the root of $mx+b=0$. Every further step reproduces it, since $f(-b/m)=0$. **Interpretation.** Newton's method is *exact on linear functions*, and for a general $f$ each step is exact on the tangent line — the best linear model of $f$ at $x_n$. The whole error of a step therefore comes from the gap between $f$ and its linear approximation, which by Taylor's theorem is of size $\frac12 f''(\xi)(x-x_n)^2$. That quadratic-in-the-step error is precisely the source of the quadratic convergence rate.

(a) $f$ is a polynomial, hence continuous on $[0,1]$. $f(0)=0+0-1=-1<0$ and $f(1)=1+1-1=1>0$. The values have opposite signs, so by the Intermediate Value Theorem there is $c\in(0,1)$ with $f(c)=0$.

Uniqueness: $f'(x)=3x^2+1\ge 1>0$ for all real $x$, so $f$ is strictly increasing on all of $(-\infty,\infty)$ and can cross zero at most once. Hence exactly one real root, and it lies in $(0,1)$.

(b) Bisection.

• Midpoint $0.5$: $f(0.5)=0.125+0.5-1=-0.375<0$. Same sign as $f(0)$, so the root is in $(0.5,1)$.
• Midpoint $0.75$: $f(0.75)=0.421875+0.75-1=0.171875>0$. Same sign as $f(1)$, so the root is in $(0.5,0.75)$.

Take $x_0=\dfrac{0.5+0.75}{2}=0.625$.

(c) Newton. $x_{n+1}=x_n-\dfrac{x_n^3+x_n-1}{3x_n^2+1}$.

Step 1: $f(0.625)=0.244140625+0.625-1=-0.130859375$; $f'(0.625)=3(0.390625)+1=2.171875$. $x_1=0.625-\frac{-0.130859375}{2.171875}=0.625+0.0602517986=0.6852517986.$

Step 2: $x_1^2=0.46957002743$, $x_1^3=0.32177370585$, so $f(x_1)=0.32177370585+0.68525179856-1=0.00702550441$ and $f'(x_1)=3(0.46957002743)+1=2.40871008229$. $x_2=0.6852517986-\frac{0.0070255044}{2.4087100823}=0.6852517986-0.0029167082=0.6823350904.$

Step 3: $x_2^2=0.46558117556$, $f(x_2)=0.0000174639$, $f'(x_2)=3(0.46558117556)+1=2.39674352668$. $x_3=0.6823350904-\frac{0.0000174639}{2.3967435267}=0.6823350904-0.0000072865=0.6823278039.$

The true root is $r=0.6823278038$ (to $10$ d.p.). Errors: $2.92\times10^{-3}$, $7.29\times10^{-6}$, $4.5\times10^{-11}$ — quadratic. Independent check: $0.6823278038^3+0.6823278038-1=-6.7\times10^{-11}$, essentially zero.

(d) After $n$ bisections the bracket $[0,1]$ has length $2^{-n}$. To match an error of about $10^{-10}$ we need $2^{-n}<10^{-10}$, i.e. $2^{n}>10^{10}$. Since $2^{33}=8.59\times10^{9}$ and $2^{34}=1.72\times10^{10}$, we need $n=34$ bisections, versus the $3$ Newton steps above (plus the two cheap bisections that produced $x_0$). That is the trade-off: bisection is guaranteed but linear; Newton is quadratic but needs a decent start — so bracket first, then switch.

(a) $f(x)=x^{-1}-a$ on $x\ne0$, so $f'(x)=-x^{-2}=-\dfrac{1}{x^2}$, which is never zero. Then

$x_{n+1}=x_n-\frac{\frac{1}{x_n}-a}{-\frac{1}{x_n^{2}}}=x_n+x_n^{2}\left(\frac{1}{x_n}-a\right)=x_n+x_n-a x_n^{2}=x_n\left(2-a x_n\right).$

Only multiplications and one subtraction appear — this is how hardware computes reciprocals (and hence divisions).

(b) Let $e_n=x_n-\dfrac1a$, so $x_n=e_n+\dfrac1a$. Then

x_{n+1}-\frac1a&=2x_n-a x_n^{2}-\frac1a =-a\left(x_n^{2}-\frac{2}{a}x_n+\frac{1}{a^{2}}\right) =-a\left(x_n-\frac1a\right)^{2}=-a\,e_n^{2}. \end{aligned}$$ So $e_{n+1}=-a e_n^{2}$ **exactly** (no Taylor remainder needed): perfect quadratic convergence, and after the first step every $e_n\le0$ — strictly negative unless some iterate lands exactly on $1/a$ — i.e. the iterates approach $1/a$ from below. **(c)** Put $u_n=a e_n=a x_n-1$. Multiplying the relation by $a$ gives $u_{n+1}=-u_n^{2}$, hence $|u_{n+1}|=|u_n|^{2}$ and by induction $|u_n|=|u_0|^{2^{n}}$. Therefore $u_n\to0$ (equivalently $x_n\to 1/a$) if and only if $|u_0|<1$: $$|a x_0-1|<1\quad\text{is the same as}\quad 0<a x_0<2,\quad\text{i.e.}\quad 0<x_0<\frac{2}{a}.$$ If $x_0<0$ or $x_0>2/a$ then $|u_0|>1$, so $u_n\to-\infty$ and the iterates run off to $-\infty$; if $x_0=2/a$ then $x_1=0$ and the method dies. The value $x_0=0$ is not a legal start at all — $f$ and $f'$ are undefined there — and the map would freeze at $0$ anyway. **(d)** $a=7$, so $x_{n+1}=x_n(2-7x_n)$, and $x_0=0.1$ satisfies $0<0.1<\frac27=0.2857$, so we expect convergence. $$\begin{aligned} x_1&=0.1\left(2-0.7\right)=0.1(1.3)=0.13\\ x_2&=0.13\left(2-0.91\right)=0.13(1.09)=0.1417\\ x_3&=0.1417\left(2-0.9919\right)=0.1417(1.0081)=0.14284777\\ x_4&=0.14284777\left(2-0.99993439\right)=0.14284777(1.00006561)=0.1428571422 \end{aligned}$$ **Check with the error law.** $\frac17=0.1428571429$, so $e_0=-0.0428571429$ and $$e_1=-7e_0^{2}=-7(0.0018367347)=-0.0128571429\ \Rightarrow\ x_1=0.1428571429-0.0128571429=0.13$$ — matching the direct computation. Continuing: $e_2=-1.1571\times10^{-3}$, $e_3=-9.3729\times10^{-6}$, $e_4=-6.1495\times10^{-10}$, matching the computed iterates. **Answer:** $x_{n+1}=x_n(2-ax_n)$; converges exactly for $0<x_0<2/a$; for $a=7$, $x_4=0.1428571422$, whose error is $6.1\times10^{-10}$ — that is $8$ correct decimals ($\frac17\approx0.14285714$), and the next step gives $|e_5|=2.6\times10^{-18}$.

(a) $f(x)=x^3-2x+2$, $f'(x)=3x^2-2$.

x_2=1-\frac{f(1)}{f'(1)}=1-\frac{1-2+2}{3-2}=1-\frac{1}{1}=0.$$ So $x_2=x_0=0$ and the iteration repeats forever: $0,\,1,\,0,\,1,\,0,\dots$ — a **2-cycle**. It never converges, and $f$ is never zero at either point ($f(0)=2$, $f(1)=1$). **(b)** The Newton map here satisfies $N(0)=1$ and $N(1)=0$, so $N(N(0))=0$: the pair $\{0,1\}$ is a periodic orbit of $N$. Because the iteration is deterministic — $x_{n+1}$ depends only on $x_n$ — once a value repeats, the entire future repeats. Exact arithmetic will therefore never break out. (In floating point, rounding sometimes nudges you off the cycle, which is luck, not method.) **(c) Exactly one real root.** $f'(x)=3x^2-2=0$ at $x=\pm\sqrt{2/3}=\pm0.8164965809$. These are the only critical points, and $$f\left(-\sqrt{\frac23}\right)=2+\frac{4}{3}\sqrt{\frac23}=3.0886621079>0\ \text{(local max)},\qquad f\left(\sqrt{\frac23}\right)=2-\frac{4}{3}\sqrt{\frac23}=0.9113378921>0\ \text{(local min)}.$$ Since the local minimum value is positive, $f>0$ on $\left[-\sqrt{2/3},\infty\right)$, so all real roots lie to the left of the local max, where $f$ is increasing; an increasing function crosses zero at most once. And $f(-2)=-8+4+2=-2<0$ while $f(-1)=-1+2+2=3>0$, so by the IVT the unique real root lies in $(-2,-1)$. **Newton from $x_0=-2$.** $$\begin{aligned} f(-2)&=-2,\ f'(-2)=10 &&\Rightarrow x_1=-2-\frac{-2}{10}=-1.8\\ f(-1.8)&=-5.832+3.6+2=-0.232,\ f'(-1.8)=3(3.24)-2=7.72 &&\Rightarrow x_2=-1.8+\frac{0.232}{7.72}=-1.7699481865\\ f(x_2)&=-0.0048496619,\ f'(x_2)=7.3981497490 &&\Rightarrow x_3=-1.7692926629\\ f(x_3)&=-0.0000022814,\ f'(x_3)=7.3911895810 &&\Rightarrow x_4=-1.7692923542 \end{aligned}$$ **Answer:** the cycle is $0\to1\to0\to\cdots$; the unique real root is $r\approx-1.7692923542$. Check: $(-1.7692923542)^3-2(-1.7692923542)+2=2.9\times10^{-10}\approx0$. Moral: a perfectly smooth cubic can trap Newton — always bracket the root first (here $f(-2)<0<f(-1)$ tells you to start near $-2$, not at $0$).

Set-up. $f'(x)=2x$, and

$x_{n+1}=x_n-\frac{x_n^2-4}{2x_n}=\frac{x_n^2+4}{2x_n}=\frac12\left(x_n+\frac{4}{x_n}\right).$

(a) $f'(0)=0$, so $x_1=0-\dfrac{f(0)}{f'(0)}=0-\dfrac{-4}{0}$ is undefined. Geometrically, $x=0$ is the vertex of the parabola; the tangent there is the horizontal line $y=-4$, which never meets the $x$-axis. Newton's method simply cannot start here.

(b) With $x_0=0.001$: $f(0.001)=0.000001-4=-3.999999$ and $f'(0.001)=0.002$.

$x_1=0.001-\frac{-3.999999}{0.002}=0.001+1999.9995=2000.0005 .$

Geometrically, the tangent at $(0.001,-3.999999)$ has slope $0.002$ — almost horizontal — so travelling from height $-4$ up to the axis along it requires a horizontal run of about $4/0.002=2000$. A nearly-flat tangent flings the next iterate enormously far away. This is the "$f'$ near zero" failure: the method does not break, but it wastes the start entirely.

(c) For large $x_n$ the term $4/x_n$ is negligible next to $x_n$, so $x_{n+1}=\frac12\left(x_n+\frac{4}{x_n}\right)\approx\frac{x_n}{2}.$ Halving from $2000$ down to about $2$ needs $n$ with $2000/2^{n}\approx2$, i.e. $2^{n}\approx1000$, so $n\approx\log_2 1000\approx10$ steps of pure halving; only then does the quadratic phase begin. In fact the iterates are $2000.0005,\ 1000.0012,\ 500.0026,\ 250.0053,\ 125.0107,\ 62.5213,\ 31.2927,\ 15.7102,\ 7.9824,\ 4.2418,\ 2.5924,\ 2.0677,\ 2.0011,\ 2.00000031,\ 2.0000000000000,$ i.e. $15$ steps in total — eleven wasted crawling back, then four fast ones.

(d) From $x_0=3$ (a sensible start: $f(1)=-3<0<5=f(3)$ brackets the root, and $3$ is on the side where $f\cdot f''>0$):

x_1&=\frac12\left(3+\frac43\right)=\frac{13}{6}=2.1666666667\\ x_2&=\frac12\left(2.1666666667+1.8461538462\right)=\frac{313}{156}=2.0064102564\\ x_3&=\frac12\left(2.0064102564+1.9936102236\right)=\frac{195313}{97656}=2.0000102400 \end{aligned}$$ For the last step use the exact error law $e_{n+1}=\dfrac{e_n^{2}}{2x_n}$ (see the quadratic-convergence problem): with $e_3=1.02400\times10^{-5}$, $$e_4=\frac{\left(1.024\times10^{-5}\right)^{2}}{2(2.00001024)}=2.6214\times10^{-11},\qquad x_4=2.0000000000262 .$$ Four steps give $10$ correct decimals. **Moral:** the method is only as good as $x_0$; bracket with the IVT and keep $|f'(x_0)|$ comfortably away from $0$.

(a) The simplified iteration is $x_{n+1}=\dfrac{x_n^{2}+2}{2x_n}$. Hence

e_{n+1}=x_{n+1}-\sqrt2&=\frac{x_n^{2}+2}{2x_n}-\sqrt2 =\frac{x_n^{2}+2-2\sqrt2\,x_n}{2x_n}\\ &=\frac{x_n^{2}-2\sqrt2\,x_n+\left(\sqrt2\right)^{2}}{2x_n} =\frac{\left(x_n-\sqrt2\right)^{2}}{2x_n}=\frac{e_n^{2}}{2x_n}, \end{aligned}$$ using $2=\left(\sqrt2\right)^{2}$. Two immediate consequences: the error is *squared* each step, and (for $x_n>0$) $e_{n+1}>0$ — after one step every iterate overshoots above $\sqrt2$. **(b)** From $x_0=1$: $x_1=1.5$, $x_2=1.4166666667$, $x_3=1.4142156863$, $x_4=1.4142135624$, and $\sqrt2=1.4142135623730950$. $$e_1=8.578644\times10^{-2},\quad e_2=2.453104\times10^{-3},\quad e_3=2.123901\times10^{-6},\quad e_4=1.594862\times10^{-12}.$$ Check with (a): $e_2=\dfrac{e_1^{2}}{2x_1}=\dfrac{(0.0857864376)^{2}}{3}=\dfrac{0.0073593129}{3}=0.0024531043$ ✓ (matches exactly). Correct decimal places: about $1$, then $2$, then $5$, then $11$ — the count **doubles** each iteration (writing $L_n=-\log_{10}e_n$ gives $L_1,\dots,L_4=1.07,\,2.61,\,5.67,\,11.80$, which satisfy $L_{n+1}\approx 2L_n+0.45$, the $0.45$ being $-\log_{10}0.354$). **(c)** If $x_n>\sqrt2$ then $2x_n>2\sqrt2=2.8284271$, so $$e_{n+1}=\frac{e_n^{2}}{2x_n}<\frac{e_n^{2}}{2\sqrt2}=0.3535534\,e_n^{2}\le 0.354\,e_n^{2}.$$ (The upper bound $x_n\le1.5$ is not even needed for this direction; it only tells us $e_{n+1}\ge e_n^2/3$.) So if $x_n$ is correct to $6$ decimals, $e_n\le5\times10^{-7}$ and $$e_{n+1}\le0.354\left(5\times10^{-7}\right)^{2}=8.85\times10^{-14},$$ i.e. $x_{n+1}$ is correct to about $13$ decimal places — one step turns $6$ digits into $13$. **(d)** Taylor-expand $f$ about $x_n$ and evaluate at the root $r$ (valid because $f$ is twice differentiable): for some $\xi_n$ strictly between $x_n$ and $r$, $$0=f(r)=f(x_n)+f'(x_n)\left(r-x_n\right)+\frac{f''(\xi_n)}{2}\left(r-x_n\right)^{2}.$$ Divide by $f'(x_n)\ne0$: $$0=\frac{f(x_n)}{f'(x_n)}+\left(r-x_n\right)+\frac{f''(\xi_n)}{2f'(x_n)}\left(x_n-r\right)^{2},$$ so that $$\left(x_n-\frac{f(x_n)}{f'(x_n)}\right)-r=\frac{f''(\xi_n)}{2f'(x_n)}\left(x_n-r\right)^{2},$$ and the bracket on the left is exactly $x_{n+1}$, so $$e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}\,e_n^{2}.$$ **Consistency.** For $f(x)=x^2-2$ we have $f''\equiv2$ and $f'(x_n)=2x_n$, so the general formula reads $e_{n+1}=\dfrac{2}{2\cdot 2x_n}e_n^{2}=\dfrac{e_n^{2}}{2x_n}$ — exactly part (a), with no unknown $\xi_n$ left over because $f''$ is constant. The limiting constant is $\dfrac{|f''(r)|}{2|f'(r)|}=\dfrac{2}{2\cdot2\sqrt2}=\dfrac{1}{2\sqrt2}=0.3536$, agreeing with (c).

(a) Expand: $(x-2)^2(x+1)=\left(x^2-4x+4\right)(x+1)=x^3+x^2-4x^2-4x+4x+4=x^3-3x^2+4$ ✓. So $f(2)=0$, and $f'(x)=3x^2-6x=3x(x-2)$ gives $f'(2)=0$ while $f''(x)=6x-6$ gives $f''(2)=6\ne0$: the root $x=2$ has multiplicity exactly $m=2$. Note $f'(r)=0$, so the quadratic-convergence theorem does not apply.

(b) Plain Newton, $x_{n+1}=x_n-\dfrac{x_n^3-3x_n^2+4}{3x_n^2-6x_n}$. From $x_0=3$: $f(3)=27-27+4=4$, $f'(3)=27-18=9$, so $x_1=3-\frac49=2.5555555556$. Continuing (using $f=e^2(x+1)$ and $f'=3x(x-2)$ to keep the arithmetic clean):

The error is only halving: this is linear (first-order) convergence with ratio $\to\frac12$, not quadratic. Ten more steps would gain about $3$ decimals, not $3000$.

(c) Write $f(x)=(x-r)^{m}g(x)$ with $g$ differentiable and $g(r)\ne0$, and set $e=x-r$. By the product rule, $f'(x)=m(x-r)^{m-1}g(x)+(x-r)^{m}g'(x)=(x-r)^{m-1}\left[m\,g(x)+(x-r)g'(x)\right].$ Hence, cancelling $(x-r)^{m-1}$, $\frac{f(x)}{f'(x)}=\frac{e\,g(x)}{m\,g(x)+e\,g'(x)} ,$ and the new error is $e_{\text{new}}=e-\frac{e\,g}{mg+eg'}=e\cdot\frac{mg+eg'-g}{mg+eg'}=e\cdot\frac{(m-1)g(x)+e\,g'(x)}{m\,g(x)+e\,g'(x)}.$ Letting $e\to0$ (so $x\to r$, $g(x)\to g(r)\ne0$): $\frac{e_{\text{new}}}{e}\to\frac{(m-1)g(r)}{m\,g(r)}=\frac{m-1}{m}=1-\frac1m .$ For $m=2$ this is $\frac12$, matching the table; for a simple root $m=1$ the ratio is $0$, which is the fingerprint of superlinear (in fact quadratic) convergence.

(d) Modified Newton, $x_{n+1}=x_n-2\dfrac{f(x_n)}{f'(x_n)}$. From the same formula with the factor $m=2$ inserted, the new error is $e_{\text{new}}=\dfrac{e^{2}g'(x)}{2g(x)+e\,g'(x)}$ — quadratic. Here $g(x)=x+1$, $g'=1$:

x_1&=3-2\cdot\frac49=3-\frac89=2.1111111111 &&e_1=1.111\times10^{-1}\\ x_2&=2.1111111111-2\cdot\frac{0.0384087791}{0.7037037037}=2.0019493177 &&e_2=1.949\times10^{-3}\\ x_3&=2.0000006327 &&e_3=6.327\times10^{-7}\\ x_4&=2.0000000000 &&e_4=6.7\times10^{-14} \end{aligned}$$ **Answer:** plain Newton on a double root converges linearly with ratio $\to\frac12$; the modified step with $m=2$ restores quadratic convergence, driving the error to $6.7\times10^{-14}$ ($12$ correct decimals) in four steps, where plain Newton still had barely one.

(a) For $x\ne0$, $f(x)=x^{1/3}$ has $f'(x)=\dfrac13x^{-2/3}$, which is non-zero, so every step is defined:

$x_{n+1}=x_n-\frac{x_n^{1/3}}{\frac13 x_n^{-2/3}}=x_n-3\,x_n^{1/3}\cdot x_n^{2/3}=x_n-3x_n=-2x_n .$

Hence $|x_{n+1}|=2|x_n|$, so $|x_n|=2^{n}|x_0|\to\infty$ for any $x_0\ne0$, while the sign alternates. From $x_0=0.5$: $0.5,\ -1,\ 2,\ -4,\ 8,\ -16,\ 32,\dots$ The iterates straddle the root and run away from it geometrically.

Which hypothesis fails. The convergence theorem needs $f$ to be (twice) continuously differentiable near the root $r=0$ with $f'(r)\ne0$. Here $f'(x)=\frac13x^{-2/3}\to+\infty$ as $x\to0$: $f$ is not differentiable at the root at all, and $f''(x)=-\frac29x^{-5/3}$ is unbounded near $0$, so the constant $C=\frac{\max|f''|}{2\min|f'|}$ in the error bound is infinite. Geometrically the graph has a vertical tangent at $0$, so tangent lines near the root are steep and point away; each one crosses the axis further out.

(b) $f(x)=\arctan x$, $f'(x)=\dfrac{1}{1+x^{2}}$, which is never zero, so

$N(x)=x-\frac{\arctan x}{\frac{1}{1+x^{2}}}=x-\left(1+x^{2}\right)\arctan x .$

From $x_0=2$ (radians):

x_1&=2-(1+4)\arctan 2=2-5(1.1071487178)=2-5.5357435890=-3.5357435890\\ x_2&=-3.5357435890-\left(13.5014827269\right)\left(-1.2951690588\right)=-3.5357435890+17.4867026759=13.9509590869\\ x_3&=13.9509590869-\left(195.6292594451\right)\left(1.4992390527\right)=13.9509590869-293.2950256205=-279.3440665336\\ x_4&=-279.3440665336-\left(78034.1075075\right)\left(-1.5672165274\right)=122016.998918 \end{aligned}$$ The iterates explode: $2\to-3.54\to13.95\to-279\to1.22\times10^{5}$. (Only the leading digits of $x_4$ are meaningful here — the factors above are themselves rounded, so quoting ten decimals of $x_4$ would be fiction.) **Where $2x=(1+x^{2})\arctan x$ comes from.** The behaviour is symmetric because $N$ is odd: $N(-x)=-N(x)$. The borderline between "step lands closer" and "step lands further" is the starting point that Newton maps exactly onto its own negative, producing a perfect $2$-cycle $x^{*}\to-x^{*}\to x^{*}\to\cdots$. Setting $N(x)=-x$: $$x-\left(1+x^{2}\right)\arctan x=-x\quad\Rightarrow\quad 2x=\left(1+x^{2}\right)\arctan x .$$ Solving numerically gives $x^{*}=1.3917452$. For $|x_0|<x^{*}$ each step lands strictly nearer $0$ and Newton converges; for $|x_0|>x^{*}$ each step lands strictly further away and it diverges; at $|x_0|=x^{*}$ it cycles. The cause is that $\arctan$ has flat tails — $f'(x)=\frac{1}{1+x^2}\to0$ — so far from the root the tangent is nearly horizontal and its $x$-intercept is thrown across to the other side. A **damped** step $x_{n+1}=x_n-\lambda\frac{f(x_n)}{f'(x_n)}$ with $0<\lambda\le1$ chosen so that $|f(x_{n+1})|<|f(x_n)|$ cures it.

(a) Set-up. A general point of the parabola is $\left(x,x^{2}\right)$. Its squared distance to $(4,0)$ is

$D(x)=(x-4)^{2}+\left(x^{2}-0\right)^{2}=(x-4)^{2}+x^{4}.$

Minimising $D$ is equivalent to minimising the distance $\sqrt{D}$, since $t\mapsto\sqrt t$ is increasing on $[0,\infty)$. Now

$D'(x)=2(x-4)+4x^{3}=4x^{3}+2x-8,\qquad D''(x)=12x^{2}+2 .$

Since $D''(x)=12x^{2}+2\ge2>0$ for all $x$, $D$ is strictly convex for all real $x$; hence $D'$ is strictly increasing, so $D'$ has at most one zero, and any zero is a global minimum. Also $D(x)\to\infty$ as $x\to\pm\infty$, so a minimum exists. Exactly one critical point, and it is the global minimiser.

(b) Root-finding problem. Solve $D'(x)=0$, i.e. (dividing by $2$)

$g(x)=2x^{3}+x-4=0,\qquad g'(x)=6x^{2}+1 .$

Newton on $g$ is Newton on $D'$, because $\dfrac{D'(x)}{D''(x)}=\dfrac{2\left(2x^{3}+x-4\right)}{2\left(6x^{2}+1\right)}=\dfrac{g(x)}{g'(x)}$.

Bracket. $g$ is continuous; $g(1)=2+1-4=-1<0$ and $g(1.5)=6.75+1.5-4=4.25>0$, so by the IVT there is a root in $(1,1.5)$. Sharpen: $g(1.1)=2(1.331)+1.1-4=-0.238<0$ and $g(1.2)=2(1.728)+1.2-4=0.656>0$, so the root lies in $(1.1,1.2)$. Take $x_0=1.1$ (note $g'(1.1)=8.26$, comfortably away from $0$).

(c) Newton. $x_{n+1}=x_n-\dfrac{2x_n^{3}+x_n-4}{6x_n^{2}+1}$.

x_1&=1.1-\frac{-0.238}{8.26}=1.1+0.0288135593=1.1288135593\\ x_2&=1.1288135593-\frac{0.0055273032}{8.6453203103}=1.1288135593-0.0006393405=1.1281742188\\ x_3&=1.1281742188-\frac{0.0000027679}{8.6366624084}=1.1281742188-0.0000003205=1.1281738983 \end{aligned}$$ Carrying extra digits, $x_3=1.12817389836$, so the iterates have stabilised at $x^{*}=1.1281738984$ to $10$ decimal places. Independent check by sign change: $g(1.1281738983)=-5.3\times10^{-10}<0$ and $g(1.1281738984)=+3.3\times10^{-10}>0$, so the root really is trapped between those two ten-decimal values. **Answer.** The closest point is $$\left(x^{*},\left(x^{*}\right)^{2}\right)=\left(1.1281738984,\;1.2727763449\right),$$ and the minimum distance is $$\sqrt{D(x^{*})}=\sqrt{(1.1281738984-4)^{2}+(1.1281738984)^{4}}=\sqrt{8.2473851578+1.6199596245}=\sqrt{9.8673447823}=3.1412330035 .$$ (That is $3.1412$, tantalisingly close to $\pi=3.14159\ldots$ but not equal to it — a good reminder to check, not assume.) A geometric sanity check: the segment from $(4,0)$ to the closest point should be perpendicular to the parabola. The tangent slope there is $2x^{*}=2.2563477968$, and the segment has slope $\dfrac{1.2727763449-0}{1.1281738984-4}=\dfrac{1.2727763449}{-2.8718261016}=-0.4431940862$; the product is $2.2563477968\times(-0.4431940862)=-1.0000000000$ ✓.