## Blob

1 ;; The first three lines of this file were inserted by DrScheme. They record metadata2 ;; about the language level of this file in a form that our tools can easily process.3 #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |27.4|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))4 (define TOLERANCE 0.0001)6 ;newton : (number -> number) number -> number7 ;Given f, ig (initial guess), find the root of f using Newton's Method.8 ;TERMINATION ARGUMENT: There is no guarantee that newton will terminate.10 (define (newton f ig)11 (cond12 [(<= (abs (f ig)) TOLERANCE) ig]13 [else (newton f (find-root-tangent f ig))]))15 ;find-root-tangent : (number -> number) number -> number16 ;Finds the root of the tangent line to f at point x.18 (define (find-root-tangent f x)19 (local ((define fprime (d/dx f TOLERANCE)))20 (- x (/ (f x)21 (fprime x)))))23 ;d/dx : (number -> number) number -> (number -> number)24 ;Returns f', the slope of f, given epsilon e.26 (define (d/dx f e)27 (local ((define (slope x) (/ (- (f (+ x e))28 (f (- x e)))29 (* 2 e))))30 slope))32 ;find-root : (number -> number) number number -> number33 ;Given f, left and right, approximate a root by using a binary search. find-root returns the left interval once the interval size is less than tolerance. find-root uses generative recursion to find the root--it splits the interval in half and finds the root for one half of the interval.34 ;Assume that (<= (f left) 0 (f right)) or (<= (f right) 0 (f left)).35 ;Termination argument: Each interval is half the size of the previous interval. Hence, the nth recursive call has an interval of initial * (1/2)^n, where initial is the size of the initial interval. As n-> infinity, the interval approaches zero, which implies that this function must terminate for any value of tolerance greater than zero.37 (define (find-root f left right)38 (local ((define mid (/ (+ left right) 2))39 (define f-mid (f mid)))40 (cond41 [(<= (- right left) TOLERANCE) left]42 [(or (<= (f left) 0 f-mid)43 (>= (f left) 0 f-mid)) (find-root f left mid)]44 [else (find-root f mid right)])))46 (time (find-root (lambda (x) (- (* (expt x 3)47 (exp x))48 (cos x)))49 0 1000))50 (time (newton (lambda (x) (- (* (expt x 3)51 (exp x))52 (cos x)))53 500))