# Metodo di Newton

Analisi numerica > Metodo di Newton
* Indice delle lezioni di:
** Analisi numerica
* Torna al corso:
** Matematica
Con il metodo di Newton si costruisce la successione degli $\displaystyle x_{k}$ per trovare la radice $\displaystyle \alpha$ di una funzione $\displaystyle f$ partendo da una stima iniziale $\displaystyle x_{0}$. La stima iniziale $x_{0}$ si suppone essere vicino alla radice $\alpha$. Si costruisce, quindi, la tangente di $\displaystyle f$ in $\displaystyle x_{0}$ e si fa una prima approssimazione di $\alpha$ calcolando la radice della tangente. Ripetendo questo processo si ottiene la successione degli $\displaystyle x_{k}$.

## Derivazione del metodo di Newton

Approssimiamo $\displaystyle f(x)$ con uno sviluppo di Taylor intorno a $\displaystyle x_{k}$ fermandoci al secondo ordine
    $f(x)=f(x_{k})+f'(x_{k})(x-x_{k})+{\frac {f''(\eta _{k})}{2}}(x-x_{k})^{2},$
con $\displaystyle \eta _{k}$ preso tra $\displaystyle x$ e $\displaystyle x_{k}$. Imponendo $x=\alpha$ e ricordando che $f(\alpha )=0$ si ottiene
    $\alpha =x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}-{\frac {(\alpha -x_{k})^{2}}{2}}{\frac {f''(\eta _{k})}{f'(x_{k})}}.$
Tralasciando l'ultimo termine, si ottiene un'approssimazione di $\displaystyle \alpha$ che chiamiamo $\displaystyle x_{k+1}$ ottenendo così il
Metodo di Newton:
    $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}.$

## Analisi di convergenza

Risulta chiaro dalla derivazione del metodo che l'errore commesso dal metodo di Newton è dato da
Formula dell'errore per il metodo di Newton:
    $\alpha -x_{k+1}=-{\frac {f''(\eta _{k})}{2f'(x_{k})}}(\alpha -x_{k})^{2}.$
Da questo si nota che se il metodo converge, l'ordine di convergenza è pari a 2. La convergenza del metodo di Newton dipende però dalla scelta della stima iniziale $\displaystyle x_{0}$.
Vale il seguente
Teorema
Si assuma che $f(x),\,f'(x),$ e $\displaystyle f''(x)$ siano continue in un intorno della radice $\displaystyle \alpha$ e che $\displaystyle f'(\alpha )\neq 0$. Allora preso $\displaystyle x_{0}$ sufficientemente vicino a $\displaystyle \alpha$, allora la successione $\displaystyle x_{k}$, con $k\geq 0$, definita dal metodo di Newton converge ad $\alpha$. Inoltre si ha ordine di convergenza $\displaystyle p=2$ essendo
    $\lim _{k\to \infty }{\frac {\alpha -x_{k+1}}{(\alpha -x_{k})^{2}}}=-{\frac {f''(\alpha )}{2f'(\alpha )}}.$
Si prenda un intorno $\displaystyle I$ di raggio $\displaystyle \epsilon$, cioè $\displaystyle I=[\alpha -\epsilon ,\alpha +\epsilon ]$, con $\displaystyle \epsilon$ scelto in modo che $\displaystyle f'(x)\neq 0\;\forall x\in I$. Tale condizione é possibile data la continuitá di $\displaystyle f'(x)$. Si definisce
    $\displaystyle M={\frac {\displaystyle \max _{x\in I}|f''(x)|}{\displaystyle 2\min _{x\in I}|f'(x)|}}$
Dall'equazione per l'errore introdotta precedentemente si ha
    $\displaystyle |\alpha -x_{1}|\leq M|\alpha -x_{0}|^{2}$
    $\displaystyle M|\alpha -x_{1}|\leq M^{2}|\alpha -x_{0}|^{2}$
Scelto $\displaystyle \epsilon \geq |\alpha -x_{0}|$ e $\displaystyle M|\alpha -x_{0}|\leq 1$, si ha allora che $\displaystyle M|\alpha -x_{1}|\leq 1$, $\displaystyle M|\alpha -x_{1}|\leq M|\alpha -x_{0}|$ e quindi che $\displaystyle |\alpha -x_{1}|\leq \epsilon$. Per induzione si trova che $\displaystyle |\alpha -x_{k}|\leq \epsilon$ e che $\displaystyle M|\alpha -x_{k}|\leq 1$, per ogni $\displaystyle k\geq 1$.
Utilizzando nuovamente la formula dell'errore, si vede che
    $\displaystyle M|\alpha -x_{k+1}|\leq (M|\alpha -x_{k}|)^{2}\leq ...\leq (M|\alpha -x_{0}|)^{2k}$
e quindi che
    $\displaystyle |\alpha -x_{k+1}|\leq {\frac {1}{M}}(M|\alpha -x_{0}|)^{2k}$
e data l'ipotesi fatta in precedenza che $\displaystyle M|\alpha -x_{0}|\leq 1$, si vede che $\displaystyle x_{k}\to \alpha$ per $\displaystyle k\to \infty$.
Infine, sempre dalla formula dell'errore, si ha che il punto $\displaystyle \eta _{k}$ é compreso tra $\displaystyle x_{k}$ ed $\displaystyle \alpha$ e quindi, dato che $\displaystyle x_{k}\to \alpha$, $\displaystyle \eta _{k}\to \alpha$
    $\displaystyle$