Learn4Less Logo

Navigation

Home

Learn

CoursesServicesCompetition MathResearch MentorshipConcept Review

Tools

WeBWorK WorkshopGrade CalculatorUBC Grade Statistics

More

Free Resources (Blog)ContactJoin Our TeamPrivacy PolicyTerms & Conditions

Our Other Platforms

Concept Review

Differential Calculus

Newton's Method

Newton's method is the standard fast algorithm for solving an equation f(x)=0f(x)=0 when you cannot solve it exactly. It is the biggest payoff of the tangent line / linear approximation: replace the curve by its tangent, solve the linear equation instead, and repeat. It sits at the end of the derivative-applications block, alongside the IVT (which finds a bracket) and linear approximation (which supplies the step).

1. Derivation from the tangent line

Let ff be differentiable near a current guess xnx_n, and suppose f′(xn)≠0f'(x_n)\ne 0. The tangent line to y=f(x)y=f(x) at (xn,f(xn))\left(x_n,f(x_n)\right) is

L(x)=f(xn)+f′(xn)(x−xn).L(x)=f(x_n)+f'(x_n)\left(x-x_n\right).

The curve is hard to zero; the line is not. Set L(x)=0L(x)=0 and solve:

f(xn)+f′(xn)(x−xn)=0x−xn=−f(xn)f′(xn)x=xn−f(xn)f′(xn).\begin{aligned} f(x_n)+f'(x_n)(x-x_n) &= 0 \\ x-x_n &= -\frac{f(x_n)}{f'(x_n)} \\ x &= x_n-\frac{f(x_n)}{f'(x_n)}. \end{aligned}

Call that number xn+1x_{n+1}. Newton's iteration:

xn+1=xn−f(xn)f′(xn),n=0,1,2,…x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\qquad n=0,1,2,\dots

Same thing via linear approximation: we want a step hh with f(xn+h)=0f(x_n+h)=0; since f(xn+h)≈f(xn)+f′(xn)hf(x_n+h)\approx f(x_n)+f'(x_n)h, take h=−f(xn)/f′(xn)h=-f(x_n)/f'(x_n).

Hypotheses that must actually hold: ff differentiable on an interval containing every iterate, and f′(xn)≠0f'(x_n)\ne 0 at every step. If f′(xn)=0f'(x_n)=0 the tangent is horizontal, so it has no unique xx-intercept and xn+1x_{n+1} does not exist: when f(xn)≠0f(x_n)\ne0 the tangent is a horizontal line that never meets the xx-axis, and in the edge case f(xn)=0f(x_n)=0 the tangent is the xx-axis (you are already standing on a root, so stop).

Newton is the fixed-point iteration xn+1=N(xn)x_{n+1}=N(x_n) with N(x)=x−f(x)f′(x)N(x)=x-\dfrac{f(x)}{f'(x)}. Note

N′(x)=1−f′(x)2−f(x)f′′(x)f′(x)2=f(x)f′′(x)f′(x)2,N'(x)=1-\frac{f'(x)^2-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2},

so at a root rr with f′(r)≠0f'(r)\ne 0 we get N(r)=rN(r)=r and N′(r)=0N'(r)=0. A fixed point with zero derivative is superattracting — that is exactly why Newton is fast.

2. Choosing x0x_0, and bracketing with IVT / bisection

Intermediate Value Theorem. If ff is continuous on [a,b][a,b] and f(a)f(a) and f(b)f(b) have opposite signs, then f(c)=0f(c)=0 for some c∈(a,b)c\in(a,b). (Continuity is essential; differentiability is not needed.) If in addition f′>0f'>0 on (a,b)(a,b) (or f′<0f'<0 throughout), the root is unique.

Bisection. Given a sign-change bracket [a,b][a,b], test the midpoint m=a+b2m=\frac{a+b}{2} and keep the half that still changes sign. After nn steps the bracket has length b−a2n\dfrac{b-a}{2^{n}}, so the midpoint is within b−a2 n+1\dfrac{b-a}{2^{\,n+1}} of a root. Bisection always works but gains only log⁡102≈0.30\log_{10}2\approx 0.30 decimal digits per step (about 3.33.3 steps per digit).

Recommended workflow: sketch or use IVT to bracket a root ⇒\Rightarrow bisect two or three times ⇒\Rightarrow start Newton from the midpoint ⇒\Rightarrow stop when ∣xn+1−xn∣|x_{n+1}-x_n| is below tolerance and ∣f(xn+1)∣|f(x_{n+1})| is small.

A useful sufficient condition (Fourier): if on [a,b][a,b] we have f(a)f(b)<0f(a)f(b)<0 and f′f', f′′f'' are each of constant sign, then starting from the endpoint where f(x0)f′′(x0)>0f(x_0)f''(x_0)>0 makes Newton converge monotonically to the root.

3. Standard set-ups

Equationf(x)f(x)f′(x)f'(x)Simplified iteration
x2=ax^2=a, a>0a>0x2−ax^2-a2x2xxn+1=12(xn+axn)x_{n+1}=\dfrac{1}{2}\left(x_n+\dfrac{a}{x_n}\right)
xk=ax^k=axk−ax^k-akxk−1kx^{k-1}xn+1=(k−1)xn+a xn1−kkx_{n+1}=\dfrac{(k-1)x_n+a\,x_n^{1-k}}{k}
x=1ax=\dfrac{1}{a}1x−a\dfrac{1}{x}-a−1x2-\dfrac{1}{x^2}xn+1=xn(2−axn)x_{n+1}=x_n(2-a x_n) — no division used
cos⁡x=x\cos x=xcos⁡x−x\cos x-x−sin⁡x−1-\sin x-1xn+1=xn+cos⁡xn−xnsin⁡xn+1x_{n+1}=x_n+\dfrac{\cos x_n-x_n}{\sin x_n+1}
ex=ce^{x}=cex−ce^{x}-cexe^{x}xn+1=xn−1+c e−xnx_{n+1}=x_n-1+c\,e^{-x_n}
critical point of ggg′(x)g'(x)g′′(x)g''(x)xn+1=xn−g′(xn)g′′(xn)x_{n+1}=x_n-\dfrac{g'(x_n)}{g''(x_n)}

4. Worked example 1 — 2\sqrt{2} from x0=1x_0=1

Take f(x)=x2−2f(x)=x^2-2, f′(x)=2xf'(x)=2x. Then

xn+1=xn−xn2−22xn=2xn2−xn2+22xn=12(xn+2xn).x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}=\frac{2x_n^2-x_n^2+2}{2x_n}=\frac{1}{2}\left(x_n+\frac{2}{x_n}\right).

x1=12(1+2)=1.5x2=12(1.5+21.5)=12(1.5+1.3333333333)=1.4166666667x3=12(1.4166666667+1.4117647059)=1.4142156863x4=12(1.4142156863+1.4142114385)=1.4142135624\begin{aligned} x_1&=\frac12\left(1+2\right)=1.5 \\ x_2&=\frac12\left(1.5+\frac{2}{1.5}\right)=\frac12\left(1.5+1.3333333333\right)=1.4166666667 \\ x_3&=\frac12\left(1.4166666667+1.4117647059\right)=1.4142156863 \\ x_4&=\frac12\left(1.4142156863+1.4142114385\right)=1.4142135624 \end{aligned}

Against 2=1.41421356237310\sqrt{2}=1.41421356237310 the errors are 8.58×10−28.58\times10^{-2}, 2.45×10−32.45\times10^{-3}, 2.12×10−62.12\times10^{-6}, 1.59×10−121.59\times10^{-12}: the number of correct digits roughly doubles each step.

5. Worked example 2 — solving cos⁡x=x\cos x=x

Move everything to one side: f(x)=cos⁡x−xf(x)=\cos x-x, so f′(x)=−sin⁡x−1f'(x)=-\sin x-1.

Bracket. ff is continuous, f(0)=1>0f(0)=1>0 and f(1)=cos⁡1−1=−0.4596976941<0f(1)=\cos 1-1=-0.4596976941<0, so by the IVT there is a root in (0,1)(0,1). On (0,1)(0,1), sin⁡x>0\sin x>0 gives f′(x)<−1<0f'(x)<-1<0, so ff is strictly decreasing and the root is unique.

Iterate from x0=1x_0=1 (radians!):

xn+1=xn−cos⁡xn−xn−sin⁡xn−1=xn+cos⁡xn−xnsin⁡xn+1.x_{n+1}=x_n-\frac{\cos x_n-x_n}{-\sin x_n-1}=x_n+\frac{\cos x_n-x_n}{\sin x_n+1}.

x1=1+0.5403023059−10.8414709848+1=1−0.2496361322=0.7503638678x2=0.7503638678+−0.01892307381.6819049529=0.7391128909x3=0.7391128909+−0.00004645591.6736325442=0.7390851334x4=0.7390851332\begin{aligned} x_1&=1+\frac{0.5403023059-1}{0.8414709848+1}=1-0.2496361322=0.7503638678\\ x_2&=0.7503638678+\frac{-0.0189230738}{1.6819049529}=0.7391128909\\ x_3&=0.7391128909+\frac{-0.0000464559}{1.6736325442}=0.7390851334\\ x_4&=0.7390851332 \end{aligned}

The root is r=0.7390851332r=0.7390851332 (to 1010 decimal places); errors 1.1×10−21.1\times10^{-2}, 2.8×10−52.8\times10^{-5}, 1.7×10−101.7\times10^{-10}.

6. How fast: quadratic convergence

Theorem. Suppose ff is twice continuously differentiable on an open interval II containing a root rr, and f′(r)≠0f'(r)\ne 0 (a simple root). Then there is δ>0\delta>0 such that for every x0x_0 with ∣x0−r∣<δ|x_0-r|<\delta all iterates are defined, stay in (r−δ,r+δ)(r-\delta,r+\delta), and xn→rx_n\to r; moreover with en=xn−re_n=x_n-r,

