Da Wikiversità, l'apprendimento libero.
Soluzione degli esercizi sul metodo di Newton
Analisi numerica > Soluzione degli esercizi sul metodo di Newton
Indice delle lezioni di:
Torna al corso:
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
Si consideri la successione generata dal metodo di Newton
x
k
+
1
=
x
k
−
f
(
x
k
)
f
′
(
x
k
)
{\displaystyle \displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}
e si supponga esista
z
{\displaystyle \displaystyle z}
unico zero della funzione.
Allora abbiamo tre casi:
x
0
=
z
{\displaystyle \displaystyle x_{0}=z}
In questo caso ovviamente la successione converge in quanto si ha che
x
k
=
z
∀
k
≥
0.
{\displaystyle \displaystyle x_{k}=z\qquad \forall k\geq 0.}
x
0
>
z
{\displaystyle \displaystyle x_{0}>z}
Notiamo che se
x
k
>
z
{\displaystyle \displaystyle x_{k}>z}
allora
f
(
x
k
)
>
0
{\displaystyle \displaystyle f(x_{k})>0}
e dalla definizione del metodo di Newton si ottiene
x
k
+
1
−
x
k
=
−
f
(
x
k
)
f
′
x
k
<
0
,
⟹
x
k
+
1
<
x
k
,
{\displaystyle \displaystyle x_{k+1}-x_{k}=-{\frac {f(x_{k})}{f'{x_{k}}}}<0,\quad \implies x_{k+1}<x_{k},}
ovvero la successione è decrescente. Dalla formula per l'errore se vede invece che
z
−
x
k
+
1
=
−
f
″
(
η
k
)
2
f
′
(
x
k
)
(
z
−
x
k
)
2
<
0
⟹
z
<
x
k
+
1
.
{\displaystyle z-x_{k+1}=-{\frac {f''(\eta _{k})}{2f'(x_{k})}}(z-x_{k})^{2}<0\quad \implies z<x_{k+1}.}
Quindi la successione degli
x
k
{\displaystyle \displaystyle x_{k}}
è decrescente e limitata, ovvero esiste finito il suo limite
lim
k
→
∞
x
k
=
α
.
{\displaystyle \displaystyle \lim _{k\to \infty }x_{k}=\alpha .}
Dalla definizione del metodo di Newton si ha che
f
(
α
)
=
0
{\displaystyle \displaystyle f(\alpha )=0}
e quindi per l'unicità dello zero si ha che
α
=
z
{\displaystyle \displaystyle \alpha =z}
.
x
0
<
z
{\displaystyle \displaystyle x_{0}<z}
Procedendo come per il punto precedente, essendo ora
f
(
x
0
)
<
0
{\displaystyle \displaystyle f(x_{0})<0}
, si ha che
x
1
−
x
0
=
−
f
(
x
0
)
f
′
x
0
>
0
,
⟹
x
1
>
x
0
,
{\displaystyle \displaystyle x_{1}-x_{0}=-{\frac {f(x_{0})}{f'{x_{0}}}}>0,\quad \implies x_{1}>x_{0},}
Tuttavia abbiamo anche che
z
−
x
1
=
−
f
″
(
η
0
)
2
f
′
(
x
0
)
(
z
−
x
0
)
2
<
0
⟹
z
<
x
1
.
{\displaystyle z-x_{1}=-{\frac {f''(\eta _{0})}{2f'(x_{0})}}(z-x_{0})^{2}<0\quad \implies z<x_{1}.}
Quindi scelto
x
0
<
z
{\displaystyle \displaystyle x_{0}<z}
si ha che
x
1
>
z
{\displaystyle \displaystyle x_{1}>z}
e quindi la successione converge per quanto mostrato nel punto precedente ( prendendo
x
¯
0
=
x
1
{\displaystyle \displaystyle {\bar {x}}_{0}=x_{1}}
).