Equazioni differenziali ordinarie

Equazioni differenziali ordinarie

Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica

Problema di Cauchy

Problema. (

Problema di Cauchy

)

Si determini la funzione y tale che



y

0

(x ) = f (x , y (x )), x ≥ x

0

y (x

0

) = y

0

(1)

dove f `

e a valori in R

n

e definita in un sottoinsieme Ω di R × R

n

,

con (x

0

, y

0

) ∈ Ω.

Nota.

Esempi

Esempio (Equazione differenziale ordinaria)



y

0

(x ) = y (x ), x ≥ 0

y (0) = 1

(2)

la cui soluzione `

e exp (x ), `

e un problema di Cauchy con

f (x , y (x )) = y (x ).

Esempio (Sistema di equazioni differenziali ordinarie)







y

₁0

(x ) = −y

2

(x ), x ≥ 0

y

₂0

(x ) = y

1

(x ), x ≥ 0

y

1

(0) = 1, y

2

(0) = 0

(3)

la cui soluzione `

e y (x ) = (y

1

(x ), y

2

(x )) = (cos (x ), sin (x )), `

e un

problema di Cauchy con y = (y

1

, y

2

), x

0

= 0, y (x

0

) = (1, 0) e

Teorema di Picard-Lindel¨

of

Teorema (

Teorema di Picard-Lindel¨

of

)

Sia D = [t

0

− ε, t

0

+ ε] × R

n

. Dato il problema ai valori iniziali



y

0

(t) = f (t, y (t)), t ∈ [t

0

− ε, t

0

+ ε]

y (t

0

) = y

0

se

f : D → R `e una funzione lipschitziana in y cio`e

|f (t, y

₁

) − f (t, y

2

)| ≤ K ky

1

− y

2

k, (t, y

1

), (t, y

2

) ∈ D

f `

e continua in t allora per qualche ε > 0,

Teorema di Cauchy in piccolo

Teorema (Cauchy in piccolo, [2, p.7])

Si supponga che

D sia un

aperto connesso

di R × R

n

;

f : D → R sia una funzione continua in D;

(t

0

, y

0

) un punto interno a D;

la funzione f verifichi la condizione di Lipschitz

kf (t, y

1

) − f (t, y

2

)k ≤ K ky

1

− y

2

k, (t, y

1

), (t, y

2

) ∈ D.

per qualche K ≥ 0.

Allora

esiste

una unica funzione y definita su un intervallo

[t

0

− α, t

0

+ α], per qualche α > 0 tale che



y

0

(t) = f (t, y(t)), t ∈ [t

0

− α, t

0

+ α]

y(t

0

) = y

0

Teorema di Cauchy in grande

Teorema (Cauchy in grande, [5, p.331])

Sia f :

[a, b] × R

n

→ R tale che

f (t, y), t ∈ [a, b], y ∈ R

n

continua nella prima variabile,

soddisfi rispetto alla seconda variabile la condizione di

Lipschitz

kf (t, y

₁

) − f (t, y

2

)k ≤ K ky

1

− y

2

k, t ∈ [a, b], y

1

, y

2

∈

R

n

.

per qualche norma vettoriale k · k e K ≥ 0.

Allora il problema di Cauchy



y

0

(t) = f (t, y(t)), t ∈ [a, b]

y(a) = y

0

(5)

Teoremi di Cauchy

Nota.

Nel teorema diCauchy in piccolosi fornisce un teorema di esistenza e unicit`alocale.

Nel teorema diCauchy in grandesi fornisce un teorema di esistenza e unicit`aglobale.

Nota. (Soluzioni multiple)

Esistono casi in cui il problema di Cauchy hasoluzioni multiple. Ad esempio, il problema



y0(x ) = 2py(x), x > 0 y (x0) = 0

(6) ha per soluzioni, per α ∈ R+

y (x ) = 

y (x ) = (x − α)2, x ≥ α

Metodo di Eulero esplicito

Metodo di Eulero esplicito

Metodo (

Eulero esplicito

, 1768-1770)

Tale metodo consiste nell’approssimare y (x

k+1

) con u

k+1

dove

u

k+1

= u

k

+ h · f (x

k

, u

k

), u

0

= y (x

0

),

(9)

ove

h = x

k+1

− x

k

.

Supponiamo di voler determinare una approssimazione della

soluzione nei punti equispaziati x

k+1

= x

0

+ kh = x

k

+ h con k > 0.

Da

y (x ) ≈ y (x ) + f (x , y (x ))(x − x )

ponendo

x = x

k+1

,

x = x

k

Metodo di Eulero implicito

Similmente, supposto xk+1= x0+ kh = xk+ h con k > 0, da y (x ) ≈ y (x ) + f (x , y (x ))(x − x )

sceltix = xk,x = xk+1 abbiamo

y (xk) ≈ y (xk+1) + f (xk+1, y (xk+1))(xk− xk+1), (11) e quindi portato il termine f (xk+1, y (xk+1))(xk− xk+1) nel membro di sinistra

y (xk+1) ≈ y (xk) + h · f (xk+1, y (xk+1)). (12)

Metodo (Metodo di Eulero implicito)

Tale metodo consiste nell’approssimare y (xk+1) con uk+1 definito da

Eulero implicito

Nota. (Risoluzione equazioni nonlineari)

Evidentemente ad ogni iterazione del metodo di Eulero implicito

