Ordine di convergenza

Questo dato ci indica quanto velocemente la successione di valori generata da un metodo numerico converge verso la soluzione.

Considerando $e_k =x_k - \overline{x}$ come l'errore relativo commesso al passo $k$, si dice che un metodo ha convergenza $
p\mbox{ }(p \in \mathbb{R} \geq 1)$ se e solo se:

\begin{displaymath}\lim_{k
\rightarrow +\infty} \frac{\vert e_{k+1}\vert}{{\vert e_k\vert}^p} = c \not = 0
\mbox{ e positivo}\end{displaymath}

con $c$ che è detta costate asintotica dell'errore e rappresenta quanto è più piccolo $\vert e_{k+1}\vert$ rispetto a $\vert e_k\vert$. E' utile notare che, nel caso $p=1$ è necessario che $0<c<1$ altrimenti il metodo non convergerebbe, come si vede

\begin{displaymath}\mbox{per } k\gg 1 \quad \vert e_{k+1}\vert \approx c{\vert e_k\vert}^p\end{displaymath}

e se $p=1$ perché converga deve essere $c<1$.

Nel caso del metodo si bisezione, il limite diviene

\begin{displaymath}\lim_{k
\rightarrow +\infty} \frac{\vert e_{k+1}\vert}{{\vert e_k\vert}} = \frac{1}{2} \end{displaymath}

infatti ad ogni passo di dimezza il campo di ricerca. Il metodo di bisezione è quello che si dice un metodo lineare ($p=1$), è lento ma ha il pregio di avere un limite superiore al numero di iterazioni necessarie per ottenere un'approssimazione della soluzione ed in più converge sempre, ha quella che si chiama convergenza totale: qualsiasi sia l'intervallo scelto, che rispetti le ipotesi iniziali, il metodo di bisezione ci porterà verso la soluzione; vedremo che questo comportamento non è comune a tutti gli algoritmi.

Morpheus 2004-01-04