Metodo di Newton: trova le radici in fretta con l'approssimazione iterativa

Alcune equazioni semplicemente non hanno una soluzione algebrica pulita.

Puoi fattorizzare e sostituire quanto vuoi, ma alcune equazioni non hanno una forma chiusa. Ad esempio, un polinomio di grado cinque o superiore non ha una soluzione algebrica generale. Funzioni che mescolano esponenziali e polinomi, come e^x = 3x, rientrano nella stessa categoria. In questi casi serve un approccio diverso.

Il metodo di Newton è proprio quell'approccio. Trova le radici numericamente facendo ipotesi via via più intelligenti - ciascuna guidata dalla retta tangente della funzione nella stima corrente.

In questo articolo ti guiderò attraverso la formula alla base del metodo di Newton, come funziona passo dopo passo, quando converge e quando no - con esempi concreti per fissare la teoria.

Cerchi altri argomenti di matematica che devi conoscere come data scientist? Leggi il nostro post Serie Geometriche: formula, convergenza ed esempi per vedere come si applica a finanza, fisica e informatica.

Che cos'è il metodo di Newton?

Il metodo di Newton è una tecnica iterativa per trovare le radici di una funzione. Le radici sono i valori in input per cui la funzione è uguale a zero.

Inizi questo processo con una stima iniziale. Poi il metodo usa la geometria della funzione in quel punto per fare una stima migliore. Ripeti il processo, e ogni iterazione ti avvicina alla radice reale.

Tutto qui. Ti serve soltanto una regola di aggiornamento intelligente e ripetibile che converga verso la risposta.

La formula del metodo di Newton

Il cuore del metodo di Newton è un'unica regola di aggiornamento che applichi ripetutamente finché non sei abbastanza vicino alla radice.

Ecco la formula:

Formula del metodo di Newton

Ogni iterazione prende la tua stima attuale x_n e ne produce una migliore, x_{n+1}. Continui ad aggiornare finché il risultato non è abbastanza vicino a zero.

La formula ha tre componenti:

• x_n - la tua stima attuale della radice

• f(x_n) - il valore della funzione in quella stima

• f'(x_n) - la derivata della funzione in quella stima, che ti dice la pendenza della retta tangente

Se f(x_n) è grande, sei lontano dalla radice. Se f'(x_n) è ripida, la funzione cambia velocemente, quindi puoi fare un passo più grande. Il rapporto f(x_n) / f'(x_n) ti dice esattamente di quanto muoverti - e lo sottrai dalla stima corrente per avvicinarti.

Se f'(x_n) è zero o quasi zero, la formula non funziona davvero. Staresti dividendo per zero, il che significa che il metodo non può produrre una stima successiva. Tratterò questo aspetto più nel dettaglio nella sezione dei limiti.

Come funziona il metodo di Newton

Il metodo di Newton segue gli stessi quattro passaggi a ogni iterazione.

1. Scegli una stima iniziale: Scegli un valore iniziale x_0 da qualche parte vicino alla radice. Non devi essere preciso - basta essere abbastanza vicino perché la funzione si comporti in modo prevedibile attorno a quel punto. Spiegherò cosa significa "abbastanza vicino" nella sezione sulla convergenza.

2. Calcola il valore della funzione: Valuta f(x_0). Questo ti dice quanto la funzione è distante da zero nella stima attuale. Se f(x_0) = 0, hai finito - hai trovato la radice.

3. Calcola la derivata: Valuta f'(x_0). Questo ti dà la pendenza della funzione in x_0, cioè la pendenza della retta tangente in quel punto.

4. Aggiorna la stima: Applica la regola di aggiornamento secondo la formula della sezione precedente.

E hai finito!

Questo nuovo valore x_1 è il punto in cui la retta tangente incrocia l'asse x. Geometricamente, tracci una retta che tocca la curva in x_0 e la segui fino a zero. Quel punto d'intersezione è la tua prossima stima, migliore.

