Sunday, August 1, 2010

SICP 1.40: Zeros of the Cubic Function

From SICP section 1.3.4 Procedures as Returned Values

Exercise 1.40 asks us to define a procedure cubic that can be used together with newtons-method (defined earlier in the section) in expressions of the form
(newtons-method (cubic a b c) 1)

to approximate zeros of cubic functions of the form

f(x) = x3 + ax2 + bx +c

Note that this is a simplification of the standard equation

f(x) = ax3 + bx2 + cx + d

You arrive at the simplified form by dividing by the leading coefficient (see Cardano's method). This distinction will become important when we need to check our solution against known values.

Quite a lot of code that we'll need was given in the text, starting with the fixed-point procedure from section 1.3.3.
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
(try next))))
(try first-guess))

We'll also be using the code from section 1.3.4 that defines newtons-method.
(define dx 0.00001)
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))

(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))

The newtons-method procedure takes as its arguments a procedure that computes the function for which we want to find a zero, along with an initial guess. That means the cubic procedure itself needs to return a procedure. The returned procedure should take one parameter and compute the value of the cubic function given at the top. Combining it with newtons-method will compute the zeros of that function.
(define (cubic a b c)
(lambda (x)
(+ (* x x x)
(* a x x)
(* b x)

We need to know some zeros of the cubic function with specific values of a, b, and c so we can check our work. There are online tools like the Cubic Equation Calculator and Cubic Function Explorer that take four coefficients and solve cubic functions in the standard form. We can use either of these tools with the a term set to 1 to check the results of our procedure.

Adjust the sliders on the Cubic Function Explorer until the curve crosses the x-axis very close to a whole number (again, make sure the a slider is set to 1).

Now we can use the b, c, and d coefficients to check our solution.
> (newtons-method (cubic 3 -2.4 6) 1)

You should also verify this solution using the same coefficients with the Cubic Equation Calculator mentioned above.


For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

1 comment:

Mark said...

Another way to confirm your answers are at least reasonable is to check that:

((cubic a b c) (zero-for-cubic (cubic a b c)))

is approximately zero.