UNE LIMITE DE VITESSE DE 1974 POUR RÉSOUDRE LES ÉQUATIONS, ENFIN DÉMONTRÉE

Pour trouver où une fonction f passe par zéro, un ordinateur lance souvent une itération : partir d’une estimation x, poser quelques questions à la fonction, calculer une meilleure estimation, et recommencer. Les questions sont des évaluations : la valeur de f en un point, ou celle de sa pente (la dérivée), ou d’une dérivée d’ordre plus élevé.

Des chiffres qui doublent

La vitesse d’une telle méthode se mesure par son ordre. Si l’erreur actuelle vaut ε, une itération d’ordre p laisse une erreur d’environ ε puissance p. L’ordre 2 signifie que, près de la réponse, le nombre de chiffres justes double à chaque étape ; l’ordre 4, qu’il quadruple.

La méthode de Newton dépense deux évaluations par étape — f(x) et sa pente f′(x) — et passe à x − f(x)/f′(x). Elle est d’ordre 2. Poser plus de questions par étape peut faire gagner de la vitesse. Reste à savoir combien.

Une conjecture de 1974

En 1974, H. T. Kung et J. F. Traub ont proposé une réponse, la « Conjecture 8.1 » d’un article du Journal of the ACM : une itération sans mémoire qui utilise n évaluations par étape a un ordre d’au plus 2ⁿ⁻¹. « Sans mémoire » signifie que la méthode ne garde rien des étapes précédentes, sauf son estimation actuelle.

La borne ne pouvait pas être abaissée : Kung et Traub avaient déjà construit des méthodes « multipoints » qui atteignent 2ⁿ⁻¹ pour tout n ≥ 2 — ordre 4 avec trois évaluations, 8 avec quatre, 16 avec cinq. Il manquait l’autre moitié : prouver qu’aucune méthode ne fait mieux. Des résultats partiels ont accompagné la conjecture, puis l’ont suivie. La borne a été démontrée pour les méthodes fondées sur l’interpolation, pour les méthodes rationnelles à deux évaluations, et sous diverses conditions supplémentaires ; pour les méthodes qui n’utilisent que les valeurs de la fonction, une borne plus faible, 2ⁿ, a été établie. Le cas général restait ouvert.

Tromper l’algorithme

Matthew Colbrook, du département de mathématiques appliquées et de physique théorique de l’université de Cambridge, le démontre désormais en entier. Le modèle est volontairement généreux envers l’algorithme. Celui-ci peut choisir, au fur et à mesure, où évaluer et quelles dérivées prendre. Il peut traiter les réponses de n’importe quelle façon déterministe, sans aucune régularité exigée de ses règles.

La preuve retourne contre l’algorithme son propre déterminisme. Fabriquez deux fonctions qui donnent exactement les mêmes réponses à toutes ses questions mais ont des zéros différents. L’algorithme doit rendre la même estimation pour les deux : sur l’une d’elles au moins, il se trompe d’au moins la moitié de la distance entre les deux zéros.

Pour trouver de telles paires, Colbrook modifie légèrement une fonction de référence par un petit polynôme de degré au plus n, qui a n + 1 coefficients réglables. Chaque évaluation fixe au plus une combinaison de ces coefficients : après n questions, certaines modifications restent invisibles pour l’algorithme. Ce décompte ne suffit pas : une modification invisible pourrait à peine déplacer le zéro.

L’outil clé est le wronskien — un déterminant construit à partir d’une famille de polynômes et de leurs dérivées. Un nouveau lemme affirme que si un polynôme de la famille a beaucoup de zéros serrés dans un petit disque, le wronskien de la famille s’annule forcément tout près. Un wronskien n’a qu’un nombre limité de zéros. En répondant toujours à l’algorithme avec une fonction dont le zéro reste à l’écart de ceux-ci, la preuve garde au zéro sa liberté de bouger.

La comptabilité donne l’exposant. En partant à une distance ε du zéro, les zéros possibles restent répartis sur un intervalle d’au moins une constante fois une puissance de ε. Selon l’article, « l’exposant reste égal à un après la première observation, puis double, ce qui donne 2ⁿ⁻¹ après n observations ». Comme l’algorithme ne peut pas distinguer ces zéros, son erreur ne peut pas toujours descendre sous une constante fois ε puissance 2ⁿ⁻¹ : pas d’ordre au-delà de 2ⁿ⁻¹.

Une seule fonction pour toutes les échelles

Restait une difficulté. La définition de l’ordre demande seulement que l’erreur reste sous une certaine constante fois ε puissance p, et cette constante peut dépendre de la fonction : une mauvaise fonction différente à chaque échelle ne prouve donc rien. Colbrook construit par conséquent une fonction unique, en ajoutant des corrections l’une après l’autre, chacune s’annulant en tous les points déjà interrogés par l’algorithme, si bien que toutes les réponses passées restent exactement les mêmes.

La limite est une fonction entière — parfaitement régulière partout, même sur les nombres complexes — dont la pente reste entre 3/4 et 5/4 sur la droite réelle : une courbe qui monte régulièrement, avec un seul zéro bien sage. Pour tout p supérieur à 2ⁿ⁻¹, la méthode n’atteint pas l’ordre p sur cette fonction. L’ordre optimal sans mémoire vaut donc exactement 2ⁿ⁻¹ pour n ≥ 2. L’article démontre la même borne quand les évaluations sont des nombres complexes.

Le prix des questions posées d’un coup

Un énoncé plus fin couvre les évaluations faites par groupes, où toutes les questions d’un groupe sont choisies avant qu’aucune de ses réponses n’arrive — la situation des méthodes parallèles. Avec des groupes de tailles ℓ₁, …, ℓₖ, l’ordre vaut au plus ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Poser les n questions d’un coup plafonne l’ordre à n ; les poser une par une permet 2ⁿ⁻¹. Avec cinq évaluations, c’est 5 contre 16.

Vérifié par la machine

Les résultats sont vérifiés formellement dans Lean, un assistant de preuve qui contrôle chaque étape logique. Le code est public et enregistré dans un registre public de preuves formelles (Palomar). L’article indique que la formalisation Lean a été réalisée avec l’aide de ChatGPT 6, puis contrôlée avec le Lean 4 Comparator face aux théorèmes de l’article, et que chaque argument a été relu par la personne qui signe l’article, laquelle en assume l’entière responsabilité.

La limite concerne les méthodes qui oublient. Celles qui peuvent réutiliser leurs étapes précédentes obéissent à d’autres bornes, que cet article laisse de côté. Et la borne vaut pour le pire cas : sur certaines fonctions particulières, une méthode peut encore aller plus vite.