Influencia de un término constante pequeño en las raíces de un polinomio

Question

Sea $p(x)=a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0,\enspace a_i\in\mathbb{C}$ algún polinomio.

Supongamos que $|a_0|$ es muy pequeño (en comparación con la magnitud de los demás coeficientes).

¿Hay alguna forma de que las raíces (complejas) de $p(x)$ podría verse muy afectado por el ajuste $a_0 = 0$ ?

Creo que la respuesta podría ser no porque el polinomio es continuo en el término constante y, por tanto, pequeños cambios en el término constante sólo afectarán ligeramente a la función. Pero, ¿es esto cierto para la localización de las raíces?

¿Por qué pregunto esto?

Intento incorporar un buscador de raíces personalizado en mi programa Matlab, pero desafortunadamente en algunos casos raros uno de sus bucles no converge si el coeficiente constante del vector de entrada es de la magnitud $\approx 10^{-18}$ y entonces el algoritmo se bloquea. Sin embargo, converge si pongo el término constante a cero, pero me preocupa que pueda obtener resultados erróneos.

---

EDITAR 1:

Basándome en la respuesta de @Fixed Point, pude encontrar un sucesor ( NAClab ) del buscador de root de Matlab que estaba usando y ya no se bloquea. Luego pasé a investigar rápidamente los polinomios que proponía Punto Fijo. Aquí están los resultados:

Figura 1: Hasta el grado 17, el buscador de raíces mantiene los resultados en el eje real. A partir del grado 18, las raíces calculadas adquieren una parte imaginaria que crece linealmente con el grado del polinomio.

La relación entre el coeficiente constante $a_0$ y el coeficiente de orden superior $a_n$ es del orden de $10^{-16}$ cuando las raíces empiezan a divergir del eje real y crece con aproximadamente un orden de magnitud por aumento de grado del polinomio.

Figura 2: Aquí el coeficiente constante se fija en cero, se puede ver que las raíces que están cerca unas de otras se perturban bastante significativamente.

El código Matlab para reproducir los resultados puede descargarse aquí .

---

EDITAR 2: Para responder a las preguntas de Punto Fijo:

Dado que el algoritmo de Brent tiene garantizada la convergencia (puede ser lenta, pero convergerá), tengo curiosidad por saber por qué tenías el problema que decías.

Al desarrollar la extensión MIMO para ANP (diagrama de nyquist animado, un proyecto de ocio con fines educativos) llegué a darme cuenta de que el programa tendría que lidiar con polinomios de alto orden incluso para sistemas MIMO pequeños. Entonces me di cuenta de que las 'raíces' de Matlab producían resultados muy imprecisos cuando había raíces con multiplicidades altas, incluso en casos triviales y obvios como $(x+1)^4=0$ (prueba roots(poly([-1,-1,-1,-1])) ).

Aunque mi programa sólo sirviera para entretener, eso no era suficiente. Después de encontrar Multraíz (por Zeng) y probándolo con bastante éxito usando sistemas MIMO aleatorios encontré que además de algunos fallos triviales de resolver tenía un fallo más grave que tenía que ver con un pequeño término constante.

¿Cómo/por qué se bloqueaba tu aplicación?

Uno de estos polinomios se puede definir en Matlab de la siguiente manera (es el que finalmente me llevó a esta pregunta SE):

p = hex2num(['bfae7873980ada44';'bfd79794c0074ef6';'bfe9e4c737c98680';'bfe5502ed16afae0';'bf81513e302abba0';'3fc59ae0b4d97164';'bc80000000000000'])';

Úsalo como entrada para Multroot: multroot(p) Lo más probable es que termine con un error diciendo que no se ha asignado un argumento de salida. (Tenga en cuenta que el algoritmo utiliza vectores iniciales aleatorios y por lo tanto tiene éxito con una pequeña probabilidad)

¿Era el fzero de MATLAB el que fallaba?

Como ya he explicado, no utilicé 'fzero' y desgraciadamente no puede ayudarme en este caso, ya que en la documentación dice que necesita un cambio de signo para detectar un cero, lo que no ocurre con todas las raíces de un polinomio general.

Answer 1

Considera el polinomio, $$p_1(x)=(x-1)(x-2)...(x-19)(x-20).$$ Después de expandirlo, obtienes,