u

k+1

= u

k

+ h · f (x

k+1

, u

k+1

), u

0

= y (x

0

)

si richiede di risolvere un’equazione nonlineare nella variabile z del

tipo

z = u

k

+ h · f (x

k+1

, z)

la cui soluzione pu`

o essere calcolata utilizzando ad esempio

col metodo di Newton o

Osservazione

Nota. (Metodi di Eulero e sistemi di equazioni differenziali)

Il problema di Cauchy `e definito da 

y0(x ) = f (x , y (x )), x ≥ x0 y (x0) = y0

(14) dove f `e a valori in Rne definita in un sottoinsieme Ω di R × Rn, con

(x0, y0) ∈ Ω.

Neicasi multivariaticon n > 1, indipendentemente dalla derivazione dovuta alla espansione di Taylor, i metodi

Eulero esplicito: uk+1= uk+ h · f (xk, uk), u0= y (x0)

Eulero implicito: uk+1= uk+ h · f (xk+1, uk+1), u0= y (x0),

Linear Multistep Methods

Definizione (

Linear Multistep Methods

)

I metodi Linear Multistep (abbreviati con LMM) approssimano

y (x

n

) con u

n

, dove

x

n

= x

0

+ nh

e

u

n+1

=

p

X

j =0

a

j

u

n−j

+ h

p

X

j =−1

b

j

f (x

n−j

, u

n−j

)

Nota. Si osservi che

Sono metodi per cui se voglio calcolare un+1necessitano un−p, . . . , un(si chiamanometodi a p + 1 passi). Siccome inizialmente si dispone solo di u0, per calcolare u1, . . . , up, necessari ad innescare il metodo, si utilizzano di solito altre strategie (come ad esempio applicare pi`u volte metodi a un passo, cio`e in cui p = 0, come ad esempio Eulero implicito).

Linear Multistep Methods

Nota.

Metodi basati sull’integrazione numerica ([8, 125])

Si supponga di dover studiare il problema di Cauchy



y0(x ) = f (x , y (x )), x ≥ x0 y (x0) = y0

(15) e di dover approssimare la sua soluzione y nei punti equispaziati xk= x0+ kh. Osserviamo che y (xn+k) = y (xn−j) + Z xn+k xn−j y0(t)dt (16) = y (xn−j) + Z xn+k xn−j f (t, y (t))dt (17)

Sostituiamo ora l’integranda con il polinomio di grado al pi´u p πp(x ) =

p X

i =0

f (xn−i, y (xn−i))Li(x )

Metodi basati sull’integrazione numerica ([8, 125])

Ricaviamo cos´ı, da f (x , y (x )) ≈ πp(x ) =Pq_{i =0}f (xn−i, y (xn−i))Li(x ), posto

β_p,i(k,j )=1 h Z xn+k xn−j Li(t)dt= Z k −j p Y m=0,m6=i s + m −i + mds, i = 0, 1, . . . , p i metodi di tipo LMM, a pi`u passi

y (xn+k) = y (xn−j) + Z xn+k xn−j f (t, y (t))dt ≈ y (xn−j) + Z xn+k xn−j p X i =0 f (xn−i, y (xn−i))Li(t)dt = y (xn−j) + p X i =0 f (xn−i, y (xn−i)) Zxn+k xn−j Li(t)dt = y (xn−j) + h p X i =0

Metodi di Adams-Bashforth (1883)

Ponendok = 1,j = 0in y (xn+k) ≈ y (xn−j) + h p X i =0

β_p,i(k,j )f (xn−i, y (xn−i)).

otteniamo la famiglia di metodiesplicitidiAdams-Bashforth(1883)

un+1= un+ p X

i =0

β_p,i(1,0)f (xn−i, un−i), un−i≈ y (xn−i). Alcuni esempi sono i metodi a p + 1 passi:

Adams-Bashforth (p=0): un+1= un+ hfn(Eulero esplicito); Adams-Bashforth (p=1): un+1= un+h₂(3fn− fn−1);

Adams-Bashforth (p=2): un+1= un+₁₂h(23fn− 16fn−1+ 5fn−2);

Adams-Bashforth (p=3): un+1= un+₂₄h(55fn− 59fn−1+ 37fn−2− 9fn−3). dove fn−3= f (xn−3, un−3), fn−2= f (xn−2, un−2), fn−1= f (xn−1, un−1),

Metodi di Adams-Moulton (1926)

Ponendok = 0,j = 1in y (xn+k) ≈ y (xn−j) + h p X i =0

β_p,i(k,j )f (xn−i, y (xn−i)).

otteniamo la famiglia di metodiimplicitidi Adams-Moulton(1926)

un= un−1+ h p X

i =0

β(0,1)_p,i f (xn−i, un−i), un−i ≈ y (xn−i). Sostituendo n + 1 al posto di n, abbiamo cos´ı

un+1 = un+ h

p X

i =0

β_p,i(0,1)f (xn+1−i, un+1−i)

= un+ h

p−1 X

j =−1

Metodi di Adams-Moulton (1926)

Alcuni esempi di metodi di Adams-Moulton sono i metodi impliciti Adams-Moulton (p=0): un+1= un+ hfn+1(Eulero implicito);

