Visualizador do Método de Newton

busca de raízes com passos tangentes e diagnóstico de convergência

A carregar a simulação interativa...

0,55 e 0,58 acabam em raízes opostas 🖖

Newton duplica o número de algarismos corretos a cada passo, e a predefinição Raiz rápida mostra-o bem: partindo de x₀ = 1 em direção a √2, o erro toma os valores 0,414, 0,0858, 0,00245, 2,1 × 10⁻⁶, 1,6 × 10⁻¹². Quatro passos, doze algarismos. O mesmo mecanismo também pode fazê-lo falhar. Quando a derivada é quase nula, a tangente fica praticamente horizontal e o passo torna-se enorme. Em x³ − x, começar em 0,5774 lança a primeira aproximação para −2210 — é por isso que 0,55 acaba na raiz negativa, enquanto 0,58 acaba na positiva.

siga a tangente até o eixo 🖖

Para descobrir onde uma curva cruza o zero, o método de Newton substitui a curva pela sua reta tangente na estimativa atual e salta para o ponto onde essa reta corta o eixo x. Como uma curva suave parece quase reta de perto, esse cruzamento costuma ficar bem mais próximo da raiz verdadeira. Repetindo, você se aproxima rápido. A fórmula: xn+1 = xn − f(xn)/f'(xn).

computadores dividem sem dividir 🖖

CPUs modernas costumam calcular a/b encontrando primeiro 1/b, e o método de Newton faz isso sem usar nenhuma divisão. Aplicado a f(x) = 1/x − a, dá a iteração xn+1 = xn(2 − a·xn), formada apenas por multiplicações e subtrações, operações baratas para o hardware. O mesmo truque está por trás das rotinas rápidas de raiz inversa, incluindo a famosa do Quake III.

MÉTODO DE NEWTON — QUANDO ELE DOBRA SEUS DÍGITOS E QUANDO ELE FOGE

Em que caso de Newton você está?

O método de Newton segue a tangente até o eixo e repete: xₖ₊₁ = xₖ − f(xₖ)/f′(xₖ). Quando funciona é espetacular, dobrando aproximadamente o número de dígitos corretos a cada passo. Todas as formas de falhar vêm do mesmo lugar: aquele denominador. Um f′ quase nulo joga você longe, um f′ que se anula na raiz reduz tudo a passo de tartaruga, e começar do lado errado de um ponto crítico entrega outra raiz.

Convergência quadrática — o caso que deu fama a Newton ek+1 ∝ ek2
Inclinação plana na raiz — a velocidade cai para linear f′(r) = 0 ⇒ ek+1 ≈ (1 − 1/m)ek
Ele foge — o passo cresce em vez de encolher x → −2x
Ele converge — para uma raiz que você não pediu f′(x₀) = 0

01

Convergência quadrática — o caso que deu fama a Newton

O que você sabe: f é suave, f′ está confortavelmente longe de zero perto da raiz e o ponto inicial está próximo o bastante. Cada passo praticamente eleva o erro ao quadrado.

Iteração: ek+1 ∝ ek2

Exemplo resolvido: f(x) = x² − 2 a partir de x₀ = 1 → 1,5; 1,416667; 1,41421569; 1,41421356237: primeiro 1 e depois 3, 6 e 12 dígitos corretos

Abrir este caso: raiz rápida
Convergência quadrática — o caso que deu fama a Newton. Cada tangente cai bem mais perto da raiz que a anterior, e o erro vai ao quadrado. f é suave, f′ está confortavelmente longe de zero perto da raiz e o ponto inicial está próximo o bastante. Cada passo praticamente eleva o erro ao quadrado.
Cada tangente cai bem mais perto da raiz que a anterior, e o erro vai ao quadrado.

02

Inclinação plana na raiz — a velocidade cai para linear

O que você sabe: A raiz é múltipla, então f e f′ se anulam juntos ali. A tangente fica quase horizontal exatamente para onde você vai.

Iteração: f′(r) = 0 ⇒ ek+1 ≈ (1 − 1/m)ek

Exemplo resolvido: f(x) = x³ a partir de x₀ = 0,1 → 0,0667; 0,0444; 0,0296; 0,0198: cada passo multiplica o erro por 2/3 em vez de elevá-lo ao quadrado

Abrir este caso: inclinação plana
Inclinação plana na raiz — a velocidade cai para linear. Uma raiz tripla achata a tangente: cada passo cobre só um terço do que falta. A raiz é múltipla, então f e f′ se anulam juntos ali. A tangente fica quase horizontal exatamente para onde você vai.
Uma raiz tripla achata a tangente: cada passo cobre só um terço do que falta.

03

Ele foge — o passo cresce em vez de encolher

O que você sabe: f′ desaba mais rápido que f conforme você se aproxima da raiz, então a correção f/f′ passa do ponto mais a cada iteração.

Iteração: x → −2x

Exemplo resolvido: f(x) = ∛x a partir de x₀ = 0,01 → −0,02; 0,04; −0,08; 0,16: a atualização dá exatamente x → −2x, então a distância dobra e o sinal se inverte para sempre

