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 ( $\sqrt{a}$ , $\pi$ , $e$ …) par une suite convergente définie par récurrence ou par sommation partielle d'une série. Pour $\sqrt{a}$ , la méthode de Héron donne $x_{n+1} = \dfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right)$ avec $x_0 > 0$ . Pour $\pi$ , la série de Leibniz donne $\pi = 4\sum_{k=0}^{\infty} \dfrac{(-1)^k}{2k+1}$ . Dans les deux cas, on écrit une boucle TantQue sur un critère $|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 $\sqrt{a}$ par la méthode de Héron » ; « Vérifier que si la suite converge, elle converge vers $\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 $\sqrt{a}$ .**

On pose $x_0 = a$ et $x_{n+1} = \dfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right)$ . Vérifier que si la suite converge vers $\ell$ , alors $\ell = \sqrt{a}$ .
Écrire un algorithme qui calcule $\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 $a$ ?
Donner la trace pour $a = 5$ , $x_0 = 5$ , $\varepsilon = 10^{-3}$ (3 premières itérations).

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

On admet que $\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 $\left|\dfrac{(-1)^k}{2k+1}\right| < \dfrac{\varepsilon}{4}$ .
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 $x_n\to\ell$ et $x_{n+1}=\dfrac12(x_n+a/x_n)$ , alors $\ell=\dfrac12(\ell+a/\ell)$ , soit $2\ell^2=\ell^2+a$ , d'où $\ell^2=a$ et $\ell=\sqrt{a}$ car $\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=5$ , $x_0=5$ , $\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 $\sqrt{5}\approx 2{,}236$ . Contrainte : a dans ]0..+∞[ ; ne pas utiliser $|x_n-\sqrt{a}|$ comme critère (racine inconnue).

**B. Approximation de $\pi$ par Leibniz.** $\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
terme ← signe / (2k + 1)
s ← s + terme
signe ← -signe
k ← k + 1
FinTantQue
Écrire(4s)
Fin
```

TDOL pour Leibniz : `s`, `terme`, `signe` réels ; `k` entier. Type/Nature : accumulateur et terme courant. On retourne $4s$ comme approximation de $\pi$ .

Équivalent Python (extrait).
```python
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) = 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 $x_{n+1}=g(x_n)$ si $|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, $x_0 = a$ est un choix simple et sûr pour $a > 0$ .
Toujours vérifier $a > 0$ et $x_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$ à chaque tour.
Critère d'arrêt sur une série alternante : s'arrêter quand $|\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 > 0$ avant d'appliquer Héron — division par zéro si $a=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 $|x_{n+1}-x_n|$ (Héron) avec $|x_n - \sqrt{a}|$ (non calculable sans connaître $\sqrt{a}$ ).

Variantes rencontrées : Calcul de $e = \sum_{k=0}^{\infty} 1/k!$ par sommation partielle. Calcul de $\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 $n$ -ième. Parfois l'énoncé fixe le nombre d'itérations au lieu de $\varepsilon$ .