Método de Graeffe

En matemáticas , el método de Graeffe o método de Dandelin - Lobachevsky - Graeffe es un algoritmo para hallar todas las raíces de un polinomio . Fue desarrollado independientemente por Germinal Pierre Dandelin en 1826 y Lobachevsky en 1834. En 1837, Karl Heinrich Gräffe también descubrió la idea principal del método. ^{[ 1 ]} El método separa las raíces de un polinomio elevándolas al cuadrado repetidamente. Esta elevación al cuadrado de las raíces se realiza implícitamente, es decir, trabajando únicamente sobre los coeficientes del polinomio. Finalmente, se utilizan las fórmulas de Viète para aproximar las raíces.

Sea p ( x ) un polinomio de grado n

${\displaystyle p(x)=(x-x_{1})\cdots (x-x_{n}).}$

Entonces

${\displaystyle p(-x)=(-1)^{n}(x+x_{1})\cdots (x+x_{n}).}$

Sea q ( x ) el polinomio que tiene los cuadrados${\displaystyle x_{1}^{2},\cdots ,x_{n}^{2}}$como sus raíces,

${\displaystyle q(x)=\left(x-x_{1}^{2}\right)\cdots \left(x-x_{n}^{2}\right).}$

Entonces podemos escribir:

${\displaystyle {\begin{aligned}q(x^{2})&=\left(x^{2}-x_{1}^{2}\right)\cdots \left(x^{2}-x_{n}^{2}\right)\\&=(x-x_{1})(x+x_{1})\cdots (x-x_{n})(x+x_{n})\\&=\left\{(x-x_{1})\cdots (x-x_{n})\right\}\times \left\{(x+x_{1})\cdots (x+x_{n})\right\}\\&=p(x)\times \left\{(-1)^{n}(-x-x_{1})\cdots (-x-x_{n})\right\}\\&=p(x)\times \left\{(-1)^{n}p(-x)\right\}\\&=(-1)^{n}p(x)p(-x)\end{aligned}}}$

Ahora se puede calcular q ( x ) mediante operaciones algebraicas sobre los coeficientes del polinomio p ( x ) únicamente. Sea:

${\displaystyle {\begin{aligned}p(x)&=x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}\\q(x)&=x^{n}+b_{1}x^{n-1}+\cdots +b_{n-1}x+b_{n}\end{aligned}}}$

entonces los coeficientes están relacionados por

${\displaystyle b_{k}=(-1)^{k}a_{k}^{2}+2\sum _{j=0}^{k-1}(-1)^{j}\,a_{j}a_{2k-j},\qquad a_{0}=b_{0}=1.}$

Graeffe observó que si se separa p ( x ) en sus partes impares y pares:

${\displaystyle p(x)=p_{e}\left(x^{2}\right)+xp_{o}\left(x^{2}\right),}$

Entonces se obtiene una expresión algebraica simplificada para q ( x ) :

${\displaystyle q(x)=(-1)^{n}\left(p_{e}(x)^{2}-xp_{o}(x)^{2}\right).}$

Esta expresión implica elevar al cuadrado dos polinomios de grado tan solo la mitad, y por lo tanto se utiliza en la mayoría de las implementaciones del método.

Al iterar este procedimiento varias veces, se separan las raíces según sus magnitudes. Repitiéndolo k veces se obtiene un polinomio de grado n :

${\displaystyle q^{k}(y)=y^{n}+{a^{k}}_{1}\,y^{n-1}+\cdots +{a^{k}}_{n-1}\,y+{a^{k}}_{n}\,}$

con raíces

${\displaystyle y_{1}=x_{1}^{2^{k}},\,y_{2}=x_{2}^{2^{k}},\,\dots ,\,y_{n}=x_{n}^{2^{k}}.}$

Si las magnitudes de las raíces del polinomio original estuvieran separadas por algún factor${\displaystyle \rho >1}$, eso es,${\displaystyle |x_{k}|\geq \rho |x_{k+1}|}$, entonces las raíces de la k -ésima iteración están separadas por un factor de rápido crecimiento.

