Cuenca de atracción para el método de Newton

9

Se sabe que el método de Newton para resolver ecuaciones no lineales converge cuadráticamente cuando la suposición inicial está "suficientemente cerca" de la solución.

¿Qué es "suficientemente cerca"?

¿Existe literatura sobre la estructura de esta cuenca de atracción?

iterative-method convergence nonlinear-equations David Ketcheson
fuente
La raíz debe estar aislada (no múltiple). Si el Hessian es uniformemente definido (cóncavo hacia arriba o hacia abajo) en la región, debería estar listo. Por supuesto, garantizar o probar estas condiciones empíricamente generalmente no es práctico.
hardmath
Vi la pregunta en NA-Digest el otro día y me pareció intrigante. Aparentemente no fui el único :-)
Wolfgang Bangerth

Respuestas:

8

Para una sola ecuación racional en el dominio complejo, la cuenca de atracción es fractal, la competencia de un conjunto llamado Julia. http://en.wikipedia.org/wiki/Julia_set . Para la teoría con algunas buenas figuras en línea, ver, por ejemplo,
http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf

Incluso el método de Newton amortiguado "globalizado" para tiene una cuenca fractal de atracción; ver http://www.jstor.org/stable/10.2307/2653002 .X3-1=0 0

Por lo tanto, no tiene mucho sentido especificar en detalle qué está "suficientemente cerca" de la solución. Si se conocen los límites de las segundas derivadas, existe el teorema de Newton-Kantorovich, que proporciona límites más bajos en el radio de una bola en la que converge el método de Newton, pero excepto en 1D, estos tienden a ser bastante pesimistas.

Los límites computacionalmente útiles se pueden obtener usando la aritmética de intervalos; véase, por ejemplo, mi artículo
Shen Zuhe y A. Neumaier, El operador Krawczyk y el teorema de Kantorovich, J. Math. Anal. Appl. 149 (1990), 437-443.
http://www.mat.univie.ac.at/~neum/scan/61.pdf

Arnold Neumaier
fuente
Es solo en el plano complejo que tiene una cuenca fractal de atracción. En la línea real, cualquier suposición inicial x > 0 servirá (una vez que x > 1 la convergencia disminuirá mononíticamente y aparecerá rápidamente la tasa cuadrática). X3-1=0 0X>0 0X>1
hardmath
1
@hardmath: sí, pero la ecuación compleja se convierte en dos ecuaciones reales en 2 variables, para lo cual se aplica lo mismo.
Arnold Neumaier
4

"Suficientemente cerca" es difícil de caracterizar teniendo en cuenta que da lugar a una clase de fractales . Los métodos de Newton con estrategias de globalización como la búsqueda de líneas y la región de confianza extienden la cuenca de atracción. Si hay disponible una estructura de problemas adicional, como en la optimización, los supuestos necesarios para la convergencia pueden debilitarse aún más.

Jed Brown
fuente
Solo por curiosidad, ¿tiene algún ejemplo para "Si hay disponible una estructura de problema adicional, como en la optimización, los supuestos necesarios para la convergencia pueden debilitarse aún más"?
vanCompute
@vanCompute Consulte este ejemplo para ver un ejemplo relacionado con la optimización, donde el objeto funcional proporciona información que se pierde en las condiciones de optimización de primer orden. Otra forma sería saber que una cierta continuación (pseudotransiente, parámetro, cuadrícula, etc.) siempre converge, pero el residual puede tener que aumentar antes de llegar a la solución si se intenta resolver el problema directamente.
Jed Brown el
3

Hay algunos resultados útiles para el método de Newton aplicado a polinomios complejos.

F

r=η2re
ηFreF

Anthony Manning da otros límites explícitos en Cómo asegurarse de encontrar una raíz de un polinomio complejo utilizando el método de Newton (Teorema 1.2).

Vea también Cómo encontrar todas las raíces de polinomios complejos por el método de Newton de Hubbard et al.
Inventar. Matemáticas. 146 (2001), no. 1, 1–33. pdf

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