1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
 2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
 3 12687dd9 2023-08-04 jrmu #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 12687dd9 2023-08-04 jrmu (define TOLERANCE 0.0001)
 5 12687dd9 2023-08-04 jrmu 
 6 12687dd9 2023-08-04 jrmu ;newton : (number -> number) number -> number
 7 12687dd9 2023-08-04 jrmu ;Given f, ig (initial guess), find the root of f using Newton's Method.
 8 12687dd9 2023-08-04 jrmu ;TERMINATION ARGUMENT: There is no guarantee that newton will terminate.
 9 12687dd9 2023-08-04 jrmu 
10 12687dd9 2023-08-04 jrmu (define (newton f ig)
11 12687dd9 2023-08-04 jrmu   (cond
12 12687dd9 2023-08-04 jrmu     [(<= (abs (f ig)) TOLERANCE) ig]
13 12687dd9 2023-08-04 jrmu     [else (newton f (find-root-tangent f ig))]))
14 12687dd9 2023-08-04 jrmu 
15 12687dd9 2023-08-04 jrmu ;find-root-tangent : (number -> number) number -> number
16 12687dd9 2023-08-04 jrmu ;Finds the root of the tangent line to f at point x.
17 12687dd9 2023-08-04 jrmu 
18 12687dd9 2023-08-04 jrmu (define (find-root-tangent f x)
19 12687dd9 2023-08-04 jrmu   (local ((define fprime (d/dx f TOLERANCE)))
20 12687dd9 2023-08-04 jrmu     (- x (/ (f x)
21 12687dd9 2023-08-04 jrmu             (fprime x)))))
22 12687dd9 2023-08-04 jrmu 
23 12687dd9 2023-08-04 jrmu ;d/dx : (number -> number) number -> (number -> number)
24 12687dd9 2023-08-04 jrmu ;Returns f', the slope of f, given epsilon e.
25 12687dd9 2023-08-04 jrmu 
26 12687dd9 2023-08-04 jrmu (define (d/dx f e)
27 12687dd9 2023-08-04 jrmu   (local ((define (slope x) (/ (- (f (+ x e))
28 12687dd9 2023-08-04 jrmu                                   (f (- x e)))
29 12687dd9 2023-08-04 jrmu                                (* 2 e))))
30 12687dd9 2023-08-04 jrmu     slope))
31 12687dd9 2023-08-04 jrmu 
32 12687dd9 2023-08-04 jrmu ;find-root : (number -> number) number number -> number
33 12687dd9 2023-08-04 jrmu ;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 12687dd9 2023-08-04 jrmu ;Assume that (<= (f left) 0 (f right)) or (<= (f right) 0 (f left)).
35 12687dd9 2023-08-04 jrmu ;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.
36 12687dd9 2023-08-04 jrmu 
37 12687dd9 2023-08-04 jrmu (define (find-root f left right)
38 12687dd9 2023-08-04 jrmu   (local ((define mid (/ (+ left right) 2))
39 12687dd9 2023-08-04 jrmu           (define f-mid (f mid)))
40 12687dd9 2023-08-04 jrmu     (cond
41 12687dd9 2023-08-04 jrmu       [(<= (- right left) TOLERANCE) left]
42 12687dd9 2023-08-04 jrmu       [(or (<= (f left) 0 f-mid)
43 12687dd9 2023-08-04 jrmu            (>= (f left) 0 f-mid)) (find-root f left mid)]
44 12687dd9 2023-08-04 jrmu       [else (find-root f mid right)])))
45 12687dd9 2023-08-04 jrmu 
46 12687dd9 2023-08-04 jrmu (time (find-root (lambda (x) (- (* (expt x 3)
47 12687dd9 2023-08-04 jrmu                                    (exp x))
48 12687dd9 2023-08-04 jrmu                                 (cos x)))
49 12687dd9 2023-08-04 jrmu                  0 1000))
50 12687dd9 2023-08-04 jrmu (time (newton (lambda (x) (- (* (expt x 3)
51 12687dd9 2023-08-04 jrmu                                 (exp x))
52 12687dd9 2023-08-04 jrmu                              (cos x)))
53 12687dd9 2023-08-04 jrmu               500))