UM LIMITE DE VELOCIDADE DE 1974 PARA RESOLVER EQUAÇÕES, FINALMENTE DEMONSTRADO

Para encontrar onde uma função f cruza o zero, um computador muitas vezes executa uma iteração: parte de um palpite x, faz algumas perguntas à função, calcula um palpite melhor e repete. As perguntas são avaliações: o valor de f em algum ponto, ou de sua inclinação (a derivada), ou de uma derivada de ordem superior.

Algarismos que dobram

A velocidade de um método desses é medida por sua ordem. Se o erro atual é ε, uma iteração de ordem p deixa um erro de aproximadamente ε elevado a p. Ordem 2 significa que, perto da resposta, o número de algarismos corretos dobra a cada passo; ordem 4, que ele quadruplica.

O método de Newton gasta duas avaliações por passo — f(x) e sua inclinação f′(x) — e passa para x − f(x)/f′(x). Ele tem ordem 2. Fazer mais perguntas por passo pode comprar mais velocidade. A questão é quanto.

Uma conjectura de 1974

Em 1974, H. T. Kung e J. F. Traub propuseram uma resposta, como “Conjectura 8.1” de um artigo no Journal of the ACM: uma iteração sem memória que usa n avaliações por passo tem ordem no máximo 2ⁿ⁻¹. “Sem memória” significa que o método não guarda nada dos passos anteriores, exceto seu palpite atual.

O limite não podia ser baixado: Kung e Traub tinham construído métodos “multiponto” que alcançam 2ⁿ⁻¹ para todo n ≥ 2 — ordem 4 com três avaliações, 8 com quatro, 16 com cinco. O que faltava era a outra metade: uma prova de que nenhum método pode fazer melhor. Resultados parciais vieram com a conjectura e depois dela. O limite foi demonstrado para métodos baseados em interpolação, para métodos racionais com duas avaliações e sob diversas condições adicionais; para métodos que usam só valores da função, foi estabelecido um limite mais fraco, 2ⁿ. O caso geral continuava em aberto.

Enganar o algoritmo

Matthew Colbrook, do Departamento de Matemática Aplicada e Física Teórica da Universidade de Cambridge, agora o demonstra por completo. O modelo é deliberadamente generoso com o algoritmo. Ele pode escolher onde avaliar, e quais derivadas tomar, à medida que avança. Pode processar as respostas de qualquer maneira determinística que quiser, sem que se exija nenhuma suavidade de suas regras.

A prova volta o próprio determinismo do algoritmo contra ele. Construa duas funções que dão exatamente as mesmas respostas a todas as suas perguntas, mas têm zeros diferentes. O algoritmo tem de devolver o mesmo palpite para as duas, e assim, em uma delas, erra por pelo menos metade da distância entre os dois zeros.

Para encontrar esses pares, Colbrook empurra levemente uma função de referência com um pequeno polinômio de grau no máximo n, que tem n + 1 coeficientes ajustáveis. Cada avaliação fixa no máximo uma combinação deles, de modo que, após n perguntas, alguns empurrões continuam invisíveis para o algoritmo. Essa contagem sozinha não basta: um empurrão invisível poderia mal deslocar o zero.

A ferramenta-chave é o wronskiano — um determinante construído a partir de uma família de polinômios e de suas derivadas. Um novo lema diz que, se um polinômio da família tem muitos zeros concentrados num pequeno disco, o wronskiano da família tem de se anular nas proximidades. Respondendo sempre ao algoritmo com uma função cujo zero fica longe desses poucos pontos, a prova mantém o zero livre para se mover.

A contabilidade produz o expoente. Partindo de uma distância ε do zero, os zeros possíveis continuam espalhados por uma faixa de pelo menos uma constante vezes uma potência de ε. Nas palavras de Colbrook, “o expoente continua igual a um após a primeira observação e depois dobra, dando 2ⁿ⁻¹ após n observações”.

Uma função para todas as escalas

Restava uma dificuldade. A definição de ordem permite que a constante à frente dependa da função, de modo que uma função ruim diferente em cada escala não prova nada. Colbrook constrói por isso uma única função, acrescentando correções uma após a outra, cada uma se anulando em todos os pontos que o algoritmo já consultou, para que todas as respostas passadas continuem exatamente as mesmas.

O limite é uma função inteira — suave em toda parte, mesmo sobre os números complexos — cuja inclinação fica entre 3/4 e 5/4 na reta real: uma curva sempre ascendente com um único zero bem-comportado. Para qualquer p acima de 2ⁿ⁻¹, o método não consegue atingir a ordem p nela. A ordem ótima sem memória é, portanto, exatamente 2ⁿ⁻¹ para n ≥ 2. O artigo demonstra o mesmo limite quando as avaliações são números complexos.

O preço de perguntar tudo de uma vez

Um enunciado mais preciso cobre avaliações feitas em grupos, em que cada pergunta de um grupo é escolhida antes que chegue qualquer uma de suas respostas — a situação dos métodos paralelos. Com grupos de tamanhos ℓ₁, …, ℓₖ, a ordem é no máximo ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Fazer as n perguntas de uma vez limita a ordem a n; fazê-las uma de cada vez permite 2ⁿ⁻¹. Com cinco avaliações, são 5 contra 16.

Verificado por máquina

Os resultados são verificados formalmente em Lean, um assistente de provas que confere cada passo lógico. O código é público e está registrado no registro Palomar. Colbrook declara que a formalização em Lean foi feita com a ajuda do ChatGPT 6 e depois verificada com o Lean 4 Comparator em relação aos teoremas do artigo, e que cada argumento foi revisado por Colbrook, que assume total responsabilidade pelo conteúdo.

O limite diz respeito a métodos que esquecem. Métodos autorizados a reutilizar seus passos anteriores obedecem a outros limites, que este artigo deixa de lado.