Calcolo numerico/Condizionamento test e stabilità dei metodi di punto fisso

Condizionamento

Un problema è ben condizionato se, variando di poco i dati del problema, si ottengono piccole variazioni nel risultato. Per studiare il condizionamento del metodo, supponiamo quindi di avere $f(x)=\varphi (x)-D$, con $D$ piccola perturbazione della $\varphi$ originaria.

Supponiamo che la funzione $\varphi$ sia invertibile, allora $f(\alpha )=0$ se e solo se $\varphi (\alpha )=D$, e quindi $\alpha ={\varphi }^{-1}(D)$. Sia $G_D={\varphi }^{-1}(D)=\alpha$, e $\alpha$ la radice di $\varphi$. L'espressione per l'indice di condizionamento è:

$I_{cond}=\frac{D}{G_D}\ast (G_D{)}^{\prime }$

$=\frac{D}{\alpha }\ast ({\varphi }^{-1}{)}^{\prime }=\frac{D}{\alpha }\ast \frac{1}{{\varphi }^{\prime }(\alpha )}$

allora il problema è ben condizionato se ${\varphi }^{\prime }(\alpha )$ è grande, mentre è mal condizionato se ${\varphi }^{\prime }(\alpha )$ è piccolo. Questo equivale a dire che nel caso di una funzione "piatta" nell'intorno della radice (cioè ${\varphi }^{\prime }(\alpha )$ piccolo) il problema è mal condizionato.

Test del residuo

Data la successione di iterate $\{x_k\}$ generate dal metodo, a ogni iterata si calcola $|\varphi (x_k)|$. Se $|f(x_k)|<\epsilon$ con $\epsilon$ fissato, l'approssimazione della radice è già buona e il metodo si arresta. Facciamo l'ipotesi che $f$ sia di classe $C^1$, allora, siccome $f(\alpha )=0$ si ha:

$f(x_k)=f(x_k)-f(\alpha )=f^{\prime }({\eta }_k)\ast (x_k-\alpha ),\alpha <{\eta }_k<x_k,$

con ${\eta }_k-\alpha <x_k-\alpha$, dove l'ultimo passaggio deriva dall'applicazione del teorema del valor medio.

Segue che $x_k-\alpha =\frac{f(x_k)}{f^{\prime }({\eta }_k)}$, e passando al valore assoluto e supponendo $|f(x_k)|\le \epsilon$ si ha:

$|x_k-\alpha |\le \frac{\epsilon }{f^{\prime }({\eta }_k)}$

e quindi l'errore assoluto è ben controllato dal residuo.

Supponiamo che la successione di iterate $\{x_k\}$ converga ad $\alpha$, quindi $f^{\prime }({\eta }_k)\to f^{\prime }(\alpha )$, e il modo con cui il residuo controlla l'errore assoluto dipende anche da $f^{\prime }(\alpha )$. Considerando

$f(\alpha )\le \frac{\epsilon }{f^{\prime }(\alpha )},$

segue che:

1. se $|f^{\prime }(\alpha )|=1$ il test è buono;
2. se $|f^{\prime }(\alpha )|<1$ il termine a destra cresce molto, e il test non dà informazioni, perché a un residuo piccolo può corrispondere un errore grande. Si conclude che il test del residuo non dà informazioni quando il problema è mal condizionato $f^{\prime }(\alpha )$ piccolo);
3. se $|f^{\prime }(\alpha )|>>1$, il test è troppo restrittivo, perché pur avendo già trovato una buona approssimazione della radice, il metodo non si ferma perché il test del residuo non è soddisfatto.

Test dell'incremento

Calcolo le iterate finché

$|x_{k+1}-x_k|\le \epsilon$

Supponiamo di generare una successione di iterate tramite una generica funzione $\varphi$, e supponiamo che $\varphi$ sia di classe $C^1$. Tenendo conto della definizione delle iterate si può scrivere:

$x_{k+1}-\alpha =\varphi (x_k)-\varphi (\alpha )={\varphi }^{\prime }({\eta }_k)\ast (x_k-\alpha )$

con $|{\eta }_k-\alpha |<|x_k-\alpha |$ per il teorema del valor medio. Determiniamo la relazione tra l'errore relativo e l'incremento:

