Le 09/11/2023 20:48, robby a écrit :
Hello !
je ne suis pas bon pour les résolutions en nombres entiers :-/
soit a,b deux réels positifs.
je cherche k entier
tel que a + k b soit à moins de epsilon d'un entier.
→ combien vaut k ?
J'espère que tu auras eu mes réponses précédentes, parce que je ne vais pas
tout détailler ici. Cela dit, l'affichage de mon programme devrait te permettre
quand même de comprendre ce que je ne rappellerai pas ici, ou sinon le code
source lui-même du programme en python.
Tout d'abord, je rappelle que si b est entier ou rationnel, tu n'auras pas
forcément de solution pour un epsilon trop petit. Par exemple, si a vaut pi
mais b vaut 1/5, pour différentes valeurs de k tu obtiendras :
3,14159...
3,34159...
3,54159...
3,74159...
3,94159...
4,14159...
et la plus petite distance possible à un entier sera 0,05840... pour k = 5m+4
Au contraire, si b est irrationnel, alors tu auras toujours des solutions quel
que soit epsilon.
Pour simplifier le problème, je commence par calculer la partie entière et la
partie fractionnaire de a et de b (respectivement a1 et b1 pour la partie
entière, a2 et b2 pour la partie fractionnaire). On est bien d'accord que
si (a2 + k b2) est proche d'un entier, alors il en sera de même pour (a + k b)
qui est égal à (a1 + k b1) + (a2 + k b2).
Je calcule alors la fraction continue (ou continuée) de b2, et ses réduites
successives, jusqu'à ce que le dénominateur de la réduite soit supérieur ou
égal à 1/epsilon. Si tu ne sais pas ce que sont une fraction continue ou
une réduite, je te laisse cherche sur la toile, ainsi que le théorème de
meilleure approximation rationnelle.
Ensuite... eh bien je l'ai détaillé dans des messages précédents, et sinon
tu pourras lire le programme Python.
Comme illustration, voici quatre exemples avec un epsilon de plus en plus petit
pour a = e et b = pi :
=================================================================================
a = 2.718281828459045 = 2 + 0.7182818284590451 (a1 + a2)
b = 3.141592653589793 = 3 + 0.14159265358979312 (b1 + b2)
profondeur = 2
Fraction continue de b2 : [0, 7]
Réduite de b2 : 1/7 = 0.14285714285714285
Ceci convient pour epsilon ≥ 1/7 = 0.14285714285714285
delta = 7 × b2 - 1 = -0.008851424871448188
delta est négatif, on calcule incr = (a2)/(− delta)
incr = 81.14872338531485, arrondi à 81
Le nombre k cherché vaut 81 × 7 = 567
Vérifions : a + k × b
= 2.718281828459045 + 567 × 3.141592653589793
= 1784.0013164138718 (pour epsilon ≥ 0.14285714285714285)
a = 2.718281828459045 = 2 + 0.7182818284590451 (a1 + a2)
b = 3.141592653589793 = 3 + 0.14159265358979312 (b1 + b2)
profondeur = 3
Fraction continue de b2 : [0, 7, 15]
Réduite de b2 : 15/106 = 0.14150943396226415
Ceci convient pour epsilon ≥ 1/106 = 0.009433962264150943
delta = 106 × b2 - 15 = 0.008821280518070296
delta est positif, on calcule incr = (1 − a2)/(delta)
incr = 31.93619916789386, arrondi à 32
Le nombre k cherché vaut 32 × 106 = 3392
Vérifions : a + k × b
= 2.718281828459045 + 3392 × 3.141592653589793
= 10659.000562805037 (pour epsilon ≥ 0.009433962264150943)
a = 2.718281828459045 = 2 + 0.7182818284590451 (a1 + a2)
b = 3.141592653589793 = 3 + 0.14159265358979312 (b1 + b2)
profondeur = 4
Fraction continue de b2 : [0, 7, 15, 1]
Réduite de b2 : 16/113 = 0.1415929203539823
Ceci convient pour epsilon ≥ 1/113 = 0.008849557522123894
delta = 113 × b2 - 16 = -3.014435337789223e-05
delta est négatif, on calcule incr = (a2)/(− delta)
incr = 23828.07219165068, arrondi à 23828
Le nombre k cherché vaut 23828 × 113 = 2692564
Vérifions : a + k × b
= 2.718281828459045 + 2692564 × 3.141592653589793
= 8458942.000002176 (pour epsilon ≥ 0.008849557522123894)
a = 2.718281828459045 = 2 + 0.7182818284590451 (a1 + a2)
b = 3.141592653589793 = 3 + 0.14159265358979312 (b1 + b2)
profondeur = 5
Fraction continue de b2 : [0, 7, 15, 1, 292]
Réduite de b2 : 4687/33102 = 0.1415926530119026
Ceci convient pour epsilon ≥ 1/33102 = 3.0209655005739834e-05
delta = 33102 × b2 - 4687 = 1.9129332031297963e-05
delta est positif, on calcule incr = (1 − a2)/(delta)
incr = 14727.026070749831, arrondi à 14727
Le nombre k cherché vaut 14727 × 33102 = 487493154
Vérifions : a + k × b
= 2.718281828459045 + 487493154 × 3.141592653589793
= 1531504913.9999995 (pour epsilon ≥ 3.0209655005739834e-05)
=================================================================================
C'est très efficace parce que la fraction continue de pi comporte
plusieurs grands nombres (7, 15, 292) et que donc les approximations
sont très bonnes.
Au contraire, avec a = pi et b = e, c'est beaucoup moins efficace
parce que la fraction continue de e comporte beaucoup de 1. Du coup
je vais directement à la profondeur 12 de fraction continue pour avoir
un résultat à peu près convenable :
=================================================================================
a = 3.141592653589793 = 3 + 0.14159265358979312 (a1 + a2)
b = 2.718281828459045 = 2 + 0.7182818284590451 (b1 + b2)
profondeur = 12
Fraction continue de b2 : [0, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8]
Réduite de b2 : 6137/8544 = 0.7182818352059925
Ceci convient pour epsilon ≥ 1/8544 = 0.00011704119850187266
delta = 8544 × b2 - 6137 = -5.764591878687497e-05
delta est négatif, on calcule incr = (a2)/(− delta)
incr = 2456.247667996775, arrondi à 2456
Le nombre k cherché vaut 2456 × 8544 = 20984064
Vérifions : a + k × b
= 3.141592653589793 + 20984064 × 2.718281828459045
= 57040603.000014275 (pour epsilon ≥ 0.00011704119850187266)
=================================================================================
Et voici maintenant le programme Python, avec quelques commentaires (les
autres explications étant les "print").
=================================================================================
#!/usr/bin/env python3
import math
# La fonction fraction_continue(reel, profondeur) calcule la fraction
# continue (ou continuée) d'un réel jusqu'à une profondeur donnée.
# Par exemple, la fraction continue de pi est [3] à la profondeur 1,
# [3, 7] à la profondeur 2, et [3, 7, 15, 1, 292] à la profondeur 5.
def fraction_continue(reel, profondeur):
fracont = list()
resid = reel
etape = 0
while etape < profondeur:
etape += 1
entier = int(resid)
fracont.append(entier)
frac = resid - entier
if frac == 0:
break
resid = 1/frac
#print(etape, ":", fracont)
return fracont
# La fonction reduite(fracont) calcule la réduite d'un nombre réel
# obtenue à partir d'une de ses fractions continues.
# Le résultat est rendu sous la forme d'une paire d'entiers qui sont
# respectivement le numérateur et le dénominateur du nombre rationnel
# écrit sous la forme d'une fraction irréductible.
def reduite(fracont):
if len(fracont) == 0:
return (0, 1)
if len(fracont) == 1:
return (fracont[0], 1)
numer, denom = reduite(fracont[1:])
return (fracont[0]*numer + denom, numer)
# La fonction robby(a, b, ...) tente de trouver un nombre k tel que
# a + k⋅b soit aussi proche que possible d'un entier.
#
# Dans sa requête sur fr.sci.maths robby demandait de fixer le nombre
# epsilon devant être la distance maximale du résultat à un entier,
# mais ici nous choisissons de déterminer un epsilon en fonction de
# la profondeur du calcul de la fraction continue de b. C'est le
# paramètre profondeur de la fonction.
#
# Note : a et b sont censés être des réels strictement positifs.
# Qui plus est, b est censé être irrationnel (ce qui est forcément
# impossible avec les nombres en représentation IEEE 754).
def robby(a, b, profondeur):
# Commençons par réduire a et b en partie entière et partie
# fractionnaire.
a1 = math.floor(a); a2 = a - a1
b1 = math.floor(b); b2 = b - b1
print(f"a = {a} = {a1} + {a2} (a1 + a2)")
print(f"b = {b} = {b1} + {b2} (b1 + b2)")
print(f"profondeur = {profondeur}")
# Maintenant on calcule la fraction continue de b2, à la
# profondeur demandée. Noter que, puisque b2 est compris
# entre 0 et 1, le premier nombre de la fraction continue
# sera toujours zéro.
fracont = fraction_continue(b2, profondeur)
print(f"Fraction continue de b2 : {fracont}")
numer, denom = reduite(fracont)
approx = numer/denom
print(f"Réduite de b2 : {numer}/{denom} = {approx}")
epsilon = 1/denom
print(f"Ceci convient pour epsilon ≥ 1/{denom} = {epsilon}")
delta = denom * b2 - numer
print(f"delta = {denom} × b2 - {numer} = {delta}")
if delta > 0:
print("delta est positif, on calcule incr = (1 − a2)/(delta)")
incr = (1 - a2)/delta
elif delta < 0:
print("delta est négatif, on calcule incr = (a2)/(− delta)")
incr = - a2/delta
else:
print("delta est nul, on ne peut rien faire de mieux")
return
intincr = round(incr)
print(f"incr = {incr}, arrondi à {intincr}")
k = intincr * denom
print(f"Le nombre k cherché vaut {intincr} × {denom} = {k}")
resultat = a + k * b
print(f"Vérifions : a + k × b")
print(f" = {a} + {k} × {b}")
print(f" = {resultat} (pour epsilon ≥ {epsilon})")
print()
for profondeur in range(2, 6):
robby(math.e, math.pi, profondeur)
robby(math.pi, math.e, 12)
=================================================================================
Cordialement,
-- Olivier Miakinen
solve a + k b ~ entier ( i.e. à moins d'epsilon d'un entier )
Re: solve a + k b ~ entier ( i.e. à moins d'epsilon d'un entier )
