Le Problème à N corps 8


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.

Simulation du Système Solaire sur Univers Sandbox, N~20

Simulation du Système Solaire sur Univers Sandbox, N~20

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.

Simulation de la future collision de la Voie Lactée et dAndromède, N=100000000

Simulation de la future collision de la Voie Lactée et d’Andromède, N=100’000’000

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:

Logiciels N corps sur PC:

  • http://www.courtois.cc/blogeclectique/ Krysztof von Murphy

    Ç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

    • http://goulu.net Dr. Goulu

      @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…

  • Pingback: Comment localiser les sondes spatiales « Dr. Goulu()

  • Pingback: Gouttes de sable « Dr. Goulu()

  • http://drgoulu.com Dr. Goulu

    Reçu une question par e-mail :

    J’ai beaucoup aimé le documentaire « voyage aux confins de l’univers »,je ne sais pas si vous l’avez vu ?

    J’ai été sidéré par les vidéos de synthèses qui ont servi pour la réalisation de ce chef-d’oeuvre mais ce que je voulais vous demander c’est surtout avec quel programne ils ont réalisé les galaxies ?

    Y’a-t-il d’autres documentaires d’astronomie similaires qui reposent sur de pareilles vidéos de synthèses ?

    • http://drgoulu.com Dr. Goulu

      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.

  • http://drgoulu.com Dr. Goulu

    Trouvé ça sur la simulation N corps sur GPU : http://http.developer.nvidia.com/GPUGems3/gpugems3_ch31.html

  • http://drgoulu.com Dr. Goulu

    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