## 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))
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 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))``````  Posta un commento o usa questo indirizzo per il trackback.