Metodo numerico di Newton per il calcolo della radice ennesima

Per la radice quadrata il metodo di Erone di Alessandria dice che se y è una approssimazione della radice quadrata di x allora

x/(2*y)+y/2

sarà una approssimazione migliore.

Per la radice cubica:

x/(3*y^2)+2*y/3

Per la radice di ordine n:

x/(n*y^(n-1))+(n-1)*y/n

Ecco il listato di un programma in Python che calcola ricorsivamente la radice ennesima di un numero x

"""Calcolo della radice ennesima con il metodo di Newton"""

def preciso(y,x,n):
    if abs(y**n-x)<0.0000001:
        return True
    else:
        return False

def migliora(y,x,n):
    if preciso(y,x,n):
        print y
        return y
    else:
        print y
        return migliora(((n-1)*y+x/y**(n-1))/n,x,n)

def radice(x,n=2):
    n=float(n)
    return migliora(x/n,x,n)

La terza definizione si riferisce alla radice del numero x di ordine n. Se l'ordine non viene indicato si considera di ordine 2.

Questa funzione lancia la funzione ricorsiva migliora che continua a migliorare l'approssimazione della radice finchè una apposita funzione preciso riporti che la precisione desiderata è stata raggiunta.
La funzione migliora svolge anche il compito di stampare le succesive approssimazioni della radice ennesima, indicate con y.

Dimostrazione

Secondo il celebre metodo delle tangenti di Newton dovendo risolvere una equazione del tipo

f(x)=0

se x0 è un'approssimazione dello zero della funzione, sarà una approssimazione migliore

x1=x0-f(x0)/Df(x0)

dove Df è la derivata della funzione f(x).

Avviso: cambiamento di simboli

indichiamo con k il numero di cui trovare la radice
indichiamo con x l'approssimazione di tale radice

In realtà per trovare la radice quadrata x di k, si tratta di trovare lo zero della funzione

f(x)=x²-k

Lo zero di una funzione è quel valore di x che rende appunto zero il valore della funzione.
Procedendo con le approssimazioni successive di Newton dobbiamo trovare la derivata:

f'(x)=2*x

Allora se x è l'approssimazione corrente, l'approssimazione successiva sarà:

x-(x²-k)/(2*x)

Con una semplicissima approssimazione si avrà:

x/2+k/(2*x)

Ripetendo questo passaggio si può ottenere una approssimazione via via migliore della radice quadrata di k.
Ovviamente il ragionamento si può generalizzare per trovare la radice ennesima:

f(x)=xⁿ-k

f'(x)=n*x^(n-1)

Allora se x è l'approssimazione corrente, l'approssimazione successiva sarà:

x-(xⁿ-k)/(n*x^(n-1))

Con una semplicissima semplificazione si avrà:

(n-1)*x/n+k/(n*x^(n-1))

Il metodo di Newton converge rapidamente. Ma ci si può chiedere da quale valore di x conviene partire ? I dettagli sono complicati, rifacendosi però al testo Maraschini Palma "ForMat Spe" III ed. Paravia pag. 146 conviene partire da un valore più grande della radice ennesima. Per esempio per x>1, si può scegliere come prima approssimazione x/n.

L'algoritmo è comunque valido anche se si applica a valori di x minori di uno.