DEMOSTRADO POR FIN UN LÍMITE DE VELOCIDAD DE 1974 PARA RESOLVER ECUACIONES

Para encontrar dónde cruza el cero una función f, un ordenador ejecuta a menudo una iteración: parte de una conjetura x, hace unas cuantas preguntas a la función, calcula una conjetura mejor y repite. Las preguntas son evaluaciones: el valor de f en algún punto, o el de su pendiente (la derivada), o el de una derivada de orden superior.

Cifras que se duplican

La velocidad de un método así se mide por su orden. Si el error actual es ε, una iteración de orden p deja un error de aproximadamente ε elevado a p. Orden 2 significa que, cerca de la respuesta, el número de cifras correctas se duplica en cada paso; orden 4, que se cuadruplica.

El método de Newton gasta dos evaluaciones por paso, f(x) y su pendiente f′(x), y pasa a x − f(x)/f′(x). Tiene orden 2. Hacer más preguntas por paso puede comprar más velocidad. La cuestión es cuánta.

Una conjetura de 1974

En 1974, H. T. Kung y J. F. Traub propusieron una respuesta, como «Conjetura 8.1» de un artículo en el Journal of the ACM: una iteración sin memoria que usa n evaluaciones por paso tiene como máximo orden 2ⁿ⁻¹. «Sin memoria» significa que el método no conserva nada de los pasos anteriores salvo su conjetura actual.

La cota no podía rebajarse: los propios Kung y Traub habían construido métodos «multipunto» que alcanzaban 2ⁿ⁻¹ para todo n ≥ 2: orden 4 con tres evaluaciones, 8 con cuatro, 16 con cinco. Faltaba la otra mitad: una demostración de que ningún método puede hacerlo mejor. Hubo resultados parciales, junto con la conjetura y después de ella. La cota se demostró para los métodos basados en interpolación, para los métodos racionales con dos evaluaciones y bajo diversas condiciones adicionales; para los métodos que solo usan valores de la función se estableció una cota más débil, 2ⁿ. El caso general seguía abierto.

Engañar al algoritmo

Matthew Colbrook, del Departamento de Matemáticas Aplicadas y Física Teórica de la Universidad de Cambridge, lo demuestra ahora por completo. El modelo es deliberadamente generoso con el algoritmo. Este puede elegir dónde evaluar, y qué derivadas tomar, sobre la marcha. Puede procesar las respuestas de cualquier forma determinista que quiera, sin que se exija ninguna regularidad a sus reglas.

La demostración vuelve contra el algoritmo su propio determinismo. Se construyen dos funciones que dan exactamente las mismas respuestas a todas sus preguntas pero tienen ceros distintos. El algoritmo debe devolver la misma conjetura para ambas, así que en una de ellas falla por al menos la mitad de la distancia entre los dos ceros.

Para encontrar esas parejas, Colbrook perturba una función de referencia con un pequeño polinomio de grado como máximo n, que tiene n + 1 coeficientes ajustables. Cada evaluación fija como mucho una combinación de ellos, así que tras n preguntas algunas perturbaciones siguen siendo invisibles para el algoritmo. Ese recuento no basta por sí solo: una perturbación invisible podría apenas desplazar el cero.

La herramienta clave es el wronskiano, un determinante construido a partir de una familia de polinomios y de sus derivadas. Un nuevo lema dice que, si un polinomio de la familia tiene muchos ceros apiñados en un disco pequeño, el wronskiano de la familia debe anularse cerca. Respondiendo siempre al algoritmo con una función cuyo cero se mantiene alejado de esos pocos puntos, la demostración deja el cero libre para moverse.

La contabilidad produce el exponente. Partiendo de una distancia ε al cero, los ceros posibles siguen repartidos en un intervalo de al menos una constante por una potencia de ε. En palabras de Colbrook, «el exponente sigue siendo uno tras la primera observación y luego se duplica, lo que da 2ⁿ⁻¹ tras n observaciones».

Una sola función para todas las escalas

Quedaba una dificultad. La definición de orden permite que la constante de delante dependa de la función, así que una función mala distinta en cada escala no demuestra nada. Por eso Colbrook construye una única función, añadiendo correcciones una tras otra, cada una nula en todos los puntos que el algoritmo ya ha consultado, de modo que todas las respuestas pasadas siguen siendo exactamente las mismas.

El límite es una función entera, regular en todas partes, incluso en los números complejos, cuya pendiente se mantiene entre 3/4 y 5/4 en la recta real: una curva que sube de forma constante con un único cero bien comportado. Para cualquier p mayor que 2ⁿ⁻¹, el método no alcanza el orden p con ella. El orden óptimo sin memoria es, por tanto, exactamente 2ⁿ⁻¹ para n ≥ 2. El artículo demuestra la misma cota cuando las evaluaciones son números complejos.

El precio de preguntarlo todo a la vez

Un enunciado más preciso abarca las evaluaciones hechas en grupos, en los que cada pregunta de un grupo se elige antes de que llegue ninguna de sus respuestas: la situación de los métodos paralelos. Con grupos de tamaños ℓ₁, …, ℓₖ, el orden es como máximo ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Hacer las n preguntas a la vez limita el orden a n; hacerlas de una en una permite 2ⁿ⁻¹. Con cinco evaluaciones, son 5 frente a 16.

Verificado por una máquina

Los resultados están verificados formalmente en Lean, un asistente de demostración que comprueba cada paso lógico. El código es público y está registrado en el registro Palomar. Colbrook indica que la formalización en Lean se realizó con la ayuda de ChatGPT 6, que después se comprobó con Lean 4 Comparator frente a los teoremas del artículo, y que revisó personalmente cada argumento y asume toda la responsabilidad del contenido.

El límite se refiere a los métodos que olvidan. Los métodos a los que se permite reutilizar sus pasos anteriores obedecen a otras cotas, que este artículo deja de lado.