Approximation fractionnaire

[invite18230371]

Bonjour,

On peut donner une approximation fractionnaire d'un réel par une écriture en fraction continue.

Dans la même idée, je me demande si il existe un algorithme donnant :
la fraction simple (=de dénominateur le plus faible possible) appartenant à un intervalle donné.

PS: L'idée serait que sachant une valeur et son incertitude, d'en donner une fraction la plus "simple" possible.

Merci pour vos retours suggestions,

Edit :
Soit [a,b] l'intervalle donnée,
Le denominateur est forcément <= à PARTIE_ENTIERE[1/(b-a)+1] ?
-----

[invite18230371]

Je viens de me faire cette réflexion/martingale :

On fait la décomposition en fraction continue de a et de b.
Dès que le développement de 'a' diffère de 'b' on prends la valeur moyenne de ces coefficients et on arrête ?

[SULREN]

Bonjour,

PS: L'idée serait que sachant une valeur et son incertitude, d'en donner une fraction la plus "simple" possible.

On peut utiliser:
- la décomposition en fractions continues
- La méthode de "l'arbre de Brocot", développée par Achille Brocot (horloger et mathématicien) à l'usage de ses confrères horlogers
- Des méthodes non analytiques mais par calcul numérique, comme celle que j'utilise pour mes propres besoins dans ce domaine (déterminer les trains d'engrenages réducteurs, pour les horloges astronomiques).

Donnez moi n'importe quel réel, la précision rélative avec laquelle la fraction doit le représenter, et je vous indiquerai la fraction la plus simple qui atteint cet objectif.

[SULREN]

Complément:
J'ai dit dans mon post ci-dessus:

Donnez moi n'importe quel réel

Mais comme on parle ici d'approxiamtion fractionnaire , j'aurais pu dire: "donnez moi n'importe quel nombre", réel, ou irrationnel (comme Pi), ou...

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Voir les "suites particulières", et on peut en inventer des tonnes

[stefjm]

Merci Médiat.

[invite18230371]

Un exemple surement beaucoup trop simple mais allons y:
434463/214 à +ou- 1E-3

Je regarde le pdf.

[invite18230371]

Ou encore 5291005/37037036
à 1E-8 près

[SULREN]

Re,

Un exemple surement beaucoup trop simple mais allons y:
434463/214 à +ou- 1E-3

Oui c'est un exercice du niveau cours moyen 2eme année

Déjà il aurait fallu le poser sous la forme du réel : 230,2009370000000000
et pas de la fraction 434463 / 214

Je trouve en quelques secondes :
434463 / 214 = 3 * 97/2 * 1493/107 = 2030,200937 soit erreur relative = 0

Et si je devais réaliser ce rapport au moyen d’un train d’engrenages dans lequel chaque engrenage ne doit pas excéder 131 dents, je l’écrirais :

434463 / 214 ~ 53/5 * 59/5 * 127/25 * 131/41 = 2030,200937 soit erreur relative = 0,00098804 millionièmes = 9 10^-10

