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