SICP – cap. 1 – procedure ritornate come valori – II – 51


Continuo a copiare, qui.

Metodo di Newton

When we first introduced the square-root procedure, in section 1.1.7 [qui], we mentioned that this was a special case of Newton’s method. If x ↦ g(x) is a differentiable function, then a solution of the equation g(x) = 0 is a fixed point of the function x ↦ f(x) where


and Dg(x) is the derivative of g evaluated at x. Newton’s method is the use of the fixed-point method we saw above to approximate a solution of the equation by finding a fixed point of the function f. For many functions g and for sufficiently good initial guesses for x, Newton’s method converges very rapidly to a solution of g(x) = 0. (Newton’s method does not always converge to an answer, but it can be shown that in favorable cases each iteration doubles the number-of-digits accuracy of the approximation to the solution. In such cases, Newton’s method will converge much more rapidly than the half-interval method.)

In order to implement Newton’s method as a procedure, we must first express the idea of derivative. Note that “derivative”, like average damping, is something that transforms a function into another function. For instance, the derivative of the function x ↦ x3 is the function x ↦ 3x2. In general, if g is a function and dx is a small number, then the derivative Dg of g is the function whose value at any number x is given (in the limit of small dx) by


Thus, we can express the idea of derivative (taking dx to be, say, 0.00001) as the procedure

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))

along with the definition

(define dx 0.00001)

Like average-damp, deriv is a procedure that takes a procedure as argument and returns a procedure as value. For example, to approximate the derivative of x ↦ x3 at 5 (whose exact value is 75) we can evaluate


With the aid of deriv, we can express Newton’s method as a fixed-point process:

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

The newton-transform procedure expresses the formula at the beginning of this section, and newtons-method is readily defined in terms of this. It takes as arguments a procedure that computes the function for which we want to find a zero, together with an initial guess. For instance, to find the square root of x, we can use Newton’s method to find a zero of the function y ↦ y2 - x starting with an initial guess of 1 (For finding square roots, Newton’s method converges rapidly to the correct solution from any starting point). This provides yet another form of the square-root procedure:

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x))



Posta un commento o usa questo indirizzo per il trackback.



Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di

Stai commentando usando il tuo account Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: