Feuille d’exercices 6 – avancé#
Objectifs
Nombres réels
Notion de précision
Affichage graphique
Avertissement
Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d’exercices « classiques ».
Exercice 5. Approximation rationnelle de \(\sqrt{2}\)#
Une approximation rationnelle d’un nombre réel \(x\) est une suite \((p_n/q_n)\) de nombres rationnels qui tend vers \(x\).
Méthode de Théon de Smyrne#
Théon de Smyrne (I\(^{er}\) et II\(^{ème}\) siècle après JC) a défini deux suites entières \((p_n)_{n \in \mathbb{N}}\) et \((q_n)_{n \in \mathbb{N}}\) qui permettent de calculer une approximation rationnelle \(\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 :
On note enfin \(t_n := \frac{p_n}{q_n}\).
Question 1 : Écrire une fonction theon(n) qui retourne la valeur de \(t_n = p_n/q_n\) à l’ordre n.
# Votre réponse ici
On peut montrer que la suite \((t_n)_{n \in \mathbb{N}}\) converge vers \(\sqrt{2}\) ; plus précisément on a
ce qui nous assure que chaque nouveau terme de la suite \((t_n)\) donne au moins un bit de précision supplémentaire (en effet, on divise l’erreur d’approximation par au moins \(2\) à chaque étape).
Question 2 : Avec Sagemath, calculer la valeur de \(\sqrt{2}\) avec une précision de \(2000\) bits. Puis, vérifier que \(t_{1000}\) est une approximation de \(\sqrt{2}\) à \(\le 2^{-1000}\) près.
# Votre réponse ici
L’équation de convergence ci-dessus nous indique également que \(|t_n - \sqrt{2}| \le 2 |t_{n+1}-t_n|\) pour tout \(n \ge 1\). Ainsi, si on souhaite obtenir une précision d’approximation de \(\epsilon > 0\), il suffit de calculer \(t_n\) jusqu’à ce que \(|t_{n+1}-t_n| \le \epsilon/2\).
Question 3 : Écrire une fonction approx_theon(epsilon) qui prend en entrée un nombre positif epsilon, et qui retourne, avec la méthode ci-dessus, une approximation rationnelle de \(\sqrt{2}\) à \(\epsilon\) près. Avant de retourner l’approximation, on affichera le nombre d’étapes effectuées.
# Votre réponse ici
Méthode de Héron#
La méthode de Héron s’apparente à une méthode générale dite « 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éthode_de_Newton
Dans notre cas, on définit la suite \((u_n)_{n \in \mathbb{N}}\) de premier terme \(u_0 = 1\), et définie par récurrence par :
Question 4 : Écrire une fonction heron(n) qui calcule la valeur de \(u_n\) à l’ordre n.
# Votre réponse ici
Comme précédemment, on peut démontrer que la suite \((u_n)_{n \in \mathbb{N}}\) converge vers \(\sqrt{2}\). Cette fois-ci la convergence est plus rapide : à partir d’un certain rang (qui dépend du choix de \(u_0\)), on a
On parle de convergence quadratique : le nombre de bits exacts double à chaque itération.
Comme on a \(1\) bit de correct à la première itération, il faut donc environ \(\log_2(1000) \simeq 10\) itérations supplémentaires pour obtenir \(1000\) bits corrects.
Question 5 : Vérifier que heron(11) donne une approximation rationnelle à \(2^{-1000}\) près de \(\sqrt{2}\).
# Votre réponse ici
L’équation précédente assure également que, à partir d’un certain rang (petit en pratique), si \(|u_{n+1}-u_n| \le \epsilon\), alors \(|u_{n+1} - \sqrt{2}| \le 2\epsilon\).
Question 6 : Écrire une fonction approx_heron(epsilon) qui prend en entrée un nombre positif epsilon, et qui retourne, avec la méthode ci-dessus, une approximation rationnelle de \(\sqrt{2}\) à \(\epsilon\) près. Avant de retourner l’approximation, on affichera le nombre d’étapes effectuées.
# Votre réponse ici
Exercice 6. Calcul d’une décimale#
Question 1 : Un entier n a été déclaré. Comment obtenir son chiffre (décimal) des unités avec une simple instruction ? et pour un nombre flottant x ?
# Votre réponse ici
Question 2 : En s’inspirant de la question précédente, écrire une fonction decimale(k, nombre) qui prend entrée un entier strictement positif k et un nombre (flottant, symbolique ou rationnel) nombre, et qui retourne la \(k\)-ème décimale de nombre après la virgule. Par exemple, si nombre = 12.345 et k = 2, alors la fonction doit retourner \(4\).
On supposera que nombre a été stocké avec une précision assez importante pour y effectuer des calculs arbitraires.
# Votre réponse ici