Newton's method

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 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` 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)```