Newton's method is a way of finding a zero of a function by iteratively improving on an initial guess or approximation. The idea is to evaluate both the function and its derivative at the point specified by the initial guess. Dividing the function value by the value of the derivative gives an estimate of the error, that is, the amount by which the guess differs from a zero of the function. Subtracting this error estimate from the initial guess should produce a better approximation.
(Note, however, that it is possible for the error estimate to be so far off that the supposedly better approximation is actually farther from the zero than the original. A more sophisticated version of this collection of procedures would try to detect such unfavorable circumstances.)
(define improve
(lambda (initial-guess function derivative)
(- initial-guess (/ (function initial-guess)
(derivative initial-guess)))))
The following procedure iterates this operation until successive values
differ by less than a given amount epsilon:
(define newton
(lambda (initial-guess function derivative epsilon)
(let loop ((old-guess initial-guess)
(new-guess (improve initial-guess function derivative)))
(if (< (abs (- new-guess old-guess)) epsilon)
new-guess
(loop new-guess (improve new-guess function derivative))))))
To compute the square root of a given real number a to eight decimal
places, invoke newton with appropriate arguments: 1, perhaps,
for the initial guess; x^2 - a as the function, and hence
2x as the derivative; and 0.00000001 for epsilon:
(define square-root
(lambda (a)
(newton 1
(lambda (x) (- (* x x) a))
(lambda (x) (* 2 x))
1e-8)))
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/events/scheme-workshop/newton.html