¿Converge el método de Newton para todos los polinomios?

Question

Hice una implementación del método de Newton (comenzando en $x=\pi$) para polinomios en el lenguaje de programación Uiua (aquí está si estás interesado, pero ten en cuenta que Uiua se ve raro). Funciona bien para la mayoría de polinomios pero hay algunos en los que se bloquea. Intenté [12 ¯9 ¯21 37 ¯41 ¯10 31 49], (un polinomio de grado 7 con coeficientes listados desde el grado más bajo al más alto) y el tiempo de ejecución se agotó. Al inspeccionar más a fondo, parece estar oscilando de manera algo aleatoria en el rango $[0.3,0.7]$, incluso después de 500+ iteraciones, cuando la respuesta real es $-0.568$. Otra implementación en línea también falla en converger al comenzar en $x=\pi$.

Mi pregunta es si el método de Newton debería estar funcionando en este caso o si debo esperar encontrar algún problema en mi código o en la forma en que Uiua maneja los floats. ¿El método de Newton siempre converge para polinomios?

Answer 1

Aquí está una gráfica de la función $$f(x) = 49 x^7+31 x^6-10 x^5-41 x^4+37 x^3-21 x^2-9 x+12$$ en la región de interés. La curva azul es $f$. Las líneas naranjas representan la órbita hacia adelante de $x_0 = \pi$ bajo $x \mapsto x - f(x)/f'(x)$, conectando $(x_i, f(x_i))$ con la siguiente iteración $(x_{i+1}, 0)$, luego con $(x_{i+1}, f(x_{i+1}))$, y así sucesivamente. Nota que las iteraciones iniciales no se muestran porque el valor de la función en esos puntos es grande.

La línea roja gruesa muestra el comportamiento de estado estable de la órbita, y podemos ver que converge a un ciclo de valores de $3$, que son aproximadamente $$S = \{0.355634, 0.796309, 0.680185\}.$$

