🔢Algorithmes numériques

Beaucoup de problèmes reviennent à chercher un x tel que f(x) = 0. Souvent on ne sait pas le calculer exactement : on va donc en chercher une valeur approchée.

Idée clé : si f est continue et que f(a) et f(b) sont de signes contraires, alors il existe une solution entre a et b (théorème des valeurs intermédiaires). On dit que [a, b] est un encadrement de la solution.

def f(x):
    return x * x - 2     # f(x) = 0  <=>  x = racine de 2

Pour savoir si deux nombres u et v sont de signes contraires, on teste le signe de leur produit : u * v < 0 signifie « signes opposés ». C'est le test au cœur de la dichotomie.

Avec f(x) = x² - 2 : f(1) = -1 < 0 et f(2) = 2 > 0. Il y a donc une solution dans [1, 2] : c'est √2 ≈ 1,414.

« Approcher » ne veut pas dire « trouver exactement » : on se fixe une précision (par exemple 0.001) et on s'arrête quand l'encadrement est plus court que cette précision.

Le balayage parcourt l'intervalle [a, b] par petits pas réguliers et s'arrête dès qu'il a dépassé la solution. Pour f croissante qui passe du négatif au positif, on avance tant que f(x) < 0 :

def balayage(a, b, pas):
    x = a
    while x < b and x * x - 2 < 0:   # ici f(x) = x*x - 2
        x = x + pas
    return x

À la sortie, x est la première valeur balayée pour laquelle f(x) ≥ 0 : la solution est juste avant, dans [x - pas, x].

Pour balayer :

1. On part de x = a.
2. Tant que f(x) n'a pas changé de signe, on avance d'un pas.
3. Plus le pas est petit, plus l'approximation est précise, mais plus il faut d'étapes.

Sur f(x) = x² - 2 avec a = 1 et pas = 0.1 : on passe 1, 1.1, … ; f devient positive à x = 1.5 environ. La solution √2 ≈ 1,414 est bien dans le dernier intervalle balayé.

Le while doit toujours finir : on s'assure d'avancer (x = x + pas avec pas > 0) et de borner par x < b pour éviter une boucle infinie.

La dichotomie est beaucoup plus rapide que le balayage. On part d'un encadrement [a, b] où f(a) et f(b) sont de signes contraires, puis on coupe l'intervalle en deux à chaque étape :

def dichotomie(a, b, n):
    for _ in range(n):
        m = (a + b) / 2
        if (a * a - 2) * (m * m - 2) <= 0:  # f(a) et f(m) signes opposés
            b = m      # la solution est dans [a, m]
        else:
            a = m      # la solution est dans [m, b]
    return (a + b) / 2

On calcule le milieu m, on regarde dans quelle moitié se trouve la solution (celle où les signes sont opposés) et on garde cette moitié-là.

⭐ Pour les curieux — pourquoi ça marche ? Le milieu $m = \frac{a+b}{2}$ coupe l'intervalle en deux morceaux rigoureusement égaux : $m - a = b - m = \frac{b-a}{2}$. À chaque étape on jette une moitié et on garde l'autre, donc la longueur est multipliée par exactement $\frac{1}{2}$. En répétant $n$ fois, on multiplie $n$ fois par $\frac{1}{2}$ : l'amplitude passe de $b-a$ à $\frac{b-a}{2^n}$. C'est une division qui s'emballe : 10 plis suffisent à diviser par $1024$, là où le balayage avancerait encore pas à pas.

À chaque tour, la longueur de l'encadrement est divisée par 2. Après n étapes, on part de b - a et on obtient une amplitude de (b - a) / 2**n. C'est pour cela que la dichotomie converge très vite : 10 étapes divisent déjà l'écart par 1024.

Cherchons √2 dans [1, 2]. Milieu m = 1.5 : f(1.5) = 0.25 > 0, même signe que f(2), donc on garde [1, 1.5]. Milieu 1.25 : f(1.25) = -0.4375 < 0, on garde [1.25, 1.5]… et on se rapproche de 1,414.

Pour choisir la bonne moitié, on compare les signes via le produit f(a) * f(m) : s'il est négatif (ou nul), la racine est entre a et m ; sinon entre m et b.

La méthode de Héron approche la racine carrée d'un nombre a > 0. On part d'une estimation u (par exemple u = a) et on l'améliore avec la formule :

$u \leftarrow \frac{1}{2}\Big(u + \frac{a}{u}\Big)$

def heron(a, n):
    u = a
    for _ in range(n):
        u = (u + a / u) / 2
    return u

Chaque itération double environ le nombre de décimales exactes : très peu d'étapes suffisent.

⭐ Pour les curieux — pourquoi ça marche ? L'idée cachée, c'est que $u$ et $\frac{a}{u}$ encadrent toujours $\sqrt{a}$ : leur produit vaut $u \times \frac{a}{u} = a = \sqrt{a}\times\sqrt{a}$, donc si l'un dépasse $\sqrt{a}$, l'autre passe forcément en dessous. On remplace alors $u$ par leur moyenne $\frac{1}{2}\big(u+\frac{a}{u}\big)$. Pourquoi cela se rapproche de $\sqrt{a}$ ? Parce que pour deux nombres positifs, la moyenne est toujours au moins égale à la racine de leur produit : $(\sqrt{u}-\sqrt{a/u})^2 \ge 0$ donne en développant $\frac{1}{2}\big(u+\frac{a}{u}\big) \ge \sqrt{u\times\frac{a}{u}} = \sqrt{a}$. Le nouveau terme reste donc toujours $\ge \sqrt{a}$, mais collé juste au-dessus : on descend en douceur vers $\sqrt{a}$ sans jamais le franchir. Avec $a = 2$, $u = 2$ est trop grand et $\frac{2}{2} = 1$ trop petit ; leur moyenne $1{,}5$ vise déjà bien mieux, et l'écart se réduit très vite ensuite.

Pourquoi ça marche : si u est trop grand par rapport à √a, alors a / u est trop petit, et leur moyenne (u + a/u)/2 retombe tout près de √a. On remplace donc u par cette moyenne, encore et encore.

Pour √2 en partant de u = 2 :

• u = (2 + 2/2)/2 = 1.5
• u = (1.5 + 2/1.5)/2 ≈ 1.41666…
• u ≈ 1.41421568… (déjà 5 décimales exactes !)

On divise par u, donc il faut u ≠ 0 : c'est garanti tant que a > 0 et qu'on part de u = a > 0.

Trois façons d'approcher une racine, de la plus lente à la plus rapide :

Le balayage est simple à comprendre, mais pour une grande précision la dichotomie et surtout Héron demandent beaucoup moins d'étapes.

Pour atteindre une précision e :

• balayage : il faut un pas ≤ e, donc de l'ordre de (b-a)/e étapes ;
• dichotomie : il faut n tel que (b-a)/2**n ≤ e, soit très peu d'étapes.

Pour une amplitude de départ 1 et une précision 0.001, le balayage demande environ 1000 pas, la dichotomie seulement 10 étapes (car 2**10 = 1024 > 1000).

Retiens l'ordre de grandeur : balayage = lent, dichotomie = rapide, Héron = très rapide pour les racines carrées.