|
<math> x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} , n\in \mathbb{N}</math>
onde <math display="inline">x_0</math> é uma aproximação inicial dada, <math display="inline">n</math> indica a <math display="inline">n</math>-ésima iteração do algoritmo e <math display="inline">f'(x_n)</math> é a derivada da função <math display="inline">f</math> no ponto <math display="inline">x_n.</math>
== Descrição ==
[[Ficheiro:Interação de Newton.gif|miniaturadaimagem|A função <math>f</math> mostrado em azul e a reta tangente em vermelho. Vemos que <math>x_{n+1}</math> é uma aproximação melhor do que <math>x_n</math> para a raiz <math>x</math> da função <math>f</math>.]]
A ideia é começar com uma estimativa inicial que seja razoavelmente próxima da raiz verdadeira, então, aproximar a função por sua linha tangente (derivada) usando cálculo e, finalmente, calcular o intercepto ''x'' dessa linha tangente por álgebra elementar. Esta interceptação ''x'' será normalmente uma melhor aproximação da raiz da função original do que a primeira estimativa, e o método pode ser iterado.
Mais formalmente, suponha que ''f'' : (''a'' , ''b'')→ ℝ é uma função diferenciável definida no intervalo (''a'' , ''b'') com valores nos números reais ℝ, e temos alguma aproximação atual <math>x_n</math>. Então, podemos derivar a fórmula para uma melhor aproximação, referindo-nos ao diagrama à direita. A equação da linha tangente à curva <math>y = f(x)</math> em <math>x = x_n</math> = é:
<math>y=f^' (x_n )(x-x_n )+f(x_n),</math>
onde <math>f'</math> denota a derivada. O intercepto <math>x</math> desta linha (o valor de <math>x</math> que faz ''<math>y=0</math>'' ) é tomado como a próxima aproximação, <math>x_{n+1}</math>, para a raiz, de modo que a equação da linha tangente seja satisfeita quando <math>(x,y)=(x_{n+1},0)</math>:
<math>0=f^' (x_n )(x_{n+1}-x_n )+f(x_n)</math>.
Resolver para <math>x_{n+1}</math> dá:
<math>x_{n+1}=x_n- \frac{f(x_n )}{f^' (x_n)} </math>
Iniciamos o processo com algum valor inicial arbitrário <math>x_0</math>. (Quanto mais próximo do zero, melhor. Mas, na ausência de qualquer intuição sobre onde o zero pode estar, um método de "adivinhar e verificar" pode limitar as possibilidades a um intervalo razoavelmente pequeno apelando para o teorema do valor intermediário.) O método geralmente convergirá, desde que essa estimativa inicial seja próxima o suficiente do zero desconhecido e que <math>f'(x_0)\neq0</math>. Além disso, para um zero de multiplicidade 1, a convergência é pelo menos quadrática (ver taxa de convergência) em uma vizinhança do zero, o que significa intuitivamente que o número de dígitos corretos praticamente dobra a cada etapa. Mais detalhes podem ser encontrados na seção de análise abaixo.
Os métodos de agregado familiar são semelhantes, mas têm ordem superior para uma convergência ainda mais rápida. No entanto, os cálculos extras necessários para cada etapa podem diminuir o desempenho geral em relação ao método de Newton, particularmente se ''f'' ou suas derivadas forem computacionalmente caros para avaliar.
== Interpretação geométrica do método de Newton ==
Um ponto importante a ser observado diz respeito a praticidade do método de Newton. Caso a função ''f'' seja complicada, encontrar sua derivada pode ser muito trabalhoso e o método torna-se improdutivo. Nesses casos, o [[método das secantes]] é mais produtivo de ser utilizado, porque não exige que a derivada de ''f'' seja conhecida.
{{Referências}}
Apesar de método de Newton ser muito eficiente, em geral a convergência é quadrática: conforme o método converge na raiz, a diferença entre a raiz e a aproximação é ao quadrado (o número de dígitos precisos quase dobra) em cada etapa. No entanto, existem algumas dificuldades com o método:
'''Dificuldade no cálculo derivado de uma função'''
O método de Newton requer que a derivada possa ser calculada diretamente. Caso a função F seja complicada, encontrar sua derivada pode ser muito trabalhoso e o método torna-se improdutivo. Nesse sentido, pode ser apropriado aproximar a derivada usando a inclinação de uma reta através de dois pontos próximos na função. O uso dessa aproximação resultaria em algo como o [[Método das secantes|método da secante]], cuja convergência é mais lenta do que a do método de Newton.
'''A falha do método convergir para a raiz'''
É importante revisar a prova de convergência quadrática do método de Newton antes de implementá-lo. Especificamente, deve-se revisar as suposições feitas na prova. Para situações em que o método não consegue convergir, é porque as suposições feitas nesta prova não são atendidas.
'''Overshoot'''
Se a primeira derivada não se comportar bem na vizinhança de uma determinada raiz, o método pode ultrapassar e divergir dessa raiz. Um exemplo de função com uma raiz, para a qual a derivada não se comporta bem na vizinhança da raiz, é:
<math>f(x)=|x|^a,\quad 0 < a < \tfrac{1}{2}</math>
para o qual a raiz será ultrapassada e a sequência de x irá divergir.
Para a = 1/2, a raiz ainda será ultrapassada, mas a sequência oscilará entre dois valores.
Pra 1/2 < a <1, a raiz ainda será ultrapassada, mas a sequência irá convergir, e para a ≥ 1 a raiz não será ultrapassada de forma alguma.
Em alguns casos, o método de Newton pode ser estabilizado utilizando a relação sucessiva ou a velocidade de convergência pode ser aumentada usando o mesmo método.
==== Ponto estacionário ====
Se um ponto estacionário da função for encontrado, a derivada dele será zero. Então, devido à [[divisão por zero]], o método terminará.
==== Estimativa inicial ruim ====
Alguns fatores podem constribuir para a não convergência do algoritmo, sendo que uma dela é a indicação de um grande erro na estimativa inicial. Por isso, para contornar esse problema, muitas vezes pode-se linearizar a função que está sendo otimizada, usando cálculos, registros, diferenciais ou até mesmo utilizando de algoritmos evolutivos, como o tunelamento estocástico. A resolução deste problema é importante, pois as estimativas iniciais boas estão próximas da estimativa final do parâmetro globalmente ideal.
Na regressão não linear, a soma dos erros quadráticos (SEQ) está apenas "perto da" parabólica, na região das estimativas dos parâmetros finais. As estimativas iniciais encontradas aqui permitirão que o método de Newton-Raphson convirja rapidamente. É apenas aqui que a [[Matriz hessiana|matriz Hessiana]] do SEQ é positiva e a primeira derivada do SEQ é próxima de zero.
==== Mitigação de não convergência ====
Em uma implementação robusta do método de Newton, é comum colocar limites no número de [[Iteração|iterações]], limitar a solução a um intervalo conhecido para conter a raiz. Além disso, combinar o método com um método de localização de raiz mais robusto.
=== Convergência lenta para raízes de multiplicidade maior que 1 ===
Se a raiz buscada tem [[multiplicidade]] maior que um, a taxa de convergência é meramente linear (erros reduzidos por um fator constante em cada etapa), a menos que etapas especiais sejam tomadas. Quando há duas ou mais raízes próximas, podem ser necessárias muitas iterações antes que as interações se aproximem o suficiente de uma delas para que a convergência quadrática seja aparente.
No entanto, se a multiplicidade m da raiz é conhecido, o seguinte algoritmo modificado preserva a taxa de convergência quadrática:<ref>{{citar web |url=https://web.archive.org/web/20190524083302/http://mathfaculty.fullerton.edu/mathews/n2003/NewtonAccelerateMod.html |titulo=Accelerated and Modified Newton Methods |data= |acessodata=4 Março 2016 |lingua=Inglês}}</ref>
<math>x_{n+1} = x_n - m\frac{f(x_n)}{f'(x_n)}. </math>
Isso é equivalente ao uso de super-relaxamento sucessivo.
Por outro lado, se a multiplicidade m da raiz não for conhecida, é possível estimar m depois de realizar uma ou duas iterações e, em seguida, use esse valor para aumentar a taxa de convergência.{{Referências}}
==Ligações externas==
| 