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

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].

2. Idée : un écart de $10^{-4}$ est énorme quand la racine vaut elle-même $10^{-4}$.

Erreur relative de l'approximation absolue : $\dfrac{1{,}078\times10^{-4} - 1{,}000\times10^{-4}}{1{,}000\times10^{-4}} \approx \boxed{7{,}8\,\%}$, alors que le critère relatif donne une valeur exacte à $10^{-4}$ près relativement (moins de $0{,}01\,\%$).

Pourquoi trop tôt : avec $U_0 = 10^{-8}$, $U_1 \approx 0{,}5$ puis la suite est à peu près divisée par deux à chaque itération tant que $U_n \gg \sqrt a$ ($a/U_n$ étant négligeable). L'écart $|U_n - U_{n-1}| \approx U_n/2$ passe sous $10^{-4}$ dès que $U_n$ lui-même approche $2\times10^{-4}$, c'est-à-dire alors que $U_n$ est encore loin de $\sqrt a$ en valeur relative : le test absolu confond « les termes bougent peu » et « la racine est atteinte ». Le critère relatif compare l'écart à la taille du terme : il exige la même précision relative pour $\sqrt{10^{-8}}$, $\sqrt 2$ ou $\sqrt{10^{6}}$, donc il garantit un nombre de chiffres significatifs corrects indépendant de l'ordre de grandeur. C'est lui qu'il faut choisir quand $a$ n'est pas connu d'avance.

0) DEF FN RacineU (a, eps : réel) : réel
1) Si a = 0 alors
      r ← 0
   Sinon
      u ← a
      Répéter
         v ← (u + a / u) / 2
         ecart ← abs(v - u) / u
         u ← v
      Jusqu'à ecart ≤ eps
      r ← u
   FinSi
2) RacineU ← r
3) Fin RacineU

def racine_u(a, eps):
    if a == 0:
        return 0.0, 0
    u = a
    n = 0
    while True:
        n += 1
        v = (u + a / u) / 2
        if abs(v - u) / u <= eps:
            return v, n
        u = v

1. Idée : les deux méthodes partagent les mêmes évaluations de $f$ ; seule la façon de les pondérer change.

$h = \dfrac{2-1}{4} = 0{,}25$ et $f(1) = 1$, $f(1{,}25) = 0{,}8$, $f(1{,}5) = 0{,}666666667$, $f(1{,}75) = 0{,}571428571$, $f(2) = 0{,}5$.

Rectangles à gauche : la somme des quatre premières valeurs vaut $3{,}038095238$, donc $R_4 = 0{,}25 \times 3{,}038095238 = \boxed{0{,}759523810}$ ; erreur $R_4 - \ln 2 = +6{,}64\times10^{-2}$.

Trapèzes : $\dfrac{f(1)+f(2)}{2} = 0{,}75$ auquel on ajoute $0{,}8 + 0{,}666666667 + 0{,}571428571$, soit $2{,}788095238$, donc $T_4 = 0{,}25 \times 2{,}788095238 = \boxed{0{,}697023810}$ ; erreur $+3{,}88\times10^{-3}$.

Les mêmes points d'évaluation (le trapèze ajoute seulement $f(2)$) donnent une erreur $17$ fois plus petite : le trapèze remplace la marche d'escalier par la corde, qui épouse la courbe.

2. Idée : l'ordre d'une méthode se lit sur le facteur de division de l'erreur quand on divise le pas par deux.

Prévision : l'erreur des rectangles est proportionnelle à $h$ (ordre 1), celle des trapèzes à $h^2$ (ordre 2) ; diviser $h$ par $2$ doit donc diviser la première par $2$ et la seconde par $4$.

Vérification : erreur de $R_8 = 0{,}72537185 - \ln 2 = 3{,}22\times10^{-2}$, et $\dfrac{6{,}64\times10^{-2}}{3{,}22\times10^{-2}} = 2{,}06$. Erreur de $T_8 = 0{,}69412185 - \ln 2 = 9{,}75\times10^{-4}$, et $\dfrac{3{,}88\times10^{-3}}{9{,}75\times10^{-4}} = 3{,}98$.

Les facteurs $\boxed{2}$ et $\boxed{4}$ sont bien ceux annoncés, et ils se stabilisent quand $n$ grandit (de $n = 32$ à $n = 64$ : $2{,}008$ et $4{,}000$).

3. Idée : « gagner une décimale » se traduit en nombre de doublements, donc en nombre d'évaluations — c'est là que se décide le choix.

Rectangles : chaque doublement divise l'erreur par $2$, il faut $2^k \geq 10$, soit $k = 4$ doublements, donc $n = 4 \times 2^4 = \boxed{64}$ sous-intervalles. Trapèzes : chaque doublement divise par $4$, il faut $4^k \geq 10$, soit $k = 2$, donc $n = 4 \times 2^2 = \boxed{16}$.

