# Difference between revisions of "Newton's method"

From CS 61A Wiki

[unchecked revision] | [checked revision] |

(created) |
(use absolute value when checking difference, fix derivative of x^3) |
||

Line 11: | Line 11: | ||

df = lambda x: 2*x | df = lambda x: 2*x | ||

x = 1 | x = 1 | ||

− | while f(x) > 1e-15: # loops until f(x) is within 1e-15 of 0 | + | while abs(f(x)) > 1e-15: # loops until f(x) is within 1e-15 of 0 |

x = x - f(x)/df(x) | x = x - f(x)/df(x) | ||

return x | return x | ||

</syntaxhighlight> | </syntaxhighlight> | ||

− | To find the cube root of <code>a</code>, use <code>f = lambda x: x**3 - a</code> and <code>df = lambda x: 3*x</code> instead. | + | To find the cube root of <code>a</code>, use <code>f = lambda x: x**3 - a</code> and <code>df = lambda x: 3*(x**2)</code> instead. |

== Implemented with [[iterative improvement]] == | == Implemented with [[iterative improvement]] == |

## Revision as of 13:59, 25 May 2014

**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 `x`

(i.e., find the zero of ^{2} = a`f(x) = x`

). In code:
^{2} – a

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)