Méthode des rectangles / monte carlo sur un disque ou une sphère

[qnope]

Bonjour à vous.

M'intéressant au calcul intégrale en informatique, dans le cadre de rendu 3D, j'aurais besoin de savoir comment intégrer sur une sphère de manière discrète (méthode des rectangles, ou monté carlo) de manière légèrement plus efficace que la mienne.

Exemple, pour une fonction simple, on a


Maintenant, voilà ma méthode pour calculer (à la manière des rectangles, monté carlo sera le même genre, mais avec une seule somme), par exemple, l'aire d'un disque centré en O de rayon 1 (formule qui renvoie Pi)

avec f qui renvoie 1 le couple reçu x, y appartient au cercle.

L'avantage, c'est que ça fonctionne , mais le désavantage, c'est qu'une grosse partie de ces calculs sont en fait des "points" n'appartenant pas vraiment à notre disque, mais plutôt en dehors de notre disque, ce qui fait que l'on doit testé si les points appartiennent bien à notre surface / volume...

J'aurais donc aimé savoir s'il existait une formule pour intégrer sur des sphères ou autre d'une manière de ce genre (en passant par des sommes).

J'avais penser à utiliser un petit changement de variable, suis je sur la bonne voie?

Merci .
-----

[minushabens]

Tu veux intégrer une fonction réelle définie sur la sphère? Dans ce cas tu peux effectivement le faire par Monte Carlo : il suffit de tirer des points aléatoires selon la loi uniforme sur la sphère, et de multiplier la moyenne des valeurs de la fonction par la mesure de la sphère. Pour ce faire tu peux tirer des points dans la loi normale n-dimensionnelle standard (n est la dimension de la sphère) et ensuite de normaliser ces points.

[Tryss]

Tu veux intégrer une fonction réelle définie sur la sphère? Dans ce cas tu peux effectivement le faire par Monte Carlo : il suffit de tirer des points aléatoires selon la loi uniforme sur la sphère, et de multiplier la moyenne des valeurs de la fonction par la mesure de la sphère. Pour ce faire tu peux tirer des points dans la loi normale n-dimensionnelle standard (n est la dimension de la sphère) et ensuite de normaliser ces points.

Ceci dit, pas sur que ce soit plus rapide : ça nécessite un certain nombre d'opérations complexes.

Tester si un point appartient a un disque, c'est trois multiplications, deux additions et un test. Rien que pour normaliser un point, c'est deux multiplications, une addition, une division et une racine carrée, qui demande pas mal d'opérations élémentaires

[minushabens]

