Condizionamento test e stabilità dei metodi di punto fisso

(Pywikibot v.2)
 
Riga 1: Riga 1:
 
==Condizionamento==
 
==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 <math>f(x) =\phi(x)-D</math>, con <math>D</math> piccola perturbazione della <math>\phi</math> originaria.
 
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 <math>f(x) =\phi(x)-D</math>, con <math>D</math> piccola perturbazione della <math>\phi</math> originaria.
 
  
 
Suppongo che la funzione <math>\phi</math> sia invertibile, allora <math>f(\alpha)=0</math> se e solo se <math>\phi(\alpha)=D</math>, e quindi <math>\alpha = \phi^{-1}(D)</math>.
 
Suppongo che la funzione <math>\phi</math> sia invertibile, allora <math>f(\alpha)=0</math> se e solo se <math>\phi(\alpha)=D</math>, e quindi <math>\alpha = \phi^{-1}(D)</math>.
 
Sia <math>G_D=\phi^{-1}(D)=\alpha</math>, e <math>\alpha</math> la radice di <math>\phi</math>.
 
Sia <math>G_D=\phi^{-1}(D)=\alpha</math>, e <math>\alpha</math> la radice di <math>\phi</math>.
L'espressione per l'indice di condizionamento è:
+
L'espressione per l'indice di condizionamento è:<math display="block">I_{cond} = \frac{D}{G_D}*(G_D)'</math><math display="block">=\frac{D}{\alpha}*(\phi^{-1})' = \frac{D}{\alpha}*\frac{1}{\phi'(\alpha)}</math>allora il problema è ben condizionato se <math>\phi'(\alpha)</math> è grande, mentre è mal condizionato se <math>\phi'(\alpha)</math> è piccolo.
<math display="block">I_{cond} = \frac{D}{G_D}*(G_D)'</math><math display="block">=\frac{D}{\alpha}*(\phi^{-1})' = \frac{D}{\alpha}*\frac{1}{\phi'(\alpha)}</math>
 
allora il problema è ben condizionato se <math>\phi'(\alpha)</math> è grande, mentre è mal condizionato se <math>\phi'(\alpha)</math> è piccolo.
 
 
Questo equivale a dire che nel caso di una funzione "piatta" nell'intorno della radice (cioè <math>\phi'(\alpha)</math> piccolo) il problema è mal condizionato.
 
Questo equivale a dire che nel caso di una funzione "piatta" nell'intorno della radice (cioè <math>\phi'(\alpha)</math> piccolo) il problema è mal condizionato.
  
 
==Test del residuo==
 
==Test del residuo==
Data la successione di iterate <math>\{ x_k \}</math> generate dal metodo, ad ogni iterata si calcola <math>|\phi(x_k)|</math>. Se <math>|f(x_k)|<\varepsilon</math> con <math>\varepsilon</math> fissato, l'approssimazione della radice è già buona e il metodo si arresta. Facciamo l'ipotesi che <math>f</math> sia di classe <math>C^1</math>, allora, siccome <math>f(\alpha)=0</math> si ha:
+
Data la successione di iterate <math>\{ x_k \}</math> generate dal metodo, ad ogni iterata si calcola <math>|\phi(x_k)|</math>. Se <math>|f(x_k)|<\varepsilon</math> con <math>\varepsilon</math> fissato, l'approssimazione della radice è già buona e il metodo si arresta. Facciamo l'ipotesi che <math>f</math> sia di classe <math>C^1</math>, allora, siccome <math>f(\alpha)=0</math> si ha:<math display="block">f(x_k) = f(x_k)-f(\alpha) = f'(\eta_k)*(x_k-\alpha), \, \quad \alpha<\eta_k<x_k,</math>con <math>\eta_k-\alpha < x_k-\alpha</math>, dove l'ultimo passaggio deriva dall'applicazione del teorema del valor medio.
<math display="block">f(x_k) = f(x_k)-f(\alpha) = f'(\eta_k)*(x_k-\alpha), \, \quad \alpha<\eta_k<x_k,</math>
 
