Algorithme à trouver pour suite de nombres.

Olympiades mathématiques, énigmes et défis
Sylviel
Modérateur
Messages: 6466
Enregistré le: 20 Jan 2010, 14:00

par Sylviel » 14 Juin 2013, 11:53

@Benjamin : je ne cherche pas à relancer le "débat" je demande une formule. J'arrête sur le sujet.

@Dlzlogic : à ma connaissance ce que tu as calculé ne porte pas le nom d'écart-type. J'ai donné des références de la définition d'écart-type dans divers contexte, dans ce contexte précis j'ai dis que je ne la connaissais pas. Je m'arrête là.
Merci de répondre aux questions posées, ce sont des indications pour vous aider à résoudre vos exercices.



Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 14 Juin 2013, 14:24

Bonjour,
Je voudrais préciser une phrase.
Il n'y a aucune notion d'aléatoire dans ce contexte, on aurait pu calculer un écart moyen arithmétique ou je ne sais quoi d'autre, il se trouve seulement que l’écart moyen quadratique est la valeur qui représente le mieux la qualité du résultat.

Extrait de son contexte il est vrai que la remarque de Léon peut paraitre justifiée.
"représente le mieux", parce que c'est celle que l'on utilise. Si je t'avais parlé de "l'écart probable" ou de "l'écart moyen arithmétique" tu m'aurais répondu "Késako"

Par parenthèse, je trouve très regrettable cette appellation "écart-type" au lieu de "écart moyen quadratique", surtout quand on aime les abréviation "emq" est plus court.

Quand à la seconde partie, tu connais très bien ma réponse et tu sais aussi que toute réaction sur ce sujet m'est interdite.
Je dirais seulement que ce sont des questions qui s'approchent beaucoup plus de la physique, laquelle utilise les résultats des mathématiciens.

adrien69
Membre Irrationnel
Messages: 1899
Enregistré le: 20 Déc 2012, 14:14

par adrien69 » 14 Juin 2013, 14:32

leon1789 a écrit:Pour trouver les coefficients a,b,c, j'ai utilisé simplement un petit logiciel qui contient une fonction de minimisation.

D'ailleurs justement, tu penses que ça minimise au sens de quelle norme ?

Sylviel
Modérateur
Messages: 6466
Enregistré le: 20 Jan 2010, 14:00

par Sylviel » 14 Juin 2013, 15:10

Il a sans doute minimisé au sens de la norme 2 : c'est ce qui est fait de manière archi classique, et parfois de manière analytique (moindres carrés linéaires). Mais même dans le cas non linéaire il y a des algos spécifiques.
Merci de répondre aux questions posées, ce sont des indications pour vous aider à résoudre vos exercices.

adrien69
Membre Irrationnel
Messages: 1899
Enregistré le: 20 Déc 2012, 14:14

par adrien69 » 14 Juin 2013, 16:01

Je tiens pas à relancer une guerre, mais ils sont bien probabilistes ces algorithmes non ?
Dans le sens où il s'agit je pense de trouver un bon estimateur. D'où ma question étant donné qu'il existe plusieurs pistes pour ce faire : dans quelle classe d'estimateurs son logiciel a travaillé ?

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 14 Juin 2013, 18:55

adrien69 a écrit:D'ailleurs justement, tu penses que ça minimise au sens de quelle norme ?

J'ai bidouillé entre plusieurs normes (1, 2, et infinie) suivant mon feeling.