∣en+1∣≤C en 2,C=max⁡J∣f′′∣2min⁡J∣f′∣,J=[r−δ,r+δ],|e_{n+1}|\le C\,e_n^{\,2},\qquad C=\frac{\max_{J}|f''|}{2\min_{J}|f'|},\qquad J=\left[r-\delta,r+\delta\right],

(the max and the min are taken on the closed interval JJ, where the EVT guarantees they exist, and δ\delta is shrunk first so that min⁡J∣f′∣>0\min_{J}|f'|>0),

and if f′′(r)≠0f''(r)\ne0 then ∣en+1∣en2→∣f′′(r)∣2∣f′(r)∣\dfrac{|e_{n+1}|}{e_n^{2}}\to\dfrac{|f''(r)|}{2|f'(r)|}.

Why. Taylor-expand ff about xnx_n and evaluate at rr: for some ξn\xi_n between xnx_n and rr,

0=f(r)=f(xn)+f′(xn)(r−xn)+f′′(ξn)2(r−xn)2.0=f(r)=f(x_n)+f'(x_n)(r-x_n)+\frac{f''(\xi_n)}{2}(r-x_n)^2 .

Divide by f′(xn)f'(x_n) and rearrange:

xn−f(xn)f′(xn)−r=f′′(ξn)2f′(xn)(xn−r)2⇒en+1=f′′(ξn)2f′(xn) en2.x_n-\frac{f(x_n)}{f'(x_n)}-r=\frac{f''(\xi_n)}{2f'(x_n)}\left(x_n-r\right)^2 \quad\Rightarrow\quad e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}\,e_n^{2}.

Practical reading: the number of correct digits roughly doubles per step once you are close. Two consequences: (i) three or four good steps usually suffice; (ii) you must carry far more digits than you want in the answer, or rounding, not the method, limits you.

Multiple roots break this. If rr has multiplicity m≥2m\ge 2, then f′(r)=0f'(r)=0, the theorem's hypothesis fails, and Newton converges only linearly with en+1/en→1−1me_{n+1}/e_n\to 1-\frac1m. Fix: if you know mm, use the modified Newton step xn+1=xn−m f(xn)f′(xn)x_{n+1}=x_n-m\,\dfrac{f(x_n)}{f'(x_n)}, which restores quadratic speed (with the wrong mm you are back to linear).

7. When Newton fails

Failure modeConcrete exampleWhat you seeRepair
f′(xn)=0f'(x_n)=0f(x)=x2−1f(x)=x^2-1, x0=0x_0=0division by zero; step undefinedmove x0x_0
f′(xn)f'(x_n) tinyf(x)=x2−4f(x)=x^2-4, x0=0.001x_0=0.001x1=2000.0005x_1=2000.0005: huge jump awaybracket first
Cyclingf(x)=x3−2x+2f(x)=x^3-2x+2, x0=0x_0=0iterates 0,1,0,1,…0,1,0,1,\dots foreverperturb x0x_0
Divergencef(x)=x1/3f(x)=x^{1/3}, any x0≠0x_0\ne0xn+1=−2xnx_{n+1}=-2x_n; size doublesnone — f′→∞f'\to\infty at the root, so no x0x_0 works; bisect instead
Flat-tail overshootf(x)=arctan⁡xf(x)=\arctan x, x0=2x_0=22→−3.54→13.95→−279→…2\to-3.54\to13.95\to-279\to\dotsdamped step; start nearer 00 than 1.39171.3917
Wrong basinany ff with several rootsconverges, but to the wrong rootsketch, then bracket
Multiple rootf(x)=(x−2)2(x+1)f(x)=(x-2)^2(x+1)error only halves each stepmodified Newton, m=2m=2

Bisection never does any of these — it just is slow. Hence the hybrid: bracket and bisect for safety, then switch to Newton for speed.

Common mistakes

  • Sign of the step. Wrong: xn+1=xn+f(xn)f′(xn)x_{n+1}=x_n+\frac{f(x_n)}{f'(x_n)}. Right: xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. Sanity check on f(x)=x2−2f(x)=x^2-2, x0=1x_0=1: the minus sign gives 1.51.5 (toward 2\sqrt2); the plus sign gives 0.50.5 (away).
  • Not moving everything to one side. For cos⁡x=x\cos x=x, wrong: f(x)=cos⁡xf(x)=\cos x. Right: f(x)=cos⁡x−xf(x)=\cos x-x, f′(x)=−sin⁡x−1f'(x)=-\sin x-1 (the −1-1 is easy to drop).
  • Rounding intermediate values. Rounding each xnx_n to 44 decimals caps the final answer at about 44 decimals no matter how many steps you take. Carry roughly twice the digits you intend to report.
  • Degrees instead of radians. ddxcos⁡x=−sin⁡x\frac{d}{dx}\cos x=-\sin x is only true in radians; a calculator in degree mode silently gives a different root.
  • "f(xn)f(x_n) is tiny, so xnx_n is close to the root." Not necessarily — only when ∣f′∣|f'| is not small. For f(x)=(x−1)3f(x)=(x-1)^3 at x=1.1x=1.1, f=0.001f=0.001 looks excellent but the error is 0.10.1. Test ∣xn+1−xn∣|x_{n+1}-x_n| as well.
  • Reporting more digits than you have. Two iterates agreeing to 88 places is strong evidence, not proof; quote the digits that stop changing.
  • Optimising with the wrong function. To find a critical point of gg you run Newton on f=g′f=g', so the iteration needs g′′g'' — writing xn+1=xn−g(xn)/g′(xn)x_{n+1}=x_n-g(x_n)/g'(x_n) finds a root of gg instead.
  • Assuming convergence. "Newton always converges" is false; x1/3x^{1/3} and x3−2x+2x^3-2x+2 above are counterexamples with perfectly nice-looking ff.

Key terms

  • Newton's method
  • Newton-Raphson iteration
  • tangent line approximation
  • linear approximation
  • initial guess
  • root (zero) of a function
  • simple root
  • multiple root / multiplicity
  • modified Newton's method
  • fixed-point iteration
  • superattracting fixed point
  • quadratic convergence
  • linear convergence
  • error term e_n = x_n - r
  • Taylor error formula
  • Intermediate Value Theorem
  • bracketing a root
  • bisection method
  • sign change
  • divergence
  • cycling
  • basin of attraction
  • stopping criterion / tolerance
  • division-free reciprocal iteration

Practice Problems

Use Newton's method with f(x)=x2−5f(x)=x^2-5 and x0=2x_0=2 to approximate 5\sqrt{5}. Simplify the iteration formula first, then carry out three iterations, quoting each xnx_n to 1010 decimal places.

Show hint

Write xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} and combine the two terms over the common denominator 2xn2x_n before you put any numbers in.

Show answer

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

Simplify the iteration.

xn+1=xn−xn2−52xn=2xn2−(xn2−5)2xn=xn2+52xn=12(xn+5xn).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.

x1=12(2+52)=12(2+2.5)=94=2.2500000000x2=12(2.25+52.25)=12(2.25+2.2222222222)=16172=2.2361111111x3=12(2.2361111111+52.2361111111)=12(2.2361111111+2.2360248447)=5184123184=2.2360679779\begin{aligned} 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. 5=2.2360679775\sqrt5=2.2360679775, so the errors are e1=1.39×10−2,e2=4.31×10−5,e3=4.16×10−10.e_1=1.39\times10^{-2},\qquad e_2=4.31\times10^{-5},\qquad e_3=4.16\times10^{-10}. Independent verification: x32=(5184123184)2=5.0000000019x_3^2=\left(\frac{51841}{23184}\right)^2=5.0000000019, which is 55 to 88 decimal places, confirming x3x_3 is right.

Answer: x1=2.25x_1=2.25, x2=2.2361111111x_2=2.2361111111, x3=2.2360679779x_3=2.2360679779. With e3=4.16×10−10e_3=4.16\times10^{-10} the three steps have nailed 88 decimals: 5≈2.23606798\sqrt5\approx2.23606798. (Do not advertise 2.2360679782.236067978 as the 99-decimal value: 5=2.23606797749…\sqrt5=2.23606797749\ldots rounds to 2.2360679772.236067977 at 99 places, and an error of 4×10−104\times10^{-10} is not yet enough to settle that digit.)

Set up Newton's method for the equation x3=7x^3=7, simplify the iteration to a single fraction, and starting from x0=2x_0=2 compute x1x_1, x2x_2 and x3x_3 to 1010 decimal places. How many correct digits does each step buy?

Show hint

Put the equation in the form f(x)=0f(x)=0 first, then note that x3−73x2\frac{x^3-7}{3x^2} splits into x3−73x2\frac{x}{3}-\frac{7}{3x^2}.

Show answer

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

Simplify.

xn+1=xn−xn3−73xn2=3xn3−xn3+73xn2=2xn3+73xn2=23xn+73xn2.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 x0=2x_0=2.

x1=2(8)+73(4)=2312=1.9166666667x2=2(2312)3+73(2312)2=2(7.0410879630)+73(3.6736111111)=21.082175925911.0208333333=1.9129384583x3=2(7.0000798705)+73(3.6593335453)=1.9129311828\begin{aligned} 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 x2x_2 the intermediate values are (2312)2=529144=3.6736111111\left(\frac{23}{12}\right)^2=\frac{529}{144}=3.6736111111 and (2312)3=121671728=7.0410879630\left(\frac{23}{12}\right)^3=\frac{12167}{1728}=7.0410879630.)

Accuracy. The true value is 71/3=1.91293118287^{1/3}=1.9129311828 (more precisely 1.912931182772391.91293118277239). Errors: ∣x1−r∣=3.74×10−3,∣x2−r∣=7.28×10−6,∣x3−r∣=2.8×10−11.|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∣xn−r∣-\log_{10}|x_n-r|, that is 2.4→5.1→10.62.4\to5.1\to10.6: the count doubles each step, which is exactly quadratic convergence. Independent check: 1.91293118283=7.0000000001.9129311828^3=7.000000000 to 99 decimal places.

Answer: x1=1.9166666667x_1=1.9166666667, x2=1.9129384583x_2=1.9129384583, x3=1.9129311828x_3=1.9129311828; 71/3≈1.91293118287^{1/3}\approx1.9129311828.

(a) Starting from the equation of the tangent line to y=f(x)y=f(x) at x=xnx=x_n, derive Newton's iteration formula.

(b) State precisely what hypothesis on f′f' is needed, and explain geometrically what goes wrong when it fails.

(c) Show that if f(x)=mx+bf(x)=mx+b with m≠0m\ne0, then Newton's method finds the exact root in one step from any x0x_0. What does that say about how the method works in general?

Show hint

The tangent line is a linear function; asking where it crosses the xx-axis is a one-line algebra problem.

Show answer

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

L(x)=f(xn)+f′(xn)(x−xn).L(x)=f(x_n)+f'(x_n)\left(x-x_n\right).

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

f(xn)+f′(xn)(xn+1−xn)=0f′(xn)(xn+1−xn)=−f(xn)xn+1−xn=−f(xn)f′(xn)xn+1=xn−f(xn)f′(xn).\begin{aligned} 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′(xn)≠0f'(x_n)\ne0 at every iterate (and ff differentiable there). Geometrically, if f′(xn)=0f'(x_n)=0 the tangent line at xnx_n is horizontal: it is either the xx-axis itself or a line parallel to it, so it has no unique xx-intercept and xn+1x_{n+1} is undefined. Concretely, f(x)=x2−1f(x)=x^2-1 with x0=0x_0=0 gives f′(0)=0f'(0)=0 and the method stops immediately. Even f′(xn)f'(x_n) merely small is dangerous: the near-horizontal tangent meets the axis very far away, so xn+1x_{n+1} is thrown a long distance from xnx_n.

(c) With f(x)=mx+bf(x)=mx+b we have f′(x)=m≠0f'(x)=m\ne0 for all xx, so from any x0x_0,

x1=x0−mx0+bm=x0−x0−bm=−bm,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=0mx+b=0. Every further step reproduces it, since f(−b/m)=0f(-b/m)=0.

Interpretation. Newton's method is exact on linear functions, and for a general ff each step is exact on the tangent line — the best linear model of ff at xnx_n. The whole error of a step therefore comes from the gap between ff and its linear approximation, which by Taylor's theorem is of size 12f′′(ξ)(x−xn)2\frac12 f''(\xi)(x-x_n)^2. That quadratic-in-the-step error is precisely the source of the quadratic convergence rate.

Consider f(x)=x3+x−1f(x)=x^3+x-1.

(a) Use the IVT to show ff has a root in (0,1)(0,1), and show that it has exactly one real root.

(b) Do two bisection steps to shrink the bracket, and take x0x_0 to be the midpoint of the resulting interval.

(c) Run three Newton steps from that x0x_0, reporting 1010 decimal places.

(d) Roughly how many bisection steps from [0,1][0,1] would be needed for the same accuracy?

Show hint

For uniqueness look at the sign of f′f'; for the bisection steps you only need the signs of ff at 0.50.5 and 0.750.75.

Show answer

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

Uniqueness: f′(x)=3x2+1≥1>0f'(x)=3x^2+1\ge 1>0 for all real xx, so ff 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)(0,1).

(b) Bisection.

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

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

(c) Newton. xn+1=xn−xn3+xn−13xn2+1x_{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.130859375f(0.625)=0.244140625+0.625-1=-0.130859375; f′(0.625)=3(0.390625)+1=2.171875f'(0.625)=3(0.390625)+1=2.171875. x1=0.625−−0.1308593752.171875=0.625+0.0602517986=0.6852517986.x_1=0.625-\frac{-0.130859375}{2.171875}=0.625+0.0602517986=0.6852517986.

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

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

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

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

Apply Newton's method to f(x)=1x−af(x)=\dfrac{1}{x}-a (with a>0a>0) to get an iteration for 1a\dfrac{1}{a} that uses no division.

(a) Derive and simplify the iteration.

(b) Show the error satisfies en+1=−a en2e_{n+1}=-a\,e_n^{2} exactly, where en=xn−1ae_n=x_n-\frac1a.

(c) Deduce exactly which starting values x0x_0 give convergence.

(d) Take a=7a=7, x0=0.1x_0=0.1 and compute x1,…,x4x_1,\dots,x_4.

Show hint

Remember ddx(x−1)=−x−2\frac{d}{dx}\left(x^{-1}\right)=-x^{-2}, and dividing by −1/xn2-1/x_n^{2} is the same as multiplying by −xn2-x_n^{2}.

Show answer

(a) f(x)=x−1−af(x)=x^{-1}-a on x≠0x\ne0, so f′(x)=−x−2=−1x2f'(x)=-x^{-2}=-\dfrac{1}{x^2}, which is never zero. Then

xn+1=xn−1xn−a−1xn2=xn+xn2(1xn−a)=xn+xn−axn2=xn(2−axn).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 en=xn−1ae_n=x_n-\dfrac1a, so xn=en+1ax_n=e_n+\dfrac1a. Then

xn+1−1a=2xn−axn2−1a=−a(xn2−2axn+1a2)=−a(xn−1a)2=−a en2.\begin{aligned} 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 en+1=−aen2e_{n+1}=-a e_n^{2} exactly (no Taylor remainder needed): perfect quadratic convergence, and after the first step every en≤0e_n\le0 — strictly negative unless some iterate lands exactly on 1/a1/a — i.e. the iterates approach 1/a1/a from below.

(c) Put un=aen=axn−1u_n=a e_n=a x_n-1. Multiplying the relation by aa gives un+1=−un2u_{n+1}=-u_n^{2}, hence ∣un+1∣=∣un∣2|u_{n+1}|=|u_n|^{2} and by induction ∣un∣=∣u0∣2n|u_n|=|u_0|^{2^{n}}. Therefore un→0u_n\to0 (equivalently xn→1/ax_n\to 1/a) if and only if ∣u0∣<1|u_0|<1:

∣ax0−1∣<1is the same as0<ax0<2,i.e.0<x0<2a.|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 x0<0x_0<0 or x0>2/ax_0>2/a then ∣u0∣>1|u_0|>1, so un→−∞u_n\to-\infty and the iterates run off to −∞-\infty; if x0=2/ax_0=2/a then x1=0x_1=0 and the method dies. The value x0=0x_0=0 is not a legal start at all — ff and f′f' are undefined there — and the map would freeze at 00 anyway.

(d) a=7a=7, so xn+1=xn(2−7xn)x_{n+1}=x_n(2-7x_n), and x0=0.1x_0=0.1 satisfies 0<0.1<27=0.28570<0.1<\frac27=0.2857, so we expect convergence.

x1=0.1(2−0.7)=0.1(1.3)=0.13x2=0.13(2−0.91)=0.13(1.09)=0.1417x3=0.1417(2−0.9919)=0.1417(1.0081)=0.14284777x4=0.14284777(2−0.99993439)=0.14284777(1.00006561)=0.1428571422\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. 17=0.1428571429\frac17=0.1428571429, so e0=−0.0428571429e_0=-0.0428571429 and e1=−7e02=−7(0.0018367347)=−0.0128571429 ⇒ x1=0.1428571429−0.0128571429=0.13e_1=-7e_0^{2}=-7(0.0018367347)=-0.0128571429\ \Rightarrow\ x_1=0.1428571429-0.0128571429=0.13 — matching the direct computation. Continuing: e2=−1.1571×10−3e_2=-1.1571\times10^{-3}, e3=−9.3729×10−6e_3=-9.3729\times10^{-6}, e4=−6.1495×10−10e_4=-6.1495\times10^{-10}, matching the computed iterates.

Answer: xn+1=xn(2−axn)x_{n+1}=x_n(2-ax_n); converges exactly for 0<x0<2/a0<x_0<2/a; for a=7a=7, x4=0.1428571422x_4=0.1428571422, whose error is 6.1×10−106.1\times10^{-10} — that is 88 correct decimals (17≈0.14285714\frac17\approx0.14285714), and the next step gives ∣e5∣=2.6×10−18|e_5|=2.6\times10^{-18}.

Let f(x)=x3−2x+2f(x)=x^3-2x+2.

(a) Show that Newton's method with x0=0x_0=0 produces a cycle, and identify it.

(b) Explain in terms of the Newton map N(x)=x−f(x)f′(x)N(x)=x-\frac{f(x)}{f'(x)} why the iteration can never escape.

(c) Show ff has exactly one real root and locate it by running Newton from x0=−2x_0=-2 for four steps (1010 decimal places).

Show hint

For (a) just compute two steps by hand. For (c), find the local extreme values of ff and check their signs.

Show answer

(a) f(x)=x3−2x+2f(x)=x^3-2x+2, f′(x)=3x2−2f'(x)=3x^2-2.

x1=0−f(0)f′(0)=0−2−2=1,x2=1−f(1)f′(1)=1−1−2+23−2=1−11=0.x_1=0-\frac{f(0)}{f'(0)}=0-\frac{2}{-2}=1,\qquad x_2=1-\frac{f(1)}{f'(1)}=1-\frac{1-2+2}{3-2}=1-\frac{1}{1}=0.

So x2=x0=0x_2=x_0=0 and the iteration repeats forever: 0, 1, 0, 1, 0,…0,\,1,\,0,\,1,\,0,\dots — a 2-cycle. It never converges, and ff is never zero at either point (f(0)=2f(0)=2, f(1)=1f(1)=1).

(b) The Newton map here satisfies N(0)=1N(0)=1 and N(1)=0N(1)=0, so N(N(0))=0N(N(0))=0: the pair {0,1}\{0,1\} is a periodic orbit of NN. Because the iteration is deterministic — xn+1x_{n+1} depends only on xnx_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)=3x2−2=0f'(x)=3x^2-2=0 at x=±2/3=±0.8164965809x=\pm\sqrt{2/3}=\pm0.8164965809. These are the only critical points, and

f(−23)=2+4323=3.0886621079>0 (local max),f(23)=2−4323=0.9113378921>0 (local min).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>0f>0 on [−2/3,∞)\left[-\sqrt{2/3},\infty\right), so all real roots lie to the left of the local max, where ff is increasing; an increasing function crosses zero at most once. And f(−2)=−8+4+2=−2<0f(-2)=-8+4+2=-2<0 while f(−1)=−1+2+2=3>0f(-1)=-1+2+2=3>0, so by the IVT the unique real root lies in (−2,−1)(-2,-1).

Newton from x0=−2x_0=-2.

f(−2)=−2, f′(−2)=10⇒x1=−2−−210=−1.8f(−1.8)=−5.832+3.6+2=−0.232, f′(−1.8)=3(3.24)−2=7.72⇒x2=−1.8+0.2327.72=−1.7699481865f(x2)=−0.0048496619, f′(x2)=7.3981497490⇒x3=−1.7692926629f(x3)=−0.0000022814, f′(x3)=7.3911895810⇒x4=−1.7692923542\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→1→0→⋯0\to1\to0\to\cdots; the unique real root is r≈−1.7692923542r\approx-1.7692923542. Check: (−1.7692923542)3−2(−1.7692923542)+2=2.9×10−10≈0(-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)f(-2)<0<f(-1) tells you to start near −2-2, not at 00).

Let f(x)=x2−4f(x)=x^2-4 (roots ±2\pm2).

(a) What happens to Newton's method at x0=0x_0=0?

(b) Compute x1x_1 for x0=0.001x_0=0.001 and explain the size of the answer geometrically.

(c) Show that once xnx_n is large the iteration roughly halves it, and estimate how many steps are needed before the fast convergence kicks in. (The exact count is 1515 steps to reach 22 to 1212 decimal places.)

(d) Contrast with x0=3x_0=3: run Newton to full accuracy.

Show hint

Write the simplified iteration xn+1=12(xn+4xn)x_{n+1}=\frac12\left(x_n+\frac{4}{x_n}\right) and think about which of the two terms dominates when xnx_n is huge.

Show answer

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

xn+1=xn−xn2−42xn=xn2+42xn=12(xn+4xn).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)=0f'(0)=0, so x1=0−f(0)f′(0)=0−−40x_1=0-\dfrac{f(0)}{f'(0)}=0-\dfrac{-4}{0} is undefined. Geometrically, x=0x=0 is the vertex of the parabola; the tangent there is the horizontal line y=−4y=-4, which never meets the xx-axis. Newton's method simply cannot start here.

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

