Il Metodo di Newton¶

I cicli sono spesso usati per calcolare approssimazioni partendo da un’approssimazione e migliorandola iterativamente.

Per esempio, un metodo per calcolare la radice quadrata è il metodo di Newton.
Supponiamo che vogliamo calcolare la radice quadrata di n.
Se cominciamo con un’approssimazione, possiamo calcolare una approssimazione migliore usando la formula seguente:

better =  1/2 * (approx + n/approx)

L’implementazione seguente richiede due parametri.

Il primo è il numero di cui si vuole calcolare la radice.
Il secondo è il numero di volte che vogliamo applicare la formula.

def newtonSqrt(n, howmany):
    approx = 0.5 * n
    for i in range(howmany):
        betterapprox = 0.5 * (approx + n/approx)
        approx = betterapprox
    return betterapprox

print(newtonSqrt(10, 3))
print(newtonSqrt(10, 5))
print(newtonSqrt(10, 10))

(chp07_newtonsdef)

La seconda e la terza chiamata a newtonSqrt ritorna la stesso valore per la radice di 10.
Usando 10 iterazioni invece di 5, non miglioriamo il risultato.
In generale, l’algoritmo di Newton raggiunge un punto in cui la nuova approssimazione non è migliore della precedente.
A questo punto, possiamo semplicemente fermarci.

Questa implementazione usa un while per applicare la formula finché l’approssimazione non cambia. Finché la nuova approssimazione è diversa dalla precedente ripetiamo.

(chp07_newtonswhile)

Note

L’istruzione while utilizza l’uguaglianza tra due numeri in floating point. In generale, dal momento che i numeri in floating point sono approssimazione dei numeri reali, in generale è meglio controllare che la differenza tra i due numeri sia piccola.