Décomposer et itérer pour résoudre un problème
« Diviser pour mieux régner » dans le cas des équations aux dérivées partielles
Hors piste Le 24 décembre 2018 Voir les commentaires (1)
Une idée souvent utilisée en pratique pour calculer la solution d’un problème mathématique compliqué est de résoudre une succession de problèmes plus simples. On pourrait qualifier cette approche intuitive de « résolution par tâtonnements », mais nous allons voir que ce type de procédé peut être rendu systématique, étudié rigoureusement et s’avérer très efficace.
Il arrive parfois que l’on rencontre un problème d’apparence si complexe que l’on ne sache même pas quelle suite d’étapes, même compliquées, pourrait permettre de le résoudre. Une approche générale existe cependant pour contourner cette difficulté : essayer de trouver au sein du problème un ou plusieurs sous-problèmes ayant pour caractéristiques d’être faciles et peu coûteux à résoudre et de pouvoir être intégrés dans une boucle. On peut alors se lancer dans la résolution itérative de la suite éventuellement infinie de ces sous-problèmes. Considérant la question de la stratégie de mise en œuvre réglée et revenant au point de vue des mathématiques, il reste alors à étudier la convergence d’un tel procédé. Si cette dernière a lieu, elle doit permettre de construire la solution du problème initial.
Nous présentons dans cet article différentes déclinaisons de ce procédé, en nous concentrant sur la résolution numérique, c’est-à-dire au moyen d’un calculateur, de problèmes et la construction de sous-problèmes par décomposition. Nous expliquons également comment le formalisme mathématique offre un cadre efficace pour attaquer la question de la convergence.
La résolution itérative sur des exemples
Le principe auquel on va s’intéresser concerne les situations où l’on sait décomposer un problème en une suite de sous-problèmes pouvant chacun être facilement résolu. Lorsque chaque sous-résolution améliore (en un sens à définir au cas par cas) l’approximation de la solution, on peut espérer, en les répétant de manière cyclique un nombre suffisant de fois, arriver à la solution du problème initial. Quand c’est le cas, on constate que la décomposition en sous-problèmes a permis de simplifier les choses. Le prix à payer est cependant d’avoir construit une procédure itérative (engendrant éventuellement une infinité d’itérations).
Une devinette
Commençons par introduire les ingrédients d’une telle méthode sur un premier exemple. Pour cela, on s’intéresse à la question suivante : comment compléter la phrase
« Cette phrase est composée de ... consonnes et de ... voyelles. »
pour la rendre logiquement correcte ?
En suivant une approche par tâtonnements, on commence par compter les consonnes et les voyelles de la phrase contenant les points de suspension, que l’on complète alors avec les deux nombres obtenus pour arriver à :
« Cette phrase est composée de vingt-six consonnes et de dix-neuf voyelles. ».
Évidemment, cette nouvelle phrase est fausse, mais on peut néanmoins y compter les consonnes et les voyelles et la modifier pour tenter de corriger l’erreur. En répétant cette opération tant que la phrase reste fausse, on obtient alors successivement :
« Cette phrase est composée de trente-six consonnes et de vingt-quatre voyelles. »
« Cette phrase est composée de trente-neuf consonnes et de vingt-six voyelles. »
« Cette phrase est composée de trente-huit consonnes et de vingt-cinq voyelles. »
« Cette phrase est composée de trente-neuf consonnes et de vingt-cinq voyelles. »
et l’on aboutit à un résultat correct au bout de cinq essais. On observe qu’on a effectivement pu répondre à la devinette en considérant à chaque étape deux sous-problèmes très faciles à résoudre, consistant simplement à compter les consonnes et les voyelles de la phrase courante [1]. On est donc bien en présence d’un exemple de méthode par tâtonnements, que l’on peut qualifier plus précisément de méthode d’approximations successives : elle est en effet basée d’une part sur la résolution de problèmes « simples » et d’autre part sur la notion de point fixe, l’argument d’entrée d’une itération (une phrase) étant du même type que l’argument de sortie.
Observons que l’on aurait pu choisir de procéder autrement à chaque étape en comptant tout d’abord le nombre de consonnes dans la phrase courante, en insérant ce compte dans la phrase, puis, dans un second temps, en comptant le nombre de voyelles dans la phrase résultante. Dans ce cas, le comptage du nombre de voyelles intervient nécessairement après celui du nombre de consonnes et la suite des phrases construites après chaque cycle de deux comptages est la suivante :
« Cette phrase est composée de vingt-six consonnes et de vingt-et-une voyelles. »
« Cette phrase est composée de trente-huit consonnes et de vingt-sept voyelles. »
« Cette phrase est composée de trente-neuf consonnes et de vingt-cinq voyelles. »
Trois essais ont cette fois suffi pour arriver à une phrase logiquement correcte.
Nous avons donc décrit deux versions d’une technique de résolution de la devinette. La première est souvent qualifiée de parallèle, les comptages des consonnes et des voyelles pouvant être effectués simultanément, c’est-à-dire en parallèle. La seconde version est dite séquentielle, dans le sens où le comptage d’un type de lettre ne peut être entrepris qu’une fois réalisé le comptage de l’autre type de lettre, c’est-à-dire à la suite l’un de l’autre. C’est ce vocabulaire que nous emploierons dans le reste de l’article.
Résolution d’un système linéaire
Passons à présent à un problème mathématiquement plus courant : celui de la résolution d’un système d’équations linéaires, comme le système de trois équations linéaires à trois inconnues suivant :
\[ \left\{\begin{aligned} 4\,x_1+ 2\,x_2 -x_3&=5\\ x_1+ 2\,x_2+x_3&=4\\ x_1+x_2+4\,x_3&=6 \end{aligned}\right. \]
dont une solution est $x_1=x_2=x_3=1$, mais cela n’est pas ce qui nous intéresse ici. Une méthode classique pour déterminer la solution de ce problème de manière « directe », c’est-à-dire de manière systématique et avec un nombre fini d’opérations arithmétiques (addition, soustraction, multiplication ou division), est donnée par le fameux procédé d’élimination de Gauss (1809), mais il est aussi possible de considérer une technique qualifiée d’« itérative » : la méthode de Jacobi [Jac1845]. Pour expliquer son fonctionnement, on commence par réécrire le système ci-dessus en isolant une inconnue par équation de la manière suivante :
\[ \left\{\begin{aligned} x_1&=\frac{1}{4}\left(5 - 2x_2+x_3\right)\\ x_2&=\frac{1}{2}\left(4 - x_1- x_3\right)\\ x_3&=\frac{1}{4}\left(6 - x_1- x_2\right) \end{aligned}\right. \]
et l’on introduit ensuite trois suites réelles récurrentes $(x_1^{(k)})_{k\in\mathbb{N}}, (x_2^{(k)})_{k\in\mathbb{N}}$ et $(x_3^{(k)})_{k\in\mathbb{N}}$ définies, à partir de valeurs $x_1^{(0)}$, $x_2^{(0)}$ et $x_3^{(0)}$ données, par les formules de récurrence suivantes :
\[ \begin{aligned} x_1^{(k+1)}&=\frac{1}{4}\left(5-2\,x_2^{(k)} +x_3^{(k)}\right)\\ x_2^{(k+1)}&=\frac{1}{2}\left(4-x_1^{(k)} -x_3^{(k)}\right)\\ x_3^{(k+1)}&=\frac{1}{4}\left(6-x_1^{(k)}-x_2^{(k)}\right) \end{aligned}\ k=0,1,2,\dots \]
L’indice entier $k$ correspond au nombre d’itérations effectuées dans le processus itératif et, bien qu’il soit mathématiquement destiné à tendre vers l’infini, il restera, comme on va le voir, fini en pratique.
Le calcul des termes des suites est particulièrement aisé en raison de la décomposition faite sur le système et l’on peut tester le procédé avec une simple calculatrice en choisissant (par exemple) comme valeurs de départ $x_1^{(0)}=x_2^{(0)}=x_3^{(0)}=0$. Le tableau ci-dessous contient les valeurs des approximations numériques successivement obtenues (on n’indique que cinq chiffres après la virgule) :
Itération $k$ | $x_1^{(k)}$ | $x_2^{(k)}$ | $x_3^{(k)}$ |
1 | 1,25000 | 2,00000 | 1,50000 |
2 | 0,62500 | 0,62500 | 0,68750 |
3 | 1,10940 | 1,34380 | 1,18750 |
4 | 0,87500 | 0,85156 | 0,88672 |
5 | 1,04590 | 1,11910 | 1,06840 |
6 | 0,95752 | 0,94287 | 0,95874 |
7 | 1,01820 | 1,04190 | 1,02490 |
8 | 0,98529 | 0,97842 | 0,98497 |
9 | 1,00700 | 1,01490 | 1,00910 |
10 | 0,99483 | 0,99195 | 0,99452 |
11 | 1,00270 | 1,00530 | 1,00330 |
12 | 0,99817 | 0,99702 | 0,99801 |
13 | 1,00100 | 1,00190 | 1,00120 |
14 | 0,99934 | 0,99890 | 0,99927 |
15 | 1,00040 | 1,00070 | 1,00040 |
16 | 0,99976 | 0,99960 | 0,99974 |
17 | 1,00010 | 1,00030 | 1,00020 |
18 | 0,99991 | 0,99985 | 0,99990 |
On observe que les valeurs des suites tendent vers la valeur $1$ à la précision affichée, qui correspond effectivement à la valeur de $x_1$, $x_2$ et $x_3$ satisfaisant le système d’équations introduit plus haut. On dit que la méthode itérative converge.
On peut encore remarquer que, à chaque étape, les calculs respectifs des termes des suites à une étape donnée ne font intervenir que des valeurs obtenues à l’étape précédente : on peut donc les calculer de manière simultanée. On est en présence d’une méthode parallèle.
Comme on l’a fait pour le problème de la devinette, on peut trouver une variante séquentielle à la méthode de Jacobi. Il s’agit de la méthode de Gauss-Seidel [Gau1823,Sei1874], dont les formules de récurrence sont :
\[ \begin{aligned} x_1^{(k+1)}&=\frac{1}{4}\left(5-2x_2^{(k)}+x_3^{(k)}\right)\\ x_2^{(k+1)}&=\frac{1}{2}\left(4 -x_1^{(k+1)} -x_3^{(k)}\right)\\ x_3^{(k+1)}&=\frac{1}{4}\left(6 -x_1^{(k+1)} -x_2^{(k+1)}\right) \end{aligned}\ k=0,1,2,\dots \]
En inspectant ces relations, on peut remarquer que le calcul de $x_2^{(k+1)}$ ne peut maintenant se faire qu’une fois la valeur de $x_1^{(k+1)}$ obtenue. De la même manière, le calcul de $x_3^{(k+1)}$ n’est possible que si les valeurs de $x_1^{(k+1)}$ et de $x_2^{(k+1)}$ sont connues. La méthode est donc bien séquentielle. Pour l’exemple considéré, elle conduit aussi à la solution du système. En utilisant la même initialisation que précédemment, on obtient en effet les approximations numériques suivantes (là encore, on n’indique que cinq chiffres après la virgule) :
Itération $k$ | $x_1^{(k)}$ | $x_2^{(k)}$ | $x_3^{(k)}$ |
1 | 1,25000 | 1,37500 | 0,84375 |
2 | 0,77344 | 1,19141 | 1,00879 |
3 | 0,90649 | 1,04236 | 1,01279 |
4 | 0,98202 | 1,00260 | 1,00385 |
5 | 0,99966 | 0,99825 | 1,00052 |
6 | 1,00101 | 0,99923 | 0,99994 |
7 | 1,00037 | 0,99985 | 0,99995 |
8 | 1,00006 | 1,00000 | 0,99999 |
9 | 1,00000 | 1,00001 | 1,00000 |
10 | 1,00000 | 1,00000 | 1,00000 |
La convergence observée se trouve même être plus rapide que celle de la méthode de Jacobi [2].
L’usage de l’une ou l’autre ces deux méthodes se généralise facilement à tout système linéaire possédant autant d’équations que d’inconnues et une unique solution. Il est cependant important de remarquer que la convergence de tels procédés n’est a priori pas acquise. Pour le voir, ordonnons différemment les équations du système linéaire considéré plus haut :
\[ \left\{\begin{aligned} x_1+ 2\,x_2+x_3&= 4\\ x_1+x_2+4\,x_3&= 6\\ 4\,x_1+ 2\,x_2 -x_3&=5 \end{aligned}\right. \]
Cette opération ne change bien évidemment pas la solution du système. Appliquons à présent la méthode de Jacobi à la résolution du système réordonné à partir de l’initialisation $x_1^{(0)}=x_2^{(0)}=x_3^{(0)}=0$. Les approximations numériques successivement obtenues sont alors
Itération $k$ | $x_1^{(k)}$ | $x_2^{(k)}$ | $x_3^{(k)}$ |
1 | 4 | 6 | -5 |
2 | -3 | 22 | 23 |
3 | -63 | -83 | 27 |
4 | 143 | -39 | -423 |
5 | 505 | 1555 | 489 |
6 | -3595 | -2455 | 5125 |
7 | -211 | -16899 | -19295 |
8 | 53097 | 77397 | -34647 |
9 | -120143 | 85497 | 367177 |
10 | -538167 | -1348559 | -309583 |
On observe que le comportement de la suite est très différent de ce qu’il était dans le cas précédent. On n’approche effectivement plus la solution, les valeurs absolues des quantités calculées tendant même vers l’infini avec le nombre d’itérations effectuées. Le même phénomène se produit avec la méthode de Gauss-Seidel.
Dans ces conditions, comment savoir que la méthode fonctionnera ou pas ? La réponse est donnée par le domaine des mathématiques portant le nom d’analyse numérique, qui est dédié à l’étude des diverses méthodes numériques proposées depuis des siècles pour résoudre des problèmes de natures variées. Il existe ainsi des théorèmes fixant des conditions sur le système linéaire garantissant la convergence vers la solution des suites d’approximations construites par les méthodes de Jacobi ou de Gauss-Seidel.
En pratique, les méthodes itératives constituent une alternative aux méthodes directes comme l’élimination de Gauss, ces dernières pouvant s’avérer trop coûteuses en termes d’espace mémoire pour être mises en œuvre lorsque la taille du système à résoudre est grande. Elles s’avèrent aussi plus résilientes à l’accumulation des erreurs d’arrondi (inévitable lorsque que les calculs sont effectués dans une arithmétique en précision finie) que certaines méthodes directes.
Le lecteur pourra être interpellé par le fait qu’un nombre infini d’opérations arithmétiques est a priori nécessaire pour calculer la solution du système. En pratique, ceci n’est jamais un problème : les calculs étant effectués dans une arithmétique en précision finie, une solution approchée suffisamment précise sera indistinguable de la solution exacte telle que représentée sur la machine et l’on peut donc mettre fin au procédé après un nombre fini d’itérations, par exemple dès que l’approximation de la solution n’est plus modifiée significativement ou plus simplement dès qu’une précision attendue est atteinte.
« Diviser pour régner »
Nous venons de voir comment un procédé itératif et une décomposition adaptée d’un problème peuvent donner lieu à des méthodes de résolution efficaces. Cette manière d’attaquer la résolution d’un problème complexe est aujourd’hui classique et le lecteur averti aura peut-être reconnu le principe fondateur du paradigme « diviser pour régner », qui est à la base de nombreuses méthodes de traitement de données en informatique.
Décomposition de domaine et décomposition de frontière
Nous allons maintenant montrer comment ces approches itératives peuvent être mises à profit pour résoudre certaines équations aux dérivées partielles. Pour cela, on exploite de manière cruciale la linéarité des équations du problème considéré : au travers de ce que l’on appelle un principe de superposition, cette propriété rend en effet possible l’écriture de la solution du problème sous la forme d’une somme de solutions de sous-problèmes qui lui sont liés.
La méthode de Schwarz
Considérons tout d’abord une méthode inventée en 1870 par Hermann Schwarz [4] pour démontrer l’existence d’une solution au problème de Dirichlet posé dans un domaine consistant en l’union d’un carré et d’un disque se chevauchant partiellement [Sch1870]. Dans ce problème, l’inconnue est une fonction satisfaisant une équation aux dérivées partielles appelée équation de Laplace [5].
Schwarz eut l’idée d’utiliser le fait que des solutions du problème de Dirichlet dans des domaines de géométrie simple (comme le carré et le disque) étaient explicitement connues de longue date [6]. Il construisit ainsi une solution du problème sur tout domaine décomposable en sous-domaines « simples » en alternant des résolutions sur chacun de ces derniers et en combinant les solutions obtenues.
Si la motivation initiale de cette technique de décomposition de domaine était avant tout théorique, sa généralisation à la résolution d’autres problèmes que ceux liés à l’équation de Laplace et son étude mathématique réalisée avec des outils modernes d’analyse fonctionnelle lui firent par la suite connaître un renouveau en tant que méthode numérique à partir des années 1960. Elle est à ce jour, suite à de nombreuses extensions, un sujet de recherche actif en analyse numérique et en calcul scientifique.
La méthode des réflexions
- Séquence d’images de sphères de polymères qui sédimentent dans un tube étroit (10 fois le diamètre des sphères).
La méthode des réflexions est une consœur de la méthode de Schwarz, qui reste cependant moins connue de la communauté mathématique que cette dernière. En revanche, elle est depuis plusieurs décennies présente dans les ouvrages traitant de micro-hydrodynamique, domaine de la physique traitant des écoulements à petite échelle.
Elle fut introduite en 1911 par le physicien polonais Marian Smoluchowski pour étudier le phénomène de sédimentation en déterminant les vitesses respectives de $n$ particules solides de petite taille en suspension dans un fluide visqueux et soumises à des efforts extérieurs (typiquement l’action de la gravité) [Smo1911]. Le problème mathématique sous-jacent, parfois appelé problème de mobilité [7], fait alors intervenir un système d’équations aux dérivées partielles portant le nom d’équation de Stokes stationnaire.
Dans ses investigations, Smoluchowski souhaitait arriver par le biais de la modélisation mathématique à quantifier l’effet sur l’écoulement des interactions hydrodynamiques entre les particules solides, phénomène observé expérimentalement. Or, si la solution du problème à une seule particule était connue depuis les travaux de Stokes sous la forme d’une expression plus ou moins simple mais néanmoins explicite [8], il ne disposait d’aucun outil de calcul permettant de traiter le cas d’un nombre arbitraire de particules. Inspiré par la méthode des images en électromagnétisme, il proposa un procédé itératif d’approximation de la solution utilisant uniquement la résolution de problèmes ne faisant chacun intervenir qu’une seule particule.
Pour cela, son idée était de partir d’un écoulement ne contenant aucune particule et de le corriger progressivement de manière à ce que la vitesse du fluide soit tour à tour égale à la vitesse du bord de chacune des particules. Dans le cadre de la mécanique des fluides, cette correction s’apparente à la réaction (ou réflexion) d’une particule placée dans un écoulement donné, ce qui explique le nom donné à la méthode.
- Gennadi Michailowitsch Golusin
Chaque nouvelle correction sur une particule vient perturber la vitesse sur toutes les autres particules et l’on est donc amené à parcourir l’ensemble du système de particules considéré de manière cyclique et récurrente pour tenter de reconstruire les interactions hydrodynamiques absentes des problèmes à une particule qui sont résolus.
Ce faisant, la méthode des réflexions décrite par Smoluchowski suit un principe itératif séquentiel permettant de résoudre un problème posé dans un domaine dont la frontière possède plusieurs composantes d’un seul tenant bornées (en d’autres termes, le domaine présente des « trous » et est dit non simplement connexe), modélisant les bords de particules, d’obstacles ou plus généralement d’« objets » présents. Une variante parallèle de la méthode fut introduite indépendamment par Golusin en 1934 [Gol1934] et appliquée à la résolution d’un problème de Dirichlet dans un tel domaine.
Une caractéristique de la méthode des réflexions la rend intéressante d’un point de vue pratique. Dans cette méthode, la frontière du domaine sur lequel est posé le problème est en effet décomposée en tenant compte des bords respectifs des objets. On parle de décomposition de frontière en composantes connexes. Nous avons ainsi vu que les sous-problèmes résolus au cours d’un cycle de la méthode ne font intervenir qu’un objet et donc une seule composante du bord à la fois. Ceci est particulièrement adapté à l’utilisation de formulations du problème basées sur la représentation intégrale de sa solution. Cette technique se sert du fait que, pour certains problèmes, la valeur de la solution en tout point intérieur du domaine est donnée par celle d’une intégrale ne faisant intervenir que ses valeurs (et celles de sa dérivée normale) au bord du même domaine. En se servant d’une telle représentation, il est possible de reformuler le système d’équations aux dérivées partielles du problème considéré en un système équivalent d’équations intégrales, chacune étant relative à l’une des composantes de la frontière. Dans ce cas particulier, l’utilisation de la méthode des réflexions consiste à résoudre itérativement le système obtenu en considérant une à une ces équations intégrales, comme on l’avait fait avec les équations algébriques du système linéaire en début d’article, et en procédant comme dans la méthode de Gauss-Seidel (pour la version de Smoluchowski) ou de Jacobi (pour la version de Golusin).
On notera pour finir qu’à l’époque de son introduction, bien antérieure à l’apparition des premiers calculateurs électroniques, la méthode des réflexions permettait, pour une valeur du nombre d’objets $n$ de quelques unités et en n’effectuant que deux ou trois cycles au total, de produire un développement en série tronqué de la solution en accord avec les résultats expérimentaux disponibles en micro-hydrodynamique. Elle a connu ces dernières années diverses applications numériques mais aussi théoriques, puisqu’elle a servi d’outil de démonstration constructive d’existence de solution. Comme c’est souvent le cas pour une « bonne » méthode, elle a même été réinventée au début des années 2000 pour résoudre des problèmes de diffraction multiple [Bal1997,Bal2004].
L’intérêt de la formalisation et de l’analyse mathématique
Les méthodes de Schwarz et des réflexions présentent certaines similarités, comme un caractère itératif ou le recours à une décomposition géométrique du domaine, mais ce ne sont pas les mêmes méthodes. L’un des points forts des mathématiques est de proposer des formalisations qui permettent de s’affranchir des cas particuliers, ouvrant la voie à une analyse générale s’appliquant dans de nombreuses situations. Pour comprendre comment ce principe permet de relier les deux méthodes, concentrons-nous sur une interprétation abstraite de la méthode des réflexions faisant appel à deux outils déjà connus : la méthode des projections orthogonales d’une part et la méthode des projections alternées d’autre part.
La première idée consiste à voir la fonction solution de chaque problème aux limites résolu comme le résultat de la projection d’une fonction liée aux données du problème. On a en effet dit plus haut qu’une réflexion modifiait les valeurs de l’approximation courante de la solution pour que cette dernière vérifie la condition aux limites imposée au bord de l’objet associé. On peut aisément se convaincre qu’une telle opération est idempotente, c’est-à-dire que l’effectuer une ou plusieurs fois conduit au même résultat, et qu’elle est par conséquent une projection, au sens algébrique du mot. En concevant ainsi les choses, on ramène la méthode de Smoluchowski à l’application cyclique de projecteurs, chacun étant associé à un objet, à une approximation initiale de la solution. La méthode entre alors dans le cadre de la méthode des projections alternées et il ne reste qu’à faire appel aux résultats déjà existants pour cette dernière pour prouver sa convergence.
Détaillons davantage ce dernier point. On sait depuis un travail de John von Neumann dans les années 1930 [Neu1949] que la projection orthogonale sur l’intersection de deux sous-espaces peut être obtenue en projetant orthogonalement sur un sous-espace, puis sur l’autre de façon répétée. On peut illustrer ce fait de la manière suivante. Supposons que l’on veuille déterminer le point d’intersection, noté $I$, de deux droites $(d1)$ et $(d2)$ du plan en ne disposant que d’une approximation $I^{(0)}$ de ce point et en ne sachant que projeter orthogonalement un point quelconque du plan sur l’une ou l’autre de ces droites. Dans ce cas, on projette $I^{(0)}$ sur $(d1)$, puis sur $(d2)$ pour obtenir le point $I^{(1)}$, on réitère le procédé avec le point $I^{(1)}$ et ainsi de suite...
- Détermination du point d’intersection de deux droites sécantes par la méthode des projections alternées
On se convainc aisément, en observant la figure ci-contre, que la suite $(I^{(k)})_{k\in\mathbb{N}}$ des points construits de cette manière converge vers le point $I$.
Le procédé de von Neumann a été généralisé à un nombre fini de projecteurs par Israel Halperin dans les années 1960 [Hal1962] et s’applique à d’autres espaces que le plan géométrique et d’autres sous-espaces que des droites géométriques, puisqu’on peut l’utiliser dans des espaces fonctionnels de dimension infinie. Par ce biais, on a trouvé un moyen de ramener la preuve de convergence de la méthode des réflexions à celle de l’orthogonalité d’un projecteur. Ajoutons que si cette approche ne fonctionne pas avec la version de Golusin du procédé, il est néanmoins possible de modifier légèrement cette dernière pour parvenir à la même conclusion.
Cette technique de formalisation s’avère suffisamment générale pour avoir été utilisée par Pierre-Louis Lions vers la fin des années 1980 afin de donner une preuve variationnelle de convergence de... la méthode de Schwarz [Lio1988].
Décomposition de domaine, diversité des techniques et nouveaux enjeux
Les différentes méthodes que nous venons de passer en revue se servent toutes d’une décomposition pour résoudre de manière itérative un problème considéré comme trop compliqué ou trop coûteux pour être abordé directement. Elles permettent en pratique d’obtenir des approximations de la solution du problème, car on ne peut généralement pas réaliser la totalité des itérations conduisant à la solution, en particulier lorsque cette dernière n’est obtenue qu’à l’issue d’un nombre infini de ces itérations. La convergence du procédé itératif utilisé est alors certifiée
par l’analyse mathématique, la profondeur des outils mathématiques requis par celle-ci étant bien sûr liée à la nature du problème à résoudre.
Les méthodes de décomposition constituent en soi un champ de recherche complet, engageant aujourd’hui de nombreux chercheurs au sein d’une communauté très active. Les outils mathématiques qui leur sont liés sont variés : la modélisation qui conduit des phénomènes considérés à des systèmes d’équations, l’analyse fonctionnelle pour l’étude de ces équations, l’analyse numérique pour celles des algorithmes de résolution, le calcul scientifique pour leur mise-en-œuvre pratique... On voit que la décomposition de domaine offre en fait une porte d’entrée de choix vers les mathématiques appliquées !
Certains défis actuels concernant la résolution numérique des équations aux dérivées partielles sont apportés par de nouveaux types de décomposition. La décomposition en temps en est un exemple : paralléliser par rapport au temps la résolution d’une équation d’évolution ajoute comme difficulté le fait que l’écoulement du temps est profondément séquentiel, dans le sens où il est difficile de prévoir l’état d’un système dynamique à un certain instant sans avoir connaissance de son état à des instants antérieurs. Un autre exemple de recherche émergente dans ce domaine est le couplage de méthodes de décomposition avec d’autres procédures itératives, issues de l’optimisation par exemple.
Références
[Bal1997]
M. Balabane et V. Tirel, Boundary decomposition for Helmholtz and Maxwell equations 1 : disjoint sub-scatterers, Asymptotic Anal., 38(1), pp. 281—286, 1997.
[Bal2004]
M. Balabane, Boundary decomposition for Helmholtz and Maxwell equations 1 : disjoint sub-scatterers, Asymptotic Anal., 38(1), pp. 281—286, 2004.
[Gau1823]
C. F. Gauss, Lettre du 26 décembre adressée à Christian Ludwig Gerling, 1823.
[Jac1845]
C. G. J. Jacobi, Ueber eine neue Auflösungsart der bei der Methode der kleinsten Quadrate vorkommenden lineären Gleichungen, Astronom. Nachr., 22(20), pp. 297—306, 1845.
[Gol1934]
G. M. Golusin, Auflösung einiger ebenen Grundaufaben der mathematischen Physik im Fall der Laplaceschen Gleichung und mehrfachzusammenhängender Gebiete, die durch Kreise begrenzt sind, Mat. Sb., 41(2), pp. 246—276, 1934.
[Hal1962]
I. Halperin, The product of projection operators, Acta Sci. Math. (Szeged), 23(1-2), pp. 96—99, 1962.
[Lio1988]
P.-L. Lions, On the Schwarz alternating method. I, First international symposium on domain decomposition methods for partial differential equations, SIAM, pp. 1—42, 1988.
[Neu1949]
J. von Neumann, On rings of operators. Reduction theory, Ann. Math. (2), 50(2), pp. 401—485, 1949.
[Sei1874]
P. L. von Seidel, Über ein Verfahren die Gleichungen, auf welche die Methode der kleinsten Quadrate führt, sowie lineare Gleichungen überhaupt, durch successive Annäherung aufzulösen, Abh. Kgl. Bayer Akad. Wiss. Math. Phys. Kl., 11(3), pp. 81—108, 1874.
[Sch1870]
H. A. Schwarz, Ueber einen Grenzübergang durch alternirendes Verfahren, Vierteljahresschr. Naturforsch. Ges. Zürich, 15(3), pp. 272—286, 1870.
[Smo1911]
M. Smoluchowski, Über die Wechselwirkung von Kugeln, die sich in einer zähen Flüssigkeit bewegen, Bull. Int. Acad. Sci. Cracovie, Cl. Sci. Math. Nat., Sér. A Sci. Math., pp. 28—39, 1911.
[Wey1940]
H. Weyl, The method of orthogonal projection in potential theory, Duke Math. J., 7(1), pp. 411—444, 1940.
Les auteurs tiennent à remercier chaleureusement Maxime Chupin, pour son aide et ses suggestions, les relecteurs d’Images des mathématiques Cidrolin, Denis Chadebec, Didier Roche et alainfa, dont les remarques et commentaires ont permis d’améliorer cet article, et enfin Franck Boyer, pour ses apports, son travail d’édition et sa patience.
Notes
[1] Un tel procédé itératif ne converge pas toujours. Que constate-t-on quand on l’applique à la phrase suivante « Cette phrase contient ... consonnes et ... voyelles. » ?
[2] Le fait que la convergence de la méthode de Gauss-Seidel soit plus rapide que celle de la méthode de Jacobi ne signifie pas pour autant que cette dernière est moins efficace en pratique. Dans l’exemple choisi, on a besoin de dix itérations de la méthode de Gauss-Seidel (soit encore un total de trente résolutions d’équation linéaire) pour arriver à une solution approchée ayant cinq chiffres exacts après la virgule, alors que la méthode de Jacobi en nécessite vingt-quatre (c’est-à-dire un total de soixante-douze résolutions d’équation linéaire). Cependant, si l’on dispose, comme c’est aujourd’hui couramment le cas, de plusieurs unités de calcul (machines ou plus simplement processeurs), on peut faire résoudre simultanément à des unités différentes chacune des équations linéaires intervenant dans une itération de la méthode de Jacobi. On parle alors de parallélisation des calculs, expliquant le vocable « parallèle » utilisé pour qualifier la méthode de Jacobi. Une telle parallélisation est impossible dans le cas de la méthode de Gauss-Seidel, pour laquelle les résolutions au cours d’un itération s’enchaînent nécessairement. Par conséquent, en négligeant certains éléments comme le temps de communication entre unités de calcul, une itération de la méthode de Jacobi dure trois fois moins de temps qu’une itération de la méthode de Gauss-Seidel. Si l’on prend donc soin de la paralléliser, la méthode de Jacobi s’avère en pratique 20% plus rapide que la méthode de Gauss-Seidel sur le cas traité, malgré un nombre d’itérations plus que double.
[3] La matrice $A$ étant supposée inversible, il existe toujours une numérotation des inconnues et des équations du système faisant que la matrice $M$ de la décomposition est elle aussi inversible pour l’un ou l’autre de ces choix.
[4] On parle bien du mathématicien ayant donné son nom à une célèbre inégalité.
[5] L’opérateur différentiel apparaissant dans cette équation est le laplacien, défini en coordonnées cartésiennes par $\Delta u=\sum_{i=1}^n\frac{\partial^2 u}{\partial{x_i}^2}$.
[6] Le problème posé dans le carré avait en effet été résolu par Joseph Fourier en 1807 et celui posé dans le disque par Siméon Denis Poisson en 1815.
[7] On aurait pu tout aussi bien chercher à déterminer les forces appliquées connaissant les vitesses des particules. On parle dans ce cas d’un problème de résistance.
[8] Cette expression fait en général apparaître un développement en série, mais, dans certains cas particuliers d’intérêt (comme lorsque la particule est sphérique), ce développement ne contient qu’un nombre fini de termes.
Partager cet article
Pour citer cet article :
Guillaume Legendre, Julien Salomon — «Décomposer et itérer pour résoudre un problème» — Images des Mathématiques, CNRS, 2018
Laisser un commentaire
Actualités des maths
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
Commentaire sur l'article
Décomposer et itérer pour résoudre un problème
le 28 décembre 2018 à 16:53, par Pierre Cami