Il y a d'autre méthodes pour simuler des points uniformes sur la sphère, mais l'avantage de la loi normale c'est qu'on a des générateurs tout programmés (je ne vois pas ce que vient faire ici le test d'appartenance à un disque).

[A voir en vidéo sur Futura]

[Amanuensis]

Pour ce faire tu peux tirer des points dans la loi normale n-dimensionnelle standard (n est la dimension de la sphère) et ensuite de normaliser ces points.

Pourriez détailler?

[minushabens]

Je propose de tirer chaque coordonnée indépendamment dans la loi normale centrée réduite, puis de normaliser le vecteur de façon à avoir un point de la sphère. C'est facile de voir qu'on a alors la distribution uniforme sur la sphère (une distribution qui n'a pas de moyenne d'ailleurs).

[minushabens]

Ca demande d'ailleurs pas mal de calculs. Si par exemple la fonction à intégrer est donnée comme fonction de coordonnées angulaires, il faudra faire la transformation nécessaire.

On peut aussi simuler une variable uniforme sur la sphère exprimée directement en coordonnées géographiques (pour la sphère à 2 dimensions).

[Médiat]

Je propose de tirer chaque coordonnée indépendamment dans la loi normale centrée réduite, puis de normaliser le vecteur de façon à avoir un point de la sphère. C'est facile de voir qu'on a alors la distribution uniforme sur la sphère (une distribution qui n'a pas de moyenne d'ailleurs).

Bonjour,

Vous tirez les coordonnées entre quelles valeurs ? Si c'est entre -R et R, le résultat n'est pas uniforme (pour le cercle, cela saute à peu près aux yeux), en travaillant avec les angles, cela devrait mieux marcher, il me semble.

[minushabens]

Les coordonnées sont tirées dans la loi normale, donc a priori ne sont pas bornées. Maintenant, sur un ordinateur elles sont nécessairement bornées et ça peut peut-être créer un petit biais. Mais d'un autre côté, rien ne dit que l'uniformité des points sur la sphère soit indispensable pour le calcul de l'intégrale (sauf si on a de la malchance).

[Amanuensis]

Suffit d'utiliser la loi normale tronquée à une distance max pour résoudre la question de la borne. La seule chose qui importe est l'isotropie, et tronquer la loi normale tronquée a cette propriété.

S'il y a un biais venant de l'usage d'un l'ordinateur, c'est plutôt qu'il ne permet pas d'utiliser des réels, même limités à un intervalle fini.

[minushabens]

oui mais si on tronque chaque coordonnée on n'est plus isotrope. Mais bon, s'il y a biais il est minuscule. On peut quand-même avoir des réels de l'ordre de 10^30 avec quatre octets.

[Amanuensis]

oui mais si on tronque chaque coordonnée on n'est plus isotrope.

Je n'ai pas proposé de tronquer les coordonnées.

[minushabens]

Mais c'est ce qui va se passer en pratique quand on va simuler une loi multinormale, puisqu'on la simule coordonnée par coordonnée. Je ne vois pas bien comment faire autrement, à moins d'avoir déjà une variable uniforme sur la sphère, mais puisque c'est ce qu'on veut in fine...

[Amanuensis]

Mais c'est ce qui va se passer en pratique quand on va simuler une loi multinormale, puisqu'on la simule coordonnée par coordonnée. Je ne vois pas bien comment faire autrement

Une méthode simple: tirer les coordonnées dans [-1,1] et éliminer tous les tirages tels que x²+y²+z²>1. Le résultat est une troncature "à une distance max".

Je me trompe peut-être, mais c'est l'application d'une technique assez courante.

[minushabens]

Ca donne une distribution uniforme dans la boule, et ensuite tu la normalises pour avoir une distribution sur la sphère. Oui ça me paraît devoir fonctionner, et c'est plus simple que ma méthode. Bien vu.

[Médiat]

En travaillant sur les angles il n'est pas nécessaire de rejeter 48% des tirages.

[minushabens]

Je ne suis pas sûr que tu y gagnes. Prenons l'exemple de la dimension 2. Tu peux tirer la longitude dans la loi uniforme sur [0,2pi], mais pour la latitude il te faut tirer un angle dans une loi qui n'a pas une expression simple, donc tu vas le faire par acceptation/rejet et fialement tu vas rejeter une partie des tirages. En dimension supérieure je ne sais pas si les choses se compliquent ou non.

[Amanuensis]

Et rejeter la moitié des tirages peut rester la bonne approche par rapport à une alternative demandant (par exemple) trois fois plus de calculs avant admission du tirage.

[Médiat]

Cela ne me semble pas si compliqué : http://mathproofs.blogspot.fr/2005/0...on-sphere.html

Par contre il y a des calculs trigonométriques (évidemment avec les angles) à faire, donc l'efficacité globale dépend de l'efficacité de chaque type de calcul ...

[minushabens]

De toutes façons, comme j'ai écrit plus haut, si la fonction est calculable à partir des angles il faudra en passer par des calculs de trigonométrie.

[qnope]

En travaillant sur les angles il n'est pas nécessaire de rejeter 48% des tirages.

Bonjour, merci de votre réponses à tous pour commencé.

@Médiat.
J'avais commencé à travailler sur ce genre de méthode, seulement voilà, j'ai un petit problème de conception. En effet, si l'on prend l'exemple le plus simple, l'intégrale sur un disque, on a :


Seulement voilà, maintenant, si l'on prend un tirage aléatoire sur l'angle, et sur r, je ne vois pas trop comment retrouvé ce résultat avec une simple somme en fait...

Je regarderais ton lien toute à l'heure alors ^^.

Merci beaucoup de votre aide .

[minushabens]

Le disque n'est pas une sphère. Tu poses maintenant une toute autre question.

[qnope]

Le problème n'est pas le même?

Du coup, si l'on utilise une sphère, on aura 3 variables aléatoire, r, theta, et phi, donc on aurait

à transformer en triple somme... C'est pour ça qu'étant donner que je pensais que le problème était le même pour un disque, je préférer avoir une explication simple sur le disque puis me débrouiller pour la sphère ^^.

Merci

[Tryss]

Tu confond boule et sphère

La sphère c'est la surface, la boule c'est la surface plus l'intérieur

[minushabens]

Le problème n'est pas le même?

oui et non. Dans les deux cas il s'agit d'intégrer une fonction définie sur un compact, mais ce qu'il y a de spécifique à la sphère c'est que ce n'est pas tout-à-fait trivial de simuler une loi uniforme. Si tu prends "bêtement" latitude et longitude uniformes, tu vas avoir une distribution non uniforme, avec plus de points vers les pôles que vers l'équateur. Et d'autre part il n'est pas non plus trivial de découper la sphère en cellules de même taille, si tu veux faire de l'intégration dans le genre rectangles ou trapèzes. Dans la boule c'est plus simple.

[qnope]

Hmm, bon bas je vais faire la méthode normal alors a mon avis ^^.

Merci de vos réponses . Je n'ai malheureusement pas encore le niveau pour comprendre tout ce que vous avez dit, mais ça viendra .

Encore merci .

[polf]

Si l'objectif est d'avoir un calcul le plus précis possible, à nombre constant de points, alors je pense que ni la méthode des rectangles, ni la méthode de monté carlo (qui en plus ne donne pas 2 fois le même résultat !) ne sont optimales.

J'opterais pour la méthode des trapèzes, qui peut être adaptée sur une fonction à 2 variables en prenant des points en quinconce pour avoir une base de triangle équilatéral.

Pour plus de méthodes, il y a :
http://www-fourier.ujf-grenoble.fr/~.../Oral1/220.pdf