Masar
Masar
Bac Tunisie
Informatique/AP-D
Entraîner la reconnaissance
AP-DAlgorithmes d’approximation

Approximation d'une valeur par suite convergente (Héron / série de π)

Idée directrice

L'énoncé demande d'approcher une valeur (a\sqrt{a}, π\pi, ee…) par une suite convergente définie par récurrence ou par sommation partielle d'une série. Pour a\sqrt{a}, la méthode de Héron donne xn+1=12(xn+axn)x_{n+1} = \dfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right) avec x0>0x_0 > 0. Pour π\pi, la série de Leibniz donne π=4∑k=0∞(−1)k2k+1\pi = 4\sum_{k=0}^{\infty} \dfrac{(-1)^k}{2k+1}. Dans les deux cas, on écrit une boucle TantQue sur un critère ∣xn+1−xn∣<ε|x_{n+1} - x_n| < \varepsilon ou sur un nombre d'itérations fixé.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Écrire un algorithme qui approche a\sqrt{a} par la méthode de Héron » ; « Vérifier que si la suite converge, elle converge vers a\sqrt{a} » ; « Écrire un algorithme qui approche π\pi à ε\varepsilon près par la série de Leibniz » ; « Donner la trace pour les premières itérations » ; « Quel est le critère d'arrêt de l'algorithme ? »

Sujet principal

Exercice — dans l'esprit des sujets du bac

5 questionsCorrigé masqué

Partie A — Méthode de Héron pour a\sqrt{a}.

  1. On pose x0=ax_0 = a et xn+1=12(xn+axn)x_{n+1} = \dfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right). Vérifier que si la suite converge vers ℓ\ell, alors ℓ=a\ell = \sqrt{a}.
  2. Écrire un algorithme qui calcule a\sqrt{a} à ε\varepsilon près par la méthode de Héron.
    1. Préciser les données et le résultat.
    2. Quelle précaution faut-il prendre sur la valeur de aa ?
  3. Donner la trace pour a=5a = 5, x0=5x_0 = 5, ε=10−3\varepsilon = 10^{-3} (3 premières itérations).

Partie B — Approximation de π\pi par la série de Leibniz.

  1. On admet que π4=1−13+15−17+⋯=∑k=0∞(−1)k2k+1\dfrac{\pi}{4} = 1 - \dfrac{1}{3} + \dfrac{1}{5} - \dfrac{1}{7} + \cdots = \sum_{k=0}^{\infty} \dfrac{(-1)^k}{2k+1}. Écrire un algorithme qui calcule π\pi à ε\varepsilon près en s'arrêtant quand le terme courant ∣(−1)k2k+1∣<ε4\left|\dfrac{(-1)^k}{2k+1}\right| < \dfrac{\varepsilon}{4}.
  2. Comparer la vitesse de convergence de la série de Leibniz et de la méthode de Héron. Laquelle préférer en pratique ?
Voir la correction commentéeAprès avoir posé votre démarche

A.1. Limite de Héron. Si xn→ℓx_n\to\ell et xn+1=12(xn+a/xn)x_{n+1}=\dfrac12(x_n+a/x_n), alors ℓ=12(ℓ+a/ℓ)\ell=\dfrac12(\ell+a/\ell), soit 2ℓ2=ℓ2+a2\ell^2=\ell^2+a, d'où ℓ2=a\ell^2=a et ℓ=a\ell=\sqrt{a} car ℓ>0\ell>0.

A.2. Algorithme. TDOL : x, xnew réels (itérés). Type/Nature : a, eps réels avec a > 0.

DEF PROC Heron(a, eps : réel)
Variables x, xnew : réel
Début
  Si a <= 0 alors
    Écrire("Erreur : a doit être strictement positif")
  Sinon
    x ← a
    xnew ← (x + a/x) / 2
    TantQue ABS(xnew - x) > eps faire
      x ← xnew
      xnew ← (x + a/x) / 2
    FinTantQue
    Écrire(xnew)
  FinSi
Fin

A.3. Trace pour a=5a=5, x0=5x_0=5, ε=10−3\varepsilon=10^{-3} :

  • it.1 : xnew = (5+1)/2 = 3
  • it.2 : xnew = (3+5/3)/2 ≈ 2,3333
  • it.3 : xnew ≈ (2,3333+5/2,3333)/2 ≈ 2,2381