$x_{k+1}-x_k=x_{k+1}-\alpha -(x_k-\alpha )={\varphi }^{\prime }({\eta }_k)\ast (x_k-\alpha )-(x_k-\alpha )=(x_k-\alpha )\ast ({\varphi }^{\prime }({\eta }_k)-1)$

quindi

$x_k-\alpha =\frac{x_{k+1}-x_k}{{\varphi }^{\prime }({\eta }_k)-1}$

e in valore assoluto l'errore assoluto è controllato da

$\frac{\epsilon }{|{\varphi }^{\prime }({\eta }_k)-1|}$

A differenza del caso precedente:

1. se ${\varphi }^{\prime }(\alpha )\simeq 1$ il test non dà informazioni;
2. se ${\varphi }^{\prime }(\alpha )=0$ si è nel caso favorevole, perché l'incremento controlla l'errore assoluto (bilanciamento ottimale).

Si considera un metodo superlineare con $p\ge 2$ (ad esempio il metodo di Newton nel caso in cui $\alpha$ sia semplice). Per questo metodo il test dell'incremento è buono.

Stabilità

Supponiamo di voler calcolare la successione di iterate $\{x_{k+1}\}$ a partire da un punto di innesco, con la legge $x_{k+1}=\varphi (x_k)$, e indichiamo con $\{{\overline{x}}_k\}$ la successione delle iterate effettivamente ottenute sul calcolatore.

Può succedere che ${\overline{x}}_k$ non convergono ad $\alpha$, pur appartenendo a un intorno della radice di raggio via via più piccolo fino a una certa soglia.

Proposizione 4.2

Nelle ipotesi precedenti, supponiamo

${\overline{x}}_k=\varphi ({\overline{x}}_{k-1})+{\delta }_k$

con ${\delta }_k$ errore commesso localmente. Assumo per comodità che tutti i ${\delta }_k$ siano maggiorati da un certo $\delta$. Sia $\alpha$ un punto fisso di $\varphi$, $\alpha \in (\alpha -\rho ,\alpha +\rho )$, e sia $\lambda =\underset{|x-\alpha |\le \rho }{max}|{\varphi }^{\prime }(x)|$. Se definisco $\sigma =\frac{\delta }{1-\lambda }<\rho$, consideriamo un qualsiasi $x_0$ tale che $d(\alpha ,x_0)<\rho$, e supponiamo per comodità che ${\overline{x}}_0=x_0$ (assenza di errore iniziale), allora segue che

$|{\overline{x}}_k-\alpha |\le \sigma +{\lambda }^k(\rho -\sigma ),\mathrm{\forall }k\ge 0$

Dim. Dimostro per induzione.

1. Se $k=0$, la tesi è vera perché $|{\overline{x}}_0-\alpha |\le \rho$ per ipotesi, e $\rho =\sigma +{\lambda }^0(\rho -\sigma )$.

2. Ipotesi induttiva: $|{\overline{x}}_{k-1}-\alpha |\le \sigma +{\lambda }^{k-1}(\rho -\sigma )$

3. Dimostriamo l'asserto per $k$:

$|{\overline{x}}_k-\alpha |=|\varphi ({\overline{x}}_{k-1})+{\delta }_k-\alpha |=|\varphi ({\overline{x}}_{k-1})+{\delta }_k-\varphi (\alpha )|$

$\le |\varphi ({\overline{x}}_{k-1})-\varphi (\alpha )|+|\delta |$

e applicando il teorema del valor medio:

$\le |{\varphi }^{\prime }({\eta }_k)|\ast |{\overline{x}}_{k-1}-\alpha |+\delta ,{\eta }_k-\alpha \le {\overline{x}}_{k-1}-\alpha \le \rho$

con $|{\varphi }^{\prime }({\eta }_k)|\le \lambda$ per ipotesi del teorema.

$|{\overline{x}}_k-\alpha |\le \lambda \ast |{\overline{x}}_{k-1}-\alpha |+\delta$

e applicando le ipotesi del teorema:

$\le \lambda (\sigma +{\lambda }^{k-1}(\rho -\sigma ))+\delta$

e sostituendo l'espressione di $\delta =(1-\lambda )\ast \sigma$

$\le \lambda \ast (\sigma +{\lambda }^{k-1}(\rho -\sigma ))+\sigma (1-\lambda )\le {\lambda }^k(\rho -\sigma )+\sigma$

cvd