Metodo di Newton

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 )}}.$

Dimostrazione

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$