Esta é uma tradução automática; o texto original em inglês é a versão de referência. Ler o original
O método de Newton pode duplicar o erro a cada passo, e a resposta estava a 0,01 de distância
Comece a 0,01 da resposta. Vinte iterações depois, estará em −5 242,88, e todos os passos foram calculados corretamente.
Resolva x³ − x − 2 = 0. Não existe uma fórmula elegante que valha a pena memorizar; faça, por isso, o que qualquer programa de cálculo numérico faz: estime um valor inicial e deixe o método de Newton corrigir essa estimativa.
Comece em 1,5. Três iterações depois, obtém 1,52138, e o valor da função nesse ponto é 5,89387 × 10⁻⁷, a menos de um milionésimo de zero. Três passos. Cada passo praticamente duplica o número de algarismos corretos, razão pela qual este método se encontra na sua calculadora, no seu programa de CAD e no resolvedor da sua folha de cálculo.
Peça-lhe agora algo mais simples. Resolva ∛x = 0.
A resposta é óbvia: é zero, e é a única. Comece em 0,01 — já a um centésimo de distância — e observe:
0.01 → −0.02 → 0.04 → −0.08 → 0.16 → −0.32 → 0.64 → −1.28 → 2.56 → …
Ao fim de vinte iterações, a estimativa é de −5242,88. O resíduo, que começou em 0,215, é agora 17,37. O método não bloqueou nem oscilou sem rumo: afastou-se da resposta através de uma linha de raciocínio perfeitamente retilínea, duplicando o erro e invertendo o sinal em cada iteração.
Nada correu mal
A tentação é procurar um erro no código. Não existe nenhum, e vale a pena fazer os cálculos analíticos pela sua simplicidade.
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: com rigor absoluto. Cada iteração multiplica a estimativa por −2, a partir de qualquer ponto inicial, para sempre. É daí que provém −5242,88: corresponde a 0,01 × (−2)19, podendo ver toda a sucessã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 invalidar o pressuposto em que o método assenta. O método de Newton substitui a curva pela sua reta tangente e salta para o ponto onde essa reta interseta o zero. Na vizinhança de uma raiz, esta é uma aproximação excelente: corresponde ao primeiro termo do desenvolvimento de Taylor, e os termos desprezados decrescem quadraticamente, que é precisamente a razão pela qual os dígitos duplicam. Contudo, ∛x tem uma tangente vertical em zero. A sua derivada não se limita a diminuir aí: torna-se infinita, e a curva não é localmente linear a qualquer escala de ampliação. As retas tangentes perto de zero apontam quase na vertical, e a interseção com o eixo vai parar a −2x: ao dobro da distância da raiz em relação ao ponto de partida, no lado oposto.
Observe as duas colunas lado a lado na tabela: f(x) cresce enquanto f′(x) diminui até 0,001. Sendo o passo a razão entre ambas, o seu crescimento é duplamente acentuado.
A segunda falha é pior, porque se assemelha ao sucesso
A divergência, pelo menos, dá sinal de si.
Considere-se f(x) = x³ − x, cujas raízes são −1, 0 e +1. Comece em 0,57. O método converge com facilidade, treze iterações, resíduo de 2,3 × 10⁻¹¹ — e a raiz devolvida é −1.
Veja onde 0,57 se situa. Dista 0,43 de +1 e 1,57 de −1. Dista também apenas 0,57 da raiz em zero. O método de Newton devolve aquela que se encontra mais afastada, após ter ultrapassado sem hesitar duas raízes mais próximas, reportando pleno êxito com onze casas decimais corretas.
Comece agora, em vez disso, em 0,58. Quinze iterações, e a resposta é +1.
Uma variação de um centésimo na estimativa inicial faz o algoritmo convergir para o extremo oposto da função. Entre esses dois pontos de partida situa-se 1/√3 ≈ 0,5774, onde a derivada de x³ − x é nula. A tangente nesse ponto é horizontal e cruza o eixo a uma distância imensa; ao aproximar-se desse ponto por qualquer um dos lados, o primeiro passo é desmesurado, em sentidos opostos. Qualquer ponto plano numa curva atua como uma plataforma de lançamento, e a região para onde somos projetados nada tem a ver com proximidade.
É esta a propriedade que transforma «para qual das raízes o método convergirá?» numa pergunta em geral sem resposta. No caso dos polinómios sobre os números complexos, os conjuntos de pontos iniciais que conduzem a cada raiz designam-se bacias de atração, e as suas fronteiras são fractais: arbitrariamente próximo de um ponto que converge para uma raiz encontra-se um ponto que converge para outra. Hubbard, Schleicher e Sutherland demonstraram em 2001 que é, ainda assim, possível construir um conjunto finito de pontos de partida que garante encontrar todas as raízes de um dado polinómio. Trata-se de um resultado de relevo e de uma medida de todo o trabalho que o simples conselho «basta usar o método de Newton» omite discretamente.
O que isto muda na prática
Daqui decorrem três consequências práticas, estando as duas primeiras patentes nesta página.
Em primeiro lugar, um resíduo de valor reduzido não é uma garantia formal. Na execução de teste de diverge apresentada acima, o resíduo é 17,37 e continua a subir, pelo que a anomalia é detetada. Mas no teste a partir de 0,57 o resíduo é 2 × 10⁻¹¹ e o resultado é uma raiz perfeitamente válida — apenas não é aquela que se pretendia obter. Os testes de convergência podem indicar que se encontrou uma solução. Nada no método pode garantir que se trata da solução.
Em segundo lugar, a imposição de um limite máximo de iterações é um elemento estrutural crítico. O explorador para, por predefinição, ao fim de vinte iterações, razão única pela qual a execução divergente tem um termo e não resulta num erro de transbordo (overflow). Os resolvedores em ambientes de produção procedem exatamente do mesmo modo, e este valor 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; logo, qualquer cálculo que permaneça em execução às vinte iterações não está a convergir lentamente: simplesmente não está a convergir.
Em terceiro lugar, a solução para um ponto de partida desfavorável não é, em regra, recorrer a um algoritmo mais sofisticado, mas sim a um método de enquadramento por intervalos. O método da 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 — nem pode escolher a raiz errada, porque existe apenas uma dentro desse intervalo. É apenas lento, progredindo à razão de um bit por passo em vez de duplicar o número de dígitos. A maioria dos resolvedores reais recorre, por conseguinte, a uma abordagem híbrida: aplicam a bisseção até que a aproximação esteja comprovadamente próxima, deixando depois o método de Newton concluir o cálculo em três passos. Obtém-se, assim, a rapidez quando as condições teóricas se verificam e a garantia de convergência quando não se verificam.
Resta uma nota histórica sobre o nome. O método formulado pelo próprio Newton, por volta de 1669, não recorria a derivadas e fora concebido para polinómios sob a forma de uma sucessão de substituições; Raphson simplificou-o em 1690; a formulação lecionada atualmente, com f′ e uma função diferenciável f arbitrária, deve-se a Simpson em 1740. Ypma reconstituiu toda esta linhagem evolutiva em 1995. A formulação que falha de modo tão instrutivo perante a raiz cúbica é um aperfeiçoamento setecentista de uma receita do século XVII, e tem integrado desde então todas as ferramentas de cálculo numérico — razão mais do que suficiente para se conhecer com precisão onde se situam os seus limites.