If you need help reviewing Newton's method, take a look at these resources:
We will be using the implementation of Newton's method and iterative improvement from lecture:
# iterative improvement framework
def improve(update, close, guess=1):
while not close(guess):
guess = update(guess)
return guess
def approx_eq(x, y, tolerance=1e-5):
return abs(x - y) < tolerance
# Newton's method
def make_derivative(f, delta=1e-5):
def derivative(x):
df = f(x + delta) - f(x)
return df / delta
return derivative
def newton_update(f, df):
def update(x):
return x - f(x) / df(x)
return update
def find_zero(f, df):
def near_zero(x):
return approx_eq(f(x), 0)
return improve(newton_update(f, df), near_zero)""")
Each question has a "Toggle Solution" button -- click it to reveal that question's solution.
Conceptual Questions
Question 1
Describe what iterative improvement is and how it works.
Iterative improvement is a programming technique that involves updating
an initial guess until it comes close enough to the correct solution.
Iterative improvement algorithms have two major components: an
update
function; and an close
function (which tells you
when you can stop).
Question 2
Conceptually, what is the update
function for Newton's method? What
is the close
function for Newton's method?
def newton_update(f, df):
def update(x):
return x - f(x) / df(x)
return update
# the following is defined inside find_zero
def near_zero(x):
return approx_eq(f(x), 0)
newton_update
is not the actual update function — instead,
depending on what f
is given, it will create an update
function
that follows the mathematical equation for Newton's Method.
near_zero
is the close
function, and returns True when f(x)
is
approximately equal to 0 — this is the goal of Newton's method.