Difference between revisions of "Newton's method"

From CS 61A Wiki
Jump to: navigation, search
[unchecked revision][checked revision]
(created)
 
m ({{Purge}})
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{Sufficient-class}}
 +
{{Purge}}
 
'''Newton's method''' approximates the zeroes of differentiable functions.
 
'''Newton's method''' approximates the zeroes of differentiable functions.
  
Given a function <code>f</code> and an initial guess <code>x</code>, repeatedly apply the following equation to get an improved guess: <code>x = x f(x)/f'(x)</code>. When <code>f(x) 0</code>, we are done.
+
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 ==
 
== Simple examples ==
To find the square root of <code>a</code>, we can solve the equation <code>x<sup>2</sup> = a</code> (i.e., find the zero of <code>f(x) = x<sup>2</sup> – a</code>). In code:
+
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:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
def square_root(a):
 
def square_root(a):
Line 11: Line 13:
 
     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 $a$, 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]] ==

Latest revision as of 10:24, 13 June 2014

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)

Sources