Esto sugiere que para cualquier $x \in S$, la función racional $$g(x) = x - \frac{f(x)}{f'(x)} = \frac{294 x^7+155 x^6-40 x^5-123 x^4+74 x^3-21 x^2-12}{343 x^6+186 x^5-50 x^4-164 x^3+111 x^2-42 x-9}$$ cumple con $$g(g(g(x))) = x.$$

De hecho, podemos suponer que siempre que $f$ tenga un vecindario con un mínimo local pero sin raíz, entonces existe la posibilidad de una elección inicial $x_0$ para la cual la órbita hacia adelante no converge a una raíz.

Answer 2

Como ya han señalado otras respuestas, hay casos en los que la iteración de Newton no converge.

Una pregunta interesante es cuántos valores pueden ocurrir esto y si es un conjunto o una medida completa o un conjunto nulo. Resulta que hay polinomios para los cuales el proceso de Newton no converge, y el conjunto de tales valores iniciales es un conjunto de medida completa.

Esto no ocurre para polinomios de grado menor que 3, pero puede ocurrir para polinomios cúbicos como $$ p(z) = z^3-2z+2 $$ La dinámica del proceso de Newton $z\mapsto {\cal N}_p(z)$ se hace visible en la gráfica a continuación que muestra la dinámica para valores iniciales reales con $z\in[-4,4]$.

La imagen consiste en 18 franjas de colores, cada color codifica un número real (4=púrpura, 2=violeta, 1=cian, 0=negro, 1=rojo, 2=naranja, 4=amarillo, ±=blanco). De arriba a abajo, las franjas muestran los valores de la $n$-ésima iteración de Newton, donde la fila 0 indica los valores iniciales.

Los valores iniciales menores que aproximadamente 0.83 convergen al cero violeta de $p(z)$ en $z\approx-1.76929$, pero todos los valores en un intervalo alrededor de $0$ son atraídos por el ciclo negro-rojo $$\cdots0\mapsto 1\mapsto 0\mapsto 1\mapsto 0\mapsto1\cdots$$

Pero ¿cuántos de esos polinomios "malos" hay? ¿Son esos polinomios un conjunto nulo en el conjunto de todos los polinomios, o hay una cantidad sustancial de tales polinomios?

Para polinomios cúbicos uno puede estudiar el comportamiento del punto crítico de ${\cal N}_p$. Por ejemplo, $0$ es un punto crítico de ${\cal N}_{p_\lambda}$ para todos los cúbicos de la familia $$ p_\lambda(z) = z^3+(\lambda-1)z-\lambda $$ Graficar cómo se comporta el punto crítico de ${\cal N}_{p_\lambda}$ bajo la iteración da como resultado lo siguiente, donde $\lambda$ varía sobre el plano complejo donde $-2.5\leqslant Re(\lambda),Im(\lambda)\leqslant 2.5$.

Hay pequeños puntos negros que son subconjuntos de medida completa en el espacio de $\lambda$ para los cuales el punto crítico no converge a un cero de $p_\lambda$.

Ampliando el punto negro alrededor de $\lambda\approx0.3+1.64i$ se ve así:

Hay infinitos de ellos.

---

Respuesta a un comentario: El tinte en las dos últimas imágenes representa el límite de $$\lim_{n\to\infty} {\cal N}_{p_\lambda}^n(0)$$ es decir, el destino del punto crítico 0 de ${\cal N}_{p_\lambda}$ bajo iteración, siempre que la iteración converja. Cuando no converge, entonces el punto en $\lambda$ se colorea en negro. Hay 3 tonos alrededor de la isla en la 3ra imagen porque $p_\lambda$ tiene 3 ceros complejos que pueden ocurrir como límite. El tono indica cuál cero y se relaciona con el límite de una manera no obvia y de tal forma que los 3 tonos están separados por 120° en el espacio de colores (rojo, verde, azul). Esto debe tomarse con cautela porque la ubicación exacta de los ceros de $p_\lambda$ depende de $\lambda$, así que esto solo se cumple aproximadamente y solo en pequeñas regiones. Es la razón por la que los colores de los ceros en la imagen general varían suavemente sobre grandes extensiones del plano de $\lambda$.

La brillantez indica cuántas iteraciones se requirieron para concluir que la iteración converge para ese $\lambda$: más brillante = más. Para puntos cerca de las islas de Mandelbrot, la saturación se incrementa nuevamente antes de finalmente disminuir a blanco. Esto es por razones estéticas y resulta en el resplandor morado-blanco alrededor de las islas negras.

El algoritmo suaviza los colores interpolando el número de iteraciones (que son números naturales) a números reales; similar a cómo suavizarías el potencial alrededor de un conjunto de Mandelbrot con carga eléctrica. Con este fin, uno debe introducir una noción de distancia al cero complejo más cercano de $p_\lambda$.

Han pasado más de 10 años desde que hice estas imágenes; así que ten paciencia. El resumen de la página de wiki contiene y explica la parte relevante del código C que usé en ese entonces. La idea para esta familia específica de cúbicas proviene del libro de Reitgen y Richter.

Answer 3

No es necesario llegar hasta polinomios de 7mo grado para ver este comportamiento. Considera $f(x) = x^3-5x$. Si inicias la iteración de Newton-Raphson con una suposición inicial de $1$, simplemente oscilarás entre $1$ y $-1$. Este es un equilibrio inestable, pero claramente uno que podrías encontrar. (No hay error de redondeo que te salve de este ciclo).

Para un equilibrio estable considera $f(x) = x^4-6x^2-11$. Si inicias la iteración de Newton-Raphson con una suposición inicial de $1$, oscilarás entre $1$ y $-1$. Además, si comienzas con una suposición inicial cerca de $1$, digamos $1.2$ o $0.8$, ¡los iterados convergerán al mismo ciclo de oscilación!