collectionscanada.gc.cacollectionscanada.gc.ca/obj/s4/f2/dsk3/ftp04/MQ57870.pdf · Résumé Ce mémoire porte sur la résolution itérative du problème tridimensionnel de Stokes

NOTE TO USERS

This reproduction is the best copy available.

JULIE LABBÉ

RESOLUTION ITÉRATTVE

DU PROBL~~ME T R I D I M E N S I O ~ L DE STOKES

~ é m o i r e présenté

à la Faculté des Études Supérieures

pour l'obtention

du grade de Maître ès Sciences (MSc.)

Département de Mathématiques et Statistique

FACULTÉ DES SCIENCES ET GÉNIE

UNIVERSITÉ LAVAL

@Julie Labbé, 2001

National Li braiy Bibliothèque nationale du Canada

Acquisitions and Acquisitions et Bibliographie Services services bibliographiques

395 Wellington Street 395. rue Wellington Ottawa ON KIA O N 4 Ottawa ON K1 A ON4 Canada Canada

The author has granted a non- exclusive licence allowing the National Library of Canada to reproduce, loan, distriiute or sell copies of this thesis in microform, paper or electronic formats.

The author retains ownership of the copyright in this thesis. Neither the thesis nor substantid extracts fiom it may be printed or otherwise reproduced without the author's permission.

L'auteur a accorde une licence non exclusive permettant a la Bibliothèque nationale du Canada de reproduire, prêter, distribuer ou vendre des copies de cette thèse sous la forme de microfïche/fïlm, de reproduction sur papier ou sur format électronique.

L'auteur conserve la propriété du droit d'auteur qui protège cette thèse. Ni la thèse ni des extraits substantiels de celle-ci ne doivent être imprimés ou autrement reproduits sans son autorisation.

Résumé

Ce mémoire porte sur la résolution itérative du problème tridimensionnel de Stokes dis-

crétisé par la méthode des éléments f i s et est divisé en trois chapitres. On y développe .

des methodes de résolution pour le problème de Stokes qui sont également applicables aux

problemes non linéaires de Stokes généralisé. Nous proposons une méthode de résolution

basée sur l'utilisation de l'élément de Taylor-Hood en 3D qui, à notre connaissance, n'a

pas été testée auparavant. Pour y parvenir, nous présentons dans le premier chapitre le

problème de Stokes, sa formulation variationnelle et sa discrétisation. Dans le second cha-

pitre, cous décrivons le cadre général des méthodes de projection et les méthodes de type

Krylov utilisées ainsi que certains procédés d'orthogonalisation et de biorthogonalisation.

Finalement, dans le dernier chapitre, on présente les différentes méthodes itératives com-

binant des algorithmes de type Krylov avec des préconditionneus adaptés au problème

de Stokes. Par la suite, on étudie la performance de ces méthodes sur des problèmes tests

t~dimensionnek .

Avant-propos

Pour débuter, je voudrais remercier grandement mon directeur de recherche, Robert

Guénette qui a été très patient, disponibIe et extrêmement compréhensif. En effet, je

tiens à le remercier de m'avoir permis de rédiger mon mémoire à distance et d'avoir su

concilier avec tous les inconvénients que cela comportait. J'airnerais également profiter de

l'occasion pour remercier les gens qui m'entourent et qui m'ont encouragés à poursuivre

mes ambitions. Tout d'abord, je crois que l'honneur de la première place revient sans

aucun doute à Daniel Turgeon qui m'a apporté une aide exceptionnelle tout au long de

mes études graduées et ce, à la fois en tant que collègue et mari. Je dois également remercier

ma a l e Laurianne qui a su démontrer une sagesse particulière malgré son très jeune âge

me permettant ainsi de terminer mon mémoire dans un délai tout à fait raisonnable.

Ensuite, je voudrais remercier mes parents qui m'ont toujours soutenu dans mes études

et en particulier ma mère qui était toujours disponible pour garder sa petite-fille afin de

me permettre quelques passages à l'université.

En terminant, j'aimerais remercier mes amis qui ont rendu les travaux d'équipe et les

devoirs plus intéressants qu'on aurait pu le croire et enrichissants sur bien des sujets :

Daniel Turgeon à qui je dédie ce mémoire, Julie Pelchat, Manon Drolet, Charles Fortin

ainsi que Hans Bherer.

Table des matières

Avant-propos

Table des matières

Table des figures

Liste des tableaux

Introduction

v

vii

1 Problème de Stokes 5

1.1 Équations de Navier-Stokes . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Problème de Stokes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1.2 Conditions aux limites . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.3 Problèmes modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Formulation variationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.2.1 Résultats d'existence et d'unicité . . . . . . . . . . . . . . . . . . . 19

1.3 Discrétisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.3.1 Éléments f i s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

TABLE DES MAT@RES

1.3.2 L'élément de Taylor-Hood . . . . . . .. . . . . . . . . . . . . . . . 25

1.3.3 L'élément Mini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2 Méthodes de sous-espaces de Krylov 29

2.1 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2 -2 Procédé d'orthogonalisation d' Arnoldi . . . . . . . . . . . . . . . . . . . . . 33

2.3 Algorithme FOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.4 Mgonthme GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.5 Mgonthme du Gradient Conjugué . . . . . . . . . . . . . . . . . . . . . . . 43

2.6 Algorithme MINRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.7 Algorithmes de biorthogonalisation . . . . . . . . . . . . . . . . . . . . . . 56

2.8 Préconditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.8.1 Généralités sur le préconditionnement . . . . . . . . . . . . . . . . . 68

2.8.2 Algorithmes de type Krylov préconditionnés . . . . . . . . . . . . . 69

3 Résolution numérique du problème de Stokes 76

3.1 Méthodes itératives de résolution du problème de Stokes . . . . . . . . . . 76

3.1.1 Généralités sur les techniques de résolution du problème de Stokes . 77

3.1.2 Approche globale basée sur l'algorithme MINRES . . . . . . . . . . 82

3.1.3 Approche globale basée sur la méthode d'Arrow-Hurwicz . . . . . . 84

3.2 Problèmes tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.3 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

3.3.1 Résultats numériques à l'aide de l'élément de Taylor-Hood . . . . . 99

TABLE DES MATL?&ZS iv

3.3.2 Résultats numériques B l'aide de l'élément de Minî . . . . . . . . . . 116

. . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Outils informatiques utilisés 121

Conclusion 124

Bibliographie 126

Table des figures

. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Écoulement de Poiseuille 15

1.2 Éléments P l e t P2 endimension3 . . . . . . . . . . . . . . . . . . . . . . . 24

1.3 Discrétisation de Taylor-Hood (P2 - Pt) . . . . . . . . - . . . . . . . . . . 25

