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

rotella

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

s119

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

s120

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))
       dx)))

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

s121

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))
                  1.0))

s122

:mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

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

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. 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: