Método de Newton

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Algoritmo para encontrar zeros de funções

Na análise numérica, o método de Newton, também conhecido como método de Newton–Raphson, em homenagem a Isaac Newton e Joseph Raphson, é um método de descoberta de raízes algoritmo que produz aproximações sucessivamente melhores para as raízes (ou zeros) de uma função de valor real. A versão mais básica começa com uma função de variável única $f$ definida para uma variável real $x$ , a derivada da função $f'$ e uma estimativa inicial $x 0$ para uma raiz de $f$ . Se a função satisfizer suposições suficientes e a estimativa inicial for próxima, então

{displaystyle x_{1}=x_{0}-{frac {f(x_{0})}{f'(x_{0})}}}

é uma aproximação melhor da raiz do que $x 0$ . Geometricamente, $(x 1, 0)$ é a interseção de $eixo x$ e a tangente do gráfico de $f$ em $(x 0, f (x 0))$ : ou seja, a estimativa aprimorada é a única raiz da aproximação linear no ponto inicial. O processo é repetido como

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}}

até que um valor suficientemente preciso seja alcançado. O número de dígitos corretos quase dobra a cada passo. Este algoritmo é o primeiro da classe dos métodos de Householder, sucedido pelo método de Halley. O método também pode ser estendido para funções complexas e sistemas de equações.

Descrição

A ideia é começar com uma suposição inicial, depois aproximar a função por sua linha tangente e, finalmente, calcular o $x$ -intercept desta linha tangente. Esta $x$ -intercept normalmente será uma aproximação melhor para a raiz da função original do que a primeira suposição, e o método pode ser iterado.

x n + 1

é uma aproximação melhor do que

x n

para a raiz

x

da função

f

(curva azul)

Se a linha tangente à curva $f (x)$ em $x = x n$ intercepta o $x$ -eixo em $x n +1$ depois a inclinação é

{displaystyle f'(x_{n})={dfrac {f(x_{n})-0}{x_{n}-x_{n+1}}}}

Resolver para $x n +1$ fornece

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}.}

A iteração normalmente melhora a aproximação

Iniciamos o processo com algum valor inicial arbitrário $x 0$ . (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 restringir as possibilidades a um intervalo razoavelmente pequeno, apelando para o teorema do valor intermediário.) O método geralmente convergirá, desde que essa suposição inicial seja próxima o suficiente do zero desconhecido e que $f' (x 0) \neq 0$ . Além disso, para um zero de multiplicidade 1, a convergência é pelo menos quadrática (consulte Taxa de convergência) em uma vizinhança do zero, o que intuitivamente significa que o número de dígitos corretos praticamente dobra em cada etapa. Mais detalhes podem ser encontrados em § Análise abaixo.

Os métodos de Householder 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, especialmente se $f$ ou seus derivados são computacionalmente caros para avaliar.

História

O nome "método de Newton" é derivado da descrição de Isaac Newton de um caso especial do método em De analysi per aequationes numero terminorum infinitas (escrito em 1669, publicado em 1711 por William Jones) e em De metodis fluxionum et serierum infinitarum (escrito em 1671, traduzido e publicado como Method of Fluxions em 1736 por John Colson). No entanto, seu método difere substancialmente do método moderno dado acima. Newton aplicou o método apenas a polinômios, começando com uma estimativa inicial da raiz e extraindo uma sequência de correções de erros. Ele usou cada correção para reescrever o polinômio em termos do erro restante e, em seguida, resolveu uma nova correção negligenciando os termos de grau superior. Ele não conectou explicitamente o método com derivados ou apresentou uma fórmula geral. Newton aplicou esse método a problemas numéricos e algébricos, produzindo a série de Taylor no último caso.

Newton pode ter derivado seu método de um método semelhante e menos preciso de Vieta. A essência do método de Vieta pode ser encontrada no trabalho do matemático persa Sharaf al-Din al-Tusi, enquanto seu sucessor Jamshīd al-Kāshī usou uma forma do método de Newton para resolver $x P - N = 0$ para encontrar raízes de $N$ (Ypma 1995). Um caso especial do método de Newton para calcular raízes quadradas era conhecido desde os tempos antigos e é freqüentemente chamado de método babilônico.

O método de Newton foi usado pelo matemático japonês do século XVII Seki Kōwa para resolver equações de variável única, embora a conexão com o cálculo estivesse ausente.

O método de Newton foi publicado pela primeira vez em 1685 em Um tratado de álgebra histórico e prático por John Wallis. Em 1690, Joseph Raphson publicou uma descrição simplificada em Analysis aequationum universalis. Raphson também aplicou o método apenas a polinômios, mas evitou o tedioso processo de reescrita de Newton extraindo cada correção sucessiva do polinômio original. Isso permitiu que ele derivasse uma expressão iterativa reutilizável para cada problema. Finalmente, em 1740, Thomas Simpson descreveu o método de Newton como um método iterativo para resolver equações não lineares gerais usando cálculo, essencialmente dando a descrição acima. Na mesma publicação, Simpson também dá a generalização para sistemas de duas equações e observa que o método de Newton pode ser usado para resolver problemas de otimização definindo o gradiente como zero.

