Minimiser une combinaison de nombres réels

Bonjour,

pour minimiser une combinaison linéaire de deux nombres réels linéairement indépendants, je pense que les fractions continues sont le bon outil : si $p\over q$ est une réduite de $\alpha\over \beta$, où $\alpha$ et $\beta$ sont deux réels linéairement indépendant alors $|p\beta-q\alpha|<{C\over q}$.

Je me pose la question suivante : comment ça se passe dans le cas de trois nombres linéairement indépendants ?
Par exemple, que vaut :
$$
\min\{|ae +b\pi+c\sqrt{2}|\},
$$
où $a,b,c\in\mathbb{Z}$ et $|a|,|b|,|c|\leq 100$ ?
Et pour 4 nombres ou plus ? Est-ce que c'est l'algorithme LLL qu'il faut utiliser ?
Merci pour vos lumières si la question vous intéresse, bien à vous,

HT

Réponses

  • Bonjour,

    Je n’ai aucune idée sur une méthode générale.

    Voici ce que j’ai fait.

    Je tronque les irrationnels à deux chiffres significatifs : $e=2,7$, $\pi=3,1$ et $\sqrt{2}=1,4$.

    La fonction à minimiser devient $(2a +3 b+c)+(7a+ b+4c)/10$ et on annule le système $2 a+3 b+c=0,7 a+b+4 c=0$ : $19 a=-11 c, 19 b=c$.

    Et voilà : on a zéro.

    Si on tronque à trois chiffres significatifs, on obtient un système dont le discriminant n’a aucune raison de s’annuler et la seule solution sera à exclure (car $a=b=c=0$ est exclu).

    Mais on peut imposer que la troisième équation, celle qui correspond à $1/100$, soit égale au discriminant du système : la solution en entiers relatifs devrait donner un résultat assez bas.

    Cette méthode ne permet pas d’aller plus loin car on a que trois paramètres.

    Ici, avec $e=2,71$, $\pi=3,14$ et $\sqrt{2}=1,41$ on trouve pour le troisième équation $a+4b+c=12$ car $12$ est le discriminant. La solution est $a=-11, b=1,c=19$ et le minimum est $12/100$.
  • Je n'y connais absolument rien, mais en gros c'est ça, non ? https://en.wikipedia.org/wiki/Lattice_problem (This article may be incomprehensible or very hard to understand.)
  • Bonjour,

    J’ai trouvé encore mieux.

    On tronque à $n$ chiffres significatifs.
    On écrit $e=E. 10^{-n}$, $\pi=P.10^{-n}$ et $\sqrt{2}=S.10^{-n}$ avec des écritures décimales.

    On choisit $a=P.S$, $b=E.S$ et $c=-2.E.P$ et la fonction atteint $0.$
    On peut diviser $a,b,c$ par leur pgcd.

    Ça marche pour tout $n$. On remplace $2$ par $n-1.$

    Ça marche aussi pour un nombre quelconque de paramètres.

    Ai-je résolu ce problème ? Oui, sauf si la contrainte $\max(a,b,c)<100$ est cruciale car rien ne garantit cette contrainte.
  • Mots clefs: lattice reduction, Integer relation algorithm.

    Algorithme PSLQ (à ne pas confondre avec PSQL)
    https://en.wikipedia.org/wiki/Integer_relation_algorithm

    Algorithme LLL:
    https://fr.wikipedia.org/wiki/Algorithme_LLL

    Et on peut lire aussi:

    http://mathworld.wolfram.com/IntegerRelation.html

    NB:
    Apparemment C. Hermite avait un algorithme lorsqu'on est en présence de trois réels, si je lis bien.

    PS:
    Quand on est en présence de nombres qui sont rationnellement indépendants, les coefficients ont tendance à "exploser" et ce, d'autant plus que lorsqu'on augmente la précision retenue pour ces nombres.
    (un algorithme travaille avec des nombres décimaux)

    PS2:
    le programme PARI GP est doté d'une telle fonction.
    On entre un vecteur dont les composantes sont des nombres décimaux, et en sortie, on obtient un vecteur dont les composantes sont des entiers. La (valeur absolue de la) combinaison linéaire résultant est censée être minimisée
  • Merci à tous pour vos réponses, je vais creuser la question. Il me semblait bien que ça ressemblait à quelque chose qui se traite avec LLL. Ca va me donner l'occasion de mettre un peu le nez dans cet algorithme ;-)
    Bonne semaine à tous,
    HT
  • Quand on entre dans PARI GP le vecteur $(\text{e},\pi,\sqrt{2})$ on obtient (avec une précision de $50$ chiffres après la virgule pour ces trois nombres) en sortie le vecteur $(2399128336310320, -2252602581540431, 392622992498789)$.

    Quand on calcule la valeur absolue de cette combinaison linéaire on obtient: $9,754194669123998059\times 10^{-32}$
  • Merci Fin de partie pour l'exemple. La précision obtenue semble suggérer une approximation en $1\over {n^2}$, où $n$ serait une borne pour la taille des coefficients.
    Je n'ai pas PARI installé alors j'ai programmé avec Maple et en force brute pour obtenir : $$

    |-22\pi+60e-91\sqrt{2}|\simeq 2,4\times 10^{-5}

    $$ pour $n=100$ et $$

    |-749\pi+572e+169\sqrt{2}|\simeq 3,8 \times 10^{-6}

    $$ pour $n=1000$. Ce qui semble encore compatible avec du $1\over {n^2}$ mais je n'ai aucune espèce d'idée pour démontrer ce genre de majoration...
    HT
Connectez-vous ou Inscrivez-vous pour répondre.