Septembre 2011 Master 2 AMD - Méthodes numériques pour l'astrophysique1 Méthodes numériques pour lastrophysique M2 « Astrophysique et Milieux Dilués »

septembre 2011Master 2 AMD - Méthodes

numériques pour l'astrophysique 1

Méthodes numériques pour l’astrophysique

M2 « Astrophysique et Milieux Dilués »

Hervé Beust

Laboratoire d’Astrophysique de Grenoble




• Techniques de base• Estimateurs et statistique • Modélisation de données• Résolution numérique d’équations différentielles• Equations aux dérivées partielles




• Techniques de base• Résolution numérique d’équations• Intégration numérique• Minimisation de fonctions

• Estimateurs et statistique • Modélisation de données• Résolution numérique d’équations différentielles• Equations aux dérivées partielles



Résolution numérique d’équations

• Problème : résoudre numériquement une équation de type f(x) = 0, en général par une méthode itérative.

• Le problème est très différent suivant que f est une fonction scalaire ou vectorielle.

• En général, les méthodes classiques fonctionnent assez bien pourvu que– On soit sûr qu’il y ait une racine;– On parte du voisinage de la racine.– Ca marche mieux si on encadre la racine entre deux réels a et b et

si la fonction est monotone dans l’intervalle.



Différents cas de figure...

Cas standard Cas plus délicats



Méthode de dichotomie• On prend c=(a+b)/2 et on calcule f(c). Si f(c) est du même

signe que f(a), la racine est entre c et b; sinon entre a et c. On recommence avec le nouvel intervalle. Do while (abs(a-b)>…) c = (a+b)/2 if f(c)*f(a)>0 then a = c else b = c end if end do

• Cette méthode a l’avantage de marcher tout le temps pourvu qu’il y ait une racine. Elle ne nécessite pas le calcul de la dérivée.

• C’est une méthode d’ordre 1 convergence moyennement rapide.



Autres méthodes d’ordre 1• Méthodes de la sécante et de la fausse position

• Ces méthodes convergent en général plus vite que la dichotomie, mais pas toujours…



Méthode de Newton-Raphson

• On part d’un point, on approxime la fonction par sa tangente, on recommence avec la racine trouvée, etc…

f(x+h) ≈ f(x)+h f ’(x)+(h2/2) f ’’(x)+.. xn+1 = xn - f(xn)/f ’(xn)

• Cette méthode ne nécessite pas d’encadrer la racine au préalable, mais juste de partir d’un point. Elle fonctionne dans le complexe.

• C’est une méthode d’ordre 2 très efficace.

• MAIS, il faut être sûr d’être au voisinage de la racine. La méthode peut échouer sinon.



Méthode de Newton-Raphson : Problèmes

• Il faut être sûr d’être au voisinage d’une racine…• Il faut aussi pouvoir calculer la dérivée. Sinon: f’(x) ≈ (f(x+h)-f(x-h)) / 2h



Amélioration : Newton-Raphson quartique

• On peut améliorer la convergence si on sait calculer des dérivées d’ordre supérieur

• Exemple : équation de Képler

M = u - e sin u

31

226

122

13

1212