x1=0.001−−3.9999990.002=0.001+1999.9995=2000.0005.x_1=0.001-\frac{-3.999999}{0.002}=0.001+1999.9995=2000.0005 .

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

(c) For large xnx_n the term 4/xn4/x_n is negligible next to xnx_n, so xn+1=12(xn+4xn)≈xn2.x_{n+1}=\frac12\left(x_n+\frac{4}{x_n}\right)\approx\frac{x_n}{2}. Halving from 20002000 down to about 22 needs nn with 2000/2n≈22000/2^{n}\approx2, i.e. 2n≈10002^{n}\approx1000, so n≈log⁡21000≈10n\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,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. 1515 steps in total — eleven wasted crawling back, then four fast ones.

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

x1=12(3+43)=136=2.1666666667x2=12(2.1666666667+1.8461538462)=313156=2.0064102564x3=12(2.0064102564+1.9936102236)=19531397656=2.0000102400\begin{aligned} 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 en+1=en22xne_{n+1}=\dfrac{e_n^{2}}{2x_n} (see the quadratic-convergence problem): with e3=1.02400×10−5e_3=1.02400\times10^{-5}, e4=(1.024×10−5)22(2.00001024)=2.6214×10−11,x4=2.0000000000262.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 1010 correct decimals. Moral: the method is only as good as x0x_0; bracket with the IVT and keep ∣f′(x0)∣|f'(x_0)| comfortably away from 00.

