Le « problème à N corps » consiste à déterminer le mouvement de N masses sous l’effet des forces d’attraction gravitationnelles entre elles.
Pour N=2, Newton savait déjà que les deux corps décrivent des ellipses autour de leur centre de gravité commun.
Pour N=3, Poincaré avait découvert que les trajectoires des corps pouvaient être « chaotiques » : une toute petite différence dans les positions et vitesses initiales des corps pouvait causer de très importantes différences dans la trajectoire des corps. Cependant, malgré ce que beaucoup croient, il existe une solution analytique au problème des trois corps découverte en 1909 par Karl Sundman. Elle n’est cependant pas utilisable en pratique pour des calculs.
Pour plus de 3 corps, il n’existe pas de solution analytique. Ceci signifie entre autres qu’il n’est pas possible de démontrer la stabilité d’un système avec quelques corps, comme le Système Solaire par exemple. Des mathématiciens comme Laplace ou Lyapunov s’y sont cassés les dents : rien ne prouve que les planètes suivront toujours leurs orbites actuelles dans quelques centaines de millions d’années. Encore moins qu’un astéroïde viennent percuter notre belle planète beaucoup plus tôt.
Il est aujourd’hui facile de simuler quelques millions d’années d’évolution du Système Solaire sur un PC, par exemple avec Universe Sandbox, le chouette programme dont j’ai déjà parlé ici. Comme on connait avec une très grande précision la position, la vitesse et la masse des planètes et de leurs principaux satellites, on estime que l’on peut calculer leur position dans 5 millions d’années à 150m près. Pour arriver à cette précision, mais aussi tout simplement pour réaliser une simulation réaliste, il faut tout particulièrement veiller à la l’intégration numérique utilisée, pour garantir la conservation de l’énergie totale du système. Selon cette étude, la méthode de Gauss-Hermite donne les meilleurs résultats.
D’autre part, pour chacun des N corps, il faut calculer les N-1 forces exercées par les autres corps. Au total, il faudra calculer [N.(N-1)]/2 forces (le /2 vient du fait qu’il suffit de ne calculer qu’une fois la force entre deux corps). On dit que la complexité est O(N²) : il faut effectuer un nombre d’opérations proportionnel au carré de N. Pour quelques dizaines de corps, ça ne pose aucun problème, mais si l’on veut simuler des galaxies ou même la collision de galaxies avec N=1’000’000, on se retrouve avec mille milliards de forces à évaluer, ce qui nécessite beaucoup de temps de calcul.
On pourrait se dire qu’une petite étoile à un bout de la galaxie n’attire pratiquement pas une autre petite étoile très distante, mais négliger cette force n’est pas une bonne idée. D’une part, l’énergie totale du système ne serait plus conservée, et d’autre part il faudrait trouver un critère permettant de savoir quelles forces sont négligeables, sans les calculer.
Barnes et Hut ont proposé en 1986 un algorithme dont la complexité est O(N.log N). Pour N=1’000’000, il n’y a environ que 20’000’000 de forces à évaluer, ce qui rend le calcul possible. L’algorithme consiste à diviser l’espace en une structure arborescente appelée octree et à y répartir les corps. On ne calcule les forces qu’entre les corps situé dans la même zone de l’octree, puis l’algorithme calcule les interactions entre les zones. Reste une difficulté : en se déplaçant, les corps changent de zone, et l’algorithme nécessite d’adapter l’octree de l’adapter à la distribution des corps.
interaction de 2 amas de 50 galaxies. N=160’000
Dès 1987, Leslie Greengard a développé un algorithme baptisé « Fast Multipole Method » (FMM), dont la complexité est O(N) seulement, et qui ne nécessite pas d’adaptation de la division de l’espace utilisée. Il est assez facile d’illustrer cette méthode en 2D, mais en 3D l’interaction entre zones est beaucoup plus complexe.
La FMM est considérée par certains comme l’un des algorithmes les plus importants du XXième siècle, car il peut être appliqué à des problèmes beaucoup plus généraux que les N corps, comme certains problèmes de mécanique des fluides ou de mécanque traités jusqu’ici par des méthodes de type « éléments finis » ou de simulation de molécules. Inutile de dire que je vais regarder ça de plus près …
Références:
- NEMO A Stellar Dynamics Toolbox, le logiciel développé par Barnes et Hut, site avec énormément de liens sur le domaine
- Dossier « le chaos dans le système solaire » sur AstroSurf
- Problème à N corps sur la Wikipedia
- N-body Methods à Berkeley
- The Art of Computational Science
- VPNBody : code VPython
- Fast Multipole Method sur Wikipedia
- Guy Blelloch and Girija Narlikar « A Practical Comparison of N-Body Algorithms » Parallel Algorithms. Series in Discrete Mathematics and Theoretical Computer Science, Volume 30, 1997.
- CUNBody, une librairie de simulation N corps parallélisée sur GPU (processeur graphique)
- Parallel N-Body Simulations : comparaisons et implémentation sur super ordinateurs
Logiciels N corps sur PC:
- Universe Sandbox : le plus beau et le plus fun
- Gravit : utilise l’alogrithme de Barnes Hut
- AstroGrav
- Gravity 6
- Gravity Simulator, un peu ancien
9 commentaires sur “Le Problème à N corps”
Quelqu’un m’a demandé par e-mail « Je voulais savoir s’il était envisageable théoriquement de déplacer une meteorite (ou autre, en orbite avec un satellite) en envoyant une sonde au bon endroit pour modifier son orbite (ceci, meme si a la sonde a une masse inférieure à la meteorite en question) »
Théoriquement oui, mais en pratique pas : la force de la gravité est proportionnelle au produit des masses, et à l’inverse du carré des distances. La masse d’une sonde est pas grande, mais les distances dans l’espace sont vites grandes, et leur carré encore plus…. Finalement, la constante de la gravitation universelle G est toute petite, donc la force de la gravitation entre objets de taille « normale » distants de milliers ou millions de kilomètres est vraiment toute petite.
Je repense qu j’avais donné des exemples dans mon article sur l’astrologie, où il y a un tableau qui calcule les forces sur un bonhomme de 80kg exercées par les différentes planètes, et la masse équivalente placée à 1m qui exercerait la même force. Ainsi l’attraction de Jupiter correspond à celle d’une camionnette de 4 tonnes par exemple. Donc si un astéroïde s’approchait de la Terre et qu’on lui envoyait une sonde de 4 tonnes le frôler à 1m, ça lui ferait le même effet que l’attraction de Jupiter : rien. En fait, on aurait eu meilleur temps de le percuter, ou mieux encore de planter dessus une fusée de 4 tonnes pour le pousser, ça le ferait nettement plus dévier.
Maintenant si on se rend compte qu’un astéroïde va probablement heurter la Terre dans quelques dizaines d’années voire siècles ( voir https://drgoulu.com/2012/01/28/risques-meteoritiques/ ), là on peut imaginer le faire dévier beaucoup en appliquant une toute petit force au bon moment en se basant sur le réseau de transport interplanétaire dont je parle un peu ici Il y a d’étonnantes idées dans ce domaine comme peindre Apophys en blanc, mais on pourrait imaginer que dans un cas extrême, faire passer une grosse sonde tout près au bon moment puisse suffire…
Article sur le sujet dans le flash informatique de l’EPFL, en particulier l’allocation des processeurs selon une fractale de Peano-Hilbert pour minimiser la distance entre points de l’espace
Trouvé ça sur la simulation N corps sur GPU : http://http.developer.nvidia.com/GPUGems3/gpugems3_ch31.html
Reçu une question par e-mail :
je n’ai pas encore vu le documentaire « voyage aux confins de l’univers » mais ça ne va pas tarder car je viens de le télécharger, et j’ai fait une chose que je n’avais jamais fait avant : sauter au générique de fin et trouvé « Animation : Red Vision & C4 Studios »
http://www.redvision.co.uk/ fait visiblement des anims pour des documentaires, mais je n’y ai pas trouvé d’infos précise sur les outils utilisés, idem pour http://www.c4studios.com/
Pour la simulation physique de galaxies, je « connais » Gadget : mais je serais surpris que de tels outils aient été utilisés pour un documentaire car ils demandent d’énorme puissance de calcul et le résultat graphique est souvent peu « sexy » car ce n’est pas le but recherché. Je suis toujours bluffé par les artistes qui parviennent à représenter de tels phénomènes physiques sans s’appuyer sur les lois physiques, en utilisant « juste » des logiciels d’animation du type 3D-Studio Max avec quelques plugins bien maitrisés…
Les prochains documentaires astronomiques à ne pas rater seront les « Wonders of the Solar System » de la BBC une fois qu’ils auront été traduits. Je les ai vus en anglais, ils sont fantastiques, et à première vue plus rigoureux du point de vue scientifique que « voyage aux confins de l’univers » que je vais regarder en détail d’ici quelques heures.
Ça me rappelle qu’il y a un paquet d’années, Jacques Laskar avait fait des simulations sur la stabilité des planètes du système solaire. Donc pas de solution analytique mais une simulation (plus subtile que l’intégration complète des orbites). En gros, Mercure était assez instable pour avoir une chance de percuter Vénus dans les prochains milliards d’années.
Cf un de ses articles :
http://www.imcce.fr/Equipes/ASD/preprints/prep.2003/th2002_laskar.pdf
ou sa page Wikipédia :
http://fr.wikipedia.org/wiki/Jacques_Laskar
@Krysztof : merci pour ces infos, et désolé pour le retard, ton commentaire avait atterri dans les « spams » pour une raison inconnue…
les travaux de Laskar semblent en effet très intéressants. J’en ai trouvé un résumé ici qui confirme un truc qu’on voit en faisant de petites simulations : l’espace intersidéral doit être pavé de petits cailloux voire de planètes éjectées des systèmes…