Poi ripeti. Inserisci di nuovo x_1 nei passaggi da 2 a 4 per ottenere x_2, poi x_3 e così via. Ogni iterazione traccia una nuova tangente nel punto aggiornato e trova dove incrocia l'asse x.

Il processo si ferma quando f(x_n) è abbastanza vicino a zero - in genere quando scende sotto una piccola soglia che definisci in anticipo.

Interpretazione geometrica del metodo di Newton

Immagina una curva su un grafico - quella è la tua funzione f(x). La radice è dove la curva incrocia l'asse x. Non sai ancora dove sia quell'incrocio, quindi inizi con una stima x_0 da qualche parte sull'asse x.

A ogni passo, tracci il punto (x_0, f(x_0)) sulla curva, poi disegni la retta tangente in quel punto - una retta che tocca la curva lì e ne segue la pendenza. Quella tangente non è orizzontale. È inclinata e, se la segui verso il basso, incrocia l'asse x in un punto. Quell'incrocio è la tua prossima stima, x_1.

Poi ripeti. In x_1, disegni una nuova tangente e trovi dove incrocia l'asse x. Questo ti dà x_2. Ogni tangente è un'approssimazione lineare locale della curva, e ogni punto d'incrocio cade più vicino alla radice reale.

Il grafico qui sotto mostra due iterazioni del metodo di Newton applicato a f(x) = x^2 - 2, partendo da x_0 = 2.5:

Grafico dell'interpretazione geometrica

Funziona perché una retta tangente è la migliore approssimazione lineare di una curva in un dato punto. Più ti avvicini alla radice, più la tangente assomiglia alla curva stessa - e più accurato diventa il passo successivo.

In pratica, le stime non si avvicinano alla radice a piccoli passi. Ci arrivano in fretta, spesso raddoppiando il numero di cifre decimali corrette a ogni iterazione.

Esempio passo dopo passo del metodo di Newton

Applichiamo il metodo di Newton a f(x) = x^2 - 2. La radice di questa funzione è x = sqrt(2) ≈ 1.4142 - in altre parole, stiamo calcolando la radice quadrata di 2.

La derivata è f'(x) = 2x, quindi la regola di aggiornamento diventa:

Esempio (regola di aggiornamento)

Partiamo con una stima iniziale di x_0 = 2.5.

Iterazione 1:

Esempio (iterazione 1)

Iterazione 2:

Esempio (iterazione 2)

Iterazione 3:

Esempio (iterazione 3)

Dopo appena tre iterazioni, siamo già accurati a quattro decimali. L'errore è sceso da 1.086 in x_0 a 0.0001 in x_3 - e continua a ridursi a ogni passo.

Ecco come funzionano visivamente queste stime e i valori dell'errore:

Panoramica visiva di stima ed errore

Il pannello di sinistra mostra come ogni stima si avvicina a sqrt(2) ≈ 1.4142, mentre quello di destra mostra l'errore che diminuisce su una scala logaritmica - ogni iterazione approssimativamente quadruplica la precisione della precedente.

Convergenza del metodo di Newton

Il metodo di Newton può convergere velocemente, ma solo alle giuste condizioni.

Quando la stima iniziale è vicina alla radice e la funzione è regolare in quella regione, il metodo mostra convergenza quadratica. È il termine tecnico per ciò che hai visto nell'esempio: ogni iterazione approssimativamente quadruplica la precisione della precedente. Due cifre decimali corrette diventano quattro, quattro diventano otto e così via.

Perché ciò funzioni devono valere due condizioni:

• Una buona stima iniziale: più x_0 è vicino alla radice reale, più velocemente il metodo converge. Se parti troppo lontano, la tangente in quel punto potrebbe mandarti nella direzione sbagliata.
• Una funzione ben comportata: la funzione deve essere regolare e derivabile vicino alla radice. Svolte brusche o regioni piatte possono interferire con l'approssimazione tramite tangente.