Vérification numérique : erreur de $R_{64} = 3{,}92\times10^{-3}$, inférieure au dixième de l'erreur de $R_4$, soit $6{,}64\times10^{-3}$, alors que $R_{32}$ ($7{,}87\times10^{-3}$) n'y suffit pas ; erreur de $T_{16} = 2{,}44\times10^{-4}$, inférieure au dixième de celle de $T_4$, soit $3{,}88\times10^{-4}$, alors que $T_8$ ($9{,}75\times10^{-4}$) n'y suffit pas.

$64$ évaluations contre $16$ pour le même gain : dès que $f$ coûte cher (mesure, simulation, appel réseau), on prend les trapèzes. L'unique cas où les rectangles se défendent est celui où $f$ n'est connue qu'aux extrémités gauches des sous-intervalles.

0) DEF FN Integrale (a, b, eps : réel) : réel
1) n ← 1
   S ← FN Trapeze (a, b, n)
   Répéter
      Sp ← S
      n ← n * 2
      S ← FN Trapeze (a, b, n)
   Jusqu'à abs(S - Sp) ≤ eps
2) Integrale ← S
3) Fin Integrale

1. Idée : dans une série alternée, chaque nouveau terme fait passer la somme de l'autre côté de la limite.

$A_1 = 1$ ; $A_2 = 1 - 0{,}5 = 0{,}5$ ; $A_3 = 0{,}5 + \dfrac13 = 0{,}833333333$ ; $A_4 = 0{,}833333333 - 0{,}25 = 0{,}583333333$.

On lit $A_2 < A_4 < \ln 2 < A_3 < A_1$ : les sommes de rang pair croissent, celles de rang impair décroissent, et $\ln 2$ est pris entre deux sommes consécutives. D'où la majoration : $\boxed{|\ln 2 - A_n| \leq |u_{n+1}| = \dfrac{1}{n+1}}$ — l'erreur est majorée par le premier terme négligé.

2. Idée : ici le critère d'arrêt est adossé à un théorème, donc il prouve quelque chose — mais il coûte cher.

Pour une erreur $\leq 10^{-2}$ : $\dfrac{1}{n+1} \leq 10^{-2}$ donne $n \geq 99$, soit $\boxed{99 \text{ termes}}$ ($A_{99} = 0{,}698172$, erreur réelle $5{,}03\times10^{-3}$). Pour $10^{-4}$ : $n \geq 9999$, soit $\boxed{9999 \text{ termes}}$ ($A_{9999} = 0{,}693197$, erreur réelle $5{,}00\times10^{-5}$). La boucle « tant que $|u_k| > eps$ » s'arrête en fait à $k = 100$ (resp. $10^4$) : un terme de plus que le minimum, ce qui ne nuit pas à la garantie.

Oui, c'est une preuve — non parce que le terme est petit, mais parce qu'un théorème majore le reste par ce terme. Le prix est une convergence très lente : il faut de l'ordre de $10^{p}$ termes pour une erreur $\leq 10^{-p}$, là où la suite de Héron double le nombre de décimales exactes à chaque itération — pour $\sqrt2$ à $10^{-4}$ près elle s'arrête en 4 itérations, contre $10^4$ termes ici.

3. Idée : un terme qui tend vers $0$ ne dit rien sur la somme.

D'aucune valeur : $H_n$ ne converge pas — $H_{100} = 5{,}187378$, $H_{1000} = 7{,}485471$, $H_{10^6} = 14{,}392727$ — la somme continue de croître sans borne (elle se comporte comme $\ln n + \gamma$ avec $\gamma \approx 0{,}5772$ ; pour $n = 10^6$, $\ln(10^6) + \gamma = 14{,}392727$, ce que le calcul retrouve).

La boucle s'arrête uniquement parce que le terme $\dfrac1k$ est devenu petit, ce qui arrive aussi pour une série divergente. La valeur rendue ne dépend que de $eps$ : avec $eps = 10^{-4}$ le même code s'arrête à $k = 10^4$ et affiche $9{,}787606$. Deux « approximations » d'une même quantité qui diffèrent de $4{,}6$ : le critère n'approche rien du tout. Remarquons aussi que $|A_k - A_{k-1}| = |u_k|$ exactement : le test « deux sommes successives diffèrent peu » est le même test, il hérite donc de la même faiblesse.

0) DEF FN SommeAlt (eps : réel) : réel
1) s ← 0
   k ← 0
   signe ← 1
   Répéter
      k ← k + 1
      u ← signe / k
      s ← s + u
      signe ← -signe
   Jusqu'à (1 / k) ≤ eps
2) SommeAlt ← s
3) Fin SommeAlt