Metodo di Newton e bisezione in Python

Se sei in quinta al liceo scientifico opzione scienze applicate, nel primo quadrimestre l’informatica arriva al calcolo numerico: trovare gli zeri di una funzione con il computer, quando l’equazione non si risolve con una formula. La verifica scritta o la consegna di laboratorio su questo blocco cade di solito tra sei e nove settimane da ora, fra fine novembre e dicembre. Il tempo c’è, e il tema è uno dei più belli del programma, perché per la prima volta il codice che scrivi dà un risultato che puoi controllare con la calcolatrice.

Vedo ogni anno nelle mie lezioni gli stessi due ostacoli: capire perché il metodo converge, e scrivere un ciclo con un criterio di arresto sensato. Uso sempre lo stesso esempio, il più semplice che esista: $f(x)=x^2-2$, la cui radice positiva è $\sqrt{2}\approx 1,41421356$. Conosciamo già la risposta, quindi possiamo vedere se il metodo la trova.

Se Python è ancora un po’ nuovo, parti da programmazione in Python da zero. Per ragionare su cicli e condizioni prima del codice ti serve diagrammi di flusso e pseudocodice; per un altro esempio di algoritmo con confronto di costo, algoritmi di ordinamento.

Metodo di bisezione

L’idea viene dal teorema degli zeri: se $f$ è continua in $[a,b]$ e $f(a)$ e $f(b)$ hanno segno opposto, nell’intervallo c’è almeno una radice. Si prende il punto medio $m=(a+b)/2$ e si tiene la metà in cui il segno cambia. Ripeti.

Per $f(x)=x^2-2$ su $[1,2]$: $f(1)=-1$ e $f(2)=2$, segni opposti, si parte.

Dopo 5 passi la radice è in $[1,40625;1,4375]$: l’errore massimo è $0,03125$. A ogni passo l’intervallo si dimezza, quindi dopo $n$ passi l’ampiezza è $(b-a)/2^n$. Per avere un errore sotto $10^{-6}$ da un intervallo di ampiezza 1 serve $2^n>10^6$, cioè $n=20$ (infatti $2^{20}=1048576$).

Metodo di Newton–Raphson

Newton usa la derivata: dal punto $x_n$ si traccia la tangente al grafico e si prende dove incontra l’asse $x$. La formula è:

Per $f(x)=x^2-2$ la derivata è $f^{\prime }(x)=2x$, e la formula diventa $x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}$. Partiamo da $x_0=1,5$:

• $x_1=1,5-\frac{0,25}{3}=1,41666\dots$
• $x_2=1,41666\dots -\frac{0,006944\dots }{2,8333\dots }=1,41421568\dots$
• $x_3=1,41421356237\dots$

Dopo soli 3 passi le cifre giuste sono 11. Un’osservazione utile per la verifica: il numero di cifre corrette circa raddoppia a ogni passo (errore: circa $2,5\cdot 10^{-3}$, poi $2\cdot 10^{-6}$, poi $10^{-12}$). La bisezione guadagna invece un solo bit (un fattore 2) per passo.

Il codice Python

Ho testato queste funzioni con python3 sull’esempio di sopra.

def f(x):
    return x * x - 2

def df(x):
    return 2 * x

def bisezione(f, a, b, tol=1e-6, max_iter=100):
    if f(a) * f(b) > 0:
        raise ValueError("f(a) e f(b) devono avere segno opposto")
    for i in range(1, max_iter + 1):
        m = (a + b) / 2
        if f(m) == 0 or (b - a) / 2 < tol:
            return m, i
        if f(a) * f(m) < 0:
            b = m
        else:
            a = m
    return (a + b) / 2, max_iter

def newton(f, df, x0, tol=1e-10, max_iter=50):
    x = x0
    for i in range(1, max_iter + 1):
        d = df(x)
        if d == 0:
            raise ZeroDivisionError("derivata nulla")
        x_nuovo = x - f(x) / d
        if abs(x_nuovo - x) < tol:
            return x_nuovo, i
        x = x_nuovo
    return x, max_iter

print(bisezione(f, 1, 2))
print(newton(f, df, 1.5))

Output: la bisezione dà circa 1.4142141 in 20 iterazioni, Newton 1.4142135623730951 in 4 iterazioni. Con tolleranza $10^{-10}$ la bisezione ne richiede 34. A parità di precisione, Newton fa meno del 15 % del lavoro.

Alcune scelte da saper spiegare in laboratorio:

• le funzioni ricevono f come parametro, così lo stesso codice vale per qualunque equazione;
• max_iter evita il ciclo infinito se il metodo non converge;
• il controllo del segno iniziale in bisezione protegge da intervalli che non contengono una radice;
• in newton il controllo d == 0 evita la divisione per zero.

Criteri di arresto

Un ciclo numerico deve sapere quando fermarsi. Tre criteri, spesso combinati:

1. Ampiezza dell’intervallo (bisezione): $(b-a)/2<tol$.
2. Differenza tra approssimazioni: $|x_{n+1}-x_n|<tol$.
3. Residuo: $|f(x_n)|<tol$. Attenzione: se la funzione è molto piatta vicino alla radice, un residuo piccolo non garantisce un $x$ vicino.

Aggiungi sempre un numero massimo di iterazioni: è l’ultima rete di sicurezza.

Confronto e limiti

In pratica: Newton è più veloce, la bisezione è più robusta. Un errore tipico: partire con Newton da $x_0=0$ per $x^2-2$. La derivata $2x$ vale 0 e il codice solleva l’eccezione. Con $x_0=0,1$ il primo passo manda il punto a $x_1=0,1-\frac{-1,99}{0,2}=10,05$ e servono altri passi per tornare vicino alla radice: il metodo funziona, ma il punto di partenza conta.

Se vuoi un livello oltre il liceo, dove si studia anche l’errore e la convergenza in modo formale, lo trovi in calcolo numerico: metodi per l’esame. Per la parte di analisi dietro Newton, utile ripassare le derivate spiegate bene.

Un esercizio completo

Trova $\sqrt{3}$ come radice positiva di $f(x)=x^2-3$, con Newton da $x_0=2$. La derivata è $2x$ e il passo è $x_{n+1}=x_n-\frac{x_n^2-3}{2x_n}$.

• $x_1=2-\frac{1}{4}=1,75$
• $x_2=1,75-\frac{0,0625}{3,5}=1,7321428\dots$
• $x_3=1,7320508100\dots$

Il valore esatto è $\sqrt{3}=1,7320508075\dots$: al terzo passo l’errore è già sotto $10^{-8}$. Quante iterazioni avrebbe usato la bisezione su $[1,2]$ per la stessa tolleranza? Serve $2^n>10^8$, cioè $n=27$ ($2^{27}=134217728$). Il confronto 3 contro 27 è la risposta che molti professori vogliono sentire sulla velocità di convergenza.

Un’avvertenza sul codice: se ti chiedono di modificarlo per $x^2-3$, cambiano solo f e df, non le due funzioni dei metodi. Se hai dovuto toccare bisezione o newton, qualcosa non è generale.

Metti alla prova

Prima di una verifica rifai a mano tre iterazioni di Newton per $f(x)=x^2-3$ da $x_0=2$ e controlla poi con il codice. Poi prova la simulazione sulle verifiche del liceo, gratuita. Se vuoi riguardare insieme il tuo codice di laboratorio, possiamo farlo in una lezione di prova online con me.