Arthur Cayley em 1879 em O problema imaginário de Newton-Fourier foi o primeiro a notar as dificuldades em generalizar o método de Newton para raízes complexas de polinômios com grau maior que 2 e valores iniciais complexos. Isso abriu caminho para o estudo da teoria das iterações de funções racionais.

Considerações práticas

O método de Newton é uma técnica poderosa—em geral, a convergência é quadrática: conforme o método converge na raiz, a diferença entre a raiz e a aproximação é elevada ao quadrado (o número de dígitos precisos aproximadamente dobra) a cada etapa. No entanto, existem algumas dificuldades com o método.

Dificuldade em calcular a derivada de uma função

O método de Newton requer que a derivada possa ser calculada diretamente. Uma expressão analítica para a derivada pode não ser facilmente obtida ou pode ser cara para avaliar. Nessas situações, pode ser apropriado aproximar a derivada usando a inclinação de uma linha que passa por dois pontos próximos na função. O uso dessa aproximação resultaria em algo como o método da secante, cuja convergência é mais lenta que a do método de Newton.

Falha do método para convergir para a raiz

É importante revisar a prova da 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.

Excesso

Se a primeira derivada não se comportar bem na vizinhança de uma raiz específica, 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 alttext="{displaystyle f(x)=|x|^{a},quad 0<af(x)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =|x|um,0<um<12{displaystyle f(x)=|x|^{a},quad 0<a<{tfrac Não.<img alt="f(x)=|x|^{a},quad 0<a

para o qual a raiz será ultrapassada e a sequência de $x$ divergirá. Para $a = 1 / 2$ , a raiz ainda será ultrapassada, mas a sequência oscilará entre dois valores. Para $1 / 2 < a < 1$ , a raiz ainda será ultrapassada, mas a sequência irá convergir e para $a \geq 1$ a raiz não será ultrapassada.

Em alguns casos, o método de Newton pode ser estabilizado usando sobre-relaxamento sucessivo, 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 é zero e o método terminará devido à divisão por zero.

Estimativa inicial ruim

Um grande erro na estimativa inicial pode contribuir para a não convergência do algoritmo. Para superar esse problema, muitas vezes pode-se linearizar a função que está sendo otimizada usando cálculos, logs, diferenciais ou até mesmo usando algoritmos evolutivos, como o tunelamento estocástico. Boas estimativas iniciais estão próximas da estimativa final do parâmetro globalmente ótimo. Na regressão não linear, a soma dos erros quadrados (SSE) é apenas "perto de" 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 converja rapidamente. É somente aqui que a matriz Hessiana do SSE é positiva e a primeira derivada do SSE é 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ções, limitar a solução a um intervalo conhecido por conter a raiz e 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 procurada tiver multiplicidade maior que um, a taxa de convergência é meramente linear (erros reduzidos por um fator constante a cada passo) a menos que passos especiais sejam tomados. Quando há duas ou mais raízes próximas, pode levar muitas iterações antes que as iteradas cheguem perto o suficiente de uma delas para que a convergência quadrática seja aparente. No entanto, se a multiplicidade $m$ da raiz for conhecida, o seguinte algoritmo modificado preserva a taxa de convergência quadrática:

