Learn4Less Logo

Navigation

Home

Learn

CoursesServicesCompetition MathConcept Review

Tools

WeBWorK WorkshopGrade CalculatorDerivative CalculatorIntegral CalculatorUBC Grade StatisticsMath 100 Readiness Check

More

Free Resources (Blog)ContactJoin Our TeamPrivacy PolicyTerms & Conditions

Our Other Platforms

Approximation · Topic 21 of 23

Newton's Method

Newton's method solves f(x)=0f(x)=0 by replacing the curve with its tangent at the current guess and zeroing that line instead: xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. Near a simple root it roughly doubles the number of correct digits each step, but every step needs f′(xn)≠0f'(x_n)\neq0 and a starting guess near the root you actually want.

5 min readFrequent on exams7 formulas6 quick checks
01

Key ideas

5 things to remember
  1. 1

    Each step zeroes the tangent line

    The tangent at (xn,f(xn))(x_n,f(x_n)) is L(x)=f(xn)+f′(xn)(x−xn)L(x)=f(x_n)+f'(x_n)(x-x_n). Solving the easy equation L(x)=0L(x)=0 gives xn+1x_{n+1}. Newton is linear approximation applied over and over.

  2. 2

    Every step needs f′(xn)≠0f'(x_n)\neq0

    A horizontal tangent has no xx-intercept, so xn+1x_{n+1} does not exist. A nearly horizontal one is almost as bad: for f(x)=x2−4f(x)=x^2-4, x0=0.001x_0=0.001 gives x1=2000.0005x_1=2000.0005.

  3. 3

    Correct digits roughly double

    At a simple root (f′(r)≠0f'(r)\neq0) the error obeys en+1≈f′′(r)2f′(r)en2e_{n+1}\approx\frac{f''(r)}{2f'(r)}e_n^{2}. Three or four steps from a decent start give ten decimals — so carry about twice the digits you intend to report.

  4. 4

    Bracket with the IVT before you iterate

    A sign change f(a)f(b)<0f(a)f(b)<0 on a continuous ff traps a root, and f′f' of one sign makes it unique. Bisect two or three times, then start Newton from the midpoint.

  5. 5

    Newton can cycle, diverge or crawl

    x3−2x+2x^3-2x+2 from x0=0x_0=0 cycles 0,1,0,1,…0,1,0,1,\dots; f(x)=x1/3f(x)=x^{1/3} doubles its distance from the root each step; at a double root the error only halves. Never assume convergence.

1.21.41.61.82.02.2123xytangent at x₀x₀ = 2x₁ = 1.5(x₀, f(x₀))√2 ≈ 1.4142y = x² − 2
One Newton step on f(x)=x2−2f(x)=x^2-2: the tangent at (2,2)(2,2) has slope 44 and meets the axis at x1=1.5x_1=1.5. Repeating gives 1.41666666671.4166666667, then 1.41421568631.4142156863, then 1.41421356241.4142135624 — the error falls from 8.6×10−28.6\times10^{-2} to 1.6×10−121.6\times10^{-12}.
-2.0-1.5-1.0-0.50.51.01.5-224xytangent at x₀tangent at x₁x₀ = 0x₁ = 1the real root ≈ −1.769y = x³ − 2x + 2
Failure by cycling: on f(x)=x3−2x+2f(x)=x^3-2x+2 the tangent at (0,2)(0,2) lands on x1=1x_1=1, and the tangent at (1,1)(1,1) sends you straight back to 00. The iterates repeat 0,1,0,1,…0,1,0,1,\dots forever and never reach the real root near −1.769-1.769.
02

Formulas