Chaque fraction élémentaire étant réalisée par un étage d'engrenages. Exemple: 127/25 signifie roue de 127 dents engrenant sur pignon de 25 dents.
(oui, je ne fais pas des maths théoriques mais des réalisations pratiques....en bon vieux laiton d'horlogerie).

[SULREN]

Erratum: j'ai fait une erreur de frappe. Désolé.
Il faut lire:
"Déjà il aurait fallu le poser sous la forme du réel : 230,2009350000000000"

et pas ce que j'ai écrit:

Déjà il aurait fallu le poser sous la forme du réel : 230,2009370000000000

Idem 3 lignes plus bas: 35 et pas 37

Je prendrai plus le temps de me relire la prochaine fois.

[SULREN]

Re,

Ou encore 5291005/37037036
à 1E-8 près

5291005 / 37037036=(5*373*2837)/(2*2*53*174703) = 5/4 * 373/53 * 2837/174703

Qu'on peut approximer par des fractions comportant un maximum et un minimum, pour chaque terme du numérateur et du dénominateur, comme lorsqu'on utilise des trains d'engrenages.
Il suffit de préciser ce maximum et ce minimum ainsi que l'erreur relative admise dans cette approximation.

[SULREN]

Re,
Voici un exemple d'approximation de ce rapport, avec un train d’engrenages dont le cahier des charges serait le suivant:
- Comportant un maximum de 8 roues et pignons
- Avec un nombre maximum de dents pour les roues fixé à : 130
- Avec un nombre minimum de dents pour les pignons fixé à :13
(En mécanique générale on aime bien ne pas descendre en dessous de 13. En horlogerie, avec les pignons ogivaux, on peut descendre jusqu’à 6)

Votre rapport :
5291005 / 37037036 = 0,1428571390000

Aurait été réalisé comme suit :
34/47 * 38/75 * 64/93 * 64/113 = 0,1428571390007
Soit avec une erreur relative de 5,24 10^-12 , bien meilleure que le seuil que vous aviez spécifié.

J’arrête mes posts, parce qu’il ne s’agit pas là de mathématiques, science fondamentale, mais de "bidouilles" pour réalisations matérielles, et que je vais finir par irriter la Modération.

[invite18230371]

Vous répondez pas à ma question...
Qui est de trouver La fraction la plus simple possible (dénominateur le plus faible) qui entre dans un intervalle donné.

Typiquement dans le deuxieme cas 1/7 était valide...

[SULREN]

Re,

Vous répondez pas à ma question...

Désolé de vous avoir fait perdre du temps. Je n’interviendrai plus.

Votre idée du 1/7 était astucieuse je le reconnais (en plus elle me rappelle le 22/7 pour faire l’approximation de Pi dans les trainards des tours d’usinage).

Mais votre 1/7 donne le rapport recherché : 5291005 / 37037036 à 2,7*10^-8 et pas à 1*10^-8 spécifié sauf erreur de ma part.

Pour arriver à ce 10^-8 spécifié il faut le rapport : 3861004 / 27027029

(Ah.... 1 sou c’est 1 sou par chez nous ).

[SULREN]

Re,
Quant au cas précédent: 434463 / 214 à simplifier avec une approximation meilleure que 1*10^-3
La réponse était bien sûr: 2030 / 1 avec une erreur de 0,098 *10^-3

[SULREN]

Re,

Et si on accepte d'alourdir un peu la fraction on peut gagner beaucoup en précision:

10151 / 5 = 2030,00000 avec précision = 4,6*10^-7

[invite18230371]

Bonsoir,

Mais votre 1/7 donne le rapport recherché : 5291005 / 37037036 à 2,7*10^-8 et pas à 1*10^-8 spécifié sauf erreur de ma part.

Il me semble qu'il y a effectivement une erreur... Je trouve ça

Quant au cas précédent: 434463 / 214 à simplifier avec une approximation meilleure que 1*10^-3
La réponse était bien sûr: 2030 / 1 avec une erreur de 0,098 *10^-3

Non plus, mais effectivement 10151/5 était la réponse attendu.
434463/214 - 10151/5 = 9,346E-4 <1E-3

Bref, ce n'est pas pour tester les capacités ou faire des enigmes que j'ai posté, au moins ça illustre bien la question.
Je pensais qu'il existait une réponse simple et claire à cette problématique.

Apparemment pas vraiment.
Joyeux Noël,

[gg0]

Bizarre, ces erreurs à répétition :

"Mais votre 1/7 donne le rapport recherché : 5291005 / 37037036 à 2,7*10^-8 et pas à 1*10^-8 spécifié sauf erreur de ma part." Et justement, il y a une erreur (0,3857.. à la place de 2,7).
"10151 / 5 = 2030,00000 avec précision = 4,6*10^-7 " deux affirmations fausses
434463/214-2030/1 = 43/214 de l'ordre de 2*10^(-1) Très largement supérieur à 0,098 *10^-3 .

Sulren, tu devrais rechercher comment tu as pu te tromper aussi souvent !

Cordialement.

[SULREN]

Bonjour,

Bizarre, ces erreurs à répétition :
Sulren, tu devrais rechercher comment tu as pu te tromper aussi souvent !

A ggo :
Bonjour,
Nous sommes ici sur un forum de « mathématiques supérieures » et j’admets que ma formation d’ingénieur, remontant de surcroît aux années 1960, ne m’a donné qu’un tout petit niveau en mathématiques, comparé au niveau d’un Mathématicien.

Mais je prétends que mes calculs d’erreur sont justes et que toi et StrangQuark les trouvez faux, parce que nous ne parlons pas des mêmes choses.
StrangQuark a écrit :
- Au post#7 : 434463/214 à +ou- 1E-3
- Au post#8 : 5291005/37037036 à 1E-8 près

On m’a appris dans les années 1960 (mais l’enseignement a dû évoluer depuis) qu’il fallait dans ce cas prendre l’erreur comme une erreur relative et j’ai bien employé au post#9 deux fois le terme « d’erreur relative ».
Donc pour faire « 5291005/37037036 à 1E-8 » avec une fraction plus simple A/B il faut que :

-1*10^-8 < (A/B - 5291005/37037036) / ValeurAbsolue(5291005 / 37037036) < 1*10^-8
Et je trouve A / B = 3861004 / 27027029……et pas votre 1 / 7

Si nous ne savez pas ce que sont l’erreur relative et l’erreur absolue :
https://fr.wikipedia.org/wiki/Erreur_relative

En mathématiques pures, les approximations ne sont pas de mise, mais en mathématiques appliquées à la physique, on passe son temps à faire des approximations et à les exprimer en erreur relative.
Quand je vois sur un instrument de mesure, comme un multimètre, qu’il est de classe 1,5, cela ne signifie pas que ce multimètre fait une erreur de 1,5 volt, mais qu’il peut faire une erreur pouvant aller jusqu’à 1,5% de l’étendue d’échelle.
Mais j’irai quand même exposer ce débat sur les forums dédiés aux mathématiques et à la physique, en France et dans les pays anglo-saxons.

Bref, ce n'est pas pour tester les capacités ou faire des enigmes que j'ai posté, au moins ça illustre bien la question.
Je pensais qu'il existait une réponse simple et claire à cette problématique.
Apparemment pas vraiment.

Là encore je suis désolé.
N’étant qu’un micro-matheux, je ne connais pas de méthode analytique pour résoudre votre problème, mais il en existe peut-être.
Ce dont je suis sûr, c’est qu’il existe une méthode simple pour les « bricoleux comme moi ».
Je résous ce genre de problème en écrivant quelques lignes de code.
Je n’en avais pas déjà qui soient dédiés à votre problème, et j’ai donc répondu dans un premier temps à vos questions en détournant de son usage le code que j’utilise pour mes trains d’engrenages d’horloges astronomiques, et qui me permet de trouver que :

34/47 * 38/75 * 64/93 * 64/113 donne 5291005 / 37037036 à 5,24 10^-12

Hier j’ai écrit les quelques dizaines de ligne de code, que j’ai appelé « Simplification de fractions », qui répond exactement au problème que vous avez posé.

Si je lui donne comme entrées quelques chiffres de Pi sur quelques chiffres de e (de Neper).
- Titre du travail
- Numérateur = 314159265
- Dénominateur =271828182
- Que j’indique l’erreur relative admise
- Et que je fais ENTER.

Déjà il me fait remarquer, lors des saisies des données, que cette fraction se simplifie d’un rapport 3, puis en 1 seconde après ENTER il me sort le tableau ci-dessous, où on voit que la fraction approximative à 10^-8 est : 4600419 / 3980540
Le nombre à gauche est l’erreur relative en millionièmes (oui mon unité d’erreur est le 10^-6 dans mes calculs pour horloges astronomiques).
Les nombres à droite sont la décomposition du numérateur et du dénominateur en éléments simples.
Et il ajoute plus bas des solutions plus précises mais plus lourdes.

Cette discussion qui m’aura fait passer pour un gâteux(*) aura au moins eu l’avantage de me faire ajouter cet outil à ma liste d’autres outils numériques faits maison. Je vais quand même améliorer la présentation de son tableau de sortie.
Cordialement

(*) auprès de certains, car d’une façon générale je suis plutôt apprécié sur les autres forums.

[SULREN]

Et j'ajouterai aussi des digits dans le format d'édition des éléments simples des numérateurs et dénominateurs, parce que je vois que des digits ne sont pas sortis.

[SULREN]

Avec tous les digits présents.

[invite18230371]

StrangQuark a écrit :
- Au post#7 : 434463/214 à +ou- 1E-3
- Au post#8 : 5291005/37037036 à 1E-8 près

Je parle effectivement du delta autorisé (en absolue)

Et en relatif, dans les années 90, on parlait en %...
C'est l'enseignement qui a évoluer...

Ca n'a pas d'importance, maintenant si je vous donne un intervalle [a,b] pouvez vous explicitez l'algorithme permettant de trouver la fraction simple qui tombe à l'intérieur ?

[stefjm]

Pour mettre d'accord tout le monde, vu que personne n'a cité cette page : https://fr.wikipedia.org/wiki/Fracti...lan%C3%A9taire

https://fr.wikipedia.org/wiki/Fracti...on_rationnelle

[invite18230371]

Si je comprends votre remarque, vous proposez,
Sachant l'intervalle [A,B] dont on cherche une fraction la plus simple possible y appartenant.
On calcul x = (A+B)/2
Puis décomposition de x en fraction continue jusqu'a ce que le résidu soit inférieur à (A-B)/2.
La fraction trouvée est la plus simple possible appartenant à l'intervale [A,B]

Est-ce bien la votre réponse ?

[gg0]

Donc finalement, Sulren fait ses propres calculs, qui ne correspondent pas à la question posée, puis dit que les autres se trompent !! Drôle de mentalité. D'ailleurs tout à fait cohérente avec le ton de supériorité de ses messages initiaux.
Quand on prétend répondre mieux que les autres à une question, il vaut mieux l'avoir bien lue et comprise

[SULREN]

Re,

Donc finalement, Sulren fait ses propres calculs, qui ne correspondent pas à la question posée, puis dit que les autres se trompent !! Drôle de mentalité. D'ailleurs tout à fait cohérente avec le ton de supériorité de ses messages initiaux.
Quand on prétend répondre mieux que les autres à une question, il vaut mieux l'avoir bien lue et comprise

Ce que vous affirmez est faux cher monsieur et de la part d’un animateur c’est…….
StrangQuark a écrit :
Au post#8 : 5291005 / 37037036 à 1E-8 près
Sans préciser s’il s’agissait d’erreur absolue ou relative.

Je l’ai interprétée comme étant l’erreur relative, car c’est ce qui est le plus courant dans le domaine scientifique.
Et j’ai donné la réponse EXACTE : 3861004 / 27027029 à 1E-8 en erreur relative.


Stefjm a écrit :

Pour mettre d'accord tout le monde, vu que personne n'a cité cette page

Dès le post#3 j’ai écrit que notre ami pouvait résoudre son problème par les fractions continues ou par la méthode de Brocot.
Je les connais très bien toutes les deux parce que ma passion très ancienne pour les horloges astronomiques (dont celles de Stasbourg, de Bourges, etc) m’a conduit à découvrir que les génies qui ont conçu ces mécanismes (dont Jean Baptiste Schwilgué) avaient calculé leurs trains d’engrenages avec ces méthodes. Les fractions continues étaient utilisées par les mathématiciens indiens déjà au Moyen Age.

Mais ils n’avaient pas la chance d’avoir comme nous, sur leur bureau, l’énorme puissance de calcul que nous procurent nos PC.
J’utilise donc des algorithmes numériques de mon cru, qui sont bien plus rapides à mettre en œuvre et qui ne ratent aucune solution qui conviendrait, alors que ce peut être le cas pour les deux méthodes citées.
J’ai un doute là-dessus, né en recalculant certains des trains d’engrenages qu’ils avaient retenus pour leur horloges (moins bons que mes résultats, mais ce pouvait être : soit par insuffisance de leur méthode, soit par choix délibéré d’un train moins performant mais répondant mieux à d’autres critères dans leur choix : équilibre esthétique, etc).
Je n’ai pas encore pris de temps d’essayer de lever ce doute (parce qu'il ne m'empêche pas de dormir), en cherchant pour un même problème, les solutions par leurs deux méthodes et par la mienne, et de faire des comparaisons.

Ca n'a pas d'importance, maintenant si je vous donne un intervalle [a,b] pouvez vous explicitez l'algorithme permettant de trouver la fraction simple qui tombe à l'intérieur ?

Justement, je ne vous donnerai pas un executable de mon code et vous laisserai chercher vos solutions par les deux méthodes citées, et je serais heureux que vous veniez les indiquer ici.
Cela nous donnera l’occasion de vérifier qu’elles ne ratent aucune solution, ou qu’au contraire mes doutes étaient fondés.

[SULREN]

Re,

A StrangQuark:

Je donne en PJ quelques exemples simples qui permettront de comparer les résultats trouvés avec mon nouvel outil et ceux trouvés avec Brocot et les Fractions Continues, pour le cas où vous voudriez vous entraîner sur ces méthodes.

Il s'agit d'exemples simples en ce sens qu'il n'y a que 6 digits dans les numérateurs et les dénominateurs.

La comparaison m'intéresse (égoïstement) parce qu'elle me permettrait de vérifier que mon outil créé hier, dans les brumes non encore dissipées du réveillon, tiend la route. D'avance merci.
Je ferai moi même l'exercice de comparaison avec la méthode de Brocot....que j'aime bien parce qu'elle est facilement applicable par les horlogers, qui ne sont pas tous matheux, tant s'en faut.

J'en avais donné une description ici, il y a 11 ans:
https://passion-usinages.forumgratui...ghlight=Brocot

[invite18230371]

La communication c'est compliquée.

Message #1:

Bonjour,
On peut donner une approximation fractionnaire d'un réel par une écriture en fraction continue.

Ensuite je n'ai que faire de vos exécutables, on trouve facilement des martingales pour approximer l'importe quel nombre sur le net.

Moi ce que je demande c'est LA fraction simple (dénominateur le plus petit possible) entre A et B.
Elle est unique.

Par exemple,
- Si approximer (A+B)/2 jusqu’à un résidu de inférieur à (A-B)/2 garantie qu'on trouve LA fraction la plus simple ?
- Peut être, mais je reste circonspect...

Aujourd'hui je pense qu'il suffit de faire l'écriture en fraction continue de A et de B,
Dès que les coefficients divergent, on garde le plus grand des 2 et on tronque.
Mais je reste dans le doute que ce soit la bonne solution, c'est juste (à ce stade) une martingale.
>>>Très étonné que personne n'est une réponse claire. ^^

Sinon, maintenant que le problème est claire, un dernier exemple pour SULREN afin qu'il puisse au moins trouver une bonne réponse et laver son honneur.

On cherche la fraction la plus simple dans [A ; B]
Avec :
A = 977/684
B = 973/681

[Verdurin]

En fait j'ai l'impression que « la fraction la plus simple » n'est pas unique.
Par exemple en prenant a=0,5 et b=2,1 on a deux fractions de dénominateur 1 dans l'intervalle [a;b].

Mais il est clair que le dénominateur minimal est unique : c'est un entier naturel et tout ensemble d'entiers naturels a un plus petit élément.

Pour la réponse à ta dernière question

 Cliquez pour afficher

10/7

Mais je ne saurais pas faire dans le cas général.

[Médiat]

Avec x < y Il faut trouver le plus petit n tel que E(nx) < E(ny)