${\displaystyle \rho ^{2^{k}}\geq 1+2^{k}(\rho -1)}$.

A continuación se utilizan las relaciones de Vieta

${\displaystyle {\begin{aligned}a_{\;1}^{k}&=-(y_{1}+y_{2}+\cdots +y_{n})\\a_{\;2}^{k}&=y_{1}y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n}\\&\;\vdots \\a_{\;n}^{k}&=(-1)^{n}(y_{1}y_{2}\cdots y_{n}).\end{aligned}}}$

Si las raíces${\displaystyle x_{1},\dots ,x_{n}}$están suficientemente separados, digamos por un factor.${\displaystyle \rho >1}$,${\displaystyle |x_{m}|\geq \rho |x_{m+1}|}$, luego los poderes iterados${\displaystyle y_{1},y_{2},...,y_{n}}$de las raíces están separadas por el factor${\displaystyle \rho ^{2^{k}}}$, que rápidamente se vuelve muy grande.

Los coeficientes del polinomio iterado pueden entonces aproximarse mediante su término principal,

${\displaystyle a_{\;1}^{k}\approx -y_{1}}$

${\displaystyle a_{\;2}^{k}\approx y_{1}y_{2}}$etcétera,

reticente

${\displaystyle y_{1}\approx -a_{\;1}^{k},\;y_{2}\approx -a_{\;2}^{k}/a_{\;1}^{k},\;\dots \;y_{n}\approx -a_{\;n}^{k}/a_{\;n-1}^{k}.}$

Finalmente, se utilizan logaritmos para hallar los valores absolutos de las raíces del polinomio original. Estas magnitudes por sí solas ya son útiles para generar puntos de partida significativos para otros métodos de búsqueda de raíces.

Para obtener también el ángulo de estas raíces, se ha propuesto multitud de métodos, siendo el más sencillo calcular sucesivamente la raíz cuadrada de una raíz (posiblemente compleja) de${\displaystyle q^{m}(y)}$, m que varía de k a 1, y probando cuál de las dos variantes de signo es una raíz de${\displaystyle q^{m-1}(x)}$. Antes de continuar a las raíces de${\displaystyle q^{m-2}(x)}$, podría ser necesario mejorar numéricamente la precisión de las aproximaciones de raíz para${\displaystyle q^{m-1}(x)}$, por ejemplo, mediante el método de Newton .

El método de Graeffe funciona mejor para polinomios con raíces reales simples, aunque puede adaptarse para polinomios con raíces y coeficientes complejos, y raíces con mayor multiplicidad. Por ejemplo, se ha observado ^{[ 2 ]} que para una raíz${\displaystyle x_{\ell +1}=x_{\ell +2}=\dots =x_{\ell +d}}$con multiplicidad d , las fracciones

${\displaystyle \left|{\frac {(a_{\;\ell +i}^{m-1})^{2}}{a_{\;\ell +i}^{m}}}\right|}$tienden a${\displaystyle {\binom {d}{i}}}$

para${\displaystyle i=0,1,\dots ,d}$Esto permite estimar la estructura de multiplicidad del conjunto de raíces.

Desde un punto de vista numérico, este método resulta problemático, ya que los coeficientes de los polinomios iterados abarcan rápidamente varios órdenes de magnitud, lo que implica graves errores numéricos. Un segundo inconveniente, aunque menor, es que muchos polinomios diferentes dan lugar a las mismas iteraciones de Graeffe.