\begin{array}{|r|r|} \hline \textrm{Exponent} & \textrm{Coefficients of $p(x)$}\\\hline 0 & 2432902008176640000 \\ 1 & -8752948036761600000 \\ 2 & 13803759753640704000 \\ 3 & -12870931245150988800 \\ 4 & 8037811822645051776 \\ 5 & -3599979517947607200 \\ 6 & 1206647803780373360 \\ 7 & -311333643161390640 \\ 8 & 63030812099294896 \\ 9 & -10142299865511450 \\ 10 & 1307535010540395 \\ 11 & -135585182899530 \\ 12 & 11310276995381 \\ 13 & -756111184500 \\ 14 & 40171771630 \\ 15 & -1672280820 \\ 16 & 53327946 \\ 17 & -1256850 \\ 18 & 20615 \\ 19 & -210 \\ 20 & 1 \\\hline \end{array}

Obsérvese que el término constante aquí es $20!$ . Consideremos ahora el polinomio $$p_2(x)=x^{20}p_1(1/x)$$ que básicamente invierte los coeficientes, dándonos

\begin{array}{|r|r|} \hline \textrm{Exponent} & \textrm{Coefficients of $p_2(x)$}\\\hline 0 & 1 \\ 1 & -210 \\ 2 & 20615 \\ 3 & -1256850 \\ 4 & 53327946 \\ 5 & -1672280820 \\ 6 & 40171771630 \\ 7 & -756111184500 \\ 8 & 11310276995381 \\ 9 & -135585182899530 \\ 10 & 1307535010540395 \\ 11 & -10142299865511450 \\ 12 & 63030812099294896 \\ 13 & -311333643161390640 \\ 14 & 1206647803780373360 \\ 15 & -3599979517947607200 \\ 16 & 8037811822645051776 \\ 17 & -12870931245150988800 \\ 18 & 13803759753640704000 \\ 19 & -8752948036761600000 \\ 20 & 2432902008176640000 \\\hline \end{array}

Este polinomio $p_2(x)$ que presento como respuesta a su pregunta. El término constante aquí es muy pequeño en comparación con los demás coeficientes . El término constante es sólo uno. Las raíces de este $p_2(x)$ polinomio son simplemente $$x=\frac{1}{20},\frac{1}{19},\frac{1}{18},...,\frac{1}{3},\frac{1}{2},1.$$ Las raíces son todas distintas, racionales y están razonablemente separadas en la recta real. Ahora definamos $p_3(x)=p_2(x)$ excepto que el término constante es igual a cero en lugar de uno y compara las raíces.

\begin{array}{|l|l|} \hline \textrm{Old roots of $p_2(x)$} & \textrm{New roots of $p_3(x)$}\\\hline 0.05 & 0\\ 0.0526316 & 0.00606612 - 0.0292961i\\ 0.0555556 & 0.00606612 + 0.0292961i\\ 0.0588235 & 0.0236616 - 0.0549143i\\ 0.0625 & 0.0236616 + 0.0549143i\\ 0.0666667 & 0.0510481 - 0.0735013i\\ 0.0714286 & 0.0510481 + 0.0735013i\\ 0.0769231 & 0.0855378 - 0.0823447i\\ 0.0833333 & 0.0855378 + 0.0823447i\\ 0.0909091 & 0.123755 - 0.0796379i\\ 0.1 & 0.123755 + 0.0796379i\\ 0.111111 & 0.16195 - 0.064656i\\ 0.125 & 0.16195 + 0.064656i\\ 0.142857 & 0.196345 - 0.0378412i\\ 0.166667 & 0.196345 + 0.0378412i\\ 0.2 & 0.218259\\ 0.25 & 0.249\\ 0.333333 & 0.333333\\ 0.5 & 0.5\\ 1 & 1\\ \hline \end{array}

Como puede ver, algunas de las raíces permanecen igual o no cambian mucho. Pero la mayoría de las raíces "cambiaron significativamente" y se volvieron complejas en lugar de puramente reales. Así que la respuesta a tu pregunta es, no pongas el término constante a cero. No funcionará en general y puede darte respuestas extrañas.

Si estos coeficientes son demasiado grandes para ti, entonces simplemente divide el polinomio $p_2(x)$ por $20!$ y se obtienen los coeficientes

