Metodo di Newton-Raphson
Il metodo di Newton-Raphson utilizza l'approssimazione iterativa per trovare una radice di un polinomio p(x) tramite una formula di ricorrenza $$ x_{n+1} = x_n - \frac{p(x_n)}{p'(x_n)} $$ Dove \( x_n \) è l'approssimazione corrente della radice. \( p(x) \) è il polinomio e \( p'(x) \) è la derivata del polinomio.
E' un motodo di calcolo numerico utile per trovare una radice reale del polinomio, anche se approssimata, quando non si trovano altre radici intere o razionali.
Il metodo di Newton-Raphson è molto efficiente e converge rapidamente alla radice reale. In particolar modo se la scelta iniziale \( x_0 \) è vicina alla radice reale.
Tuttavia, la convergenza non è sempre garantita. Se scelgo un valore iniziale \( x_0 \) troppo lontano dalla radice cercata, il metodo può divergere, ossia allontanarsi dalla soluzione, oppure oscillare senza convergere.
Inoltre, se durante un'iterazione la derivata prima si annulla, non posso proseguire il calcolo perché la formula comporterebbe una divisione per zero.
Nota. Il metodo è detto anche metodo delle tangenti e non si limita ai polinomi. Può essere applicato anche a funzioni continue non polinomiali, purché siano soddisfatte opportune condizioni. Inoltre, non serve soltanto quando non si trovano radici intere o razionali. È utile, più in generale, quando si vuole calcolare numericamente una radice.
Un esempio pratico
Ecco un esempio pratico di utilizzo il metodo di Newton-Raphson per trovare una radice reale di un polinomio.
Considero il polinomio \( p(x) = x^3 - x^2 - 1 \).
Come primo passo scelgo l'approssimazione iniziale. Ad esempio, x0=1,5
$$ x_0 = 1.5 $$
Poi calcolo la derivata del polinomio \( p(x) = x^3 - x^2 - 1 \) è il polinomio
$$ p'(x) = 3x^2 - 2x $$
Poi inzio le iterazioni
Iterazione 1
$$ x_1 = x_0 - \frac{p(x_0)}{p'(x_0)} $$
$$ x_1 = 1.5 - \frac{(1.5)^3 - (1.5)^2 - 1}{3(1.5)^2 - 2(1.5)} $$
$$ x_1 = 1.5 - \frac{3.375 - 2.25 - 1}{6.75 - 3} $$
$$ x_1 = 1.5 - \frac{0.125}{3.75} $$
$$ x_1 = 1.5 - 0.0333 $$
$$ x_1 = 1.4667 $$
Iterazione 2
$$ x_2 = x_1 - \frac{p(x_1)}{p'(x_1)} $$
$$ x_2 = 1.4667 - \frac{(1.4667)^3 - (1.4667)^2 - 1}{3(1.4667)^2 - 2(1.4667)} $$
$$ x_2 = 1.4667 - \frac{3.1550 - 2.1511 - 1}{6.4533 - 2.9333} $$
$$ x_2 = 1.4667 - \frac{0.0039}{3.5200} $$
$$ x_2 = 1.4667 - 0.001 $$
$$ x_2 = 1.4656 $$
Calcolo la differenza tra la soluzione precedente e quella attuale
$$ \epsilon = | x_2 - x_1 | = |1.4656-1.4667| = 0.001 $$
Nota. In realtà il sottraendo $ 0.001 $ calcolato durante i calcoli è già la differenza tra i due valori. Quindi, si può anche omettere di calcolare due volte. Tuttavia, per spiegare meglio a cosa serve ho preferito ripetere il calcolo.
Iterazione 3
$$ x_3 = x_2 - \frac{p(x_2)}{p'(x_2)} $$
$$ x_3 = 1.4656 - \frac{(1.4656)^3 - (1.4656)^2 - 1}{3(1.4656)^2 - 2(1.4656)} $$
$$ x_3 = 1.4656 - \frac{3.148- 2.1479 - 1}{6.4439 - 2.9312} $$
$$ x_3 = 1.4656 - \frac{0.0001}{3.5127} $$
$$ x_3 = 1.4655 $$
Calcolo la differenza tra la soluzione precedente e quella attuale
$$ \epsilon = |x_3 - x_2| = |1.4655 - 1.4656| = 0.0001 $$
Continuo iterativamente finché la differenza tra \( x_{n+1} \) e \( x_n \) è inferiore a una tolleranza desiderata, ad esempio, ε<0.001 oppure ε<0.0001.
Dopo alcune iterazioni \( x \) converge a una radice reale del polinomio \( p(x) \).
In questo caso, la soluzione \( x \approx 1.4655 \) può essere già considerata un'approssimazione accettabile della radice reale del polinomio.
Verifica. Sostituisco \( x \approx 1.4655 \) nel polinomio iniziale \( p(x) = x^3 - x^2 - 1 \) e calcolo il risultato. $$ p(1.4655) = 1.4655^3 -1.4655^2 - 1 = -0.00025 $$ Il risultato è molto vicino allo zero, quindi è molto vicino alla radice del polinomio.
Esempio 2
Applico il metodo di Newton-Raphson per calcolare una radice dell'equazione:
$$ x^2-2=0 $$
La radice positiva è \(\sqrt{2}\), un numero irrazionale che posso approssimare numericamente.
Considero la funzione:
$$ f(x)=x^2-2 $$
Calcolo la sua derivata prima:
$$ f'(x)=2x $$
Sostituisco le due espressioni nella formula di Newton-Raphson:
$$ x_{n+1}=x_n-\frac{x_n^2-2}{2x_n} $$
Scelgo come valore iniziale \(x_0=1\).
Iterazione 1
Sostituisco \(x_0=1\) nella formula:
$$ x_1=1-\frac{1^2-2}{2\cdot1} $$
$$ x_1=1+\frac12=1.5 $$
Dal punto di vistra grafico la tangente del punto \( ( x_0, f(x_0)) \) interseca l'asse x nel punto $ x_1=1,5 $
Iterazione 2
Utilizzo il valore appena ottenuto:
$$ x_2=1.5-\frac{1.5^2-2}{2\cdot1.5} $$
$$ x_2=1.5-\frac{0.25}{3} $$
$$ x_2\approx1.416667 $$
Dal punto di vistra grafico la tangente del punto \( ( x_1, f(x_1)) \) interseca l'asse x nel punto $ x_2=1,416667 $
Iterazione 3
Ripeto il calcolo utilizzando il valore precedente, mantenendo una precisione maggiore nei calcoli intermedi:
$$ x_3=x_2-\frac{x_2^2-2}{2x_2} $$
$$ x_3\approx1.414216 $$
Dal punto di vistra grafico la tangente del punto \( ( x_2, f(x_2)) \) interseca l'asse x nel punto $ x_3=1,414216 $
Iterazione 4
Applico nuovamente la formula:
$$ x_4=x_3-\frac{x_3^2-2}{2x_3} $$
$$ x_4\approx1.414214 $$
Evito di pubblicare il grafico della tangente perché è molto simile al precedente.
Riporto le approssimazioni ottenute nella seguente tabella:
- \(x_0=1\)
- \(x_1=1.5\)
- \(x_2\approx1.416667\)
- \(x_3\approx1.414216\)
- \(x_4\approx1.414214\)
Il valore della radice, arrotondato a sei cifre decimali, è:
$$ \sqrt{2}\approx1.414214 $$
Dopo quattro iterazioni ottengo quindi un'approssimazione corretta a sei cifre decimali.
Quando converge il metodo?
Il metodo di Newton-Raphson è particolarmente efficiente quando il valore iniziale \( x_0 \) è sufficientemente vicino alla radice cercata.
Se la funzione è sufficientemente regolare e la radice è semplice, ossia la derivata prima non si annulla in corrispondenza della radice, il metodo presenta generalmente una convergenza quadratica.
Questo significa che, quando le approssimazioni sono abbastanza vicine alla soluzione, il numero di cifre decimali corrette tende a raddoppiare a ogni iterazione.
Tuttavia, la convergenza non è sempre garantita. Se il valore iniziale è scelto male, il procedimento può allontanarsi dalla radice oppure oscillare senza convergere.
Inoltre, non è possibile applicare la formula quando la derivata prima si annulla nel punto utilizzato per l'iterazione.
Per questo motivo, la scelta del valore iniziale è molto importante per l'efficacia del metodo.
Come scegliere il valore iniziale?
Per favorire la convergenza del metodo di Newton-Raphson posso scegliere il valore iniziale \(x_0\) in base al segno della derivata seconda.
Considero un intervallo \([a,b]\) che contiene una sola radice, in cui la funzione è continua, cambia segno agli estremi, la derivata prima è continua e non si annulla e la derivata seconda è continua e mantiene un segno costante diverso da zero.
In queste condizioni, scelgo come valore iniziale l'estremo dell'intervallo in cui la funzione e la sua derivata seconda hanno lo stesso segno:
$$ \boxed{f(x_0)\cdot f''(x_0)>0} $$
Perché questa scelta favorisce la convergenza?
La derivata seconda determina la concavità della curva e, di conseguenza, la posizione della retta tangente rispetto al grafico.
- Se \(f''(x)>0\), la funzione è convessa e le rette tangenti si trovano al di sotto della curva. Scelgo quindi l'estremo in cui \(f(x)>0\).
- Se invece \(f''(x)<0\), la funzione è concava e le rette tangenti si trovano al di sopra della curva. In questo caso scelgo l'estremo in cui \(f(x)<0\).
In entrambi i casi, la tangente interseca l'asse delle ascisse tra il punto iniziale e la radice cercata.
Ripetendo il procedimento, ottengo una successione monotona di approssimazioni che si avvicinano alla radice senza oltrepassarla.
Nota. Questo criterio è una condizione sufficiente per garantire la convergenza nelle ipotesi indicate, ma non è necessario: il metodo può convergere anche partendo da altri punti.
Esempio pratico
Considero la funzione:
$$ f(x)=x^2-2 $$
Voglio trovare una radice nell'intervallo \([1,2]\).
Calcolo il valore della funzione agli estremi:
$$ f(1)=1^2-2=-1 $$
$$ f(2)=2^2-2=2 $$
La funzione cambia segno nell'intervallo, quindi, essendo continua, ha almeno una radice compresa tra 1 e 2.
Calcolo la derivata prima e la derivata seconda:
$$ f'(x)=2x $$
$$ f''(x)=2>0 $$
La derivata prima è positiva e la derivata seconda è positiva in tutto l'intervallo. La funzione è quindi crescente e convessa.
Quale valore iniziale devo scegliere?
Poiché la derivata seconda è positiva, scelgo l'estremo in cui anche la funzione è positiva, ossia \(x_0=2\).
Verifico la condizione:
$$ f(2)\cdot f''(2)=2\cdot2=4>0 $$
Applico la formula di Newton-Raphson:
$$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} $$
Partendo da \(x_0=2\), ottengo:
$$ x_1=2-\frac{2^2-2}{2\cdot2}=1.5 $$
Ripeto il procedimento:
$$ x_2=1.5-\frac{1.5^2-2}{2\cdot1.5} $$
$$ x_2\approx1.416667 $$
Con una terza iterazione ottengo:
$$ x_3\approx1.414216 $$
Le approssimazioni sono decrescenti e si avvicinano alla radice positiva:
$$ \sqrt{2}\approx1.414214 $$
Perché il metodo converge?
La funzione è convessa, quindi la retta tangente si trova al di sotto della curva. Partendo da \(x_0=2\), dove la funzione è positiva, la tangente interseca l'asse delle ascisse tra il punto iniziale e la radice.
La stessa proprietà vale per le tangenti successive. Ogni nuova approssimazione è quindi più vicina alla radice, senza oltrepassarla.
In questo modo ottengo una successione decrescente che converge a \(\sqrt{2}\).
Calcolo delle radici quadrate, cubiche o ennesime
Il metodo di Newton-Raphson può essere utilizzato anche per calcolare la radice quadrata, cubica o di indice qualsiasi di un numero.
Esempio
Voglio calcolare la radice quadrata di 5:
$$ \sqrt{5} $$
Per applicare il metodo di Newton-Raphson devo trasformare il problema in un'equazione della forma \(f(x)=0\).
Pongo:
$$ x=\sqrt{5} $$
Elevo entrambi i membri al quadrato:
$$ x^2=5 $$
Porto tutti i termini al primo membro:
$$ x^2-5=0 $$
In questo modo, il calcolo di \(\sqrt{5}\) si riconduce alla ricerca della radice positiva della funzione:
$$ f(x)=x^2-5 $$
Calcolo la derivata prima:
$$ f'(x)=2x $$
Sostituisco le due espressioni nella formula di Newton-Raphson:
$$ x_{n+1}=x_n-\frac{x_n^2-5}{2x_n} $$
Semplifico l'espressione:
$$ x_{n+1}=\frac{2x_n^2-x_n^2+5}{2x_n} $$
$$ \boxed{x_{n+1}=\frac12\left(x_n+\frac5{x_n}\right)} $$
Scelgo come valore iniziale \(x_0=2\) e calcolo la prima approssimazione:
$$ x_1=\frac12\left(2+\frac52\right)=2.25 $$
Ripeto il procedimento utilizzando il valore appena ottenuto:
$$ x_2=\frac12\left(2.25+\frac5{2.25}\right) $$
$$ x_2\approx2.236111 $$
Calcolo una terza approssimazione:
$$ x_3=\frac12\left(x_2+\frac5{x_2}\right) $$
$$ x_3\approx2.236068 $$
Dopo tre iterazioni ottengo un'approssimazione della radice quadrata di 5 corretta a sei cifre decimali:
$$ \boxed{\sqrt5\approx2.236068} $$
Posso generalizzare il procedimento?
Per calcolare la radice di indice \(n\) di un numero positivo \(a\), considero la funzione:
$$ f(x)=x^n-a $$
La sua derivata prima è:
$$ f'(x)=nx^{n-1} $$
Applicando il metodo di Newton-Raphson e semplificando, ottengo:
$$ \boxed{x_{k+1}=\frac1n\left((n-1)x_k+\frac{a}{x_k^{n-1}}\right)} $$
Questa formula mi permette di calcolare un'approssimazione della radice \(\sqrt[n]{a}\), partendo da un valore iniziale positivo e ripetendo il procedimento fino a raggiungere la precisione desiderata.
Dimostrazione
Per comprendere come si ottiene la formula, considero una funzione derivabile \(f(x)\) e cerco una radice dell'equazione:
$$ f(x)=0 $$
Scelgo un valore iniziale \(x_0\) vicino alla radice cercata e individuo sul grafico della funzione il punto \(P(x_0,f(x_0))\).
Traccio la retta tangente al grafico nel punto \(P\). La sua equazione è:
$$ y-f(x_0)=f'(x_0)(x-x_0) $$
La retta tangente interseca l'asse delle ascisse in un punto di ascissa \(x_1\). Poiché sull'asse delle ascisse l'ordinata è nulla, pongo \(y=0\) e \(x=x_1\):
$$ 0-f(x_0)=f'(x_0)(x_1-x_0) $$
Divido entrambi i membri per \(f'(x_0)\), supponendo che sia diverso da zero:
$$ -\frac{f(x_0)}{f'(x_0)}=x_1-x_0 $$
Isolo \(x_1\):
$$ x_1=x_0-\frac{f(x_0)}{f'(x_0)} $$
Ho così ottenuto una nuova approssimazione della radice. Il valore \(x_1\) è l'ascissa del punto in cui la tangente interseca l'asse delle ascisse, non necessariamente la radice esatta della funzione.
Per migliorare l'approssimazione, ripeto il procedimento partendo da \(x_1\). Traccio una nuova tangente al grafico nel punto \((x_1,f(x_1))\) e calcolo la sua intersezione con l'asse delle ascisse:
$$ x_2=x_1-\frac{f(x_1)}{f'(x_1)} $$
Ripetendo il procedimento, ottengo la formula generale del metodo di Newton-Raphson:
$$ \boxed{x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}} $$
Questa formula mi permette di calcolare ogni nuova approssimazione utilizzando quella precedente.
Interpretazione geometrica
Dal punto di vista geometrico, il metodo di Newton-Raphson consiste nel sostituire localmente la curva con la sua retta tangente.
L'intersezione della tangente con l'asse delle ascisse fornisce una nuova approssimazione della radice.
Ripetendo il procedimento, ottengo una successione di punti che, se il metodo converge, si avvicinano progressivamente alla radice reale.
E così via.
