Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi a più passi. Esempi

I Metodo del punto medio
R tn+1
y (tn+1 ) = y (tn−1 ) + tn−1 f (t, y (t)) dt

= y (tn−1 ) + 2hf (tn , y (tn )) + O(h3 )

un+1 = un−1 + 2hf (tn , un )

I Metodo di Simpson
R tn+1
y (tn+1 ) = y (tn−1 ) + tn−1 f (t, y (t)) dt

2h
= y (tn−1 ) + 6 [f (tn−1 , y (tn−1 )) + 4f (tn , y (tn )) + f (tn+1 , y (tn+1 ))]
+O(h5 )
h
un+1 = un−1 + [f (tn−1 , un−1 ) + 4f (tn , un ) + f (tn+1 , u(tn+1 ))]
3
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi a più passi

I Un metodo si dice a q passi (q ≥ 1) se un+1 dipende da

un+1−q ma non da valori di uk per k < n + 1 − q.
I Per innescare un metodo a più passi servono q condizioni
iniziali.
Poichè il problema di Cauchy ne fornisce una sola, per
assegnare le condizioni mancanti si utilizzano metodi espliciti
ad un passo di ordine elevato.
I Un generico metodo a p + 1 passi è della forma
p
X p
X
un+1 = aj un−j + h bj f (tn−j , un−j ) + hb−1 f (tn+1 , un+1 )
j=0 j=0

Se b−1 6= 0 lo schema è implicito

 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi a più passi

Per un metodo a più passi, l’errore di troncamento locale è definito

da
 
p p
1 X X
τn+1 (h) := y (tn+1 ) − aj y (tn−j ) − h bj f (tn−j , y (tn−j ))
h
j=0 j=−1

e l’errore di troncamento globale è definito da

τ (h) = max |τn (h)|

p≤n≤N

Come per i metodi a un passo, un metodo a più passi si dice

consistente se
τ (h) → 0 per h → 0
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi a più passi

Dato il metodo a p + 1 passi

Xp Xp

 u
n+1 = aj un−j + h bj f (tn−j , un−j ) n = p, . . . , N − 1
 j=0 j=−1
un = wn n = 0, . . . p


consideriamo anche la successione data da

  
 Xp Xp

zn+1 = aj zn−j + h  bj f (tn−j , zn−j ) + δn+1  n = p, . . . , N − 1


 j=0 j=−1
zn = wn + δn n = 0, . . . p


Il metodo si dice stabile se esiste h0 > 0 e una costante C > 0 tali

che per ogni h ∈ (0, h0 ]
|zn − un | ≤ C  per 0≤n≤N
se |δn | <  per 0 ≤ n ≤ N.
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi a più passi

Sia
p
X p
X
un+1 = aj un−j + h bj f (tn−j , un−j )
j=0 j=−1
un metodo multistep e sia
p
X
ρ(r ) = r p+1 − aj r p−j .
j=0

Il metodo multistep soddisfa la condizione delle radici se tutte le

radici di ρ(r ) sono contenute nel cerchio unità centrato nell’origine
e le radici che si trovano sul bordo sono radici semplici.
Per un metodo multistep consistente la condizione delle radici è
equivalente alla stabilità.

Stabilità + consistenza ⇒ convergenza

(se l’errore sui dati iniziali tende a zero per h che tende a zero.)
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi di Adams

Sia (Πp f )(t) il polinomio di grado p che interpola la funzione

f (t, y (t)) in p + 1 punti.
Z tn+1 Z tn+1
y (tn+1 ) = y (tn ) + f (t, y (t)) dt ≈ y (tn ) + (Πp f )(t) dt
tn tn

I Se i nodi di interpolazione sono tn , tn−1 , . . . , tn−p lo schema è

esplicito e si ha un metodo di Adams-Bashforth.
I Se i nodi sono tn+1 , tn , . . . , tn+1−p lo schema è implicito e si
ha un metodo di Adams-Moulton.
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi di Adams-Bashforth

I Per p = 0 (metodo ad un passo)

Z tn+1
y (tn+1 ) ≈ y (tn ) + f (tn , y (tn )) dt
tn

un+1 = un + hf (tn , un ) Eulero esplicito

I Per p = 1 (metodo a due passi)
t − tn−1 t − tn
(Π1 f )(t) = f (tn , y (tn )) + f (tn−1 , y (tn−1 ))
tn − tn−1 tn−1 − tn

