Convergenza del Metodo di Newton

Il metodo di Newton richiede che

$$f \in C'[a,b]$$

$$\forall x \in [a,b]: f'(x) \neq 0$$

La convergenza del metodo di Newton non è sempre garantita. Esistono diversi teoremi che sotto particolari ipotesi permettono di provarne la convergenza. Alcuni sono detti di convergenza locale e dicono che se $x_o \in \mathscr{I}$ intorno di $\xi$ sufficientemente piccolo allora il metodo converge. Altri sono detti di convergenza globale e dicono che se $x_0$ appartiene a un ben definito intorno $\mathscr{I}$ di $\xi$ allora il metodo converge.

Teorema 3.12 (Convergenza del metodo di Newton)   Sia $f \in \mathcal{C}^2 \left[ a,\,b \right]$ tale che:

• $f(a)f(b) < 0$.
• $f''(x) > 0 \vee f''(x) < 0,\,\,\forall x \in \left[ a,\,b \right]$

  La funzione è ossia strettamente concava o strettamente convessa.

• $f'(x) \neq 0,\,\,\forall x \in \left[ a,\,b \right]$.
• $x_0 \, : \, f(x_0)f''(x_0) > 0$

  La funzione e la derivata seconda hanno ossia segni concordi.

Sotto queste ipotesi di convergenza globale, il metodo di Newton è ben definito e si ha

$$\lim_{n \to +\infty} e_n = \lim_{n \to +\infty} \abs{x_0 - \xi} = 0$$

Lemma 3.4   Sotto le stesse ipotesi, la successione $x_n$ è decrescente.

Dimostrazione 3.2   Quattro casi possibili soddisfano le condizioni iniziali:

$$\begin{cases} f''(x) > 0 \begin{cases}f(a) < 0, f(b) > 0 \\ ... ...) < 0, f(b) > 0 \\ f(a) > 0, f(b) < 0 \\ \end{cases}\end{cases}$$

Si considererà il caso $f''(x) > 0$, $f(a) < 0, f(b) > 0$ (gli altri casi sono simmetrici).

Se $f(a) < 0$ e $f(\xi) = 0$ allora $f' > 0$ in un intorno sinistro sufficientemente piccolo di $\xi$.

Se $f' > 0$ in un intorno sinistro sufficientemente piccolo di $\xi$, poichè $f'' > 0$ allora $f' > 0$ in $[\xi, b]$.

Allora in $[\xi, b]$

$$\frac{f(x_n)}{f'(x_n)} > 0$$

Quindi

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} < x_n$$

$\qedsymbol$

Dimostrazione 3.3  

Si considererà ancora il caso $f''(x) > 0$, $f(a) < 0, f(b) > 0$ (gli altri casi sono simmetrici).

Poichè $f'' > 0$ l'intersezione della tangente con l'asse delle $x$ è sempre a destra dell'intersezione della $f$ con l'asse medesima, dunque $x_n$ è inferiormente limitata da $\xi$: $x_n \ge \xi$.

Per questo e poichè $\{x_n\}$ è decrescente è vero: $\forall n : x_n \in [\xi, b]$.

Posto allora che:

$$\eta = \inf\{x_n\} \qquad (\eta \ge \xi)$$

Poichè $x_n$ è strettamente decrescente:

$$\lim_{n\to\infty} x_n = \eta$$

$$\begin{split}x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \Rightarr... ...} \\ \eta & = \eta - \frac{f(\eta)}{f'(\eta)} \\ \end{split}$$

$$\frac{f(\eta)}{f'(\eta)} = 0 \Rightarrow f(\eta) = 0$$

Allora $\eta$ è soluzione, e per unicità:

$$\eta = \xi$$

$\qedsymbol$

Teorema 3.13 (Maggiorazione dell'errore nel metodo di Newton)   Sia $f \in C^2(\mathscr{I})$ tale che, con $e_n = \lvert x_n - \xi \rvert$:

• $\lim_{n\to\infty} x_n = \xi \Leftrightarrow \lim_{n\to\infty} e_n = 0$
• $\{x_n\} \subset \mathscr{I}, \xi \in \mathscr{I}$ con $\mathscr{I}$ intervallo chiuso e limitato e $f'(x) \neq 0 \ \forall x \in I$

Allora

$$\exists\ C > 0 : e_{n+1} \le C e_n ^2$$

$&sstarf#star;$ Dimostrazione 3.1   Si rammenti:

Teorema 3.14 (Polinomio di Taylor (con resto di Lagrange))   $f \in C^2(x, x_0)$ è esprimibile da un polinomio di Taylor di secondo ordine centrato su $x_0$:

$$f(x) = f(x_0)+ f'(x_0)(x-x_0)+\frac{f''(z)}{2}(x-x_0)^2 \qquad z \in int(x_0, x)$$

Pertanto si può esprimere $f(\xi)$ come

$$f(\xi) = f(x_n) + f'(x_n)(\xi - x_n) + \frac{f''(z_n)}{2}(\xi - x_n)^2$$

Dunque, manipolando algebricamente:

$$\begin{split} f(\xi) = 0 & = f(x_n) + f'(x_n)(\xi - x_n) + \... ...}} \cdot \abs{(\xi-x_n)^2} \\ e_{n+1} &= C_n e_n^2 \end{split}$$

Si ricordi a questo punto il teorema di Weierstrass:

Teorema 3.15 (Teorema di Weierstrass)   Sia $f \in C[a,b]$ chiuso e limitato. Allora

$$\exists(c,d) \in [a,b] : f(c) \le f(x) \le f(d) \qquad \forall\ x \in [a,b]$$

Pertanto, $\abs{f''(x)}$ ha un massimo assoluto in $\mathscr{I}$ e $\abs{f'(x)}$ ha un minimo assoluto in $I$:

$$\begin{split} \vert f''(z_n)\vert& \leq \max_{x \in [a,b]} \... ...rt& \geq \min_{x \in [a,b]} \vert f'(x)\vert = m > 0\end{split}$$

Dunque, scelto $C = \frac{M}{2m}$:

$$C_n = \abs{\frac{f''(z_n)}{2f'(x_n)}} \le \frac{M}{2m} = C$$

E segue dunque:

$$e_{n+1} = C_n e_n^2 \le C e_n^2$$

$\qedsymbol$