Metodi numerici per ODE

Metodi numerici per ODE

Problema di Cauchy

Consideriamo un’equazione differenziale (sistema di equazioni) del primo ordine in forma normale con condizioni iniziali

assegnate.

 y ⁰ (x ) = f (x , y (x )) x ∈ [x 0 , x _F ] y (x ₀ ) = y ₀



 

 



 

 



y ₁ ⁰ (x ) = f ₁ (x , y ₁ (x ), . . . , y _n (x )) y ₂ ⁰ (x ) = f ₂ (x , y ₁ (x ), . . . , y _n (x ))

. . . x ∈ [x ₀ , x _F ]

y _n ⁰ (x ) = f _n (x , y ₁ (x ), . . . , y _n (x ))

y ₁ (x ₀ ) = y ₀ ⁽¹⁾ , y ₂ (x ₀ ) = y ₀ ⁽²⁾ , . . . , y n (x ₀ ) = y ₀ ⁽ⁿ⁾

Si ricordi che un’equazione differenziale di ordine n esprimibile

in forma normale, pu `o essere sempre ricondotta a un sistema

di n equazioni differenziali di ordine uno.

Questioni teoriche: esistenza e unicit `a della soluzione

Teorema Sia f(x, y) una funzione definita nella striscia

S = {(x , y )| x ∈ [x ₀ , x _F ]; y ∈ R ⁿ }, ivi continua rispetto a x e a y e che gode di una condizione di Lipschitz rispetto a y in S, ossia esiste L > 0 (costante di Lipschitz) tale che

kf (x, y ₁ ) − f (x , y ₂ )k ≤ Lky ₁ − y ₂ k per ogni y ₁ , y ₂ ∈ R ⁿ e per ogni x ∈ [x ₀ , x _F ].

Allora per ogni ¯ x ∈ [x ₀ , x _F ] e per ogni ¯ y ∈ R ⁿ esiste una e una

sola funzione y (x ) continua e differenziabile con continuit `a in

[x ₀ , x _F ] tale che y (x ) soddisfa y ⁰ (x ) = f (x , y (x )) in [x ₀ , x _F ] e

y (¯ x ) = ¯ y .

Questioni teoriche

Dipendenza continua dai dati: si studia il comportamento della soluzione quando la pertubazione sul dato iniziale tende a zero.

Condizionamento: perturbazione sul dato iniziale fissata.

Infatti non possiamo farla tendere a zero!

Il condizionamento `e legato a ∂f /∂y .

Se ∂f /∂y < 0, le soluzioni ottenute a partire da differenti valori iniziali tendono a diminuire la loro distanza per x crescente.

Il problema `e ben condizionato (stabile).

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35

0 0.2 0.4 0.6 0.8 1 1.2 1.4

dato iniziale dato perturbato soluzione sol. prob. perturbato

Questioni teoriche

Se ∂f /∂y > 0, segue che la distanza tra due soluzioni ottenute a partire da valori iniziali di poco diversi, aumenta al crescere di x. Il problema `e mal condizionato (instabile).

0 0.005 0.01 0.015 0.02 0.025 0.03

0 5 10 15 20 25

dato iniziale dato perturbato soluzione sol. prob. perturbato

Metodi numerici

Nelle applicazioni, si richiede che f (x , y ) sia sufficientemente regolare, ossia che ammetta derivate parziali continue e limitate fino all’ordine p, con p > 1, in S.

La risoluzione numerica del problema di Cauchy si basa su una discretizzazione del dominio I = [x ₀ , x _F ] che pu `o essere fatta a passo costante o a passo variabile.

Si decompone I in µ sottointervalli di ampiezza h n , con i nodi dati da

x _n = x ₀ +

n

X

j=1

h _j .

Se h _n = h, allora x _n = x ₀ + nh. In tal caso la discretizzazione `e a passo costante. Ci `o capita raramente nelle applicazioni.

I metodi numerici risolutivi si propongono di determinare una

successione di valori y _n , n = 1 . . . , µ, ove y _n rappresenta una

approssimazione della soluzione analitica incognita in x _n , ossia

y n `e una approssimazione di y (x n ).

Metodi numerici

Il valore di y n si ottiene mediante approssimazioni calcolate in k passi precedenti.

Se k = 1, si parla di metodi ad un passo.

In questo caso y _n viene calcolato a partire dall’approssimazione y _n−1 .

Se k > 1, si parla di metodi multipasso.

Metodo di Eulero

Metodo semplice da illustrare ma non efficiente nella maggior parte delle applicazioni.

x _i+1 = x _i + h, y _i+1 = y _i + hf (x _i , y _i ), i = 0, . . . , µ − 1

