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.