Let f(x)=x2−2f(x)=x^2-2 and let r=2r=\sqrt2, en=xn−2e_n=x_n-\sqrt2.

(a) Prove the exact identity en+1=en22xne_{n+1}=\dfrac{e_n^{2}}{2x_n}.

(b) Starting from x0=1x_0=1, compute e1,e2,e3,e4e_1,e_2,e_3,e_4 and describe the pattern in the number of correct decimal places.

(c) Show that once xn∈(2,1.5]x_n\in\left(\sqrt2,1.5\right] we have en+1≤0.354 en2e_{n+1}\le 0.354\,e_n^{2}, and use this to predict the accuracy of xn+1x_{n+1} if xnx_n is correct to 66 decimals.

(d) Derive the general error formula en+1=f′′(ξn)2f′(xn)en2e_{n+1}=\dfrac{f''(\xi_n)}{2f'(x_n)}e_n^{2} and confirm it is consistent with (a).

Show hint

For (a) substitute the simplified iteration xn+1=12(xn+2xn)x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right) into xn+1−2x_{n+1}-\sqrt2 and put everything over 2xn2x_n — a perfect square appears.

Show answer

(a) The simplified iteration is xn+1=xn2+22xnx_{n+1}=\dfrac{x_n^{2}+2}{2x_n}. Hence