What to have memorised

  • 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

    Minus, always — and f′(xn)≠0f'(x_n)\neq0 at every step.

  • Where the step comes from

    0=f(xn)+f′(xn)(xn+1−xn)0=f(x_n)+f'(x_n)\left(x_{n+1}-x_n\right)

    The tangent at xnx_n crosses the axis at xn+1x_{n+1}.

  • Square roots: f(x)=x2−af(x)=x^{2}-a

    xn+1=12(xn+axn)x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)

    Simplify the step to one fraction before substituting numbers.

  • Error law (en=xn−re_n=x_n-r)

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

    ξn\xi_n lies between xnx_n and rr; this is quadratic convergence.

  • Critical point of gg

    xn+1=xn−g′(xn)g′′(xn)x_{n+1}=x_n-\frac{g'(x_n)}{g''(x_n)}

    Optimising means running Newton on g′g', so the step uses g′′g''.

  • Root of multiplicity mm

    xn+1=xn−m f(xn)f′(xn)x_{n+1}=x_n-m\,\frac{f(x_n)}{f'(x_n)}

    Plain Newton only halves the error at a double root; this restores speed.

  • Bisection bracket after nn steps

    length=b−a2n\text{length}=\frac{b-a}{2^{n}}

    Safe but slow: about 3.33.3 steps per decimal digit.

03

Run Newton's method on an exam

The steps, in order
  1. 1

    Move everything to one side so the question reads f(x)=0f(x)=0, then differentiate to get f′f'.

  2. 2

    Bracket the root: find a<ba<b with f(a)f(a) and f(b)f(b) of opposite signs, and check f′f' has one sign there.

  3. 3

    Pick x0x_0 inside the bracket with ∣f′(x0)∣\left|f'(x_0)\right| comfortably away from 00; two bisections give a safe one.

  4. 4

    Simplify xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} to a single fraction before any numbers go in.

  5. 5

    Iterate in radians, carrying about twice the digits you will report.

  6. 6

    Stop when ∣xn+1−xn∣\left|x_{n+1}-x_n\right| is under the tolerance and ∣f(xn+1)∣\left|f(x_{n+1})\right| is small; quote only the digits that have stopped changing.

04

Watch out

The mistakes that cost marks

  • ✗ 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)}

    Why: On x2−2x^2-2 from x0=1x_0=1 the minus gives 1.51.5; the plus gives 0.50.5, away from 2\sqrt2.

  • ✗ Wrong

    For cos⁡x=x\cos x=x, taking f(x)=cos⁡xf(x)=\cos x

    ✓ Right

    f(x)=cos⁡x−xf(x)=\cos x-x, so f′(x)=−sin⁡x−1f'(x)=-\sin x-1.

    Why: Newton finds zeros, not intersections — and the −1-1 is easy to drop.

  • ✗ Wrong

    Rounding each xnx_n to four decimals as you go

    ✓ Right

    Carry ten digits through and round once at the end.

    Why: Rounding caps the answer's accuracy no matter how many steps you take.

  • ✗ Wrong

    "f(xn)f(x_n) is tiny, so xnx_n is close to the root."

    ✓ Right

    Check ∣xn+1−xn∣\left|x_{n+1}-x_n\right| too.

    Why: For (x−1)3(x-1)^3 at x=1.1x=1.1, f=0.001f=0.001 but the error is 0.10.1.

  • ✗ Wrong

    To minimise gg, iterating xn+1=xn−g(xn)g′(xn)x_{n+1}=x_n-\frac{g(x_n)}{g'(x_n)}

    ✓ Right

    Run Newton on g′g': xn+1=xn−g′(xn)g′′(xn)x_{n+1}=x_n-\frac{g'(x_n)}{g''(x_n)}.

    Why: The first finds a root of gg, not a critical point.

  • ✗ Wrong

    "Newton's method always converges."

    ✓ Right

    It can cycle, diverge, or converge to a different root — bracket first.

05

Quick check

