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

Sara1993

Bonjour
Est-ce qu’il y aurait une meilleure approximation rationnelle de la racine carrée d’un rationnel ? 

Merci d’avance.

Math Coss

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.

Sara1993

Par la famille des meilleurs approximations, vous désignez peut-être les réduites dans les fractions continues? 

Area 51

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).

Héhéhé

La méthode d'Héron est très efficace pour cela.

Ludwig

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}$?

Sara1993

Merci pour votre éclaircissement.

Poirot

@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

Bonjour,
Ludwig : on dirait bien en regardant les 5 premières valeurs x1, x2, x3, x4 et x5.
Bien cordialement.
kolotoko

Ludwig

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.

Héhéhé

Un peu bizarre d'utiliser une formule faisant intervenir $\sqrt 2$ pour calculer $\sqrt 2$.

Math Coss

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]

Ludwig

Ah oui c'est sûr !
Mais ici en fait ce n'est pas pour calculer $\sqrt 2$, c'est pour prouver que $x_n=r_{2^n}$.

kolotoko

Bonsoir,

On pourra consulter : A001601, A051009, A001333, A000129 de O.E.I.S.

Bien cordialement.

kolotoko

Ludwig

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.

kolotoko

Bonjour,

je ne me vois pas faire la 3ième division !

Bien cordialement.

kolotoko

Ludwig

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.

LP2

@Ludwig

Ludwig

Merci @LP2

Ludwig

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

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.

Ludwig

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.