Approximation rationnelle de la racine carrée d’un rationnel

Sara1993
Modifié (March 2023) dans Arithmétique
Bonjour
Est-ce qu’il y aurait une meilleure approximation rationnelle de la racine carrée d’un rationnel ? 
Merci d’avance.

Réponses

  • Math Coss
    Modifié (March 2023)
    Il n'y a pas une meilleure approximation puisque l'on peut approcher un irrationnel aussi près que l'on veut. En revanche, il y a une famille de meilleures approximations : étant donné un entier $Q$, parmi les fractions dont le dénominateur est au plus $Q$, laquelle est la plus proche du nombre ? Réponse donnée par la théorie des fractions continu(é)es.
  • Par la famille des meilleurs approximations, vous désignez peut-être les réduites dans les fractions continues? 
  • Pour les irrationnels quadratiques, ça se passe bien, leur mesure d'irrationnalité vaut $2$ (avec une fraction continue périodique, résultat remontant à Lagrange). Mais ça se passe moins bien pour de nombreux irrationnels transcendants dont la mesure d'irrationnalité est $> 2$ et qui ne pourront jamais être approchés à $\dfrac{1}{q^2}$ près (cf. Khintchin).

  • La méthode d'Héron est très efficace pour cela.
  • Ludwig
    Modifié (March 2023)
    Je regardais les premières réduites de $\sqrt{2}$ : $r_1=1$, $r_2=3/2$, $r_3=7/5$, $r_4=17/12$, etc. En commençant avec $x_0=1$ les fractions obtenues par la méthode de Héron sont : $x_1=3/2$, $x_2=17/12$, $x_3=577/408$, etc. Est-il vrai que $x_n=r_{2^n}$?
  • Merci pour votre éclaircissement.
  • @Area 51 Justement, si un irrationnel (nécessairement transcendant d'après le théorème de Roth) a une mesure d'irrationnalité $> 2$, alors on peut l'approcher en $\frac{1}{q^2}$, et même mieux que ça. En fait tous les irrationnels sont approchables en $\frac{1}{q^2}$ d'après Dirichlet.
  • kolotoko
    Modifié (March 2023)
    Bonjour,
    Ludwig : on dirait bien en regardant les 5 premières valeurs x1, x2, x3, x4 et x5.
    Bien cordialement.
    kolotoko
  • Ludwig
    Modifié (March 2023)
    Je l'ai vérifié jusqu'à $n=10$. Pour les fractions $x_n$ obtenues par la méthode de Héron pour approcher $\sqrt{2}$ le site Wolfram Alpha donne la formule $x_n=\sqrt{2}\coth(2^n\tanh^{-1}(\sqrt{2}))$. D'où sort cette formule je n'en sais rien du tout mais on peut la réécrire sans les fonctions hyperboliques et du coup poser : $$y_m=\sqrt{2} ~~ \frac{\left(\sqrt{2} + 1 \right)^{m} + \left(\sqrt{2} - 1 \right)^{m}}{\left(\sqrt{2} + 1 \right)^{m} - \left(\sqrt{2} - 1 \right)^{m}}.$$ Si $m=2^n$ ($n\geq 1$) alors $y_m=r_m=x_n$ ($r_m$ est la m-ième réduite de $\sqrt{2}$), sinon $r_m=2/y_m$. On doit pouvoir démontrer cela par récurrence en utilisant le binôme de Newton ?

    Il y a sans aucun doute le même genre de formules pour la racine carrée d'un rationnel quelconque et cela montre à quel point la méthode de Héron est efficace pour approcher une telle racine.
  • Un peu bizarre d'utiliser une formule faisant intervenir $\sqrt 2$ pour calculer $\sqrt 2$.
  • Math Coss
    Modifié (March 2023)
    Pas tant, dans la mesure où le numérateur est un entier et le dénominateur un multiple entier de $\sqrt2$, de sorte que $y_m$ est un rationnel. Illustration.
    sage: K.< r2 > = NumberField(x^2-2)
    sage: def f(m):
    ....:     return r2*((r2+1)^m+(r2-1)^m)/((r2+1)^m-(r2-1)^m)
    ....: 
    sage: [f(m) for m in range(1,10)]
    [2, 3/2, 10/7, 17/12, 58/41, 99/70, 338/239, 577/408, 1970/1393]
    sage: map(n, _)  # calcul numérique
    [2.00000000000000, 1.50000000000000, 1.42857142857143, 1.41666666666667, 1.41463414634146, 1.41428571428571, 1.41422594142259, .41421568627451, 1.41421392677674]
  • Ah oui c'est sûr ! :smiley:
    Mais ici en fait ce n'est pas pour calculer $\sqrt 2$, c'est pour prouver que $x_n=r_{2^n}$.
  • Bonsoir,
    On pourra consulter : A001601, A051009, A001333, A000129 de O.E.I.S.
    Bien cordialement.
    kolotoko
  • On a bien $x_n=r_{2^n}$. C'est un cas particulier (prendre $k=2$) de l'égalité $(3.15a)$ de cet article : 
    On two sequences of algorithms for approximating square roots, A. K. Yeyios, 1991.

    La méthode de Héron est d'ordre $2$. Yeyios montre qu'on peut construire des méthodes itératives d'ordre $k$, pour n'importe quel entier $k$. Il semblerait que l'idée de la méthode revienne à un certain M. A. Grant (Approximating square roots, Math. Gaz. Note 66.36 (1982). Si quelqu'un débusque cet article je suis preneur.

    Voir aussi K. R. Johnson, An iterative method for approximating square roots, Math. Mag. 62 (1989). La lecture est possible en ligne à condition de se créer un compte. On pourrait télécharger directement le pdf ?

    Voici ce que cela donne pour l'ordre $4$ et pour le calcul de la racine carrée de $2$. On prend $x_0=1$ puis : $$x_{n+1}=\frac{{x_n}^4+12{x_n}^2+4}{4x_n({x_n}^2+2)}.$$ On obtient : $x_1=17/12$, $x_2=665857/470832$, $x_3=\frac{1572584048032918633353217}{1111984844349868137938112}$, respectivement les réduites de rang $4$, $4^2$ et $4^3$. Si je ne me suis pas trompé, douze multiplications, neuf additions et trois divisions suffisent pour calculer $x_3$, nombre qui approxime $\sqrt {2}$ à moins de $3\times 10^{-49}$ près.
  • Bonjour,
    je ne me vois pas faire la 3ième division !
    Bien cordialement.
    kolotoko
  • Et tu aurais bien raison de ne pas la faire ! Celle-ci et les deux d'avant. Car il vaut mieux calculer séparément les numérateurs et les dénominateurs. Si $x_n=p_n/q_n$ alors on a : $$p_{n+1}={p_n}^2({p_n}^2+12{q_n}^2)+4{q_n}^4, \quad \quad q_{n+1}=4p_n q_n({p_n}^2+2{q_n}^2).$$ Du coup il faut $30$ multiplications et $9$ additions pour avoir $x_3$. C'est rien du tout vu la précision obtenue.
  • Ludwig
    Modifié (March 2023)
    Dans cet article Yeyios définit par récurrence des fractions rationnelles $f_k(x)=P_k(x)/Q_k(x)$ qui permettent d'approcher la racine carrée d'un entier $N$ de façon itérative : on prend pour $x_0$ la partie entière de cette racine puis on fait $x_{n+1}=f_k(x_n)$. La convergence est alors d'ordre $k$. Il pose $P_0(x)=x$ et $Q_0(x)=1$ puis définit : $$P_{k+1}(x)=xP_k(x)+NQ_k(x), \quad \quad Q_{k+1}(x)=xQ_k(x)+P_k(x).$$ J'ai donné par exemple cette fraction un plus haut, pour $N=2$ et $k=4$. 

    On peut demander à un logiciel de déterminer ces premières fractions, le tableur de GeoGebra le fait sans problème. Pour $N=2$ j'ai constaté que l'écriture développée des numérateurs et dénominateurs ne comporte que des entiers produits de nombres premiers inférieurs ou égaux à $k$. Exemple pour $k=12$ : $$P_{12}(x)=x^{12} + 132 \; x^{10} + 1980 \; x^{8} + 7392 \; x^{6} + 7920 \; x^{4} + 2112 \; x^{2} + 64,\\ Q_{12}(x)=12 \; x^{11} + 440 \; x^{9} + 3168 \; x^{7} + 6336 \; x^{5} + 3520 \; x^{3} + 384 \; x.$$ On pourrait le démontrer par récurrence ? Je ne vois pas comment faire. Et que ce soit vrai en général me paraît assez douteux..

  • Magnéthorax
    Modifié (March 2023)
    Bonsoir,

    Quand on applique la méthode de Newton à $f\left(x\right)=x^2-a^2$, l'itératrice est la petite fonction rationnelle $\varphi\left(x\right)=1/2\left(x+a^2/x\right)$ : il faut $u_n$ et $1/u_n$ pour calculer $u_{n+1}$. Quand on applique la méthode de Newton à $g\left(x\right)=1/a^2-1/x^2$, l'itératrice est un petit polynôme de degré 3.
  • Oui, et ces deux méthodes sont d'ordre $2$. Mais la méthode de Newton a l'avantage de toujours donner des réduites. Et puis, si on veut des fractions, peu importe qu'il y ait le calcul de $1/u_n$, car on va calculer séparément les numérateurs et dénominateurs.
Connectez-vous ou Inscrivez-vous pour répondre.