Metodi multipasso

Aumento dell'ordine di convergenza[modifica | modifica wikitesto]

Per aumentare l'ordine di convergenza del metodo ci sono due strade possibili:

  1. metodi multipasso: usano informazioni precedenti ma rimangono lineari, ne sono esempi i metodi di Adam-Bashword (espliciti), di Adam-Multonn (impliciti), di Mistrom, i generalized Simpson (espliciti e impliciti), BDF usate nel caso dei problemi stiff.
  2. metodi a un passo non lineari

Metodi multipasso lineare[modifica | modifica wikitesto]

I metodi di questo tipo si definiscono come

dove
sono tali che e
Osservo che se il metodo è esplicito perché a secondo membro non compare la soluzione da calcolare al passo corrente, mentre diversamente è implicito, e si può pensare di applicare il metodo del punto fisso
Dev'essere .

Teorema 7.2

Considero i seguenti polinomi

con variabile complessa (primo polinomio caratteristico).
e considero il metodo
Il metodo è consistente, (cioè l'errore di troncamento locale tende a 0 per ) se valgono le seguenti condizioni:

  1. ( tende a 0 quindi tutti gli istanti tendono a )

con .

 
Dimostrazione

Affermo che

con con per il teorema del valor medio.
Considero l'errore di troncamento:
e in base a quanto appena ricavato per :
e spezzando le somme
Per e

Segue quindi che si ha consistenza se

e se

 

Nella pratica tenendo conto che si impongono le condizioni di consistenza:

Relazione tra convergenza e consistenza[modifica | modifica wikitesto]

Se ho convergenza, allora ho consistenza, ma non vale viceversa. Per avere convergenza, oltre alla consistenza devo richiedere la 0-stabilità.
Definizione 7.4

Considero un problema di Cauchy perturbato

Si dice che il problema è ben posto o totalmente stabile se per qualunque coppia di perturbazioni e tali che
segue che, posto le soluzioni dei corrispondenti problemi di Cauchy, esiste una costante positiva tale che per ogni ,

 

Definizione corrispondente nel discreto: Consideriamo un sistema di differenze perturbato.

Il metodo è 0-stabile se, date le successioni delle perturbazioni , e che corrispondono a soluzioni per e per , se esiste una costante positiva ed esiste tale che scelto , segue che la norma della differenza tra le due soluzioni discrete è minore di , dove suppongo che . (la differenza rispetto alla definizione precedente è che deve esistere tale per cui si abbia la conservazione dell'entità della perturbazione)

Stabilità come condizione necessaria[modifica | modifica wikitesto]

Questo esempio mostra che è necessario richiedere la stabilità.

Esempio 7.1

Considero il problema di Cauchy

Applicando il metodo multipasso:
perché (e quindi il secondo membro) è identicamente nullo.
sono molto piccoli ma non esattamente nulli.
Questa è un'equazione alle differenze omogenea. Il polinomio
ha radici distinte rispettivamente con molteplicità , allora la soluzione dell'equazione alle differenze è
(simile alla scrittura delle soluzioni nell'equazioni differenziali nel continuo)
Se , il metodo diverge, e lo stesso avviene nel caso in cui il modulo di z è uguale a 1 e ha molteplicità maggiore di .

 

Root condition[modifica | modifica wikitesto]

Definizione 7.5

Considero e chiamo le sue radici, per . è detta radice principale, e le altre radici per sono le radici spurie.

 


Definizione 7.6 (root condition)

Il metodo numerico

soddisfa la root condition se tute le radici del polinomio caratteristico sono in modulo e quelle per cui vale che hanno molteplicità algebrica 1.

 


Teorema 7.3

Il metodo numerico

è 0-stabile se e solo se vale la root condition.

 


Teorema 7.4

Il metodo

è convergente se e solo se è consistente e 0-stabile.

 


Teorema 7.5 (prima barriera di Dahlquist)

Nessun metodo lineare multipasso a passi che sia 0-stabile può avere ordine di convergenza maggiore di se è dispari, e di se è pari.

 

Espressione dei polinomi caratteristici nei metodi multipasso[modifica | modifica wikitesto]

  1. Nei metodi di Adam-Bashword e Adam-Multonn il polinomio caratteristico è della forma
    e è la radice principale necessaria per la consistenza, e c'è poi la radice 0 con molteplicità .
  2. Nel Simpson generalizzato
    dove le radici sono con molteplicità 1, e con molteplicità .
  3. Le BDF hanno il secondo polinomio caratteristico definito come

Metodi di Adam-Bashword[modifica | modifica wikitesto]

I metodi di Adam-Bashword derivano da formule di quadratura. Considero l'equazione integrale

Considero il polinomio interpolante con nodi equispaziati: in particolare, per i metodi espliciti considero il polinomio interpolante di grado p nei nodi , per gli Adam-Multonn considero il polinomio di grado nei nodi e ottengo la formula
Se il metodo è esplicito, altrimenti è implicito.

In conclusione vale il seguente teorema:

Teorema 7.6

I metodi espliciti di Adam-Bashword hanno ordine mentre quelli di Adam-Multonn hanno ordine ad eccezione dell'eulero per cui e .

 

Tecnica del predictor-corrector[modifica | modifica wikitesto]

Consideriamo un metodo multipasso implicito, da risolvere con un metodo di punto fisso. Pongo

e considero la relazione
dove il secondo addendo è noto e ne conosco tutte le quantità. con , e si dà come innesco soluzione all'istante precedente. Si impone quindi
e supponendo di avere le condizioni del teorema di esistenza e unicità
cioè sul passo ottengo la condizione e la costante di Lipschitz condiziona la convergenza del metodo di punto fisso.

Il metodo è costoso, perché ad ogni iterazione del metodo di punto fisso si richiede una valutazione della funzione . Più l'innesco fornito è buono, più velocemente viene soddisfatto il criterio d'arresto, e meno oneroso è il metodo dal punto di vista computazionale.

Metodo Predictor-Corrector[modifica | modifica wikitesto]

Il metodo predictor-corrector consiste dei seguenti passi:

  1. Predictor (): è ottenuto applicando uno schema multipasso esplicito, cioè
  2. evaluation ():
    (ora un'espressione approssimativa di è nota)
  3. Corrector ():

I passi possono essere iterati nel seguente modo:

dove è stato calcolato prima.

Si può quindi considerare anche il metodo:

in cui valutazione e correzione vengono alternate m volte.

Il passo finale è

cioè il metodo si prepara per un'eventuale iterazione.

Se ha ordine i dati di innesco aggiuntivi sono calcolabili con un errore di ordine di e se il corrector è di ordine p, allora ha ordine p.
Esempio 7.2 (esempio di metodo predictor corrector)

Uso come predictor l'Eulero esplicito

e come corrector il metodo dei trapezi:
Questo metodo può anche essere considerato come metodo a un passo.

 
 PrecedenteSuccessivo