Adams-Moulton (p=1): un+1= un+h 2(fn+1+ fn)(Crank-Nicolson); Adams-Moulton (p=2): un+1= un+₁₂h(5fn+1+ 8fn− fn−1); Adams-Moulton (p=3): un+1= un+₂₄h(9fn+1+ 19fn− 5fn−1+ fn−2). dove fn−2= f (xn−2, un−2), fn−1= f (xn−1, un−1), fn= f (xn, un), fn+1= f (xn+1, un+1).

Si verifica facilmente che tanto i metodi Adams-Bashforth quanto gli Adams-Moulton sono di tipo Linear Multistep Methods.

The Adams-Bashforth methods were designed by John Couch Adams to solve a differential equation modelling capillary action due to Francis Bashforth. Bashforth (1883) published his theory and Adams’numerical method (Goldstine 1977).

Metodi di Nystr¨

om (1925)

Ponendok = 1,j = 1in y (xn+k) ≈ y (xn−j) + h p X i =0

β_p,i(k,j )f (xn−i, y (xn−i)).

otteniamo la famiglia di metodi di Nystr¨om (1925)

un+1= un−1+ h p X i =0

β_p,i(1,1)f (xn−i, un−i), un−i ≈ y (xn−i).

Un esempio `e il metodo del punto medioun+1= un−1+ 2hfn.

Nota.

Un metodo molto noto in questa famiglia `e quello di Milne un+1= un−1+ (h/3) (fn−1+ 4fn+ fn+1)

ottenuto ponendo in (18) i parametri k = 0, j = 2, p = 2 e sostituendo n con n + 1,

Consistenza

Definizione (Errori di troncamento, [2], p.112)

Si risolva un problema di Cauchy (1) nel compatto[x0, b]con il metodo LMM

un+1= p X j =0 ajun−j+ h p X j =−1 bjf (xn−j, un−j), uk≈ y (xk)

con y soluzione di (1), xk= x0+ kh, k = 0, . . . , N, b − h < xN≤ b, e sia

τn(h) := 1 h·  y (xn+1) − ( p X j =0 ajy (xn−j) + h p X j =−1 bjf (xn−j, y (xn−j)))   .

La quantit`aτn(h)chiamaerrore locale di troncamentodel metodo.

La quantit`aτ (h) = maxn=0,...|τn(h)|, assunto che sia stato commesso errore

Analisi convergenza: consistenza

La consistenza rende conto di

come la soluzione y del problema di

Cauchy verifichi lo schema discreto del metodo linear multistep

u

n+1

=

p

X

j =0

a

j

u

n−j

+ h

p

X

j =−1

b

j

f (x

n−j

, u

n−j

).

Osserviamo inoltre che per metodi

espliciti

la quantit´

a detta

residuo

y (x

n+1

) − (

p

X

j =0

a

j

y (x

n−j

) + h

p

X

j =−1

b

j

f (x

n−j

, y (x

n−j

)))

Consistenza Eulero esplicito

Teorema (Errore locale di troncamento di Eulero esplicito)

Sia y ∈ C2_{([a, b]) l’unica soluzione del problema di Cauchy (1) in [a, b] e} siano xk = a + kh, b − h < xN ≤ b. Allora l’errore locale di troncamento di Eulero esplicito risulta

τk(h) =

y00(ξk)h

2

per qualche ξk ∈ (xk, xk+1), k ∈ 0, . . . , N − 1.

Nota.

Se y ∈ C2_{(a, b), allora per M = max}

Consistenza Eulero esplicito

Dimostrazione.

Osserviamo che se y ∈ C2_{([a, b]), dalla formula di Taylor} y (xk+1) = y (xk) + y0(xk)(xk+1− xk) +

y00(ξ)(xk+1− xk)2 2

Consistenza Eulero implicito

Teorema (Errore locale di troncamento di Eulero implicito)

Sia y ∈ C2_{([a, b]) l’unica soluzione del problema di Cauchy (1) in [a, b] e} siano xk = a + kh, b − h < xN ≤ b. Allora l’errore locale di troncamento di Eulero implicito risulta

τk(h) = −

y00(ξk)h

2

per qualche ξ ∈ (xk, xk+1), k = 0, . . . , N − 1.

Nota.

Se y ∈ C2_{(a, b), allora per M = max}

x ∈[a,b]|y00(x )| τ (h) = max n=0,...,N|τk(h)| =k=0,...,N−1max     −y00_(ξ k)h 2     ≤Mh 2 (21)

Consistenza Eulero implicito

Dimostrazione.

Osserviamo che se y ∈ C2_{([a, b]), dalla formula di Taylor} y (xk) = y (xk+1) + y0(xk+1)(xk− xk+1) +

y00(ξk)(xk− xk+1)2 2

Consistenza LMM

Teorema ([6, p.437])

Un metodo linear multistep ` econsistentese e solo se p X j =0 aj= 1, − p X j =0 jaj+ p X j =−1 bj= 1,

Consistenza LMM

Esempio

Il metodo diEulero Esplicitoha parametri a0= 1, b−1= 0 e b0= 1, p = 0 ed ´e immediato vedere che vale formula relativa allaconsistenza di ordine 1.

Il metodo diEulero Implicitoha parametri a0= 1, b−1= 1 e b0= 0, p = 0 ed ´e immediato vedere che vale formula relativa allaconsistenza di ordine 1.

Il metodo diCrank-Nicolsonha parametri a0= 1, b−1= 1/2, b0= 1/2, p = 0, ed ´e immediato vedere che vale formula relativa alla consistenza di ordine 1. Inoltre per i = 2 si ha

p X j =0 (−j )iaj+ 2 p X j =−1 (−j )i −1bj= . . . = 2b−1= 1

Stabilit`

