Valeur Moyenne d'une surface

La question :

Bonjour,

Je dispose d'une surface en dimension n : y = f(x1, x2, ..., xn)
( au besoin je connais les dérivés partielles de cette surface )

Je cherche une manière intelligente de calculer la valeur moyenne de y
Par echantillonnage, le temps de calcul quand n est grand devient
prohibitif.

Remerciements,

kpdp

Poser votre question sur le forum Programmation

Les 12 réponses :

Je sais pas mais :

En systématique dans mon cas, les données vont de -1 à 1, si je me
donne un pas de 0.01 ça fait 200. Donc le nombre de points est 200^n.
Pour n=8 ca n'est pas jouable.

Je pense qu'en monte-carlo, il faut augmenter le nb de point jusqu'à
ce que des essais successifs donnent à peu prés la même valeur. Le
critère du bon nombre de point doit se baser à mon avis sur l'analyse
de la variance des résultats sur plusieurs essais : Si je décide de
tirer 1 millions de points, 100 fois je reste dans le domaine du
possible.

Dans l'absolu, je pense que le nb de point à tirer dépend fortement
de la courbe, plus elle est "régulière" moins il faut de point. Si
f(x1,x2,...,xn) = 1, il ne faut qu'un 1 point en Monte-carlo ( Dans
l'idée bien sur

kpdp a écrit :


Je sais pas mais :

En systématique dans mon cas, les données vont de -1 à 1, si je me
donne un pas de 0.01 ça fait 200. Donc le nombre de points est 200^n.
Pour n=8 ca n'est pas jouable.

Je pense qu'en monte-carlo, il faut augmenter le nb de point jusqu'à
ce que des essais successifs donnent à peu prés la même valeur. Le
critère du bon nombre de point doit se baser à mon avis sur l'analyse
de la variance des résultats sur plusieurs essais : Si je décide de
tirer 1 millions de points, 100 fois je reste dans le domaine du
possible.


Mais il faut reflechir a en quoi tirer 100 fois 1 million de points serait
superieur a une evaluation avec un pas de 0.2 (soit 100 millions de points).

En particulier puisque l'on dispose de la derivee, on peut augmenter
directement la densite de points la ou il y a des reliefs tourmentes,
plutot que d'attendre que ces endroits soient decouverts par hasard et par
l'analyse de la variance.



Dans l'absolu, je pense que le nb de point à tirer dépend fortement
de la courbe, plus elle est "régulière" moins il faut de point. Si
f(x1,x2,...,xn) = 1, il ne faut qu'un 1 point en Monte-carlo


Il ne faut qu'un point en grille reguliere, si tu sais que la derivee est
nulle. Avec Monte-Carlo, il te faudra en tirer une trentaine pour etre
raisonnablement sur que tu n'en avais besoin que d'un !

Fabien LE LEZ a écrit :


À partir de combien de dimensions un échantillonnage aléatoire est-il
plus efficace qu'un échantillonnage systématique ?


1. Si par efficacité tu entends "précision du résultat", un
échantillonnage aléatoire est tout le temps meilleur, puisque la méthode
est sans biais. La convergence est garantie (aux erreurs numériques
près, c'est un autre débat). Toutes les valeurs ont la même chance
d'être atteintes, donc prises en compte dans le résultat. Il faut juste
être patient, quitte à devoir effectuer une infinité de tirages. D'un
point de vue strictement mathématique ce n'est pas dérangeant.

Un échantillonnage régulier, aussi fin soit-il, ignore par principe
toutes les valeurs comprises entre 2 points successifs. On est donc
certain de rater des valeurs. Ce n'est pas du tout grave si la variance
est nulle, mais ce n'est pas un cas très passionnant. Ce n'est pas trop
grave si le gradient est faible (ou connu, c'est encore mieux pour
compenser). Par contre c'est bien plus grave lorsque la fonction est
complètement inconnue, car rien ne prouve que des valeurs très
significatives n'ont pas été oubliées.

En plus l'échantillonnage régulier risque de produire des effets de bord
assez amusants dans le domaine fréquentiel, c'est la faute à Shannon,
Nyquist et cie, et à leurs théorèmes pervers.


2. Si par efficacité tu entends "temps de calcul", la réponse est très
simple : "ça dépend..."
Disons que plus la fonction est lourde à calculer et plus la dimension
est grande, plus il y a de chances que ça vaille le coup. Ça aide à se
décider ça, hein

Par exemple les méthodes de Monte Carlo sont particulièrement efficaces
pour la simulation de processus markoviens (par exemple étude de
l'évolution d'un grand nombre de particules qui rebondissent plein de
fois selon des lois de probabilité plus ou moins compliquées, avant
d'être absorbées ou de générer d'autres particules qui recommencent la
danse).


3. Le hasard peut (doit) aussi être guidé pour accélérer sensiblement la
convergence, en particulier :

Echantillonnage stratifié : une grille grossière subdivise l'espace,
avec l'espoir que la variance dans chacune des zones soit beaucoup plus
faible que la variance globale (hypothèse plutôt raisonnable), puis
échantillonnage aléatoire qui devrait converger assez vite dans chaque
zone. La grille initiale n'est pas forcément régulière (gros pavés dans
les zones "plates" si elles sont connues, plus fins ailleurs).

