Introduction à la simulation numérique/Objets des simulations

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Introduction

Nous avons évoqué dans le chapitre introductif précédent les différents domaines d'application des simulations numériques. Nous avons dit qu’elles pouvaient étudier la structure de l'espace, le mouvement de corps, l'évolution de gaz... c'est-à-dire des données physiques — seulement l'ordinateur ne peut manipuler que des données numériques, au mieux des concepts mathématiques.

Il convient ainsi de préciser ce que l'ordinateur utilise pour simuler, donc en quoi consiste, du point de vue informatique, une simulation numérique.

Des lois de la physique

La physique moderne présente le monde en termes d'équations mathématiques. Ces équations peuvent prendre différentes formes, qui déterminent la possibilité, l'efficacité et la profondeur des simulations que l’on peut effectuer.

Équation différentielle, équation intégrale

Les lois de la physique peuvent être écrits de différentes manières, dont certaines sont plus efficaces que d'autres. Prenons l'exemple de l'électromagnétisme : il est régi dans le vide par quatre équations, dites équations de Maxwell. Ces équations prennent deux formes : une forme locale (effectivement due à Maxwell) et une forme intégrale (précédent Maxwell). Pour le champ électrique, par exemple, l'équation locale de Maxwell-Gauss s'écrit :

$\mathrm {div} \,\mathbf {E} =\nabla \cdot \mathbf {E} ={\frac {\rho }{\varepsilon _{0}}}$

La même équation s'écrit également en termes de flux (d'après le théorème de Stokes). Soit une surface fermée S, alors :

$\iint _{S}\mathbf {E} \cdot \mathrm {d} ^{2}\mathbf {S} ={\frac {Q_{\mathrm {int} }}{\varepsilon _{0}}}$

Physiquement, il est toujours possible d'écrire une équation globale, intégrale, sous forme locale. Cela est pratique, mais pas seulement. En effet, une loi intégrale ne se préoccupe pas des mouvements de son contenu. En relativité générale par exemple, on montre qu'aucun objet massif ne peut se déplacer plus vite que la vitesse de la lumière c. La conservation de l'énergie (et la matière est de l'énergie, sachant que E=mc²) n'interdit pas la téléportation : l'énergie totale de l'univers n’est pas modifiée si un objet se déplace instantanément d'un point à un autre.

Pourtant, en réécrivant la conservation de l'énergie sous forme locale une telle action apparaît nettement comme une violation de la vitesse limite. En effet, la conservation d'une quantité de densité ρ se déplaçant localement selon un vecteur v s'écrit de manière générale :

$\nabla \cdot \left(\rho \mathbf {v} \right)+{\frac {\partial \rho }{\partial t}}=0$

D'autres raisons physiques justifient cela. En tout cas, on utilisera toujours des relations locales, différentielles, pour les simulations : cela implique des quantités continues (et dérivables), plus faciles à manier.

L'avantage des expression intégrales est de pouvoir gérer des distributions de tout ordre (linéique, point, surfacique...) alors que les relations locales nécessitent des quantités étendues. Pour les simulations, on utilisera toujours une version « étendue » des distributions non-volumique.

Forme résolue, forme non-résolue

La condition sine qua non pour qu'une simulation numérique ait un sens, c’est de pouvoir incorporer le temps. Il faut pour cela que les équations physiques qu'on étudie soient écrites sous forme explicite comme dépendant du temps. Une équation différentielle est sous forme résolue lorsqu'elle dépend explicitement du temps et de ses dérivées uniquement.

Qu'on aimerait à ce que tous les problèmes physiques soient si simples ! En réalité, même pour des problèmes simples, on est presque systématiquement amenés à des équations couplées, ne serait-ce qu'en électromagnétisme ou électricité et magnétisme sont dépendants l'un de l'autre. Même en l'absence de charges (donc de courants) :

$\nabla \cdot \mathbf {E} =0$ $\nabla \cdot \mathbf {B} =0$ $\nabla \times \mathbf {E} =-{\frac {\partial \mathbf {B} }{\partial t}}$ $\nabla \times \mathbf {B} ={\frac {1}{c^{2}}}{\frac {\partial \mathbf {E} }{\partial t}}$

En fait, beaucoup d'équations sous forme implicite (donc en formes non résolues) peuvent être ramenées à des équations en forme résolue. Pas toutes, cependant. On a alors des systèmes d'équations, dont les solutions ne permettent pas toujours de tirer des expressions temporelles : on ne connait alors pas les échelles de temps, d'énergie (et de même, toutes les dérivées temporelles). Ces cas sont bien souvent problématiques.

Dans le cadre des simulations, les expressions résolues sont toujours préférables.

Début d’un principe

Objet des simulations

Les simulations numériques consistent pour l'essentiel à intégrer des équations différentielles, en minimisant l'impact des défauts numériques sur la situation physique simulée.

Fin du principe

De l'informatique