\begin{array}{|r|r|} \hline \textrm{Exponent} & \textrm{Coefficients of $\frac{p_2(x)}{20!}$}\\\hline 0 & 4.110317623312165\times10^{-19}\\ 1 & -8.631667008955546\times10^{-17}\\ 2 & 8.473419780458027\times10^{-15}\\ 3 & -5.166052704859894\times10^{-13}\\ 4 & 2.1919479625883945\times10^{-11}\\ 5 & -6.873605325572918\times10^{-10}\\ 6 & 1.6511874089046065\times10^{-8}\\ 7 & -3.1078571268337856\times10^{-7}\\ 8 & 4.6488830858656685\times10^{-6}\\ 9 & -0.0000557298 \\ 10 & 0.000537438 \\ 11 & -0.00416881 \\ 12 & 0.0259077 \\ 13 & -0.127968 \\ 14 & 0.495971 \\ 15 & -1.47971 \\ 16 & 3.3038 \\ 17 & -5.29036 \\ 18 & 5.67378 \\ 19 & -3.59774 \\ 20 & 1 \\\hline \end{array}

Hacer ese pequeño $10^{-19}$ constante a cero te dará el mismo problema con las raíces porque multiplicar un polinomio por una constante no cambia sus raíces. Lo que hay que tener en cuenta aquí es que las raíces de un polinomio dependen continuamente de los coeficientes pero pueden ser extremadamente sensibles y debes considerar el plano complejo como un todo con la línea real incrustada en él. La recta real es sólo una pequeña parte de todo el plano complejo. La recta real no es nada especial en este contexto. Cambiar los coeficientes hace que las raíces vaguen pero pueden vagar en cualquier dirección en el plano complejo aunque originalmente estuvieran estrictamente en la línea real . No hay nada que limite las raíces a la línea real. Las raíces reales pueden convertirse en complejas o viceversa cambiando ligeramente los coeficientes de un polinomio.

---

James Wilkinson es uno de los analistas numéricos más respetados del siglo XX y su especialidad era idear contraejemplos. Demostró que el problema de encontrar las raíces de un polinomio arbitrario utilizando sus coeficientes es un problema mal condicionado en general.

Presentó un ejemplo concreto, $$p(x)=(x-1)(x-2)...(x-19)(x-20).$$ Las raíces son fáciles de encontrar; $x=1,2,3,...,19,20$ por lo que son bien esperados. Si se expande el polinomio, el coeficiente del $x^{19}$ término es $-210$ . Perturbemos este coeficiente mediante $2^{-23}$ y redondearlo a $210.0000001192$ y llamemos a este nuevo polinomio $q(x)$ . Ocurre lo siguiente:

• El valor de $p(20)=0$ explota hasta $q(20)\approx-6.24949\times10^{17}$ .
• Las raíces en $x=1,2,3,4,5,6$ se mantienen más o menos igual.
• Las raíces en $x=7,8,9$ tienen cambios notables.
• Las siguientes diez raíces en realidad se vuelven complejas (pares, porque los coeficientes siguen siendo reales). Estas diez raíces tienen una parte imaginaria no muy pequeña. La parte imaginaria más pequeña es $\approx 0.643439$ para que decidas lo lejos que está de ser un número real.
• La raíz que estaba en $x=20$ se ha trasladado a $x\approx20.8469$ .

Recuerda, esto es así a pesar de que los coeficientes eran enteros (aunque enteros muy grandes). Las raíces eran todas enteras reales y bien separadas y mira lo que pasó por una pequeña perturbación. Este polinomio es en el que se basa mi respuesta.

Wilkinson presentó otro polinomio. Defina $$q(x)=(x-2^{-1})(x-2^{-2})(x-2^{-3})...(x-2^{-19})(x-2^{-20}).$$ Demostró que este polinomio $q(x)$ es más bien insensible a cambios relativamente grandes en los coeficientes. Por lo tanto, en general, no se puede decir nada en ninguno de los dos sentidos. Eche un vistazo a este página para más detalles y también le insto a que lea sus obras publicadas (como las referencias al final de la página de la wikipedia). Puede que sean un poco difíciles de encontrar, pero merecen totalmente la pena.

---

Addendum (demasiado largo para ser un comentario)

En respuesta al comentario del OP,

Por curiosidad, ¿cómo has calculado las nuevas raíces (para p3) en la tercera tabla? ¿Es un resultado analítico?

la respuesta es que no, no se trata de un resultado analítico. Para estimar numéricamente las raíces de $p_3(x)$ .

Quiero señalar aquí que en el siglo pasado se presentaron muchos métodos nuevos o mejorados. Sabemos bastante sobre polinomios y sus raíces . Pero (todavía) no existe un método numérico único que funcione para todos los polinomios de forma óptima. Siempre se pueden encontrar contraejemplos en los que un método bien conocido sea "lento" o subóptimo para encontrar las raíces de un polinomio. Sin embargo, hay métodos que son mucho mejores que otros.