1

)(''')('')('

)(

)('')('

)(

)('

)(

nn

nnn

n

nn

n

n

n

xx

xfxfxf

xf

xfxf

xf

xf

xf

SUBROUTINE KEPLER0(M,E,U)

IMPLICIT NONE

REAL*8 M, ! Mean anomaly & E, ! Eccentricity & U, ! Eccentric anomaly & F,F1,F2,F3, ! Intermediaires & DELA ! Correction REAL*8, PARAMETER :: EPSI=1d-12 LOGICAL OK INTEGER I

U = M OK = .FALSE. I=0 DO WHILE (.NOT.OK) F = U-E*SIN(U)-M F1 = 1.d0-E*COS(U) F2 = U-M-F F3 = 1.d0-F1 DELA = -F/F1 DELA = -F/(F1+0.5d0*DELA*F2) DELA = -F/(F1+0.5d0*DELA*F2+DELA*DELA*F3/6.d0) U = U+DELA I = I+1 OK = ((ABS(DELA).LT.EPSI).OR.(I.GE.500)) END DO END



En multidimensions …

))((11 nxnn xfJxx

n

0)(

0),,(

..........................

0),,( 11

xf

xxf

xxf

nnn

n

• En dimensions plus que 1, c’est beaucoup plus difficile.

• La seule méthode générale, c’est Newton-Raphson, sans garantie de succès…

• Jxn = Matrice jacobienne en x

)()( , nj

ijix x

x

fJ

n

• A chaque étape il faut résoudre un système linéaire• La convergence est quadratique pouvu qu’on soit au voisinage de la racine…



Intégration numérique

• Problème : calculer numériquement une intégrale de la forme

• w(x) est une fonction de poids• La technique consiste toujours à faire une combinaison linéaire

d’évaluations de la fonction f en un certain nombre de points xi , i=1..n

• Tout repose dans le choix des coefficients i et des points xi.

• Les formules convergent vers l’intégrale lorsque n ∞

b

a

b

axwxxfxwxxf 0)(avecd)()(oud)(

)(d)()(1

i

b

a

n

ii xfxxfxw



Formules à points régulièrement espacés

• Formule des trapèzes :

• Formule de Simpson :

)()(,1)(

,,

1

1

ii

n

xfxfhxw

bxax

22

113212

1 1)()()()()(d)(

nOxfxfxfxfxfhxxf

b

a nn

4

31

134

232

434

332

234

131 1

)()()(

)()()()(d)(

nO

xfxfxf

xfxfxfxfhxxf

b

annn



Quadratures de Gauss – polynômes orthogonaux

• Idée : ne plus imposer que les xi soient régulièrement espacés.

• Choisir les xi et les i de manière à ce que la formule d’approximation soit

exacte pour des polynômes de degré le plus élevé possible.• C’est possible jusqu’à des polynômes de degré 2n-1 : Pour un choix donné de a,

b, w(x), et n il existe une unique jeu de xi et les i telle que l’approximation soit exacte pour toute fonction f polynôme de degré ≤ 2n-1.

• La théorie est liée à celle des polynômes orthogonaux. On définit

• La suite des polynômes Pn lorsque n varie est orthogonale au sens du produit scalaire suivant

n

iin xXP

1

)(

b

axxgxfxwgf d)()()(




• Les Pn obéissent à la récurrence suivante :

• Les xi se calculent comme les racines de Pn et les i vérifient :

)()()(

)(

1)(

111

1

00

001

0

xPPP

PPxP

PP

PxPxxP

PP

PxPxxP

xP

nnn

nnn

nn

nnn

)()(1

11

inin

nni xPxP

PP




(a,b) w(x) Nom des polynômes Récurrence

(-1, 1) 1 Polynômes de Legendre (n+1) Pn+1(x) = (2n+1) xPn(x) - nPn-1(x)

(-1,1) (1-x²)-1/2 Polynômes de Tchébychev Pn+1(x) = 2xPn(x) - Pn-1(x)

(0,+∞) xc e-x Polynômes de Laguerre (n+1) Pn+1(x) = (-x+2n+c+1) xPn(x) -

(n+c) Pn-1(x)

(-∞,+∞) e-x² Polynômes de Hermite Pn+1(x) = 2xPn(x) - 2nPn-1(x)

22 )()1(

2

ini

ixPx

Cas particuliers :

Dans le cas de Gauss-Legendre, on a en outre

Et pour tout intervalle (a,b) on ayy

abbaf

abxxf

b

ad

222d)(

1

1



Exemple résolu : Gauss-LegendreSUBROUTINE GAULEG(X1,X2,X,W,N)

IMPLICIT NONE

INTEGER*4 N,M, ! Ordres & I,J ! Indices REAL*8 X(N), ! Tableau de racines & W(N), ! Tableau de poids & Z, ! Racine & X1,X2,XM,XL, ! Bornes & Z1,P1,P2,P3, ! Intermediaires & PP ! Derivee LOGICAL OK ! Test d'arret REAL*8, PARAMETER :: EPS=3.d-14, & PI=3.14159265358979323846d0

M = (N+1)/2 XM = 0.5d0*(X2+X1) XL = 0.5d0*(X2-X1) ! Conversion d’intervalle DO I = 1,M Z = COS(PI*(I-0.25d0)/(N+0.5d0)) ! Guess initial OK = .FALSE. DO WHILE(.NOT.OK) P1 = 1.0d0 P2 = 0.0d0 DO J = 1,N

P3 = P2 P2 = P1 P1 = ((2.0d0*J-1.0d0)*Z*P2-(J-1.0d0)*P3)/J END DO ! Calcul de Pn(Z) par récurrence PP = N*(Z*P1-P2)/(Z*Z-1.0d0) Z1 = Z Z = Z1-P1/PP ! Newton-Raphson OK = (ABS(Z-Z1).LT.EPS) END DO X(I) = XM-XL*Z X(N+1-I) = XM+XL*Z W(I) = 2.d0*XL/((1.0d0-Z*Z)*PP*PP) W(N+1-I) = W(I) END DO END



Intégration multidimensionnelle

• C’est en général beaucoup plus difficile.

• Technique de base : intégrales emboîtées

• 2 difficultés :– Nombre de points nd – Ca ne marche que si le

domaine à intégrer n’est pas trop compliqué

• Dans les autres cas : Intégration Monte-Carlo

xyyxfb

a

xd

xcdd),(

)(

)(



Intégration Monte-Carlo• On veut intégrer une fonction f sur un domaine W. La moyenne de f

sur W vaut par définition

• On tire au hasard un nombre n de points dans l’ensemble et on approxime la moyenne par

• L’erreur moyenne sur l’intégrale est convergence en n-1/2, lente

• Si W n’est pas calculable directement, on inclut le volume W dans un volume V plus grand, facilement calculable, et on prolonge f par 0 en dehors de W. On intègre ensuite sur V. Mais il faut choisir un volume V proche de W sinon, la convergence est encore plus lente.

WW Vff d1

n

iixf

nf

1

)(1

22

n

ffW



Minimisation de fonctions

• Problème : Trouver numériquement un point minimum (ou maximum) d’une fonction f donnée

• Un minimum peut être local ou global : les méthodes itératives garantissent en général la convergence vers un minimum local.

• Le problème est très différent suivant que la fonction est mono- ou multidimensionnelle

• Il y a deux familles de méthodes : les méthodes avec gradient et celles sans gradient.



Méthodes en dimension 1• On veut minimiser une fonction f d’une variable réelle.

• Avant de converger, il faut encadrer un minimum : trouver 3 points a<b<c, tels que f(b)<f(a) et f(b)<f(c).

• Pour encadrer, on déplace le triplet dans le sens de la descente jusqu’à trouver un encadrement.

• Première méthode simple une fois qu’on a un encadrement: On tire un réel d entre a et c, on évalue f(d), et on cherche un nouvel intervalle d’encadrement… puis on recommence…

• Ca marche toujours, mais ce n’est pas très rapide.



Méthode : interpolation par paraboles inverses

• Idée : près d’un minimum, la fonction s’approxime bien par une parabole.

• Quand on a un encadrement (a,b,c), on calcule la fonction de degré 2 (parabole) qui passe par ces trois points et on en cherche le minimum d. On a

• Le nouvel encadrement est (a,d,b) ou (b,d,c).

• La méthode de Brent combine les deux méthodes précédentes.

)()()()()()(

)()()()()()(

2

1 22

afbfcbcfbfab

afbfcbcfbfabbd



Méthodes multidimensionnelles

• On cherche à minimiser une fonction f(x1,…,xn) = f(x)

• La plupart des méthodes procèdent à des minimisations successives le long de plusieurs directions.

• Minimisation le long d’une direction: étant donné deux vecteurs x et n, trouver le réel qui minimise f(x+n). On utilise une méthode de dimension 1

• A partir de x+n, on recommence à minimiser dans une autre direction n’.

• Problème : En minimisant le long de n’, il ne faut pas détruire la minimisation le long de n. Les directions n et n’ doivent être conjuguées.



Directions conguguées• On se place en un point P

• Le changement de gradient dans un déplacement infinitésimal vaut

• Une fois qu’on a minimisé le long de u, si on recommence le long de v, il faut que le gradient reste perpendiculaire à u.

• Les directions u et v sont alors dites conjuguées.

)(etbavec

2

1)(

2

1)()(

2

ij

,

2

Hessiennematricexx

ff

xxxbPf

xxxx

fx

x

fPfxPf

PjiP

ji

Pji jii

Pi i

A

A

xf

A

00 vufu

A



Méthode de Powell• Idée : faire des minimisations successives le long de directions conjuguées.• Problème : Comment trouver des directions conjuguées en chaque point ?• La méthode de Powell minimise le long de directions qui tendent à être

conjuguées au fil des itérations : On a à chaque instant n directions ui, i=1..n. Au départ, on prend ui=ei (vecteurs de base). On répète ensuite la séquence suivante:

– On part d’une position de départ x0.– On fait n minimisation successives le long des n directions. On appelle x1,… xn les

points trouvés.– On remplace u0 par u1, puis u1 par u2, …, un-1 par un.– On remplace un par xn-x0

– On minimise dans la direction de un à partir de xn et on remplace x0 par le point trouvé.

• La méthode a un défaut : elle tend à produire des directions ui linéairement dépendantes

• Solution : Réinitialiser les directions (ui=ei) toutes les n itérations.• Remarque : Cette méthode est une méthode sans gradient.



Méthodes avec gradient

• Quand on sait calculer le gradient f en tout point…

• Méthode de descente maximale : On part de x, on minimise dans la direction de -f , et on recommence.

• Cette méthode ne donne pas de bons résultats car les directions successives ne sont pas conjuguées.



Méthode de Fletcher-Reeves-Polak-Ribiere

• On part d’un point x0, on fixe une direction u0, et on calcule

• A chaque étape on dispose de• On minimise le long de ui. On appelle xi+1 le nouveau

point trouvé. On calcule

• On calcule ui+1 comme

• On recommence.• Cette méthode garantit que les directions ui sont

conjuguées. Elle est recommandée quand on n’a aucune idée de la matrice Hessienne.

ixiii fgux

et,

00 x

fg

ii

iiiiiii gg

gggugu

11i1 avec

11

ixi fg




• Techniques de base• Estimateurs et statistique

• Propriétés et exemples• Convergence• Recherche d’estimateurs• Estimation par ajustement

• Modélisation de données• Résolution numérique d’équations différentielles• Equations aux dérivées partielles



Estimateurs et statistiques• Une série de mesures doit être considérée comme une séries de réalisations

d’une ou plusieurs variables aléatoires• Le phénomène aléatoire dépend d’un paramètre physique θ que l’on cherche

à estimer.• Un estimateur est une fonction T arbitraire d’un échantillon de données (X1,

…,Xn) censée représenter (estimer) le paramètre inconnu θ• En général, on a plutôt une suite d’estimateurs (Tn) de θ en fonction de la

taille n de l’échantillon• Exemple : On cherche à estimer la moyenne (espérance) d’une variable

aléatoire. Si on fait n tirages successifs, un estimateur de la moyenne est

• On dit que l’estimateur est convergent si pour tout ε>0, on a

• La loi faible des grands nombre montre que Xn est un estimateur convergent de l’espérance.

n

XXX n

n

1

0lim

nn

TP



Propriétés des estimateurs• Si (Tn) est un estimateur convergent du paramètre θ, si φ est une

fonction de IRR dans IRR, continue en θ, alors φ(Tn) est un estimateur convergent de φ(θ).

• Exemple : X suit la loi uniforme sur [0,θ]. Xn est un estimateur convergent de la moyenne = θ/2 Tn=2Xn est un estimateur convergent de θ.

• On pose Y=ln X. On a alors E(Y)=ln θ – 1 (calcul). Doncest un estimateur convergent de ln θ – 1 . Et ensuite

est un autre estimateur convergent de θ• On peut en créer beaucoup d’autres. Comment sélectionner le

meilleur ?

n

iin X

1

1 ln

n

iinn XT

1

1 1lnexp



Propriétés des estimateurs• Variance de Tn : V[Tn] = E[(Tn-E(Tn))2]• Erreur quadratique de Tn par rapport à θ:

EQ(Tn,θ) = E[(Tn-θ)2]• Biais de Tn par rapport à θ : B(Tn,θ) = E[Tn-θ].• Propriété 1 : si EQ(Tn,θ))0 quand n∞, alors l’estimateur

Tn est convergent.• Un estimateur est meilleur qu’un autre si son erreur

quadratique est inférieure.• Avec un estimateur biaisé, E[Tn] ≠ θ (décalage). On préfère

en général des estimateurs sans biais (B(Tn,θ) = 0).• Un estimateur est asymptotiquement sans biais si B(Tn,θ)0

quand n∞.



Exemples

• On reprend X, loi uniforme entre 0 et θ. On a Tn et Tn’, estimateurs de θ.

• E(Tn) = θ B(Tn,θ) = 0; EQ(Tn,θ) = θ2/(3n).• B(Tn’) ~ θ/(2n) ; EQ(Tn’,θ) ~ θ2/n

Tn est meilleur que Tn’ (non biaisé et plus petite erreur quadratique).

• Autre estimateur de θ : Tn″ = max {X1,…,Xn}, convergent et biaisé.

• E(Tn″) = nθ/(n+1) B(Tn″,θ) = -θ/(n+1);

EQ(Tn,θ) = 2θ2/(n+1)(n+2) ~ 2θ2/n2.• On construit alors Tn″′=(n+1)Tn″ /n, non biaisé…

EQ(Tn,θ) = θ2/n(n+2) ~ θ2/n2.C’est le meilleur des 4 (non biaisé et convergence en n2)



Convergence des estimateurs• EQ(T,θ) = E[(T-θ)2]= E[(T-E(T)+E(T)-θ)2]

= E[(T-E(T))2] + (E(T)-θ)2 + 2(E(T)-θ)×E[T-E(T)] = Var(T) + B(T,θ)2

• Conséquence : Si un estimateur est sans biais (même asymptotiquement), et si sa variance tend vers 0, il est convergent.



Estimateurs standards

• On a (X1,...,Xn), un échantillon de loi inconnue.

• Estimateur de l’espérance convergent et non biaiséVar(Xn)=Var(X)/n

• Estimateur de la variance Convergent, mais biaisé (variance empirique)E[Sn

2]=(n-1)/n×Var(X)• Estimateur non biaisé

(variance empirique non biaisée)

n

XX

n

i in

1

21

22

n

n

i in X

n

XS

2

1 nn Sn

nV



Recherche d’estimateurs• Je cherche à estimer un paramètre physique à partir de

statistiques : Comment trouver un bon estimateur ?• Ceci nécessite de faire une hypothèse sur le processus

physique, par exemple une loi de probabilité (modélisation de données)

• Exemple : méthode des moments. Pour k>0 E[Xk] et E[(X-E(X))k] sont les moments de la variable aléatoire X. – Je suppose une loi de probabilité d’une forme particulière,

dépendant de k paramètres k que je cherche à estimer.– Les k premiers moments peuvent s’exprimer en fonction des

k Les paramètres s’expriment en fonction des moments.– Il suffit d’avoir des estimateurs des moments (p.ex la moyenne et

la variance) pour en déduire des estimateurs des paramètres.– Inconvénient de la méthode : les estimateurs qu’on tire sont

souvent peu précis.



Estimation par ajustement• Idée : définir une métrique sur les lois de probabilités, et trouver la loi

de probabilité P qui minimise une « distance » par rapport à la loi empirique Pe.

• Si (x1,…,xn) est un échantillon observé, (c1,…,ck) l’ensemble des valeurs prises par les xi’s, on définit Pe(ci)=n(ci)/n, où n(ci) est le nombre de fois où ci est réalisé (fréquence empirique).

• Distance du χ2 :

• Distance de Kolmogorov-Smirnov = comparaison entre les fonctions de répartition théoriques (F) et empiriques (Fe)

k

i i

ieie cP

cPcPPPD

1

22

)(

))()((),(2

)()(max),(n,,1i

ieieKS cFcFFFD




• Techniques de base• Estimateurs et statistique • Modélisation de données

• Régression linéaire• Modèles linéaires de moindres carrés• Modèles non-linéaires : méthode de Levenberg-Marquardt• Recuit simulé et algorithmes génétiques

• Résolution numérique d’équations différentielles• Equations aux dérivées partielles



Modélisation de données par régression

• On mesure une série de données (x1,y1)… (xn,yn). On cherche à trouver une relation physique y=F(x).

• Dans la pratique on se donne un modèle dépendant d’un nombre k de paramètres α1,…,αk: y=f(α1,…,αk; x).

• On va chercher les paramètres α1,…,αk qui collent au mieux avec les observations (xi,yi) .

• Chaque mesure yi vient avec son erreur standard σi2. Yi=f(α1,…,αk; xi)+Ei , où Ei est

une variable aléatoire de variance σi2.

• On va chercher les paramètres qui minimisent

• Toute la difficulté consiste à 1. Trouver les paramètres réalisant le minimum2. Estimer l’incertitude sur les paramètres.

2

1

12 );,,(

n

i i

iki xfy



Régression linéaire

2

1

2 )(

n

i i

ii baxy

• But : modéliser des données par une relation linéaire y = ax+b• Méthode : Minimiser le χ2

pour trouver a et b

2

12

12

2

12

12

12

12

21

2

2

,,,,,1

avec

02

0)(

2

xxx

n

i i

iixy

n

i i

ixx

n

i i

iy

n

i i

ix

n

i i

xyxyxx

yxxy

yx

xyxxx

n

i i

ii

n

i i

iii

SSSσ

yxS

σ

xS

σ

yS

σ

xS

σS

SSSSb

SSSSa

SbSaS

SbSaS

baxy

b

baxyx

a



Régression linéaire (2)

• Erreur sur a et b : – Var(yi)=σi

2 Variyii2 σi

2 (Somme de variables aléatoires indépendantes)

n

i

xx

i

ixxx

n

i i

xi

n

i i

iixxx

n

i i

ixi

xyxyxx

yxxy

SxSSb

SSSxa

yxSSb

ySSxa

SSSSb

SSSSa

12

21

2

2

12

12

1)(Var

1)(Var

xx

xab

xxxba

SS

SSba

SS

;),(cov;;



Modèles linéaires de moindres carrées

• On cherche un modèle qui dépend linéairement des paramètres

y = f(α1,…,αk; x) = α1X1(x)+∙∙∙+αkXk(x)où les X1,…,Xk sont des fonctions données à l’avance

• On va chercher à minimiser

en disant ∂χ2/∂αi=0 pour i=1…k

• On introduit la matrice A, n×k, et le vecteur b de longueur n tels que

2

1

12)(

n

i i

ij

k

j ji xXy

i

ii

i

ijij

yxX

bA et

)(



Modèles linéaires de moindres carrés

• ∂χ2/∂αj=0 pour j=1…k revient à

…autrement dit résoudre un système linéaire ! (équations normales)

• On appelle fij = [c]-1ij . On a

bAAA

tt

n

l l

lili

n

l l

ljliiji

k

jjij

xXyd

xXxXcdc

detcencore ou

)(et

)()(avec

12

12

1

n

l l

ljlk

j

k

jijjiji

xXyfdc

12

1 1

1 )(

ii

c

n

l l

lpljip

k

j

k

piji f

xXxXff

jp

12

1 1

)()()(Var

ijjiiii ff ,covet



Modèles non linéaires• y = f(α1,…,αk; x) où la dépendance est quelconque.

• Le jeu de paramètres (α1,…,αk) minimisant le χ2 doit être trouvé de manière itérative.

• C’est conceptuellement identique à un problème de minimisation dans un espace de dimension k.

• La non-linéarité ne garantit pas l’existence d’un minimum unique problèmes de minima locaux nécessité de faire de nombreux essais !

• Quand on peut calculer le gradient de la fonction f par rapport aux paramètres, la méthode recommandée est celle de Levenberg-Marquardt.



Méthode de Levenberg-Marquardt• On appelle α le vecteur (α1,…,αk) courant.

• Si le modèle est linéaire, la fonction χ2(α) est une forme quadratique

v est un vecteur et H une matrice k×k

• Dans ce cas on sait où est le minimum : αm = H-1∙v. De manière équivalente, si on part d’un vecteur α0 , on a

• Si la fonction n’est pas trop éloignée d’une forme quadratique, cette formule peut-être une bonne formule d’itération.

• Si la fonction est plus compliquée, on se contentera d’une simple descente de gradient

• Idée de la méthode : Alterner entre les deux formules

• Problème : Il faut la matrice H = matrice Hessienne

Hv 2

12 )(

)( 021

0 Hm

)(cte 02

0 m



Méthode de Levenberg-Marquardt (2)

• Problème : Les termes cjl dépendent des dérivées secondes de f qui ne sont pas forcément accessibles

• Souvent on laisse tomber les termes en question…

jl

n

i lj

iii

l

i

j

i

ilj

j

n

i j

i

i

ii

j

n

i i

ii

cxf

xfyxfxf

dxfxfy

xfy

2);(

);();();(1

2

2);();(

2

);()(

1

2

2

22

1

2

2

1

2

)1(1)(1

021 kjdc jl

k

ljlm

H

)2(cte)(cte 02

jjm d

n

i l

i

j

i

ijl

xfxfc

12

);();(1



Méthode de Levenberg-Marquardt (3)• Deux questions :

1. Comment décider de l’alternance entre les deux formules (1) et (2) ?2. Comment fixer la constante dans la formule (2) ?

• Levenberg-Marquardt : 1. cte ~ 1/cjj . En fait cte = 1/(λcjj) (2) devient λcjjδαj = dj

2. (1) et (2) peuvent se combiner en une seule équation. On définit C’= C + λ×diag(c11,…,ckk) et on remplace (1) et (2) par

3. Quand λ>>1, (3) revient à (2); quand λ<<1, (3) équivaut à (1)

• Recette :1. On part d’un choix initial α, et on calcule χ2(α). On prend un petit λ =0.0012. On résout (3) et on calcule l’incrément . On calcule χ2(α3. Si χ2(αχ2(α), on est loin du minimum on multiplie λ par 10 et

on revient à 2. 4. Si χ2(αχ2(α), on approche On divise λ par 10, on remplace α

par αet on revient à 2.

));1(()3(11

ljcccckjdc jljljjjjjl

k

ljl



Intervalles de confiance des paramètres

• Une fois qu’on a obtenu les paramètres (α1,…,αk) qui minimisent, on souhaite obtenir des intervalles de dispersion (δα1,…,δαk) des paramètres à un niveau de confiance donné.

• La méthode de Levenberg-Marquardt fournit la matrice des covariances F = C-1. Mais celle-ci n’est utilisable que si les erreurs de mesure sont distribuées de manière gaussienne ! Si ce n’est pas le cas, on peut en déduire n’importe quoi !!

• Si les erreurs ne sont pas gaussiennes (ou si on ne sait pas), il faut avoir recours à d’autres méthodes statistiques beaucoup plus robustes…



Avec la matrice des covariances…

• Si les erreurs sont gaussiennes, alors on a avec un degré de confiance de 68% (1σ dans la loi normale).

• Attention : le jeu d’intervalles de confiances δαj, j=1..n ne constitue pas une région de confiance pour les k paramètres conjointement…

jjj f



Méthodes statistiquesou quand les erreurs ne sont pas gaussiennes…

• Simulation de jeu de données Monte-Carlo– Idée : tirer plusieurs (N) jeux de données fictives dans les intervalles de

confiance ±σi (de manière gaussienne…), et effectuer N minimisations.– On observe la distribution des jeux de paramètres α obtenus, on en déduit

des intervalles de confiance.• Méthode Bootstrap

– Au lieu de tirer des jeux de données fictives, on tire au hasard n données (avec éventuelle répétition) parmi les n de base, et on refait une minimisation.

– On répète l’opération N fois, on obtient la distribution des α .• Avantage de ces méthodes : Elles sont simples, robustes et ne

présupposent rien sur la distribution des erreurs de mesure. • Désavantage : Elles sont coûteuses en temps de calcul

(il faut refaire N minimisations).

Méthode MCMC(Monte-Carlo + Chaînes de Markov)

• Idée : ne plus chercher d’intervalle de confiance pour les paramètres, mais échantillonner leur distribution statistique.

• C’est une amélioration de la méthode de simulation de jeu de données.

• On a un vecteur de données y. Pour un jeu de paramètres , on connaît , probabilité d’observer y sachant . On cherche

• Par le théorème de Bayes

• On suppose connaître (prior).

• Une chaîne de Markov = une suite de modèles i, où chaque i+1 se déduit de i via une probabilité de transition . A la fin, la distribution des i échantillonne



d

,

pyp

pyp

yp

pyp

yp

ypyp

yp yp

p

iitrp

1

yp

Méthode MCMC (2)

• Définition : La chaîne de Markov est réversible si

• Théorème : Si la chaîne est réversible, apériodique et irréductible, ell converge vers

• Problème : Il n’est pas facile de trouver une probabilité de transition réversible. On peut en construire une à partir d’une autre qui ne l’est pas, par l’algorithme de Metropolis-Hastings



yp

iitrq

1

iitriiitr pyppyp

111

1,p

pminavec

1i

11i1

111

iitr

iitrii

iiiitriitr

qy

qy

qp

Méthode MCMC (3)• Méthode à chaque pas :

1. Connaissant i, on tire au hasard un i+1 en suivant

2. On calcule 2(i+1) et 2(i).

3. On détermine le rapport

4. On tire un nombre u au hasard entre 0 et 1.

5. On calcule . Si u<, on accepte le pas, sinon on revient à i.

• Souvent, on prend qtr symétrique

dans une direction v. On fait tourner les directions.• On peut prendre qtr non symétrique quand on considère le modèle

uniforme dans des combinaisons de paramètres. Dans ce cas, on multiplie par le rapport des jacobiens.



iitrq 1

1

21

221

i

1i expp

p

iiy

y

ii

1

2

21

21 2exp

2

1

v

ii

v

iitr

vvq

Méthode MCMC (4)

• Test d’arrêt : Statistique de Gelman-Rubin.

• On fait tourner 10—20 chaînes en parallèle. On teste la convergence des variances des différentes chaînes.

• Quand la convergence est acquise (ça peut être long !), on laisse tourner les chaînes plus longtemps en retenant tous les modèles calculés. Ceux-ci échantillonnent la distribution des paramètres.





Problèmes de minima locaux…

• La méthode de Levenberg-Marquardt permet de converger vers jeu de paramètres α qui minimise localement le χ2. Si le modèle est non-linéaire, il peut y avoir d’autres minima Comment savoir si on est dans le bon ?

• Technique 1 : Je recommence N fois la minimisation en partant de points de départ différents– Efficace s’il n’y a pas trop de minima locaux et si la dimension de

l’espace n’est pas trop élevée ( ≤ 5-6)

• Technique 1 bis : Technique 1 + Recuit simulé – Permet de relier des minima locaux voisins

• Technique 2 : Algorithmes génétiques– La seule technique permettant d’explorer correctement un espace des

paramètres de dimension élevée.



Recuit simulé

• A employer comme tel ou (mieux) à combiner avec Levenberg-Marquardt;

• On introduit une fonction « température » T(n) décroissante (souvent linéairement) en fonction du nombre d’itération. La température initiale T0 est élevée.

• A chaque itération, on teste un saut aléatoire de la solution, qui induit une variation de χ2 : Δχ2.– Si Δχ2<0, on applique le saut;– Si Δχ2>0, on l’applique avec la probabilité e-Δχ2/T(n)

• Cette technique peut permettre de sortir d’un minimum local.



Algorithmes génétiques• Au lieu de partir d’un seul point dans l’espace des paramètres et de

minimiser, je prends N points de départ (~100) différents (Génération 0 d’individus).

• Je classe les individus par χ2, et je construis ma génération suivante comme suit :

1. Je garde ceux qui ont les meilleurs χ2 ; 2. J’en construis d’autres en « croisant les caractères » d’individus «

parents » pris dans la génération précédente, en choisissant de préférence des parents ayant de bons χ2

3. J’en construis quelques autres en introduisant des « mutations » sur des individus de la génération précédente.

4. Eventuellement, j’applique quelques pas de minimisation (Levenberg-Marquardt…) sur ma population et j’obtiens ma génération suivante. Puis retour en 1…




• Techniques de base• Estimateurs et statistique • Modélisation de données• Résolution numérique d’équations différentielles

• Méthodes de type Runge-Kutta• Contrôle du pas• Méthode de Bulirsch et Stoer• Equations mal conditionnées (Stiff)• Codes N corps• Conditions au limites en plusieurs points : relaxation

• Equations aux dérivées partielles



Résolution numérique d’équations différentielles

• Un type de problème qui se pose couramment en astrophysique (intégration de systèmes dynamiques, calculs MHD, etc…)

• Deux grands types de problèmes … avec des méthodes d’approche très différentes– Les équations différentielles ordinaires (ODEs)– Les équations aux dérivées partielles (PDEs)

• Dans tous les cas, la nature des conditions aux limites conditionne la résolution.



Equations différentielles ordinaires• C’est résoudre le problème

• Remarques :– y n’est pas nécessairement scalaire. Ce peut être un vecteur système

différentiel– Les équations d’ordre supérieur se ramènent à ce schéma :

– avec une condition aux limites de la forme y(x0)=y0, dy/dx(x0)=y′0 (problème de type conditions initiales)

– Si les conditions aux limites sont de la forme y(xa)=ya et y(xb)=yb, le problème est de nature différente (et la méthode d’approche aussi…)(problème de conditions aux limites en deux points distincts)

00)(avec),(d

dyxyyxf

x

y

),(d

d)

dx

d,(

),,(d

dd

d

)d

d,,(

d

d21

212

21

2

2

YxFx

Yyyyy

yyxfx

y

yx

y

x

yyxf

x

y



Méthodes de type Runge-Kutta

• Pour un problème de type « conditions initiales ».On part de y(x0), on en tire y(x0+h≡x1), puis y(x0+2h≡x2), etc…h est le pas (de temps), supposé petit.Les diverses méthodes sont d’autant plus précises que h est petit.

• La méthode la plus simple : Euler (explicite)

• Méthode d’ordre 1 : yn+1=y(xn+1)+O(h2)peu précise (+asymétrique, peu stable)

• Variante : Euler implicite, plus stable, mais non linéaire

),()(d

d1 nnnnnn yxhfyx

x

yhyy

),( 111 nnnn yxhfyy



Méthodes de type Runge-Kutta (2)• Runge-Kutta d’ordre 2 (ou méthode du point

médian) yn+1=y(xn+1)+O(h3)

• Runge-Kutta d’ordre 4: yn+1=y(xn+1)+O(h5)

• Remarque : Si le système est vectoriel les ki’s sont des vecteurs…

21

121

21

2

1

),(),(

kyykyhxhfk

yxhfk

nn

nn

nn

461

331

231

161

1

34

221

21

3

121

21

2

1

),(

),(

),(

),(

kkkkyy

kyhxhfk

kyhxhfk

kyhxhfk

yxhfk

nn

nn

nn

nn

nn



Contrôle du pas• Comment s’assurer de la qualité de l’intégration ? Comment doit-on adapter le

pas d’intégration au fil du calcul ?

• Première méthode : doublement de pas. On calcule y(x+h) de deux façons.

– En prenant un pas h → y1

– En prenant deux pas h/2 → y2

• En comparant y1 et y2, on teste si l’intégration est bonne. On pose Δ=y2-y1 h5. Si l’erreur qu’on souhaiterait avoir est Δ0, alors il faudrait choisir

• Stratégie :– Si Δ>Δ0, on recommence en diminuant le pas. On prend

– Si Δ<Δ0, on peut augmenter le pas en posant

5/1

0

hh5/1

0

Shh

)9.0(4/1

0

SShh



Contrôle du pas (2)• Que doit valoir Δ0 ? On doit avoir au moins Δ0 |y|, mais il faut se

méfier des situations où y passe par 0. Dans la pratique, on utilise

• Si un pas est bon, quel valeur choisir ? y1 ou y2 ? Une combinaison…

• Deuxième méthode : Fehlberg-Cash-Karp. Au lieu d’utiliser une seule formule de Runge-Kutta et de doubler le pas, on utilise deux formules différentes et on compare les résultats. Dans la pratique, on utilise une formule d’ordre 5 et une d’ordre 4.

x

yhy

x

yhy i

i d

dminou

d

d0

)()()()(

22)(

)()(6

151

26

21516

1151

65

2

651

hOyhOyyhxyhO

hcyhxy

hOhcyhxy



Contrôle du pas (3) : Felhberg-Cash-carp• La formule d’ordre 5 est de la forme

• La formule d’ordre 4 utilise les mêmes coefficients ai et bij, mais des coefficients c′i différents

)()( 516655443322111 hOxykckckckckckcyy nnn

)()(

),(

),(

),(

616655443322111

56546436326216166

12122

1

hOxykckckckckckcyy

kbkbkbkbkbyhaxhfk

kbyhaxhfk

yxhfk

nnn

n

nn

nn

j 1 2 3 4 5

i ai bij ci c′i

1 37/378 2825/27648

2 1/5 1/5 0 0

3 3/10 3/40 9/40 250/621 18575/48384

4 3/5 3/10 -9/10 6/5 125/594 13525/55296

5 1 -11/54 5/2 -70/27 35/27 0 277/14336

6 7/8 1631/55296 175/512 575/13824 44275/110592 253/4096 512/1771 1/4



Contrôle du pas (4) : Felhberg-Cash-carp

• L’estimation de l’erreur se fait au moyen de

• Δh5, donc la correction du pas en fonction de l’erreur se fait de la même façon que pour la méthode de doublement de pas.

• Si le pas est accepté, on prend yn+1 comme valeur (erreur O(h6)).

• Les méthodes de ce type donnent en général de meilleurs résultats que les méthodes de doublement de pas.

6

1

511 )(

iiiinn hkccyy



Méthode de Bulirsch et Stoer

• Une méthode en général plus puissante que Runge-Kutta, mais si la solution est bien régulière…

• Partant de x0 , on va calculer y(x0+H) (H grand). On prend une méthode de Runge-Kutta

– Si on prend n1 pas (h1=H/n1), on obtient une estimation yest(x0+H,H/n1);

– Si on prend maintenant n2 pas (n2>n1), on obtient une nouvelle (meilleure) estimation yest(x0+H,H/n2)

• Idée de Bulirsh-Stoer : Considérer yest(x0+H,h) comme une fonction de h (ou n=H/h) et extrapoler cette fonction à h→0 (ou n→∞).



Méthode du point médian modifiée (ou différences centrées)

• C’est la méthode de Runge-Kutta qu’on utilise pour Bulirsh-Stoer. On veut aller de x0 à x0+H en n pas de h=H/n.

• C’est une méthode d’ordre 2 (moins précise que RK4). Mais avantage pour Bulirsch-Stoer : L’erreur ne contient que des puissances paires de h :

),()(

1-n,1,2,mpour),(2

),(

)(

0121

0

011

0001

00

nnnn

mmm

zHxhfzzyhxy

zmhxhfzz

zxhfzz

xyz

i

iin hcyHxy 2

10 )(



Extrapoler ?• On a des valeurs yest(x0+H,h)≡g(h) pour différentes valeurs de h : h1,

…,hk Comment extrapoler à h=0 ?

• Extrapolation polynômiale : Je calcule l’unique polynôme de degré k-1 (interpolation de Lagrange) qui passe par les k points de mesure

que l’on calcule de la manière suivante, et on évalue en X=0.

k

ik

ijj

ji

k

ijj

j

i

hh

hX

hgXP1

1

1

)(

)(

)()(

mii

miiiimiiimimiii

kkk

kkkkkkk

kkkk

kk

hh

PXhPhXP

PPPP

PPPPPPPPP

PPPPPPPPP

hgPhgPhgP

)()2)(1()1()1()()1(

1234)1(123

)1)(2()1()1)(2(23434231232312

)1(123321221

2211

)()( récurrencela avec

),(

.................

),(,,),(,),(

),(,,),(,),(

)(,),(),(



Extrapoler (2) ?• Extrapolation rationnelle : On utilise des fractions rationnelles au lieu

de polynômes. Les résultats sont en général meilleurs

• On utilise en général la séquence n=2,4,6,8,…,16 (h=H/n) et on s’arrête lorsque la correction est suffisamment petite.

11

récurrencela avec

),,(

...................

),,(,,),,(,),,(

),,(,,),,(,),,(

),,(,,),,(,),,(

)(,),(),(;0

)1()1()()1(

)1()()1(

)1()()1()()1()()1(

1234)1(23)1(123

)1)(2)(3()1)(2()1)(2()1)(2)(3(234534534234123423423123

)1)(2()1(1)1)(2(2343432312323212

)1(*1233*2122*1

2211

miimii

miimii

mi

i

miimiimiimiii

kkkk

kkkkkkkkkkkk

kkkkkkkk

kkkk

kk

RR

RR

hXhX

RRRR

RRRRR

RRRRRRRRRRRR

RRRRRRRRRRRR

RRRRRRRRRRRR

hgRhgRhgRR



Equations mal conditionnées (stiff)• Des situations où les méthodes traditionnelles fonctionnent mal…• Exemple 1 : équation (y′=-cy, y(0)=1) avec c>0 (solution y(x)=e-cx), que je

choisis de résoudre par la méthode d’Euler

qui diverge clairement pour h>2/c (|1-hc|>1) il faut choisir h<2/c sinon on s’éloigne de la solution.

• Exemple 2 : Système différentiel (Y′=-C.Y, Y(0)=Y0), où C est une matrice symétrique définie positive (solution Y(x) = exp(-Cx).Y0)

qui diverge dès qu’une des valeurs propres de (I-hC) sort de [-1..1] , c’est-à-dire qu’on doit avoir h<2/λmax (valeurs propres de C)

• Exemple 3 : (u’=998u+1998v, v’=-999u-1999v, u(0)=1, v(0)=0) Solution (u(x)=2e-x-e-1000x, v(x)=-e-x+e-1000x) il faut h<1/1000 , même si dans la solution, le terme en exp(-1000x) est très vite négligeable

nnnn yhchcyyycyy )1()( 1

nn h YCIYYCY )()( 1



Equations mal conditionnées (stiff)

• Exemple 4 : équation (y″=y,y(0)=1,y′(0)=-1). Solution y(x)=e-x. Les méthodes numériques finissent toutes par diverger, car on introduit des éléments de la solution parasite y(x)=ex…

• Que faire ?– Eviter d’avoir des valeurs propres très différentes

dédimensionnement

– Faire très attention à l’adaptation du pas

– Employer des méthodes implicites



Méthodes implicites

• Exemple 1toujours stable !

• Exemple 2toujours stable aussi !

• De manière générale, les méthodes implicites sont plus stables. Mais– Les équations à résoudre à chaque pas sont souvent non-linéaires

– Il est difficile de définir des schémas implicites d’ordre supérieur Méthodes semi-implicites de Rosenbrock

hc

yyhcyyycyy n

nnnn 1

)( 111

nn h YCIYYCY

11 )()(

),( 11 nnnn yxfyy



Méthodes semi-implicites• On approxime…

• J = matrice jacobienne. On doit résoudre un système linéaire à chaque pas…

• Méthodes de Rosenbrock : généralisation à des schémas d’ordre supérieur

• Les γ, γij, αij, ci et l’entier s (ordre de la méthode) sont des caractéristiques de la méthode

• A chaque pas, il faut inverser s matrices.

• On ajuste le pas en comparant avec une autre formule avec des c′i.

)(

)()(),(1

1

111

nnn

nnnnnnnn

fhh

fhxhf

n

n

yJIyy

yyJyyyyy

y

y

sihhfh

c

i

jjij

i

jjijniij

s

iiinn

nn,,1pour

1

1

1

1

11

kJkykJI

kyy

yy



Codes N corps

• Le problème (gravitationnel) des N corps est un exemple de système différentiel d’ordre 6N qui peut s’intégrer par les méthodes classiques.

• Il y a deux types de difficultés spécifiques à ce problème– Lorsque N est modéré (mécanique céleste) on a souvent

besoin d’intégrer pendant longtemps avec une grande stabilité méthodes symplectiques.

– Lorsque N est grand, la difficulté réside dans le calcul des N(N-1)/2 termes de forces codes autogravitants



Intégration symplectique• La particularité des systèmes N corps est d’être des systèmes

hamiltoniens.

• On considère un système dynamique régi par un Hamiltonien conservatif H(xi,pi) :

• Pour toute quantité q(xi,pi)

• La solution donnant q(t) à partir de q(t-) est

i

i

i

i

x

H

t

p

p

H

t

x

d

d,

d

d

)(d

dqF

x

H

p

q

p

H

x

q

t

q

i iiii

)(2

1)()exp()(22

tq

FFtqFtq



Intégration symplectique (2)• Une intégration numérique, c’est trouver q(t) connaissant q(t-• Les méthodes classiques ne garantissent pas H=cte

(Runge-Kutta, Bulirsh & Stoer …)

• Une méthode symplectique conserve exactementH ou un autre Hamiltonien voisin de H. Du coup, l’erreur faite sur H est bornée



Intégration symplectique (3)• Hypothèses de base de l’intégration symplectique :

H = HA+HB (F = A+B) où on sait intégrer HA et HB (on sait calculer exp(τA) et exp(τB))

• Souvent, on suppose en plus HB<<HA (HB/HA ~ ε <<1)

• On a alors

En intégrant d’abord HA pendant puis HB pendant , on réalise un intégrateur symplectique d’ordre 1 : On résout exactement un Hamiltonien

2exp)exp().exp( OBABA

)(integ OHH



Intégration symplectique (4)• On a aussi

On obtient un intégrateur symplectique d’ordre 2 en intégrant 1) HB pendant pendant pendant Dans ce cas,

• Il y a aussi des méthodes d’ordre 4, 6, 8…

• En fait, compte tenu de HB/HA~ε on a même

On peut intégrer avec un grand pas de temps

3exp2

exp.exp.2

exp OBABAB

2integ OHH

2integ OHH



Intégrateurs symplectiques pour codes N corps

• Exemple le plus simple : la méthode T+U– H=Hamiltonien du problème à N corps = E. cinétique + E. potentielle =

T+U– Variable conjuguées cartésiennes : xi=x,y,z.. pi=mvx,mvy,mvz…– T = T(pi) et U=U(xi) On sait intégrer séparément T et U Méthode symplectique avec HA=T, HB=U. Mais on n’a pas HB<<HA

• Deuxième exemple: la méthode MVS (Mixed Variable Symplectic)– Hypothèse : (mi<<m0 pour tout i = 1,…,n-1) (système planétaire)– HA = Somme des Hamiltoniens Képlériens (on sait intégrer…)– HB = Le reste = Les perturbations mutuelles dépend que des xi’s)

• La condition HB<<HA reste vérifiée si 1) L’objet 1 est beaucoup plus massif que les autres 2) Les distances mutuelles ne sont pas trop petites (pas de rencontres proches)



Les problèmes de rencontres proches• Lorsque deux corps passent proches l’un de l’autre, on a

des perturbations importantes et rapides.• L’idéal est de diminuer le pas de temps dans ce type de

situation.• Mais une intégration symplectique demande que le pas de

temps soit constant (Hinteg=f(τ)) difficulté ! Deux variantes :– On laisse tomber la symplecticité le temps de la rencontre proche

(code RMVS Levison & Duncan)– On modifie le découpage HA+HB le temps de la rencontre proche.

On est toujours symplectique mais le temps de calcul est plus long (code MERCURY Chambers)

– On découpe les potentiels en cercles concentriques avec un pas de temps adapté à chaque tranche (Code SyMBA Duncan, Lee & Levison).



Codes autogravitants• On veut calculer un système N corps avec N grand• La difficulté réside surtout dans le calcul des forces. Les différents types

de codes se différencient par la méthode choisie.• Codes directs (PP): On calcule directement les N(N-1)/2~N2/2 termes de

forces. C’est lent et le temps de calcul est N2. On arrive à simuler quelques 104 particules.

• Codes en arbre : tempe de calcul N×ln N ~108 particules– Les forces proches sont calculées directement– Pour les termes lointains, les objets sont regroupés en groupes cubiques

appelée nœuds.– La contribution des nœuds lointains est développée en harmoniques

sphériques et tronquée.

lointains termes

2

0

directs termes

)()(

k l

l

lmijml

jiji rrUrrUa



Codes autogravitants (2)• Codes particule-maille (PM): On découpe l’espace en J3 cellules cubiques de

côté a, et on suppose que la masse dans chaque cellule est concentrée en son centre. Le potentiel dans la cellule (i,j,k) se calcule comme

C’est une convolution discrète. En passant par l’espace de Fourier, il n’y a qu’à multiplier les transformées de Fourier temps de calcul en J×ln J (~109 cellules)

• Codes particule-particule/particule-malle (P3M) : Les codes PM manquent de résolution pour traiter les forces proches. On divise alors le calcul en deux :

– Les forces lointaines sont calculées par la méthode PM– Les termes proches sont calculées individuellement (PP)– On atteint ~107 particules– Variante : TMP (Tree/Particle Mesh), où la partie PP est calculée avec un code en

arbre. On atteint ~1010 particules !• Codes à grille adaptatives (AP3M) : On crée des sous-grilles plus fines dans la

partie P3M là où la densité de particules est plus grande (Codes MLAPM, ART, RAMSES…)

entadoucissemd' terme//

),,(

),,(),,(2222,,

aakjia

kjiGMU

kjikjikji



Conditions aux limites en plusieurs points

• Cas général : on a un système différentiel de la forme dY/dx = f(x,Y), où Y=(y1,…yn) est un vecteur de dimension n, avec n1 conditions de la forme gi(x1,Y)=0 (à satisfaire en x=x1) et n2 conditions hi(x2,Y)=0 (en x=x2≠x1) (n=n1+n2)

• Cas particulier classique : une équation scalaire du second ordre y″=f(x,y,y′) avec y(x1)=y1 et y(x2)=y2.

• Deux méthodes d’approche : méthodes de tir et méthodes de relaxation.



Méthodes de tir

• Idée : On va intégrer en partant de x1 à partir d’un point initial qui vérifie les n1 premières conditions. On ajuste ensuite le point de départ de manière à ce que les n2 autres en x=x2 soient satisfaites.

• Le point de départ est Y(x1), en vecteur à n composantes. Les n1 conditions en x=x1 laissent un « espace » de dimension n2 pour choisir Y(x1). On dira Y(x1)=Y(x1,v1,…,vn2

). On écrit V=(v1,…,vn2).

• Pour un choix de V, on intègre par une méthode classique jusqu’à x=x2. On obtient Y(x2,V). On regarde ensuite fk=hk(x2,Y(x2,V)) pour k=1,…,n2. (F=(f1,…,fn2

))• On va chercher à fixer V de manière à obtenir F=0 Résoudre un

système d’équations linéaires. Si on est capable de calculer les dérivées partielles (∂Fi/∂Vj) (même numériquement), on peut utiliser Newton-Raphson. Sinon, on peut faire de la dichotomie.

• Inconvénient : Chaque essai nécessite une intégration, et même plusieurs si on veut les dérivées partielles numériquement. Numériquement, ça peut être long !



Méthodes de relaxation• On remplace l’équation différentielle par un schéma de différences

finies :– On divise l’intervalle en p segments de longueur h=(x2-x1)/p; on pose

ti=x1+i×h, i=0,…,p (t0=x1, tp=x2); on pose Yi=Y(ti).

– On approxime

– Et on remplace l’équation par

– Et les conditions aux limites s’écrivent

• Ceci donne un système non linéaire d’équations (dimension p×n+n1+n2 = (p+1)×n) que l’on doit résoudre pour trouver Y0,…,Yp.

htt

tttt

xii

ii

iiii 1

1

11 )()(

2d

d

YYYYY

pitt

hf iiiiii ,...,1

2,

211

1

YYYY

22101 ,...,10),(et,...,10),( njxhnjxg pjj YY



Méthodes de relaxation (2)• Cas particulier : une équation scalaire du second ordre y

″=f(x,y,y′), avec y(x1)=y0 et y(x2)=yp donnés. – On ne transforme pas en système différentiel.

On se place sur les points ti

– Et on remplace l’équation par

• Ca permet de diminuer la dimension du système d’équations.

211

2114

1

112

2 2

)(

)(2)()()(

d

d

h

yyy

tt

tytytyt

x

y iii

ii

iiii

donnés.etavec1,...,12

,,2 0112

11 pii

iiiii yypih

yyytfhyyy



Méthodes de relaxation : résolution• On doit résoudre l’équation aux différences finies :

• On peut réécrire cela F(Y)=0 avec Y=(Y0,…,Yp) qui se résout par Newton-Raphson (dimension n(p+1)). A chaque pas, on cherche l’incrément ΔY à appliquer à Y :(JF = Jacobienne de F)

• Yn(i-1)+j =Yi,j . On a

La matrice JF est bloc-diagonale ! Il faut tenir compte de cette forme pour résoudre le système (élimination Gaussienne bloc par bloc) !

YYJF

22101

111

,...,10),(et,...,10),(

,...,12

,2

njxhnjxg

pitt

hf

pjj

iiiiii

YY

YYYY

1 ou si02

,2 ,

,11,1,,

iii

Y

FtthfYYF

ji

jiiiiijijiji

YY



Méthodes de relaxation : plus loin

• Dans certains cas, il peut y avoir des conditions au limites au milieu de l’intervalle considéré Ca rajoute un bloc spécial dans la milieu de la matrice.

• Dans d’autres situations, on cherche à ce que les p+1 points ti ne soient pas régulièrement répartis, mais puissent être alloués de manière dynamique au cours du processus de relaxation– La solution = considérer le vecteur T=(t0,…,tp) comme un

ensemble de variables supplémentaires et donner des équations à satisfaire.

– Les codes d’évolution stellaire fonctionnent de cette façon…




• Techniques de base• Estimateurs et statistique • Modélisation de données• Résolution numérique d’équations différentielles• Equations aux dérivées partielles

• Types d’équations• Equations elliptiques : Méthodes de relaxation• Equations elliptiques : Surrelaxation• Equations hyperboliques : schémas de Lax, leapfrog…• Equations paraboliques : schémas FTCS, de Crank-Nicholson…



Equations aux dérivées partielles (PDEs)

• Une gamme de problèmes très vastes en astrophysique : HD, MHD = codes eulériens.

• Méthode de base : différences finies, mais il y a d’autres approches.

• Trois familles d’équations : hyperboliques, paraboliques, elliptiques

• Deux types de problèmes : – Hyperboliques, paraboliques = problèmes avec des conditions

initiales propagation, diffusion = évolution temporelle. problème = stabilité du schéma de discrétisation

– Elliptiques = problèmes statiques avec des conditions aux limites complexes problème = efficacité de la convergence vers la solution



Types d’équations aux dérivées partielles

• Equation hyperbolique B2-4AC>0 . Exemple l’équation des ondes (c = vitesse de propagation)

• Equation parabolique B2-4AC=0 . Exemple l’équation de diffusion (D = coefficient de diffusion)

• Equation elliptique B2-4AC<0 . Exemple l’équation de Poisson (ρ = terme source)

0),(),(),(

2

22

2

2

y

yxuC

yx

yxuB

x

yxuA

2

22

2

2

x

uc

t

u

x

uD

xt

u

),(2

2

2

2

yxy

u

x

u



Equations elliptiques : problèmes de conditions aux limites

• Dans ce type de problème, la forme des conditions aux limites compte au moins autant que l’équation elle-même…

• Discrétisation : On introduit un réseau de points (xj,yl), pour j=0...J, l=0…L, réalisant un maillage de l’espace considéré.

• On approxime

• L’équation de Poisson se réduit à

plus des conditions aux limites pour j=0, j=L, l=0, l=L .

• Mis bout à bout, la résolution se ramène à un système linéaire

),,0(),,,0( 00 LllhyyJjjhxx lj

2

1,,1,

22

2

2

,1,,1

22

2 2),(et

2),(

h

uuuyx

y

u

h

uuuyx

x

u ljljljlj

ljljljlj

11et11pour4 ,2

,1,1,,1,1 L-lJjhuuuuu ljljljljljlj

),,,,,,,,,,(avec ,1,2,10,1,01,00,0 LJLL uuuuuuu ubuA



Equations elliptiques : Résolution du système

• La résolution de l’équation aux différences finies se ramène donc à la résolution d’un système linéaire. Simple ?

• OUI MAIS : La taille du vecteur u est (J+1)(L+1) La taille de la matrice A est (J+1)(L+1)×(J+1)(L+1) . Si J=L=100, u est de taille 10000 et la matrice A contient 108 éléments !! Impossible par des méthodes générales…

• En fait la matrice A est très creuse : tridiagonale avec bordures• Toute méthode de résolution doit tenir compte explicitement de la

forme de la matrice• Les méthodes directes (pivot, LU, gradient conjugué…) ne sont

efficaces que pour des tailles modérées (<300×300) de grilles, et si on a l’espace mémoire suffisant pour stocker la matrice…

• Autrement, les bonnes méthodes sont les méthodes de relaxation



Equations elliptiques : Méthodes de relaxation

• En général, une équation elliptique du second ordre se réduit toujours à une équation de la forme

équivalente au système A.u=b. Idée : On décompose A en E-F où E est facilement inversible (diagonale ou tridiagonale)

• On part d’un choix initial u(0) et itère l’équation par une procédure de point fixe:

• Dans la pratique on a A = L+D+U (L= diagonale inférieure, D = diagonale, U = diagonale supérieure)– Méthode de Jacobi : E = D, F=-(L+U);– Méthode de Gauss-Seidel : E = L+D, F=U

ljljljljljljljljljljlj fueuducubua ,,,1,,1,,,1,,1,

buFuEbuFE )(

buFuE )()1( kk



Equations elliptiques : Méthodes de relaxation

• Les deux méthodes sont convergentes mais lentement. Gauss-Seidel est un peu plus efficace.

• L’erreur décroît comme ρs-k , où ρs = rayon spectral de la matrice

E-1.F. Plus la grille est grande, plus ρs est proche de 1 convergence lente ! Typiquement,

• Solution : méthode de surrelaxation (SOR). On part de Gauss-Seidel

avec w(k) = vecteur résidu, et on remplace par

avec 1<ω<2

)(1)()(1)(

)(1)1(

)()1(

)()(.)(

.)(

)(

kkkk

kk

kk

wDLubuUDLDLu

buUDLu

buUuDL

22 1~1 JkJ kss

)(1)()1( )( kkk wDLuu



Equations elliptiques : Méthode de surrelaxation (SOR)

• Avec un bon choix de ω, la méthode converge plus vite. On montre que le choix optimal est

• Dans ce cas le rayon spectral de la méthode SOR est

• La convergence est plus rapide !• Problème : le gain n’est réel que si ω ≈ ωop. Or il est très difficile de

connaître ρJacobi (dépend du problème et de ses conditions aux limites)• Quand on ne sait pas, on prend une valeur standard (Neumann-Dirichlet)

2Jacobi11

2

op

JJJ op

221

2221

-11

SOR2Jacobi

2

2Jacobi

JacobiSOR

Lcos

Jcos

2

1Jacobi



Equations elliptiques : Méthode de surrelaxation (SOR) : Formules pratiques

• Le but est de dégager des formules pratiques pour la SOR. On reprend l’équation générale

• Le résidu wj,l s’écrit

• La formule d’itération

à condition de prendre les variables dans la bon ordre pour faire l’inversion de L+DDO J = 2,…. DO L = 2,… W = A(J,L)*U(J+1,L)+B(J,L)*U(J-1,L)+C(J,L)*U(J,L+1)+D(J,L)*U(J,L-1)+E(J,L)*U(J,L)-F(J,L) U(J,L) = U(J,L)-OMEGA*W/E(J,L) END DOEND DO

• Amélioration : accélération de Tchébychev. On prend ω=1 au départ, et on le change à chaque itération pour le faire tendre vers ω=ωop

ljljljljljljljljljljljlj fueuducubuaw ,,,1,,1,,,1,,1,,

ljljljljljljljljljljlj fueuducubua ,,,1,,1,,,1,,1,

lj

ljklj

klj

kkk

e

wuu

,

,)(,

)1(,

)(1)()1( )( wDLuu

1pour 4/1

1,

2/1

1,1

Jacobi)(

)1(

Jacobi

)1()0(

kk

k



Equations de propagation (hyperboliques)

• On cherche une fonction u(x,t) satisfaisant une équation hyperbolique; on connaît u(x,0) (condition initiale). On cherche à connaître l’évolution dans le temps.

• On va discrétiser spatialement et temporellement. Par exemple, si u(x,t), on écrit

• Un schéma de discrétisation est un formule permettant de calculer ujn+1 (j=1,

…,J) en fonction des ujn (j=1,…,J) et éventuellement uj

n-1 (j=1,…,J)• Important : La stabilité d’un schéma (von Neumann). Un schéma doit être

stable pour être praticable. Un mode propre du schéma c’est

• ujn+1/uj

n=ξ . Stabilité |ξ(k)| ≤ 1 pour tout k (sinon on pourrait trouver un mode croissant exponentiellement)

• On injecte la forme d’un mode propre dans l’équation du schéma pour trouver ξ(k)…

),(),,1,0(),,,0( 00 njnjnj txuuntnttJjxjxx

ion)amplificatd'facteur )( onde;d' nombre(e kku xikjnnj



Equations de conservation de flux• La plupart des équations de propagation peuvent se réécrire comme

des équation de conservation de flux

• Exemple : l’équation des ondes

• On va considérer une équation conservative scalaire tout simple

et la discrétisation

flux) (sionsmultidimen en)(

FFuFu

xt

uuFuFu

00)(etavecavec

2

22

2

2

cc

vr

xtt

us

x

ucr

x

rc

t

sx

sc

t

r

x

uc

t

u

x

uc

t

u

x

uu

x

u

t

uu

t

u nj

nj

nj

nj

nj

nj

2; 11

,

1

,



Schéma explicite FTCS

• On injecte dans l’équation

• On obtient un schéma explicite dit FCTS (Forward Time Centered Space)

• Est-il stable ? On cherche les modes propres….

• |ξ(k)| > 1 pour tout k FCTS est toujours instable !!! Il faut trouver mieux…

x

uutcuu

x

uuc

t

uu nj

njn

jnj

nj

nj

nj

nj

2211111

1

x

uu

x

u

t

uu

t

u nj

nj

nj

nj

nj

nj

2; 11

,

1

,

xkx

tcik

xc

t

xjiknxjiknxikjnxikjn

sin1)(2

eeee )1()1(1



Schéma de Lax• On remplace uj

n par (uj+1n+uj-1

n)/2 dans la dérivée temporelle

• Stabilité ? On trouve

• On veut |ξ(k)| ≤ 1 pour tout k

• On appelle cela la condition de Courant.Interprétation : On calcule uj

n+1 (en x=xj) à l’aide de uj+1n et uj-1

n (en x=xj-

1 en x=xj+1 ). L’information se propage à la vitesse maximale ±c. Les points uj+1

n et uj-1n doivent être en dehors de zone liée à uj

n+1.

xkx

tcixkk

sincos)(

nj

nj

nj

njn

j

nj

nj

nj

nj

nj

nj

nj

uux

tcuuu

x

uu

x

u

t

uuu

t

u11

11111

,

111

, 222;

2

2

1x

tc



Schéma de Lax• Dissipation

• Si |c|Δt < Δx, |ξ(k)| < 1 L’amplitude des modes décroît. Il y a de la viscosité numérique ! Interprétation :

• Tout se passe comme si on avait ajouté un terme de diffusion (parabolique) à l’équation initiale…

• Dans la pratique l’effet est faible car |kΔx|<<1 (longueur d’onde >> Δx).

xkx

tck

22

22

sin11)(

diffusion de terme

2

221111

1

2

2

2

1

2 x

u

t

x

x

uc

t

u

t

uuu

x

uuc

t

uu nj

nj

nj

nj

nj

nj

nj



Ordre 2 en temps : Staggered Leapfrog

• On va centrer le calcul de ∂u/∂t.

• Le schéma est du second ordre spatialement et temporellement. Mais on a besoin de l’information à tn et tn-1 pour calculer à tn+1

• Stabilité : On cherche les modes propres. On tombe sur

• Si |c|Δt/Δx ≤ 1 (Condition de Courant…) la racine est réelle on a |ξ| = 1 (stabilité); sinon ξ est imaginaire pur avec |ξ| > 1

• |ξ| = 1 pas de viscosité numérique ! C’est ce qui fait l’intérêt de cette méthode.

nj

nj

nj

nj

nj

nj

nj

nj

nj

nj

uux

tcuu

x

uu

x

u

t

uu

t

u11

1111

,

11

, 2;

2

22 sin1sin01sin2

xkx

tcxk

x

tcixk

x

tci



Staggered Leapfrog : Equations du second ordre

• Dans le cas d’une équation de conservation de flux le leapfrog s’écrit

• On écrit ce schéma pour l’équation des ondes (r = c∂u/∂x, s = ∂u/∂x).

• On remplace. La deuxième équation donne

ce qui est complètement équivalent à la discrétisation directe de l’équation des ondes avec 2Δt et 2Δx. On écrira donc le leapfrog pour ces équations sous la forme classique

)(avec1111 n

jnj

nj

nj

nj

nj x

tuFFFFuu

2222

2

22

)(2

2

)(2

2

x

uuuc

t

uuu nj

nj

nj

nj

nj

nj

xt

)(uFu

t

uu

t

us

x

uuc

x

ucr

rrx

tcss

ssx

tcrr

nj

nj

n

j

nj

nj

nj

n

j

nj

nj

nj

nj

nj

nj

nj

nj

nj

2

2avec

11

11

1111

1111

2112

2

11

)(

2

)(

2

x

uuuc

t

uuu nj

nj

nj

nj

nj

nj



Schéma en deux temps de Lax-Wendroff• Quand les équations sont plus complexes, le leapfrog peut

être instable car il couple les points deux par deux. Dans ce cas on utilise le schéma de Lax-Wendroff :– On introduit des points intermédiaires (xj+1/2, tn+1/2 ). On calcule la

valeur correspondante de u par le schéma de Lax. On en tire le flux correspondant

– On en tire les flux correspondants et on utilise le leapfrog pour tirer uj

n+1

• Dans le cas de l’équation simple (F=cu), l’ensemble se réduit à

2/12/11

12/12/1 22

nj

nj

nj

nj

njn

j x

tFFF

uuu

2/12/1

2/12/1

1

nj

nj

nj

nj x

tFFuu

x

tcuuuuuuu n

jnj

nj

nj

nj

nj

nj

avec2

2 11111



Schéma en deux temps de Lax-Wendroff• Stabilité ? On trouve

• |ξ| ≤ 1 |α| ≤ 1 (Condition de Courant !).

• En général quand α ≠ 1, |ξ| < 1. Il y a de la dissipation…

• L’effet est plus faible que dans le schéma de Lax. Quand

|kΔx|<<1, on a

alors que dans le schéma de Lax on a

• Quelle stratégie adopter ? Pour les problèmes qui se mettent sous la forme d’une conservation d’un flux (type ondes), adopter d’abord le leapfrog. S’il y a des problèmes d’instabilité, passer au schéma de

Lax-Wendroff.

22 )(11 xk

8

)(11

422 xk

2222 cos111cos1sin1 xkxkxki



Raffinement : dérivation « face au vent »

• Certaines équations (advection…) sont sensibles aux problèmes de transport (passage de chocs, changement d’états…). Si c>0, l’information sur uj

n+1 ne peut pas venir de unj+1 (et vice versa si

c<0). Dans ce cas on préfère calculer ∂u/∂x comme ceci :

• On appelle cela dérivation « face au vent » (upwind)

• Du coup la discrétisation spatiale n’est plus que du premier ordre. Mais ça peut être plus stable dans certains cas… A utiliser quand c’est nécessaire !

x

uu

cx

uu

cx

uu

x

u nj

nj

nj

nj

nj

nj

nj 2 de lieu au

0 si

0si11

1

1

,



Equations de diffusion (paraboliques)

• Equations du type

• D = coefficient de diffusion. C’est une équation de conservation de flux avec F = -D(∂u/∂x). Mais on préfère en général utiliser des méthodes spécifiques.

• Si D est constant, on a l’équation de la chaleuravec une discrétisation immédiate

• C’est un schéma explicite de type FTCS, mais plus stable…

• Interprétation : Le pas de temps doit être plus petit que le temps de diffusion à travers une (demi) cellule.

x

uD

xt

u

2

2

x

uD

t

u

211

1

)(

2

x

uuuD

t

uu nj

nj

nj

nj

nj

D

xt

xk

x

tD

2

)(1;

2sin

)(

41

22

2



Equations de diffusion : schémas implicites

• La condition Δt ≤ (Δx)2/(2D) est très contraignante temps de calcul prohibitif

• Il faut chercher des schémas plus stables. Solution : schémas implicites.• Exemple 1 : on évalue ∂2u/∂x2 en t = tn+1 au lieu de t = tn.

• C’est un schéma implicite = il faut résoudre un système linéaire (tridiagonal) pour trouver les un+1

j (j=0,…,J)

+conditions aux limites en j=0 et J-1• Stabilité :

• Mais c’est un schéma du premier ordre Mieux : Crank-Nicholson !

211

111 )(

;1,...,1)21(x

tDJjuuuu n

jnj

nj

nj

2

11

111

1

)(

2

x

uuuD

t

uu nj

nj

nj

nj

nj

! toujours1

2sin41

1

2

xk



Equations de diffusion : schéma de Crank-Nicholson

• On prend la moyenne du schéma explicite et du schéma implicite

• C’est encore un schéma implicite. Mais il est du second ordre en temps (centré en tn+1/2)

• Stabilité :

• C’est le schéma recommandé pour tous les problèmes de diffusion…

1,...,12

)1(22

)1(2 11

11

111

Jjuuuuuu n

jnj

nj

nj

nj

nj

211

11

111

1

)(

22

2 x

uuuuuuD

t

uu nj

nj

nj

nj

nj

nj

nj

nj

! toujours1

2sin21

2sin21

2

2

xk

xk



Equations de diffusion plus complexes

• Si D n’est pas une constante… On discrétise DSi D(x), on appelle Dj+1/2=D(xj+1/2). Le schéma FTCS devient

avec la condition de stabilité

• Crank-Nicholson devient

• Les vraies difficultés commencent quand l’équation n’est pas linéaire : D(x,u) . Les schémas implicites deviennent non-linéaires. Si on est capable de calculer z = ∫D(u) du, le membre de droite de l’équation = ∂2z/∂x2 qu’on linéarise. On calcule zj

n+1 en faisant un développement limité au 1er ordre.

2

111

12/11

1112/1

1

)(2 x

uuuuDuuuuD

t

uu nj

nj

nj

njj

nj

nj

nj

njj

nj

nj

2

12/112/11

)( x

uuDuuD

t

uu nj

njj

nj

njj

nj

nj

2/1

2

2

)(min

jj D

xt

Documents

Septembre 2011 Master 2 AMD - Méthodes numériques pour l'astrophysique1 Méthodes numériques pour lastrophysique M2 « Astrophysique et Milieux Dilués »