L'informatique sera le support de la simulation. Ses limites imposeront des limites sur les modèles mathématiques utilisés, donc sur les phénomènes physiques observables.

Dérivées et différences

Les mathématiques utilisent des outils tels que l'analyse, qui font intervenir la notion de « limite ». Certaines fonction admettent des propriétés « aussi petit qu'on puisse regarder », parmi lesquelles, la continuité et la dérivabilité. En mathématique, on peut regarder aussi petit qu'on veut, jusqu'à l'infini.

En informatique, ce n’est pas le cas. La plus petite entité accessible est le bit. Même si chaque bit représentait la décimale d'un nombre, on serait limité par la quantité de bits disponibles. Rappelons qu'un giga-octet (Go) correspond à un milliard d'octets, c'est-à-dire à 8 milliards de bits : c’est beaucoup, certes, mais loin d’être infini.

C'est la principale limite des ordinateurs : ils ont une précision limitée. Supposons qu'un ordinateur ait une précision d'un chiffre derrière la virgule. Les opérations :

2,45 + 2,49 + 2,48 + 2,46 + 0,02 (dont le résultat est 10)

seront effectuées ainsi par l'ordinateur :

2,4 + 2,4 + 2,4 + 2,4 + 0 (dont le résultat est 9,6)

La différence dans cet exemple est de 0,4 — la précision maximale est 0,1 — c’est dire l'écart sur un seul calcul ! Ces erreurs peuvent s'accumuler (et elles le feront) et, en fin de compte, donner à la simulation une direction toute autre que celle prévu à l'origine.

Les relations dont nous avons parlé sont différentielles. Pour les raisons évoquées ci-dessus, le calcul d'une dérivée ne serait qu'approximatif. Cela nous incite à effectuer plutôt des opérations d'intégration.

Lorsqu’il est nécessaire de dériver, on effectuera en fait une opération de différence. En effet, une des définitions possibles d'une dérivée de la fonction f est :

$f':x\mapsto \lim _{h\to 0}{\frac {f(x+h)-f(x)}{h}}$

Si on note $h_{min}$ la plus petite quantité positive non nulle accessible par l'ordinateur, la meilleure approximation que l’on puisse obtenir de cette fonction est :

