Método de Newton para las raíces de los polinomios

Question

La forma estándar de utilizar el método de Newton para encontrar una raíz de un polinomio $p(x)$ es utilizar la fórmula de iteración $$x_{n+1}=x_n-{p(x)\over p'(x)}$$ Hace poco se me ocurrió una nueva forma de encontrar las raíces. Dejando que $x_1,...,x_n$ denotan el $n$ raíces y entorno $p(x)=x^n+\cdots +a_1x+a_0$ tenemos las fórmulas $$x_1+\cdots +x_n=-a_{n-1}$$ $$x_1x_2+\cdots +x_{n-1}x_n=a_{n-2}$$ y así hasta $$x_1x_2\cdots x_n=(-1)^na_0$$ Esto da un sistema no lineal de $n$ variables y $n$ ecuaciones, que pueden resolverse utilizando la versión multivariable del método de Newton. Utilizaríamos la iteración $$\bf x_{n+1}=x_n-[Df(x_n)]^{-1}f(x_n)$$ donde $$f(x_1,...,x_n)=\begin{bmatrix}x_1+\cdots +x_n+a_{n-1} \\ x_1x_2+\cdots +x_{n-1}x_n-a_{n-2} \\ \vdots \\ x_1\cdots x_n-(-1)^na_0 \end{bmatrix}$$ y $Df$ es la matriz derivada de $f$ .

Mi pregunta es: ¿hay alguna ventaja en utilizar este método para encontrar las raíces? La ventaja obvia es que el uso del método de Newton multivariable proporciona todas $n$ raíces simultáneamente mientras que el método normal sólo las da de una en una. Sin embargo, también me interesa saber cómo se compararía la tasa de convergencia de este método con el otro, y si uno tendería a ser más estable numéricamente que el otro.

Answer 1

Enhorabuena, has reinventado el método Durand-Kerner (1960) que fue desarrollado por Weierstraß en 1891.

Tiene una convergencia bastante satisfactoria, pero puede mostrar una fase inicial bastante lenta hasta que las aproximaciones de las raíces se acerquen lo suficiente a las raíces exactas. (Antes había applets de Java, pero como ahora son prácticamente inutilizables, e incluso a veces ya no se encuentran, que lo demuestran muy bien, especialmente para configuraciones simétricas de raíces y valores iniciales).

Answer 2

Los métodos de Newton o Quasi-Newton son un buen método para resolver sistemas de ecuaciones no lineales como la búsqueda de raíces de polinomios. Estos métodos pueden hacerse robustos utilizando métodos de búsqueda lineal y de región de confianza para garantizar la convergencia, así como técnicas de continuación para evitar quedarse atascado en mínimos locales. No es necesario formar la matriz completa de las segundas derivadas, sino sólo la capacidad de aplicarla a los vectores, o aproximaciones a su inversa son necesarios. Una buena referencia es el capítulo 11 del libro de Nocedal y Wright Optimización numérica .

Para el caso especial de la búsqueda de raíces numéricas se puede convertir el problema en la búsqueda de los valores propios de la matriz de acompañamiento a la que métodos rápidos y estables para resolver problemas de valores propios dispersos.