Sujet MM
Sujet MM
Sujet MM
L’objectif de ces travaux pratiques est la résolution numérique d’une équation aux dérivées
partielles modélisant l’écoulement de peinture induit par le déplacement d’un pinceau. Un tel
calcul permet par exemple d’estimer l’épaisseur de la couche de peinture déposée sur une surface.
Ces travaux vous permettrons de mettre en application des méthodes itératives de résolution
de système linéaire vu en cours. Vous utiliserez également des formules d’intégration numérique
basées sur la théorie des polynômes d’interpolation.
Informations pratiques :
Elles seront mise à jour sur la page web suivante :
http ://www-ljk.imag.fr/membres/Adrien.Magni/mn.html
1 Description du problème
Il s’agit d’étudier l’écoulement de peinture induit par le déplacement d’un pinceau sur une
paroi plane horizontale. Dans ce modèle rudimentaire, on suppose que le pinceau est constitué
d’une infinité de plaques planes rigides d’épaisseur négligeable et disposées verticalement. La
peinture occupe la totalité du volume délimité par les plaques et la paroi (figure 1).
. .
. .
. .
l
l
. . H
. . l
. x .
y
z
0
Wp
La distance de séparation des plaques est l. Le pinceau se déplace à une vitesse constante
−WP par rapport à la paroi horizontale. On choisit un repère cartésien orthonormé Oxyz dans le
référentiel lié au pinceau. La paroi horizontale coïncide avec le plan Oyz et défile sous le pinceau
1
(fixe) avec une vitesse WP dans la direction Oz. Les plaques verticales composant le pinceau
sont parallèles au plan Oxz, de longueur infinie dans la direction Oz et H suivant Ox. On fait
les hypothèses suivantes :
– fluide newtonien homogène incompressible,
– écoulement permanent et unidirectionnel dans la direction Oz,
– champ de pression uniforme et constant au cours du temps,
– forces de pesanteur négligeables.
La loi fondamentale de la dynamique se réduit alors à l’équation de Laplace
∂2w ∂2w
+ = 0, (1)
∂x2 ∂y 2
où w(x, y) est la composante du champ de vitesse suivant 0z. Le problème étant périodique en y
de période l, on étudie seulement un élément fondamental de largeur l. La peinture adhère aux
plaques, donc les conditions aux limites s’écrivent
w(0, y) = WP , ∀y ∈ [0, l],
w(H, y) = 0, ∀y ∈ [0, l], (2)
w(x, 0) = w(x, l) = 0, ∀x ∈ [0, H].
Le problème à résoudre est donc modélisé par (1) et (2). Il est schématisé dans la figure 2.
x
w=0
H
w=0 w=0
∆w = 0
w=Wp l y
z
∂2w 1
2
(xi , yj ) = 2 [w(xi+1 , yj ) − 2 w(xi , yj ) + w(xi−1 , yj )] = O(h2 )
∂x h
(utiliser la formule de Taylor comme dans le premier chapitre du cours). De même
∂2w 1
(xi , yj ) = 2 [w(xi , yj+1 ) − 2 w(xi , yj ) + w(xi , yj−1 )] = O(k 2 ).
∂y 2 k
2
L’équation (1) donne donc en (xi , yj )
1
2
−k w(xi+1 , yj ) − k 2 w(xi−1 , yj ) − h2 w(xi , yj−1 ) − h2 w(xi , yj+1 ) + 2(h2 + k 2 )w(xi , yj )
h2 k2
= O(h2 ) + O(k 2 ).
On définit le vecteur
u = (w1,1 , w1,2 , ..., w1,N , w2,1 , w2,2 , ..., w2,N , ..., wM,1 , wM,2 , ..., wM,N )T (4)
où seulement les N premières composantes de b sont non nulles. Le problème (3) s’écrit sous la
forme
Au = b (6)
avec A ∈ MM N (R). La matrice A s’écrit par blocs de taille N
S −D 0 ... 0
−D ..
S −D 0 .
A= 0
.. ..
(7)
−D . . 0
..
..
. 0 . S −D
0 ... 0 −D S
3
Notons
Ax = b (8)
le système à résoudre. On peut décomposer la matrice A sous la forme A = M − (M − A) =
M − N , la matrice M étant facilement inversible. On considère alors la solution du système (8)
comme la limite de la suite (x(k) )k≥0 définie par
et on note r(k) = b − Ax(k) le résidu. Ainsi si x(k) → x alors Ax = b. Les méthodes de Jacobi
et Gauss-Seidel sont définies par des choix particulier de la matrice M . Dans le premier cas
M = D, la diagonale de A et dans le second P = D + L, L étant la partie triangulaire inférieure
de A. Citons aussi la méthode de relaxation SOR qui consiste à choisir M = L + D/ω, ω ∈ ]0, 2[
étant un paramètre à determiner pour optimiser la vitesse de convergence. Supposons connu
x(k) , l’itéré suivant est donné par la relation
4
P
Les parenthèses représentent le produit scalaire euclidien (x, y) = xi yi . On peut montrer que
le minimum de Φ est atteint en x, solution du système (8). La méthode de Richardson est donc
aussi une méthode de minimisation de (13).
(r(k+1) , −Ap(k) )
p(k+1) = rk+1 + β (k+1) p(k) , avec β (k+1) = .
(p(k) , Ap(k) )
Le paramètre α(k) est calculé afin que Φ(x(k+1) ) soit minimal ∀α ∈ R. On obtient
(r(k) , p(k) )
α(k) = .
(p(k) , Ap(k) )
où ||x||22 = (x, x). La méthode des gradients conjugués se résume donc ainsi :
Cette méthode est efficace pour résoudre de nombreux systèmes, mais la convergence peut être
lente si la matrice A est mal conditionnée. Une astuce dite de préconditionnement consiste à
multiplier le système (8) par l’inverse d’une matrice P , facile à calculer. L’intérêt est d’obtenir
un nouveau système à résoudre dont la matrice P −1 A est mieux conditionnée que A. Le nouveau
système obtenu sera plus rapide à résoudre. Dans le cas extrême où l’on choisirait P = A le
système P −1 Ax = P −1 b est directement résolu, mais la matrice P = A doit être inversée. La
matrice A étant symétrique et définie positive il existe une décomposition de cholesky A = T T T .
Il est possible de choisir P comme étant une décomposition “simplifiée” P = T̃ T̃ T , où l’on impose
que seuls les termes diagonaux et sous diagonaux de T soient non nuls. Les coefficients non nuls
de T̃ = (ti,j ) sont alors donnés en fonction de A = (ai,j ) par les formules suivantes :
√
t1,1 = a1,1 , t2,1 =a2,1 /t1,1
1/2
tp,p = ap,p − t2p,p−1 , p = 2, ..., M N (15)
t
p,p−1 = a /t
p,p−1 p−1,p−1 , p = 2, ..., M N.
5
Considérons à nouveau la méthode de Richardson (12) pour résoudre le système P −1 Ax =
P −1 b. En remplacant A par P −1 A et b par P −1 b on a,
x(k+1) − x(k) = α P −1 b − P −1 Ax(k)
On obtient la méthode des gradients conjugués préconditionnés suivante, où P est une matrice
symétrique définie positive :
x(0) donne, r(0) = b − Ax(0) , p(0) = z (0) = P −1 r(0) .
Tant que ||r(k) ||2 /||b||2 > Faire :
α(k) = (z (k) , r(k) )/(p(k) , Ap(k) )
x(k+1) = x(k) + α(k) p(k)
(k+1) (17)
r = r(k) − α(k) Ap(k)
P z (k+1) = r(k+1)
(k+1)
β = (z (k+1) , r(k+1) )/(z (k) , r(k) )
p(k+1) = z (k+1) + β (k+1) p(k) .
L’erreur faite avec la solution numérique pourra ainsi être calculée. Le terme source f (x, y) est
déterminé en injectant la solution (19) dans l’équation (18). La résolution du problème (18) est
faite par la méthode des différences finies, en utilisant la même discrétisation qu’au paragraphe
1.1. La solution numérique wnum est contenue dans le vecteur u (4) qui est solution du système
Au = s, la matrice A étant la même qu’en (7). Le second membre s est
s = h2 k 2 (f1,1 , f1,2 , ..., f1,N , f2,1 , f2,2 , ..., f2,N , ..., fM,1 , fM,2 , ..., fM,N )T , (20)
6
Question 1 Ecrire une fonction définissant la matrice A sous forme de matrice creuse. On
évite de stocker les zeros de la matrice pour économiser de l’espace mémoire. On utilisera un
tableau A(1 :N*M,1 :5), puisqu’il y a au maximum 5 coefficients non nuls sur chaque ligne.
Question 2 Ecrire une fonction qui calcule la composante i du produit de la matrice A par un
vecteur x puis une autre qui calcule le vecteur y = Ax. La matrice A construite à la question 1
sera présente en argument de ces deux fonctions.
Question 3 Ecrire une fonction sor qui calcule les itérés x(k) définis par (11) jusqu’à ce que le
critère d’arrêt (21) soit atteint. Les paramètres d’entrée sont la matrice A, les dimensions N et M,
le second membre b, le critère d’arrêt , le paramètre ω, et le nombre d’itérations maximal kmax .
En sortie, la fonction retourne la solution du système, le nombre d’itérations nite effectuées et
le residu obtenu à chaque itération (sous la forme d’un tableau res(1 :nite)).
P
Question 4 Ecrire une fonction qui calcule le produit scalaire euclidien (x, y) = xi yi de deux
vecteurs.
Question 5 Ecrire une fonction gc qui calcule les itérés x(k) définis par l’algorithme (14) jus-
qu’à ce que le critère d’arrêt (21) soit atteint. Les paramètres d’entrée sont la matrice A, les
dimensions N et M, le second membre b, le critère d’arrêt , et le nombre d’itérations maxi-
mal kmax . En sortie, la fonction retourne la solution du système, le nombre d’itérations nite
effectuées et le residu obtenu à chaque itération (sous la forme d’un tableau res(1 :nite)).
Question 6 Ecrire une fonction qui construit la matrice T̃ dont les coefficients sont définis en
(15). Seuls les coefficients non nuls seront stockés.
Question 7 Ecrire une fonction qui résout le système P x = y dans les deux cas suivants :
P = D et P = T̃ T̃ T . On rapelle que D est la partie diagonale de A. Dans le cas où P = T̃ T̃ T on
résoudra deux systèmes triangulaire, une étape de descente (T̃ z = y) et une autre de remontée
(T̃ T x = z).
Question 8 Ecrire une fonction gcp qui calcule les itérés x(k) définis par l’algorithme (17)
jusqu’à ce que le critère d’arrêt (21) soit atteint. Les paramètres d’entrée sont la matrice A, les
dimensions N et M, le second membre b, le critère d’arrêt , le nombre d’itérations maximal kmax
et un entier numP qui indique la matrice P que l’on considère. En sortie, la fonction retourne la
solution du système, le nombre d’itérations nite effectuées et le residu obtenu à chaque itération
(sous la forme d’un tableau res(1 :nite)).
7
2.3 Application au problème physique : simulation de l’écoulement de la
peinture
Ayant validé la méthode des gradients conjugués pour résoudre le système Au = s dans la
section précédente, on l’utilise maintenant pour simuler l’écoulement de peinture présenté dans
le paragraphe 1.
Désignons dans la suite f , une fonction réelle, continue sur un intervalle [a, b] et cherchons
tout d’abord à approcher l’intégrale monodimensionnelle
Z b
I(f ) = f (x) dx.
a
c’est-à-dire une somme pondérée de valeurs de f en des points (xi )1,...,m de l’intervalle [a, b]. On
dit que ces points sont les nœuds de la formule de quadrature, et que les nombres αi ∈ R sont
ses poids — même si les poids réels sont en fait les (b − a)αi . Les poids et les nœuds dépendent
de m mais pas de f .
Une manière d’obtenir une formule de quadrature est d’intégrer une approximation polyno-
miale de la fonction f . L’idée est que si les deux fonctions sont proches, leurs intégrales le sont
aussi. Ainsi, pour m ≥ 2, la formule de Newton-Cotes à m points est définie par
Z b
QN C(m) = Pm−1 (x) dx,
a
b−a
où Pm−1 est le polynôme de degré m − 1 qui interpole f aux points xi = a + (i − 1) m−1 ,
i = 1, . . . , m. Un calcul simple permet d’obtenir les expressions suivantes de QN C pour m =
2, . . . , 4 :
QN C(2) = b−a
2 f (a) + f (b) , (formule des trapèzes)
b−a a+b
QN C(3) = 6 f (a) + 4f 2 + f (b) , (formule de
Simpson)
b−a 2a+b a+2b
QN C(4) = 8 f (a) + 3f 3 + 3f 3 + f (b) ,
8
Il est possible d’estimer l’erreur de ces différentes approximations, suivant les valeurs de m.
On peut montrer, par exemple, que si f est au moins de classe C 4 sur [a, b], alors l’erreur pour
la formule de Simpson vérifie
Z b
(b − a)5
f (x) dx − QN C(3)
≤ M4 ,
a
2880
où M4 = supx∈[a,b] f (4) (x).
Une idée pour améliorer l’approximation est de diviser l’intervalle [a, b] de départ, et d’ap-
pliquer les formules de Newton-Cotes sur chaque sous-intervalle.
Soit a = z0 < · · · < zn+1 = b une subdivision de [a, b], on peut écrire
Z b n Z
X zi+1
f (x) dx = f (x) dx.
a i=0 zi
Considérons maintenant l’intégrale d’une fonction g, réelle et continue sur un intervalle [a, b]×
[c, d] :
Z bZ d
J(g) = g(x, y) dx dy.
a c
On introduit une subdivision a = z0 < ... < zM +1 = b de l’intervalle [a, b] et c < w0 < ... <
wN +1 = d de [c, d]. Alors,
M X
X N Z wj+1 Z zi+1
J(g) = g(x, y) dx dy. (23)
i=0 j=0 wj zi
9
En utilisant la formule de quadrature des trapèzes, et en notant h = (b − a)/(M + 1), k =
(d − c)/(N + 1), (24) se simplifie comme ceci
M N
(M,N ) hk X X
Q2D(2) = (g(zi , wj ) + g(zi , wj+1 ) + g(zi+1 , wj ) + g(zi+1 , wj+1 )) . (25)
4
i=0 j=0
(M,N )
Question 11 Ecrire une fonction Int_2d qui calcule Q2D(2) .
8 Wp l 2 X 1
D= , (27)
π3 n3
n impair
10