Commit to an answer before you reveal one
  1. Q1easy

    Use Newton's method with f(x)=x2−5f(x)=x^2-5 and x0=2x_0=2 to approximate 5\sqrt5. Simplify the iteration first, then give x1x_1, x2x_2 and x3x_3 to 1010 decimal places.

    Hint

    Put xn−xn2−52xnx_n-\frac{x_n^2-5}{2x_n} over the common denominator 2xn2x_n before any numbers go in.

    Show answer

    Answer

    xn+1=12(xn+5xn)x_{n+1}=\frac12\left(x_n+\frac{5}{x_n}\right); x1=2.25x_1=2.25, x2=2.2361111111x_2=2.2361111111, x3=2.2360679779x_3=2.2360679779.

    Steps

    f′(x)=2xf'(x)=2x, so

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

    From x0=2x_0=2: x1=12(2+2.5)=2.25x_1=\frac12(2+2.5)=2.25; x2=12(2.25+2.2222222222)=2.2361111111x_2=\frac12(2.25+2.2222222222)=2.2361111111; x3=12(2.2361111111+2.2360248447)=2.2360679779x_3=\frac12(2.2361111111+2.2360248447)=2.2360679779.

    Against 5=2.2360679775\sqrt5=2.2360679775 the errors are 1.4×10−21.4\times10^{-2}, 4.3×10−54.3\times10^{-5}, 4.2×10−104.2\times10^{-10}: the correct-digit count doubles each step. Report 5≈2.23606798\sqrt5\approx2.23606798 — the last digits of x3x_3 are not yet settled.

  2. Q2easy

    (a) Derive Newton's iteration from the tangent line to y=f(x)y=f(x) at x=xnx=x_n.

    (b) State the hypothesis it needs, and say what goes wrong geometrically when it fails.

    (c) Show that for f(x)=mx+bf(x)=mx+b with m≠0m\neq0 one step from any x0x_0 lands on the exact root.

    Show answer

    Answer

    (a) xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. (b) f′(xn)≠0f'(x_n)\neq0; a horizontal tangent never meets the axis. (c) x1=−bmx_1=-\frac{b}{m}.

    Steps

    (a) The tangent is L(x)=f(xn)+f′(xn)(x−xn)L(x)=f(x_n)+f'(x_n)(x-x_n). Setting L(xn+1)=0L(x_{n+1})=0 gives f′(xn)(xn+1−xn)=−f(xn)f'(x_n)(x_{n+1}-x_n)=-f(x_n), so

    xn+1=xn−f(xn)f′(xn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

    (b) That division needs f′(xn)≠0f'(x_n)\neq0. If f′(xn)=0f'(x_n)=0 the tangent is horizontal: it either misses the xx-axis entirely or is the axis, so there is no next iterate.

    (c) x1=x0−mx0+bm=−bmx_1=x_0-\frac{mx_0+b}{m}=-\frac{b}{m}, the exact root. Newton is exact on lines, so each step's whole error is the gap between ff and its tangent — a quantity of size en2e_n^{2}.

  3. Q3medium

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

    (a) Show ff has exactly one real root and that it lies in (0,1)(0,1).

    (b) Take two bisection steps and let x0x_0 be the midpoint of the surviving interval.

    (c) Run two Newton steps from that x0x_0, to 1010 decimal places.

    Hint

    For (b) you only need the signs of f(0.5)f(0.5) and f(0.75)f(0.75).

    Show answer

    Answer

    (a) f(0)=−1<0<1=f(1)f(0)=-1<0<1=f(1) and f′>0f'>0. (b) x0=0.625x_0=0.625. (c) x1=0.6852517986x_1=0.6852517986, x2=0.6823350904x_2=0.6823350904.

    Steps

    (a) ff is continuous with f(0)=−1f(0)=-1 and f(1)=1f(1)=1, so the IVT gives a root in (0,1)(0,1); f′(x)=3x2+1≥1>0f'(x)=3x^2+1\ge1>0 makes ff strictly increasing, so there is at most one.

    (b) f(0.5)=−0.375<0f(0.5)=-0.375<0, so the root is in (0.5,1)(0.5,1); f(0.75)=0.171875>0f(0.75)=0.171875>0, so it is in (0.5,0.75)(0.5,0.75). Midpoint: x0=0.625x_0=0.625.

    (c) f(0.625)=−0.130859375f(0.625)=-0.130859375, f′(0.625)=2.171875f'(0.625)=2.171875, giving x1=0.6852517986x_1=0.6852517986. Then f(x1)=0.0070255044f(x_1)=0.0070255044, f′(x1)=2.4087100823f'(x_1)=2.4087100823, giving x2=0.6823350904x_2=0.6823350904. The root is 0.68232780380.6823278038 — bisection alone would need 1717 steps for that accuracy.

  4. Q4medium

    (a) Run Newton on f(x)=x3−2x+2f(x)=x^3-2x+2 from x0=0x_0=0 for two steps. What happens, and can the iteration ever escape?

    (b) For f(x)=x2−4f(x)=x^2-4, compute x1x_1 from x0=0.001x_0=0.001 and explain the size of the answer geometrically.

    Show answer

    Answer

    (a) x1=1x_1=1, x2=0x_2=0: the 22-cycle 0,1,0,1,…0,1,0,1,\dots, which never escapes. (b) x1=2000.0005x_1=2000.0005 — the tangent is almost horizontal, so it meets the axis about 20002000 away.

    Steps

    (a) f′(x)=3x2−2f'(x)=3x^2-2, so x1=0−2−2=1x_1=0-\frac{2}{-2}=1 and x2=1−11=0x_2=1-\frac{1}{1}=0. Since xn+1x_{n+1} depends only on xnx_n, a repeated value repeats forever; neither point is a root (f(0)=2f(0)=2, f(1)=1f(1)=1).

    (b) f(0.001)=−3.999999f(0.001)=-3.999999 and f′(0.001)=0.002f'(0.001)=0.002, so

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

    Climbing from height −4-4 to the axis along a line of slope 0.0020.002 takes a run of about 4/0.002=20004/0.002=2000. Both failures are cured by bracketing the root first.

  5. Q5medium

    Apply Newton's method to f(x)=1x−af(x)=\frac1x-a, where a>0a>0.

    (a) Show the iteration simplifies to xn+1=xn(2−axn)x_{n+1}=x_n(2-ax_n), which uses no division.

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

    (c) With a=7a=7 and x0=0.1x_0=0.1, compute x1x_1 through x4x_4.

    Hint

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

    Show answer

    Answer

    (c) x1=0.13x_1=0.13, x2=0.1417x_2=0.1417, x3=0.14284777x_3=0.14284777, x4=0.1428571422x_4=0.1428571422, against 17=0.1428571429\frac17=0.1428571429.

    Steps

    (a) f′(x)=−1x2f'(x)=-\frac{1}{x^{2}}, which is never 00, so

    xn+1=xn−1xn−a−1xn2=xn+xn2(1xn−a)=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\left(2-ax_n\right).

    (b) xn+1−1a=2xn−axn2−1a=−a(xn2−2axn+1a2)=−a(xn−1a)2x_{n+1}-\frac1a=2x_n-ax_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}.

    (c) xn+1=xn(2−7xn)x_{n+1}=x_n(2-7x_n): 0.1(1.3)=0.130.1(1.3)=0.13, 0.13(1.09)=0.14170.13(1.09)=0.1417, then 0.142847770.14284777 and 0.14285714220.1428571422 — an error of 6.1×10−106.1\times10^{-10}, so 88 correct decimals.

  6. Q6hard

    Find the point on y=x2y=x^{2} closest to (4,0)(4,0).

    (a) Write the function to minimise and turn the problem into a root-finding one.

    (b) Bracket that root with the IVT.

    (c) Run Newton to 1010 decimal places, then state the closest point and the distance.

    Hint

    Minimise the square of the distance, and remember a critical point of DD is a root of D′D' — so the step needs D′′D''.

    Show answer

    Answer

    x∗=1.1281738984x^{*}=1.1281738984; closest point (1.1281738984, 1.2727763449)(1.1281738984,\,1.2727763449), distance 3.14123300353.1412330035.

    Steps

    (a) D(x)=(x−4)2+x4D(x)=(x-4)^{2}+x^{4}, so D′(x)=4x3+2x−8D'(x)=4x^{3}+2x-8 and D′′(x)=12x2+2>0D''(x)=12x^{2}+2>0: DD is convex, so its single critical point is the global minimum. Since D′D′′=gg′\frac{D'}{D''}=\frac{g}{g'} with g(x)=2x3+x−4g(x)=2x^{3}+x-4, g′(x)=6x2+1g'(x)=6x^{2}+1, iterate on gg.

    (b) g(1.1)=−0.238<0<0.656=g(1.2)g(1.1)=-0.238<0<0.656=g(1.2), so the root is in (1.1,1.2)(1.1,1.2); take x0=1.1x_0=1.1.

    (c) x1=1.1+0.2388.26=1.1288135593x_1=1.1+\frac{0.238}{8.26}=1.1288135593, x2=1.1281742188x_2=1.1281742188, x3=1.1281738984x_3=1.1281738984. Then y=(x∗)2=1.2727763449y=(x^{*})^{2}=1.2727763449 and the distance is 8.2473851581+1.6199596243=3.1412330035\sqrt{8.2473851581+1.6199596243}=3.1412330035.

06

On the exam

How this topic is marked

  • Marks live in the set-up: the equation moved to f(x)=0f(x)=0, the derivative, the simplified iteration, and one clean substitution. A bare final decimal with no working scores almost nothing.

  • Show each iterate with the f(xn)f(x_n) and f′(xn)f'(x_n) that produced it, carry ten digits, and quote only the digits that have stopped changing. Trig equations are in radians.

  • If the question asks you to justify that a root exists or is unique, that is an IVT sign change plus f′f' of constant sign — do it before you iterate, not after.

Keep going

Stuck on this topic?

One session with a tutor who teaches it every term usually settles it.

Book a session