SICP Exercise 1.29

Question

Simpson’s Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson’s Rule, the integral of a function \(f\) between \(a\) and \(b\) is approximated as \[\frac{h}{3}(y_0+4y_1+2y_2+4y_3+2y_4+\cdots +2y_{n-2}+4y_{n-1}+y_n),\] where \(h=(b-a)/n\), for some integer \(n\), and \(y_k=f(a+kh)\). (Increasing \(n\) increases the accuracy of the approximation.)

Define a procedure that takes as arguments \(f\), \(a\), \(b\) and \(n\) and returns the value of the integral, computed using Simpson’s Rule. Use your procedure to integrate cube between 0 and 1 (with \(n=100\) and \(n=1000\)), and compare the results to those of the integral procedure shown above.

Answer

Here is the answer code:

(define (sum term a next b)
  (if (> a b) 0
      (+ (term a) (sum term (next a) next b))))

(define (cube x) (* x x x))

(define (simpsons_rule f a b n)
  (define h (/ (- b a) n))
  (define (yk k count) (* count (f (+ a (* k h)))))
  (define (term k)
    (cond ((or (= k 0) (= k n)) (yk k 1))
          ((even? k) (yk k 2))
          (else (yk k 4))))
  (* (/ h 3) (sum term 0 inc n)))

(simpsons_rule cube 0 1.0 100)
(simpsons_rule cube 0 1.0 1000)

And the results. Interestingly, using \(n=1000\) actually gives us a slightly worse accuracy. Nevertheless, both results are highly accurate.

0.24999999999999992
0.2500000000000003

Let us compare this to the results we previously received from integral (using a dx-value of \(0.0000001\)):

0.25000000112005644

This result is much less accurate. Not only that, it took much longer to compute as well. Looks like Simpson’s rule is to be preferred for calculating integrals.