Uno de los más populares es El método de Brent que es un método híbrido. Brent escribió un libro, " Algoritmos de minimización sin derivadas "pero el libro está agotado. Así que escanearon una copia y la pusieron a disposición del público. aquí . En este libro, se recomienda el capítulo 4, "An Algorithm with Guaranteed Convergence for Finding a Zero of a Function", que describe su método. Su método también ha sido revisado por pares. publicado .

Además, uno de los cofundadores de MATLAB, Cleve Moler tiene una blog (útil en sí mismo) y una vez tuvo un post en tres partes ( un , dos y tres ) describiendo varios algoritmos y cómo funciona fzero de MATLAB. La segunda parte es donde se discute el método de Brent que se implementa en fzero de MATLAB. Dado que el algoritmo de Brent está garantizado para converger (que podría ser lento, pero va a converger), tengo curiosidad por saber por qué estaba teniendo el problema que usted dijo que era. ¿Cómo/por qué se bloqueaba tu aplicación? ¿Fue algo que tú mismo escribiste? Pero entonces yo le aconsejaría en contra de esto. Hay un montón de rutinas enlatadas y no debería haber necesidad de reinventar la rueda. ¿Era fzero de MATLAB lo que fallaba? En ese caso me interesaría mucho conocer esos polinomios. ¿Quizás puedas poner algunos ejemplos aquí? Por último, hay esto libro divertido uno de mis favoritos de todos los tiempos y habla bastante sobre ceros de polinomios y cómo encontrarlos.

---

Apéndice - 72 días después

El OP proporcionó un ejemplo específico de un polinomio con el que tenía un problema. Sólo por curiosidad, quería echarle un vistazo y ver lo que estaba pasando. El OP proporcionó los coeficientes en coma flotante (en hexadecimal). Dado que no puedo decir lo que los coeficientes reales se supone que son, voy a suponer que los coeficientes de punto flotante proporcionados representan los coeficientes exactamente como números racionales. Primero, convierta la forma hexadecimal en fracciones de base diez y luego en decimales sólo para ver qué son.

$$ \begin{array}{|l|l|l|r|r|} \hline &\text{Exponent} & \text{Hex Form} & \text{Fractional Form} & \text{Decimal Form} \\\hline a_6 & 6 & \text{BFAE7873980ADA44} & -\frac{2144171792184977}{36028797018963968} & -0.05951272231 \\ a_5 & 5 & \text{BFD79794C0074EF6} & -\frac{3320294798501755}{9007199254740992} & -0.3686267734 \\ a_4 & 4 & \text{BFE9E4C737C98680} & -\frac{56940771119885}{70368744177664} & -0.8091770258 \\ a_3 & 3 & \text{BFE5502ED16AFAE0} & -\frac{187473016346583}{281474976710656} & -0.6660379496 \\ a_2 & 2 & \text{BF81513E302ABBA0} & -\frac{152325066937821}{18014398509481984} & -0.008455739827 \\ a_1 & 1 & \text{3FC59AE0B4D97164} & \frac{1520316102106201}{9007199254740992} & 0.1687889941 \\ a_0 & 0 & \text{BC80000000000000} & \frac{1}{36028797018963968} & 2.775557561562\times10^{-17} \\ \hline \end{array} $$

