Feuille d’exercices 6 – avancé

Contenu

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 :

\[ p_{n+1} = p_n + 2q_n \quad \text{ et } \quad q_{n+1} = p_n + q_n, \quad \forall n \ge 0\,. \]

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.

def theon(n):
    p = 1
    q = 1
    for i in range(n):
        nouveau_p = p + 2*q
        nouveau_q = p + q
        p = nouveau_p
        q = nouveau_q
    return p/q

On peut montrer que la suite \((t_n)_{n \in \mathbb{N}}\) converge vers \(\sqrt{2}\) ; plus précisément on a

\[ |t_{n+1} - \sqrt{2}| \le \frac{1}{2} |t_n - \sqrt{2}| \]

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.

s = RealField(2000)(sqrt(2))
t1000 = theon(1000)
print(t1000)
print(abs(s-t1000) < 2**(-1000))

72016336943533875056131468444247239328723197628440751797201898063588088312700201943482948477109536203740206649612702729920170001354454107173480483962605519493117789821758457767858986227019805650639002566946496865364666543562826303377877700877266135276209125278037204443042487153089226849544681245300260167141025277156482737568934079466850318276966893735585103845471745828701580706481/50923240208988086528630631809520139740233813238121746983184087440294876496910992032199150140268994975929379287364741267843829764622711478409393315655847391426474051205489599791876548045932140034723376284514492359420266988954982032735984900118578499266240851000814909302953919098957411314364525062171896557231165855421007859932974745573266780329830972204644845348897749854049994681209
True

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.

def approx_theon(epsilon):
    p, q = 1, 1                # une manière d'assigner (p, q) à (1, 1) en une ligne
    t = p/q
    p, q = p + 2*q, p + q      # une manière d'assigner (p, q) à (p + 2*q, p + q) en une ligne
    steps = 1
    while abs(p/q - t) > epsilon/2:
        t = p/q
        p, q = p + 2*q, p + q
        steps += 1
    print("steps =", steps)
    return p/q
    
t = approx_theon(2**(-1000))
print(abs(s-t) < 2**(-1000))

steps = 395
True

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 :

\[ u_{n+1} = \frac{u_n}{2} + \frac{1}{u_n}, \quad \forall n \ge 0 \]

Question 4 : Écrire une fonction heron(n) qui calcule la valeur de \(u_n\) à l’ordre n.

def heron(n):
    u = 1
    for i in range(n+1):
        u = u/2 + 1/u
    return u

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

\[ |u_{n+1} - \sqrt{2}| \le \frac{1}{2\sqrt{2}} |u_n - \sqrt{2}|^2\,. \]

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

h11 = heron(11)
print(h11)
print(abs(s-h11) < 2**(-1000))

35332726218913082002358766567827133403671835402604373950214227741215442484749150955273090178912608481198897853368677449335995881087244538678290206830418162774359733435287323797237328954776430706234113433451845011017420071003585630000741417839336284541684996470487244538747886851321045013449097020971979829080007863459398205102274621539252406059437113694061276533416838442752036477377285665580031045075305667660780081786425072132321243484569812363079897761850586673077795635795883465127642978549060248943470341266945351444290281205344606113449121955343732035824675647295545778804839861084648227428027205738691255356908295557230413188833721567060585767808732827617204869412227198237283429379813249866199201416615876892112411524426811419866249990696965745171717817422622562682438363092664485642832947927443151601527359189163417709253561016343488370329029585831327776394329216180144214930909237283637492608470079057271872248952501520874288386823231621192012874782227366578088738868911631337861377623018019037632439341813994901701122235924802807033643138348715789752591317659444556916319088480894501003196095706425280809090500181540773251421775695294520400781732432876502534542845385961208207822267335357830445556698863375695074697445589948526104879367950290305961624127368550768977250835228412091675544074876078513692883156476870744638792993260730998051752445796633655179188384438251649122556708863266126720906055336405070283541885888759326087142666395773249829681135123306671975516588372947658685690152085540674258629344850569601363203602574753855251595448225066391699457/24984010307201163339947983356301141616506447664487440183998810625058752168423324876345697485648790341609412002644655629412905132278379217868484556663287775731050845260730078203242599232472745227920679113063794049752437460981417866332131328395755341349753062559392972068081111918344156477612649348595211491067455489237457910155651004107009048180626919290946081541440148801661958564193598020244065505190786402719245384074252704561095281880456896817874403336969582795243258680340898219825513614657448394985422467221011934983262955360496189619472621400284115715288480382270722104540794780523070446693883270347990895469101178377691926263031421481448827494798554741341670262654080173175016283673279935535934852810962006385757200844486464083629290021915870934966800154480166282275001270982689689154583147508681525494843192315422085012166515924290106489737455158618093568404195679968385318684717834082972614221999122177016269590409818014579764679971236940524480753371978831311605588219064932370351315353772791737116335036856123399572239079392444178222707643932212683788067910953111224799145119835497757908787464889401399155223624057578426686398366195576141848364526279398255637945691268246191955996126558409043995911907057399961628590021716196825459819630668018546857838477083355412835636688350256316068114037351274317433071855241661763541825367319352845206312966830268604961919428245071600234081088836304955895409229527078577447991563333997254415362184904418568880688711037556338564582304559403993718370643949781411157627238782780565038167716008066343635609932346552357957632
True

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.

def approx_heron(epsilon):
    u = 1
    nouveau_u = u/2 + 1/u
    steps = 1
    while abs(nouveau_u - u) > epsilon/2:
        u = nouveau_u
        nouveau_u = u/2 + 1/u
        steps += 1
    print("steps =", steps)
    return u
    
u = approx_heron(2**(-1000))
print(abs(s-u) < 2**(-1000))

steps = 10
True

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 ?

Pour un entier \(n\), on calcule le reste de la division euclidienne de \(n\) par \(10\).

n = 12345
print(n % 10)

Pour un nombre flottant \(x\), on calcule sa partie entière inférieure, puis on revient au cas précédent.

x = 12.345
print( floor(x) % 10 )

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.

def decimale(k, nombre):
    return floor(nombre * 10**k) % 10
    
print(decimale(2, 12.345))
print(decimale(4, pi))

4
5