a di un metodo LMM

Definizione (Zero stabile, [9, p.332])

Si consideri un metodo numerico LMM a p passi per la soluzione di problemi di Cauchy (1) nell intervallo [a, b]. Siano xk= a + khN con hN= (b − a)/N, k = 0, . . . , N. Tale metodo si dicezero-stabilese qualsiasi siano le sequenze {u(hN)

k }, {v

(hN)

k } che sono state generate dal metodo con dati iniziali rispettivamente u(hN) 0 , . . . , u (hN) p−1, v (hN) 0 , . . . , v (hN) p−1, abbiamo max s=0,...,N|u (hN) k − v (hN) k | ≤ K_{s=0,...,p−1}max (|u (hN) s − vs(hN)|)

per hN≤ h∗, con K indipendente da hN.

Questo concetto di stabilit`a viene dettozero-stabilit`a, in quanto determinato esclusivamente dallo studio relativo al problema (1) con f (x , y ) = 0 (cf. [7, p.440]).

Stabilit`

a di un metodo LMM

In generale risulta tedioso studiare caso per caso la stabilit`

a dei

LMM

u

n+1

=

p

X

j =0

a

j

u

n−j

+ h

p

X

j =−1

b

j

f (x

n−j

, u

n−j

)

Risulta pi`

u semplice studiare la cosidetta

root-condition

che `

e un

concetto equivalente.

In particolare questa `

e verificata se e solo se il polinomio

caratteristico

ρ(z) = z

p+1

−

p

X

k=0

a

k

z

k

Stabilit`

a di un metodo LMM

Esempio

Nel caso di Eulero esplicito: un+1= un+ hfn, Eulero implicito: un+1= un+ hfn+1, Crank-Nicolson: un+1= un+h₂(fn+1+ fn), abbiamo un+1= p X j =0 ajun−j+ h p X j =−1 bjf (xn−j, un−j) cona0= 1,p = 0, da cui ρ(z) = zp+1− p X k=0 akzk= z − 1

Convergenza di un metodo LMM

Definizione (Convergenza)

Supponiamo di analizzare il problema di Cauchy nell’intervallo compatto

I = [x0, xfin]. Siano xs= x0+ shN, con NhN= xfin− x0, y(hN)_{= {y (x}

k)}k=0,...,N la soluzione esatta di un fissato problema di Cauchy,

u(hN)_{= {u}

k}k=0,...,N dove uk `e l’approssimazione di y (xk) fornita nei punti xk da un metodo numerico a p + 1 passi.

Un metodo Linear Multistep a p + 1 passi si diceconvergentese qualora i passi iniziali u(hN)

0 , . . . , u (hN)

p sono tali che

η(hN) = max 0≤k≤p|y (hN) k − u (hN) k | → 0 per hN→ 0 si ha che ky(hN)_{− u}(hN)_k ∞→ 0 per hN → 0.

Analisi convergenza

Importante.

Un teorema dovuto a Lax e Richtmyer (1956), mostra che un

metodo `

e convergente se e solo se consistente e stabile.

Di conseguenza, se vengono verificate

le condizioni di consistenza

la root condition,

un metodo `

e convergente.

Corollario

Esempio: Convergenza di Eulero esplicito

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 8 16 32 64 128

Figura:Si consideri il problema di Cauchy y0(x ) = y (x ) in [0, 1] con dato iniziale

Esempio: un metodo consistente ma non stabile

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 10-10 100 1010 1020 1030 1040

1050 Metodo non convergente, ma consistente (Dahlquist, 1956)

10 20 40 80

Figura:Si consideri il problema di Cauchy y0(x ) = y (x ) in [0, 1] con dato iniziale

y (0) = 1, avente soluzione y (x ) = exp(x ) e si applichi il metodo consistente

un+2= −4un+1+ 5un+ hk(4f (xn+1, un+1) + 2f (xn, un)) per approssimare la soluzione nei punti xn= nhk, n = 0, . . . , Nk ove hk= 1/Nk, con dato iniziale u0= 1,

Convergenza di un metodo LMM

Teorema (Convergenza LMM (cf.[2, p.116]), facoltativo)

Sia un+1=Pp_{j =0}ajun−j+ hPp_{j =−1}bjf (xn−j, un−j) e si supponga si debba studiare il problema di Cauchy (1) in [x0, xfin], che

f : [x0, xfin] × R → R sia continua e L-lipschitziana, rispetto la seconda variabile e che la soluzione y ∈ C(1)([x0, xfin]),

i dati iniziali siano calcolati in modo che η(h) = max

i =0,...,p|y (xi) − ui| → 0, per h → 0; il metodo siaconsistente;

aj≥ 0, j = 0, . . . , p;

il passo di discretizzazione h sia tale cheh ≤ h∗= 1/(2c), dove

c = LPp

j =−1|bj|e L `e la costante di Lipschitz di f .

Allora il metodo LMMconvergeed inoltre esistono C1, C2positive tali che per ogni n |y (xn) − un| ≤ C1η(h) + C2τ (h).

