Nous allons comparer deux méthodes de résolution numériques par rapport à un problème simple : trouver une valeur approchée de PI.
On sait que la surface d'un disque vaut PI multiplié par le rayon au carré. Donc la surface d'un disque de rayon 1 a une aire d'exactement PI.
La méthode générale pour trouver une valeur approchée de PI consiste à tester des points de coordonnées (x,y) dans une zone où x et y varient de -1 à +1. Si le point est à une distance du centre (0,0) inférieur ou égal à 1, on peut dire que le point est dans le disque, sinon il est à l'extérieur. Mathématiquement, on peut écrire que le point (x,y) est à l'extérieur du disque si x*x + y*y > 1.
Une valeur approchée de PI est le rapport entre le nombre de points à l'intérieur du disque et le nombre total des points. Le carré circonscrit au cercle a une aire égale à 4. Si on pouvait prendre tous les points de notre zone, on aurait une valeur exacte de PI ! Mais c'est impossible car ce nombre de points est infini. Il faut donc que l'on choissise bien nos points pour s'approcher le plus possible avec le minimum d'essais.
La méthode de Monte-Carlo prend ses points au hasard. Tout simplement !
Tandis que la méthode par Multi-Résolution travaille par échelle. C'est une approche fractale qui ajoute des points à chaque niveau de détail suivant un modèle initial qui se répète. Par exemple, pour recouvrir un carré de points, on commence par placer 5 points, puis on divise la zone en 4 carrés pour lesquels on place 5 points, et ainsi de suite. On premier niveau, on place donc 5 points, mais au deuxième, on en est déjà à 20, puis on passe à 80, puis 320, etc... Le nombre de points que l'on rajoute à chaque niveau croit exponentiellement. Mais on est sûr que la répartition des points est toujours homogène.
Nous avons procédés à des tests afin de déterminer laquelle de ces deux méthodes convergeait le plus rapidement vers PI. Puisque la méthode de Multi-Résolution semblait plus complèxe, nous nous attendions à ce qu'elle converge plus vite, mais quelle ne fut notre surprise de découvrir l'inverse.
Monte-Carlo
  785083 /  1000000 : PI ~ 0.0012606535897932147
 1570431 /  2000000 : PI ~ 0.0007306535897932953
 2355927 /  3000000 : PI ~ 0.0003566535897929768
 3141123 /  4000000 : PI ~ 0.0004696535897932286
 3926793 /  5000000 : PI ~ 0.00015825358979304482
 4711630 /  6000000 : PI ~ 0.0005059869231263114
 5497010 /  7000000 : PI ~ 0.00044408216122171495
 6281662 /  8000000 : PI ~ 0.0007616535897931875
 7066802 /  9000000 : PI ~ 0.0007917647009043627
 7852348 / 10000000 : PI ~ 0.0006534535897930738
 8638509 / 11000000 : PI ~ 0.00031665358979315883
 9424180 / 12000000 : PI ~ 0.00019932025645985618
10209665 / 13000000 : PI ~ 0.00015726897440870857
10995281 / 14000000 : PI ~ 8.379644693601307e-05
11780872 / 15000000 : PI ~ 2.678692312629849e-05
12566479 / 16000000 : PI ~ 2.7096410206706167e-05
13182912 / 16785405 : PI ~ 7.48886028891782e-05
Multi-Résolution
       3 /        5 : PI ~ 0.7415926535897932
      14 /       21 : PI ~ 0.4749259869231266
      55 /       77 : PI ~ 0.2844497964469359
     213 /      285 : PI ~ 0.15211896937926683
     832 /     1085 : PI ~ 0.07431154759900949
    3275 /     4221 : PI ~ 0.038062684388182166
   12984 /    16637 : PI ~ 0.019875997942741197
   51719 /    66045 : PI ~ 0.009243497711225679
  206378 /   263165 : PI ~ 0.004731748834221339
  824546 /  1050621 : PI ~ 0.002321689084038958
 3296228 /  4198397 : PI ~ 0.0011292814980161658
13180824 / 16785405 : PI ~ 0.0005724637284223455
Monte-Carlo vs Multi-Résolution
22 mai 2013
Sommaire général