Il metodo di Newton-Raphson

Riepilogo

Il teorema di Bolzano assicura che una funzione continua che cambia segno ha una radice, e la bisezione la localizza guadagnando una cifra binaria per iterazione. Questa lezione studia un procedimento molto più rapido quando funziona: il metodo di Newton-Raphson, che sostituisce il grafico con la sua retta tangente e prende come nuova approssimazione il punto in cui la tangente taglia l’asse. Le approssimazioni così ottenute si definiscono una dopo l’altra per gli interi $n \geq 0$ , e il loro limite si intende con la definizione del limite quando la variabile tende all’infinito, senza la teoria delle successioni. La lezione dimostra, con la convessità, che se la derivata non si annulla e la funzione è convessa o concava, le iterate che partono dal lato giusto si avvicinano alla radice senza oltrepassarla e convergono a essa; e, con il teorema del valor medio, che il valore della funzione, che si calcola, limita la distanza dalla radice, che non si conosce. Mostra poi, con esempi numerici, che il numero di cifre corrette raddoppia a ogni iterazione, e i modi in cui il metodo fallisce: una derivata nulla, un ciclo, una divergenza. I problemi calcolano radici cubiche e reciproci senza dividere, spezzano un ciclo, studiano una radice doppia e trovano il confine esatto tra la convergenza e la divergenza per l’arcotangente.

Obiettivi di apprendimento

Calcolare le iterate di Newton-Raphson di una funzione derivabile e riconoscere in esse il punto in cui la retta tangente taglia l’asse.
Dimostrare la convergenza monotona delle iterate quando la derivata non si annulla e la funzione è convessa o concava, e scegliere un punto iniziale dal lato giusto.
Stimare la distanza di un’approssimazione dalla radice con il valore della funzione e un minorante della sua derivata.
Riconoscere i modi in cui il metodo fallisce e confrontarlo con la bisezione, in rapidità e in sicurezza.

L’iterazione

Sia $f$ una funzione derivabile di cui si cerca la radice $r$ , e sia $x_0$ una prima approssimazione. Vicino a $x_0$ , il grafico di $f$ somiglia alla sua retta tangente, $y = f(x_0) + f'(x_0)(x - x_0)$ , secondo la definizione di retta tangente della lezione sulla derivata come limite; detto con il differenziale della lezione sulle derivate di ordine superiore e il differenziale, l’incremento $f(x_0 + \Delta x) - f(x_0)$ somiglia a $f'(x_0) \Delta x$ . La tangente taglia l’asse in un solo punto se $f'(x_0) \neq 0$ , ed è naturale prenderlo come nuova approssimazione: lo si ottiene uguagliando a zero l’equazione della tangente. Ripetere il procedimento dal punto ottenuto è il metodo di Newton-Raphson.

DefinizioneIterate di Newton-Raphson

Siano $f$ una funzione derivabile in un intervallo $I$ e $x_0$ un punto di $I$ . Le iterate di Newton-Raphson a partire da $x_0$ sono i numeri definiti, uno dopo l’altro, da

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

finché $x_n$ sta in $I$ e $f'(x_n) \neq 0$ . Se queste condizioni valgono per ogni intero $n \geq 0$ , le iterate formano una funzione $n \mapsto x_n$ definita nell’insieme degli interi non negativi, che non è limitato superiormente, e la definizione del limite quando la variabile tende all’infinito, della lezione sui limiti quando la variabile tende all’infinito, si applica a essa. Si dice che le iterate convergono a $r$ se $\lim_{n \to \infty} x_n = r$ , cioè se

(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

Ogni iterata è il punto in cui la tangente in $(x_n, f(x_n))$ taglia l’asse: ponendo $y = 0$ e $x = x_{n+1}$ nell’equazione $y = f(x_n) + f'(x_n)(x - x_n)$ e ricavando l’incognita, si ottiene la formula della definizione. Il metodo non chiede che la funzione cambi segno in un intervallo dato, come la bisezione, ma che sia derivabile e che la sua derivata non si annulli nei punti che attraversa; in cambio, nulla assicura in anticipo che le iterate si avvicinino a una radice. Più avanti si danno condizioni che lo assicurano.

EsempioLa radice quadrata di 2

Applicare il metodo di Newton-Raphson a $f(x) = x^2 - 2$ a partire da $x_0 = 2$ . Il calcolo che segue mostra le prime tre tangenti e i punti in cui tagliano l’asse.

Dimostrazione

$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}$
La derivata è $f'(x) = 2x$ , che non si annulla se $x > 0$ . L’iterazione assume questa forma: ogni approssimazione è la media tra quella che la precede e $2$ diviso per essa. A partire da $x_0 = 2$ , la tangente $y = 2 + 4(x - 2)$ taglia l’asse in $\frac{3}{2}$ .
$x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1{,}416667$
La tangente in $\left(\frac{3}{2}, \frac{1}{4}\right)$ taglia l’asse molto più vicino alla radice.
$x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1{,}4142157, \qquad \sqrt{2} \approx 1{,}4142136$
La terza iterata ha già cinque cifre decimali corrette. Gli errori, $x_n - \sqrt{2}$ , sono circa $0{,}59$ , $0{,}086$ , $0{,}0025$ e $0{,}0000021$ : ciascuno è dell’ordine del quadrato di quello che lo precede.

L’errore di questo esempio si eleva al quadrato in modo esatto. Dalla formula dell’iterazione si ottiene, per ogni $x_n > 0$ , questa identità:

x_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

Pertanto, tutte le iterate dalla prima in poi sono maggiori o uguali a $\sqrt{2}$ , e se $x_n \geq 1$ , il nuovo errore è al più la metà del quadrato dell’errore attuale: la quarta iterata, $x_4 = \frac{665\,857}{470\,832}$ , ha undici cifre decimali corrette. Con $2$ sostituito da un numero positivo qualsiasi, lo stesso procedimento calcola radici quadrate; compare già nella Metrica di Erone di Alessandria, nel I secolo, e per questo si chiama anche metodo di Erone.

Isaac Newton descrisse il suo metodo per le equazioni polinomiali nel 1669, in uno scritto che circolò manoscritto e fu pubblicato nel 1711; Joseph Raphson pubblicò nel 1690 un’esposizione più semplice, e Thomas Simpson lo presentò nel 1740 come un metodo iterativo per equazioni generali.