${\tilde {f'}}:x\mapsto {\frac {f(x+h_{min})-f(x)}{h_{min}}}$

En pratique même, on ne pousse pas les calculs jusqu'à leurs limites. On pose une quantité dx fixe, et on définit la fonction :

$f':x\mapsto {\frac {f(x+\mathrm {d} x)-f(x)}{\mathrm {d} x}}$

qui est donc une très mauvaise approximation de la dérivée de la fonction f. Plus dx est petit, meilleure sera la précision. Quoiqu’il en soit, les dérivation successives sont très mauvaises. De telles méthodes apparaissent lorsqu’il est nécessaire de calculer des dérivées spatiales (et non temporelles), comme les opérateur divergence ou laplacien discrets. Nous verrons dans ce cours comment améliorer les choses, mais le principe fondamental — et donc les limitations intrinsèques — demeurent.

Précision et performances

Nous l'avons suggéré précédemment, la précision mathématique que peut afficher un ordinateur dépend de la quantité de bits qu’il utilise pour représenter les nombres. Cette quantité est, en théorie, arbitraire et ne dépend que de l’argent qu'on a investi dans un disque dur. En pratique, il ne s'agit pas seulement de représenter les nombres — il faut aussi et surtout effectuer des opérations avec, les manipuler.

C'est le micro-processeur (ou les micro-processeurs, le cas échéant) qui s'occupent de manipuler les nombres. La vitesse de calcul dépendra donc de leur capacité à gérer ces quantités. Les constructeurs ont optimisés les processeurs pour traiter certaines classes de précision :

• Octet (précision : 8 bits) ;
• Mot (précision : 16 bits) ;
• Long (précision : 32 bits) ;

Les dernières générations de processeur peuvent également gérer des chiffres représentés par 64 bits. On peut bien entendu utiliser plusieurs « mots » pour représenter un chiffre sur 128 bits, si l'envie nous prend — mais le processeur, lui, n'effectuera des opérations rapides que sur des mots d'une certaine taille.

La performance d'une machine dépend également et surtout des calculs effectués — mais gardons à l'esprit que ces calculs seront d'autant plus rapidement effectués qu’ils impliquent des chiffres dans un format optimisé. D'ailleurs, la mesure « standard » de la puissance de calcul d'un ordinateur se fait en floating-point operation per second, ou « flops » : le nombre d'opération en virgule flottante par seconde. La « virgule flottante » est l'une des représentation des nombres décimaux sur 16, 32 ou 64 bits.

D'une manière générale, selon les applications, il est pertinent de se limiter à une précision honnête, et de prévoir et mesurer l'influence d'une baisse de la précision des calculs sur le résultat de la simulation. En effet, dans de nombreux cas, il n’est pas possible (ou inutile) de faire varier la précision des calculs en cours de simulation (les erreurs se cumulent, ne plus en faire ne « nettoiera » pas ce qu'on a fait).

Du temps et de l'espace

Continu et discret

Découpage de l'espace pour une simulation d'électromagnétisme.

Découpage d'un cercle en triangles élémentaires.

Nous l'avons suffisamment dit : impossible de représenter des objets continus sur un ordinateur. Il en va de même pour le temps et l'espace : nous devons discrétiser ces indivisibles.

C'est très pompeux, mais on peut facilement montrer le théorème suivant :

Début d’un théorème

Théorème

L'ensemble des nombres représentables sur un ordinateur ne forme pas un ensemble dense dans $\mathbb {R}$ ou $\mathbb {C}$.

Fin du théorème

De fait, il faut découper l'espace et découper le temps. Nous n'accèderons pas à certains instants, et ne saurons pas ce qui se passe dans certaines zones. Il ne nous sera possible que de savoir ce qui se passe avant ou après dans une région proche. La prise en compte de lois de conservation permet en général de s'assurer que cela n'a pas de conséquence physique.

La diversité des géométries fait que l'unité de base naturelle de cette découpe spatiale est le triangle : dans le plan euclidien au moins, tous les polygones peuvent être exactement reproduits par un ensemble de triangles, et toutes les figures peuvent être approchées de façon d'autant plus précises que le nombre de triangles est grand. On peut remarquer comme ce découpage est inhomogène, on peut en effet resserrer les mailles près des zones intéressantes et les relâcher en dehors — pour le temps, en revanche, sauf quelques cas, le découpage sera plutôt régulier.

En physique des fluides, l'effet de ces découpage induit une viscosité, appelée « viscosité numérique ».

Processeurs et disques durs

Il est possible de mesurer la déviation qu'implique une approximation sur le résultat final de la simulation. De même, on peut évaluer le temps que nécessite un algorithme pour s'effectuer, et l’espace mémoire qu’il demandera. On ne cherche, généralement, pas les valeurs exactes de ces quantités — un ordre de grandeur suffit.

Il existe un formalisme généralisé pour l’expression de ces grandeurs, représenté par la notation de Landau. On rappelle que :

• $f={\underset {x\to \infty }{o}}\left(g\right)$ signifie que la limite du rapport f/g est nulle, à l'infini.
• $f={\underset {x\to \infty }{O}}\left(g\right)$ signifie que la limite du rapport f/g est finie, à l'infini.

Le premier cas implique le second. Définissons encore quelques termes.

Durée d'exécution d'un algorithme

On suppose qu’il existe un algorithme f, qui prend en entrée des données de taille n. On note tf le temps d'exécution de f, k un nombre supérieur à 1. Alors, par ordre croissant de lenteur :

• f est logarithmique en n lorsque tf = O(log n) ;
• f est linéaire en n lorsque tf = O(n) ;
• f est linéarithmique en n lorsque tf = O(n log n) ;
• f est quadratique en n lorsque tf = O(n²) ;
• f est polynomiale en n lorsque tf = O(n^k) ;
• f est exponentielle en n lorsque tf = O(kⁿ) ;
• f est factorielle en n lorsque tf = O(n!)

Il existe des cas plus rapides, des cas moins rapides et des cas intermédiaires en plus de ceux-ci, mais la liste précédente trace un bon profil de ce que l’on rencontre en simulations informatiques.

Début d’un principe

« Efficacité » d'un algorithme

Un algorithme est efficace lorsque il est, au plus, polynomial.

Fin du principe

En pratique, on préfère même lorsqu’il est quadratique, voire un peu moins que quadratique. Il n’est pas toujours possible de ramener un algorithme trop lent dans un cadre raisonnable. En revanche, on sait par des astuces de programmation ramener le calcul d'interactions à n corps (qui demanderait un temps en n²) en un temps linéarithmique.

Concernant l'espace mémoire impliqué dans le calcul, on utilise la notation $\Omega$ avec le même vocabulaire que pour le temps. L'hypothèse est que, généralement, un algorithme s'exécute en un temps proportionnel au nombre d'instruction appelées.

Finissons ce chapitre par quelques ordres de grandeur des simulations :

• une simulation météorologique doit pouvoir donner des résultats précis en moins d'une journée (pour plusieurs jours simulés) ;
• une simulation de l'univers peut prendre une année complète (pour 15 milliards d'années simulées !) ;
• une simulation des contraintes sur un appareil aérien doit se faire en temps réel ;

Les supercalculateurs impliqués dans les deux premiers cas rendent évidemment la chose plus facile. Il est tout de même important, car souvent envisageable, d'optimiser les algorithmes utilisés lors de la simulation — s'ils n'améliorent pas sa précision, ils permettent d'effectuer plusieurs simulations pour comparer les résultats et moyenner les erreurs.