Iterative improvement

From CS 61A Wiki
Jump to: navigation, search

Iterative improvement is a technique that involves updating an initial guess until it reaches the correct solution. The two major components are an update function and a done function.

The general pattern is:

def iter_solve(guess, done, update):
    while not done(guess):
        guess = update(guess)
    return guess

In practice, the loop may continue forever and not get closer to the solution. To prevent this, we can (1) impose a maximum number of iterations and (2) use a close function (instead of a done function) that checks if the guess is within some tolerance of the solution. In code:

def iter_solve(guess, close, update, iteration_limit=32):
    while not close(guess):
        if iteration_limit <= 0:
            raise ValueError("failed to converge")
        guess = update(guess)
        iteration_limit -= 1
    return guess


Main article: Newton's method#Implemented with iterative improvement