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 , con piccola perturbazione della originaria.


Suppongo che la funzione sia invertibile, allora se e solo se , e quindi . Sia , e la radice di . L'espressione per l'indice di condizionamento è:

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

Test del residuo

Data la successione di iterate generate dal metodo, ad ogni iterata si calcola . Se con fissato, l'approssimazione della radice è già buona e il metodo si arresta. Facciamo l'ipotesi che sia di classe , allora, siccome si ha:

con , dove l'ultimo passaggio deriva dall'applicazione del teorema del valor medio.


Segue che , e passando al valore assoluto e supponendo si ha:

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


Supponiamo che la successione di iterate converga ad , quindi , e il modo con cui il residuo controlla l'errore assoluto dipende anche da . Considerando

segue che:

  1. se il test è buono;
  2. se 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 è malcondizionato ( piccolo).
  3. se , 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é

Suppongo di generare una successione di iterate tramite una generica funzione , e suppongo che sia di classe . Tenendo conto della definizione delle iterate si può scrivere:

con per il teorema del valor medio. Determiniamo la relazione tra l'errore relativo e l'incremento:
quindi
e in valore assoluto l'errore assoluto è controllato da
A differenza del caso precedente:

  1. Se il test non dà informazioni.
  2. Se si è nel caso favorevole, perché l'incremento controlla l'errore assoluto (bilanciamento ottimale).

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

Stabilità

Supponiamo di voler calcolare la successione di iterate a partire da un punto di innesco, con la legge , e indichiamo con la successione delle iterate effettivamente ottenute sul calcolatore. Può succedere che non convergono ad , pur appartenendo ad un intorno della radice di raggio via via più piccolo fino ad una certa soglia.


Proposizione 4.2

Nelle ipotesi precedenti, supponiamo

con errore commesso localmente. Assumo per comodità che tutti i siano maggiorati da un certo . Sia un punto fisso di , , e sia . Se definisco , considero un qualsiasi tale che , e suppongo per comodità che (assenza di errore iniziale), allora segue che

 
Dimostrazione

Dimostro per induzione.

  1. Se , la tesi è vera perché per ipotesi, e .
  2. Ipotesi induttiva:
  3. Dimostriamo l'asserto per :
    e applicando il teorema del valor medio:
    con per ipotesi del teorema.
    e applicando le ipotesi del teorema:
    e sostituendo l'espressione di


cvd

 
 PrecedenteSuccessivo