Abrir este caso: diverge
Ele foge — o passo cresce em vez de encolher. Cada tangente cruza o eixo ao dobro da distância da anterior, do lado oposto. f′ desaba mais rápido que f conforme você se aproxima da raiz, então a correção f/f′ passa do ponto mais a cada iteração.
Cada tangente cruza o eixo ao dobro da distância da anterior, do lado oposto.

04

Ele converge — para uma raiz que você não pediu

O que você sabe: A função tem várias raízes e o início fica perto de um ponto crítico, onde f′ é pequeno e o primeiro passo é enorme.

Iteração: f′(x₀) = 0

Exemplo resolvido: f(x) = x³ − x a partir de x₀ = 0,7 assenta em +1, mas a partir de x₀ = 0,5 o primeiro passo já aterrissa em −1 — uma raiz do outro lado de outras duas

Abrir este caso: bacia errada
Ele converge — para uma raiz que você não pediu. Dois inícios vizinhos, duas raízes diferentes: a fronteira está no ponto crítico. A função tem várias raízes e o início fica perto de um ponto crítico, onde f′ é pequeno e o primeiro passo é enorme.
Dois inícios vizinhos, duas raízes diferentes: a fronteira está no ponto crítico.

Problema resolvido na íntegra

  1. A raiz de x³ − x − 2 pelo método de Newton 5 passos

    O método de Newton encontra o zero de x³ − x − 2 em três iterações. A bisseção precisa de cerca de vinte passos só para chegar a 10⁻⁶, valor que Newton ultrapassa logo no segundo. Descubra de onde vem esta rapidez e qual é o seu preço.

    1. O método resume-se a uma ideia: substituir a curva pela sua tangente e resolver essa em seu lugar, porque uma reta pode ser resolvida exatamente. A estimativa seguinte é onde a tangente cruza o zero.

    2. A partir de 1,5, o primeiro passo é quase toda a viagem. A função é apenas −0,125 aí, o declive é 5,75 e a sua razão desloca a estimativa em cerca de 0,022.

    3. Mais dois passos e os dígitos deixam de mudar. A ferramenta indica três iterações porque a quarta moveria a resposta por menos do que a tolerância.

    4. A grandeza reveladora não é a aproximação, mas o erro. Ao acompanhá-lo, o padrão torna-se evidente: cada erro é aproximadamente o quadrado do anterior, pelo que o número de algarismos corretos duplica a cada passo: 2, depois 4, depois 7 e, por fim, 14.

    5. E a constante à frente não é arbitrária. A expansão de f em torno da raiz mostra que a razão dos erros ao quadrado consecutivos tende para |f″/2f′| avaliado aí, o que para esta cúbica é 0,768. As razões observadas são 0,786, 0,768, 0,768.

    Resposta

    A ferramenta apresenta a raiz 1,52138 após 3 iterações. A razão é a convergência quadrática: a bisseção reduz o intervalo para metade a cada passo e precisa de cerca de vinte para chegar a 10⁻⁶; em Newton, o erro fica aproximadamente elevado ao quadrado e já está abaixo desse valor no segundo passo. Em contrapartida, não há garantia de convergência. Depois de cercar uma raiz, a bisseção não pode falhar. Newton não dispõe desse intervalo, e um ponto inicial onde a derivada seja quase nula pode lançar a aproximação seguinte para muito longe. É esta a escolha fundamental dos métodos numéricos de determinação de raízes. Por isso, os algoritmos usados na prática começam por cercar a raiz e só depois passam para Newton.

Percurso de aprendizagem

Três métodos numéricos e onde cada um falha

Conduz a Integração numérica a tangente utilizada para encontrar a solução, bem como a convergência mais rápida do percurso.

Referências (1)

Problemas de exemplo

  • raiz rápida - A partir de x0 = 1, o erro desce por 0,414, 0,0858, 0,00245, 2,1 × 10⁻⁶, 1,6 × 10⁻¹². Cada valor é aproximadamente o quadrado do anterior, por isso quatro passos dão doze algarismos corretos de √2.
  • inclinação plana - x³ tem uma raiz tripla em 0, onde Newton avança lentamente em vez de elevar o erro ao quadrado: cada passo limita-se a multiplicar x por 2/3. Ao fim de seis, para em 0,0088 e assinala convergência. A raiz é 0.
  • diverge - Para a raiz cúbica, o método de Newton reduz-se exatamente a x → -2x; as aproximações são 0,01, -0,02, 0,04, -0,08, duplicando de módulo e alternando de sinal para sempre. Diverge a partir de qualquer ponto inicial que não seja a própria raiz.
  • bacia errada - x0 = 0,55 está do lado positivo e converge para -1. A primeira tangente lança-o para -3,60, pois a derivada quase se anula em 1/√3 = 0,5774; já 0,58 converge para +1.
  • raiz negativa - É a mesma função x² - 2 da Raiz rápida, mas parte de -1,2 em vez de 1 e converge para -1,414 em três passos. O ponto inicial decide qual raiz Newton encontra, independentemente da que se pretendia obter.
  • tolerância rigorosa - Partindo de 1,6, Newton chega a 1,5213797 para x³ - x - 2 em três iterações, mesmo com uma tolerância de 10⁻⁸. A bisseção precisaria de cerca de vinte e sete divisões ao meio para igualar o resultado.