Este método reemplaza los números por series de potencias truncadas de grado 1, también conocidas como números duales . Simbólicamente, esto se logra introduciendo un "infinitesimal algebraico".${\displaystyle \varepsilon }$con la propiedad definitoria${\displaystyle \varepsilon ^{2}=0}$. Entonces el polinomio ${\displaystyle p(x+\varepsilon )=p(x)+\varepsilon \,p'(x)}$tiene raíces${\displaystyle x_{m}-\varepsilon }$, con poderes

${\displaystyle (x_{m}-\varepsilon )^{2^{k}}=x_{m}^{2^{k}}-\varepsilon \,{2^{k}}\,x_{m}^{2^{k}-1}=y_{m}+\varepsilon \,{\dot {y}}_{m}.}$

Por lo tanto, el valor de${\displaystyle x_{m}}$se obtiene fácilmente como fracción${\displaystyle x_{m}=-{\tfrac {2^{k}\,y_{m}}{{\dot {y}}_{m}}}.}$

Este tipo de cálculo con infinitesimales es fácil de implementar, de forma análoga al cálculo con números complejos. Si se asumen coordenadas complejas o un desplazamiento inicial de un número complejo elegido al azar, todas las raíces del polinomio serán distintas y, por consiguiente, recuperables mediante la iteración.

Todo polinomio puede escalarse en dominio y rango de tal manera que en el polinomio resultante el primer y el último coeficiente tengan tamaño uno. Si el tamaño de los coeficientes internos está acotado por M , entonces el tamaño de los coeficientes internos después de una etapa de la iteración de Graeffe está acotado por${\displaystyle nM^{2}}$Después de k etapas se obtiene el límite${\displaystyle n^{2^{k}-1}M^{2^{k}}}$para los coeficientes internos.

Para superar el límite que supone el crecimiento de las potencias, Malajovich-Zubelli proponen representar los coeficientes y los resultados intermedios en la k -ésima etapa del algoritmo mediante una forma polar escalada.

${\displaystyle c=\alpha \,e^{-2^{k}\,r},}$

dónde${\displaystyle \alpha ={\frac {c}{|c|}}}$es un número complejo de longitud unitaria y${\displaystyle r=-2^{-k}\log |c|}$es un real positivo. Separando la energía${\displaystyle 2^{k}}$En el exponente, el valor absoluto de c se reduce a la raíz diádica correspondiente. Dado que esto preserva la magnitud de los coeficientes iniciales (o su representación), este proceso se denominó renormalización.

La multiplicación de dos números de este tipo es sencilla, mientras que la suma se realiza después de la factorización.${\displaystyle c_{3}=c_{1}+c_{2}=|c_{1}|\cdot \left(\alpha _{1}+\alpha _{2}{\tfrac {|c_{2}|}{|c_{1}|}}\right)}$, dónde${\displaystyle c_{1}}$se elige como el mayor de los dos números, es decir,${\displaystyle r_{1}<r_{2}}$. De este modo

${\displaystyle \alpha _{3}={\tfrac {s}{|s|}}}$y${\displaystyle r_{3}=r_{1}+2^{-k}\,\log {|s|}}$con${\displaystyle s=\alpha _{1}+\alpha _{2}\,e^{2^{k}(r_{1}-r_{2})}.}$

Los coeficientes${\displaystyle a_{0},a_{1},\dots ,a_{n}}$de la etapa final k de la iteración de Graeffe, para algún valor razonablemente grande de k , están representados por pares${\displaystyle (\alpha _{m},r_{m})}$,${\displaystyle m=0,\dots ,n}$Al identificar las esquinas de la envolvente convexa del conjunto de puntos${\displaystyle \{(m,r_{m}):\;m=0,\dots ,n\}}$Se pueden determinar las multiplicidades de las raíces del polinomio. Combinando esta renormalización con la iteración tangente, se pueden extraer directamente de los coeficientes en los vértices de la envolvente las raíces del polinomio original.

• Algoritmo de búsqueda de raíces

• Weisstein, Eric W. "El método de Graeffe" . MundoMatemático .
• Malajovich, Gregorio; Zubelli, Jorge P. (2001). "Iteración tangente de Graeffe". Matemática numérica . 89 (4): 749– 782. CiteSeerX 10.1.1.44.3611 . doi : 10.1007/s002110100278 . S2CID 100025 .