Criteri di arresto

Come abbiamo già visto, un criterio di arresto è

$$\vert f(x_k)\vert \leq tolf.$$

Inoltre vorremmo imporre una condizione del tipo:

$$\vert x_k - \overline{x}\vert \leq tolx,$$

ma non siamo in grado di valutarla in quanto non sappiamo qual'è il valore di $\overline{x}$; cerchiamo allora una maggiorazione della quantità $\vert x_k - \overline{x}\vert$ per arrestarci quando questa è minore od uguale a $tolx$.

Come visto in precedenza, prendendo $\phi (x)$ in modo che descriva il metodo di Newton, e cioè nella forma

$$\phi (x) = x- \frac{f(x)}{f'(x)}$$

si può scrivere

$$\forall 0<L<1 \quad \exists \delta >0 \mbox{ tale che } \fora... ...a] \quad \vert\phi (x) - \phi (y) \vert \leq L\vert x-y\vert.$$

Cerchiamo allora di scrivere in modo più utile $\vert x_k - \overline{x}\vert$:

$$\vert x_k - \overline{x}\vert = \vert x_k -x_{k+1} + x_{k+1} ... ...\vert x_k - x_{k+1}\vert + \vert x_{k+1} - \overline{x}\vert =$$

$$= \vert \phi(x_{k-1}) - \phi(x_k)\vert + \vert\phi (x_k) - \phi ( \overline{x})\vert.$$

Scegliendo $x_0 \in [\overline{x}-\delta, \overline{x}+\delta]=I$ tutta la successione generata apparterrà ad $I$, quindi:

$$\vert \phi(x_{k-1}) - \phi(x_k)\vert + \vert\phi (x_k) - \phi... ...\leq L\vert x_{k-1} - x_k\vert + L\vert x_k - \overline{x}\vert$$

$$\vert x_k - \overline{x}\vert \leq L\vert x_{k-1} - x_k\vert + L\vert x_k - \overline{x}\vert$$

$$(1-L)\vert x_k - \overline{x}\vert \leq L\vert x_{k-1} - \ov... ...x}\vert \leq \frac{L}{1-L} \vert x_{k-1} - x_k\vert \leq tolx.$$

Il fattore $\frac{L}{1-L}$ dipende dal punto iniziale e dalla funzione, ma sicuramente

$$\exists x_0 : L=\frac{1}{2} \quad \Rightarrow \quad \frac{L}... ...=1 \quad \Rightarrow \quad \vert x_{k-1} - x_k\vert \leq tolx$$

che è la nostra condizione di arresto.