# Newton's method

From CS 61A Wiki

*Purge this page if the LaTeX typesetting doesn't render.*

**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 - \frac{f(x)}{f'(x)}$. When $f(x) \approx 0$, we are done.

## Simple examples

To find the square root of $a$, we can solve the equation $x^2 = a$ (i.e., find the zero of $f(x) = x^2 - 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)