en+1=xn+1−2=xn2+22xn−2=xn2+2−22 xn2xn=xn2−22 xn+(2)22xn=(xn−2)22xn=en22xn,\begin{aligned} 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=(2)22=\left(\sqrt2\right)^{2}. Two immediate consequences: the error is squared each step, and (for xn>0x_n>0) en+1>0e_{n+1}>0 — after one step every iterate overshoots above 2\sqrt2.

(b) From x0=1x_0=1: x1=1.5x_1=1.5, x2=1.4166666667x_2=1.4166666667, x3=1.4142156863x_3=1.4142156863, x4=1.4142135624x_4=1.4142135624, and 2=1.4142135623730950\sqrt2=1.4142135623730950.

e1=8.578644×10−2,e2=2.453104×10−3,e3=2.123901×10−6,e4=1.594862×10−12.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): e2=e122x1=(0.0857864376)23=0.00735931293=0.0024531043e_2=\dfrac{e_1^{2}}{2x_1}=\dfrac{(0.0857864376)^{2}}{3}=\dfrac{0.0073593129}{3}=0.0024531043 ✓ (matches exactly).

Correct decimal places: about 11, then 22, then 55, then 1111 — the count doubles each iteration (writing Ln=−log⁡10enL_n=-\log_{10}e_n gives L1,…,L4=1.07, 2.61, 5.67, 11.80L_1,\dots,L_4=1.07,\,2.61,\,5.67,\,11.80, which satisfy Ln+1≈2Ln+0.45L_{n+1}\approx 2L_n+0.45, the 0.450.45 being −log⁡100.354-\log_{10}0.354).

(c) If xn>2x_n>\sqrt2 then 2xn>22=2.82842712x_n>2\sqrt2=2.8284271, so en+1=en22xn<en222=0.3535534 en2≤0.354 en2.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 xn≤1.5x_n\le1.5 is not even needed for this direction; it only tells us en+1≥en2/3e_{n+1}\ge e_n^2/3.) So if xnx_n is correct to 66 decimals, en≤5×10−7e_n\le5\times10^{-7} and en+1≤0.354(5×10−7)2=8.85×10−14,e_{n+1}\le0.354\left(5\times10^{-7}\right)^{2}=8.85\times10^{-14}, i.e. xn+1x_{n+1} is correct to about 1313 decimal places — one step turns 66 digits into 1313.

(d) Taylor-expand ff about xnx_n and evaluate at the root rr (valid because ff is twice differentiable): for some ξn\xi_n strictly between xnx_n and rr,

0=f(r)=f(xn)+f′(xn)(r−xn)+f′′(ξn)2(r−xn)2.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′(xn)≠0f'(x_n)\ne0:

0=f(xn)f′(xn)+(r−xn)+f′′(ξn)2f′(xn)(xn−r)2,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

(xn−f(xn)f′(xn))−r=f′′(ξn)2f′(xn)(xn−r)2,\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 xn+1x_{n+1}, so

en+1=f′′(ξn)2f′(xn) en2.e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}\,e_n^{2}.

Consistency. For f(x)=x2−2f(x)=x^2-2 we have f′′≡2f''\equiv2 and f′(xn)=2xnf'(x_n)=2x_n, so the general formula reads en+1=22⋅2xnen2=en22xne_{n+1}=\dfrac{2}{2\cdot 2x_n}e_n^{2}=\dfrac{e_n^{2}}{2x_n} — exactly part (a), with no unknown ξn\xi_n left over because f′′f'' is constant. The limiting constant is ∣f′′(r)∣2∣f′(r)∣=22⋅22=122=0.3536\dfrac{|f''(r)|}{2|f'(r)|}=\dfrac{2}{2\cdot2\sqrt2}=\dfrac{1}{2\sqrt2}=0.3536, agreeing with (c).