1.4 Discrétisation Mini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1 Méthode de projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Ellipse E(c.d. a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1 Problème de la cavité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Premier maillage de la cavité : CUBE1 . . . . . . . . . . . . . . . . . . . .

3.3 Problème de la section carrée . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Premier maillage de la conduite à section carrée : PRISME1 . . . . . . . .

3.5 Problème de la jonction des deux cylindres . . . . . . . . . . . . . . . . . .

3.6 Premier maillage des cylindres : CYLINDRES1 . . . . . . . . . . . . . . .

3.7 Problème de la contraction en trois dimensions . . . . . . . . . . . . . . . .

3.8 Premier maillage de la contraction : CONTRACTION3Dl . . . . . . . . .

3.9 Comparaison des rapports E. zj pour les plus gros maillages de chaque

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . problème

TABLE DES FIGURES

3.10 Graphique du nombre d'itérations en fonction de h pour le problème de la

cavité 3D résolu par la méthode MINRES avec une discrétisation Taylor-Hoodl04

3.11 Graphique du nombre d'itérations en fonction de h pour le problème de

la section carrée résolu par la méthode MINRES avec une discrétisation

Taylor-Hood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

3.12 Graphique du nombre d'itérations en fonction de h pour le problème de

la cavité 3D résolu par la méthode Arrow-Hurwicz avec une discrétisation

Taylor-Hood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

3.13 Graphique du nombre d'itérations en fonction de h pour le problème de la

section carrée résolu par la méthode Arrow-Hurwicz avec une discrétisation

Taylor-Hood. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

3.14 Solution en pression pour le problème de la jonction de deux cylindres

résolu par Arrow-Humvicz avec un préconditionnernent SSOR. . . . . . . . 114

3.15 Solution en vitesse pour le problème de la jonction de deux cylindres résolu

. . . . . . . . . . . par Arrow-Hurwicz avec un préconditionnement SSOR 114

3.16 Graphique de convergence pour le problème de la jonction de deux cylindres

résolu par Arrow-Hurwicz avec un préconditionnement SSOR . 115

3-17 Solution en pression pour le problème de la contraction3D résolu par Arrow-

H m i c z avec un préconditionnernent SSOR. . . . . . . . . . . . . . . . . . 117

3.18 Solution en vitesse pour le problème de la contraction3D résolu par Arrow-

Hurwicz avec un préconditionnement SSOR. . . . . . . . . . . . . . . . . . 117

3.19 Comparaison entre le nombre de flops en fonction du nombre de degrés de

liberté de la discrétisation Mini et P2 -Pl pour le problème de la cavité 3D. 121

3.20 Comparaison entre le nombre de flops en fonction du nombre de degrés

de liberté de la discrétisation Mini et Taylor-Hood pour le problème de la

conduite à section carrée. . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Liste des tableaux

. . . . . . . . . . . . . . . . . . . . . . 3.1 Maillages utilisés pour la cavité 3D 88

3.2 Maillages utilisés pour la conduite à section carrée . . . . . . . . . . . . . . 90

3.3 Maillages utilisés pour la jonction de deux cyhdres . . . . . . . . . . . . . 92

3.4 Maillages utilisés pour la contraction 3D . . . . . . . . . . . . . . . . . . . 94

3.5 Nombre de degrés de liberté pour les différents maillages utilisés lors des

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . tests numériques 98

3.6 Problème de la cavité 3D résolu par MINRES avec un préconditionnement

LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

3.7 Problème de la section carrée résolu par hllIVRES avec un préconditionne-

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ment LU 101


SSOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

3.9 Problème de la section carrée résolu par MINRES avec un préconditionne-

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ment SSOR 102

3.10 Problème de la cavité 3D résolu par M L M S avec un préconditionnernent

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jacobi 103

3.11 Problème de la section carrée résolu par MINRES avec un préconditionne-

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ment Jacobi 103

vii

LISTE DES T ' . E A U X

3.12 Problème de la cavité 3D résolu par A r r o w - H k c z avec un précondition-

nement LU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

3.13 Problème de la section carrée résolu par Arrow-Hurwicz avec un précondi-

tionnement LU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

3.14 Problème de la cavité 3D résolu par A r r o w - H e c z avec un précondition-

nement SSOR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

3.15 Problème de la section carrée résolu par Arrow-Hurwicz ab-ec un précondi-

tionnement SSOR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.16 Problème de la cavité 3D résolu par Arrow-Hurwicz avec un précondition-

nement Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.17 Problème de la section carrée résolu par Arrow-Hurwicz avec un précondi-

tionnement Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

3.18 Problème de la jonction de deux cylindres pour l'élément Taylor-Hood. . . 113

. . . . . . . . . 3.19 Problème de la contraction 3D pour l'élément Taylor-Hood. 118


Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

3.21 Problème de la conduite à section carrée résolu par MINRES avec un pré-

conditionnement Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

3.22 Problème de la jonction de deux cylindres résolu par MLNRES avec un

préconditionnement Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . 119

3.23 Problème de la contraction 3D résolu par MINRES avec un précondition-

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nement Jacobi. 119

Introduction

Ce mémoire porte sur la résolution itérative du problème de Stokes discrétisé par la

méthode des éléments finis. Il s'agit d'un problème très important en mécanique des fluides

numérique. En effet, le système de Stokes est le cas Limite des équations de Navier-Stokes

où le nombre de Reynolds est négligeable (Re -t O). Les équations discrétisées constituent

un système linéaire symétrique mais indéfini qui possède la structure d'un problème de

point de selle. Il est primordial de développer une stratégie de résolution du problème

de Stokes car beaucoup de schémas numériques pour les équations de Navier-Stokes sont

basés sur des résolutions successives du système de Stokes. De plus, le problème de Stokes

est largement utilisé dans le traitement numérique des systèmes issus de la modélisation

des écoulements de fluides non newtoniens, en particulier pour les fluides viscoélastiques.

Par ailleurs, dans le contexte d.es fluides newtoniens généralisés, on obtient un système non

linéaire pour lequel la structure du système linéarisé est très voisine de celle du problème

de Stokes. Donc, en principe les méthodes développées dans le cadre de ce mémoire sont

également applicables à ce type de fluide.

On s'intéresse ici à la résolution approchée des écoulements tridimensionnels. Le calcul

tridimensionnel suscite actuellement un très grand intérêt puisqu'on assiste à un dévelop-

pement Ngurant de l'informatique. Les stations de travail disposent présentement d h e

puissance de calcul rendant possible le calcul tridimensionnel. De plus, nous avons accès

à une mémoire centrale de plus en plus grande (1 gigaoctet) même sur des ordinateurs

de bas de gamme. Ces ressources informatiques sont nécessaires pour des calculs tridi-

mensionnels d'intérêt industriel. Toutefois, le calcul 3D présentent plusieurs diflicultés.

En premier lieu, il y a la taille considérable des maillages. Un petit maillage 3D atteint

facilement l'ordre des 10 000 éléments et il n'est pas rare de voir des maillages ayant plus

de 100 000 éléments pour des simulations plw réalistes. Évidemment, l'utilisation de ces

maillages conduit à des systèmes discrets de très grande taille ayant un nombre de degrés

de liberté de l'ordre de 100 000 et même beaucoup plus. Donc, pour l'instant, il est ab-

surde de penser aux méthodes directes pour résoudre des problèmes aussi gigantesques.

C'est pourquoi, on a pensé à développer des méthodes itératives efficaces pour résoudre

le problème de Stokes.

Dans les années 1980, on a assisté à I'émergence de nouvelles méthodes itératives par-

ticulièrement efficaces pour les systèmes creux de grande taille. Depuis, il y a beaucoup

d'intérêts pour ce type de méthodes de résolution. Il s'agit des méthodes de projection sur

des sous-espaces de Krylov (GMRES, CG, LINRES, etc.). En général, une application

directe de ces méthodes n'est pas particulièrement efficace puisqu'elle dépend grandement

du conditionnement de la matrice du système qui est très souvent élevé. C'est pourquoi

on doit préconditionner le système linéaire. Mais la recherche d'un bon préconditionneur

n'est pas évidente. Nous proposons dans ce mémoire différentes combinaisons de précon-

ditionneurs et de résoluteurs de type Krylov.

Avant de proposer des méthodes de résolution, nous devons faire face aux difficultés

que comporte la discrétisation. Le problème de Stokes est un système à quatre équations

dont les inconnues sont les champs de vitesses et de pression. En particulier, nous ne

pouvons choisir le même type d'interpolation pour toutes les variables. Par ailleurs, le

cadre naturel du problème de Stokes est la théorie des éléments mixtes qui exige une

certaine compatibilité entre les choix des espaces de discrétisation. Dans ce mémoire, nous

avons utilisé deux types de discrétisation du problème de Stokes, soit l'élément de Taylor-

Hood qui est d'ordre deux et celui connu sous le nom de Mini qui est d'ordre un. Toutefois,

l'élément de Taylor-Hood comporte beaucoup plus de degrés de liberté que l'élément

Mini. Ceci a eu pour conséquence de réduire l'utilisation de l'élément Taylor-Hood pour

INTRODUCTION 3

les calculs tridimerisio~els jusqu'ici. Un des objeztÏfi du mémoire est de montrer qu'il

est possible de développer une stratégie de résolution pour l'élément Taylor-Hood qiii

soit moins coûteuse qu'on pourrait le croire. Mais les comparaisons des performances sur

les deux types de discrétisatiori ne sont pas évidentes vu la différence entre le nombre de

degrés de liberté. Pour comparer les performances relatives aux différents types d'éléments

pour une méthode et un problème donné, nous pensons qu'il faut faire la comparaison

pour des systèmes ayant un nombre de degrés de liberté du même ordre de grandeur.

Suivant ce critère, nous allons montrer, dans le dernier chapitre, qu'une résolution efficace

du problème de Stokes discrétisé par I'élément de Taylor-Hood peut être plus économique

qu'une résolution avec l'élément Mini.

Plusieurs méthodes furent proposées pour résoudre le problème de Stokes. Parmi celles-

ci on retrouve la méthode d'Uzawa qui est applicable pour les problèmes de point de

selle. Cette méthode réduit le problème au calcul de la pression et sur le plan numérique,

nous obtenons une méthode avec deux niveaux d'itérations. Mais cette stratégie demeure

coûteuse malgré sa robustesse. Dans ce mémoire, on préfère plutôt utiliser une approche

globale afin de réduire le temps de calcul. L'utilisation de la méthode MINFUZS a déjà été

proposée pour la discrétisation Mini. Mais à notre connaissance, l'usage de cette méthode

avec l'élément de Taylor-Hood en 3D n'a pas été testé jusqu'ici. Dans ce mémoire nous

appliquons cette méthode au problème de Stokes. De plus, nous allons étudier une variante

de la méthode d7Uzawa connue sous le nom de Arrow-HuI-Rricz. Pour toutes ces méthodes,

le préconditionnement joue un rôle primordial- On envisage de tester plusieurs stratégies

de préconditionnement afin de déterminer le meilleur choix.

Cet ouvrage est divisé en trois chapitres. Le premier porte sur la formulation du pro-

blème tridimensionnel de Stokes allant des équations gouvernant la mécanique des fluides

à la discrétisation. On présente d'abord les équations de conservation de la masse et de

la quantité de mouvement ainsi que la loi de comportement afm de pouvoir écrire les

équations de Navier-Stokes et de Stokes. Par la suite, on traite des différents types de

conditions aux Iimites et de la formulation variationnelle en y présentant différents résul-

tats d'existence et d'unicité. Puis, on écrit ensuite le problème de Stokes sous la forme

d'un problème mixte. Et finalement, dans la sous-section traitant de la discrétisation, on

décrit brièvement les deux types d'éléments utilisés.

Le second chapitre traite des méthodes de résolution de type Krylov qui ont été utilisées

pour les tests numériques en débutant avec les méthodes de projection. On ne peut parler

des méthodes de type Krylov sans mentionner les procédés d'orthogonalisation ou de bior-

thogonalisation qu'elles requièrent. On étudiera donc quelques uns de ces procédés. On

présentera en détail les algorithmes GMRES, MINRES, BICGSTAB ainsi que la méthode

du Gradient Conjugué qui seront utilisées au chapitre 3. Plus précisément, on présentera

une façon d'obtenir l'algorithme du gradient conjugué comme cas particulier de la mé-

thode de Krylov FOM. La même méthodologie sera appliquée pour obtenir l'algorithme

MINRES. A la fin du chapitre, on traite du préconditionnernent et on y présente différents

algorithmes de type Krylov préconditionnés.

Finalement, le troisième chapitre présente les méthodes itératives de résolution du pro-

blème de Stokes et les quatre problèmes tests que nous avons considérés. Les maillages

et les géométries de chaque problème sont illustrés. Pour clore le chapitre et le mémoire,

on présente les résultats obtenus pour les différentes combinaisons de discrétisations, mé-

thodes de résolution et préconditionnements utilisés. Ces résultats figurent dans des ta-

bleaux et des graphiques commentés dans le but de faire le meilleur choix pour le type de

résolution à adopter.

Chapitre 1

Problème de Stokes

1.1 Équations de Navier-St okes

Tout d'abord, pour se situer un peu, disons que le problème de Stokes est la version

linéaire du problème de Navier-Stokes. E t ce dernier est un problème typique de la méca-

nique des fluides incompressibles. Dans cette section; nous verrons les équations générales

qui gouvernent la mécanique des fluides : l'équation de conservation de la masse, l'équa-

tion de conservation de la quantité de mouvement et la loi de comportement. Pour écrire

ces équations, on s'est inspiré du livre de Pironneau [15]. Pour plus de détails sur la mé-

canique des milieux continus, on consultera le livre de Duvaut [S] ou celui de Marsden et

Hugues (131.

Équation de conservation de la masse

Supposons que p(x, t ) (que nous noterons par la suite p) est la densité d'un fluide au

point x à l'instant t, R est le domaine occupé par le fluide et W un sous-domaine régulier

de Cl. Le taux de changement de la masse du f i i d e dans TV est alors défini par

CHAPITRE 1. PROBLÈME: DE STOKES

et le flvz de masse à travers la frontière aW de W est donné par

où u représente la vitesse du fluide, n désigne la normale extérieure à i3W et d-f est

l'élément de surface.

Pour qu'il y ait conservation de la masse, le taux de changement de masse du fluide

(1.1) doit être égal au flu'r de masse à travers la frontière (1.2), Le.

Or, d'après la formule de Stokes, il est possible de transformer le membre de droite comme

suit

Par conséquent, l'équation (1.3) devient

a V (pu) dx.

On peut supposer la fonction p assez régulière pour qu'elle soit intégrable, que sa dérivée

existe et que cette dernière soit bornée. Alors, on peut faire passer l'opérateur $ sous le

signe de l'intégrale et en regroupant les termes, on obtient

lv [ $ p + ~ (pu ) dx = 0. 1 Nous avons donc une intégrale sur un domaine W quelconque et cette intégale est nulle.

Comme le domaine W est arbitraire, l'intégrand doit donc être nul. C'est ce qui nous

donne l' équation de conservation de la masse ou équation de continuité

CBXPITRE 1. PROBLÈMIE DE STOKES 7

Si on fait maintenant l'hypothèse que la densité du fluide est constante, on a évidemment

et de l'équation (1.4)' on déduit que V - ( p u ) = O, d'où

Ceci exprime le fait que le volume d'une partie quelconque du fluide demeure inchangé

lorsqu'elle est déformée par l'écoulement. On appelle cette relation la condition d'incom-

pressib ilité.

Équation de conservation de la quantité de mouvement

Pour déterminer l'équation de conservation de la quantité de mouvement, nous avons

d'abord besoin d'écrire la loi de Newton (masse x accélération = force) sur un élément de

volume du fluide, noté W. Comme nous connaissons déjà le taux de changement de masse

(LI), nous avons maintenant besoin d'exprimer l'accélération d'une particule du fluide.

En notant par x = (xi, 52, x3) la position d'une particule du fluide à l'instant t, on peut

dire que la particule sera en x + u ( x , t ) At + O(&) à l'instant t + At- Ainsi, l'accélération

d'une particule du fluide est donnée par

Le membre de droite constitue la dérivée matérielle de la vitesse. Plus généralement on

défmira la défivée matérielle d'un champ scalaire f (x7 t ) par

et la dérivée d'un champ uectonel w(z, t ) par

CHAPITRE 1. PROBLÈME DE STOKES 8

Pour appliquer la loi de Newton, nous devons finalement connaître les forces exercées

s u r w :

- les forces extérieures volumiques, 1, f dx,

- les forces de pression,- Iawp n dy, et

- les contraintes de viscosité dues à la déformation du fluide, hW Q n dy,

où a est le tenseur des contraintes visqueuses et u - n te vecteur de traction de Cauchy.

Ce dernier représente la résultante des forces du milieu continu exercée sur l'élément de

surface de normale n. Par conséquent, la loi de Newton s'écrit comme suit

Or, en appliquant la formule de Stokes sur le deuxième terme du membre de droite, on

trouve

En regroupant les termes, on obtient

Puisque nous avons une intégrale nulle sur un domaine W quelconque, l'intégrand doit

être nul et c'est ainsi que nous obtenons l'équation de conseruation de la quantité de

mouvement

Qui s7ecrit encore sous la forme

o ù 7 = -p I + a est le tenseur total des contraintes.

Loi de comportement

Pour étudier les équations d'évolution d'un fluide particulier, il faut décrire la loi de

comportement, c'est-à-dire la relation entre le tenseur a et le champ de vitesse u. Les

CHAPmm 1. PROBL~ME DE STOKES 9

principes généraux de la mécanique des fluides (voir [8] pour plus de détails) suggèrent

une relation de la forme CT = a ( ~ ( u ) ) entre le tenseur des contraintes et le tenseur du

taux de déformation

Ainsi, pour parler de fluide newtozlien en dimension trois, on doit avoir la loi Linéaire

où 17 est la viscosité du fluide et E est une constante. Cette relation peut être simplifiée

grâce à la condition d'incompressibilité (1.5) puisque t r ~ ( u ) = V . ZL = O. On a donc

où q représente la viscosité constante du fluide newtonien. Ainsi, on peut réécrire ltéquation

(1.6) comme suit

p ( g + u * V u +Vp--27jV-(c(u))= f. (1.9)

Donc, on est maintenant en mesure d'écrire les équations de Nauier-Stokes. II s'agit du

système formé par les équations (1.9) et (1.5).

Plusieurs auteurs préfèrent une forme alternative de ce système. Pour y parvenir, nous

allons remplacer ~ ( u ) par l'expression donnée en (1.7) dans l'équation de conservation de

quantité de mouvement réécrite en (1.9). Ainsi, on obtient

Or, puisque V Vu = Au et que V . VuT = V(V u), cette dernière se réécrit encore

comme suit


E t en tenant compte de la condition d'incompressibilité (1.5)' le dernier terme de l'équation

disparaît et on a

D'où le système équivalent de NaMer-Stokes

1 . 1 Problème de Stokes

Par ia suite, nous nous intéresserons au système de Stokes qui est le cas limite des

équations de Navier-Stokes lorsque l'écoulement est lent. Pour bien décrire cette situation,

nous aurons recours à la forme adimensionnelle des équations de Navier-S tokes. Pour plus

de détails à ce sujet, consultez le livre de Pironneau [15]. Pour ce faire, nous avons besoin

d'une vitesse caractéristique U du fluide étudié ainsi que d'une longueur caractéristique

L et d'un temps caractéristique T. Par la suite, nous posons le changement de variables

suivant :

À l'aide de ces nouvelles

suivante : d u

variables, les diverses dérivées se transforment de la manière

En substituant ces relations dans les équations de Navier-Stokes (1.11), on trouve

En multipliant la première équation du système que nous venons d'obtenir par et en

posant

CHAPITRE 1. PROBLÈME DE STOKES

Ce système 1.12 avec les nouvelles variables est identique au système (1.11). La forme

adimensionnelle des équations de Navier-Stokes (1.12) fait apparaître un nombre sans

dimension appelé nombre de Reynoldsdéfini par

Ce nombre traduit l'intensité de la convection du fluide par rapport à la diffusion. Plus

ce nombre est grand, plus l'écoulement est rapide tandis qu'à l'autre extrémité, si R e

est petit, l'écoulement sera considéré comme lent (on dit aussi laminaire). Le nombre de

Reynolds peut être rendu petit de plusieurs façon, en particulier si la viscosité devient

très grande. C'est le cas des polymères fondus. On définit le problème de Stokes comme

étant le problème limite lorsque Re tend vers O.

Le problème de Stokes se lit donc comme suit :

Trouver les champs de vitesses u ( x , y, z ) E R3 et de pression p(x, y, z) E B tels que

puisque si Re + 0, >> 1 et les autres termes de vitesse deviennent négligeables dans la

première équation du système (1 -12).

Notons que dans de nombreuses applications, il est nécessaire de généraliser la relation

linéaire de Newton, on parle alors du problème de Stokes généralisé qui se ditférencie du

problème de Stokes par le fait que la viscosité n'est plus constante :


Le problème obtenu en combinant les relations (1 -6) et (1.8) à partir &J système (1.10)

se lit comme suit :

Trouver les champs de vitesses u (x, y, z) E IR? et de pression p(x, y, z) E R tels que

Exemples de fluides newtoniens généralisés

Nous avons vu que pour le cas newtonien le tenseur des contraintes est défini comme

suit :

U = 277€(~).

Dans le cas newtonien généralisé, il existe d'autres lois pour modéliser a. Voici deux

exemples : la loi de Carreau et la loi de puissance. Dans le cas de la loi de Carreau, le

tenseur des contraintes est donné par

où 77, X et m sont des constantes rhéologiques. Pour la loi de puissance, le tenseur des

contraintes est donné par

Dans le cas newtonien m = 1 et la viscosité q est constante. Ce qui nous conduit au

problème de Stokes. Dans le cas viscoplastique, O < m < 1 et la viscosité dépend de la

vitesse. Pour plus de détails sur ces modèles rhéologiques, le lecteur consultera le livre de

Bird et al. [2].


1-1.2 Conditions aux limites

Conditions aux Iiwiites de type Dirichlet

La forme la plus simple est la condition de Dirichlet homogéne. Elle es t de la forme

où ro est une partie de la paroi r = dS2. Cette condition aux Iimites traduit l'adhérence

du fluide visqueux sur la paroi ro. Plus généralement, on a

où g (x, y, z) E R3. Par exemple, r0 peut être la partie entrante ou sortante du domaine

R occupée par le fluide.

Conditions aux limites de type Neumann

La condition de type Neumann la plus courante est de la forme

r n = O sur I' \r0.

Cette condition signifie que la traction est nulle sur la partie complémentaire à ro de Ia

paroi r. On peut également rencontrer une condition aux limites de Sp e Neumann de la

forme

7 - n = g s u r r o

où ro serait par exemple la partie sortante du domaine R.

Conditions aux limites rnixtes

Il est aussi possible d'imposer une condition de type Dirichlet sur une partie de la paroi

ro et une condition de type Neumann sur une autre partie de la paroi rl. Ce qui nous

CH-APITRE 1. PROBLÈUE DE STOKES

donnerait quelque chose du genre :

où ro et ri sont des parties disjointes de la paroi et dans ce cas-ci, il faudrait avoir

r, u ri = m.

1.1.3 Problèmes modèles

Écoulement de Poiseuille

L'un des écoulements les plus classiques est l'écoulement de Poiseuille. Il s'agit d'étudier

l'écoulement d'un fluide dans un canal. Pour ce faire, on considère un cylindre de révolution

d'axe Z, de rayon R et de longueur L. La longueur du cylindre sera prise assez grande par

rapport à R afin de pouvoir négliger les effets aux extrémités du cylindre. De plus, chaque

section du cylindre est parallèle au plan xOy.

On cherche un écoulement laminaire tel que

1. les lignes de courant soient parallèles à l'axe Oz,

2. le champ de vitesse soit de la forme u = (0,0, u3),

3. l'écoulement soit stationnaire Le. u3 = w(x, y, z),

4. l a vitesse soit nulle sur la paroi du cylindre.

Comme nous considérons un fluide incompressible, nous avons

d'où w = w(x, y). Nous allons maintenant substituer dans les équations de Navier-Stokes

(1.10). D'abord, = O puisqu'il s'agit d'un écoulement stationnaire. De même u. Vu = 0 a u puisque u Vu = us g; = O et &a = " = O. Par ailleurs, comme il n'y a pas de forces a% Bz

STOKES

FIG. 1-1 - Écoulement de Poiseuille

extérieures: f = O. Ainsi, l'équation de conservation de la quantité de mouvement dans

(1.11) s'écrit comme suit :

V p - r]Au =O.

En explicitant termes à termes, on obtient :

Ces équations montrent que la pression p ne dépend que de la variable r, i.e. p = p ( z ) , ~ P ( z ) de telle sorte que , = gAw (x, y) = -C où C est une constante positive. Cette équation

nous dit d'abord que p ( z ) = -Cz + po, C étant donnée par C = y, p, et p~ étant les

pressions respectives dans les sections z = O et z = L et d'autre part que

Aw(x, y) = dans w { - = O sur aw

où w est une section droite quelconque du cylindre. Donc, w est la solution d'un problème

de Dirichlet pour une section w du cylindre.


Pour résoudre ce problème dans le cas pazticulier où la section w serait un disque,

définissons une nouvelle vanable 6 = $9 telle que

AG(x, y) = 5 dans w

G = - c - r l 4

sur aw

Posons W = w - 6, alors le problème de Dirichlet devient

AW(x, y) = O dans w

w=cE r] 4

sur dw

Mais la fonction constante W = :$ est trivialement l'unique solution de ce problème.

Donc, il est facile de voir que

où r2 = x2 + y2. Ceci illustre le fait que le profil de la vitesse est parabolique pour chaque

section du cylindre. Pour plus de détails sur cet écoulement, on peut consulter le livre de

Duvaut [8].

1.2 Formulation variationnelle

Pour plus d'informations relatives à cette section, on peut consulter le livre de Girault-

Raviart [9]. Nous aurons besoin tout d'abord de quelques définitions avant de poursuivre :

L2(12) = {v mesurable : lut2 d z < m 1

CEDIPITRE 1. PROBLBME DE STOKES

De plus, on introduit le produit contracté de deux tenseurs (matrices) d'ordre deux A et

A l'aide de ces définitions, nous verrons maintenant comment on obtient la formulation

variationnelle du problème de Stokes. Pour simplser, considérons le problème de Stokes

avec des conditions aux limites de type Dirichlet homogène, défini comme suit :

Trouver les champs de vitesse u E Et3 et de pression p E B tels que

La formulation variationnelle de la première équation est obtenue en prenant le pro-

duit scalaire dans L2(R) de la première équation du système (1.14) avec une fonction

quelconque v E que nous appelons fonction-test. Ce qui nous donne :

Supposons que u E et que p E L2(f l ) . Comme on a choisi v E v

s'annule sur la frontière r de !2 et la formule de Green nous permet de réécrire le premier

terme de (1.15) de la façon suivante :

par symétrie du tenseur c ( - ) défini par (1.7). De même, nous avons que

C W I T R E 1. PROBLÈME DE STOKES

Donc, la première équation du système de Stokes (1.14) devient :

En procédant de la même façon avec la deuxième équation, Le. en prenant son produit

scalaire dans L2(S2) avec une fonction-test quelconque q E @(Cl), on obtient la formulation

variationnelle du problème de Stokes homogène :

Trouver u E (3ti(R))3 et p E L2(Q) tels que

Nous pouvons considérer une autre formulation variationnelle pour ce problème, en

choisissant une fonction-test v à divergence nulle i.e. dans l'espace

Ainsi, la deuxième formulation variationnelle se lit comme suit :

Trouver ZL E V tel que :

Problèmes mix tes

Nous allons voir ici la théorie ghérale des problèmes mixtes qui constituera le cadre

naturel pour l'étude du problème de Stokes. La référence de base pour cette section est le

livre de Brezzi et Fortin [3].

CKWITRE 1- PROBLEMEDE STOKES 19

On se donne d'abord deux espaces de Hilbert X et M et on note X' et M' les espaces

duaux associés. De plus, on se donne les deux formes bilinéaires suivantes :

A partir de la forme bilinéaire b(-, -) , on peut introduire les applications linéaires continues

B : X + M' et Bt : M + X' définies par

Dans le cadre théorique que nous venons d'établir, le problème à résoudre (appelé

problème mixte) est le suivant :

Trouver (u, A) E X x M tels que :

Si on note par V le noyau de la forme bilinéaire b(-, -) Le.

et qu'on prend v E V , le problème devient :

Trouver u f V tel que :

a ( u , v ) = ( f , v ) V V E V .

1.2.1 Résultats d'existence et d'unicité

Dans cette sous-section, nous énonçons sans preuve quelques résultats connus. Pour

connaître les démonstrations de ces théorèmes, on peut consulter le livre de Girrault-

Ravi& 191.

CHAPITRE 1. PROBLEME DE STOKES 20

ThéorBrne 1 (Lax-Milgram) Soit V un espace de HiZbert et Y' son dual. Soit a(- , -)

une forme bilinéake continue e t V -elliptique, i.e.

b(u7 v) 1 5 Mll~llvllvllv 'v' U r V E V

a(v, v) 2 crllvll; V E V, CE > O.

Alors, pour chaque élément f E V ' le problème (1.19) admet une solution unique TL qui

Théorème 2 Supposons que

inf-sup continue

dépend contznuement de f : 1

l l 4 l v 5 ~ l l f l l v ) -

a(-, 0 ) soit V-elliptique et que b(-, -) satisfasse la condztion

Alors, le problème (1.18) admet une solution uniqve u E V , p E Q où u est la solution

du problème (1.19). De plus, le couple ( u , p ) dépend continuement du second membre f.

Nous allons maintenant; écrire le problème de Stokes homogène sous la forme d'un

problème mixte en considérant la formulation variationnelle (1.16). On &ce le cadre fonc-

tionnel en posant

x = r2(n) e t M = ( X ~ ( R ) ) ~ .

Sur ces espaces, on définit les formes bilinéaires de la façon suivante :

b(v, q ) = - q div V dz.

Ainsi, le problème de Stokes homogène (1.16) peut s'écrire comme suit :

Trouver u E e t p E L2(fl) tels que :

CHAPITRE 1. PROBLËM. DE STOKES

AppLiquons maintenant la théorie des problèmes mixtes au problème de Stokes. D'abord,

l'ellipticitii uniforme est toujours vérifiée car a(v, v) = ~ ~ [ v ( : ~ . P a r ailleurs, le problème

de Stokes homogène satisfait la condition id-sup car l'opérateur B : (31; _t Lg(S1)

est surjectif et, selon un résultat bien connu d'analyse fonctionnelle, ceci est équivalent à

la condition inf-sup :

On peut donc conclure que le problème de Stokes admet une solution unique qui dépend

continuement de f .

1.3 Discrétisation

1.3.1 Éléments finis

Pour la première partie de cette section, on peut se rapporter au livre de Brezzi-Fortin

[3]. Pour commencer, nous devons faire une approximation variationnelle de notre pro-

blème. Revenons à la forme générale d'un problème mixte (1.18). L'approximation interne

d'une formulation variationnelle mixte consiste simplement à introduire des sous-espaces

de dimension h i e & c X et M h c M , et à restreindre la formulation variationnelle à

ces sous-espaces.

Écrivons maintenant le problème (1.18) dans ces sous-espaces. On a alors :

Trouver u h E Xh et ph E Mh tels que


Condition inf-sup discrètes

Nous allons maintenant examiner ce que devient la condition ini-sup (théorème 2) dans

le cas où nous avons des espaces de dimension f i e .

Théorëme 3 Supposons que la fonne G ( - , -) sozt Vh - elliptique i. e. il existe une constante

positive a h > O telle que

Alors, le problème (1.21) admet une solution (uh,ph)- De plus, la solution u h E Vh est

unique tandis que la solution ph est unique à u n élément du noyau de Bi près, i-e. ph est

unique dans Mh \ Ker (Bi).

En effet, en dimension h i e , la condition inf-sup du théorème 2 est toujours vérifiée.

Dans la pratique, ce résultat n'est pas vraiment intéressant car la qualité de la solution est

fonction du paramêtre a h qui dépend du maillage. Nous sommes principalement intéressés

à obtenir des estimations d'erreur qui font intervenir des coefficients indépendants du

mailIage. Voici le théorème fondamental à ce sujet.

Théorème 4 Supposons que les hypothèses du théorème 2 pour le problème continu sont

vér$ées et, de plus, supposons l'existence d'une constante positive P > O vérifiant la

condition :

inf sup { b(vhi qh) ) I P > O . qheMh Z>hEXh I l v h l l ~ l I q h l l ~

Alors,

IIu - u ~ I I x + ~ I P - ph[[,w $ Ci inf [lu - vhllx + c2 inf l l p - VhE'Vh 9hfMh

o ù CL et C2 sont des constantes positives indépendantes de h donc du maillage.

La condition (1.22) est connue sous le nom de condition de Brezzi-Babuska ou encore

la condition inf-sup.

ClilAPITRE 1. PROBLEME DE STOKES

Problème de Stokes

Pour le problème de Stokes, introduisons les deux espaces de dimension finie Wh c

et eh c L2(Q) et posons

Triangulation d'un domaine

Pour les détails de ce paragraphe, on se réfère au livre de P i r o ~ e a u [15]. Pour définir les

espaces d'éléments finis Mh, Xh et Vh, nous devons spécifier la triangulation du domaine

51, la nature des fonctions v h et qh sur chaque élément (linéaire ou quadratique) ainsi que

les paramètres à utiliser pour décrire les fonctions dans Vh. On donnera d'abord quel-

ques définitions et précisions sur les notations de base concernant la discrétisation et la

méthode des éléments finis.

La méthode des éléments finis s'appuie sur des éléments géométriques, plus précisément

sur un maillage du domaine O. Le maillage facilitera la construction des fonctions de base

qu'on note généralement { ~ j } i < - j<N. - Une t~iangulat ion du domaine 0, qu'on notera {z). est un ensemble fini de tétraèdres (en dimension 3) fermés {Tk)t<k<N tels que : - -

r. TkEn' V k = l , ..., N ,

face commune à Ti et Tk

côté commun à T. et Tk

sommet commun à Tj et Th

0

CHAPITRE 1. PROBLEME DE STOKES

L'union des sera noté par Oh. Les sommets de la triangulation seront définis par

{ s ~ } ~ = ~ . . . ~ ~ où Ns est le nombre de sommets de la triangulation. Notons également par

Ne, le nombre d'éléments de la triangulation,

Nb3 le nombre de sommets aux bords (Le. sur la frontière r), Na, le nombre d'arêtes de la trimgdation et

N f , le nombre de faces de la triangulation.

De plus, nous définissons par A$(=) la jième coordonnée barycentrique de e E EX3 par

rapport aux sommets { s : } ~ = ~ - - - ~ de l'élément Tk. Les coordonnées sont définies par le 4 4

système linéaire : C Aisi = s, C Xi = 1 i=l i=l

Par la suite, il sera souvent question d'éléments Pl et d'éléments P2- On peut voir à

quoi ressemble ce genre d'éléments en dimension trois à la figure 1.2.

EIement Pl Rement P2

FIG. 1.2 - Éléments P 1 et P2 en dimension 3.

Les fonctions de base usuelles pour ces éléments sont les suivantes :

- pour l'élément Pl, on a les quatre fonctions de base suivantes :

( A l , A*, X3, X 4 = 1 - X 1 - A 2 - ~ 3 )

- pour l'élément P2, on a les 10 fonctions de base suivantes :

CHAPITRE 1. P R O B L E ~ DE STOKES

ou, si on utilise une base hiérarchique :

Nous d o n s maintenant décrire les deux types d'éléments continus utilisés lors de nos

expérimentations. Ces éléments (en dimension 3) sont bien décrits dans le livre de Brezzi-

Fortin [3].

1.3.2 L'élément de Taylor-Hood

L'élément Taylor-Hood est également connu sous le nom d'élément P2 - Pl. Avant de

décrire ce type d'élément, nous avons besoin de définir quelques espaces. Pour débuter,

posons :

wh = {vh E c0(nh) : vhlZ E ( P ~ ) ~ v k)

où (Pm)" designe l'espace des polynômes de degré < m à n variables. Cet élément est

illustré à la figure 1.3.

Tay lor-Hood

Vitesse Pression

FIG. 1.3 - Discrétisation de Taylor-Hood (P2 - Pl)

CHAPITRE 1. PROBLEME DE STOKES 26

A partir de ce choix, on déduit les espaces d'approximation de la formulation mixte du

problème de Stokes tel que prescrit par la théorie des éléments mixtes :

Cet élément mixte vérifie la condition id-sup discrète et les autres conditions du théorème

3. Par conséquent, nous obtenons l'existence et l'unicité de la solution avec des majorations

d'erreurs indépendantes du maillage. De plus, le théorème implique que cet élément est

d'ordre deux O (h2).

Donnons une borne supérieure du nombre total de degrés de liberté de cet élément. La

dimension de Wh est donnée par

dim Wh = 3Ns + 3Na

tandis que la dimension de Qh correspond à

dim Qh = Ns.

Donc, la dimension totale est au plus

dim Kh + dim M h 5 4Ns + 3Na.

1.3.3 L'élément Mini

Pour définir la discrétisation Mini de l'équation (1.16), nous choisissons une famille de

partitions Th de 0 et nous posons :

Notons ici que pour les tests numériques du dernier chapitre, nous avons utilisé

h = longueur moyenne des arêtes du maillage

CHAPITRE 1. PROBLEME DE STOKES

Pour la partie Linéaire de la solution discrète, définissons les espaces :

& = {ph E C'(a) : P ~ I K E &(K) 'v' K E 7h)

Mais, avec ces deux espaces, la condition de Brezzi-Babuska (1.22) n'est pas satisfaite et la

discrétisation de (1.16) n'est donc pas stable. Pour remédier à cette situation, nous allons

enrichir L'espace XhYl à l'aide de fonctions Locales qui sont en général définies comme suit.

Posons { # K } K ~ ~ , une famille de fonctions satisfaisant :

Xous appelons ces fonctions, les fonctions bulles et nous définissons l'ensemble discret

On peut montrer que &+ et <Ph sont des sous-espaces orthogonaux de (3~:)~ au sens de

la norme 1 11. Posons Xh = Xh,l @ Qh. La formulation discrète de (1.16) est alors :

Les fonctions bulles sont données par

où Ar pour i = 1, .. . , N + 1 sont les coordonnées bqcentriques de l'élément K et iV la

dimension de l'espace. Cet élément est illustré à la figure 1.4.

L'élément Mini fut proposé par Fortin et al. [l] et étudié en détail par R. Pierre [14]. Cet

élément mixte satisfait la condition de Brezzi-Babuska (1.22) et, par conséquent, conduit

à une discrétisation stable du problème de Stokes. En pratique, il est possible d'éliminer


Mini

Vitesse Pression

FIG. 1.4 - Discrétisation bfini

les degrés de liberté associés aux fonctions bulles par un procédé de condensation statique.

Cette procédure est détaillée dans l'article de R. Pierre [14]. Ainsi, sur le plan numérique,

nous obtenons une discrétisation dont le nombre de degrés de liberté correspond à au plus

4Ns. Paxmi toutes les approximations continues du problème de Stokes, c'est celle qui

contient le moins de degrés de liberté d'où son utilisation extensive dans les calculs 3D.

Chapitre 2

Méthodes de sous-espaces de Krylov

Ce chapitre porte sur les méthodes de fype Krylov. Ce type de méthodes fait l'objet

des chapitres 6 et 7 du livre de Saad [16].

2.1 Méthodes de projection

Les méthodes de projection sont à la base de plusieurs méthodes numériques que nous

avons utilisées pour résoudre le problème de Stokes. A h de définir ces méthodes, on

s'inspire du chapitre 5 du livre de Saad [16].

Considérons le système de la forme

oii A est une matrice réelle inversible d'ordre n, b et x étant des vecteurs de Rn. Dénotons

par xo un vecteur de départ, et par ro = b - A x o le résidu associé. La solution x est

caractérisée par

( b - A l , Y) = O V ~ E R *

c'est-à-dire que

b - A X LRn.

CHAPITRE 2. ~MÉTHODES DE SOUS-ESPACES DE KRYLOV

comme on peut voir sur la figure 2.1.

A 6 ' O

FE. 2.1 - Méthode de projection

Le principe de base d'une méthode de projection consiste à se donner un sous-espace

IC C Rn et d'e-xtraire une solution approchée 5 dans l'ensemble de xo + K: vérifiant une

condition d'orthogonalité plus faible que (2.2)

OU encore

On notera la grande similitude avec le procédé de Gderkin qui est à la base de la

méthode des éléments finis. C'est pourquoi la condition d'orthogonalité (2.3) est appelée

condition de Galerkin. Plus généralement, on se donne deux sous-espaces IC et t. Le sous-

espace K: est le sous-espace des candidats approximants, parfois appelé sous-espace de

recherche et le sous-espace L est appelé sous-espace des contraintes ou encore sous-espace

de gauche. Dans ce cas, on cherche une solution approchée Î dans x0 + K vérifiant la

condition

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV

Cette relation peut se réécrire de la façon suivante :

Trouver une solution approchée dans xo + K: telle que

Par analogie avec un procédé utilisé dans la méthode des éléments finis, l'équation (2.4)

porte le nom de condition de Petrou-Galerkin.

Si on note la solution approchée par I = x, + 6, avec 6 E K, et le résidu initial (ou erreur

initiale) par ro = 6 - Axo alors le problème (2.4) devient :

Trouver une solution approchée xo + 6 avec S E K: telle que

Bref! une méthode de projection consiste en une méthode itérative de résolution des

systèmes linéaires qui, à chaque itération construit deux sous-espaces K et L: et recherche

le nouvel itéré dans xo + K: qui satisfait la condition de Petrov-Galerkin (2.4).

11 y a deux classes de méthodes de projection : orthogonale et oblique. Dans les méthodes

de projection orthogonale, on choisit L = K. C'est le cas des méthodes Full Orthogona-

lisation Method (FOM) et Gradient Conjugué (CG) qui seront décrites respectivement

aux sections 2.3 et 2.5 du présent chapitre. Par contre, dans une méthode de projection

oblique, les deux espaces (K: et t) sont différents. En particulier, si on prend L = AK,

on retrouve les méthodes de projection Generalized Minimal RESidual (GMRES) et Ré-

sidu Conjugué (CR) aussi connue sous le nom de méthode MINRES. On parlera de ces

méthodes aux sections 2.4 et 2.6 respectivement.

Au paragraphe précédent, nous avons défini ce qu'était une étape de base d'une méthode

projection dans sa forme la plus générale. La plupart des techniques standards utilisent

plutôt une succession de telles projections. C'est le cas des méthodes itératives de type

Krylov. Les méthodes de type Krylov sont des méthodes de projection basées sur un

CELAPITRE 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV 32

choix particulier du sous-espace K: appelé sous-espace de Krylov (qu'on notera IC, par la

suite). La définition des sous-espaces de Krylov est motivée par le théorème classique de

Cayley-Hamilt on.

Théorème de Cayley-Hamilton

Si pA(X) = det(XI - A) dénote le polynôme caractéristique de A, alors on a que

Si A-' existe, une conséquence directe de ce théorème est l'existence d'un polynôme p de

degré n - 1 satisfaisant

A-' = p ( A ) (2-5)

ce qui nous permet d'écrire la solution du problème (2.1) comme suit

En effet, puisque x = A-'b = A-'(Axo + ro) par définition du résidu initial, en simpli-

fiant, on a x = xo + AM'ro et par (2.5) on obtient le résultat.

Au lieu de choisir ce polynôme de degré n - 1: on pourrait choisir une approximation

de la forme aC = xo +p(A)ro avec un polynôme p d'un degré très petit par rapport à n.

Ceci conduit à la définition suivante des sous-espaces de Krylov. Étant donné une matrice

A et un vecteur ro, on d é f i t la famille de sous-espaces indexée par l'entier m 2 1

OU encore

CHAPITRG 2. ~/~ÉTHODES DE SOUS-ESPACES DE KRYLOV 33

En général, la dimension de IC, est égale à m. D'une manière plus précise, cette dimen-

sion est donnée par

dim IC, = min{m, degré du polynôme minimal de A).

De plus, ces espaces vérifient la chaîne d'inclusions

Les différentes méthodes de me Krylov proviennent des chok des sous-espaces L et de

la manière dont le système est préconditionné. Nous parlerons de la notion de précondi-

tionnement à la £in de ce chapitre, à la section 2.8. Dans ce travail, nous allons considérer

trois choix possibles pour L (que nous noterons par la suite Lm) qui nous mèneront au-

méthodes itératives les plus connues.

- Lm = Km : ceci conduira a m méthodes Fùll Orthogonalization Method (FOM) et du

Gradient Conjugué (CG) (voir respectivement sections 2.3 et 2.5).

- Lm = AIÇ, : ceci conduira aux méthodes GMRES (section 2.4) et M N R E S (section 2.6).

- Li, = K ~ ( A ~ , ro) : les méthodes de biorthogonalisation font partie de cette classe. Ce

sera le sujet de la section 2.7.

2.2 Procédé d'orthogonalisation d' Arnoldi

Ce procédé est utilisé pour construire une base orthonormale du sous-espace de Krylov

IC,(A, ro) . Il s'agit d'une méthode de projection orthogonale semblable au procédé de

Gram-Schmidt mais qui est adaptée à la structure des sous-espaces de Krylov.


Procédé dYArnoldi - Gram-Schmidt

1. Poser = ro/llroll

2. Pour j = 1, ..., m, faire :

3. Pour i = 1, ..., j, faire :

4. Calculer hi,j = (Avj, vi) i

5. Calculer wj = Auj - C hi j ~ i i=L

6. Fin

Si hj+l,j = O , alors arrêter.

Il est facile de vérifier que ce procédé conduit à une base orthonormale de K, (A , ro) .

Par contre, il est instable tout comme le procédé original de Gram-Schmidt. En pratique,

on préfère utiliser une variante comme sous le nom de procédé de Gram-Schmidt modifié

qui est moins sensible aux erreurs d'arrondi. Ce procédé est basé sur l'observation suivante

où E = (vi, va, VQ; . . . , v ~ ) ~ ~ Le. le sous-espace orthogonal au sous-espace engendré par

les j vecteurs vl à vj et Pp dénote le projecteur sur le sous-espace E. Or, ce projecteur

peut être obtenu d'une manière différente :

Ceci conduit à l'algorithme de Gram-Schmidt modifié que nous avons décrit par un pseudo-

code.

C W f l R E 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV

Procédé d'ArnoIdi - Gram-S chmidt Modifié

1. Pour V I = rc/llroll

2. Pour j = 1, ..., m, faire :

3. Calculer Wj = Auj

4. Pour i = 1, ...,j, faire :

5. hi,j = ( w j 3 v ~ )

6- wj = wj - hijvi 7. Fin

8 . hj+i j = IIwjII2 Si h j c t j = O alors, arrêter.

9 - Vj+i = wj /h j+ i j

10. Fin.

Notons qu'en arithmétique exacte ces deux algorithmes sont mathématiquement équi-

valents. Par la suite, on désignera ces procédés par l'appellation commune de procédé

d 'Arnoldi.

Nous voulons maintenant écrire le procédé d ' b o l d i sous forme matricielle. Pour ce

faire, notons d'abord par

V m = [WL> - - - 7 v m ]

la matrice orthogonale de dimension n x rn dont les vecteurs colonnes sont issus du procédé

d7Arnoldi. De plus, définissons la matrice de format (m + 1) x m

Remarquons qu'il s'agit d'une matrice de Hessenberg et notons par Hm la sous-matrice

carrée formée des m premières lignes de z,. Ainsi, on est en mesure d'écrire le procédé

d7Arnoldi sous forme matricielle :

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE KRMOV

où e, est le vecteur unitaire dont la m composante est 1. Il est facile de vériIier

ces égalités. D'après la définition de W, et en isolant Avj1 la ligne 5 de l'algorithme de

Amoldi-Gram-Schmidt devient

De plus, Ia ligne 8 du même algorithme, nous permet d'écrire que üjil = IlÜjiilllvjci et

la définition de Wm permet de dire que üj+l = hj+ij~jii d'où,

2.3 Algorithme FOM

Avec ces notations, nous sommes maintenant en mesure d'écrire une méthode de Krylov

basée sur le procédé d'hrnoldi pour les systèmes linéaires. Cette méthode porte le nom de

Full Orthogonalization Method (FOM). Il s'agit d'une méthode de projection orthogonale,

i.e. 1;, = IC, = K m ( A , rO). On cherche une solution approchée x, dans le sous-espace

affine xo + Km (A, ro) de dimension m en imposant la condition de Galerkin

Voici maintenant un bref aperçu de l'idée générale de la méthode. D'abord, on remar-

quera que tout vecteur v E Km peut s'écrire sous la forme

CHAPmRE 2- MÉTHODES DE SOUS-ESPACES DE KRYLOV 37

où y E IRm car les colonnes de V, forment une base de G. De plus, si on pose vl = $& et B = l l~o1121 on a que

V ~ A V , = H~ (2-8)

et grâce aux notations introduites plutôt,

par hypothèse et par orthogonalité de V,.

Vérifions l'équation (2.8). D'après ce qu'on a v u à l'équation (2.6); il est clair que

T AVm = V m H m + hm+l,mvrn+lem (2.9)

En mdtipliant par V: des deux côtés de (2.9)' on obtient

T V ~ A V , = V;V,H, + ~ ~ h , + l , , v , + l e ~ .

Par ailleurs, comme Vm est orthogonale vTV, = I et on trouve que

De plus, toujours grâce à l'orthogonalité de Vm, on a que V ~ V , + ~ = O. Ce qui annule le

dernier terme et on trouve halement la relation désirée

La condition de Galerkin (2.7) est équivalente à trouver y, E Rm solution de

CH-APIT1ZE 2- MÉTHODES DE SOUS-ESPACES DE KRnOV

Par conséquent, la solution approchée est donnée par la relation suivante :

Enz = 20 f V m ~ m

Nous sommes maintenant en mesure d'écrire l'algorithme :

Algorithme FOM

1. Calculer r o = b - Axo

B = I l ro l l 2

vi = TOIP 2. Définir la matrice de Hesssenberg rn x m Hm = (hi,j)i,j=l,-.-,m

Poser N, = O

3. Pour j = 1, ..., rn, faire :

4. Calculer wj = Auj

5. Pour i = 1, ...,j , faire :

6. hij = (wj, vi)

7. W j = wj - hijvi

8. Fin

9. Calculer = llwjl12

Si hjci,j = O , poser m = j et d e r à la ligne 12

10- Calculer vj+l = ~ ~ / h j + ~ , j

11. Fin

12. Calculer y, = ~ i ' ( p e ~ )


2.4 Algorithme GMRES

En plus de consulter le livre de Saad [16], on peut se référer a [17] pour en connaître

plus sur cette méthode. La méthode GMRES est une méthode de projection pour laquelle

La condition de Petrov-Galerkin relatif à ce choL~ consiste à déterminer xm E xo -I- Km

solution de

( b A A ) = O VU € Km

(Ax,, Av) = (b, Au) V v E IC,

Mais cette dernière relation correspond à la condition dioptimalité du problème de mini-

misation :

Trouver x, E xo + h& tel que

Autrement dit, cette méthode minimise la norme du résidu sur tous les vecteurs de

xo + Km- Ceci explique l'origine de l'acronyme GMRGS qui signifie Generalized Minimal

RESidual. Étant donné qu'un vecteur v de Içn s'écrit sous la forme v = V,y, on peut

projeter la fonctionnelle J sur IRm

Nous allons voir maintenant quelle est la similitude avec l'algorithme FOM (section 2.3)

en développant davantage l'expression du résidu. D'abord, il est clair que

CHAPITRE 2. *THODES DE SOUS-ESPACES DE KRYLOV

Et comme le résidu initial est donné par ro = b - Axo, on a que

b - A ( x o + V,y) = TO - AV,y.

Or, en remplaçant AV, par son expression dans (2.9)' on trouve que

b - A(xo + V ~ Y ) = Ta - ( I m H m + hm+i,mvrn+ie~)y

qui peut aussi s'écrire comme

- b - A(xo + V,y) = - VmTIHmy.

Par ailleurs, par hypothèse on a que ro = Pvl. Ainsi l'expression devient

- b - A(XO + Vmy) = Bvï - V m + i H m ~ -

De plus, il est clair que v l = Vmtlel7 d'où

- b - A(XO + Vmy) = Vm+i(Pei - Hmy)-

Et l'équation (2.10) devient

- J(Y) = IIVm+i(Bei - H m ~ ) I l 2 -

Or, comme les vecteurs colonnes de la matrice Vm+1 sont orthonormaux, on peut écrire

- J(Y) = llPe1 - Hmyll2- (2.11)

L'approximation de GMRES est donc l'unique vecteur de xo + IC, qui minimise (2.1 1).

Cette approximation est obtenue simplement comme suit :

où la notation y, = argminy J(y) signifie que y, est la solution du problème de moindres

carrés

CHAPITRE 2. ~ ~ É s H o D E S DE SOUS-ESPACES DE KRYLOV

Ceci nous donne l'algorithme suivant :

Algorithme GMRES

1. Calculer r o = b - Axa

B = Ilroll2

v1 = T O / P 2- Définir la matrice (m + 1) x m Hm = (hi,j)l<icm+l,l<icm.

Poser x, = O.

3. Pour j = 1, ..., m, faire :

4. Calculer wj = Avj

5. Pour i = 1, ..., j , faire :

6. hij = (wj , vi)

7. wj = W j - hijvi

8. Fin

Si hj+i,j = O poser m = j et aller à la ligne 12.

10. Vj+i = wj/hj+i ,j

11. Fin -

12. Calculer y, = argminy IlBel - Hmy1I2

Donnons quelques détails sur la résolution du problème de moindres carrés à la ligne

12 de l'algorithme GMRES. Pour résoudre ce problème, on effectue une factorisation QR

à l'aide des matrices de Givens (car la matrice Hm est de Heisenberg)

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE KRM;OV

- - On a noté par QmR, la factorisation complète tandis que Q,R, est la factorisation

réduite Le. -Ï2, est d'ordre m x m. On obtient

Le minimum est atteint en

Le principal inconvénient de l'algorithme GMRES provient du fait qu'il faut garder en

mémoire toutes les directions de descentes Le. la matrice V,. Ceci devient prohibitif si

m augmente constamment. Pour pallier à ce défaut, on préfère fixer un nombre maximal

m de directions de descente et de recommencer l'algorithme a tous les m itérés. Cette

variante porte le nom de méthode GMRES (m) .

Résultats de convergence

Par la suite, nous allons exposer sans preuve quelques résultats connus sur la conver-

gence de GMRES. On peut trouver les démonstrations dans le livre de Saad [16].

Théorème 5 S i A est une matrice définie positive, alors la méthode GMRES(m) converge

pour tout m > 1.

Théorème 6 Soit x, la solution approchée obtenue à la dème étape de l'algorithme

GMRES et soit r, = b - Asm le résidu associé. Alors, z, est de la forme

où q, est un polynôme de degré rn et

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV 43

Théorème 7 Supposons que A est une matn'ce diagonalisable e t posons A = XDX-'

où D = diag{AL, X2, ..., A,) est la matrice diagonale des valeurs propres. Définissons

@) = max Ip&) 1. Alors, la nonne du résidu donnée à la m p ~ P , , p ( O ) = l i=L---,n

étape de

GMRES satisfait l'inégalité

où le nombre 6 = IIX11211~-1112 défini le conditionnement de la matrice X .

I c-a

FIG. 2.2 - Ellipse E(c , d, a)

Théorème 8 Soit A une matn'ce diagonalisable. Supposons que toutes les valeurs propres

de A sont localisées sur l'ellipse E(c, d , a) qui exclut l'origine et qui est ilhstrée à la figure

2.2. Alors, la norme du résidu calculée à l'étape m de GMRES satisfait l'inégalité :

où Ck est le polynôme de Chebychev de première espèce de degré k i-e.

C&) = cos[k cos-'(t)] pour - 1 5 t 5 1.

2.5 Algorithme du Gradient Conjugué

La méthode du Gradient Conjugué (CG) est la méthode itérative la mieux connue

pour la résolution des systèmes linéaires dont la matrice associée est creuse, symétrique

CHAPlTRG 2. MÉTRODES DE SOUS-ESPACES DE KRYLOV 44

et définie positive. Cette méthode fut proposée par Hestenes et Stiefel en 1952 [IO]. À

l'origine, la méthode était considérée comme directe puisqu'après n itérations, elle doit (en

principe) produire la solution exacte. Malheureusement, ce n'est pas le cas en arithmétique

flottante et par conséquent cette méthode fut abandonnée pendant plusieurs décennies.

Ce n'est qu'autour de 1970 qu'on a découvert les bonnes propriétés de convergence de

l'algorithme.

Il existe plusieurs façons d'obtenir la méthode CG. En particulier on pourra consulter le

livre de Ciarlet [5] pour une approche plus classique. Dans ce qui suit, nous allons montrer

que l'algorithme CG n'est rien d'autre qu'une simplification de l'algorithme FOM (traité

à la section 2.3) sous l'hypothèse que A est symétrique et définie-positive.

Il s'agit de nouveau d'une méthode de. projection orthogonale pour laquelle

En premier lieu, on remarque que le procédé dY-4rnoldi se simplifie grandement si on

suppose que la matrice A est symétrique. En effet, nous savons que

est une matrice symétrique et de Heissenberg. Par conséquent, Hm est tridiagonale (d'où

le nouveau nom Tm)

Tm = Hm =

où ai = hsi et ,8i = hi-l,i = Nous pouvons maintenant écrire le procédé d7Arnoldi

pour les matrices symétriques. Cette simplification de la méthode d'Arnoldi porte le nom

de procédé de Lanczos.

CHAPITRE 2. A ~ É T ' D E S DE SOUS-ESPACES DE K R n O V

Procédé de Lanczos

1. CalcuTer ro = b - Axo

8 = I I ~ o l l *

v1 = ~ 0 l P

2. Pour j = 1, -.-, m, faire :

3. Calculer W j = Avj - Djvj-*

Si j = 1, poser ,BLvo = O

4- CXj = (wj ,v j )

5. W j = W j - QjVj

IIwjll2

, aller à la ligne 8.

La solution approchée de Ia méthode FOM à l'étape m s'exprime comme suit

où y, est donné ici dans le cas où A est symé t~que d'où y, = ~ i ' ( ~ e ~ ) ) et ,B = I1roU2-

L'application de la relation matricielle correspondant au procédé de Lanczos (équation

(2.6)) fournit la relation

Donc


e t par (2.12)

De ceci, on en tire l'importante conséquence que les résidus obtelius dans la méthode

CG sont orthogonaux entre eux. Pour obtenir L'algorithme du Gradient Conjugué, nous

procédons comme il est fait dans le livre de Saad [16]. Pour ce faire, nous devons premiè-

rement écrire la factorisation LU de la matrice Tm : Tm = L,U, qui nous permettra

de modifier l'expression (2.13) de la solution approchée. La matrice Lm est bidiagonale

inférieure de la forme

et la matrice Um est bidiagonale supérieure de la forme

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE K R n O V

et

Cette factorisation nous permet de réécrire (2.13) de la façon suivante

Pour simplifier la notation, posons Pm = V,U; et zm = &~'pel. La solution approchée

est donc donnée par

xm = 2 0 + Pmxm. (2.15)

cause de la structure particulière de la matrice Um; Pm peut être mise à jour plus faci-

lement. En effet, en écrivant explicitement les dernières colonnes de la relation matricielle

PmUm = V,, on trouve que

et puisque par définition de U , u=,m = O pour i = 1, ..., m - 2, ~ ~ - 1 , ~ = Pm et a,,, = rl,,

on peut écrire

Étant donné que v, est proportionnel à (par (2.14)), on en déduit que le vecteur

p, est une combinaison linéaire des vecteurs p,-, et T,+ En normalisant le vecteur p,,

on en déduit que

Pm = Tm-1 + 6m~m-1 (2.16)

où 6, est une constante qui sera déterminée plus loin.


Par ailleurs, une décomposition par blocs de Lm permet d'écrire

et çi étant la i"me composante du vecteur 2,. La dernière égalité nous permet de dire

que Cm = -ArnÇm-~ et par conséquent, on a que

Or, comme xo + P m - l X m - l = par (2.15) on trouve finalement que x, peut être

m i s à jour à chaque étape de la façon suivante :

Finalement, montrons que les directions de descentes pi sont A-conjuguées, i-e. (Ap,, p j ) =

O Vi # j. En effet, évaluons

qui est une matrice triangulaire inférieure et symétrique, donc diagonale.

CHAPITRE 2. MÉTIIODES DE SOUS-ESPACES DE KRnOV

Résumons la situation. Nous avons obtenu les différentes relations :

1. Les résidus sont orthogonaux entre eux : (ri' vj) = O tii # j (voir (2.14)).

2. Les directions de descentes sont A-conjuguée : (Api,pj) = O Vi # j.

3. = Xi + yip, (voir(2.17)).

4- ri+l = ri - yiApi.

5. pi+l = + 6ipj (voir(2.16)).

La relation 4 est obtenue en multipliant l'équation 3 par -A et en ajoutant le vecteur

b des deux côtés de l'égalité. Pour déduire l'algorithme du Gradient Conjugué, il d t

d'imposer les relations 1 et 2 d'orthogonalité et de conjugaison.

En effet, on peut évaluer le coeficient yi grâce à la relation :

( i l , ) O = (ri ; ri)

( A P ~ > ri)

Or ri = pi - &-Lpi-l. Donc

Ce qui fournit la valeur de -/i

qui est bien définie puisque la matrice A est supposée définie-positive. De même, on peut

calculer 6i par la relation :

Ce qui nous donne

En rassemblant toutes ces informations, on peut maintenant écrire l'a,lgorithme du

Gradient Conjugué.


Algorithme du Gradient Conjugué

1. Calculer ro = b - Axo et poser po = r o

2. Pour j = O, 1, ..., jusqu'à ce qu'il y ait convergence, faire :

3. % = ( y j j ~ j ) I ( & j t p j )

4- Xj+i = X j + O!jpj

5. T j + i = T j - q A p j

6- = (r j+~l r j + l ) / ( r j , y j )

7.

8. Fin

Résultats de convergence

D'abord, rappelons la notation suivante *

et citons sans démontrer quelques résultats de convergence pour l'algorithme CG (voir

[16] pour les démonstrations).

Théorème 9 Soit x, la solution approchée obtenue à l'étape rn de l'algorithme du Gra-

dient Conjugué et soit

où x. est la solutàon exacte. Alors, x, est de la forme

où q, est un polynôme de degré rn - 1 tel que


Théorème 10 Soi t x, la solution approchée obtenue à l'étape rn de l'algorithme du Gra-

dient Conjugué e t z, est la solution exacte. Dé jn i s sons

Alors, -.

o ù Cm es t le polynôme de Chebychev de première espèce de degré rn i-e.

Cm@) = cos[mcos-'(t)] pour - 1 5 t 5 1.

En faisant les substitutions appropriées, o n obtient le résultat équivalent suivant :

où K = iz," est le conditionnement de la matrice A.

2.6 Algorithme MINRES

A la section précédente, nous avons obtenu la méthode du Gradient Conjugué comme

cas particulier de l'algorithme FOM lorsque la matrice du système est symétrique et définie

positive. Nous allons maintenant voir qu'il est possible d'appliquer le même raisonnement

a partir de l'algorithme GMRES. La nouvelle méthode ainsi déduite portera le nom de

MINRES ou encore CR pour Résidu Conjugué. On rappelle que GMRES (voir section

2.4) est une méthode de projection où IC, = K(A, ro) et Lm = A G . La solution est

caractérisée par

où V, est la matrice dont les colonnes forment la base orthogonale donnée par le procédé

de Lanczos (voir section 2.5) car la matrice est considérée comme symétrique. On adoptera

les mêmes notations qu'a la section précédente pour la matrice Tm de Heissenberg qui est

C W I T R E 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV 52

tridiagonale ainsi que la matrice étendue Tm. La solution approchée donnée à la ligne 12

de l'algorithme GMRES devient donc

A paztir de la factoris&ion QR introduite à la section 2.4 portant sur la méthode

GMRES, on a Tm = Q,&. Posons V, = Pm& afin de simplifier la remise à jour de

la solution approchée x, (comme nous l'avons fait pour déduire l'algorithme CG à partir

de la méthode FOM à la section 2.5). En effet, d'après ce qu'on a fait pour la méthode

GNIRES, on a que

x, = x0 + V , R ; ~ ,

où g, = ~ z ( ~ e l ) . On verra par Ia suite que les vecteurs colonnes de Pm sont en fait des

directions de descentes.

Dans un premier temps, montrons que ces vecteurs sont orthogonaux entre eux. Pour

y parvenir, il s&t de montrer que P ~ P , est une matrice diagonale. L'orthogonalité de

V, foutnit la relation

Or la matrice de l'extrême droite (RG~K') est symétrique et triangulaire supérieure.

Par conséquent, elle est diagonale.

En deuxième lieu, montrons que les vecteurs résidus sont A-conjugués entre eux Le.

(Ari, rj) = O b'i # j. Cette propriété particulière explique l'appellation CR ou méthode

du Résidu Conjugué parfois donnée à cet algorithme. En effet, selon l'interprétation de

l'algorithme GMRES comme méthode de projection, on a que

CHAPITRE 2. METHODES DE SOUS-ESPACES DE KRYLOV 53

Choisissons les indices i < j. On a que xi = xo + ui E xo + & et T~ = b - Axi =

TO - Aui E c Kj- On en déduit que

Montrons que les vecteurs pm forment des directions de descente de l'algorithme.

D'abord, il est facile de montrer que g, satisfait la récurrence (on consultera le livre

Une décomposition de (2.20) par bloc conduit à

X m = XO + P m - l g m - I f Ç m ~ m .

Donc, xm peut être mis à jour à chaque étape de la façon suivante

Résumons la situation.

1. Les résidus sont A-conjugués : (Arii ~ j ) = O V2 f j.

2. Les directions de descentes sont orthogonales entre elles : (pi, pj) = O Vi # j.

3. Xi+l = Xi i Tipi (voir (2.21)).

4. Ti+l = ri - y i A p i -

5. pitl = ri+i + &pi.

6 . Ti+l I Apj v j 5 i.

CHAPITRE 2- MÉTHODES DE SOUS-ESPACES DE KRYLOV 54

Notons que les propriétés 1 et 2 sont les duales de celles de l'algorithme du Gradient

Conjugué. La propriété 4 est une conséquence directe de la relation 3. La propriété 5

découle de l'écriture de la dernière ligne du système Pm& = V, et du fait que v, est

proportionnel à r,-~ (voir section 2.5).

Quant à la dernière propriété, elle se déduit de la manière suivante. Étant donné que

xj Fi xo + Kj et que Kj C Kj+i, les directions de descentes satisfont la relation

Or, par défmition de GMRES, nous avons que I AGtl , d'où la propriété 5 ci-

dessus. Maintenant, nous sommes en mesure d'écrire l'algorithme MINRES. Pour cela, il

suffit d'imposer les relations d'orthogonalité et de conjugaison. En effet, on peut évaluer

le coefficient yi en combinant les relations 4 et 6 :

d'où la valeur

Or, grâce awc relations 5 et 6, on a

Ce qui nous fournit la valeur définitive

Par ailleurs, en isolant Apj dans la relation 4, on a

et on obtient grâce à la relation 6

CHAPITRE 2- MI?EWDES DE SOUS-ESPACES DE KRYLOV 55

Maintenant en appliquant la relation 5, on peut réécrire ce produit scalaire de la façon

suivante

En remplaçant (2.23) dans (2.24): on trouve finalement que :

Or, Tj+l est A-conjugué à T j , donc on a :

et par (2.23), on obtient :

Finalement, la relation (2.22) nous donne :

En rassemblant toutes ces informations, on peut maintenant écrire l'algorithme MINRES.

C W I T R E 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV

Algorithme MINRES


Poser p, = 7-0

2. Pour j = 0'1, ..., jusqu'à ce qu'il y ait convergence, faire :

3. Tj = ( ~ j , Arj)/(Apj7 &Pi)

4, X j + r = Xj + TjPj

5. Tj+i = T j - y jApj

6- 6j = (vj+l) Arj+l)/(rj7 Arj)

