Bacia de atração pelo método de Newton

9

Sabe-se que o método de Newton para resolver equações não lineares converge quadraticamente quando o palpite inicial é "suficientemente próximo" da solução.

O que é "suficientemente próximo"?

Existe literatura sobre a estrutura dessa bacia de atração?

iterative-method convergence nonlinear-equations David Ketcheson
fonte

A raiz deve ser isolada (não múltipla). Se o hessiano é uniformemente definido (côncavo para cima ou para baixo) na região, você deve estar pronto. É claro que garantir ou testar essas condições empiricamente é geralmente impraticável.

23312 hardmath

Vi a pergunta no NA-Digest outro dia e achei intrigante. Aparentemente eu não era o único :-)

Wolfgang Bangerth

8

Para uma única equação racional no domínio complexo, a bacia de atração é fractal, a obrigatoriedade de um conjunto chamado Julia. http://en.wikipedia.org/wiki/Julia_set . Para uma teoria com algumas figuras on-line interessantes, consulte, por exemplo,
http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf

Até o método de Newton amortecido '' globalizado '' para tem uma bacia de atração fractal; veja http://www.jstor.org/stable/10.2307/2653002 . $x^3-1=0$

Portanto, há pouco sentido em especificar em detalhes o que é "suficientemente próximo" da solução. Se alguém conhece limites nas segundas derivadas, existe o teorema de Newton - Kantorovich, que fornece limites inferiores no raio de uma bola em que o método de Newton converge, mas, exceto em 1D, estes tendem a ser bastante pessimistas.

Limites computacionalmente úteis podem ser obtidos usando aritmética de intervalo; veja, por exemplo, meu artigo
Shen Zuhe e A. Neumaier, operador de Krawczyk e teorema de Kantorovich, J. Math. Anal. Appl. 149 (1990), 437-443.
http://www.mat.univie.ac.at/~neum/scan/61.pdf

Arnold Neumaier
fonte

É somente no plano complexo que

tem uma bacia de atração fractal. Na linha real, qualquer palpite inicial

será suficiente (uma vez que

a convergência será mononone decrescente e a taxa quadrática aparecerá rapidamente).

x^{3} - 1 = 0

$x^3 - 1 = 0$

x > 0

$x > 0$

x > 1

$x > 1$

hardmath

11

@hardmath: sim, mas a equação complexa se torna duas equações reais em 2 variáveis, às quais o mesmo se aplica.

Arnold Neumaier

4

É difícil caracterizar "suficientemente próximo", considerando que dá origem a uma classe de fractais . Os métodos de Newton com estratégias de globalização, como busca por linha e região de confiança, estendem a bacia de atração. Se uma estrutura adicional de problemas estiver disponível, como na otimização, as suposições necessárias para a convergência podem ser ainda mais enfraquecidas.

Jed Brown
fonte

Apenas por curiosidade, você tem algum exemplo para "Se uma estrutura de problema adicional estiver disponível, como na otimização, as suposições necessárias para a convergência podem ser mais enfraquecidas".

vanCompute

@vanCompute Veja este exemplo para um exemplo relacionado à otimização, onde o objeto funcional fornece informações que são perdidas nas condições de otimização de primeira ordem. Outra forma seria o conhecimento de que uma certa continuação (pseudotransiente, parâmetro, grade etc.) sempre convergiu, mas o resíduo pode precisar aumentar antes de chegar à solução se tentar resolver o problema diretamente.

precisa

3

Existem alguns resultados úteis para o método de Newton aplicado a polinômios complexos.

$f$

r = \frac{η}{2 d}

$r=\frac{\eta}{2d}$

η

$\eta$

f

$f$

d

$d$

f

$f$

Outros limites explícitos são dados por Anthony Manning em Como ter certeza de encontrar a raiz de um polinômio complexo usando o método de Newton (Teorema 1.2).

Veja também Como encontrar todas as raízes de polinômios complexos pelo método de Newton por Hubbard et al.
Inventar. Matemática. 146 (2001), n. 1, 1-33. pdf

lhf
fonte

Adaptado de math.stackexchange.com/a/1038487/589 .

lhf 31/12/14

Bacia de atração pelo método de Newton

Respostas: