Zeri di funzioni: bisezione, Newton, secanti e punto fisso

Trovare dove una funzione si annulla è uno dei problemi più frequenti: il punto di lavoro di un diodo in un circuito (dove l’equazione esponenziale del diodo incontra la retta di carico), la frequenza a cui un filtro attenua di 3 dB, l’angolo di lancio per colpire un bersaglio. Per quasi tutte le equazioni non lineari non esiste una formula, e si procede per iterazioni: si parte da una stima e la si migliora finché è abbastanza precisa.

Il metodo di bisezione

Se è continua su e e hanno segni opposti, per il teorema degli zeri di Analisi 1 c’è almeno una radice. La bisezione dimezza l’intervallo a ogni passo:

1. si calcola il punto medio ;
2. se e hanno segni opposti la radice è in , altrimenti in ;
3. si ripete finché l’intervallo è più piccolo della tolleranza.

Dopo passi l’intervallo è largo . Per passare da un intervallo di 1 a una tolleranza di servono 20 passi (). Il metodo è lento ma converge sempre, e la stima dell’errore è garantita. Si guadagna una cifra decimale ogni 3,3 passi circa.

Il metodo di Newton

L’idea è sostituire la funzione con la sua retta tangente e prendere come nuova stima il punto in cui la tangente taglia l’asse:

Esempio: la radice quadrata. Con la formula diventa , il metodo babilonese. Per partendo da (come nella figura): 1,8333; 1,4621; 1,41500; 1,4142138; 1,41421356237311. Le cifre decimali corrette diventano 0, 1, 3, 6, 13: circa raddoppiano a ogni passo.

Dimostrazione della convergenza quadratica

Sia la radice ed l’errore. Sviluppando con Taylor attorno a , calcolata in :

Dividendo per e usando la definizione dell’iterazione, :

L’errore nuovo è proporzionale al quadrato di quello vecchio: se , è dell’ordine di . È la convergenza quadratica, molto più rapida della bisezione, che è lineare.

I limiti di Newton

• Serve la derivata, che non sempre è disponibile.
• La convergenza è garantita solo se si parte abbastanza vicino alla radice. Lontano, le tangenti possono mandare la stima ovunque, o farla oscillare: con e le stime divergono.
• Se (radice doppia) la convergenza diventa solo lineare.

Nella pratica si combinano i due metodi: si usa la bisezione finché l’intervallo è piccolo, poi Newton per finire in pochi passi. È ciò che fanno le funzioni come fzero di MATLAB o brentq di SciPy.

Il metodo delle secanti

Quando la derivata non è disponibile la si approssima con il rapporto incrementale tra le ultime due stime:

La convergenza è superlineare, di ordine (la sezione aurea), e ogni passo richiede una sola valutazione di : spesso è più efficiente di Newton.

Le iterazioni di punto fisso

Ogni equazione si può riscrivere come , e cercare un punto fisso con . Converge se vicino alla soluzione : l’errore viene moltiplicato circa per a ogni passo.

Esempio. : partendo da qualsiasi valore e premendo ripetutamente il tasto coseno di una calcolatrice (in radianti) si arriva a 0,739085…, perché vicino alla soluzione. Newton stesso è un’iterazione di punto fisso con , che ha : per questo converge più in fretta.

Sistemi non lineari

Per un sistema di equazioni in incognite, Newton si generalizza con la matrice jacobiana di Analisi 2:

a ogni passo si risolve un sistema lineare. È il cuore di SPICE: per un circuito con diodi e transistor, il simulatore linearizza i componenti attorno alla stima corrente e risolve il sistema lineare, ripetendo finché le tensioni non cambiano più. Quando una simulazione “non converge”, è Newton che non trova la soluzione partendo dalla stima iniziale.

Criteri di arresto

Si smette quando la differenza tra due stime successive è sotto una tolleranza, , oppure quando il residuo è abbastanza piccolo, e comunque dopo un numero massimo di iterazioni, per non restare bloccati se il metodo non converge. Il residuo piccolo da solo non basta: se la funzione è molto piatta vicino alla radice, può essere minuscolo anche lontano dalla soluzione.