7. Pj+i = rj+i -k bjpj

8- C a l c ~ l e r A ~ ~ + ~ = A ~ ~ + ~ + b ~ A ~ ~

9. Fin

2.7 Algorithmes de biorthogonalisation

Les méthodes de biort;hogonalisation sont des méthodes de type Krylov basées sur

l'algorithme de biorthogonalisation de Lanczos. Ce sont des méthodes d'orthogonalisation

non-orthogonales et l'analyse théorique de ces méthodes n'est pas évidente.

La méthode de biorthogonalisation que nous allons considérer est le procédé de bior-

thogonalisation de Lanczos qui s'applique aux matrices non-symétriques et qui est décrite

dans [El. C'est l'analogue du procédé dJArnoldi dans le cas de l'orthogonalisation. Dans

cet algorithme, on construit une paire de bases biorthogonales pour les deux sous-espaces

m-1 Km(A,vl) =< vl, Aul, ..., A >

G ( A ~ , =< W ~ , A ~ W ~ ) ..., ( A ~ ) ~ - ~ w ~ > .

En considérant le système Ax = b où A est une matrice non-symétrique d'ordre m,

l'algorithme de biorthogonalisation de Lanczos est le suivant :


Algorithme de biorthogonalisation de Lanczos

1. Choisir deux vecteurs vl et wl tels ques (vl, w l) = 1

2. Poser pl =JI = O 'wg = v0 = O

3. Pour j = 0,1, ..., m, faire :

Notons que les deux paramètres Pjci et bjcl peuvent être choisis de différentes ma-

nières pour que ( v ~ + ~ ; wjc1) = l. Ces paramètres doivent également satisfaire l'égalité

Bj+iJj;i = (Ûj+l, uj+i).

Par la suite, nous aurons besoin de la matrice suivante :

Cette matrice est en fait la projection de la matrice A obtenue par un procédé de pro-

jection oblique sur le sous-espace IC,(A, etl) et orthogonale au sous-espace I C , ( A ~ , pul).

De même, on a que la matrice T: est la projection de la matrice obtenue par un pro-

cédé de projection oblique sur le sous-espace I C , ( A ~ , wi ) et orthogonale au sous-espace

Km (A, vl). Ainsi, les opérateurs A et A~ jouent un rôle dual puisque des opérations

similaires peuvent être effectuées sur eux


Nous allons maintenant décrire la méthode du Gradient BiConjugué (BCG). Cet al-

gorithme dérive du procédé de biorthogonalisation de Lanczos. Il s'agit d'une méthode

de projection sur IC, =< vl , Aul, ..., A ~ - ' V ~ > orthogonale au sous-espace Lm =< T ml , A w l , ..., ( A ~ ) ~ - ' W ~ >- Nous posons toujours ui = ro/llrol12 Le vecteur wl est

souvent égal à V I . En procédant comme nous l'avons fait pour dériver la méthode du

Gradient Conjugué de l'algorithme FOM, nous pouvons déduire l'algorithme du Gradient

BiConjugué à partir du procédé de biorthogonalisation de Lanczos. Dans cet algorithme,

rj et r; sont respectivement dans la même direction que vj+l et W j + l et ils forment une

suite orthogonale.

Algori thme du Gradient BiConjugué

1. Calculer ro = b - Axo

Choisir ri tel que (r0, ri) # O .

2. Poser po = ro

p; = rg

3. Pour j = 1, ... , jusqu'à ce qu'il y ait convergence, faire :

4. aj = (rj, r;)/(Apjl P;)

5. xj+l = Xj -k +jPj

6. Tj+i = T j - a j A p j

7. T,'+~ = - a j ~ T p ;

8. Pj = (y j i -1 , r;+dI(rj, r;)

9. Pj+i = r j i -1 f Pj+ipj

IO. P;+I = r&i+ B j + i ~ ;

11. Fin

Notons que les vecteurs produits par cet algorithme satisfont les propriétés suivantes :

(rj, r,') = O pour i # j (Apj, pt) = O pour i # j.

C W I T m 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV

On remarque qu'à chaque étape de l'algorithme BCG, on doit faire deux produits

matrice-vecteur, un avec la matrice A et un avec la matrice transposée A ~ . De plus, le

vecteur p,? généré avec sert à obtenir les scalaires q et wj mais ne contribue pas direc-

tement a la solution. On pourrait donc penser à éliminer le calcul de la matrice transposée

( A ~ ) dam l'algorithme. C'est pour cette raison que des algorithmes portant l'appellation

"transpose-kee" ont été développés dans les années 1980. Les deux algorithmes qui suivent

font partie de cette catégorie.

Ainsi, pour éviter l'utilisation de la matrice transposée de A dans l'algorithme BCG et

pour obtenir une convergence plus rapide pour le même coût, Sonneveld [18] a développé

en 1984 l'algorithme Conjugate Gradient Squared (CGS). Voyons comment on peut y

arriver en partant de l'algorithme BCG. Dans cet algorithme, le résidu à l'étape j peut

s'écrire comme

T j = 4j(A)r~

où 4j est un certain polynôme de degré j satisfaisant la contrainte dj(0) = 1. De même,

on peut écrire

Pj = rj(A)r0

où 7ij est un polynôme de degré j . Toujours d'après l'algorithme BCG, on peut définir des

relations semblables pour T; et p: :

Par conséquent, le scalaire de l'algorithme BCG est donné par

CHAPITRE 2. ~/~I?THODES DE SOUS-ESPACES DE KRYLOV 60

Avec la réécriture des vecteurs r j , r;, pj et p,l, on peut réécrire la ligne 6 de l'algorithme

BCG comme suit :

4j+l(A)y0 = $ j ( A ) ~ o - a jA?(A) r~ - (2.25)

On peut kalement éliminer ro des deux côtés de l'équation pour obtenir :

De même la ligne 10 de l'algorithme BCG nous donne la relation suivante :

Puisque ro est commun aux trois termes, on peut écrire :

L'idée de Sonneveld est de développer un algorithme (CGS) qui donnera une séquence

d'itérés dont la norme du résidu T> devront satisfaire

ri = $;(A)T~

où TO est le résidu initial dans l'algorithme BCG. Pour y parvenir, on éleve d'abord au

carré les équations (2.26) et (2.28), on trouve que :

D'après (2.28), on peut remplacer rj(A) et (2.29) devient

4;+i = 4; - 2ajA(+j + fljBj_i~j-l)4j + ojA 2 2 2 9-

En distribuant, on trouve :

4Ll = 4; - 2ajA4,' - 2 ~ t ~ , 6 ~ - ~ A ~ ~ - i 4 ~ + +?A2r:.

C m I T R E 2, ~~ÉTHODES DE SOUS-ESPACES DE KRYLOV

Finalement, en mettant en évidence a j A , on obtient la relation de récurrence suivante :

$Li = 4; - ~ ~ ~ ( 2 4 ; + 2,8 j - l~j - l$ j - Q~AT?)- ( 2 -31)

D'après (2.28), on peut remplacer rj et alors $jj?rj est donné par

6jrj = 4j(4 j + P j - l ~ j - 1 )

et en distribuant, on obtient :

$ j r j = 4; + p j - l ~ j - ~ $ ~ .

En laissant tomber les arguments des fonctions dans (2.26) et en multipliant cette

équation par T j , on trouve :

2 = =jrj - O L ~ A ~ .

En remplaçant maintenant 6jTj par (2.32) dans cette équation, OR trouve :

2 #j+lîrj = 4; + ,8j-i7ij-i@j - ajArj

Les équations (2.31), (2.33) et (2.30) sont les relations de récurrence de base de l'algo-

rithme CGS . Définissons quelques termes :

Ainsi, les relations de récurrence deviennent :

CHAPITRE 2. METHODES DE SOUS-ESPACES DE KRYLOV

Avec ces notations, aj devient :

De la même manière, on trouve que

On peut simplifier encore les expressions en posant

Ainsi, qj devient

En rassernbiant toutes ces équations, on trouve l'algorithme CGS.

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE I(-RYZOV

Algorithme Conjugate Gradient Squared

1. Calculer ro = b - Azo

Choisir r: arbitrairement.

2. Poser p, = u, = r ,

3. Pour j = 1, ..., jusqu'à ce qu'il y ait convergence, faire :

4. = ( ~ j , r ; ) / ( A p j ; T G ) 5- qj = U j - a jApj

6. X j + i = X j + to?j(uj + q j )

7. P j + l = rj - ajA(uj + q j )

8- D ~ = ( T ~ + I ~ ~ ~ ) / ( T ~ , T ~ ) 9 . uj+l = r j + ~ + P j q j

IO. P j + i = U j + i 4- P j ( q j + P j ~ j )

Il. Fin

Dans cet algorithme, il y a deux produits matrice-vecteur avec la matrice A à chaque

étape. De plus, les erreurs d'arrondis sont plus importantes que dans l'algorithme BCG

puisque les polynômes sont élevés au carré. C'est pour remédier à cette difficulté qu'une

variante de l'algorithme CGS a été développée. Il s'agit de l'algorithme BIConjugate

Gradient Stabilized (BICGSTAB) qui fut développé par van der Vorst [21]. Au lieu de

donner un vecteur résidu de la forme T: = d!(A)rO, l'algorithme BIGCSTAB produit des

itérations qui conduisent aax vecteurs résidus de la forme

où $j(A) est le polynôme associé à l'algorithme BCG et &-(A) est un nouveau polynôme

qui est défini à chaque étape dans le but de stabiliser la convergence de l'algorithme

original (CGS).

CHAPITRE 2. THO ODES DE SOUS-ESPACES DE KRYLOV

Le polynôme est défini par la relation de récurrence suivante :

où wj est un scalaire à déterminer. Ainsi, on trouve que

et en rernplçant $jM par (2.26), on obtient :

De même, il est possible d'écrire une relation de récurrence pour $j7ij en utilisant la

relation (2.28) :

'$'jrj = '$'j (6j Pj-irj-1)

En remplaçant @j par la relation de récurrence dans le deuxième terme de l'équation, on

trouve :

$jrj = $j#j + pj-l(I - ~ j - ~ A ) $ j - l ~ j - ~ - (2.36)

Définissons maintenant

D'après (2.35)' on a que

T j t ï = ( I - ~ j A ) + ~ ( # i - a i A ~ j ) ~ o

r j + ~ = (1 - w j A ) (1Cj4j - - j A + j ~ j ) ~ ~

T j t i = (1 - wjA) (vj - ajApj)

et d'après (2.36), on a que

CHAPITRE 2. ~~LÉ%ToDEs DE SOUS-ESPACES DE KRYLOV

Malheureusement, on ne peut pas calculer pj de cette façon car le vecteur 4 j ( A ) 2 ~ o

n'est pas disponible. On peut cependant considérer la relation suivante :

pj = ( y j , T:) .

Pour voir la relation entre pj et &, nous avons besoin de développer explicitement $ j (A)~8

b-1) (AT) j-'Tt + ) P j = ((Q (A)To i qp) (AT) jy8 + 172 ... .

Puisque C#~(A)T~ est orthogonal à tous les vecteurs ( A ~ ) krs, avec k < j , il ne reste que

le terme dont le degré est le plus élevé du côté droit du produit scdaire :

où n t ) est le coefficient dominant de 4jj. En simplifiant cette dernière équation, on trouve :

CHAPITm 2. MÉTHODES DE SOUS-ESPACES DE KRYLOV 66

En examinant les relations de récurrence (2.25) et (2.34), on trouve facilement les rela-

tions suivantes en consemant seulement les coefficients dominants :

Pax conséquent, on trouve que

par déhit ion de pj et en remplaçant #C1) et ') par les valeurs qu'on vient de trouver,

on obtient : di) 0') pj-f-i -wjqi 'Yi Pj+l -- -

P;- -aj?'l di) -737 71

D'où, on peut conclure que

e t par définition de pji cette équation est équivalente à

En procédant de la même manière, nous pouvons trouver une expression pour aj. Par

définition, on a que

aj = (4j(A)r0i $j(AT)G) (Arj (A) ~0 rj ( A ~ ) T; ) '

De plus, le coefficient dominant de q+l et #j+l sont les mêmes d'après la relation de

récurrence (2.27). Ainsi, on trouve que

CHAPITRE 2. MÉTHODES DE SOUS-ESPACES DE KRYLQ)V

Et puisque pj = hq, il suit que

Par ailleurs, wj est choisi de façon à minimiser la norme h de

.Ahsi, r j+i devient :

Et la valeur optimale pour mj est alors donnée par

Il nous manque maintenant la relation qui nous donne y+'. Cette dernière peut être

obtenue en réécrivant r j + i de la manière suivante en remplaçanrt s j :

Tj+' = î j - a j A p j - w j A s j -

D'où, par définition du résidu, on trouve :

Finalement, en soustrayant b des deux côtés et en multipliant pax A-' on trouve l'expres-

sion recherchée :

Cette dernière équation nous permet d'écrire l'algorithme suivant.


Algorithme BICGSTAB

1. Calculer r o = b - Azo

Choisir rg arbitrairement.

2. Poser p, = r o

3. Pour j = 1, ..., jusqu'à ce qu'il y ait convergence, faire :

4. aj = (r j , r;)/(Apj, Tg)

5- S j = T j - %Apj

6. wj = (Asj, sj)/(Asj, Asj)

IO. Pj+i = rj+i + Bj(pj - wjAp j )

11. Fin

2 -8 Préconditionnement

On traite du préconditionnement dans les chapitres 8 et 9 du livre de Saad [16] qui est

le principal ouvrage de référence pour le chapitre 2.

2.8.1 Généralités sur le préconditionnement

Un préconditionneur peut être défini comme une approximation du solveur qui est

associé a une méthode itérative de type Krylov. Ainsi, on peut dire qu'un préconditionneur

est une forme de modification implicite ou explicite du système linéaire original qui le rend,

dans un certain sens, plus facile à résoudre par une méthode itérative donnée. Le système

résultant peut être résolu par une méthode de m e Krylov et doit converger en moins

d'étapes que le système original.

CHAPITRE 2. &THODES DE SOUS-ESPACES DE K R n O V

Ainsi, considérons toujours le système

où A est une matrice inversible d'ordre n. Soit M, une matrice inversible d'ordre n, alors

le système

M - I A X = M-lb

admet la même solution que le système précédent et M est appelée la matrice de précon-

ditionnement. II y a trois types de préconditionnement : à gauche, à droite et les deux (le

préconditionnement à gauche et à droite). On dit d'un système qu'a est préconditionné à

gauche si le système original est transformé sous la forme :

De même, M est une matrice de préconditionnement à droite si le système transformé

s'écrit sous la forme :

AM-^^ = 6.

Dans ce cas, on obtient la solution en posant x = M-ly. Pour obtenir le précondition-

nement à gauche et à droite, il s'agit de combiner ces deux types de préconditionnement.

Pour ce faire, nous avons besoin de deux matrices inversibles : MG et M D . Le système

s'écrit alors sous la forme :

M ~ ~ A M ; ~ ~ = M,%.

Par exemple, ce type de préconditionnement est particulièrement utile d m le cas où

la matrice A du système onginal est symétrique et défmie positive. En effet, avec ce

type de matrice, on opte généralement pour l'algorithme du Gradient Conjugué et un

préconditionnement à gauche (ou à droite) détruirait la symétrie du système.

2.8.2 Algorithmes de type Krylov précondit ionnés

Comme nous venons de le voir, lorsqu'on désire utiliser le préconditionnement avec les

méthodes itératives, il y a trois façons de procéder : on peut préconditionner à gauche,

CHAPITRE 2. MÉTRODES DE SOUS-ESPACES DE KRYLOV 70

à droite ou combiner les deux à Ia fois (préconditionnement à gauche et à droite). Pour

la description détaillée des méthodes de Krylov préconditionnées décrites plus loin, nous

nous attarderons seulement sur le préconditionnement à gauche.

GPI/I[RES préconditionné

Considérons le système linéaire Ax = b préconditionné par la matrice M. Par déihition,

l'algorithme GMRES préconditionné est la méthode GMRES appliquée au système

Le résidu préconditionné correspondant à un vecteur initial $0 est défini par

Dans le cas où le préconditionnement à gauche est utilisé, le sous-espace de Krylov cor-

respond à

CHAPITRE 2. MZTHODES DE SOUS-ESPACES DE KRYLOV

Algorithme GMRES préconditionné à gauche

1. Calculer r o = M-'@ - Alo)

8 = I l r o l l 2

v1= TOIP 2 . Pour j = 1, .,., m, faire :

3. Calculer w = M-'Av~

4. Pour i = 1, .--,j, faire :

5. hij = (w, vi)

6 . w = w -hijvi

'7. Fin

8. Calculer hj+i = Il w 1 I2 vj+i = w/hj-+i,j

9. Fin .

10. Poser V, = [al, ..-, v,] - H m = {hi, j}I<=i<=j+I;l<=j<m

- 11. Calculer y, = a ~ g m i n ~ llPel - Hmyllz

Xrn = 20 f V m ~ m

12. Si le critère est satisfait, arrêter ici.

Sinon, poser ECO = xm et aller à la ligne 1.

Gradient Conjugué préconditionné

Comme il en a été question à la sous-section 2.6.1, nous ferons face ici à un problème

de symétrie avec le préconditionnernent à gauche. La méthode du Gradient Conjugué est

utilisée lorsque la matrice A du système à résoudre est symétrique et d é f i e positive.

Comme la matrice de préconditionnement M doit être aussi près que possible de la

matrice A, M est aussi symétrique et définie positive. Or, cela ne garantie pas que le

système préconditionné à gauche M-'AX = M-% sera symétrique.

C W I T R E 2. MÉTRODES DE SOUS-ESPACES DE KRYLOV 72

En effet, en général, la symétrie n'est pas conservée. Dans ce cas, il faut donc utiliser le

préconditionnement à gauche et à droite. Pour ce faire, la matrice de préconditionnement

M est issue d'une factorisation de Cholesky Le. M = L L ~ . Dans ce cas, le système à

résoudre est de la forme L - ' A L - ~ ~ = L-'b où z = L - ~ ~ et la matrice L-'AL-~ est

une matrice symétrique définie positive.

Algorithme du Gradient Conjugué préconditionné


To = L - ~ T ~

p, = L-%~

2. Pour j = 0,1, ..., jusqu'à ce qu'il y ait convergence, faire :

3. 0l.i = (%> j ) / (Ap j , pj)

4. x j t l = Xj f ajpj

5. PjCl = % - O r i ~ - l ~ p j

6- Pj = (ej+13 ej+l)/(Fj, Fj)

7. -T - Pjri = L rj f 1 + Bjpj

8. Fin

Or, on peut remarquer que l'opérateur M-'A est auto-adjoint pour le M-produit sca-

laire i.e. que (M-'AX, y)M = (x, M - ~ A ~ ) ~ . Par conséquent, en remplaçant le produit

scalaire usuel par le M-produit scalaire dans I'algonthme du Gradient Conjugué précon-


ditionné, la symétrie est conservée et l'algorithme devient :

1. Calculer ro = b - Axo

zo = M-'ro

Nous présentons maintenant la version préconditionnée de l'algorithme MLNRES décrit

à la section 2.6. Nous avions alors mentionne que cet algorithme s'applique aux systèmes

symétriques. Nous faisons donc face à un problème de conservation de la symétrie lors

du préconditionnement comme c'était le cas pour l'algorithme CG. Pour conserver la

symétrie en préconditionnant, nous utilisons la même idée que précédemment Le. on utilise

le M-produit scalaire au lieu du produit scalaire usuel. L'algorithme qui en résulte est le

suivant :


Algorithme NIlINRES préconditionné

1. Calculer ro = b - Arco

Poser z o = M-'rO

Po = Zo

2. Pour j = 0 , 1 , ..., jusqu'à ce qu'il y ait convergence, faire :

3. aj = (rj) A % j ) / ( A p j , A p j )

4. xj+l = X j + OrjPj

5 - Tj+l = T j - %A%

6- Z j+ i = M - ' T ~ + ~

7- P j = ( r j + i Azj+l) ( y j , Azj)

8. - Pj+i - %j+i f Bjpj

9 . Calculer A P ~ + ~ = Arjcl + PjApj

10. Fin

Pour clore ce chapitre, nous écrivons l'algorithme BICGSTAB préconditionné à gauche.

Cet algorithme est utilisé pour résoudre des systèmes non-symétriques et son intérêt vient,

entre autre, du fait qu'il est plus économique que GMRES. Il en sera question lorsqu'on

discutera des algorithmes choisis lors des simulations numériques à la section 3.1.2 du

prochain chapitre.

CHAPITRG 2. -THODES DE SOUS-ESPACES DE KRYLOV

Algorithme BICGSTAB préconditionné

1. Calculer r o = M-'(b - Axa)

Poser p, = 7-0

2. Pour j = 0,1, ..., juçqu'à ce qu'il y ait convergence, faire :

3. = ( ~ j , T ~ ) / ( M - ' A ~ ~ ) T G ) 4. S j = T j - a j M - l ~ p j

5- 9 = ( M - ~ A S ~ , s j ) / (As j ) Asj) 6 - xj+l = xj + % p j + w j s j

7. Tj+l = Sj+ l - w j M - l A s j

8. - (T -;1,7") 4- - (+j,r;y uj

9. - ~ j + i - T j + l + Bj kj - w j ~ - ' ~ p j )

10. Fin

Chapitre 3

Résolution numérique du problème de

Stokes

3.1 Méthodes itératives de résolution du problème de

Stokes

En suivant les notations du chapitre 1, on introduit les espaces fonctionnels fiés au

problème de Stokes : V = (3ti(C2))3 et Q = t'(O). Étant donné une condition aux limites

de type Dirichlet sur la vanable vitesse, i.e. ulr = uo, on peut prolonger cette fonction

dans tout le domaine pour obtenir une fonction ua E ('?7!1(fl))3. Comme nous le donne

l'équation (1.16) du chapitre 1, la formulation variationnelle du problème de Stokes s'écrit :

Trouver u vérifiant u - u0 E V et p E Q tels que

Dans la pratique, on résout plutôt la forme correctionnelle associée à ce problème. Étant

donné la l i n é a ~ t é de l'équation, cela consiste à faire une seule itération de la méthode

CHAPITRE 3. RÉSOLUTION NUMÉRIQUE DU PROBLÈME DE STOKES 77

de Newton. Ainsi, à partir d'une solution initiale ( u o , p o ) , on doit calculer la correction

(bu; bp) E V x Q satisfaisant

27701n €(bu) : E(V) d x - J , b p divv dx =S, f - V dx + Jnpo div v dx - 2q0 ln e(uo) : E(V) dx

SQq div bu dx = -J,q div uo dx

La solution désirée correspond à

Par la suite, tous les problèmes considérés seront résolus en correction. Par conséquent,

pour ne pas alourdir inutilement les notations, nous désignerons la correction (6u ,6p) par

(u: P) -

3.1.1 Généralités sur les techniques de résolution du problème de

Stokes

Rappelons que pour le problème de Stokes, nous avions introduit au chapitre 1 (sec-

tion 1.3) les deux sous-espaces de discrétisation de dimension finie Vh C V et Qh C Q. Si

{vi)iN,, est une base de Vh et {qi)gl une base de Qh, le problème de Stokes est équivalent

au système linéaire suivant :

où u est formé des composantes de uh sur la base {vi)b1 mises en colonne et p est formé

des composantes de ph sur la base Iqi)E1 mises en colonne et

Bq = -Jnqi div vj dx i = 1 ,..., M j = 1,--.,IV

CHAPITRE 3. RÉSOLUTION NUMÉRIQQUE DU PROBLÈME DE STOKES

Le problème de Stokes revient donc à résoudre un problème de point de selle. Le la-

grangien correspondant est

Il y a plusieurs difficultés associées à la résolution du problème de Stokes, en voici

quelques unes :

1. Malgré le fait que la matrice A soit symétrique et déh ie positive, le système global

demeure symétrique mais indéfini.

2. Il y a la présence d'un bloc diagonal nul. Ce qui a pour conséquence qu'un pivot nul

peut être rencontré lors d'une résolution par une méthode directe.

3. Il faut aussi tenir compte que la pression est unique à une constante près. Cela

dépend grandement des conditions aux limites. Par exemple, pour des conditions de

type Dirichlet seulement, la matrice globale est singulière.

4. Finalement, avec les conditions aux limites appropriées, la matrice globale est inver-

sible si et seulement si B satisfait 18 condition inf-sup discrète telle que mentionnée

dans le premier chapitre à la section 1.3.

Si on choisit comme discrétisation du problème de Stokes l'élément fini mixte appelé

b Ih i (voir la sous-section 1.3.3 du chapitre l), il est possible d'éliminer les degrés de liberté

associés aux bulles liées aux barycentres des éléments. Ceci permet de réduire l'ensemble

des degrés de liberté à la partie linéaire des variables u et p, Le. PL - PL. On consultera

l'article de R. Pierre [14] pour les détails de cette réduction. Par conséquent, par rapport

à ces degrés de liberté, le système s'écrira sous forme matricielle

où C est la matrice de stabilisation du système. Selon R. Pierre (voir [Ml), cette matrice

prend la forme

où c u ~ sont des coefficients positifs déterminés par la procédure d'élimination.

Nous allons maintenant passer en revue les principales méthodes de résolution du pro-

blème de Stokes.

Méthode directe

En premier lieu, il y a la méthode directe. Pour décrire cette méthode, nous avons

besoin de la matrice masse pour la pression qui est définie comme suii :

On ne peut appliquer une méthode directe de résolution avec aucune stratégie de pivot

sans modifier le bloc diagonal nul. Pour pallier à cet inconvénient, on régularise le système

de la manière suivante :

où E est un nombre positif très petit. En fait, il est facile de montrer que cela consiste à

pénaliser le problème contraint. En effet, l'élimination de la pression p dans la dernière

équation conduit à

BU - E M ~ P =

CHAPITRE 3. RÉSOLUTTON NUM&UQUE DU PROBLÉME DE STOKES 80

p = E-~M;'(Bu - 8).

En remplaçant dans la première équation, on obtient le système suivant à résoudre :

On notera que la pression est uniquement déterminée. On peut la caractériser de la

manière suivante. En correction, on a que = -Buo. Par conséquent, la dernière équation

peut s'écrire

Bu = ~ M , 6 p

En prenant q r 1, on obtient

Ceci montre que p dx = f, po dx. etant donné qu'on choisit toujours po = O, la pression

sera caractérisée par l p dz =O.

Méthode dYUzawa

Comme nous l'avons vu précédemment, nous devons résoudre un problème de point de

selle. Or, il existe une méthode bien connue pour résoudre ce genre de problème : c'est la

méthode dlUzawa (voir [4]). Si on considère le problème ( 3 4 , l'algorithme d'Uzawa est

le suivant :

CHAPITRE 3. I~Y?SOLUTION NUMERTQUE DU PROBLÈME DE STOKES

Algorithme d'Uzawa

1. Choisir u0, po

2. Pour i = 0'1, ..., jusqu7à convergence, faire :

3. ui+l = A-'(f - B * ~ ~ )

4. Pi+i = Pi + p(Bui+l - g) 5. Fin

où p est une constante positive suffisamment grande. En multipliant par B la première

équation, on obtient

BU^+^ = BA-'(^ - B ~ ~ , ) .

En remplaçant dans la seconde équation du système, nous obtenons

-1 T Pi+l = pi + p ( ~ ~ - ' f - BA B pi - g)

qui n'est en fait rien d'autre que la méthode du gradient à pas constant appliquée au

système linéaire : -1 T BA B p = ~ ~ - ' f - g .

Cette méthode fut appliquée avec succès à des problèmes tridimensionnels de Stokes gé-

néralisés par Jean-Philippe Marcotte (voir [12] pour plus de détails). Dans cet algorithme,

nous devons calculer la solution du système linéaire

à chaque itération (voir la ligne 3 de l'algorithme d'Uzawa). En général, pour des pro-

blèmes de grandes tailles, ceci exigera l'application d'une autre méthode itérative telle

que la méthode du Gradient Conjugué préconditionné. Grosso modo, le nombre total

de produits matrice-vecteur sera le nombre d'itérations internes multiplié par le nombre

d'itérations externes d'Uzawa. Étant donné que la quantité de produits matrice-vecteur

CHAPITRE 3. RÉSOLUTION NUMÉRIQ QUE DU PROBLEME DE STOKES 82

est proportionnelle au temps CPU, ceci montre que cette stratégie est coûteuse. Les tests

numériques de J.P. Marcotte [12] le prouvent bien. De plus, on ne peut se contenter d'une

résolution incomplète à la ligne 3 sans détériorer grandement la précision. C'est pourquoi

nous allons explorer d'autres alternatives qui itèrent plutôt sur le système global.

3.1.2 Approche globale basée sur l'algorithme MINRES

Les systèmes (3.1) et (3.4) issus d'une discrétisation du problème de Stokes sont des

systèmes linéaires symétriques mais indéfinis, Le. les valeurs propres peuvent être posi-

tives et négatives. Dans ce cas, on ne peut (du moins théoriquement) appliquer la méthode

du Gradient Conjugué telle que présentée à la section 2.5 du chapitre 2. Par contre, il

existe une autre méthode qui s'applique à ce type de système, il s'agit de la méthode

des Résidus Conjugués (CR) aussi connue sous le nom dyalgorithrne MINRES. A la sec-

tion 2.6 (chapitre 2)' nous avons vu que cet algorithme est en fait un cas particulier

de l'algorithme GMRES sous l'hypothèse supplémentaire que la matrice du système est

symétrique. Contrairement à la méthode du Gradient Conjugu6, la méthode MINRES

s'applique tout aussi bien aux matrices indéfinies.

C'est Wathen et Silvester qui furent les premiers à proposer d'utiliser cet algorithme

pour résoudre le problème de Stokes dans un contexte d'éléments finis (voir [19]). Cette

stratégie fut repris avec succès par Coupez et son équipe (voir [6] et [7]) sur des problèmes

de grande taille appliqués à l'ingénierie des polymères. Toutefois, il est important de noter

que cette méthode fut surtout appliquée à des systèmes discrets provenant de formulations

stabilisées de type Pl - Pl pour le problème de Stokes. Comme l'a montré R. Pierre [14],

l'élément Mini conduit à une formulation stabilisée. A notre connaissance, aucune tentative

ne fut faite pour appliquer l'algorithme A4DXUSS à un problème de Stokes discrétisé par

l'élément de Taylor-Hood (Pz - Pl) tel que présenté à la sous-section 1.3.2 du chapitre 1.

Par la suite, on se propose d'étudier le comportement de cet algorithme pour des problèmes

tridimensionnels à l'aide de l'élément mixte de Taylor-Hood qui est connu pour être stable,

i-e. qui vérifie la condition inf-sup.

CHAPITRE 3. RESOLUTION NUMÉNQUE DU PROBLÈME DE STOKES 83

Dans la pratique, le succès d'une méthode itérative dépend grandement du choix du

préconditionnement. Nous nous sommes inspirés du choix fait par Wathen et Silvester

dans les articles [19] et [20]. Pour cela, on considère la famille de préconditionneurs qui

admettent la forme générique d'une matrice diagonale par bloc

où M A est une approximation de la matrice A liée à la vitesse et Mc une approxirna-

tion de la matrice masse Mp associée à la pression et définie par (3.3) dans le cas d'un

système discret de la forme (3.1). Pour un système de la forme (3.2), Mc dénotera plu-

tôt une approximation de la matrice de stabilisation C . Il est important de noter que la

matrice M doit être symétrique et défie-positive afin d'être un préconditionneur effectif

pour l'algonthme MINRES. Ceci impose que les matrices M A et Mc soient aussi symé-

triques et définies positives. Les deux chercheurs, Wathen et Silvester ([19] et [20]), ont

montré que le choix de la partie diagonale de la matrice de masse Mp était largement

sufEsant et n'affectait pas la convergence de l'algorithme. En effet, ils montrent que la

matrice diagonale (diag(Mp)) est spectralement équivalente à la matrice masse. Ceci est

une conséquence de la validité de la condition inf-sup. Étant donné que tous nos tests

numériques concernent des systèmes provenant d'une discrétisation par les éléments Mini

ou Taylor-Hood, nous allons toujours faire le choix

Concernant le choix de MA, plusieurs possibilités s'ofient à nous et feront l'objet de tests

numériques dans les sections subséquentes.

Terminons cette section par une remarque sur le choix de l'dgorithme MNRES par

rapport à la méthode GMRES. Pour l'algorithme GMRES, nous avons besoin de fixer

le nombre maximal de directions de descente, i.e GMRES(m). Ceci devient coûteux en

mémoire et en temps de calcul si m est relativement grand. Par contre, l'algorithme

MINRES utilise seulement une récurrence à trois termes qui nécessite moins de mémoire

et moins de calculs.

CHAPITRE 3. RÉSOLUSION NUMÉRTQUE DU PROBLÈME DE STOKES 84

3.1.3 Approche globale basée sur la méthode d'Arrow-Hurwicz

Comme il fut mentionné précédemment à la sous-section 3.1.1, le principal défaut de

l'algorithme d7Uzawa est la nécessité de résoudre le plus exactement possible l'inversion

de la matrice A, ce qui est très coûteux surtout pour de grands systémes. Or, il existe une

variante de l'algorithme d'Uzawa pour le calcul de point de selIe. Il s'agit de la méthode

d'Arrow-Hurnricz. En se référant au livre de Saad [161, voici l'algorithme.

Algorithme Arrow-Hurwicz

1. Choisir uo et p,

2- Pour i = 0'1, ..., jusqu'à convergence, faire :

3. Calculer u ~ + I = ~i + C Y ( ~ - Aui - B ~ ~ ~ )

4. Calculer = pi + p ( B ~ i + ~ - g )

5. Fin

Cet algorithme peut aussi être interprété comme une discrétisation en temps des équations

d'évolution

Dans ce cas, les paramètres positifs cu et p correspondent à des pas de temps possiblement

multipliés par un facteur d'échelle f l

Dans cet algorithme, les itérations peuvent s'écrire sous la forme :

CITAPITRE 3. RÉSOLUTION NCIM'RIQUE DU PROBLÈME DE STOKES 8s

Cette écriture a l'avantage de mettre en évidence le préconditionnement associé au calcul

des directions de descente, i.e. u+l- Ui et p,, - p i :

Par conséquent, il semble naturel d'étendre ce préconditionnement à une classe plus

vaste tout à fait analogue au choix fait pour l'algorithme MINRES à la sous-section

précédente (3.1.2)- On fera le choix suivant comme matrice de préconditionnement

M =

Tout comme la section précédente,

positive qui approximera la matrice 1

trique et défie-positive associée à la pression. Concernant la matrice Mc, nous ferons

exactement le même choix qu'à la section 3.1.2

\ B - M c ) -

M A dénotera une matrice symétrique et définie-

iritesse A tandis que Mc sera une matrice symé-

Pour le choix de M A , nous reportons cette discussion lors des tests numériques.

Il est clair qu'en général, un simple schéma itératif de la forme (3.5) sera beaucoup trop

lent à converger. Ceci suggère d'utiliser un processus itératif de type Krylov. Plusieurs

possibilités s'offrent à nous. En premier lieu, malgré que le système soit symétrique, la

matrice de préconditionnement M est non symétrique. Ceci a comme conséquence que

l'algorithme MINRES de la sous-section 3.1.2 devient inapplicable car le système précon-

ditionné est non symétrique. Ainsi, on doit obligatoirement utiliser une méthode de Krylov

pour des systèmes non symétriques. En principe, l'algorithme GMRES ferait l'affaire, mais

il y a mieux. Nous allons plutôt utiliser la méthode BICGSTAB présentée à la section 2.7

du chapitre 2. On rappelle que cette méthode n'est pas basée sur le procédé d ' h o l d i

mais plutôt sur le procédé de biorthogonalisation de Lanczos. Tout comme l'algorithme

MINRES, la méthode BICGSTAB fait appel à une récurrence à trois termes, donc est

plus économique que GMRES(m) surtout si m est relativement élevé. Évidemment, il y

a un prix à payer lorsqu'on utilise les méthodes de biorthogonalisation. Cela concerne le

comportement souvent erratique de la convergence de ces algorithmes. Heureusement, la

version stabilisée de van der Vorst (voir [21]) comge grandement ce comportement. Ici,

une remarque s'impose sur l'appellation de méthode d' Arrow-Hurwicz. Dans la stratégie

décrite ci-dessus, la méthode d'Arrow-Hurwicz est plutôt utilisée comme préconditiomeur

et non comme méthode de résolution. Ce préconditonneur a pour but d'accélérer la conver-

gence de la méthode de Krylov choisie (BICGSTAB). Cet abus de langage est souvent

utilisé pour décrire certaines méthodes itératives de résolution. Par exemple, en décom-

position de domaines, la méthode de Schwarz désigne à la fois la méthode de résolution

et le precondionneur tout dépendant du contexte.

L'algorithme BICGSTAB utilisé dans les tests numénques est basée sur une variante

dite "transpose-free" qui ne nécessite pas le produit matrice-vecteur avec la matrice trans-

posée. En fait, étant donné qu'en général nous assemblons les matrices, l'opération aurait

été facile à calculer- 'Toutefois, il existe une classe de problèmes où cette opération devient

virtuellement impossible à calculer. C'est le cas où l'opération matrice-vecteur est ap-

proximée par une formule de différences finies comme dans la méthode de Newton-Krylov

[N-

3.2 Problèmes tests

Dans le cadre de cette étude, quatre problèmes tests ont été considérés pour étudier les

performances des algorithmes (section 3.1) de résolution du problème tridimensionnel de

Stokes. Les problèmes sont décrits par les différents types d'écoulements suivmts :

1. la cavité,

2. l'écoulement dans une conduite à section carrée,

3. l'écoulement dans une jonction de deux cylindres,

CHAPITRE! 3. RÉSOLuSION NU&&RTQUE DU PROBLÈME DE STOKES 87

4. la contraction.

Écoulement dans une cavité 3D

Il s'agit d'étudier l'écoulement du fluide dans une cavité de forme cubique. Pour ce faire,

on suppose qu'une des faces du cube se déplace selon une vitesse constante. On a imposé

la vitesse v = (1,0, O) sur cette face. De plus, on suppose que le fluide adhère aux parois

solides. Ainsi on doit imposer que le fluide ait une vitesse nulle v = (0,0,0) sur ces parois

du cube tel qu'illustré à la figure 3.1. Ce type de problème est intéressant mais n'est pas

très réaliste car la vitesse change brusquement sur le contour de la face d'entraînement

du fluide. On crée donc des singularités où la pression est infinie.

FIG. 3.1 - Problème de la cavité

On a utilisé cinq maillages différents. Le maillage de base CUBE1 pour la cavité est

représenté a la figure 3.2. Les maillages suivants (CUBEZ, CUBE3, CUBE4 et CUBES) ont

été obtenus à partir du maillage CUBE1. Par exemple, pour obtenir le maillage CUBE2,

on a appliqué un algorithme sur le maillage de base a h de diviser les arêtes en deux. On

obtient le maillage CUBE3 en divisant les arêtes en deus du maillage CUBE2 et ainsi de

suite. Les caractéristiques de ces maillages figurent au tableau 3.1.

FIG. 3.2 - Premier maillage de la cavité : CUBE1

TAB. 3.1 - Maillages utilisés pour la cavité 3D

7

CUBE1

48

27

98

120

0.60596

Nombre d'cléments

Nombre de sommets

Nombre d'arêtes

Nombre de faces

h

CUBE2

384

125

604

864

0.313967

CUBE3

3 072

729

4 184

6 528

0.163743

CUBE4

24 576

4 913

3 1 024

50 688

0.0847969

CUBES

196 608

35 937

238 688

399 360 / 0.0437389

CHAPITRE 3. R~?SOLUTION NUMÉRIQ UE DU PROBLÈME DE STOKES 89

Écoulement dans une conduite à section carree

n s'agit d'étudier l'écoulement du fluide qui entre dans un prisme rectangulaire puis

y sort par la face opposée. L'écoulement est entraîné par un gradient de pression. On

suppose que Ie fluide adhère à la surface de la conduite. On peut voir la géométrie du

problème à la figure 3.3. A l'entrée et à la sortie, on suppose que l'écoulement est établi.

On impose donc un écoulement suivant la normale axiale n : w = (0, O, v,) où v, est laissé

libre et n est la normale unitaire extérieure à la frontière. De plus, à l'entree et à la sortie,

on impose une condition de type Neumann de la forme :

Remarquons que, pour ce type d'écoulement, le terme enn(u) doit vérifier la relation

car v, est indépendant de la variable axiale z. Donc, la condition de Neumann revient

à fixer la pression aux deux entrées. Nous imposerons donc une pression pius grande à

l'entrée qu'à la sortie pour que le fluide s'écoule de l'entrée vers la sortie. Ainsi, à l'entrée,

on fixera la pression à p = I ce qui correspond à prendre r,, = -1 et à la sortie T,, = O

(condition naturelle).

FIG. 3.3 - Problème de la section carrée

CHAPITRE 3. RÉSOLUTION NUMERIQUE DU PROBLÈME DE STOKES 90

On a utilisé quatre maillages différents. Le maillage de base PRIçME1 est représenté à

la figure 3.4 et Ies caractéristiques des

3.2. Les maillages suivants (PRISME2,

du maillage PRISME1 comme il a été

de la cavité 3D.

maillages utilisés sont regroupées dans le tableau

PRISME3 et PRISME4) ont été obtenus à partir

expliqué pour les maillages associés au problème

FIG. 3.4 - Premier maillage de la conduite à section carrée : PRISME1

SAB. 3.2 - Maillages utilisés pour la conduite à section carrée

Nombre d'éléments

Nombre de sommets

Nombre d'arêtes

Nombre de faces

h

Écoulement dans une jonction de deux cylindres

Il s'agit d'étudier l'écoulement du fluide dans deux cylindres placés perpendiculairement.

Le fluide entre par deux des trois extrémités (cercles) situées sur le plus gros des deux

cylindres. On appellera ces deux extrémités entrée gauche et entrée droite. Le fluide sort

par la plus petite extrémité située sur le second cylindre placé perpendiculairement. Dans

ce problème, on suppose encore une fois que le fluide adhère aux parois solides d'où la

PRISME1

120

54

221

288

1.22369

PRISME2

960

275

1 426

2 112

0.631985

PNSME3

7 680

1 701

10 184

16 128

0.328889

PRISME4

61 440

11 849

76 360

125 932

0.170034

CHAPITRE 3- R É S O L U T ! NUMÉRTQUE DU PROBLÈI\~E DE STOKES 91

vitesse nulle imposée sur les faces qui ne correspondent pas aux entrées ou à la sortie. Ici,

nous utilisons des conditions aux limites de type Neumann aux entrées comme dans le cas

de la conduite à section carrée. A l'entrée, on impose un écoulement suivant la normale

axiale (axe y) - Donc v = (O, a,, O ) et u, est laissé libre. De plus, on impose une condition

de traction de type Neumann sur ces faces et r,, = -100 où r, est défini par (3.6). La

vitesse à la sortie suit la normale axiale (axe 3 et est donnée par le vecteur v = (0, O, v,)

où uz est laissé libre. Remarquons que si on s'éloigne de la jonction, l'écoulement est

presqu'un écoulement de Poiseuille (référence sous-section 1.1.3 chapitre 1) et le terme

e,.&) = $$ = O puisque v, est indépendant de la variable axiale y. Ainsi, on peut

dire que la condition de Neumann correspond à fixer la pression aux deux extrémités, Le.

p = 100. Étant donné qu'on veut un écoulement entrant aux deux bouts, on prend la

même pression des deux côtés.

(O, ïoy -1)

FIG. 3.5 - Problème de la jonction des deux cylindres

On a utilisé deux maillages différents. Le maillage de base CYLINDRES1 est illustré

à la figure 3.6 et ses caractéristiques sont données dans le tableau 3.3. Pour obtenir le

deuxième maillage CYLINDRES2, on a appliqué un algorithme sur le premier maillage

afin de diviser les arêtes en deux.

CHAPITRE 3. RÉSOLUSION NUMÉRIQUE DU PROBLÈME DE STOKES

FIG. 3.6 - Premier maillage des cylindres : CYLINDRES1

Nombre d'éléments

Nombre de sommets

CYLINDRES1

16 726

Nombre d'arêtes

TAB. 3.3 - Maillages utilisés pour la jonction de deux cylindres

CYLINDRES2

133 808

3 847

Nombre de faces

26 424

22 577 168 251

L 35 457 275 636

CHAPITRE 3. RÉSOLUTION ~W&&RIQUE DU PROBLÈME DE STOKES

Écoulement dans une contraction 3D

Il s'agit d'étudier le comportement d'un fluide qui entre dans un cube lorsque subit

la section est diminuée d'un facteur 4. La géométrie consiste en deux prismes attachés un

à l'autre, elle est représentée à la figure (3.7). L'un étant carré et l'autre rectangulaire.

L'ouverture du prisme carrée étant 4 fois plus grande que celle du prisme rectangulaire (la

face carrée). On suppose que le fluide adhère à la surface d'où la vitesse nulle sur toutes

les faces sauf à L'entrée et à la sortie. A l'entrée nous posons v = (0,0,162(1- x) y (1 - y))

et à la sortie, nous imposons que la vitesse soit donnée par v = (0,0, v,) où u, est la

composante libre. Le maillage utilisé pour la contraction est représenté à la figure 3.8 et

ses caractéristiques sont données dans le tableau 3.4. Le maillage CONTR4CTION3D2 a

été obtenu en divisant les arêtes en deux.

FIG. 3.7 - Problème de la contraction en trois dimensions

Maintenant que nous avons décrits les problèmes étudiés, essayons d'établir un lien

entre les nombres de sommets, d'arêtes, de faces et d'éléments composant un maillage.

Nous sommes particulièrement intéressés au comportement asymptotique de ces relations

lorsque le nombre d'éléments devient grand. Cette information sera utile par la suite

CHAPITRE 3. RÉSOLUTION NUMÉHQUE DU PROBLÈME DE STOKES

FIG. 3.8 - Premier maillage de la contraction : CONTRACTIONJDl

Nombre d'éléments

Nombre de sommets

Nombre d'arêtes

Nombre de faces

TAB. 3.4 - Maillages utilisés pour la contraction 3D

CONTR4CTION3DI

30 720

6 209

38 976

63 488

CONTRACTIOX3D2

245 760

45 185

299 136

499 712

CHAPITRE 3. R.ÉSOLUTION NUMÉRlQUE DU PROBLEME DE STOKES

lorsqu'on voudra comparer les tailles des systèmes linéaires obtenus par discrétisation

avec les éléments mixtes de Taylor-Hood et Mini.

Notons respectivement par Ns, Na, N f et Ne, les nombres de sommets, d'arêtes, de

faces et d'éléments d'un maillage donné. En premier lieu, on sait qu'il existe une relation

connue sous le nom de relation d 'Euler-Poincaré qui relie toutes ces quantités entres elles :

où c(R) est l'indice d 'Euler-Poincaré du domaine Cl. Cet indice est entièrement déterminé

par la topologie du domaine. Par exemple, pour les cas qui nous intéressent, c(R) = 1

puisque le domaine est simplement connexe.

L'objectif consiste à étudier les rapports E, 9, pour les différents maillages uti-

lisés. À la figure 3.9, nous avons représenté graphiquement ces rapports pour les plus

gros maillages de chaque problème (l=CUBE5,2=PRISME4,3=CYLINDRES2,4=CON-

TRACT10 N3D 2 en abscisse). Sur le graphique (voir figure 3.9), les droit es représentent

la valeur moyenne de chaque rapport s, , et E. En regardant la droite de E, on

remarque que

Na cx alNs

où <ri E [6.3,6.7]. De même, si on considère la droite de ,, on peut dire que le nombre

de faces se comporte comme suit par rapport au nombre de sommets

où a2 E [10.3,11.1]. Finalement le nombre d'éléments semble varier de la façon suivante

FIG. 3.9 - Comparaison des rapports s, ,, pour les plus gros maillages de chaque

problème.

Graphique des rapports NaWs, Ne/Ns. NfNs pour les maillages CUBE4 PRISME4, CYLINDRES2 et CONTRAON3D2

12 1 1 1 I I L I

11

10

- - A

- ..--*------................- '..-'--".*'~.~".~..~..*.......~*~~..*.*~~~~~~.~~~*.a.aaaaa*.aaaaaaaaaaaaaaaaaaaaaaa..a.aaaaa.a.aaaa.aaaaaaaa - A - A -

9

t C:

c 2 7

6

5

- - - - = - - - -

- - -

gr -

- -

- -

- -

- - - -

- -

0

- - ------------------------------a---44--------------T------------------------------Y - - CI

y

- - -

- -

- - O

- - - h

- O O - -

d - - 4 1 1 1 1 I 1 I -

1 2 3 4

De plus, les coefficients al, 0 2 et c r ~ sont liés par la relation d'Euler-Poincaré. En effet,

en divisant par Ns, on obtient

Or, d'après le graphique (voir figure 3.9), on peut dire que

et on voit bien que la relation (3.7) est v é s é e puisque I - 6.4 + 10.6 - 5.2 = 0.

3.3 Résultats numériques

Par la suite, tous les tests numériques utilisent le critère d'arrêt suivant :

i.e. r = ~ - ' ( b - Au) ; ro étant le résidu initial et r~ le où r est le résidu préconditionné

résidu à la IVième itération. Par contre, la norme du résidu qui figure dans les tableaux de

résultats est la norme du résidu non préconditionné Le. r = b - Au. Dans les tableaux qui

suivent, le nombre d'itérations correspond au nombre de produits matrice-vecteur exigé

par la méthode itérative pour résoudre le problème en question.

Avant de présenter les tests numériques, il est utile de connaître la taille des systèmes

linéaires étudiés, surtout si on désire comparer les calculs provenant des deux discrétisa-

tions par les éléments mixtes Taylor-Hood (Pî - Pl) et Mini (PT - Pl). Ces informations

figurent au tableau 3.5 pour les maillages que nous avons utilisés pour les tests. Pour

l'élément P2 - Pi, nous avons un degré de liberté pour chacune des trois composantes du

vecteur vitesse (P2) sur chaque arête (3Na) et chaque sommet (3Ns) du maillage plus

un degré de liberté pour la pression (Pl) sur chaque sommet du maillage (1Ns) (voir

figure 1.3 au chapitre 1). Pour l'élément Mini, on a un degré de Liberté pour chacune des

CHAPITRE 3. RÉsoLuTION NUM&UQUE DU PROBLÈME DE STOKES 98

trois composantes du vecteur vitesse et un degré de liberté pour la pression sur chaque

sommet du maillage (3Ns + lNs)(voir figure 1.4 au chapitre 1). Évidemment, cela pré-

suppose qu'on a déjà éliminé par condensation statique les degrés de liberté associés aux

barycentres des éléments (voir les détails dans [14]).

--

Élément Mini

Nombre de degrés de liberté

TAB. 3.5 - Nombre de degrés de liberté pour les différents maillages utilisés lors des tests

MaiUage

CUBE1

numériques.

Élément Taylor-Hood

402

Ainsi, en se servant des notations introduites à la section 3.2, le nombre total de degrés

de liberté pour l'élément de Taylor-Hood (qu'on notera Np2-pl) est donné par

tandis qu'avec l'élément Mini, il correspond à

CHAPITRE 3. RÉsOLUTION ~VU~L~?&UE DU PR OBI;&^^ DE STOKES 99

Alors, si on fait le rapport du nombre de degrés de liberté de Pz - Pl par rapport à celui

de Mini, on obtient

Selon la section 3.2, on a vu que = 6.4 lorsque la taille du maillage est importante.

Par conséquent, on peut dire qu'asyrnptotiquement, le nombre de degrés de liberté pour

une discrétisation P2 - Pl est environ 6 fois plus grand que pour une discrétisation Mini

i.e NP,-R = 6NIMirZi- Cette règle empirique permet de comparer les efforts de calcul des

deux discrétisations. Toutefois, i1 faut préciser que l'élément de Taylor-Hood est d'ordre

2 tandis que l'élément Mini est d'ordre 1. De ce point de vue, la comparaison perd de son

sens.

3.3.1 Résultats numériques à l'aide de l'élément de Taylor-Hood

Méthode NIINRES

Dans un premier temps, nous avons étudié la performance de l'algorithme MmRES tel

que présenté à la sous-section 3.1.2 appliqué à une discrétisation Pz - PL (Taylor-Hood) du

problème de Stokes. Nous avons utilisé une matrice de préconditionnement de la forme :

Rappelons qu'à la section 3.1.2, le choix de la matrice Mc fut discuté et donné par

l'expression

Mc = diag(M,)

où M p est la matrice masse associée au Pl. Pour ce qui est de la matrice Ma, nous avons

fait successivement les choix suivants :

1. M A = A.

L'action du préconditionneur est résolue par une méthode directe d'où IYappeIlation

de préconditionnement LU.

CHAPITRE 3. RÉSOLUTION ~VUMÉRTQUE DU PROBLÈME DE STOKES 100

2. MA = SSOR(A).

Ceci correspond à appliquer deux itérations de l'algorithme de Gauss-Seidel : une

parcourue dans l'ordre habituelle tandis que l'autre est faite dans le sens iaverse.

3. Ma = d iag (A) .

Ceci revient à appliquer une itération de l'algorithme de Jacobi.

On notera que ces matrices sont toutes symétriques et définies positives. Ce point est

essentiel pour la méthode MINRES (voir la section 2.6 du chapitre 2).

Nous avons faits des tableaux pour les différents préconditionnements (LU, SSOR et

Jacobi) utilisés avec la méthode MINRES pour les maillages tests des problèmes de la

cavité 3D et de la conduite à section canée. Les tableaux 3.6 à 3.10 regroupe ces informa-

tions pour le problème de la cavité 3D. De même, les tableaux 3.7 à 3.11 présentent ces

informations pour le problème de la conduite à section carrée. A h de mieux comparer

l'effet des préconditionneurs, les figures 3.10 et 3.11 montrent les nombres d'itérations par

rapport à h pour chaque préconditionneur et cela pour les deux géométries : la cavité 3D

et la conduite à section carrée respectivement (h dénote le pas du maillage).

Méthode MINRES (Élément Taylor-Hood)

II Préconditionnement LU

TAB. 3.6 - Problème de la cavité 3D résolu par MINRES avec un préconditionnement

LU.

u

Débutons avec le préconditionnement LU. Selon les figures 3.10 et 3.11, on constate

que le nombre d'itérations semble converger vers une constante à mesure que h tend vers

klaillage

CUBE1

CUBE2

CUBE3

Nombre d'itérations

N

33

55

63

Norme Z,

Ilb - AuIVllrn

5.20 x IO-^

2.35 x IO-^

3.72 x IO-^

Nombre de flops

x I O 6

6.205

224-9

14 540

CHAPITRE 3. RÉSOLUTION NUMÉRIQUE DU P R O B L ~ ~ ~ E DE STOKES


TAB. 3.7 - Problème de la section carrée résolu par MINEES avec un préconditionnement

LU.

C

zéro. Autrement dit, le taux de convergence est indépendant de h. Ce résultat est bien

connu pour la méthode d'Uzawa ([4]) et est en accord avec les travaux de Silvester et

Wathen ([20]). Les normes 1, apparaissant aux tableaux 3.6 et 3.7, indiquent bien que

les solutions approchées sont suffisamment précises. On rappelle que le critère d'arrêt est

uniquement basé sur la norme du résidu préconditionné. La dernière colonne des tableaux

3.6 et 3.7 montre le coût de cette méthode préconditionnée par LU. On constate que le

nombre d'opérations devient rapidement prohibitif dû à l'utilisation de la factorisation

LU.

Les tableaux 3.8 et 3.9 traitent du préconditionnement SSOR. Les figures 3.10 et 3.11

indiquent une augmentation du nombre d'itérations à mesure que h tend vers zéro. Tou-

tefois cette augmentation est très lente. Afin de la quantifier, on suppose que la courbe

exprimant le nombre d'itérations d'une méthode itérative est de la forme O(hqP). En fai-

sant des régressions linéaires dans une échelle log-log à partir des données des tableaux 3.8

et 3.9, on trouve que a! = 0.82 pour le problème de la cavité et a! = 0.73 pour la conduite.

Ceci montre bien la progression lente du nombre d'itérations en fonction de h. Tout comme

le préconditionnement LU, les normes 1, sont très acceptables et comparables. Par contre,

le coût de la méthode est passablement inférieur à celui du préconditionnement LU. Par

exemple, le nombre d'opérations pour CUBE4 avec SSOR est inferieur à celui de CUBE3

Préconditionnement LU

Maillage

PRISME1

PRISME2

PRISME3

Nombre de flops

x 106

20.97

800.2

70 110


N

35

43

45

Norme I, du résidu

116 - Au~llrn

4.68 x IO-?

1.41 x IO-'

1.23 x IO-^

C W I T R E 3. RÉSOLUSION NUM@R~QUE DU PROBLÈME DE STOKES 102

avec LU même si ce dernier possède 8 fois moins d'éléments. Cet écart augmente avec la

taille du maillage.

n P


TAB. 3.8 - Problème de la cavité 3 0 résolu par MIiuRES avec un préconditionnement

SSOR.

Préconditionnement SSOR



Maillage

TAB. 3.9 - Problème de la section carrée résolu pax MINRES avec un préconditionnement

SSOR.


Finalement, les tableaux 3.10 et 3.11 concernent le préconditionnement Jacobi. Les

figures 3.10 et 3.11 semblent indiquer une augmentation linéaire du nombre d'itérations

en fonction du paramètre h. En effet, en faisant une régression linéaire comme décrite

Norme I, du résidu

J

Maillage

PRISLMEI

PRISME2

PRIS ME3

PRISME4

I

Nombre de flops

x Io6

18.85

236.8

2 844


N

75

134

215

Norme I, du résidu

llb - A~~l l rn

1.74 x IO-^

0.87 x IO-^

0.57 x IO-^

314 0.26 x IO-? 1 32 120

CHAPITRE 3. RÉSOLUTION NUMEEUQUE DU PROBLÈME DE STOKES 103

Préconditionnement Jacobi

- Méthode MINRES (Élément Taylor-Hood)

TAB. 3.10 - Problème de la cavité 3D résolu par MINRJ3S avec un précornditionnement

Jacobi.


TAB. 3.11 - Problème de la section carrée résolu par MïIPEtECS avec un préconditionnement

Jacobi.

Norme I, du résidu


Nombre d e flops

Maillage

PRISME1

PRISME2

PRISME3

PRISME4

Nombre dte flops

x10a6


*v Norme 1, du résidu

II0 - Auwl lm

16.23

253.3

3 40.5

50 7 8 0

109

244

441

853

2.66 x IO-^

1.40 x IO-^

0.40 x IO-^

0.10 x l o4

CHAPITRE 3. RÉSOLUTION N U ~ A & Q U E DU PROBLÈIME DE STOKES 104

Graphique du nombre d'iterations en fonction de h Methode MINRES (EIement P2-Pl)

Probleme de la Cavite 3D

O LU O. SSOR A Jacobi - Tendance Lu ---- Tendance SSOR ------• Tendance Jacobi

FIG. 3.10 - Graphique du nombre d'itérations en fonction de h pour le problème de la

cavité 3D résolu par la méthode MINRES avec une discrétisation Taylor-Hood

CHAPITRE 3. RJ%OLUTION NUMÉRIQLB DU PROBLÈME DE STOKES 105

plus haut, on obtient que l'exposant de la courbe O(h-P) est donné par cr = 1.18 pour

la cavité et (i. = 1.03 pour le problème de la conduite. Comme les exposants (1.18 et

1.03) sont près de 1, on peut affumer que le comportement est Linéaire, i.e NbIterJacn FZ

ch-' où c est une constante. De nouveau, les normes 1, sont du même ordre que celles

correspondant aux autres types de préconditionnement. En ce qui concerne le coût de la

méthode préconditionnée par Jacobi, il demeure supérieur à celui de SSOR surtout pour

les gros maillages.

Graphique du nombre d'iterations en fonction de h Methode MINRES (Element P2-P 1)

Probleme de la conduite a section carree


section carrée résolu par la méthode MINRES avec une discrétisation Taylor-Hood

CHAPITRE 3. ELÉSOLUTION NUMÉRIQUE DU PROBLELME DE STOKES 106

Méthode de Arrow-Hurwicz

En deuxième lieu, nous avons étudié la méthode dYArrow-Hurwicz telle que présentée à

la sous-section 3.1 -3. Nous avons utilisé une matrice de préconditionnement de la forme :

où M = diag(Mp). En ce qui concerne la matrice Ma, nous avons adopté la même

stratégie dans le cas de l'algorithme bllXRES :

1. M A = A :

2. M A = SSOR(A),

3. M A = diag(A).

Notons que le premier choix du préconditionnement i.e. M A = A correspond à I'dgo-

rithme d'Uzawa que nous avons décrit à la sous-section 3.1.1. En effet, on a d'après la

première ligne de l'équation matricielle (3.5)

M A ( Z L ~ + ~ - uK) = f - AuK - B ~ I ) ~ .

En remplçant M A par A et en distribuant le premier terme, on a

et en simplifiant, on obtient finalement

AuKil = f - B~~~

dont la solution est calculée à la ligne 3 dans l'algorithme d7Uzawa tel que décrit à la

sous-section 3.1.1. Nous verrons également ci-dessous que le nombre d'itérations est indé-

pendant du pas h avec ce choix de préconditionnement.

Dans les tableaux 3.12 (LU), 3.14 (SSOR) et 3.16 (Jacobi) on retrouve les informations

pour le problème de la cavité 3D résolu avec la méthode de Arrow-Rurwicz. Dans les

tableaux 3.13 (LU), 3.15 (SSOR) et 3.17 (Jacobi) on retrouve les mêmes informations

pour le problème de la conduite à section carrée.

Il Méthode de Arrow-Hurmicz (Élément Taylor-Hood) -7

TSB. 3.12 - Problème de la cavité 3D résolu par Arrow-Hurmicz avec un préconditionne-

ment LU.

II Méthode de Arrom-Hudcz (Élément Taylor-Hood) II

-

Préconditionnernent LU

Maillage

CuBE1

CUBE2

CUBE3

TAB. 3.13 - Problème de la section carrée résolu par Arrow-Hurwicz avec un précondi-

tionnement LU.

u

Nombre de flops

x 106

6.019

214.7

14 l50


N

32

50

52

Norme I, du résidu

Ilb - Au~llrn 0.36 x IO-^

5.05 x IO-^

3.03 x IO-^

L

Préconditionnement LU

Maillage

PRISME1

PRISME2

PRISME3

Nombre de flops

x 106

19.63

782.5

70 230


IV

32

40

46

Norme lm du résidu

Ilb - Au~llrn

0.43 x

7.80 x IO-^

0.47 x IO-^

ClïXPZTRE 3. RÉSOLUTION NUMERIQUE DU PROBLÈME DE STOKES

600

500

400 C O .LI 3 c= 5 a a 300 2 s E

zoo

Graphique du nombre d'iterations en fonction de h Methode Arrow-Hurwicz (Element P2P1)

Probleme de la cavite 3D

1 I 1 1 1

0 LU a SSOR 1 A Jacobi - Tendance LU ---- Tendance SSOR ------- Tendance Jacobi


cavité 3D résolu par la méthode Arrow-Hurwicz avec une discrétisation Taylor-Hood

CHAPITRE 3. R&sOLUTION N U ' Q U E DU PROBLÈME DE STOKES 109

Graphique du nombre d'iterations en fonction de h Mediode de Arrow-Hurwicz (Element =-Pl)

Robleme de la conduite a secrion carree

0 LU 0 SSOR A Jacobi

tendance LU ---- tendance SSOR .--.-.. tendance Jacobi


section carrée résolu par la méthode Arrow-Hurwicz avec une discrétisation Taylor-Hood.

CIZAPITRE 3. RÉSOLUTION NUM~RTQUE DU PROBLÈME DE STOKES 110

S u . les figures 3-12 et 3.13, on retrouve les graphiques du nombre d'itérations en fonction

de h obtenus avec la méthode de Arrow-Hurwicz pour les différents préconditionneurs (LU,

SSOR et Jacobi) respectivement pour le problème de la cavité 3D et celui de la conduite

à section carrée. Comme pour la méthode MINRES, ces graphiques nous permettent de

mieux comparer l'effet des préconditionneurs sur la méthode. Premièrement, étudions

l'effet d'un préconditionnement LU. Les figures 3.12 et 3.13 indiquent que le nombre

d'itérations semble converger vers une constante à mesure que h tend vers zéro comme

s'était le cas pour la méthode hlIINRES. On peut dire que les solutions approchées sont

suffisamment précises : les normes I , qui figurent aux tableaux 3.12 et 3.13 en témoignent.

Dans la dernière colonne de ces tableaux, on peut voir que le nombre d'opérations devient

rapidement très imposant. Notons par ailleurs que le nombre d'opérations pour un maillage

donné est très près d'une méthode à l'autre. Par exemple, on a besoin de 14 540 x 106

opérations avec la méthode MmRES (voir tableau 3.6) pour le maillage CUBE3 tandis

que la méthode Arrow-Hunvicz requiert 14 150 x 106 opérations pour obtenir la même

précision.

Méthode de Arrow-Hurwicz (Élément Taylor-Hood)

Mail1 age

CUBE2

CUBE3

CUBE4

Nombre de flops

x IO6

Préconditionnement SS OR

TAB. 3.14 - Problème de la cavité 3D résolu par Arrow-Hurwicz avec un préconditionne-

ment SSOR.


Deuxièmement, considérons les tableaux 3.14 et 3.15 traitant du préconditionnement

SSOR. Les normes 1, sont très acceptables et comparables comme s'était le cas pour le

Norme Z, du résidu

préconditionnement LU et pour la méthode MJNRES. Par contre, on peut conclure à la vue

de la troisième colonne de ces tableaux que le coût de l'utilisation du préconditionnemnt

SSOR est nettement inférieur à celui du préconditionnemnt LU pour la même méthode.

De plus, notons que le nombre d'opérations pour Les maillages CUBE4 et PRISME4 est

diminué de moitié compaxativement à la méthode MIIVRES. Par exemple, on a besoin

de 10 400 x I O 6 opérations avec la méthode MINRES pour le maillage CUBE4 tandis

que la méthode Arrow-Hurwicz requiert 5 788 x 106 opérations pour obtenir la même

précison. Les figures 3.12 et 3.13 indiquent une augmentation du nombre d'itérations à

mesure que h tend vers zéro. Toutefois, cette augmentation est très lente. Pour la qualifier,

nous avons fait des régressions Iinéaires comme pour la méthode MINRES en supposant

que la courbe exprimant le nombre d'itérations d'une méthode itérative est de ta forme

O(h-&). Pour le problème de la cavité, on a trouvé cr = 0.47 et pour la conduite à section

carrée a = 0.62. Rappelons qu'on avait obtenu des exposants plus élevés dans le cas de la

méthode MINRES : pour le problème de la cavité 3D on avait obtenu cu = 0.82 et pour le

problème de la conduite à section carrée, cr = 0.73.



Maillage Nombre d'itérations Norme 1, du résidu 1 Nombre de flops

TAB. 3.15 - Problème de la section carrée résolu par kow-Hurwicz avec un précondi-

tionnement SSOR.

Finalement, les tableaux 3.16 et 3.17 concernent le préconditionnement Jacobi. Les

figures 3.12 et 3.13 semblent indiquer une augmentation linéaire du nombre d'itérations

CHAPITRE 3. RÉSOLUTION NUMÉRTQUE DU PROBLEME DE STOKES

en fonction de h. En effet, en faisant une régression linéaire, on obtient que l'exposant de

la courbe O(h-a) est donné par cr = 0.93 pour le problème de la cavité 3D et a = 0.97

pour Ia conduite à section carrée. Puisque les exposants (0.93 et 0.97) sont très près de 1,

on peut af6rmer que le comportement est approximativement béa i r e Le. -VbIterJambi x

ch-' où c est une constante. Remarquons que ce comportement semble être similaire au

comportement que nous avions obtenu avec la méthode MINRES. De plus, les normes Z,

sont du même ordre que celles correspondant aux autres types de préconditionnement. En

ce qui concerne le coût de la méthode préconditionnée par Jacobi, il demeure supérieur

à celui de SSOR surtout pour les gros maillage. De plus, le nombre d'opérations est

sensiblement le même que celui obtenu avec la méthode MZNRES.

7


Préconditionnernent Jacobi 1

TAB. 3.16 - Problème de la cavité 3D résolu par Arrotv-Hunvicz avec un préconditionne-

ment Jacobi.

Maillage 11 Nombre d'itérations

Problème de la jonction de deux cylindres

Norme I, du résidu 1 Nombre de flops 1 I

On peut comparer les données du probIème de la jonction des deux cylindres figurant

dans le tableau 3.18 avec les données obtenues pour le maillage PRISME4 figurant aux

tableaux 3.9, 3.11, 3.15 et 3.17 puisque ces deux problèmes ont un nombre de degrés

de liberté du même ordre de grandeur (CYLINDRES1 = 83 119 DDLs et PRISME4 =

37 248 DDLs). Ainsi, on remarque que les nombres d'opérations et d'itérations pour une

CHAPITRE 3- R~?SOLUTION L W R I Q U E DU PROBLÈME DE STOKES 113


TA%. 3.17 - Problème de la section carrée résolu par Arrow-Hurwicz avec un précondi-

tioanernent Jacobi.

Y

méthode et un préconditionnement donnés sont comparables. De plus, le tableau 3.19 nous

indique que la méthode Arrow-Hurwicz préconditionnée par SSOR est la moins coûteuse

et elle requiert le nombre d'itérations le moins élevé.


Maillage

PRISME1

PRISME2

PRISME3

P RISME4

--- - -

Problème des deux cylindres

TAB. 3.18 - Problème de la jonction de deux cylindres pour l'élément Taylor-Hood.

Méthode

Jacobi 399 6.43 x 6.800 x log

Sur les figures 3.14 et 3.15, nous pouvons observer respectivement les solutions en pres-

sion et en vitesse respectivement.


IV

78

130

318

488

Arrow-Hurwicz

A la figure (3.16)' on peut observer le graphique de convergence pour le problème de la

Norme I, du résidu

llb - Au~llol~

0.98 x IO-^

2.98 x IO-^

0.82 x

0.56 x IO-^

Nombre de flops

x I O 6

11.49

Précond

134.2

2 452

29 080

SSOR

Jacobi

L

Nombre

d'itérations

88

230

Norme 2, du résidu

llb - Au~llm

Nombre

de flops

3.54 x

1.22 x IO-"

2.572 x l o g 3.913 x log

CHAPITRE 3. RÉSOLUTION NUIMÉRIQ QUE DU PROBLÈME DE STOKES 114

FIG. 3.14 - Solution en pression pour le problème de la jonction de deux cylindres résolu

par Arrow-Hurwicz avec un préconditionnement SSOR.

FIG. 3.15 - Solution en vitesse pour le problème de la jonction de deux cylindres résolu

par Arrow-Hurwicz avec un préconditionnement SSOR

C W I T R E 3. -R.&WLUTION NUIMÉRIQQUE DU PROBLÈME DE STOKES

Graphique de convergence de la methode Arrow-Hurwin preconditionnee par SSOR pour le problene de la jonction des deux cylindres

Nombre d'iterations

FIG. 3.16 - Graphique de convergence pour le problème de la jonction de deux cylindres

résolu par Arrow-Hurwicz avec un préconditionnement SSOR

jonction des deux cylindres résolu par la méthode de how-Hurwicz avec un précondition-

nement SSOR. On y voit deux courbes : la première, en pointillée, est celle du logarithme

en base 10 de la norme du résidu préconditionné (logIo (11 M-'(b - Ax) Il2)) en fonction

du nombre d'itérations (= $ nombre de produits matrice-vecteur). L'autre courbe (trait

plein) est celle du logarithme en base 10 de la norme Z2 du résidu (loglo (llb - Axl12))

en fonction du nombre d'itérations. On remarque une certaine décroissance de la norme

du résidu lorsque le nombre d'itérations augmente. Toutefois, cette décroissance est loin

d'être monotone car il y a présence de nombreux sauts. Ces sauts réfiètent Ie comporte-

ment erratique de la convergence de la méthode utilisée comme nous avions mentionné à

la fin de la section 3.1.

Problème de la contraction 3D

Comme on l'a fait pour le problème de la jonction des deux cylindres, on peut comparer

le problème de la contraction 3D (141 674 DDLs) avec le maillage CUBE4 (112 724 DDLs)

qui ont un nombre de degrés de libertés compafable. Ainsi, on voit que le nombre d'opéra-

tions et d'itérations pour une méthode et un préconditionnement donnés pour obtenir une

précision similaire sont du même ordre de grandeur. Par ailleurs, la méthode de Arrow-

Hurwicz préconditionnée par SSOR nous donne le nombre d'itérations et d'opérations les

moins élevés.

Nous pouvons visualiser sur les figures 3.17 et 3.18, les solutions en pression et en vitesse

respectivement.

3.3.2 Résultats numériques à l'aide de l'élément de Mini

Pour la discrétisation Mini, nous avons utilisé 1'algorithmeMINRES préconditionné par

Jacobi qui fut proposé pour la première fois par Silvester et Wathen [19] dans le contexte

du problème de Stokes avec des formulations stabilisées. Par la suite, Coupez et Marie [6j

et [7] ont utilisé cette méthodologie pour des problèmes tridimensionnels de grande taille

CHAPITRG 3. SOLUTION NUMÉHQUE DUPROBLEME DE STOKES 117

FIG. 3.17 - Solution en pression pour le problème de la contraction3D résolu par h o w -

H m i c z avec un préconditionnement SSOR.

FIG. 3.18 - Solution en vitesse pour le problème de la contraction3D résolu par Arrow-

Hurwicz avec un préconditionnement SSOR.

CHAPITRE 3. RÉSOLUTION NUMÉRIQUE DU PROBLÈME DE STOKES 118

TAB. 3.19 - Problème de la contraction 3D pour l'élément Taylor-Hood.

dans le domaine des polymères fondus.

Problème de la contraction 3D

Méthode MINRES

Méthode MINRGS (Élément Mini)

Préconditionnernent Jacobi

Nombre de

flops

1.071 x 1oLo

1.805 x lo10

9.424 x 10'

1.941 x 10''

Méthode

1

MINRES


N

-- --

Norme Z, du résidu Nombre de %ops

x IO6

A.rrow-Hurwicz

Norme I, du résidu

- AuNII,

9.01 x IO-'

5.64 x 10-~

Précond

SSOR

Jacobi

TAB. 3.20 - Problème de la cavité 3D résolu par lLlINRES avec un préconditionnement

Jacobi.

Nombre

d'itérations

207

599

Dans les tableaux 3.20, 3.21, 3.22 et 3.23 on retrouve les résultats obtenus lors de la

résolution des différents problèmes tests pour l'élément Mini. En regardant la norme du

résidu, on peut dire que les solutions approchées sont sufEsamment précises et comparables

2.11 x 10-~

3.41 x 10-~

SSOR

Jacobi

182

644

7 Méthode MINRES (Élément Mini)

Nombre de flops

x 106


T~B. 3.21 - Problème de la conduite à section carrée résolu par I'vIINRES avec un pré-

conditionnement Jacobi.

Maillage

Méthode MINRES (Mément Mini)

Préconditionnement Jacobi U

Norme 1- du résidu Nombre de flops


TAB. 3-22 - Problème de la jonction de deux cylindres résolu par MINRES avec un

Norme 1, du résidu

préconditionnement Jacobi.

-- -

Méthode MINRES (Élément Mini)

TAB. 3.23 - Problème de la contraction 3D resolu par MINRES avec un préconditionne-

ment Jacobi.


Nombre de flops

x IO6

Maillage NbIter

IV

Norme 1, du résidu

Ilb - A ~ ~ l l m

à celles obtenues lors des tests pour l'élément Taylor-Hood. Sur les tableaux 3.20 et 3.21

qui contiennent respectivement les informations pour le problème de la cavité et de la

conduite à section carrée, on peut m e r que le coût est plus élevé que celui de la

méthode Ar row-Hhcz préconditionnée par SSOR pour un problème de même ordre de

grandeur. Par exemple, en comparant le problème CUBE4 (112 724 DDLs) discrétisé par

Pz - Pl résolu par Arrow-Hurwicz préconditionné par SSOR avec le problème CUBES

(143 748 DDLs) discrétisé par Mini, on a que Nb f ~ ~ s ~ ~ ~ E ~ ~ ~ ~ ~ 2NbFlopscvBE4,-,

(voir tableau 3.14).

Aux figures 3.19 et 3.20, on a fait des graphiques du nombre de Bops en fonction du

a, ion. nombre de degrés de liberté pour comparer plus justement les deux types de discrétis t'

Nous comparons les résultats de l'élément Pz - PL obtenu avec la méthode dYArrow-

Hurwicz préconditionnée par SSOR (meilleurs résultats en Pz - Pl) et ceux obtenu pour

l'élément Mini en utilisant la méthode MTNRES préconditionnée par Jacobi pour le pro-

blème de la cavité 3D et de la conduite a section carrée. Sur ces graphiques, on peut

voir que la courbe pour l'élément Mini est toujours située au-dessus de la courbe pour

l'élément Ps -Pi, sauf éventuellement pour de petits maillages. De plus, la distance entre

les deux courbes augmente considérablement lorsque les maillages grossissent. Par consé-

quent, il semble que l'utilisation de l'élément P2 - Pl avec la méthode Arrow-Hurwicz

préconditionnée par SSOR est moins coûteuse que l'utilisation de l'élément Mini résolue

par la méthode MINRES préconditionnée par Jacobi.

Pour le problème de la jonction des deux cylindres, le nombre d'opérations pour CY-

LINDRES2 figurant dans le tableau 3.22 nous permet de dire que le coût de la méthode

MINRES appliquée sur la discrétisation Mini semble plus coûteuse que la méthode A.rrow-

Humicz préconditionnée par SSOR si on compare le nombre d'opérations avec celui de

CYLINDRES1 au tableau 3.18 qui est du même ordre de grandeur (voir le tableau 3.3).

On peut tirer la même conclusion en comparant les résultats des tableaux 3.19 et 3.23 pour

Graphique du nombre de flops en fonction du nombre de degres de hiberte

FIG. 3.19 - Comparaison entre le nombre de flops en fonction du nombre de degrés de

liberté de la discrétisation Mini et P2 - f i pour le problème de la cavité 3D.

le problème de la contraction. En effet, Nb f l ~ p ~ ~ ~ ~ ~ ~ ~ ~ ~ , ~ '= 2.7Nb f ~opsCon~3nlp2-pi .

3.4 Out ils informatiques utilisés

Dans cette section, nous discuterons brièvement des principaux logiciels informatiques

qui nous ont permis d'effectuer les tests numériques que nous venons d'exposer à la section

précédente. D'abord, les algorithmes utilisés ont été codés dans le logiciel de recherche

du Groupe Interdisciplinaire de Recherche en Éléments Finis (GIREF) nommé MEF++

pour Méthode d'Éléments Finis en Cf+. Il s'agit d'un outil de calcul très complexe

permettant la résolution des équations aux dérivées partielles par la méthode des éléments

finis. Plusieurs membres du GIREF travaillent au développement de ce code depuis 1995

CHAPITRE 3. RÉSOLUTION NUMEMQUE DU PROBLEME DE STOKES

Graphique du nombre de flops en fonction du nombre de degres de iiberte

FIG. 3.20 - Comparaison entre le nombre de flops en fonction du nombre de degrés de

liberté de la discrétisation Mini et Taylor-Hood pour le problème de la conduite à section

carrée.

soit en tant que membre régulier, associé, stagiaire postdoctoral, employé ou étudiant. La

majorité des membres évoluent à l'université Laval.

Le codage des algorithmes nécessaires aux simulations numériques a été fait à partir de

librairies déjà existantes dans MEF++. Pour la partie algèbre linéaire numérique qui est

centrale dans le mémoire, nous avons utilisé la librairie PETSc (Portable Extensible Tool-

kit for Scientific Computation) développée par L'équipe du laboratoire nationale d'Argonne

(US). Cette dernière comprend des structures de données et des fonctions qui forment les

fonctionnalités de base nécessaires à l'implémentation des codes destinés à résoudre des

problèmes de grandes tailles.

Par ailleurs, nous avons créé les maillages à l'aide du logiciel MEFISTO développé par

Alain Perronnet au laboratoire d'analyse numérique de l'université de Pierre et Marie

Curie. Après avoir obtenu les maillages, nous avons défini les entités géométriques sur

lesquelles se base l'imposition des conditions aux limites pour chacun des problèmes décrits

à la section 3.2 à l'aide du logiciel PreGIREF qui, comme son nom l'indique, a été mis

sur pied par le GIREF.

En terminant, mentionnons que nous avons visualisé les solutions obtenues à l'aide du

logiciel W créé par le CERCA (Centre de recherche en calcul appliqué) de l'université de

Montréal.. Ce logiciel permet de visualiser les solutions sous différentes formes. Les figures

3.14, 3.15, 3.17 et 3.18 sont des images prises avec VU.

Conclusion

Dans ce mémoire, nous avons proposé deux stratégies de résolution itérative du problème

t~dimensionnel de Stokes discrétisé par l'élément mixte quadratique Pz - Pl. La première

stratégie est basée sur l'utilisation de l'algorithme MINRES qui est une méthode de Kwlov

applicable aux matrices symétriques et indéfinies. La deuxième stratégie utilise la méthode

de JLrylov de bi~rthogonalisation, BICGSTAB, pour accélérer une variante de l'algorithme

d7Uzawa connue sous le nom de Arrow-Hurtvicz. Dans les deux cas, nous avons étudié l'effet

de trois types de préconditionnement : LU, SSOR et Jacobi.

Malgré sa robustesse, le préconditionnement LU est beaucoup trop coûteux. En effet,

cela revient à utiliser une méthode directe sur des problèmes de grande taille. Le pré-

conditionnement Jacobi est applicable aux grands systèmes mais le nombre d'itérations

semble croître de façon linéaire avec la taille du maillage, i.e. O(h-') ce qui conduit à un

coût prohibitif pour les gros problèmes. Par contre, les courbes du nombre d'itérations en

fonction de h nous indiquent que l'augmentation du nombre d'itérations est lente dans le

cas où on a recours au préconditionnement SSOR. De plus, cette augmentation semble

plus lente pour un problème donné si on utilise la méthode d7Arrow-Hurmicz. La compa-

raison des coûts entre les deux stratégies de résolution avantage celle d'Arrow-Hurwicz.

Par conséquent, nous recommandons cette méthode préconditionnée par SSOR.

Finalement, nous avons comparé le coût d'une résolution basée sur l'élément quadra-

tique P2 - Pl avec celui d'une résolution basée sur l'élément linéaire P: - Pl aussi connu

sous le nom de Mini. Cette dernière résolution basée sur l'élément Mini est couramment

CONCLUSION 125

utilisée pour les calculs tridimensionnels car elle possède beaucoup moins de degrés de li-

berté comparativement au cas du P2 - Pr. Nous jugeons donc que la comparaison ne doit

pas se faire sur le même maillage mais plutôt sur un maillage deux fois plus fin dans le cas

de l'élément Mini. Sous ce critère, nous avons montré que l'algorithme d'how-Hurcvicz

utilisé avec la discrétisation P2 - Pl et préconditionné par SSOR est plus économique

que l'algorithme MI_sllSRES utilisé avec Ia discrétisation Mini, et il demeure plus précis car

O (h2).

Bibliographie

AmOLD, D. N., BREZZI, F., FORTIN, M., A stable finite element for the Stokes

equations, Calcolo, v. 21 (4), pp. 337-344.

BIRD, R.B ., ARMSTRONG, R.C., HASSAGER O., Dynamics of polymen'c liquids,

Volume 1, Wiley-Interscience, 1987, 649 p.

BREZZI, F., FORTIN, M., Mixed and hybrid finite element rnethods, New York,

Springer-Verlag, 199 1

CAHOUET, J., CHABARD, J.-P., Some fast 3-D finite element solvers for genera-

lized Stokes problem, Rapport EDF HE/41/87.03, 1987

CLMUET, Ph., The Finite Element Method., North HoIland, 1978.

COUPEZ, Thierry, MARIE, Stéphane, From a direct solver to a parallel iterative

solver in 30 fonning simulation, International Journal of Supercornputer and appli-

cations, 11, 1997, pp. 205.

COUPEZ, Thierry, Stable-stabilized finite element for 3D f o n i n g calmlation, Inter-

na1 report, CEMEF, 1996.

DUVAUT, G., Mécanique des milieux continus, MASSON, 1990, 288 p.

GIRAULT, V., R A . . R T , P. A., Finite element approzimations of the Navier-Stokes

equations, Lecture Notes in Mathematics, Springer, 1979.

[IO] HESTENES, M. R., STIELFEL, E. L., Methods of conjugate gradients for solving

Zinear systems, Journal of Research of the National Bureau of Standards, Section B,

Vol. 49, pp. 409-436, 1952.

BIBLIOGRAPHIE 127

[Il] JOHNSON, Claes, Numerical Solutions of Partial Differential Equations by the Finite

Element Method, Cambridge University Press, Cambridge, UK, 1987.

[12] MARCOTTE, J- P., Méthodes itératives pour la résolution d u problème de Stokes

non linéaire, École Polytechnique de Montréal, Juin 2000.

[13] MARSDEN, J., HUGHES, T. J.R., A short course in fluid mechanics, Publish or

Perish, Boston, 1976.

[14] PIERRE, RogeqSimple Co approximations for the computation of incompressible

flous, Comput. Methods Appl. Mech. Engrg., Vol. 68, 1988, pp. 205-227.

[15] PIRO-JNl3AU7 Olivier, Méthode des éléments pour les fluides, M4SSON, 1988.

[16] SAAD, Y., Iterative methods for sparse linear systems, PWS Publishing Company,

1996.

[17] SAAD, Y., SCHULTZ, M. H., GMRES : a generalzzed minimal residual algorithm

for solving nonsymmetric Zinear systems, S I A M Journal on Scientific and Statistical

Cornputing, Vol. 7 , pp. 856-869, 1986.

[18] SONXEVELD, P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems,

S IAM Jourrial on Scientfic and Statistical Computing, Vol. 10 ( l ) , pp. 36-52, 1989.

[19] SILVESTER, David J. , WATHEN, Andrew J., Fast iterative solution of stabilized

Stokes systerns. Part 1 : Using simple diagonal preconditioners, SLOf J. Numer.

Anal-, Vol- 30, 1993, pp.630-649.

[20] SILVESTER, David, WATHEN, Andrew, Fast iterative so h t ion of stabilized Stokes

systems. Part II : Using general block preconditioners,SLAld J. NUMER. ANAL., Vol.

31, 1994, pp.1352-1367.

1211 VAS DER V O R S T , H., Bi-CGSTAB : a fast and smoothly converging variant of Bi-

CG f o r the solution of non-symrnetric Zinear system, S I A M Journal on Scientific and

Statistical Cornputing, Vol. 12 , 1992, pp.631-644.

Documents

collectionscanada.gc.cacollectionscanada.gc.ca/obj/s4/f2/dsk3/ftp04/MQ57870.pdf · Résumé Ce mémoire porte sur la résolution itérative du problème tridimensionnel de Stokes