∑Richard Hummel Math

Newton's Method

Iteratively finding roots of a function by following the tangent line at each guess — converges quadratically near a root.

Newton's method for x^2 - 2: use the tangent line to choose the next guess
0.91.11.31.51.7actual rootcurrent guessnext guessxf(x)
iteration 0

Start at x = 1.000000, where f(x) = -1.000000.

The tangent line is the local straight-line approximation to the curve.

Where that tangent hits the x-axis becomes x = 1.50000000.

xnext= x - f(x) / f'(x)
For f(x) = x^2 - 2, this quickly moves toward sqrt(2).
step 0
Definition

Newton's Method (also called the Newton-Raphson method) is an iterative algorithm for finding roots of a function f(x)=0f(x) = 0.

Starting from an initial guess x0x_0, the iteration is:

xn+1=xn−f(xn)fâ€ē(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

Geometric idea: At each step, draw the tangent line to y=f(x)y = f(x) at (xn,f(xn))(x_n, f(x_n)). The tangent line intersects the xx-axis at xn+1x_{n+1}. Under mild conditions, successive tangent line intercepts converge to the root.

The tangent line at xnx_n has equation y=f(xn)+fâ€ē(xn)(x−xn)y = f(x_n) + f'(x_n)(x - x_n). Setting y=0y = 0: xn+1=xn−f(xn)fâ€ē(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

Finding √2 with Newton's Method

2\sqrt{2} is the positive root of f(x)=x2−2f(x) = x^2 - 2, so fâ€ē(x)=2xf'(x) = 2x.

xn+1=xn−xn2−22xn=xn2+1xnx_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n}{2} + \frac{1}{x_n}

Starting with x0=1x_0 = 1:

nnxnx_nxn2−2x_n^2 - 2
01.0−1-1
11.50.250.25
21.41\overline60.006940.00694
31.41421356â€Ķ≈10−8\approx 10^{-8}

Correct to 8 significant figures after just 3 iterations.

Try it

Use Newton's Method with x0=3x_0 = 3 to approximate 10\sqrt{10} to four decimal places. Perform three iterations.

Solution

f(x)=x2−10f(x) = x^2 - 10, fâ€ē(x)=2xf'(x) = 2x. Iteration: xn+1=xn2+5xnx_{n+1} = \frac{x_n}{2} + \frac{5}{x_n}.

x1=32+53=1.5+1.66â€ū=3.16â€ūx_1 = \frac{3}{2} + \frac{5}{3} = 1.5 + 1.6\overline{6} = 3.1\overline{6}

x2=3.16â€ū2+53.16â€ū≈1.583+1.579=3.1623x_2 = \frac{3.1\overline{6}}{2} + \frac{5}{3.1\overline{6}} \approx 1.583 + 1.579 = 3.1623

x3≈3.16228x_3 \approx 3.16228

True value: 10≈3.16228\sqrt{10} \approx 3.16228. Three iterations from x0=3x_0 = 3 gives 5 correct decimal places.

Related concepts

View in full concept graph →