Se y ∈ C(m+1)_([x

Convergenza di un metodo LMM

Nota.

Nelle ipotesi del teorema precedente, per ricavare la convergenza chiedavamo: i dati iniziali siano calcolati in modo che

η(h) = max

i =0,...,p|y (xi) − ui| → 0, per h → 0; il metodo siaconsistente;

aj≥ 0, j = 0, . . . , p;

il passo di discretizzazione h sia tale cheh ≤ 1/(2c), dovec = LPp

j =−1|bj|e L

`

e la costante di Lipschitz di f .

Convergenza di un metodo LMM

In particolare, nelle ipotesi richieste,

il metodo diEulero esplicito, avendo ordine di consistenza 1, `e convergente con ordine di convergenza 1;

il metodo diEulero implicito, avendo ordine di consistenza 1, `e convergente con ordine di convergenza 1;

Regione di assoluta stabilit`

a

Nell’ambito delle equazioni differenziali ordinarie, esistono vari

criteri di stabilit´

a. Un classico problema `

e quello di vedere se un

metodo `

e

assolutamente stabile

(spesso A-stabile).

Definito il problema di Cauchy



y

0

(x ) = λy (x ), x ≥ 0

y (0) = 1

(23)

per un certo λ ∈ C con <(λ) < 0, visto che l’unica soluzione `e

y (x ) = exp (λx ) si cerca di definire il passo h cosicch`

e il metodo

numerico per la soluzione del problema di Cauchy (1) abbia lo

stesso comportamento asintotico di exp (λx ).

La

regione di assoluta stabilit`

a

`

e composta dagli hλ, per cui il

metodo numerico con passo h `

e tale da avere lo stesso

A-stabilit`

a. Una nota.

Nota. (Dahlquist, 1979)

Regione di assoluta stabilit`

a

Nota.

Stabilire la stabilit`a per il problema di Cauchy 

y0(x ) = f (x , y (x )), x ≥ 0 y (x0) = y0

(24) `e in generale complicato. Se invece consideriamo



y0(x ) = λy (x ) + g (x ), x ≥ 0 y (0) = y0

(25) la questione `e pi`u semplice.

Ricordiamo che la soluzione di (25) `e y (x ) = y0· exp (λx) +

Z x

0

Regione di assoluta stabilit`

a

Sia y la soluzione di  y0(x ) = λy (x ) + g (x ), x ≥ 0 y (0) = y0 (26) e yquella di  y0(x ) = λy (x ) + g (x ), x ≥ 0 y (0) = y0+  (27) Posto z= y− y , da (26), (27),  z0(x ) = λz(x ), x ≥ 0 z(0) =  (28) la cui soluzione `e z=  · exp (λx ).

Di solito nelle applicazioni ci si interessa al caso λ < 0 o complesso con parte reale negativa. In questi casi z→ 0 per n → ∞ e quindi l’effetto delle perturbazioni si annulla per valori grandi di x .

Regione di assoluta stabilit`

a

Nota.

Ricordiamo a tal proposito che dalla formula di Eulero, se

z = a + ib = <(z) + i =(z) allora

exp (z) = exp (a) · (cos (b) + i sin (b)).

Quindi, visto che per qualsiasi b si ha che |cos(b) + i sin(b)| = 1,

se <(λ) < 0

| exp (λx)

| = |exp(<(λx))(cos (=(λx)) + i sin (=(λx)))|

=

|exp(<(λx))|| cos (=(λx)) + i sin (=(λx))|

Problema stiff

Definizione (Problema stiff (Curtiss-Hirschfelder, 1952))

Un problema di Cauchy



y

0

(x ) = λy (x ), x ≥ 0

y (0) = 1.

(29)

Regione di assoluta stabilit`

a: Eulero esplicito

Nel caso del metodo di Eulero esplicito,

u

n

= u

n−1

+ hf (x

n−1

, u

n−1

) = (1 + hλ)u

n−1

, u

0

= 1.

Visto che

u

n

= (1+hλ)u

n−1

= (1+hλ)

2

u

n−2

= . . . = (1+hλ)

n

u

0

= (1+hλ)

n

,

necessariamente

u

n

= (1 + hλ)

n

e quindi

u

n

→ 0 se e solo se |1 + hλ| < 1

Regione di assoluta stabilit`

a: Eulero esplicito

Di conseguenza,

fissato λ,

il metodo risulta stabile se e solo se si sceglie un

passo sufficientemente piccolo

;

se λ ∈ R

−

, allora bisogner´

a scegliere un passo minore di

h

∗

= 2/|λ|.

Regione di assoluta stabilit`

a: Eulero esplicito

−4 −3 −2 −1 0 1 2 −3 −2 −1 0 1 2

Figura:In magenta: regione di assoluta stabilit`a di Eulero esplicito: disco

Regione di assoluta stabilit`

a: Eulero implicito

Nel caso del metodo di Eulero implicito,

u

n

= u

n−1

+ hf (x

n

, u

n

) = u

n−1

+ hλu

n

, u

0

= 1.

Portando a primo membro hλu

n

, dividendo i membri per 1 − hλ

Regione di assoluta stabilit`

a: Eulero implicito

Essendo <(λ) < 0, si vede facilmente che |

_1−hλ1

| < 1 per qualsiasi

h. Infatti, hλ = a + ib con a < 0, ci`

o `

e vero se e solo se

1

|1 − hλ|

< 1 ⇔ 1 < |1 − hλ| =

q

(1 − a)

2

_{+ b}

2

ovvero, elevando ai quadrati entrambi i membri, se e solo se

1 < (1 − a)

2

+ b

2

ovviamente verificata in quanto a < 0, a, b ∈ R. La regione di ass.

stabilit`

a `

e tutto il

semipiano negativo

<(hλ) < 0.

Nota.

Regione di assoluta stabilit`

a: Eulero implicito

−6 −5 −4 −3 −2 −1 0 1 −6 −4 −2 0 2 4 6

Figura:In magenta: regione di assoluta stabilit`a di Eulero implicito,

Regione di assoluta stabilit`

a: Crank-Nicolson

Regione di assoluta stabilit`

a: Crank-Nicolson

Posto C = 2+hλ_2−hλ, essendo un= Cun−1, otteniamo come in precedenza un= Cun−1= C2un−2= . . . = Cnu0= Cn e quindi un=  2 + hλ 2 − hλ n da cui un→ 0 se e solo se |2 + hλ| |2 − hλ|< 1.

Da <(λ) < 0, |2+hλ_2−hλ| < 1 per h > 0. Infatti, se hλ = a + ib, a < 0 |2 + hλ| |2 − hλ| = |2 + (a + ib)| |2 − (a + ib)| = |(2 + a) + ib| |(2 − a) + ib| = p(2 + a)2_{+ b}2 p(2 − a)2_{+ b}2 < 1 in quanto (2 + a)2< (2 − a)2, qualora a < 0.

Ne segue che la regione di assoluta stabilit`a `e tutto ilsemipiano negativo

Regione di assoluta stabilit`

a di Crank-Nicolson

−6 −5 −4 −3 −2 −1 0 1 −6 −4 −2 0 2 4 6

Figura:In magenta: regione di assoluta stabilit`a di Crank-Nicolson,

A-stabilit´

a e Barriere LMM

Definizione

Un metodo numerico `

e detto A-stabile se la sua regione di stabilit`

a

assoluta contiene tutto il semipiano negativo.

Valgono le seguenti

barriere di stabilit`

a

(Dahlquist, 1963)

Teorema

Nessun metodo LMM esplicito `

e A-stabile.

Teorema

Runge-Kutta

Sia h = (xfin − x0)/Nh, xn= x0+ nh, n = 0, . . . , Nh, e supponiamo che y sufficientemente regolare sia la soluzione del problema di Cauchy (1) nell’intervallo [x0, xfin], ed f continua e L-lipschitziana rispetto la seconda variabile.

Consideriamo un metodo numerico, che diremo diRunge-Kutta, che definisca una sequenza un tale che

y (xn+1) ≈ un+1= un+ hF (xn, un; h) con

Runge-Kutta 2

Teorema

Affinch´e il metodo di Runge-Kutta sia del second’ordine, necessita che

γ1+ γ2= 1, γ2α = 1/2, γ2β = 1/2.

Dimostrazione. (Facoltativa)

Per ottenere questo risultato usiamo la formula di Taylor bivariata, ovvero se g : Ω ⊂ R2→ R `e di classe C2_{, Ω}

aperto contenente (x0, y0), (x0+ h, y0+ k),

g (x0+ h, y0+ k) = g (x0, y0) + gx0(x0, y0)h + gy0(x0, y0)k + O(h2+ k2).

Runge-Kutta 2

Facilmente, dalla formula di Taylor, se y `e sufficientemente regolare,

yn+1 = yn+ hy(1)(xn) + (h2/2)y(2)(xn) + O(h3)

= yn+ hf (xn, yn) + (h2/2)(fx0(xn, yn) + fy0(xn, yn)f (xn, yn)) + O(h3)

Quindi affinch`e yn+1− un+1= O(h3), per confronto con

Runge-Kutta 2

Vediamo alcuni metodi in cui

γ

1

+ γ

2

= 1, γ

2

α = 1/2, γ

2

β = 1/2.

Metodo di

Heun

(α = 1), (scoperto nel 1900):

u

n+1

= u

n

+

h

2

(f (x

n

, u

n

) + f (x

n

+ h, u

n

+ hf (x

n

, u

n

))).

Metodo di

Eulero modificato

(α = 1/2):

u

n+1

= u

n

+ hf (x

n

+

h

2

, u

n

+

h

Runge-Kutta 4 (facoltativo)

La scelta particolare di un maggior numero di vincoli permette, con

qualche fatica, di calcolare un metodo di ordine 4 (scoperto da

Kutta nel 1901). Posto

u

n+1

= u

n

+ h ·

f

1

+ 2f

2

+ 2f

3

+ f

4

6

ove

f

1

=

f (x

n

, u

n

)

f

2

=

f (x

n

+

h

2

, u

n

+

h · f

1

2

)

f

3

=

f (x

n

+

h

2

, u

n

+

h

2

f

2

)

f

4

=

f (x

n

+ h, u

n

+ h · f

3

)

(31)

Parte facoltativa

Convergenza Eulero esplicito, caso Lipschitziano

Di seguito intendiamo mostrare, sotto opportune ipotesi e senza usare i teoremi precedenti, laconvergenza del metodo di Eulero esplicito.

Consideriamo il metodo di Eulero esplicito, con xn= x0+ nh per un prefissato passo h = (xfin − x0)/N. Sia y ∈ C2([x0, xfin]) soluzione di (1), e

un= y (xn−1) + h · f (xn−1, y (xn−1)), un= un−1+ h · f (xn−1, un−1).

Osserviamo che

la prima sequenza u(h)= {un}, ha il generico unottenuto applicando il metodo di Eulero esplicito partendo dal valore assunto dalla soluzione y in ogni xn−1,

la seconda sequenza u(h)_{= {u}

Convergenza Eulero esplicito, caso Lipschitziano

Sketch della dimostrazione: Basta mostrare che

1 |en| ≤ (1 + (1 + hL) + . . . + (1 + hL)n−1)hτ (h) + (1 + hL)n|e0|; 2 (1 + hL)n≤ exp(L(xfin− x0));

3 1 + (1 + hL) + . . . + (1 + hL)n−1≤ exp(L(xfin−x0))

hL .

Infatti ne consegue che |en| ≤

exp(L(xfin− x0))

L τ (h) + exp(L(xfin− x0))|e0|. Da y ∈ C2_([x

0, xfin]), posto M := maxx ∈[x0,xfin]|y

00

(x )| ∈ (0, +∞), per quanto visto sulla consistenza di Eulero Esplicito in (21)

τ (h) = max

n |τn(h)| ≤ Mh/2.

Convergenza Eulero esplicito, caso Lipschitziano

Punto 1. Sef `e L-Lipschitziana (rispetto al secondo argomento) allora

|f (x, y1) − f (x , y2)| ≤ L|y1− y2|. Mostriamo per prima cosa che da en:= y (xn) − un,

|un− un| ≤ (1 + hL)|en−1|.

Infatti da

un=y (xn−1)+ h · f (xn−1,y (xn−1)), un= un−1+ h · f (xn−1, un−1) ricaviamo dalla L-lipschitzianit`a

|un− un| = |(y (xn−1) + h · f (xn−1, y (xn−1))) − (un−1+ h · f (xn−1, un−1))| = |(y (xn−1) − un−1) + h · (f (xn−1, y (xn−1)) − f (xn−1, un−1))| ≤ |y (xn−1) − un−1| + h|f (xn−1, y (xn−1)) − f (xn−1, un−1))| ≤ |y (xn−1) − un−1| + hL|y (xn−1) − un−1|

Convergenza Eulero esplicito, caso Lipschitziano

Da en:= y (xn) − un= (y (xn) − un) + (un− un), |y (xn) − un| = h|τn(h)| ≤ hτ (h), |un− un| ≤ (1 + hL)|en−1| si deduce

Convergenza Eulero esplicito, caso Lipschitziano

Punto 2. Notiamo che per γ > 0

1 + γ = 1 X k=0 γk k! ≤ ∞ X k=0 γk k! = exp (γ) (33)

e quindi (1 + γ)n_{≤ (exp(γ))}n_{= exp(nγ) implica che per γ = hL, essendo} nh = xn− x0,

(1 + hL)n≤ exp (nhL) = exp (L(xn− x0)) ≤ exp (L(xfin− x0)).

Punto 3. Ricordando che

1 + s + . . . + sk=(1 − s k+1

) (1 − s)

posto s =1 + hLdeduciamo che

1 + (1 + hL) + . . . + (1 + hL)n−1=1 − (1 + hL) n

1 − (1 + hL) =

(1 + hL)n− 1

Convergenza Eulero esplicito, caso Lipschitziano

Da 1 + (1 + hL) + . . . + (1 + hL)n−1= 1−(1+hL)_1−(1+hL)n =(1+hL)_hLn−1 (1 + hL)n_{≤ exp (L(x} fin− x0)), concludiamo che 1 + (1 + hL) + . . . + (1 + hL)n−1 = (1 + hL) n_{− 1} hL ≤ exp (L(xfin− x0)) − 1 hL ≤ exp (L(xfin− x0)) hL . (34)

Quindi, per quanto detto in precedenza, il metodo di Eulero esplicito `e

Convergenza Eulero implicito, caso Lipschitziano

Sia h = (xfin − x0)/Nh, xn= x0+ nh, n = 0, . . . , Nh, e supponiamo che y sia la soluzione del problema di Cauchy (1) nell’intervallo [x0, xfin], ed f continua e L-lipschitziana rispetto la seconda variabile, con L > 0.

Consideriamo il metodo di Eulero implicito

un= un−1+ hf (tn, un), u0= y0

con un che si desidera approssimi yn:= y (xn). Di seguito richiederemo y ∈ C2([x0, xfin]).

Dalla definizione di errore locale di troncamento, posto ¯

un= yn−1+ hf (tn, yn) abbiamo

yn− ¯un= hτn(h)

con τn(h) = −hy00(ξn)/2, ξn∈ [x0, xfin]. Di conseguenza, visto che il teorema di Weierstrass esiste M finito tale che M = maxx ∈[x0,x_fin]|y

Convergenza Eulero implicito, caso Lipschitziano

Per prima cosa notiamo che per la disuguaglianza triangolare, posto en:= yn− un

|en| = |yn− un| = |(yn− un) + (un− un)| ≤ |yn− un| + |un− un|

≤ h|τn(h)| + |un− un| ≤ hτ (h) + |un− un|. (35)

Dalla lipschitzianit`a (rispetto la seconda variabile)

|un− un| = |yn−1+ hf (tn, yn) − un−1− hf (tn, un)| = |yn−1− un−1+ hf (tn, yn) − hf (tn, un)| ≤ |yn−1− un−1| + h|f (tn, yn) − f (tn, un)|

≤ |yn−1− un−1| + hL|yn− un| = |en−1| + hL|en|. (36) Quindi, per h < h∗= 1/L abbiamo 0 < 1 − hL < 1 e quindi posto

γ := 1/(1 − hL) > 1, da (35), portando hL|en| a primo membro e dividendo ambo i membri per 1 − hL, ricaviamo con facili conti

Convergenza Eulero implicito, caso Lipschitziano

Di conseguenza, da |en| ≤ γhτ (h) + γ|en−1| si ha |en| ≤ γhτ (h) + γ|en−1| ≤ γhτ (h) + γ(γhτ (h) + γ|en−2|) = γhτ (h)(1 + γ) + γ2|en−2| ≤ . . . ≤γhτ (h) n−1 X k=0 γk+ γn|e0|. (37)

Osserviamo che da (1 + x )k_{≤ exp(kx), γ − 1 = hL/(1 − hL) > 0, nh = x} n− x0,

γn = (1 + (γ − 1))n≤ exp(n(γ − 1)) = exp(nhL/(1 − hL))

= exp((xn− x0)L/(1 − hL)) ≤exp((xfin − x0)L/(1 − hL)), (38)

per cui, visto che da 0 < γ − 1

Convergenza Eulero implicito, caso Lipschitziano

Quindi da |en| ≤ γhτ (h)Pn−1_k=0γk+ γn|e0|, γPn−1 k=0γk< 1 hL· exp  (x_fin−x₀)L 1−hL  , γn ≤ exp((xfin − x0)L/(1 − hL)), ricaviamo per n = 0, . . . , Nh |en| ≤ γhτ (h) n−1 X k=0 γk+ γn|e0| < hτ (h) 1 hL· exp  (xfin − x0)L 1 − hL  + exp  (xfin − x0)L 1 − hL  |e0| ≤  τ (h) L + |e0|  exp  (xfin − x0)L 1 − hL  . (40)

Visto che per h → 0, abbiamo che τ (h) → 0 e e0→ 0, e che l’ultimo membro di (40) non dipende da n, deduciamo per il teorema del confronto che

lim

Facoltativo: Analisi convergenza Eulero esplicito, caso

dissipativo

Se f non `

e L-Lipschitziana ma `

e

L-dissipativa

, cio`

e

−L ≤

∂f

∂y

(ξ) ≤ 0, ξ ∈ Ω := (x

0

, x

fin

) × R

abbiamo da

u

n

= y (x

n−1

) + h · f (x

n−1

, y (x

n−1

)),

u

n

= u

n−1

+ h · f (x

n−1

, u

n−1

),

f (x

n−1

, u

n−1

) = f (x

n−1

, y (x

n−1

)) +

∂f_∂y

(ξ)(u

n−1

− y (x

n−1

)),

che per qualche ξ ∈ (x

n−1

, x

n

) × R ⊆ Ω

Facoltativo: Analisi convergenza Eulero esplicito, caso

dissipativo

Da

u

n

− u

n

= (1 + h

∂f

∂y

(ξ)) · (u

n−1

− y (x

n−1

)).

(41)

abbiamo che se 0 < h ≤ 2/L (non restrittivo per mostrare la conv.

visto che si studia il comportamento per h → 0) allora da

Facoltativo: Analisi convergenza Eulero esplicito, caso

dissipativo

Da

e

n

:= y (x

n

) − u

n

,

|y (x

_n

) − u

n

| ≤ hτ (h),

|u

n

− u

n

| ≤ |e

n−1

|,

|e

n

| ≤ hτ (h) + |u

n

− u

n

| ≤ hτ (h) + |e

n−1

|

ricaviamo, essendo hτ (h) > 0, e

0

= 0, n ≤ N, Nh = xfin − x

0

Predictor-corrector

In generale un metodo LMM implicito ha propriet`

a di stabilit`

a

migliori rispetto ad un LMM esplicito e questo ne suggerisce

l’utilizzo.

Purtroppo ad ogni iterazione bisogna risolvere una equazione

nonlineare.

Un approccio comunemente utilizzato `

e quello del

predictor-corrector

. Consiste nell’utilizzare il metodo di punto fisso

con una certa scelta del punto iniziale.

Esempio Predictor-corrector

Consideriamo i seguenti metodi di Adams (porremo f

i

= f (x

i

, u

i

)).

Bibliografia

K. Atkinson e W. Han, Elementary Numerical Analysis, Wiley, (2004).

K.E. Atkinson, W. Han, D.E. Steward Numerical Solution of Ordinary Differential Equations, Wiley, (2009). V. Comincioli, Analisi Numerica, metodi modelli applicazioni, Mc Graw-Hill, 1990.

G. Dahlquist, Convergence and stability in the numerical integration of ordinary differential equations, Math. Scand. 4 (1956), pp.33-53.

W. Gautschi, Numerical Analysis, Birkha¨user, second edition, 2012. A. Quarteroni, F. Saleri, Introduzione al Calcolo Scientifico, Springer, (2002). A. Quarteroni, R. Sacco, F. Saleri, Matematica Numerica, Springer, (1998). J. Stoer, R.Bulirsch Introduzione all’analisi numerica, Zanichelli, (1975).