Utilizando la forma fraccionaria exacta de los coeficientes, defina los polinomios $$p(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6$$ $$q(x)=a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6$$ donde $q(x)$ es sólo $p(x)$ con el término constante a cero. Después de mirarlos, sé que todas las raíces son irracionales, excepto la raíz trivial $x=0$ para $q(x)$ . Además, no lo sé con seguridad, pero sospecho que ambos polinomios no son resolubles en los radicales (comprobar este y este si el lector no sabe lo que esto significa) por lo que no hay soluciones en los radicales. Ahora no nos queda más remedio que recurrir a métodos numéricos.

La imagen de arriba muestra ambos $p(x)$ y $q(x)$ . Mira los límites de los ejes y las escalas. Puedo ver las tres raíces reales simples distintas con bastante facilidad (las tres raíces de más a la derecha). A la izquierda, la gráfica es muy plana cerca de las $x$ -pero seguro que hay al menos una raíz. Podría ser una sola raíz real con multiplicidad tres o podrían ser tres raíces reales distintas muy próximas entre sí o cualquier otra combinación intermedia. Yo diría que no hay raíces complejas. Observa cómo ambos polinomios son indistinguibles entre sí. Sólo vemos una única curva.

Esta segunda imagen, arriba, amplía esa región plana. La tercera raíz simple (la de la derecha en este gráfico) es aún más obvia ahora. Pero seguimos sin saber qué ocurre con las otras tres raíces de la izquierda. El gráfico sigue siendo demasiado plano. Observa que seguimos sin poder distinguir entre $p(x)$ y $q(x)$ . Esto significa que para este polinomio en concreto, el polinomio que dio lugar a esta pregunta, poner el término constante a cero en realidad no cambia mucho las raíces . Verificaremos esto ahora.

Partiendo de los coeficientes exactos y llevando un centenar de dígitos a lo largo de los cálculos para mayor precisión y exactitud, obtuve las siguientes raíces.

$$ \begin{array}{|r|r|r|}\hline \text{Roots of $p(x)$} & \text{Roots of $q(x)$} & \frac{|\text{Roots}(p(x))-\text{Roots}(q(x))|}{|\text{Roots}(p(x))|}\cdot100\%\\ \hline -1.7613269 & -1.7613263 & 0.00003277 \\ -1.3071486 & -1.3071486 & 1.70941691\times10^{-13} \\ -1.64439487\times10^{-16} & 0 & 100 \\ 0.39708223 & 0.39708223 & 1.72600660\times10^{-14} \\ -1.7613452-0.0000106 i & -1.7613455-0.0000111 i & 0.00003276 \\ -1.7613452+0.0000106 i & -1.7613455+0.0000111 i & 0.00003276 \\\hline \end{array} $$

La primera columna muestra las raíces de $p(x)$ . La segunda columna muestra las raíces de la perturbada $q(x)$ . La tercera columna muestra la diferencia relativa de las raíces en porcentaje. El valor absoluto de la tercera columna es la norma habitual en $\mathbb{R}$ o $\mathbb{C}$ según proceda. Los cambios relativos son pequeños para que pueda ver que ninguna de las raíces ha cambiado realmente de forma significativa.

La magnitud de todo el vector diferencia de las raíces es $$||\text{Roots}(p(x))-\text{Roots}(q(x))||_2=9.995367\times10^{-7}$$ y de hecho las raíces cambiaron muy poco . Todo esto es relativo porque otra perspectiva es que un cambio del orden $10^{-17}$ al vector de coeficientes hizo que la magnitud del vector de raíces cambiara en casi $10^{-6}$ que es de once órdenes de magnitud. Esto es gigantesco desde otro punto de vista. La función vectorial que asigna los coeficientes de un polinomio a sus raíces es, en efecto, continua. Pero ser continua no restringe el gradiente de ninguna manera. Puede ser grande o pequeño. Y en este caso, el gradiente de esta función vectorial resulta ser muy grande en este punto concreto de su dominio.

Answer 2

Si $r$ es una raíz, pensada como una función de $a_0$ entonces por diferenciación implícita obtenemos $$ \dfrac{dr}{da_0} = - \frac{1}{p'(r)}$$

Las raíces que se verán fuertemente afectadas por un pequeño cambio en $a_0$ son aquellos para los que $|p'(r)|$ es pequeño - en particular, las raíces múltiples, que son aquellas en las que $p'(r) = 0$ .

EDIT: Por otro lado: dado cualquier contorno cerrado simple $\Gamma$ tal que ninguna raíz esté en $\Gamma$ , dejemos que $\eta = \inf_{z \in \Gamma} |p(z)|$ . A continuación, cualquier cambio en $a_0$ por menos de $\eta$ en valor absoluto dejará constante el número de raíces dentro de $\Gamma$ contados por multiplicidad.

Answer 3

El dictado general es que las raíces del polinomio varían continuamente con los coeficientes, pero no analíticamente.

Lo típico que hace que las "trayectorias" de las raíces sigan curvas que no son analíticas es lo que le ocurre a una raíz doble cuando llega al origen. Es decir, consideremos $x^2 = \varepsilon$ de modo que valores positivos pequeños de $\varepsilon$ dan un par de raíces reales distintas (positivas/negativas) que se convierten en una raíz doble en $\varepsilon = 0$ . Si $\varepsilon$ se vuelven negativas pequeñas, las dos raíces que se unieron en cero salen volando como un par conjugado, es decir, siguiendo una trayectoria perpendicular a la trayectoria que unió al par como una raíz doble.