NUMÉRIQUE CALCUL

Méthode de dichotomie

Soit g une fonction numérique continue et strictement monotone sur un intervalle[a, b], telle que g (a)g (b) < 0. Il existe alors un élément α de[a, b]et un seul tel que g (α) = 0. On peut trouver des valeurs approchées de α par l'algorithme suivant : supposons par exemple g (a) > 0 et g (b) < 0 ; posons a₀ = a, b₀ = b, et :

Dès le xvi^e siècle, cette méthode est employée pour séparer les racines d'une équation algébrique. La convergence n'est pas très rapide ; c'est pourquoi cette méthode n'est pas utilisée lorsqu'on désire obtenir α avec une grande précision.

En revanche, le méthode de dichotomie a eu une importance considérable dans le développement des concepts fondamentaux de l'analyse :

– Lagrange (1736-1813), dans La Théorie des fonctions analytiques (1797), utilise une variante de cette méthode pour démontrer le principe fondamental du calcul différentiel, suivant lequel une fonction admettant une dérivée positive est croissante ; ce principe est à la base de la formule de Taylor.

– Bolzano (1781-1848), dans Une preuve analytique... (1817) et Cauchy (1789-1857), dans son Cours d'analyse à l'École polytechnique (1821), utilisent la dichotomie pour démontrer le théorème des valeurs intermédiaires.

– L'école de Weierstrass (1815-1897) utilise systématiquement la dichotomie pour démontrer les théorèmes fondamentaux sur les fonctions continues (existence d'un maximum, continuité uniforme). Ces résultats reposent sur le théorème suivant, dit de Bolzano-Weierstrass : de toute suite bornée de nombres réels, on peut extraire une suite convergente.

Méthode d'interpolation linéaire (ou « regula falsi »)

Sous les mêmes hypothèses que précédemment, on cherche une valeur approchée β de ω en interpolant g sur l'intervalle[a,b]par une fonction affine ϕ, et en définissant β par la relation ϕ(β) = 0. Cette méthode a été utilisée par Viète (1540-1603) et par Descartes (1596-1650), dans le cas des équations algébriques. La majoration de l'erreur a été effectuée par Lagrange.

Cette méthode est peu employée seule car elle ne conduit pas à un processus itératif qui soit à la fois commode et performant.

Méthode des tangentes (ou de Newton)

L'école d' Alexandrie, et en particulier Archimède, utilise fréquemment des encadrements des racines carrées d'un nombre entier par des nombres rationnels. À cet effet, on utilise l' algorithme d'Euclide de divisions successives. Héron d'Alexandrie part d'une autre idée. Pour approcher √ a, il écrit a sous la forme a = r² + b, où r est le plus grand des entiers p tels que p² ≤ a. Ainsi, √ a = r √1 + (b/r²). Il approche √1 + (b/r²) par 1 + (b/2r²). D'où la valeur approchée suivante :

On itère alors ce processus. Plus précisément, on pose :

Cette rapidité peut être prévue grâce aux encadrements suivants : on prouve d'abord que |u₂ − √2| ≤ 1/400. Par ailleurs, pour tout entier naturel n,

En particulier,[...]