con <math>\eta_k-\alpha < x_k-\alpha</math>, dove l'ultimo passaggio deriva dall'applicazione del teorema del valor medio.
 
 
 
  
 
Segue che <math>x_k-\alpha = \frac{f(x_k)}{f'(\eta_k)}</math>, e passando al valore assoluto
 
Segue che <math>x_k-\alpha = \frac{f(x_k)}{f'(\eta_k)}</math>, e passando al valore assoluto
 
e supponendo <math>|f(x_k)| \le \varepsilon</math> si ha:
 
e supponendo <math>|f(x_k)| \le \varepsilon</math> si ha:
<math display="block">|x_k-\alpha| \le \frac{\varepsilon}{f'(\eta_k)}</math>
+
<math display="block">|x_k-\alpha| \le \frac{\varepsilon}{f'(\eta_k)}</math>e quindi l'errore assoluto è ben controllato dal residuo.<br>
e quindi l'errore assoluto è ben controllato dal residuo.
+
Supponiamo che la successione di iterate <math>\{ x_k \}</math> converga ad <math>\alpha</math>, quindi <math>f'(\eta_k) \to f'(\alpha)</math>, e il modo con cui il residuo controlla l'errore assoluto dipende anche da <math>f'(\alpha)</math>. Considerando<math display="block">f(\alpha) \le \frac{\varepsilon}{f'(\alpha)},</math>segue che:
 
 
 
 
Supponiamo che la successione di iterate <math>\{ x_k \}</math> converga ad <math>\alpha</math>, quindi <math>f'(\eta_k) \to f'(\alpha)</math>, e il modo con cui il residuo controlla l'errore assoluto dipende anche da <math>f'(\alpha)</math>. Considerando
 
<math display="block">f(\alpha) \le \frac{\varepsilon}{f'(\alpha)},</math>
 
segue che:
 
  
 
#se <math>|f'(\alpha)|=1</math> il test è buono;
 
#se <math>|f'(\alpha)|=1</math> il test è buono;
Riga 31: Riga 20:
  
 
==Test dell'incremento==
 
==Test dell'incremento==
Calcolo le iterate finché
+
Calcolo le iterate finché<math display="block">|x_{k+1}-x_k| \le \varepsilon</math>Suppongo di generare una successione di iterate tramite una generica funzione <math>\phi</math>, e suppongo che <math>\phi</math> sia di classe <math>C^1</math>. Tenendo conto della definizione delle iterate si può scrivere:<math display="block">x_{k+1}-\alpha = \phi(x_k)-\phi(\alpha) = \phi'(\eta_k)*(x_k-\alpha)</math>con <math>|\eta_k-\alpha| < |x_k-\alpha|</math> per il teorema del valor medio.
<math display="block">|x_{k+1}-x_k| \le \varepsilon</math>
+
Determiniamo la relazione tra l'errore relativo e l'incremento:<math display="block">x_{k+1}-x_k = x_{k+1}-\alpha-(x_k-\alpha) = \phi'(\eta_k)*(x_k-\alpha)-(x_k-\alpha) = (x_k-\alpha)*(\phi'(\eta_k)-1)</math>quindi<math display="block">x_k-\alpha = \frac{x_{k+1}-x_k}{\phi'(\eta_k)-1}</math>e in valore assoluto l'errore assoluto è controllato da<math display="block">\frac{\varepsilon}{|\phi'(\eta_k)-1|}</math>A differenza del caso precedente:
 
 
Suppongo di generare una successione di iterate tramite una generica funzione <math>\phi</math>, e suppongo che <math>\phi</math> sia di classe <math>C^1</math>. Tenendo conto della definizione delle iterate si può scrivere:
 
<math display="block">x_{k+1}-\alpha = \phi(x_k)-\phi(\alpha) = \phi'(\eta_k)*(x_k-\alpha)</math>
 
con <math>|\eta_k-\alpha| < |x_k-\alpha|</math> per il teorema del valor medio.
 
Determiniamo la relazione tra l'errore relativo e l'incremento:
 
<math display="block">x_{k+1}-x_k = x_{k+1}-\alpha-(x_k-\alpha) = \phi'(\eta_k)*(x_k-\alpha)-(x_k-\alpha) = (x_k-\alpha)*(\phi'(\eta_k)-1)</math>
 
quindi
 
<math display="block">x_k-\alpha = \frac{x_{k+1}-x_k}{\phi'(\eta_k)-1}</math>
 
e in valore assoluto l'errore assoluto è controllato da
 
<math display="block">\frac{\varepsilon}{|\phi'(\eta_k)-1|}</math>
 
A differenza del caso precedente:
 
  
 
#Se <math>\phi'(\alpha)\simeq 1</math> il test non dà informazioni.
 
#Se <math>\phi'(\alpha)\simeq 1</math> il test non dà informazioni.
Riga 52: Riga 30:
 
==Stabilità==
 
==Stabilità==
 
Supponiamo di voler calcolare la successione di iterate <math>\{ x_{k+1} \}</math> a partire da un punto di innesco, con la legge <math>x_{k+1} = \phi(x_k)</math>, e indichiamo con <math>\{ \bar x_k \}</math> la successione delle iterate effettivamente ottenute sul calcolatore.
 
Supponiamo di voler calcolare la successione di iterate <math>\{ x_{k+1} \}</math> a partire da un punto di innesco, con la legge <math>x_{k+1} = \phi(x_k)</math>, e indichiamo con <math>\{ \bar x_k \}</math> la successione delle iterate effettivamente ottenute sul calcolatore.
Può succedere che <math>\bar x_k</math> non convergono ad <math>\alpha</math>, pur appartenendo ad un intorno della radice di raggio via via più piccolo fino ad una certa soglia.
+
Può succedere che <math>\bar x_k</math> non convergono ad <math>\alpha</math>, pur appartenendo ad un intorno della radice di raggio via via più piccolo fino ad una certa soglia.{{InizioProposizione|titolo=|number=4.2|anchor=Proposizione4_2}}
 
+
Nelle ipotesi precedenti, supponiamo<math display="block">\bar x_k = \phi (\bar x_{k-1})+\delta_k</math>con <math>\delta_k</math> errore commesso localmente. Assumo per comodità che tutti i <math>\delta_k</math> siano maggiorati da un certo <math>\delta</math>. Sia <math>\alpha</math> un punto fisso di <math>\phi</math>, <math>\alpha \in (\alpha-\rho, \alpha+\rho)</math>, e sia <math>\lambda = \max_{|x-\alpha| \le \rho} |\phi'(x)|</math>. Se definisco <math>\sigma = \frac{\delta}{1-\lambda} < \rho</math>, considero un qualsiasi <math>x_0</math> tale che <math>d(\alpha,x_0) < \rho</math>, e suppongo per comodità che <math>\bar x_0 = x_0</math> (assenza di errore iniziale), allora segue che<math display="block">|\bar x_k-\alpha| \le \sigma+\lambda^k (\rho-\sigma), \, \forall k \ge 0</math>
 
 
{{InizioProposizione|titolo=|number=4.2|anchor=Proposizione4_2}}
 
Nelle ipotesi precedenti, supponiamo
 
<math display="block">\bar x_k = \phi (\bar x_{k-1})+\delta_k</math>
 
con <math>\delta_k</math> errore commesso localmente. Assumo per comodità che tutti i <math>\delta_k</math> siano maggiorati da un certo <math>\delta</math>. Sia <math>\alpha</math> un punto fisso di <math>\phi</math>, <math>\alpha \in (\alpha-\rho, \alpha+\rho)</math>, e sia <math>\lambda = \max_{|x-\alpha| \le \rho} |\phi'(x)|</math>. Se definisco <math>\sigma = \frac{\delta}{1-\lambda} < \rho</math>, considero un qualsiasi <math>x_0</math> tale che <math>d(\alpha,x_0) < \rho</math>, e suppongo per comodità che <math>\bar x_0 = x_0</math> (assenza di errore iniziale), allora segue che
 
<math display="block">|\bar x_k-\alpha| \le \sigma+\lambda^k (\rho-\sigma), \, \forall k \ge 0</math>
 
 
{{FineProposizione}}
 
{{FineProposizione}}
  
Riga 67: Riga 39:
 
#Se <math>k=0</math>, la tesi è vera perché <math>|\bar x_0-\alpha| \le \rho</math> per ipotesi, e <math>\rho =\sigma+\lambda^0 (\rho-\sigma)</math>.
 
#Se <math>k=0</math>, la tesi è vera perché <math>|\bar x_0-\alpha| \le \rho</math> per ipotesi, e <math>\rho =\sigma+\lambda^0 (\rho-\sigma)</math>.
 
#Ipotesi induttiva: <math>|\bar x_{k-1}-\alpha| \le \sigma+\lambda^{k-1} (\rho-\sigma)</math>
 
#Ipotesi induttiva: <math>|\bar x_{k-1}-\alpha| \le \sigma+\lambda^{k-1} (\rho-\sigma)</math>
#Dimostriamo l'asserto per <math>k</math>:<math display="block">|\bar x_k-\alpha| = |\phi(\bar x_{k-1})+\delta_k-\alpha| = |\phi(\bar x_{k-1})+\delta_k-\phi(\alpha)|</math><math display="block">\le |\phi (\bar x_{k-1})-\phi(\alpha)|+|\delta|</math>e applicando il teorema del valor medio:<math display="block">\le |\phi'(\eta_k)|*|\bar x_{k-1}-\alpha|+\delta, \quad \eta_k-\alpha \le \bar x_{k-1}-\alpha \le \rho</math>con <math>|\phi'(\eta_k)| \le \lambda</math> per ipotesi del teorema.<math display="block">|\bar x_k-\alpha| \le \lambda*|\bar x_{k-1}-\alpha|+\delta</math>e applicando le ipotesi del teorema:<math display="block">\le \lambda(\sigma+\lambda^{k-1} (\rho-\sigma))+\delta</math>e sostituendo l'espressione di <math>\delta = (1-\lambda)*\sigma</math><math display="block">\le \lambda*(\sigma+\lambda^{k-1}(\rho-\sigma))+\sigma(1-\lambda) \le \lambda^k (\rho-\sigma)+\sigma</math>
+
#Dimostriamo l'asserto per <math>k</math>:<math display="block">|\bar x_k-\alpha| = |\phi(\bar x_{k-1})+\delta_k-\alpha| = |\phi(\bar x_{k-1})+\delta_k-\phi(\alpha)|</math><math display="block">\le |\phi (\bar x_{k-1})-\phi(\alpha)|+|\delta|</math>e applicando il teorema del valor medio:<math display="block">\le |\phi'(\eta_k)|*|\bar x_{k-1}-\alpha|+\delta, \quad \eta_k-\alpha \le \bar x_{k-1}-\alpha \le \rho</math>con <math>|\phi'(\eta_k)| \le \lambda</math> per ipotesi del teorema.<math display="block">|\bar x_k-\alpha| \le \lambda*|\bar x_{k-1}-\alpha|+\delta</math>e applicando le ipotesi del teorema:<math display="block">\le \lambda(\sigma+\lambda^{k-1} (\rho-\sigma))+\delta</math>e sostituendo l'espressione di <math>\delta = (1-\lambda)*\sigma</math><math display="block">\le \lambda*(\sigma+\lambda^{k-1}(\rho-\sigma))+\sigma(1-\lambda) \le \lambda^k (\rho-\sigma)+\sigma</math>cvd{{FineDimostrazione}}
 
 
 
 
cvd
 
{{FineDimostrazione}}
 

Versione delle 14:34, 20 set 2017

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