Newton's Method

Next: Extended Exercise: Gaussian Elimination Up: Variations on a Theme Previous: Binary Search

Newton's Method

Newton invented another method for finding the root of a function. Newton's method exploits the idea of an approximation. To search a root of some function f, we start with a guess, say, r1. Then we study the tangent of f at r1, that is, the line that goes through the Cartesian point (r1, f(r1)) and has the same slope as f. This tangent is a linear approximation of f and it has a root that is in many cases closer to the root of f than our original guess. Hence, by repeating this process sufficiently often, we can find an r for which (f r) is close to 0.

To translate this process description into Scheme, we follow the familiar process. The function--let's call it newton in honor of its inventor--consumes a function f and a number r0, the current guess. If (f r0) is close to 0, the problem is solved. Of course, close to 0 could be mean (f r0) is a small positive number or a small negative number. Hence we translate this idea into

(<= (abs (f r0)) TOLERANCE)

That is, we determine whether the absolute value is small. The answer in this case is r0.

The generative step of the algorithm consists of finding the root of the tangent of f at r0. It generates a new guess. By applying newton to this new guess, we resume the process with what we hope is a better guess:

;; newton : (number -> number) number -> number
;; to find a number r such that (< (abs (f r)) TOLERANCE) 
(define (newton f r0) 
  (cond 
    [(<= (abs (f r0)) TOLERANCE) r0] 
    [else (newton f (find-root-tangent f r0))]))

Since finding the root of a tangent is domain knowledge, we define a separate function for this purpose:

;; find-root-tangent : (number -> number) number -> number
;; to find the root of the tagent of f at r0 
(define (find-root-tangent f r0) 
  (local ((define fprime (d/dx f))) 
    (- r0 
       (/ (f r0) 
          (fprime r0)))))

The function first computes (d/dx f), that is, the derivative of f at r0 (see section

) at r0. The body of the local-expression computes the root from the current guess, (f r0), and the slope of f at r0.

The most interesting aspect of newton is that, unlike all other functions we have discussed, it does not always terminate. Consider the following function:

;; f : number -> number
(define (f x) 
  (- (* x x) x 1.8))

A simple hand-calculation shows that its derivative is

;; fprime : number -> number
(define (fprime x) 
  (- (* 2 x) 1))

If we were to use 1/2 as the initial guess, we would have to find the root of a tangent with slope 0, that is, a tangent that is parallel to the x axis. Of course, such a tangent doesn't have a root. As a result, find-root-of-tangent cannot find a tangent and newton won't find a root.

Exercises Exercise 27.4.1

Test newton with f. Use the initial guesses 1, 2, and 3. Also use find-root from the preceding section to find a root.

Use a hand-evaluation to determine how quickly newton finds a value close to the root (if it finds one). Compare newton's behavior with find-root's behavior.

Employ the strategy of section to formulate the tests as boolean-valued expressions. Solution

Next: Extended Exercise: Gaussian Elimination Up: Variations on a Theme Previous: Binary Search

PLT