Soluzione degli esercizi sul metodo di Newton

Soluzione degli esercizi sul metodo di Newton

Template:Navigazione lezione

Esercizio 1

• Ecco una possibile implementazione del metodo di Newton con Octave/MATLAB:

function [x e iter]=newton(f,df,x0,err,itermax)
%The function newton find the zeros of function
%with the Newton algorithm.
%It returns the zero x, the error e, and the number of iteration needed iter
%
%HOW TO USE IT:
%Example
%>>f=@(x)x.^2-1;
%>>df=@(x)2*x;
%>>err=1e-5; itermax=1000;
%>>[x e iter]=newton(f,df,err,itermax);

iter=0;
e=2*err;
x=x0;
while ( e > err )
	iter = iter + 1;
	e = abs(f(x)./df(x));	
	x=x-f(x)./df(x)
	if(iter == itermax)
		break;
	end
end

Esercizio 2

Si consideri la successione generata dal metodo di Newton

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

e si supponga esista $z$ unico zero della funzione. Allora abbiamo tre casi:

1. $x_0=z$

   In questo caso ovviamente la successione converge in quanto si ha che

   $x_k=z\mathrm{\forall }k\ge 0.$

2. $x_0>z$

   Notiamo che se $x_k>z$ allora $f(x_k)>0$ e dalla definizione del metodo di Newton si ottiene

   $x_{k+1}-x_k=-\frac{f(x_k)}{f^{\prime }{x}_k}<0,⟹x_{k+1}<x_k,$

   ovvero la successione è decrescente. Dalla formula per l'errore se vede invece che

   $z-x_{k+1}=-\frac{f^{″}({\eta }_k)}{2f^{\prime }(x_k)}(z-x_k{)}^2<0⟹z<x_{k+1}.$

   Quindi la successione degli $x_k$ è decrescente e limitata, ovvero esiste finito il suo limite

   $\underset{k\to \mathrm{\infty }}{\lim }{x}_k=\alpha .$

   Dalla definizione del metodo di Newton si ha che $f(\alpha )=0$ e quindi per l'unicità dello zero si ha che $\alpha =z$.

3. $x_0<z$

   Procedendo come per il punto precedente, essendo ora $f(x_0)<0$, si ha che

   $x_1-x_0=-\frac{f(x_0)}{f^{\prime }{x}_0}>0,⟹x_1>x_0,$

   Tuttavia abbiamo anche che

   $z-x_1=-\frac{f^{″}({\eta }_0)}{2f^{\prime }(x_0)}(z-x_0{)}^2<0⟹z<x_1.$

   Quindi scelto $x_0<z$ si ha che $x_1>z$ e quindi la successione converge per quanto mostrato nel punto precedente ( prendendo ${\overline{x}}_0=x_1$).