{displaystyle x_{n+1}=x_{n}-m{frac {f(x_{n})}{f'(x_{n})}}.}

Isto é equivalente a usar o relaxamento excessivo 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, usar esse valor para aumentar a taxa de convergência.

Se a multiplicidade $m$ da raiz é finita, então $g (x) = f (x) / f' (x)$ terá uma raiz em o mesmo local com multiplicidade 1. Aplicando o método de Newton para encontrar a raiz de $g (x)$ recupera convergência quadrática em muitos casos, embora geralmente envolva a segunda derivada de $f (x)$ . Em um caso particularmente simples, se $f (x) = x m$ então $g (x) = x / m$ e o método de Newton encontra a raiz em uma única iteração com

{displaystyle x_{n+1}=x_{n}-{frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{frac {;{frac {x_{n}}{m}};}{frac {1}{m}}}=0,.}

Análise

Suponha que a função $f$ tenha um zero em $α$ , ou seja, $f (α) = 0$ , e $f$ é diferenciável em uma vizinhança de $α$ .

Se $f$ for continuamente diferenciável e sua derivada for diferente de zero em $α$ , então existe uma vizinhança de $α$ tal que para todos os valores iniciais $x 0$ nessa vizinhança, a sequência $(x n)$ irá convergir para $α$ .

Se $f$ for continuamente diferenciável, sua derivada será diferente de zero em $α$ , e tem uma segunda derivada em $α$ , então a convergência é quadrática ou mais rápida. Se a segunda derivada não for 0 em $α$ então a convergência é meramente quadrática. Se a terceira derivada existe e é limitada em uma vizinhança de $α$ , então:

{displaystyle Delta x_{i+1}={frac {f''(alpha)}{2f'(alpha)}}left(Delta x_{i}right)^{2}+Oleft(Delta x_{i}right)^{3},,}

onde

Delta x_{i}triangleq x_{i}-alpha ,.

Se a derivada for 0 em $α$ , então a convergência geralmente é apenas linear. Especificamente, se $f$ for duas vezes continuamente diferenciável, $f' (α) = 0$ e $f ″ (α) \neq 0$ , então existe uma vizinhança de $α$ tal que, para todos os valores iniciais $x 0$ em nessa vizinhança, a sequência de iterações converge linearmente, com taxa 1/ 2. Alternativamente, se $f' (α) = 0$ e $f' (x) \neq 0$ para $x \neq α$ , $x$ em uma vizinhança $U$ de $α$ , $α$ sendo um zero de multiplicidade $r$ , e se $f \in C r (U)$ , então existe uma vizinhança de $α$ tal que, para todos os valores iniciais $x 0$ nessa vizinhança, a sequência de iterações converge linearmente.

No entanto, mesmo a convergência linear não é garantida em situações patológicas.

Na prática, esses resultados são locais e a vizinhança de convergência não é conhecida antecipadamente. Mas também há alguns resultados na convergência global: por exemplo, dada uma vizinhança certa $U +$ de $α$ , se $f$ for duas vezes diferenciável em $U +$ e se $f' \neq 0$ , $f \cdot f ″ > 0$ em $U +$ , então, para cada $x 0$ em $U +$ a sequência $x k$ é monotonicamente decrescente para $α$ .

Prova da convergência quadrática para o método iterativo de Newton

De acordo com o teorema de Taylor, qualquer função $f (x)$ que tem uma segunda derivada contínua pode ser representada por uma expansão sobre um ponto próximo a uma raiz de $f (x)$ . Suponha que esta raiz seja $α$ . Em seguida, a expansão de $f (α)$ sobre $x n$ é:

{displaystyle f(alpha)=f(x_{n})+f'(x_{n})(alpha -x_{n})+R_{1},}

(1)

onde a forma de Lagrange do resto da expansão em série de Taylor é

{displaystyle R_{1}={frac {1}{2!}}f''(xi _{n})left(alpha -x_{n}right)^{2},,}

onde $ξ n$ está entre $x n$ e $α.$

Como $α$ é a raiz, (1) se torna:

{displaystyle 0=f(alpha)=f(x_{n})+f'(x_{n})(alpha -x_{n})+{tfrac {1}{2}}f''(xi _{n})left(alpha -x_{n}right)^{2},}

(2)

Dividindo a equação (2) por $f' (x n)$ e reorganizando dá

{displaystyle {frac {f(x_{n})}{f'(x_{n})}}+left(alpha -x_{n}right)={frac {-f''(xi _{n})}{2f'(x_{n})}}left(alpha -x_{n}right)^{2}}

(3)

Lembrando que $x n + 1$ é definido por

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}},,}

(4)

alguém descobre que

{displaystyle underbrace {alpha -x_{n+1}} _{varepsilon _{n+1}}={frac {-f''(xi _{n})}{2f'(x_{n})}}{(,underbrace {alpha -x_{n}} _{varepsilon _{n}},)}^{2},.}

Ou seja,

{displaystyle varepsilon _{n+1}={frac {-f''(xi _{n})}{2f'(x_{n})}}cdot varepsilon _{n}^{2},.}

(5)

Tomar o valor absoluto de ambos os lados dá

{displaystyle left|{varepsilon _{n+1}}right|={frac {left|f''(xi _{n})right|}{2left|f'(x_{n})right|}}cdot varepsilon _{n}^{2},.}

(6)

A equação (6) mostra que a ordem de convergência é pelo menos quadrática se as seguintes condições forem satisfeitas:

$f ? (x) \neq 0$ ; para todos $x \in Eu...$ , onde $Eu...$ é o intervalo $Não. α - Não. ε 0 |, α + | ε 0 |]$ ;
$f " (x)$ é contínuo, para todos $x \in Eu...$ ;
$M | ε 0 | < 1$

onde M é dado por

{displaystyle M={frac {1}{2}}left(sup _{xin I}vert f''(x)vert right)left(sup _{xin I}{frac {1}{vert f'(x)vert }}right).,}

Se essas condições forem válidas,

{displaystyle vert varepsilon _{n+1}vert leq Mcdot varepsilon _{n}^{2},.}

Bacias de atração

Os subconjuntos disjuntos das bacias de atração - as regiões da reta numérica real de modo que dentro de cada região a iteração de qualquer ponto leve a uma raiz específica - podem ser infinitas em número e arbitrariamente pequenas. Por exemplo, para a função $f (x) = x 3 - 2 x 2 - 11 x + 12 = (x - 4)(x - 1)(x + 3)$ , as seguintes condições iniciais estão em sucessivas bacias de atração:

2.35287527	converge para	4;
2.35284172	converge para	-3;
2.35283735	converge para	4;
2.352836327	converge para	-3;
2.352836323	converge para	1.

Análise de falha

O método de Newton só tem garantia de convergir se certas condições forem satisfeitas. Se as suposições feitas na prova da convergência quadrática forem atendidas, o método irá convergir. Para as subseções seguintes, a falha do método em convergir indica que as suposições feitas na prova não foram atendidas.

Pontos de partida ruins

Em alguns casos, as condições da função necessárias para a convergência são satisfeitas, mas o ponto escolhido como ponto inicial não está no intervalo onde o método converge. Isso pode acontecer, por exemplo, se a função cuja raiz é procurada se aproxima de zero assintoticamente quando $x$ vai para $\infty$ ou $-\infty$ . Nesses casos, um método diferente, como a bissecção, deve ser usado para obter uma estimativa melhor para o zero a ser usado como ponto inicial.

O ponto de iteração é estacionário

Considere a função:

{displaystyle f(x)=1-x^{2}.}

Tem um máximo em $x = 0$ e soluções de $f (x) = 0$ em $x = \pm1$ . Se começarmos a iterar do ponto estacionário $x 0 = 0$ (onde a derivada é zero), $x 1$ será indefinido, pois a tangente em $(0, 1)$ é paralelo ao eixo $x$ :

x_{1}=x_{0}-{frac {f(x_{0})}{f'(x_{0})}}=0-{frac {1}{0}}.

O mesmo problema ocorre se, em vez do ponto inicial, qualquer ponto de iteração for estacionário. Mesmo que a derivada seja pequena, mas não zero, a próxima iteração será uma aproximação muito pior.

O ponto de partida entra em um ciclo

As linhas tangentes

x 3 - 2 x + 2

em 0 e 1 cruzam o

x

-axis a 1 e 0 respectivamente, ilustrando por que o método de Newton oscila entre esses valores para alguns pontos iniciais.

Para algumas funções, alguns pontos iniciais podem entrar em um ciclo infinito, impedindo a convergência. Deixar

f(x)=x^{3}-2x+2!

e tome 0 como ponto de partida. A primeira iteração produz 1 e a segunda iteração retorna a 0, de modo que a sequência alternará entre as duas sem convergir para uma raiz. Na verdade, este 2-ciclo é estável: existem vizinhanças em torno de 0 e em torno de 1 a partir das quais todos os pontos iteram assintoticamente para o 2-ciclo (e, portanto, não para a raiz da função). Em geral, o comportamento da sequência pode ser muito complexo (ver fractal de Newton). A solução real dessa equação é −1,76929235….

Problemas derivados

Se a função não for continuamente diferenciável em uma vizinhança da raiz, então é possível que o método de Newton sempre diverja e falhe, a menos que a solução seja adivinhada na primeira tentativa.

A derivada não existe na raiz

Um exemplo simples de uma função em que o método de Newton diverge é tentar encontrar a raiz cúbica de zero. A raiz cúbica é contínua e infinitamente diferenciável, exceto para $x = 0$ , onde sua derivada é indefinida:

f(x)={sqrt[{3}]{x}}.

Para qualquer ponto de iteração $x n$ , o próximo ponto de iteração será:

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{frac {{x_{n}}^{frac {1}{3}}}{{frac {1}{3}}{x_{n}}^{-{frac {2}{3}}}}}=x_{n}-3x_{n}=-2x_{n}.}

O algoritmo ultrapassa a solução e cai do outro lado do eixo $y$ , mais longe do que estava inicialmente; aplicar o método de Newton na verdade dobra as distâncias da solução a cada iteração.

Na verdade, as iterações divergem ao infinito para cada $f (x) = | x | α$ , onde $0 < α < 1 / 2$ . No caso limite de $α = 1 / 2$ (raiz quadrada), as iterações irão alternar indefinidamente entre os pontos $x 0$ e $- x 0$ , então eles também não convergem neste caso.

Derivada descontínua

Se a derivada não for contínua na raiz, então a convergência pode não ocorrer em qualquer vizinhança da raiz. Considere a função

{displaystyle f(x)={begin{cases}0&{text{if }}x=0,\x+x^{2}sin {frac {2}{x}}&{text{if }}xneq 0.end{cases}}}

Sua derivada é:

{displaystyle f'(x)={begin{cases}1&{text{if }}x=0,\1+2xsin {frac {2}{x}}-2cos {frac {2}{x}}&{text{if }}xneq 0.end{cases}}}

Em qualquer vizinhança da raiz, esta derivada continua mudando de sinal conforme $x$ se aproxima de 0 pela direita (ou pela esquerda) enquanto $f (x) \geq x - x 2 > 0$ para $0 < x < 1$ .

Então $f (x) / f' (x)$ é ilimitado perto da raiz, e o método de Newton irá divergir em quase todos os lugares em qualquer vizinhança dele, embora:

a função é diferenciada (e, portanto, contínua) em toda parte;
o derivado na raiz é nonzero;
$f$ é infinitamente diferente, exceto na raiz; e
o derivado é limitado em um bairro da raiz (ao contrário $f (x) / f ? (x)$ ).

Convergência não quadrática

Em alguns casos, as iterações convergem, mas não convergem tão rapidamente quanto prometido. Nesses casos, métodos mais simples convergem tão rapidamente quanto o método de Newton.

Derivado zero

Se a primeira derivada for zero na raiz, a convergência não será quadrática. Deixar

f(x)=x^{2}!

então $f' (x) = 2 x$ e conseqüentemente

{displaystyle x-{frac {f(x)}{f'(x)}}={frac {x}{2}}.}

Portanto, a convergência não é quadrática, embora a função seja infinitamente diferenciável em todos os lugares.

Problemas semelhantes ocorrem mesmo quando a raiz está apenas "quase" dobro. Por exemplo, deixe

{displaystyle f(x)=x^{2}(x-1000)+1.}

As primeiras iterações começando em $x 0 = 1$ são

x 0

= 1

x 1

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 0.500250376...

x 2

x 3

x 4

x 5

x 6

x 7

leva seis iterações para chegar a um ponto onde a convergência parece ser quadrática.

Sem segunda derivada

Se não houver segunda derivada na raiz, a convergência pode não ser quadrática. Deixar

{displaystyle f(x)=x+x^{frac {4}{3}}.}

Então

{displaystyle f'(x)=1+{tfrac {4}{3}}x^{frac {1}{3}}.}

{displaystyle f''(x)={tfrac {4}{9}}x^{-{frac {2}{3}}}}

exceto quando $x = 0$ onde é indefinido. Dado $x n$ ,

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}={frac {{frac {1}{3}}{x_{n}}^{frac {4}{3}}}{1+{tfrac {4}{3}}{x_{n}}^{frac {1}{3}}}}}

que tem aproximadamente 4/3 vezes mais bits de precisão que $x n$ tem. Isso é menos do que 2 vezes o que seria necessário para a convergência quadrática. Então a convergência do método de Newton (neste caso) não é quadrática, embora: a função seja continuamente diferenciável em todos os lugares; a derivada não é zero na raiz; e $f$ é infinitamente diferenciável, exceto na raiz desejada.

Generalizações

Funções complexas

Bacias de atração para

x 5 - 1 = 0

; mais escuro significa mais iterações para convergir.

Ao lidar com funções complexas, o método de Newton pode ser aplicado diretamente para encontrar seus zeros. Cada zero tem uma bacia de atração no plano complexo, o conjunto de todos os valores iniciais que fazem com que o método converja para aquele zero em particular. Esses conjuntos podem ser mapeados como na imagem mostrada. Para muitas funções complexas, os limites das bacias de atração são fractais.

Em alguns casos, existem regiões no plano complexo que não estão em nenhuma dessas bacias de atração, o que significa que os iterados não convergem. Por exemplo, se alguém usar uma condição inicial real para buscar uma raiz de $x 2 + 1$ , todas as iterações subsequentes serão ser números reais e, portanto, as iterações não podem convergir para nenhuma das raízes, pois ambas as raízes são não reais. Nesse caso, quase todas as condições iniciais reais levam a um comportamento caótico, enquanto algumas condições iniciais iteram até o infinito ou repetem ciclos de qualquer comprimento finito.

Curt McMullen mostrou que para qualquer algoritmo puramente iterativo possível semelhante ao método de Newton, o algoritmo divergirá em algumas regiões abertas do plano complexo quando aplicado a algum polinômio de grau 4 ou superior. No entanto, McMullen forneceu um algoritmo geralmente convergente para polinômios de grau 3. Além disso, para qualquer polinômio, Hubbard, Schleicher e Sutherland forneceram um método para selecionar um conjunto de pontos iniciais tal que o método de Newton certamente convergirá em um dos eles, pelo menos.

Método de terceira ordem de Chebyshev

Iteração Nash–Moser

Sistemas de equações

K variáveis, k funções

Pode-se também usar o método de Newton para resolver sistemas de $k$ equações, que equivale a encontrar os (simultaneos) zeros de $k$ funções continuamente diferenciadas ${displaystyle f:mathbb {R} ^{k}to mathbb {R}.}$ Isto é equivalente a encontrar os zeros de uma única função de valor vetorial ${displaystyle F:mathbb {R} ^{k}to mathbb {R} ^{k}.}$ Na formulação dada acima, os escalares $x n$ são substituídos por vetores $x n$ e em vez de dividir a função $f (x n)$ por seu derivado $f ? (x n)$ um em vez tem de esquerda multiplicar a função $F (x n)$ pelo inverso de sua $k \times k$ Matriz jacobita $JJ F (x n)$ . Isso resulta na expressão

{displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-J_{F}(mathbf {x} _{n})^{-1}F(mathbf {x} _{n})}

Em vez de realmente calcular o inverso da matriz jacobiana, pode-se economizar tempo e aumentar a estabilidade numérica resolvendo o sistema de equações lineares

{displaystyle J_{F}(mathbf {x} _{n})(mathbf {x} _{n+1}-mathbf {x} _{n})=-F(mathbf {x} _{n})}

para o desconhecido $x n + 1 - x n$ .

K variáveis, m equações, com m > k

A variante $k$ -dimensional do método de Newton pode ser usada para resolver sistemas maiores que $k$ equações (não lineares) também se o algoritmo usar o inverso generalizado da matriz jacobiana não quadrada $J + = (J T J) -1 J T$ em vez do inverso de $J$ . Se o sistema não linear não tiver solução, o método tenta encontrar uma solução no sentido de mínimos quadrados não lineares. Veja algoritmo de Gauss-Newton para mais informações.

Em um espaço Banach

Outra generalização é o método de Newton para encontrar uma raiz de um $F$ funcional definido em um espaço de Banach. Neste caso, a formulação é

{displaystyle X_{n+1}=X_{n}-{bigl (}F'(X_{n}){bigr)}^{-1}F(X_{n}),,}

onde $F' (X n)$ é a derivada de Fréchet calculada em $X n$ . É preciso que a derivada de Fréchet seja limitadamente invertível em cada $X n$ para que o método seja aplicável. Uma condição para a existência e convergência para uma raiz é dada pelo teorema de Newton-Kantorovich.

Sobre números p-ádicos

Na análise $p$ -ádica, o método padrão para mostrar uma equação polinomial em uma variável tem um $p$ -adic root é o lema de Hensel, que usa a recursão do método de Newton no $p$ -ádicos. Devido ao comportamento mais estável de adição e multiplicação nos números $p$ -ádicos em comparação com os números reais (especificamente, a bola unitária no $p$ -adics é um anel), a convergência no lema de Hensel pode ser garantida sob hipóteses muito mais simples do que no método clássico de Newton na linha real.

Método de Newton-Fourier

O método de Newton-Fourier é a extensão de Joseph Fourier do método de Newton para fornecer limites no erro absoluto da aproximação da raiz, enquanto ainda fornece convergência quadrática.

Suponha que $f (x)$ é duas vezes continuamente diferenciável em $[a, b]$ e que $f$ contém uma raiz neste intervalo. Suponha que $f' (x), f ″ (x) \neq 0$ neste intervalo (este é o caso, por exemplo, se $f (a) < 0$ , $f (b) > 0$ , e $f' (x) > 0$ e $f ″ (x) > 0$ neste intervalo). Isso garante que haja uma única raiz nesse intervalo, chame-o de $α$ . Se for côncavo para baixo em vez de côncavo para cima, substitua $f (x)$ por $- f (x)$ já que eles têm as mesmas raízes.

Seja $x 0 = b$ o ponto final direito do intervalo e seja $z 0 = a$ seja o ponto final esquerdo do intervalo. Dado $x n$ , defina

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}},}

que é apenas o método de Newton como antes. Então defina

{displaystyle z_{n+1}=z_{n}-{frac {f(z_{n})}{f'(x_{n})}},}

onde o denominador é $f' (x n)$ e não $f' (z n)$ . As iterações $x n$ serão estritamente decrescentes até a raiz enquanto as iterações $z n$ será estritamente crescente até a raiz. Também,

lim _{nto infty }{frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}={frac {f''(alpha)}{2f'(alpha)}}

para que a distância entre $x n$ e $z n$ diminui quadraticamente.

Métodos quase-Newton

Quando o jacobiano não está disponível ou é muito caro para calcular a cada iteração, um método quasi-Newton pode ser usado.

Q-analógico

O método de Newton pode ser generalizado com o q-análogo da derivada usual.

Métodos de Newton modificados

Procedimento de Maehly

Uma equação não linear tem múltiplas soluções em geral. Mas se o valor inicial não for apropriado, o método de Newton pode não convergir para a solução desejada ou pode convergir para a mesma solução encontrada anteriormente. Quando já encontramos soluções N de $f(x)=0$ , então a próxima raiz pode ser encontrada aplicando o método de Newton para a próxima equação:

{displaystyle F(x)={frac {f(x)}{prod _{i=1}^{N}(x-x_{i})}}=0.}

Este método é aplicado para obter zeros da função Bessel do segundo tipo.

Hirano's Modified Newton Method Method

O método de Newton modificado de Hirano é uma modificação que conservava a convergência do método Newton e evitando a deserdidão. É desenvolvido para resolver polinômios complexos.

Intervalo Newton, Método

Combinando o método de Newton com a aritmética de intervalo é muito útil em alguns contextos. Isso fornece um critério de parada mais confiável do que os usuais (que são um pequeno valor da função ou uma pequena variação da variável entre iterações consecutivas). Além disso, isso pode detectar casos em que o método de Newton converge teoricamente, mas diverge numericamente por causa de uma precisão insuficiente de ponto flutuante (esse é normalmente o caso dos polinômios de grande grau, onde uma mudança muito pequena da variável pode mudar drasticamente o valor da função; ver Wilkinson, polinomial).

Considere $f \to C 1 (x)$ , onde $x$ é um intervalo real, e suponha que tenhamos uma extensão de intervalo $f '$ de $f'$ , o que significa que f toma como entrada um intervalo $y \subseteq x$ e produz um intervalo $f ' (y)$ tal que:

{displaystyle {begin{aligned}F'([y,y])&={f'(y)}\[5pt]F'(Y)&supseteq {f'(y)mid yin Y}.end{aligned}}}

Também assumimos que $0 \notin F' (X)$ , portanto, em particular $f$ tem no máximo uma raiz em $X$ . Em seguida, definimos o operador de intervalo de Newton por:

{displaystyle N(Y)=m-{frac {f(m)}{F'(Y)}}=left{left.m-{frac {f(m)}{z}}~right|~zin F'(Y)right}}

onde $m \in Y$ . Observe que a hipótese em $F'$ implica que $N (Y)$ é bem definido e é um intervalo (consulte aritmética de intervalo para obter mais detalhes sobre operações de intervalo). Isso naturalmente leva à seguinte sequência:

{displaystyle {begin{aligned}X_{0}&=X\X_{k+1}&=N(X_{k})cap X_{k}.end{aligned}}}

O teorema do valor médio garante que, se houver uma raiz de $f$ em $x k$ , então também está em $x k + 1$ . Além disso, a hipótese em $f '$ garante que $x k + 1$ é no máximo metade do tamanho de $x k k k$ Quando $m$ é o ponto médio de $y$ , então essa sequência converge para $[x*, x*]$ , onde $x*$ é a raiz de $> f$ em $x$ .

se $f ' (x)$ contém estritamente 0, o uso da divisão de intervalo prolongada produz uma união de dois intervalos para $n (x)$ ; As raízes múltiplas são, portanto, automaticamente separadas e limitadas.

APLICAÇÕES

Problemas de minimização e maximização

O método de Newton pode ser usado para encontrar um mínimo ou máximo de uma função $f (x)$ . A derivada é zero no mínimo ou no máximo; portanto, os mínimos locais e os máximos podem ser encontrados aplicando o método de Newton ao derivado. A iteração se torna:

{displaystyle x_{n+1}=x_{n}-{frac {f'(x_{n})}{f''(x_{n})}}.}

Inversos multiplicativos de números e séries de potências

Uma aplicação importante é a divisão de Newton–Raphson, que pode ser usada para encontrar rapidamente o recíproco de um número $a$ , usando apenas multiplicação e subtração, ou seja, o número $x$ tal que $1 / x = a$ . Podemos reformular isso como encontrar o zero de $f (x) = 1 / x - a$ . Temos $f' (x) = - 1 / x 2$ .

A iteração de Newton é

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{frac {{frac {1}{x_{n}}}-a}{frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).}

Portanto, a iteração de Newton precisa apenas de duas multiplicações e uma subtração.

Este método também é muito eficiente para calcular o inverso multiplicativo de uma série de potências.

Resolvendo equações transcendentais

Muitas equações transcendentais podem ser resolvidas até uma precisão arbitrária usando o método de Newton.

Quando o método de Newton pode ser aplicado a uma equação transcendental, e converge para uma solução da equação, isso implica que a solução é um número computável que é exatamente representado pelo par formado por uma aproximação inicial e um algoritmo para aumentar a precisão de qualquer aproximação.

Obtenção de zeros de funções especiais

O método de Newton é aplicado à razão das funções de Bessel para obter sua raiz.

Verificação numérica para soluções de equações não lineares

Uma verificação numérica para soluções de equações não lineares foi estabelecida usando o método de Newton várias vezes e formando um conjunto de candidatos a soluções.

Exemplos

Raiz quadrada

Considere o problema de encontrar a raiz quadrada de um número $a$ , ou seja, o número positivo $x$ tal que $x 2 = a$ . O método de Newton é um dos muitos métodos de cálculo de raízes quadradas. Podemos reformular isso como encontrar o zero de $f (x) = x 2 - a$ . Temos $f' (x) = 2 x$ .

Por exemplo, para encontrar a raiz quadrada de 612 com uma estimativa inicial $x 0 = 10$ , a sequência dada pelo método de Newton é:

{displaystyle {begin{matrix}x_{1}&=&x_{0}-{dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{dfrac {10^{2}-612}{2times 10}}&=&35.6qquad qquad qquad quad ;,{}\x_{2}&=&x_{1}-{dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{dfrac {35.6^{2}-612}{2times 35.6}}&=&{underline {2}}6.395,505,617,978dots \x_{3}&=&vdots &=&vdots &=&{underline {24.7}}90,635,492,455dots \x_{4}&=&vdots &=&vdots &=&{underline {24.738,6}}88,294,075dots \x_{5}&=&vdots &=&vdots &=&{underline {24.738,633,753,7}}67dots end{matrix}}}

onde os dígitos corretos estão sublinhados. Com apenas algumas iterações, é possível obter uma solução precisa para muitos lugares decimais.

Reorganizando a fórmula, como segue, produz o método babilônico de encontrar raízes quadradas:

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{frac {x_{n}^{2}-a}{2x_{n}}}={frac {1}{2}}{biggl (}2x_{n}-{Bigl (}x_{n}-{frac {a}{x_{n}}}{Bigr)}{biggr)}={frac {1}{2}}{Bigl (}x_{n}+{frac {a}{x_{n}}}{Bigr)}}

ou seja a média aritmética da estimativa, $x n$ e $a / x n$ .

Solução de cos(x) = x3

Considere o problema de encontrar o número positivo ${textstyle x}$ com ${textstyle cos x=x^{3}}$ . Podemos reformular isso como encontrar o zero de ${textstyle f(x)=cos(x)-x^{3}}$ . nós temos ${textstyle f'(x)=-sin(x)-3x^{2}}$ . Desde então ${textstyle cos(x)leq 1}$ para todos ${textstyle x}$ e $1}" xmlns="http://www.w3.org/1998/Math/MathML">x3>1- Sim. 1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ae03d6d4b823349f5e1e0eb8028426cfc045a8f" style="vertical-align: -0.338ex; width:6.645ex; height:2.509ex;"/>$ para $1}" xmlns="http://www.w3.org/1998/Math/MathML">x>1- Sim. 1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/638645c800c290bcb96035d96b2813f1cecc328a" style="vertical-align: -0.338ex; width:5.591ex; height:2.176ex;"/>$ , sabemos que a nossa solução está entre 0 e 1.

Por exemplo, com uma estimativa inicial $x 0 = 0,5$ , a sequência dada por Newton método é (observe que um valor inicial de 0 levará a um resultado indefinido, mostrando a importância de usar um ponto de partida próximo da solução):

{displaystyle {begin{matrix}x_{1}&=&x_{0}-{dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{dfrac {cos 0.5-0.5^{3}}{-sin 0.5-3times 0.5^{2}}}&=&1.112,141,637,097dots \x_{2}&=&x_{1}-{dfrac {f(x_{1})}{f'(x_{1})}}&=&vdots &=&{underline {0.}}909,672,693,736dots \x_{3}&=&vdots &=&vdots &=&{underline {0.86}}7,263,818,209dots \x_{4}&=&vdots &=&vdots &=&{underline {0.865,47}}7,135,298dots \x_{5}&=&vdots &=&vdots &=&{underline {0.865,474,033,1}}11dots \x_{6}&=&vdots &=&vdots &=&{underline {0.865,474,033,102}}dots end{matrix}}}

Os dígitos corretos estão sublinhados no exemplo acima. Em particular, $x 6$ está correto até 12 casas decimais. Vemos que o número de dígitos corretos após o ponto decimal aumenta de 2 (para $x 3$ ) para 5 e 10, ilustrando a convergência quadrática.

Código

O seguinte é um exemplo de implementação do método de Newton na linguagem de programação Python (versão 3.x) para encontrar uma raiz de uma função f que tem derivada f_prime .

A estimativa inicial será $x 0 = 1$ e a função será $f (x) = x 2 - 2$ para que $f' (x) = 2 x$ .

Cada nova iteração do método de Newton será denotada por x1. Verificaremos durante o cálculo se o denominador (yprime) se torna muito pequeno (menor que epsilon), o que seria o caso se $f' (x n) \approx 0$ , caso contrário, uma grande quantidade de erro pode ser introduzida.

de f(x: retorno xNão.2 - Não. 2 # f(x) = x^2 - 2de F_prime(x:retorno 2*x # f'(x) = 2xde newtons_method( x0, # O palpite inicial f, # A função cuja raiz estamos tentando encontrar F_prime, # O derivado da função tolerância, # A precisão de 7 dígitos é desejada Epsilon, # Não dividir por um número menor do que este Max_iterations, # O número máximo de iterações para executar : para Eu... em gama(Max_iterations: Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = f(x0) Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = F_prime(x0) se abs(Sim.) < Epsilon: # Pare se o denominador é muito pequeno pausa x1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x0 - Não. Sim. / Sim. Computação de Do Newton se abs(x1 - Não. x0) < tolerância: # Pare quando o resultado está dentro da tolerância desejada retorno x1 # x1 é uma solução dentro da tolerância e número máximo de iterações x0 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x1 # Atualizar x0 para iniciar o processo novamente retorno Nenhuma O método de Newton não convergiu

Más resultados...