Newton's Method

Description

Newton's Method is a way to solve equations that cannot typically be solved using ordinary techniques of algebra. Newton's method is a series of numerical approximations based that successively get more accurate. Consider the equation $\cos x = x-1$. Normally we would have no way to solve this equation using algebra, but we can make the equation be $\cos x - x + 1 = 0$. Then using the formula

(1)
\begin{align} x_{ n+1 } = x_n - \frac{ f(x_n) }{ f'(x_n) } \end{align}

we can get each successive approximation. Note that this will only work as long as your initial approximation is near the root you are trying to solve for. The Sage code below will approximate the solution for the equation $\cos x = x-1$ with an initial approximation of $x_0 = 1$.

Sage Cell

Code

f(x) = cos(x) - x + 1 
def newton_method(f, c, eps, maxiter=100):
    x = f.variables()[0]
    fprime = f.derivative(x)
    try:
        g = f._fast_float_(x)
        gprime = fprime._fast_float_(x)
    except AttributeError:
        g = f; gprime = fprime
    iterates = [c]
    for i in range(maxiter):
       fc = g(c)
       if abs(fc) < eps: return c, iterates
       c = c - fc/gprime(c)
       iterates.append(c)
    return c, iterates

var('x')    
pretty_print(html("<h1>Double Precision Root Finding Using Newton's Method</h1>"))
@interact
def _(f = x^2 - 2, c = float(0.5), eps=(-3,(-16, -1)), interval=float(0.5)):
     eps = 10^(eps)
     print("eps = %s"%float(eps))
     z, iterates = newton_method(f, c, eps)
     print("root = {}".format(z))
     print("f(c) = %r" % f(x=z))
     n = len(iterates)
     print("iterations = {}".format(n))
     pretty_print(html(iterates))
     P = plot(f, (x,z-interval, z+interval), rgbcolor='blue')
     h = P.ymax(); j = P.ymin()
     L = sum(point((w,(n-1-float(i))/n*h), rgbcolor=(float(i)/n,0.2,0.3), pointsize=10) + \
             line([(w,h),(w,j)],rgbcolor='black',thickness=0.2) for i,w in enumerate(iterates))
     show(P + L, xmin=z-interval, xmax=z+interval)

Options

None

Tags

Primary Tags: Single Variable Calculus: Applications of differentiation

Secondary Tags: Applications of differentiation: Newton's method

Related Cells

None

Attribute

Permalink: https://wiki.sagemath.org/interact/calculus#Newton.27s_Method

Author: William Stein

Date: 04 Dec 2018 11:02

Submitted by: James A Phillips

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License