Echantillonnage d'importance : lorsque l'allure de la fonction est
connue, on effectue les tirages selon une loi de probabilité déduite de
cette allure estimée, pour concentrer les tirages dans les zones
"utiles", puis on pondère les échantillons obtenus par une loi inverse.

Ces améliorations se combinent bien entre elles, et rien n'empêche de
changer de stratégie après les premiers tirages qui donnent une
indication grossière mais utile de la variance. La difficulté vient de
ce qu'il n'y a que des cas particuliers. Aucune solution générique n'est
vraiment efficace.


Bref, il faut faire des essais, car tout cela est difficilement
prédictible... et je n'ai pas répondu à ta question

Si j'ai bien suivi le film de kpdp, son problème semble parfaitement
relever d'un cas où ça vaut le coup d'essayer.

A+
Jacques

Michel OLAGNON a écrit :


...
En particulier puisque l'on dispose de la derivee, on peut augmenter
directement la densite de points la ou il y a des reliefs tourmentes,
plutot que d'attendre que ces endroits soient decouverts par hasard et par
l'analyse de la variance.


Oui, et il ne faut surtout pas s'en priver.


...
Il ne faut qu'un point en grille reguliere, si tu sais que la derivee est
nulle. Avec Monte-Carlo, il te faudra en tirer une trentaine pour etre
raisonnablement sur que tu n'en avais besoin que d'un !


Heu, c'est à dire que si tu *sais* que la dérivée est nulle, même avec
une méthode de Monte Carlo, il n'est peut-être pas très judicieux
d'effectuer plusieurs tirages... mais bon, si tu aimes jouer


A+
Jacques

On Thu, 24 Nov 2005 23:00:48 +0100, jz :


1. Si par efficacité tu entends "précision du résultat"


Une méthode "efficace", tel que j'entends ce mot, est une méthode
demandant peu de temps pour une précision donnée (ou une précision
très grande pour un temps donné).


, un
échantillonnage aléatoire est tout le temps meilleur, puisque la méthode
est sans biais. [...] Il faut juste
être patient, quitte à devoir effectuer une infinité de tirages. D'un
point de vue strictement mathématique ce n'est pas dérangeant.


Ah oui mais là non. Il me semble qu'un échantillonnage infini
(dénombrable) régulier est sans biais. C'est le principe classique :
Q^n est dénombrable et dense dans R^n.

Poser votre question sur le forum Programmation

Questions similaires :

Moyenne de températures

Bonjour, Ce que je veux faire est en théorie simple, c'est calculer la moyenne de températures sur une période donnée. Les données en entrée sont des couples date (en s) et température (en °C). Le problème est que les intervalles entre les dates ne sont pas identiques, sinon il suffirait de faire...

Remplissage de surface par des rectangles

Bonjour Connaissant la surface de n rectangles, je souhaiterais remplir un carré avec tous les rectangles (seule la surface est importante). Je suppose qu'il existe des algos pour faire cela, mais n'arrivant pas à mettre de nom dessus, je ne trouve rien sur google. Si quelqu'un pouvait m'aider, ce...

représenté des clusters sur une surface 2D

Bonjour, J'ai un algorithme de clustering basé sur une distance de Jacquard. Je voudrais représenter mes clusters sur une surface 2D. Je connais la distance entre les points, il me faudrait la position des points, respectant le mieux possible la contrainte de distance et me donnant un graphe le...

Faire une moyenne d'angle (girouette)

Bonjour, je cherche à faire une moyenne d'angle, valeur qui ont été relevé sur une girouette, pour donner la direction moyenne du vent sur une période (par exemple). une moyenne simple ne fonctionne pas (350° et -10° doit donner une direction à 0°, et pas 170°) j'avais pensé à la moyenne des Tan...

Afficher chaine de caracter ou valeur

Bonjour, (J'ai posté ma question sur le forum langage C mais je crois que c'est mieux ici) J'ai un afficheur à 4 lignes. je definis les lignes de cette facon *lign1 *lign2 *lign3 *lign4 Seulement voilà suivant le menu où je me trouve *lignx="chaine" ou *lignx=EntierEnChaine(var) C'est à dire que...