Stabilité des schémas auxdifférences finies et analyse

de von Neumann

I- Schémas d’Euler explicite/implicite pour l’équation de la chaleur, étude de stabilité en

!

(µ > 0)

!

"

!

u0 à support compact " [#R,R], L >> R

Numériquement, on discrétise :

Grille de calcul :

Exemple 1 : schéma d’Euler explicite!

un(x j ) " u(x j ,n #t)

Le schéma d’Euler explicite est consistant, d’ordre 1 en t et d’ordre 2 en x :

!

Solution exacte de l'équation de la chaleur,

restreinte à la grille de pas d'espace "x et pas de temps "t :

u(j"x,n"t) = u n (j"x)

!

En x = x j = j"x, t = n"t, on obtient avec un

développement de Taylor :

!

u n +1(x) " u

n(x)

#t=

u(x,(n +1)#t) " u(x,n#t)

#t

=$u

$t(x,n#t) + O(#t)

!

u n(x + "x) # 2u

n(x) + u

n(x #"x)

"x2

=u (x + "x,n"t) + u(x #"x,n"t) # 2u(x,n"t)

"x2

=1

"x2 ( "x

2 $2u

$x2(x,n"t) + O("x

4) ) =

$ 2u

$x2(x,n"t) + O("x

2)

!

u n +1

(x) " u n(x)

#t"µ

u n(x + #x) " 2u

n(x) + u

n(x "#x)

#x2

=$u

$t(x,n#t) "µ

$ 2u

$x2

(x,n#t) + O(#t + #x2)

= O(#t + #x2)

("erreur de troncature", ou "erreur de consistance")

→ schéma consistant, d’ordre 1 en t et d’ordre 2 en x

Ecriture matricielle du schéma :

!

un(x j ) " u(x j ,n #t)

Exemple 2 : schéma d’Euler implicite (ordre 1 en t, ordre 2 en x)

Le schéma d’Euler implicite est consistant, d’ordre 1 en t et d’ordre 2 en x

!

On note la solution exacte de l'équation de la chaleur

u(j"x,n"t) = u n (j"x)

!

u n +1(x + "x) # 2u

n +1(x) + u

n +1(x #"x)

"x2

=$ 2u

$x2[x,(n +1)"t]+ O("x

2) =

$ 2u

$x2(x,n"t) + O("x

2+ "t)

!

u n +1(x) " u

n(x)

#t"µ

u n +1(x + #x) " 2u

n +1(x) + u

n +1(x "#x)

#x2

=$u

$t(x,n#t) "µ

$ 2u

$x2(x,n#t) + O(#t + #x

2)

= O(#t + #x2)

→ schéma consistant, d’ordre 1 en t et d’ordre 2 en x

Ecriture matricielle du schéma d’Euler implicite :

!

" = µ#t

#x 2 coef. CFL, V

n = un(x j )( )

$N +1% j%N$1

Un système linéaire à résoudre à chaque pas de temps,toujours même matrice A

Exemples de méthodes numériques :LU ou Cholesky cas tridiagonal, complexité O(N)

CFL=0.49, T=1

CFL=0.51, T=1

CFL=2, T=1

CFL=0.51, T=0.5

!

"x = 0.1

Explicite

Explicite Explicite

Implicite

!

||Vn||"# c ||V

0||" $n /0 # n%t # T

!

Définition de la stabilité (l") du schéma : #c > 0 tel que

pour tous $t,$x assez petits :!

" = µ#t /#x 2 est fixé, #t$ 0, #x$ 0

Euler explicite stable sous condition CFL : β ≤ 1/2

Euler implicite inconditionnellement stable

Lemme

Remarque : la taille des vecteurs et matrices tend versl’infini quand Δx→0

!

Schéma explicite : Vn +1= M(")V n

!

Si " #1/2 alors M$

= Maxi

|mij |

j

% =1

& Vn

$# M

$

nV

0

$= V

0

$& schéma stable!

Vn

"# Mn

"V

0

"

$ il faut borner Mn

"indépendamment de %t,%x pour

& = µ%t/%x2 fixé et 0 # n %t # T

(matrice M positive)

!

Schéma explicite : Vn +1= M(")V n

!

Si " >1/2 :

!

Valeurs propres de B " M2N#1(IR) : 4[sin(qk /2)]2, qk = k$ /(2N), k =1K2N #1

Vecteurs propres % k = sin(qki)[ ]i=1K2N#1

!

Valeurs propres de M " M2N#1(IR) : $k =1- 4%[sin(qk /2)]2

!

"2N#1 =1# 4$ +O(%x 2) = #(4$ #1) +O(%t), 4$ #1>1

& si n0 = E(T /%t)'( alors :

Mn0) 2N#1

(

) 2N#1

(

=| "2N#1 |n0 = (4$ -1)n 0 exp[n0 *O(%t)] '( Schémainstable

!

Schéma implicite : Vn +1= A(")#1

Vn

!

A(") à diagonale strictement dominante :

# = Mini

aii $ aijj% i

&'

( ) )

*

+ , , =1 > 0

- A$1

./ #$1

=1

- A$n

./1

- Vn

.= A

$nV

0

./ V

0

. schéma stable

!

En || ||" :

!

" = µ#t /#x 2 est fixé, #t$ 0, #x$ 0

Euler explicite stable sous condition CFL : β ≤ 1/2

Euler implicite inconditionnellement stable

analyse de von Neumann

(complémentaire à la notion d’équation équivalente introduite précédemment)

Bilan :

La preuve utilise des propriétés assez fortes desmatrices du schéma (positivité, valeurs propres explicites,dominance diagonale stricte)

→ besoin d’un outil plus général :

II- Méthode de von Neumann :

II-1 Idée générale :

Basée sur l’analyse de Fourier (EDP à coefs constants)

Stabilité

Néglige les conditions aux bord du domaine, où u ≈ 0

!

L2

Passage des grands vecteurs ( taille O(N) ) à des fonctions de x:

!

Vn

Exemple : équation de la chaleur, Euler explicite

!

On calcule ensuite un en utilisant la transformée de Fourier / x,

et on étudie si reste borné

(applicationlinéaire continue)

II-2 Reformulation explicite d’un schéma différences finies par transformée de Fourier, matrice d’amplification

!

un (x) = approximation numérique de u(x,n"t) solution d'une EDP d'évolution

x # IRd, un # [L2(IRd )]p vecteur à p composantes

Schéma différences finies discrétisant l'EDP :

Aj

| j|$q

% ("t,"x)un+1(x + j"x) = Bj

| j|$q

% ("t,"x)un (x + j"x)

j = (j1,K jd ), jk entiers naturels, | j |= j&

Aj,Bj # Mp (IR)

!

Exemple : équation de transport

schéma implicite centré : un+1(x) +c"t

2"x(un+1(x + "x) # un+1(x #"x)) = u

n (x)

transformée de Fourier :

!

Equation définissant le schéma :

Aj

| j|"q

# ($t,$x)un+1(x + j$x) = Bj

| j|"q

# ($t,$x)un (x + j$x)

!

[F(u)](") = ˆ u (")= exp(#i2$" x) u(x) dx1Kdxd

IRd

%

",x & IRd, " x = "1 x1 +L+ "d

xd

!

Prenons la transformée de Fourier de l'équation précédente :

Aj

| j|"q

# ($t,$x)exp(i2%& j$x)'

( ) )

*

+ , , ˆ u

n +1(&) = Bj

| j|"q

# ($t,$x)exp(i2%& j$x)'

( ) )

*

+ , , ˆ u

n (&)

!

Mp ( )

!

H1("t,"x,2#$)%

!

H2("t,"x,2#$)%

!

Mp ( )

Hypothèse :

!

H1("t,"x,k) inversible #k $ IRd

!

" ˆ u n +1

(#) = H1($t,$x,2%#)

&1H

2($t,$x,2%#) ˆ u

n(#)

!

G("t,"x,2#$)%

!

Mp ( )

Matrice d’amplification (ou symbole) du schéma

!

un +1 = F

"1G(#t,#x,2$%) ˆ u

n(%)[ ] = C(#t,#x) u

n

Reformulation « explicite » du schéma :

!

Soit G : IRd" une fonction continue et bornée et

!

Mp ( )!

un +1 = F

"1G(#t,#x,2$%) ˆ u

n(%)[ ] = C(#t,#x) u

n

!

C("t,"x) : [L2(IRd )]p# [L2(IRd )]p opérateur linéaire continu ?

Lemme :

!

P u = F"1

G(2#$) ˆ u [ ]

!

P : [L2(IRd )]p" [L2(IRd )]p un opérateur linéaire défini par

!

Alors P est continu et P = Supk"IRd

G(k)2

Hypothèse :

!

| det(H1("t,"x,k)) |# $ > 0 %k & IRd

!

" G(#t,#x,.) vérifie les hyp. du lemme et C(#t,#x) est continu

II-3 Définition générale de la stabilité d’un schéma

!

Schéma différences finies discrétisant une EDP d'évolution pour t " [0,T] :

un+1

= C(#t,#x)un, u0 condition initiale

un" X espace de fonctions de x, espace de Banach (ex. X = L

2(IR), X = L$(IR))

un (x) = approximation numérique de u(x,n#t) solution de l'EDP d'évolution,

u(.,0) = u0

C(#t,#x) : X % X application linéaire continue

0 & n#t & T

!

Pas de temps et d'espace admissibles : ("t,"x)# $

Trois définitions possibles de $ :

* $ =]0,%[&]0,%[

* 0 < "t ' c"x( (c,( > 0)

* 0 < "t = c"x( (c,( > 0)

!

Schéma (S) : un+1

= C("t,"x)un,

u0 condition initiale donnée# u

n= C("t,"x)

nu

0

!

Le schéma (S) est stable dans X si "KT > 0 tel que :

#($t,$x)% & dans un voisinage assez petit de (0,0),

#n vérifiant 0 ' n$t ' T,

C($t,$x)n 'KT

Rappel : C($t,$x)n = Supu

X=1

C($t,$x)n uX

(norme d'application linéaire continue)

Définition :

!

Remarque : si C("t,"x) #1 alors le schéma (S) est stable dans X

car C("t,"x)n # C("t,"x)n

#1

Exemples : Ex 1: Schéma décentré amont pour l’équation de transport :

C>0

!

un+1

= C("t,"x)un

[C("t,"x)un](x) = (1#$)u

n(x) +$ un (x #"x)

Pour $ = c"t /"x %]0,1], on a dans X = Lp(IR) :

C("t,"x)uX& (1#$) u

X+$ u(.#"x)

X= u

X

' C("t,"x) &1' schéma stable dans X = Lp(IR)

Ex 2: Schéma d’Euler explicitepour l’équation de diffusion :

!

Pour " = µ#t /#x 2 $]0,1/2], on a dans X = Lp (IR) :

C(#t,#x)uX% (1& 2") u

X+ " u(.+ #x)

X+ " u(.&#x)

X= u

X

' C(#t,#x) %1' schéma stable dans X = Lp (IR)

!

Lp(IR)

!

G("t,"x,.) : IRd# fonction continue et bornée

!

Mp ( )

!

un +1 = F

"1G(#t,#x,2$%) ˆ u

n(%)[ ] = C(#t,#x) u

n

!

C("t,"x) : [L2(IRd )]p# [L2(IRd )]p opérateur linéaire continu,

Lemme :

!

" C(#t,#x)n = Supk$IR d

G(#t,#x,k)n2

II-4 Stabilité L2, analyse de von Neumann

(S)

!

Le schéma (S) est stable dans [L2(IRd )]p si et seulement si

"KT > 0 tel que : #($t,$x)% & dans un voisinage assez petit de (0,0),

#n vérifiant 0 ' n$t ' T, #k % IRd, on a :

G($t,$x,k)n 'KT (norme matricielle quelconque)

!

C("t,"x)n

u = F#1

G("t,"x,2$%)n ˆ u [ ]

!

un +1 = F

"1G(#t,#x,2$%) ˆ u

n(%)[ ] = C(#t,#x) u

n

(S)

!

Condition nécessaire pour la stabilité du schéma (S) dans [L2(IRd )]p :

"(#t,#x)$ % dans un voisinage assez petit de (0,0),

Supk$IRd

& G(#t,#x,k)[ ] '1+O(#t) (v.N.)

De plus, si G normale (GG* = G*G), alors cette condition est suffisante.

C'est le cas en particulier lorsque p =1.

Théorème de stabilité (von Neumann)

Rappels :

!

"(G) = rayon spectral de G (plus grand module des valeurs propres de G)

!

G*

= G T

!

(Gn )n"0 bornée si et seulement si #(G) <1 **OU **

#(G) =1 et les valeurs propres de G de module 1 sont semi- simples

Demo du Thm :

v.N. condition nécessaire :

!

["(G)]n = "(Gn ) # Gn

2 qui est borné par hypothèse

$ exp[n ln("(G))] est borné

exp[n ln("(G))] = exp[n%tln("(G))

%t] avec n%t & [0,T]

$ln("(G))

%t# C

$ "(G) # exp(C%t) =1+O(%t)

v.N. condition suffisante si matrice G normale :

!

G normale " Gn normale #n $ 0

Gn normale " %(Gn ) = Gn

2

( car matrice normale & diagonalisable dans base orthonormée)

" Gn

2= %(Gn ) = [%(G)]n = exp[n ln(%(G))] ' exp[T

ln(%(G))

(t]

%(G) '1+O((t)" Gn

2est borné

Ex 1: Schéma d’Euler explicitepour l’équation de diffusion :

!

L2(IR)

!

Supposons " = µ#t /#x 2 constant

un+1

(x) = (1$ 2")un(x) + " (u

n(x + #x) + un (x $#x))

!

ˆ u n +1

= (1" 2#) ˆ u n

+ # ( ˆ u n exp(i2$%&x) + ˆ u

n exp("i2$%&x))

= [1+ 2#(cos(2$%&x) "1)] ˆ u n

' G(&t,&x,k) =1+ 2#(cos(k&x) "1) =1" 4#(sin(k&x /2))2

!

G("t,"x,k) =1# 4$(sin(k"x /2))2 % [1# 4$,1]

Condition de stabilité de von Neumann : CNS G est scalaire

!

* si 1" 4# < "1, c'est à dire # > 1/2 :

Sup |G |k$IR

= 4# "1 (constante >1)

% condition v.N. non satisfaite % schéma instable dans L2(IR)

!

* si 1" 4# $ "1, c'est à dire # %1/2 :

Sup |G |k&IR

=1 ' condition v.N. satisfaite ' schéma stable dans L2

(v.N.)

Ex 2: Schéma d’Euler implicitepour l’équation de diffusion :

!

(1+ 2")un+1

(x) #" (un+1

(x + $x) + un+1(x #$x)) = un (x)

" = µ$t /$x 2 est constant

!

ˆ u n +1 1+ 2" #"(exp(i2$%&x) + exp(#i2$%&x))[ ] = ˆ u

n

ˆ u n +1 1+ 2"(1# cos(2$%&x))[ ] = ˆ u

n

ˆ u n +1 = G(&t,&x,2$%) ˆ u

n

' G(&t,&x,k) =1

1+ 4"(sin(k&x /2))2

!

Sup |G |k"IR

=1 # condition v.N. satisfaite (CNS ici)# schéma stable dans L2(IR)

stabilité inconditionnelle (i.e. quels que soient les paramètres)

Ex 3 : schéma de Lax-Wendroff pour l’équation de transport

Schéma de Lax-Wendroff

Coefficient d’amplification G :

!

(" = c#t /#x constant)

Si |α|>1 :

Si |α|≤1 :

!

" Schéma instable dans

!

" Schéma de Lax-Wendroff stable danssi |c| Δt / Δx ≤ 1

Après quelques simplifications :

>1