On retourne une approximation de 5≈2,236\sqrt{5}\approx 2{,}236. Contrainte : a dans ]0..+∞[ ; ne pas utiliser ∣xn−a∣|x_n-\sqrt{a}| comme critère (racine inconnue).

B. Approximation de π\pi par Leibniz. π=4∑k=0∞(−1)k2k+1\pi=4\sum_{k=0}^{\infty}\dfrac{(-1)^k}{2k+1}.

DEF PROC Leibniz(eps : réel)
Variables s, terme, signe : réel ; k : entier
Début
  s ← 0 ; signe ← 1 ; k ← 0
  terme ← 1
  TantQue ABS(terme) > eps/4 faire
    s ← s + terme
    signe ← -signe
    k ← k + 1
    terme ← signe / (2*k + 1)
  FinTantQue
  Écrire(4*s)
Fin

TDOL pour Leibniz : s, terme, signe réels ; k entier. Type/Nature : accumulateur et terme courant. On retourne 4s4s comme approximation de π\pi. Le terme est recalculé après avoir été ajouté, de sorte que le test porte sur le prochain terme : on s'arrête dès que celui-ci passe sous ε/4\varepsilon/4 et il n'est pas sommé.
B.2. Comparaison. Pour Leibniz, le terme courant 12k+1\frac{1}{2k+1} majore l'erreur : atteindre ε=10−3\varepsilon=10^{-3} sur π\pi demande k≈2000k\approx2000 termes, 10−610^{-6} en demanderait deux millions — convergence très lente (linéaire). Héron double le nombre de décimales exactes à chaque itération : 5\sqrt5 à 10−310^{-3} en quatre itérations. En pratique on préfère les méthodes de type Newton/Héron ; la série de Leibniz n'a qu'un intérêt pédagogique.

Équivalent Python (extrait).

def heron(a, eps):
    x = a
    xnew = (x + a/x) / 2
    while abs(xnew - x) > eps:
        x = xnew
        xnew = (x + a/x) / 2
    return xnew
print(heron(5.0, 1e-3))

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 01

Drill AP-D.1 — méthode du point fixe

1 questionCorrigé masqué

Pour résoudre f(x)=0reˊeˊcritenx=g(x),donnerlescheˊmaiteˊratifetlaconditiondeconvergencef(x) = 0 réécrit en x=g(x), donner le schéma itératif et la condition de convergence.

Voir la correction commentéeAprès avoir posé votre démarche

Point fixe xn+1=g(xn)x_{n+1}=g(x_n) si ∣g′∣<1|g'|<1. TDOL : x, xnew. Type/Nature : itérés.

DEF PROC PointFixe(x0, eps : réel)
Variables x, xnew : réel
Début
  x ← x0 ; xnew ← g(x)
  TantQue ABS(xnew-x) > eps faire
    x ← xnew ; xnew ← g(x)
  FinTantQue
  Écrire(xnew)
Fin

On retourne l'approx. ; eps dans ]0..1].

Méthode / Automatismes
  • Méthode de Héron : convergence quadratique, x0=ax_0 = a est un choix simple et sûr pour a>0a > 0.
  • Toujours vérifier a>0a > 0 et x0≠0x_0 \neq 0 pour éviter la division par zéro dans la formule de récurrence.
  • Série de Leibniz : signe alternant géré avec une variable signe initialisée à 1 et multipliée par −1-1 à chaque tour.
  • Critère d'arrêt sur une série alternante : s'arrêter quand ∣terme∣<ε/4|\text{terme}| < \varepsilon/4 (pour obtenir π\pi à ε\varepsilon près après multiplication par 4).
  • Comparer les vitesses : quadratique (Héron, Newton) >> linéaire (dichotomie) >> sous-linéaire (Leibniz).
Pièges classiques

Pièges fréquents : (1) Oublier de tester a>0a > 0 avant d'appliquer Héron — division par zéro si a=0a=0. (2) Dans la série de Leibniz, initialiser k ← 1 au lieu de k ← 0 : on saute le premier terme et le résultat est faux. (3) Confondre le critère d'arrêt sur ∣xn+1−xn∣|x_{n+1}-x_n| (Héron) avec ∣xn−a∣|x_n - \sqrt{a}| (non calculable sans connaître a\sqrt{a}).

Variantes rencontrées : Calcul de e=∑k=0∞1/k!e = \sum_{k=0}^{\infty} 1/k! par sommation partielle. Calcul de ln⁡(2)=∑k=1∞(−1)k+1/k\ln(2) = \sum_{k=1}^{\infty} (-1)^{k+1}/k (série harmonique alternée). Suite de Babylone généralisée pour la racine nn-ième. Parfois l'énoncé fixe le nombre d'itérations au lieu de ε\varepsilon.