E un metodo di ordine 1. `

Metodi Runge Kutta

Formula generale

y _i+1 = y _i + h

s

X

j=1

b _j f _j dove

f ₁ = f (x _i , y _i ), f _j = f (x _i + c _i h, y _i + h

j−1

X

l=1

a _jl f _l ), j = 2, . . . , s

Il numero s indica il numero di stadi ovvero il numero di

valutazioni della funzione f .

Esempi di metodi Runge Kutta

Il metodo di Heun

Utilizza due valutazioni funzionali (due stadi).

E’ un metodo di ordine 2.

x _i+1 = x _i + h, y _i+1 = y _i + h

2 (f ₁ + f ₂ ) dove

f ₁ = f (x _i , y _i ), f ₂ = f (x _i + h, y _i + hf ₁ )

Esempi di metodi Runge Kutta

Il metodo a tre stadi di ordine 3 y _i+1 = y _i + h

6 (f ₁ + 4f ₂ + f ₃ ) dove

f ₁ = f (x _i , y _i ) f ₂ = f (x _i + h

2 , y _i + h

2 f ₁ )

f 3 = f (x _i + h, y _i + h(2f 2 − f 1 ))

Attenzione: il numero di stadi NON `e pari all’ ordine del metodo!

Butcher ha provato una relazione tra il numero s degli stadi di una formula Runge Kutta esplicita e il suo ordine k .

s 1 2 3 4 5 6 7 8 9

k 1 2 3 4 4 5 6 6 7

Considerazioni pratiche: scelta del metodo

Metodo accurato: richiede pi `u valutazioni funzionali ad ogni passo, ma generalmente l’accuratezza richiesta `e raggiunta con h ”non troppo piccolo” ⇒ maggiore efficienza.

0 1 2 3 4 5 6

0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4

soluzione esatta eulero passo h=0.3 heun passo h=0.3

1 1.5 2

soluzione esatta eulero passo h=0.1 heun passo h=0.1

Considerazioni pratiche: scelta del passo

Passo troppo piccolo comporta elevato costo sia in termini di calcolo che di occupazione della memoria.

In ogni caso non posso scendere sotto una certa soglia in quanto gli errori di arrotondamento supererebbero quelli locali di troncamento.

Il passo deve essere scelto in modo che il metodo sia

numericamente stabile.

Considerazioni pratiche: scelta del passo

Il passo deve essere tale che (λh) appartenga ad una certa regione: la regione di assoluta stabilit `a del metodo.

Regioni di assoluta stabilit `a dei metodi RK

Ordine Intervalli di assoluta stabilit `a

1 (-2,0)

2 (-2,0)

Considerazioni pratiche: scelta del passo

Scelta di h : il pi `u grande possibile in modo da ottenere una soluzione approssimata entro una certa tolleranza.

Quale criterio uso per fare ci `o? In generale si usa un

criterio che si basa sulla stima dell’errore locale (di

troncamento).

Scelta del passo

Supponiamo di avere un metodo di ordine p y _n+1 = y n + h n Φ(x n , y n )

e consideriamo la soluzione locale del problema che passa per il punto (x _n , y _n )

 u ⁰ (x ) = f (x , u(x )) x ∈ [x n , x _F ] u(x _n ) = y _n

L’ errore locale in x _n+1 `e definito come

el(x _n+1 ) = y _n+1 − u(x _n+1 ), mentre l’errore globale `e

eg(x _n+1 ) = y _n+1 − y (x _n+1 ).

Sappiamo che el(x _n+1 ) = O(h ^p+1 ) e che eg(x _n+1 ) = O(h ^p ).

Stimare l’errore globale `e problematico. In generale si lavora su

Scelta del passo

Fissiamo una tolleranza tol (accuratezza richiesta) e

consideriamo un secondo metodo di ordine superiore a p, per esempio di ordine p + 1. Abbiamo perci `o una coppia di metodi che a partire dal punto (x n , y n ) ci forniscono due

approssimazioni di ordine diverso nel punto successivo x _n+1 : y _n+1 = y _n + h _n Φ(x _n , y _n )

y ˆ _n+1 = y _n + h _n Φ(x ˆ _n , y _n ).

Si dimostra che |el(x _n+1 )| ≈ |ˆ y _n+1 − y _n+1 |.

Scelta del passo

Se la stima dell’errore locale ottenuta con il passo h _n `e inferiore alla tolleranza fissata, il passo usato va bene e si accetta il valore y <sub>n+1</sub> . In caso contrario il passo utilizzato `e troppo grande e si deve ripartire da (x _n , y _n ) con un passo pi `u piccolo, in

genere si dimezza.

Scelta automatica del passo

Fisso un passo iniziale h ₀ = H e vado in x ₁ . Calcolo la quantit `a

el ₁ . Fino a quando |el ₁ | > tol, dimezzo il passo h 0 = h ₀ /2,

torno in x ₀ e ripeto. Quando el ₁ ≤ tol accetto il passo h ₀ . Sono

nel nuovo punto x ₁ . Con che passo mi muovo per andare nel

punto successivo?

Scelta del passo

In genere non si usa quello precedente, ma si usa un passo tentativo che dovrebbe garantire che l’approssimazione calcolata sia accurata:

h ₁ = 0.9

s

tol el ₁ h ₀ .

Con questo passo vado in x ₂ , stimo l’errore locale...

In generale, supponiamo di essere arrivati in x n con passo h _n−1 , che abbiamo accettato. Il passo tentativo per trovare l’approssimazione successiva sar `a

h _n = 0.9

s

tol

el _n h _n−1 .