La modalità di fallimento più comune è una derivata vicina a zero. 

Se f'(x_n) è vicino a zero, nel passo di aggiornamento stai dividendo per un numero molto piccolo, il che manda la stima successiva lontano dalla radice. Nel caso peggiore, f'(x_n) = 0 e i calcoli smettono di funzionare perché non puoi dividere per zero.

Un punto di partenza inadeguato può anche far oscillare o divergere il metodo. Invece di avvicinarsi alla radice, le stime rimbalzano avanti e indietro o si allontanano a ogni iterazione.

Il metodo di Newton premia una buona impostazione. Una stima iniziale ragionevole e una funzione regolare sono tutto ciò che serve per farlo convergere, e farlo convergere in fretta.

Vantaggi del metodo di Newton

Quando le condizioni sono favorevoli, il metodo di Newton è difficile da battere.

Il vantaggio più grande è la convergenza quadratica. La maggior parte dei metodi numerici si avvicina alla radice a un tasso lineare, cioè ogni iterazione riduce l'errore di una quantità fissa. Il metodo di Newton invece ne quadruplica la precisione, il che significa che diventa accurato in fretta con pochissime iterazioni.

È anche generalista. Puoi applicarlo a un'ampia gamma di funzioni - polinomiali, trigonometriche, esponenziali - senza cambiare nulla. Per questo compare in tanti campi, dalle simulazioni ingegneristiche all'addestramento di modelli di machine learning.

Limiti del metodo di Newton

Il metodo di Newton chiede molto in cambio di quella velocità. Ecco un paio di limiti da tenere a mente:

• Richiede una derivata: Ti serve un'espressione analitica per f'(x) prima ancora di eseguire una singola iterazione. Per funzioni in cui la derivata è difficile da calcolare (o non esiste) serve un approccio diverso.

• È sensibile alla stima iniziale: se parti troppo lontano dalla radice, il metodo può mandarti nella direzione sbagliata.

• Potrebbe non convergere: se la funzione ha regioni piatte o curve brusche, l'approssimazione tramite tangente semplicemente non funziona.

• Può divergere o oscillare: nei casi peggiori, le stime non convergono e si allontanano dalla radice o rimbalzano indefinitamente avanti e indietro.

Quindi, prima di scegliere il metodo di Newton, assicurati di capire la tua funzione.

Metodo di Newton vs altri metodi per trovare radici

Il metodo di Newton non è l'unico modo per trovare radici, e non è sempre quello giusto per te.

Due altri metodi emergono spesso: il metodo di bisezione e il metodo delle secanti. Te li spiego brevemente.

Metodo di bisezione

Il metodo di bisezione è il più semplice dei tre. Parti con un intervallo [a, b] in cui la funzione cambia segno - il che significa che una radice deve esistere da qualche parte all'interno. Poi dimezzi ripetutamente l'intervallo, tenendo la metà che contiene ancora il cambio di segno.

Funziona, ma è lento. L'errore si riduce della metà a ogni iterazione, il che è convergenza lineare. Ma è anche garantito che funzioni finché la funzione è continua e il tuo intervallo iniziale racchiude una radice. Nessuna derivata richiesta.

Metodo delle secanti

Il metodo delle secanti è un parente stretto del metodo di Newton. Invece di calcolare analiticamente la derivata, la approssima usando due stime precedenti:

Formula del metodo delle secanti

È un buon approccio quando la derivata è difficile da calcolare. Lo paghi in velocità di convergenza - il metodo delle secanti è più veloce della bisezione ma più lento del metodo di Newton.

Applicazioni del metodo di Newton

Il metodo di Newton compare in scienza, ingegneria e machine learning. Ecco come, in pratica.

Risoluzione numerica di equazioni

L'applicazione più diretta. Quando una funzione non ha soluzione in forma chiusa, il metodo di Newton trova la radice. Succede continuamente nel calcolo scientifico - pensa a trovare punti di equilibrio in reazioni chimiche o a risolvere equazioni trascendenti nell'elaborazione di segnali.