Pour illustrer que la norme 2 (celle qui parle de carré) n'est pas forcément la meilleure, voici un exemple tout bête qui est semblable à celui de notre discussion. Pour i allant de 1 à 12, j'ai des résultats expérimentaux (qui viennent d'un phénomène linéaire) suivants
Code: Tout sélectionner
3
5
7
9
11
13
15
17
19
21
24
26

Je précise que les résultats ont été arrondis à l'unité. Question : trouver une équation de droite qui modélise le phénomène.
Si on fait une régression linéaire (ie. méthode des carrées, ou norme 2, notée si on préfère), alors
on tombe sur .
Le problème de cette méthode est que l'on ne tient pas compte de l'hypothèse d'arrondi : on fait comme si les étaient exactement ceux donnés après l'arrondi.
Et ensuite on s'aperçoit que ne répond pas au problème : en effet, pour x = 11 , on a y = 23.4814 que l'on arrondit à 23. Or pour i=11, on lit sur l'avant-dernière ligne, ce qui n'est pas 23.

Pour tenir compte de l'arrondi, on peut utiliser la norme sup (notée ) pour minimiser le maximum des différences . On obtient alors l'équation de droite (à quelque chose près).
On peut alors vérifier que toutes les différences sont inférieures à 0.5, l'erreur maximale d'arrondi. Donc cette proposition de droite est tout à fait réaliste.

Pour information, la droite qui m'a servi à construire les données est .

Sylviel
Modérateur
Messages: 6466
Enregistré le: 20 Jan 2010, 14:00

par Sylviel » 14 Juin 2013, 19:04

Intéressant ton exemple Léon, je garde en mémoire. Reste à voir si c'est généralisable à d'autres droites.

Sinon le soucis de la norme infinie c'est qu'elle est non différentiable, tu l'envoies telle quelle dans un solveur, ou tu as raffiné ?
Merci de répondre aux questions posées, ce sont des indications pour vous aider à résoudre vos exercices.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 14 Juin 2013, 19:07

Sylviel a écrit:Tu as la fonction qui est une brave fonction convexe.

Je ne crois pas qu'elle soit convexe : par exemple pour
alors il y a une infinité de triplets (a,b,c) minimisant f : on pose b=0, a=2, et c > 0

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 14 Juin 2013, 19:08

Sylviel a écrit:Sinon le soucis de la norme infinie c'est qu'elle est non différentiable, tu l'envoies telle quelle dans un solveur, ou tu as raffiné ?

Effectivement, la norme sup pose des soucis du fait qu'elle n'est pas différentiable.
Alors je m'arrange en bidouillant : je prends en fait la norme n pour n assez grand (20 par exemple).

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 14 Juin 2013, 19:59

Je me permettrai juste une petite observation : il me parait difficile de sortir des résultats avec 4 chiffres significatifs lorsque les données n'en comportent que 2.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 14 Juin 2013, 20:40

Dlzlogic a écrit:Je me permettrai juste une petite observation : il me parait difficile de sortir des résultats avec 4 chiffres significatifs lorsque les données n'en comportent que 2.

Je te retourne ton observation : c'est bien toi qui a écrit A = 0.95949 ? Tu penses quoi de ton résultat avec 5 chiffres significatifs alors que les données en ont 3 ?

D'autre part, cette considération n'a pas lieu d'être dans mon exemple qui montre une différence entre le minimum pour la norme 2 et le minimum pour la norme sup, où justement je tiens compte de l'arrondi, donc des chiffres significatifs.

Il te parait difficile d'avoir plusieurs chiffres significatifs sur le coeff directeur de la droite ? pourtant, le calcul donne ce résultat : 2.095 pour approcher 2.1

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 14 Juin 2013, 20:54

Bon, je retire mon observation.
Voilà ce que je n'ai pas osé dire : cherches-tu à démontrer qu'il n'y a pas de solution ou qu'il y en a une infinité ?
Généralement, si on fait ce genre de calcul, c'est pour trouver, connaissant la fonction, les valeurs de paramètres "les plus probables". N'oublies pas qu'ici, on est plutôt dans le domaine de la physique, et si on fait ce genre de calcul, c'est parce qu'on en a besoin.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 14 Juin 2013, 21:04

Sylviel a écrit:Tu as la fonction qui est une brave fonction convexe.

tu penses qu'elle est convexe ?

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 14 Juin 2013, 23:20

Dlzlogic a écrit:Voilà ce que je n'ai pas osé dire : cherches-tu à démontrer qu'il n'y a pas de solution ou qu'il y en a une infinité ?

Le problème est de chercher une fonction dont le graphe est proche du nuage de points.
Comme le mot "proche" n'est pas bien spécifié, il y a une infinité de solutions. On pourrait même dire que toute fonction convient ... si on regarde de très loin !

On peut dire aussi qu'il n'y a pas intrinsèquement de solution qui soit privilégiée par rapport aux autres.

En revanche, si on spécifie un peu comment on mesure la qualité d'une approximation, alors on peut hiérarchiser différentes approximations, dire que celle-ci est meilleure ou moins bonne. Dans les cas "favorables", on peut même espérer une unique fonction ayant une qualité maximale.

Bref, avoir une infinité de solutions, ne pas avoir de solution, en avoir une unique... tout dépend des règles du jeu !

Dlzlogic a écrit:Généralement, si on fait ce genre de calcul, c'est pour trouver, connaissant la fonction, les valeurs de paramètres "les plus probables".

en connaissant quelle fonction ? Quand on a un nuage de points, on ne connait pas de fonction : on en cherche une suivant certains critères...

Comme tu l'as fait remarqué au-dessus, il n'y a pas de contexte probabiliste dans notre problème. Donc parler de proba est assez étrange. Mais imaginons qu'il ait un contexte probabiliste : il faut alors probabiliser proprement l'ensemble des paramètres possibles. Je demande à voir un exemple où on calcule les paramètres les plus probables...


Dlzlogic a écrit:N'oublies pas qu'ici, on est plutôt dans le domaine de la physique, et si on fait ce genre de calcul, c'est parce qu'on en a besoin.

Encore une fois, il n'y a pas qu'en physique qu'on fait ce genre de calcul. Mais on en a déjà parlé de ça...

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 15 Juin 2013, 00:06

Bonsoir,
Oui, je comprends bien ce que tu dis.
Juste pour ne plus en parler
Encore une fois, il n'y a pas qu'en physique qu'on fait ce genre de calcul. Mais on en a déjà parlé de ça...
Je parlais de physique par opposition aux maths théoriques. Ce que je veux dire, c'est qu'on a un problème palpable, en relation direct avec le réel, qu'il soit physique, statistique, chimique, médical, politique, qu'importe, étant donné une série d'informations numériques, la question posée est de trouver une fonction capable de numériser cela, tout ceci étant sous le vocable "régression".

Par contre, c'est le reste qui me parait plus important et plus difficile.
On dispose d'une série de groupes de données.
J'appelle groupe un ensemble de résultats ponctuels d'une expérience. Le cas le plus simple est un couple XY, le cas des triplets est assez courant aussi.
On pose comme hypothèse de base que ces groupes sont liés par une relation mathématique. Pour les couples, on dispose en première approche des 4 fonctions suivantes faciles à mettre en oeuvre, parce qu'elles sont linéaires :
Y = A + BX
Y = a.exp(B.X)
Y = A + B ln X
Y = A.X^B
depuis peu, j'en ai rajouté une cinquième : Y = A . LnX/X
Donc en première approche, on choisit la meilleure, et on calcule les paramètres A et B.
Le choix de la meilleure se fait par le coefficient de détermination R². Donc il reste le calcul des coefficients A et B les meilleurs.
Dans ma culture, ce dernier est choix est celui qui minimise le carré des écarts.
Je n'ai pas vu d'argument contraire, et s'il y en avait, comment choisir, autrement dit, le problème admet une infinité de solutions. Dans les domaines d'étude que j'ai cités, cela n'est pas acceptable.

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 15 Juin 2013, 16:10

Bonjour,
J'ai mis au point une méthode de régression avec la formule y = c + a*exp(bx)
J'obtiens un emq comparable à la régression polynomiale. Par contre, je ne suis pas sûr de converger dans tous les cas. Mais ça ne m'empêchera pas de tester la méthode chaque fois que l'occasion se présentera.
Par contre, visuellement, c'est un peu plus joli, puisque la courbe est continuellement croissante.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 15 Juin 2013, 19:21

Dlzlogic a écrit:Pour les couples, on dispose en première approche des 4 fonctions suivantes faciles à mettre en oeuvre, parce qu'elles sont linéaires :
Y = A + BX
Y = a.exp(B.X)
Y = A + B ln X
Y = A.X^B
depuis peu, j'en ai rajouté une cinquième : Y = A . LnX/X

En fait, il n'y a qu'un régression linéaire, c'est Y = A.X + B
Toutes les autres régressions que tu présentes passent par des changements de variables exp() ou ln() sur X et/ou Y.
Mais il manque aussi des régression sur des phénomènes périodiques, avec des changements de variables en cos() ou sin().

Dlzlogic a écrit:Donc en première approche, on choisit la meilleure, et on calcule les paramètres A et B.
Le choix de la meilleure se fait par le coefficient de détermination R². Donc il reste le calcul des coefficients A et B les meilleurs.
Dans ma culture, ce dernier est choix est celui qui minimise le carré des écarts.
Je n'ai pas vu d'argument contraire, et s'il y en avait, comment choisir, autrement dit, le problème admet une infinité de solutions. Dans les domaines d'étude que j'ai cités, cela n'est pas acceptable.

tu dis que "Dans ma culture, ce dernier est choix est celui qui minimise le carré des écarts." Il se peut que ce "choix" soit cohérent avec ton activité. Mais encore une fois, il existe d'autre possibilités. En fait, c'est le contexte du problème qui doit guider la quantité que l'on veut minimiser.
Il y a des circonstances (majoration d'erreur, par exemple) où on veut minimiser l'écart maximal : on utilise alors la norme sup.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 15 Juin 2013, 19:25

Dlzlogic a écrit:Bonjour,
J'ai mis au point une méthode de régression avec la formule y = c + a*exp(bx)
J'obtiens un emq comparable à la régression polynomiale.

Si ta méthode est correcte, tu dois au moins obtenir ce que j'ai proposé, qui a un emq nettement moindre (disons 40% ou 50%) que pour la régression polynomiale de degré 4.

Dlzlogic a écrit:Par contre, je ne suis pas sûr de converger dans tous les cas.

c'est normal, car il y a effectivement des situations de non-convergence malheureusement.

Dlzlogic a écrit:la courbe est continuellement croissante.

oui, c'est une caractéristique à prendre en compte.

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 16 Juin 2013, 17:09

Bonjour Léon,
Si j'ai bien compris, La formule que tu proposes est Y = 5.6 * 1.56^X -25 (Message du 11/06/2013 23H15)
En utilisant ta formulation (équivalente), j'obtiens Y = 3.73 * exp(0.425 * X) -9.67
Avec la régression polynomiale, j'avais un emq = 206., avec ta formule, je trouve un emq = 236, avec ma formule je trouve un emq = 141. Ces deux derniers calculs ont été faits sur la même feuille Excel.
Il serait intéressant de savoir comment ton petit logiciel minimise.
D'ailleurs, ta première formule Y = -13 + 4.1 * 1.6^X était pas mal, puisqu'elle donnait un emq = 143.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 16 Juin 2013, 21:03

Salut
Dlzlogic a écrit:Si j'ai bien compris, La formule que tu proposes est Y = 5.6 * 1.56^X -25 (Message du 11/06/2013 23H15)

J'ai obtenu cette formule en supprimant les données 1420 (n°12) et 7720 (n°16) que l'on a supputées trop grandes (mais rien ne le justifie réellement). Du coup, c'est normal que le emq 228.4 de cette formule soit plus grand qu'espéré car les données n°12 et n°16 ont été réintégrées dans le calcul de l'emq. Mais si on enlève les données n°12 et n°16 pour calculer l'emq, on trouve un emq de 41 !

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 10 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite