Metodo di Newton

Consideriamo f di classe $C^{(1)}$, l'idea di base del metodo di Newton consiste nel partire da un punto iniziale $x_{0}$, trovare l'intersezione tra la retta tangente alla f in ( $x_{0},f(x_{0})$) e l'asse delle ascisse e prendere questo punto come $x_{1}$ (approssimazione della radice al passo 1) e quindi reiterare il metodo che in forma compatta diventa

$$x_{i+1}=x_{i} - \frac{f(x_{i})}{f^{\prime}(x_{i})} \quad i=0\ldots$$ (2.5)

Il metodo per radici semplici ha convergenza quadratica e per radici multiple lineare, si tratta tuttavia di convergenza locale e questo é il principale svantaggio nell'utilizzo di questo metodo in luogo di quello di bisezione. Il punto di innesco $x_{0}$ deve essere scelto perciò in un opportuno intorno della radice (sconosciuta).

La procedura riceve in input la funzione della quale trovare la radice e la sua derivata, che deve quindi essere conosciuta per via analitica. Un approccio alternativo potrebbe essere quello di approssimare la derivata con un rapporto incrementale con incremento prossimo allo zero ma in questo caso sarebbe difficile determinare quanto piccolo debba essere l'incremento per ottenere un risultato sufficientemente accurato.

[x,passi]=Newton(f,df,x0,epsilon,upper) - Applica il metodo di Newton alla funzione $f$, la cui derivata è $df$, con punto iniziale $x_{0}$, accuratezza epsilon e numero massimo di passi upper. Restituisce in $x$ la radice (se trovata) e in passi, il numero di passi effettuati.

%NEWTON
%[x,passi]=newton(f,df,x0,epsilon,upper)
%  Pre: f derivabile
%  Applica il metodo di Newton per il calcolo della
%  radice dell'equazione f(x)=0
%  f       - funzione
%  df      - derivata prima di f
%  x0      - punto di innesco
%  epsilon - tolleranza per la radice
%  upper   - numero massimo di iterazioni consentite 
%
%  Restituisce in x la radice trovata e in passi il numero
%  di iterazioni che sono state necessarie per reggiungerla
%  See also BISEZ,  CORDE, SECANTI.

function [x,passi]=newton(f,df,x0,epsilon,upper)
count=0;
f0=feval(f,x0);
d=feval(df,x0);

while(count<upper) & (abs(f0)>abs(epsilon*d))
	count=count+1;
	d=feval(df,x0);
    x0=x0-(f0/d);
    f0=feval(f,x0);   
end
x=x0;
passi=count;
return

>> type f_e

function y=f_e(x)
y=exp(x)-1;


>> [x,passi]=Newton('f_e','exp',4,1E-19,200)

x =

    1.692401153459279e-017


passi =

    10

Nella figura 2.1 vediamo un esempio del metodo di Newton applicato alla funzione $y=e^x-1$ con punto di partenza $x_0=4$. Il metodo di Newton trova la radice $\overline{x}=0$ con un errore dell'ordine di $10^{-17}$ in 10 passi. Il procedimento è illustrato in figura 2.1

Figura 2.1: Metodo di Newton applicato alla funzione $y=e^x-1$ con punto di partenza $x_0=4$. Converge alla radice $\overline{x}=0$ in 10 passi.