Let f(x)=x3−3x2+4f(x)=x^3-3x^2+4.

(a) Verify that f(x)=(x−2)2(x+1)f(x)=(x-2)^2(x+1), so x=2x=2 is a double root.

(b) Run Newton's method from x0=3x_0=3 for four steps and tabulate the errors en=xn−2e_n=x_n-2 and the ratios en+1/ene_{n+1}/e_n. What kind of convergence is this?

(c) Prove that for a root of multiplicity mm the ratio tends to 1−1m1-\frac1m.

(d) Use the modified iteration xn+1=xn−2f(xn)f′(xn)x_{n+1}=x_n-2\frac{f(x_n)}{f'(x_n)} from x0=3x_0=3 and compare.

Show hint

For (c), write f(x)=(x−r)mg(x)f(x)=(x-r)^m g(x) with g(r)≠0g(r)\ne0, compute f′f' by the product rule, and cancel the common factor of (x−r)m−1(x-r)^{m-1} before taking the limit.

Show answer

(a) Expand: (x−2)2(x+1)=(x2−4x+4)(x+1)=x3+x2−4x2−4x+4x+4=x3−3x2+4(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)=0f(2)=0, and f′(x)=3x2−6x=3x(x−2)f'(x)=3x^2-6x=3x(x-2) gives f′(2)=0f'(2)=0 while f′′(x)=6x−6f''(x)=6x-6 gives f′′(2)=6≠0f''(2)=6\ne0: the root x=2x=2 has multiplicity exactly m=2m=2. Note f′(r)=0f'(r)=0, so the quadratic-convergence theorem does not apply.

(b) Plain Newton, xn+1=xn−xn3−3xn2+43xn2−6xnx_{n+1}=x_n-\dfrac{x_n^3-3x_n^2+4}{3x_n^2-6x_n}. From x0=3x_0=3: f(3)=27−27+4=4f(3)=27-27+4=4, f′(3)=27−18=9f'(3)=27-18=9, so x1=3−49=2.5555555556x_1=3-\frac49=2.5555555556. Continuing (using f=e2(x+1)f=e^2(x+1) and f′=3x(x−2)f'=3x(x-2) to keep the arithmetic clean):

nnxnx_nen=xn−2e_n=x_n-2en/en−1e_n/e_{n-1}
03.00000000001.0000000000—
12.55555555560.55555555560.5556
22.29790660230.29790660230.5362
32.15539019920.15539019920.5216
42.07956221040.07956221040.5120

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

(c) Write f(x)=(x−r)mg(x)f(x)=(x-r)^{m}g(x) with gg differentiable and g(r)≠0g(r)\ne0, and set e=x−re=x-r. By the product rule, f′(x)=m(x−r)m−1g(x)+(x−r)mg′(x)=(x−r)m−1[m g(x)+(x−r)g′(x)].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(x-r)^{m-1}, f(x)f′(x)=e g(x)m g(x)+e g′(x),\frac{f(x)}{f'(x)}=\frac{e\,g(x)}{m\,g(x)+e\,g'(x)} , and the new error is enew=e−e gmg+eg′=e⋅mg+eg′−gmg+eg′=e⋅(m−1)g(x)+e g′(x)m g(x)+e g′(x).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→0e\to0 (so x→rx\to r, g(x)→g(r)≠0g(x)\to g(r)\ne0): enewe→(m−1)g(r)m g(r)=m−1m=1−1m.\frac{e_{\text{new}}}{e}\to\frac{(m-1)g(r)}{m\,g(r)}=\frac{m-1}{m}=1-\frac1m . For m=2m=2 this is 12\frac12, matching the table; for a simple root m=1m=1 the ratio is 00, which is the fingerprint of superlinear (in fact quadratic) convergence.

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

x1=3−2⋅49=3−89=2.1111111111e1=1.111×10−1x2=2.1111111111−2⋅0.03840877910.7037037037=2.0019493177e2=1.949×10−3x3=2.0000006327e3=6.327×10−7x4=2.0000000000e4=6.7×10−14\begin{aligned} 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 →12\to\frac12; the modified step with m=2m=2 restores quadratic convergence, driving the error to 6.7×10−146.7\times10^{-14} (1212 correct decimals) in four steps, where plain Newton still had barely one.

(a) Show that Newton's method applied to f(x)=x1/3f(x)=x^{1/3} gives xn+1=−2xnx_{n+1}=-2x_n, so that it diverges from every x0≠0x_0\ne0 even though ff has the unique root x=0x=0. Which hypothesis fails?

(b) For f(x)=arctan⁡xf(x)=\arctan x (unique root x=0x=0), write down the Newton map and compute four iterates from x0=2x_0=2. It is known that the method diverges exactly when ∣x0∣>x∗|x_0|>x^{*} where x∗=1.3917452x^{*}=1.3917452 satisfies 2x=(1+x2)arctan⁡x2x=\left(1+x^2\right)\arctan x. Explain where that equation comes from.

Show hint

In (a) be careful with the negative exponent: x1/313x−2/3=3x1/3+2/3\frac{x^{1/3}}{\frac13x^{-2/3}}=3x^{1/3+2/3}. In (b), the borderline case is a starting point that Newton sends to its own negative.

Show answer

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