h
un+1 = un + [3f (tn , un ) − f (tn−1 , un−1 )]
2
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi di Adams-Moulton
I Per p = 0 (metodo ad un passo)
Z tn+1
y (tn+1 ) ≈ y (tn ) + f (tn+1 , y (tn+1 )) dt
tn

un+1 = un + hf (tn+1 , un+1 ) Eulero implicito

I Per p = 1 (metodo ad un passo)
t − tn t − tn+1
(Π1 f )(t) = f (tn+1 , y (tn+1 )) + f (tn , y (tn ))
tn+1 − tn tn − tn+1
h
un+1 = un + [f (tn+1 , un+1 ) + f (tn , un )] Crank-Nicolson
2
I Per p = 2 (metodo a due passi)
h
un+1 = un + [5f (tn+1 , un+1 ) + 8f (tn , un ) − f (tn−1 , un−1 )]
12
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi di Adams

I Per i metodi di Adams a q passi ρ(r ) = r q − r q−1 quindi le

radici sono r0 = 1 e r1 = 0 con moltiplicità q − 1. Sono
pertanto metodi stabili.
I In generale i metodi di Adams-Bashforth a q passi sono
consistenti di ordine q e i metodi di Adams-Moulton a q passi
di ordine q + 1.
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi predictor-corrector

I La risoluzione di un problema di Cauchy non lineare con un

metodo implicito richiede la risoluzione di una equazione non
lineare.
I Ad esempi usando il metodo di Crank-Nicolson
h
un+1 = un + [f (tn+1 , un+1 ) + f (tn , un )]
2
un+1 = Ψ(un+1 )
I Per risolvere questa equazione si può usare una iterazione di
punto fisso della forma
(k+1) (k)
un+1 = Ψ(un+1 ) .
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi predictor-corrector

I La condizione di convergenza di questo metodo di punto fisso

comporta una limitazione sul passo di discretizzazione.
(0)
I Bisogna fornire anche un buon dato iniziale un+1 . Questo
può essere fatto usando un metodo multistep esplicito.
I Per contenere il costo computazionale si itera poi per un
numero fissato m di iterazioni.
I In questo modo il metodo implicito correge il valore di un+1
“predetto” dallo schema multistep esplicito.
I il metodo che si ottiene è detto metodo predictor-corrector.
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi predictor-corrector. Esempio

Predictor un+1 = un + h2 (3fn − fn−1 )

h
Corrector un+1 = un + 12 (5fn+1 + 8fn − fn−1 )
(k) (k)
fm := f (tm , um ), fm := f (tm , um )
(0) (1) (1) (1)
(P) un+1 = un + h2 (3fn − fn−1 )

(0) (0)
(E) fn+1 = f (tn+1 , un+1 )

(1) (1) h (0) (1) (1)

(C) un+1 = un + 12 (5fn+1 + 8fn − fn−1 )

(1) (1)
(E) fn+1 = f (tn+1 , un+1 )
Questa procedura viene indicata come procedura PECE.
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi predictor-corrector. Esempio

Se lo schema predictor è di ordine k e lo schema corrector è di

ordine k ∗ allora il metodo predictor-corrector PECE si comporta
come un metodo di ordine min(k ∗ , k + 1).

In questo esempio il metodo predictor-corrector risulta essere di

ordine 3:
I Adams-Bashforth a due passi predictor di ordine k = 2.
I Adams-Moulton a due passi corrector di ordine k ∗ = 3.
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

I metodi predictor-corrector. Esempio

Più economica è la procedura PEC:

(0) (1) (0) (0)
(P) un+1 = un + h2 (3fn − fn−1 )

(0) (0)
(E) fn+1 = f (tn+1 , un+1 )

(1) (1) h (0) (0) (0)

(C) un+1 = un + 12 (5fn+1 + 8fn − fn−1 )
 Risoluzione numerica di equazioni differenziali ordinarie Metodi a più passi

Metodi a più passi. Esercizi

I Verificare che il metodo di Adams-Bashforth

h
un+1 = un + [3f (tn , un ) − f (tn−1 , un−1 )]
2
è consistente di ordine 2.
I Verificare che lo schema PECE che usa Eulero esplicito come
metodo predictor e Crank-Nicolson come metodo corrector è il
metodo di Heun.
I Verificare che il metodo a più passi
4 1 2h
un+1 = un − un−1 + f (tn+1 , un+1 )
3 3 3
è convergente.