Dans ce devoir, le but est d'étudier différentes méthodes d'approximation de $\sqrt{2}$.
Le devoir est à rendre avant le lundi 07/03/2022, 15h, sur la page Moodle du cours.
Question 1 : Stocker dans une variable S la valeur approchée de $\sqrt{2}$ avec une précision de $10000$ bits. Pour cela, on créera l'objet RealField(10000) qui permet de calculer des réels avec $10000$ bits de précision.
Théon de Smyrne (I$^{er}$ et II$^{ème}$ siècle après JC) a défini deux suites entières $(p_n)$ et $(q_n)$ qui permettent de calculer une valeur approchée $\frac{p_n}{q_n}$ de $\sqrt{2}$.
Les suites sont définies de la sorte. Les termes initiaux sont $p_0 = q_0 = 1$, et la relation de récurrence est : $$ p_{n+1} = p_n + 2q_n \quad \text{ et } \quad q_{n+1} = p_n + q_n $$
Question 2 : Écrire une fonction theon(n) qui calcule la valeur de $p_n/q_n$ à l'ordre n.
Question 3 : Déterminer le plus petit entier $n$ tel que $|\frac{p_n}{q_n} - \sqrt{2}| < 10^{-1000}$. Pour cela, on utilisera la grandeur S calculée à la question 1.
La méthode de Héron s'apparente à une méthode générale dit "méthode de Newton". L'idée est de chercher une solution de l'équation $x^2 - 2 = 0$, en suivant les tangentes à la courbe $y = x^2 - 2$. Pour plus de précisions (non nécessaires pour cet exercice), voir :
https://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton
Dans notre cas, on définit une suite la suite $(u_n)$ de premier terme $u_0 = 1$, et définie par récurrence par :
$$ u_{n+1} = u_n/2 + 1/u_n $$Question 4 : Écrire une fonction heron(n) qui calcule la valeur de $u_n$ à l'ordre n.
Question 5 : Déterminer le plus petit entier $n$ tel que $|u_n - \sqrt{2}| < 10^{-1000}$.
La méthode de Halley permet une approximation encore plus rapide de $\sqrt{2}$.
Si l'on cherche une approximation rationnelle sous la forme $p_n/q_n$, alors les suites $(p_n)$ et $(q_n)$ peuvent définies par les termes initiaux $p_0 = q_0 = 1$, et par la relation de récurrence : $$ p_{n+1} = p_n \cdot (p_n^2 + 6 q_n^2) \quad \text{ et } \quad q_{n+1} = q_n \cdot (3 p_n^2 + 2 q_n^2) $$
Question 6 : Écrire une fonction halley(n) qui calcule la valeur de $p_n/q_n$ à l'ordre n.
Question 7 : Déterminer le plus petit entier $n$ tel que $|\frac{p_n}{q_n} - \sqrt{2}| < 10^{-1000}$.
La vitesse de convergence d'une méthode mesure le nombre de chiffres décimaux exacts apportés par chaque nouvelle itération de la méthode. On dit que la vitesse est linéaire si ce nombre de chiffres est linéaire en $n$, qu'elle est quadratique s'il est une fonction quadratique en $n$, etc.
Question 8 (cette question est "ouverte") : Estimer la vitesse de convergence des trois méthodes ci-dessus. On pourra utiliser un outil graphique pour illustrer sa réponse, et on l'argumentera (par des commentaires, un bloc "Markdown", ou un fichier .txt joint par exemple).