xn+1=xn−xn1/313xn−2/3=xn−3 xn1/3⋅xn2/3=xn−3xn=−2xn.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 ∣xn+1∣=2∣xn∣|x_{n+1}|=2|x_n|, so ∣xn∣=2n∣x0∣→∞|x_n|=2^{n}|x_0|\to\infty for any x0≠0x_0\ne0, while the sign alternates. From x0=0.5x_0=0.5: 0.5, −1, 2, −4, 8, −16, 32,…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 ff to be (twice) continuously differentiable near the root r=0r=0 with f′(r)≠0f'(r)\ne0. Here f′(x)=13x−2/3→+∞f'(x)=\frac13x^{-2/3}\to+\infty as x→0x\to0: ff is not differentiable at the root at all, and f′′(x)=−29x−5/3f''(x)=-\frac29x^{-5/3} is unbounded near 00, so the constant C=max⁡∣f′′∣2min⁡∣f′∣C=\frac{\max|f''|}{2\min|f'|} in the error bound is infinite. Geometrically the graph has a vertical tangent at 00, so tangent lines near the root are steep and point away; each one crosses the axis further out.

(b) f(x)=arctan⁡xf(x)=\arctan x, f′(x)=11+x2f'(x)=\dfrac{1}{1+x^{2}}, which is never zero, so

N(x)=x−arctan⁡x11+x2=x−(1+x2)arctan⁡x.N(x)=x-\frac{\arctan x}{\frac{1}{1+x^{2}}}=x-\left(1+x^{2}\right)\arctan x .

From x0=2x_0=2 (radians):

x1=2−(1+4)arctan⁡2=2−5(1.1071487178)=2−5.5357435890=−3.5357435890x2=−3.5357435890−(13.5014827269)(−1.2951690588)=−3.5357435890+17.4867026759=13.9509590869x3=13.9509590869−(195.6292594451)(1.4992390527)=13.9509590869−293.2950256205=−279.3440665336x4=−279.3440665336−(78034.1075075)(−1.5672165274)=122016.998918\begin{aligned} 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→−3.54→13.95→−279→1.22×1052\to-3.54\to13.95\to-279\to1.22\times10^{5}. (Only the leading digits of x4x_4 are meaningful here — the factors above are themselves rounded, so quoting ten decimals of x4x_4 would be fiction.)

Where 2x=(1+x2)arctan⁡x2x=(1+x^{2})\arctan x comes from. The behaviour is symmetric because NN is odd: N(−x)=−N(x)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 22-cycle x∗→−x∗→x∗→⋯x^{*}\to-x^{*}\to x^{*}\to\cdots. Setting N(x)=−xN(x)=-x:

x−(1+x2)arctan⁡x=−x⇒2x=(1+x2)arctan⁡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.3917452x^{*}=1.3917452. For ∣x0∣<x∗|x_0|<x^{*} each step lands strictly nearer 00 and Newton converges; for ∣x0∣>x∗|x_0|>x^{*} each step lands strictly further away and it diverges; at ∣x0∣=x∗|x_0|=x^{*} it cycles. The cause is that arctan⁡\arctan has flat tails — f′(x)=11+x2→0f'(x)=\frac{1}{1+x^2}\to0 — so far from the root the tangent is nearly horizontal and its xx-intercept is thrown across to the other side. A damped step xn+1=xn−λf(xn)f′(xn)x_{n+1}=x_n-\lambda\frac{f(x_n)}{f'(x_n)} with 0<λ≤10<\lambda\le1 chosen so that ∣f(xn+1)∣<∣f(xn)∣|f(x_{n+1})|<|f(x_n)| cures it.

Find the point on the parabola y=x2y=x^{2} closest to the point (4,0)(4,0), using Newton's method.

(a) Set up the function to minimise, and show it has exactly one critical point which is a global minimum.

(b) Reduce the minimisation to a root-finding problem and bracket the root with the IVT.

(c) Run Newton's method to 1010 decimal places, and state the closest point and the minimum distance.

Show hint

Minimise the square of the distance to avoid a square root, then remember that finding a critical point of DD means running Newton on D′D' — so the iteration involves D′′D''.

Show answer

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

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

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

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

Since D′′(x)=12x2+2≥2>0D''(x)=12x^{2}+2\ge2>0 for all xx, DD is strictly convex for all real xx; hence D′D' is strictly increasing, so D′D' has at most one zero, and any zero is a global minimum. Also D(x)→∞D(x)\to\infty as x→±∞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)=0D'(x)=0, i.e. (dividing by 22)

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

Newton on gg is Newton on D′D', because D′(x)D′′(x)=2(2x3+x−4)2(6x2+1)=g(x)g′(x)\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. gg is continuous; g(1)=2+1−4=−1<0g(1)=2+1-4=-1<0 and g(1.5)=6.75+1.5−4=4.25>0g(1.5)=6.75+1.5-4=4.25>0, so by the IVT there is a root in (1,1.5)(1,1.5). Sharpen: g(1.1)=2(1.331)+1.1−4=−0.238<0g(1.1)=2(1.331)+1.1-4=-0.238<0 and g(1.2)=2(1.728)+1.2−4=0.656>0g(1.2)=2(1.728)+1.2-4=0.656>0, so the root lies in (1.1,1.2)(1.1,1.2). Take x0=1.1x_0=1.1 (note g′(1.1)=8.26g'(1.1)=8.26, comfortably away from 00).

(c) Newton. xn+1=xn−2xn3+xn−46xn2+1x_{n+1}=x_n-\dfrac{2x_n^{3}+x_n-4}{6x_n^{2}+1}.

x1=1.1−−0.2388.26=1.1+0.0288135593=1.1288135593x2=1.1288135593−0.00552730328.6453203103=1.1288135593−0.0006393405=1.1281742188x3=1.1281742188−0.00000276798.6366624084=1.1281742188−0.0000003205=1.1281738983\begin{aligned} 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, x3=1.12817389836x_3=1.12817389836, so the iterates have stabilised at x∗=1.1281738984x^{*}=1.1281738984 to 1010 decimal places. Independent check by sign change: g(1.1281738983)=−5.3×10−10<0g(1.1281738983)=-5.3\times10^{-10}<0 and g(1.1281738984)=+3.3×10−10>0g(1.1281738984)=+3.3\times10^{-10}>0, so the root really is trapped between those two ten-decimal values.

Answer. The closest point is (x∗,(x∗)2)=(1.1281738984,  1.2727763449),\left(x^{*},\left(x^{*}\right)^{2}\right)=\left(1.1281738984,\;1.2727763449\right), and the minimum distance is D(x∗)=(1.1281738984−4)2+(1.1281738984)4=8.2473851578+1.6199596245=9.8673447823=3.1412330035.\sqrt{D(x^{*})}=\sqrt{(1.1281738984-4)^{2}+(1.1281738984)^{4}}=\sqrt{8.2473851578+1.6199596245}=\sqrt{9.8673447823}=3.1412330035 . (That is 3.14123.1412, tantalisingly close to π=3.14159…\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)(4,0) to the closest point should be perpendicular to the parabola. The tangent slope there is 2x∗=2.25634779682x^{*}=2.2563477968, and the segment has slope 1.2727763449−01.1281738984−4=1.2727763449−2.8718261016=−0.4431940862\dfrac{1.2727763449-0}{1.1281738984-4}=\dfrac{1.2727763449}{-2.8718261016}=-0.4431940862; the product is 2.2563477968×(−0.4431940862)=−1.00000000002.2563477968\times(-0.4431940862)=-1.0000000000 ✓.