Metodo di Newton

Per questo metodo si richiede che $f \in \mathbb{C}^1$ che significa che la funzione deve essere continua, derivabile e a derivata continua ma non si suppone l'esistenza della soluzione come si faceva nel metodo di bisezione.

Il metodo di Newton approssima la funzione con la retta tangente ad essa nel punto di coordinate $(x_0, f(x_0))$ e si prende il nuovo punto di approssimazione come l'intersezione di questa retta con l'asse delle $x$, reiterando nuovamente il procedimento. Se sviluppiamo nuovamente la funzione in serie di Taylor arrestandoci al primo ordine si ottiene:

$$f(x) \approx fa(x) = f(x_k) + f'(x_k)(x-x_k)$$

scegliendo $x_{k+1}$ in modo tale che $fa(x_{k+1})=0$ quello che si ottiene è

$$\begin{eqnarray*} fa(x_{k+1}) & = & f(x_k)+f'(x_k)(x_{k+1}-x_k)=0\\ x_{k+1} & = & x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$$

otteniamo quindi la relazione ricorsiva

$$\left\{ \begin{array}{l} x_0 \mbox{ assegnato} \\ x_{k+1}=x_k - \frac{f(x_k)}{f'(x_k)} \end{array} \right.$$

La convergenza del metodo di Newton è locale, cioè si deve scegliere $x_0$ abbastanza vicino ad $\overline{x}$ perché il metodo converga; questo inconveniente non si aveva con il metodo di bisezione, che garantiva la convergenza qualsiasi fosse l'intervallo scelto (che rispettasse le richieste).

Teorema 1 (del punto fisso)   Sia $\phi : \mathbb{R} \rightarrow \mathbb{R}$ una funzione continua $( \in \mathbb{C}^0)$ e tale che $\overline{x}= \phi (\overline{x})$, allora $\overline{x}$ è detto punto fisso di $\phi$. Se $\exists 0 < L <1$ ed un intorno di $\overline{x}$ di raggio $r$ $(I(\overline{x},r))$ tale che

$$\forall x,y \in I : \vert\phi (x) - \phi(y)\vert \leq L\vert x-y\vert$$

allora la successione definita da

$$\left\{ \begin{array}{l} x_0 \in I \mbox{ assegnato} \\ x_{k+1}= \phi(x_k) \end{array} \right.$$

è tale che

$$\lim_{k \rightarrow + \infty} x_k = \overline{x}$$

Dividiamo adesso lo studio della convergenza nel caso di radici semplici e radici multiple, definendo prima cosa si intenda per molteplicità di una radice:

Definizione 1   Si dice che $\overline{x}$ è radice di $f$ con molteplicità $p$ $(p\in \mathbb{Z} \geq 1)$ se e solo se

$$f(\overline{x})=f'(\overline{x})= \cdots = f^{(p-1)}(\overline{x})=0 \mbox{ e } f^{(p)}(\overline{x}) \not= 0 \mbox{.}$$

Se $p=1$ $\overline{x}$ si dice radice semplice.