Ottimizzazione

Trovare il minimo o il massimo di una funzione f(x) significa trovare dove la sua derivata f'(x) = 0. È un problema di ricerca delle radici - il che significa che si può applicare il metodo di Newton. Esegui semplicemente l'algoritmo su f'(x) invece che su f(x), usando la seconda derivata f''(x) al posto della prima.

Questa variante si chiama metodo di Newton per l'ottimizzazione e converge più velocemente del gradiente discendente su funzioni regolari e ben comportate.

Machine learning

Nel machine learning, addestrare un modello significa minimizzare una funzione di perdita. Il metodo di Newton e le sue varianti compaiono in un paio di punti qui.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) è un ottimizzatore quasi-Newton che approssima la seconda derivata per evitarne il calcolo diretto. È una scelta standard per la regressione logistica e altri problemi convessi. Il metodo di Newton è anche alla base degli aggiornamenti Newton-Raphson usati nell'adattamento di modelli statistici, come i modelli lineari generalizzati.

Fisica e ingegneria

Il metodo di Newton è ovunque nella simulazione e nella progettazione. Gli ingegneri lo usano per risolvere sistemi non lineari di equazioni che descrivono sistemi fisici - pensa all'analisi delle sollecitazioni strutturali e alla dinamica dei fluidi. In ogni caso, il problema di base si riduce a trovare dove un insieme di equazioni è uguale a zero.

Errori comuni con il metodo di Newton

La maggior parte degli errori con il metodo di Newton si riduce agli stessi quattro sbagli. Eccoli:

• Partire troppo lontano dalla radice: una stima iniziale scarsa è la ragione più comune per cui il metodo diverge o oscilla. Se non hai una buona intuizione su dove sia la radice, traccia prima la funzione. Questo ti dirà da dove iniziare.

• Sbagliare la derivata: la regola di aggiornamento dipende da f'(x). Una derivata errata - per un errore di calcolo o di codice - produce stime sbagliate fin dalla prima iterazione, e l'errore si amplifica con le iterazioni.

• Non controllare la divisione per zero. Se f'(x_n) è uguale a zero o ci si avvicina molto, il passo di aggiornamento non può funzionare. Aggiungi un controllo nella tua implementazione: se la derivata scende sotto una piccola soglia, fermati e segnala il fallimento invece di produrre un risultato senza senso.

• Fermarsi troppo presto. Interrompere le iterazioni prima che la stima sia convergente ti lascia con una risposta che sembra vicina ma non lo è. Imposta la condizione di arresto sull'errore effettivo - cioè |f(x_n)| o |x_{n+1} - x_n| che scendono sotto una soglia scelta consapevolmente, non solo un numero fisso di iterazioni.

Conclusione

Il metodo di Newton è uno degli strumenti più utili nel calcolo numerico. Un'unica regola di aggiornamento, applicata ripetutamente, può trovare radici con precisione arbitraria in poche iterazioni.

Paghi quella velocità con delle condizioni. Ti servono una buona stima iniziale, una funzione non piatta, non spigolosa e con derivata non nulla per ottenere una convergenza rapida. Ti basta capire queste condizioni e saprai quando scegliere il metodo di Newton e quando usare qualcos'altro (come i metodi di bisezione o delle secanti).

Il modo migliore per costruire quell'intuizione è esercitarti su esempi semplici. Parti con f(x) = x^2 - 2, prova punti di partenza diversi e osserva cosa succede. Passa poi a funzioni con radici multiple o regioni piatte e vedi dove il metodo va in crisi.

Se ti piace il concetto di ottimizzazione per iterazione, devi conoscere il gradiente discendente. Leggi il nostro Gradient Descent nel Machine Learning: un approfondimento per scoprire come ottimizza i modelli per il machine learning.