Newton's method

From CS 61A Wiki
Revision as of 13:59, 25 May 2014 by (Talk)

Jump to: navigation, search

Newton's method approximates the zeroes of differentiable functions.

Given a function f and an initial guess x, repeatedly apply the following equation to get an improved guess: x = x – f(x)/f'(x). When f(x) ≈ 0, we are done.

Simple examples

To find the square root of a, we can solve the equation x2 = a (i.e., find the zero of f(x) = x2 – a). In code:

def square_root(a):
    """Return the square root of A with a tolerance of 1e-15."""
    f = lambda x: x**2 - a
    df = lambda x: 2*x
    x = 1
    while abs(f(x)) > 1e-15: # loops until f(x) is within 1e-15 of 0
        x = x - f(x)/df(x)
    return x

To find the cube root of a, use f = lambda x: x**3 - a and df = lambda x: 3*(x**2) instead.

Implemented with iterative improvement

def newton_solve(f, df, guess, tolerance):
    def close(x):
        return abs(f(x)) < tolerance
    def newton_update(x):
        return x - f(x) / df(x)
    return iter_solve(guess, close, newton_update, 1000000000)