Esta é uma tradução automática; o texto original encontra-se em inglês. Ler o original
O método de Newton pode duplicar o seu erro a cada passo, e a resposta estava a 0,01 de distância
Comece a 0,01 da resposta. Vinte passos mais tarde está em −5242,88, e cada passo foi calculado corretamente.
Resolva x³ − x − 2 = 0. Não existe uma fórmula simples que valha a pena memorizar, por isso faça o que qualquer software numérico faz: dê um palpite e deixe que o método de Newton corrija a estimativa.
Comece em 1,5. Três iterações mais tarde tem 1,52138, e a função avaliada aí é 5,89387 × 10⁻⁷ — a menos de um milionésimo de zero. Três passos. Cada passo duplica aproximadamente o número de dígitos corretos, razão pela qual este método está presente na sua calculadora, no seu pacote CAD e no resolvedor da sua folha de cálculo.
Agora peça-lhe algo mais fácil. Resolva ∛x = 0.
Sabe a resposta. É zero, e é a única. Comece em 0,01 — já a menos de um centésimo — e observe:
0,01 → −0,02 → 0,04 → −0,08 → 0,16 → −0,32 → 0,64 → −1,28 → 2,56 → …
Após vinte iterações, a estimativa é −5242,88. O resíduo, que começou em 0,215, é agora 17,37. O método não estagnou nem se perdeu; afastou-se da resposta numa linha de raciocínio perfeitamente reta, duplicando o erro e invertendo o sinal a cada passo.
Nada correu mal
A tentação é procurar um erro no código. Não existe nenhum, e vale a pena fazer os cálculos porque são muito breves.
O passo de Newton é x − f(x)/f′(x). Para f(x) = x1/3, a derivada é (1/3)x−2/3, logo
f(x)/f′(x) = x1/3 ÷ ⅓x−2/3 = 3x
e a estimativa seguinte é x − 3x = −2x. Não de forma aproximada: exatamente. Cada iteração multiplica a estimativa por −2, a partir de qualquer ponto inicial, para sempre. É daí que vem −5242,88 — é 0,01 × (−2)19, e pode ler toda a progressão geométrica na tabela de iterações do Newton's Method Explorer sob a predefinição diverge.
O que a raiz cúbica fez foi quebrar o pressuposto em que o método assenta. O método de Newton substitui a curva pela sua reta tangente e salta para onde essa reta cruza o zero. Perto de uma raiz, essa é uma excelente aproximação — é o primeiro termo do desenvolvimento de Taylor, e os termos ignorados encolhem quadraticamente, que é precisamente a razão pela qual os dígitos duplicam. Mas ∛x tem uma tangente vertical no zero. A sua derivada não se limita a tornar-se pequena aí, torna-se infinita, e a curva não é localmente reta sob qualquer ampliação. As retas tangentes perto do zero apontam quase verticalmente para cima, pelo que o ponto onde cruzam o eixo fica quase três vezes mais distante do que onde começou.
Observe as duas colunas lado a lado na tabela: f(x) cresce enquanto f′(x) encolhe em direção a 0,001. O passo é o seu rácio, pelo que cresce em dobro.
A segunda falha é pior, porque parece um sucesso
A divergência pelo menos anuncia-se. Eis aquela que não o faz.
Tome f(x) = x³ − x, cujas raízes são −1, 0 e +1. Comece em 0,57. O método converge limpidamente, treze iterações, resíduo 2,3 × 10⁻¹¹ — e a raiz que devolve é −1.
Observe onde 0,57 se situa. Está a 0,43 de +1 e a 1,57 de −1. Está também a apenas 0,57 da raiz no zero. O método de Newton devolve aquela que está mais distante, após ter passado diretamente por duas raízes mais próximas, e reporta sucesso total com onze casas decimais corretas.
Agora comece em 0,58. Quinze iterações, e a resposta é +1.
Uma alteração de um centésimo na estimativa inicial, e o resolvedor aterra no extremo oposto da função. Entre esses dois pontos iniciais está 1/√3 ≈ 0,5774, onde a derivada de x³ − x é zero. A tangente aí é horizontal e cruza o eixo em lado nenhum por perto; aproxime-se desse ponto por qualquer um dos lados e o primeiro passo é enorme, em direções opostas. Cada ponto plano numa curva é uma plataforma de lançamento, e a região para onde o projeta nada tem a ver com a proximidade.
Esta é a propriedade que torna "que raiz vou obter?" uma questão sem resposta em geral. Para polinómios sobre os números complexos, os conjuntos de pontos iniciais que levam a cada raiz são chamados bacias de atração, e as suas fronteiras são fractais: arbitrariamente perto de um ponto que converge para uma raiz encontra-se um ponto que converge para outra. Hubbard, Schleicher e Sutherland mostraram em 2001 que é, contudo, possível construir um conjunto finito de pontos iniciais com a garantia de encontrar todas as raízes de um dado polinómio — um resultado notável, e uma medida de quanto trabalho a frase "basta usar o método de Newton" esconde silenciosamente.
O que isto muda na sua utilização
Daqui decorrem três consequências práticas, e todas as três são visíveis na página.
Em primeiro lugar, um resíduo pequeno não é uma garantia. Na execução diverge acima, o resíduo é 17,37 e está a subir, pelo que esse caso é detetado. Mas na execução com 0,57, o resíduo é 2 × 10⁻¹¹ e a resposta é uma raiz perfeitamente válida — apenas não aquela que quem fez a pergunta pretendia. Os testes de convergência podem dizer-lhe que encontrou uma solução. Nada no método lhe pode dizer que ela é a solução.
Em segundo lugar, os limites de iterações são fundamentais. O explorador para em vinte por predefinição, sendo essa a única razão pela qual a execução divergente tem um fim e não um transbordo (overflow). Os resolvedores em ambiente de produção fazem a mesma coisa, e o número não é arbitrário: uma iteração de Newton saudável numa função com bom comportamento atinge a precisão da máquina em cinco a dez passos, pelo que qualquer execução que ainda esteja a correr ao fim de vinte não está a convergir lentamente: simplesmente não está a convergir.
Em terceiro lugar, a solução para um mau ponto de partida raramente é um algoritmo melhor, mas sim um enquadramento num intervalo. A bisseção não pode divergir — se a função muda de sinal num intervalo, a regra do ponto médio não pode sair dele — e não pode escolher a raiz errada, porque existe apenas uma dentro do intervalo. É meramente lenta, ganhando um bit por passo em vez de duplicar os dígitos. A maioria dos resolvedores reais executa, portanto, um híbrido: aplica a bisseção até a estimativa estar comprovadamente próxima, e depois deixa que o método de Newton termine em três passos. Obtém-se a velocidade onde os pressupostos se mantêm e a garantia onde não se mantêm.
Existe uma nota de rodapé sobre o nome. O próprio método de Newton, de cerca de 1669, não usava derivadas e foi escrito para polinómios como uma sequência de substituições; Raphson simplificou-o em 1690; a forma ensinada hoje, com f′ e uma função diferenciável arbitrária f, é a de Simpson de 1740. Ypma reconstituiu toda a evolução em 1995. Aquilo que falha de forma tão instrutiva na raiz cúbica é uma arrumação do século XIX de uma receita do século XVII, e tem estado em todas as caixas de ferramentas numéricas desde então — o que é razão suficiente para saber precisamente onde falha.