El método de Graeffe

Algoritmo para encontrar raíces polinómicas

En matemáticas , el método de Graeffe o método de Dandelin-Lobachesky-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 de forma implícita, es decir, trabajando únicamente sobre los coeficientes del polinomio. Finalmente, se utilizan las fórmulas de Viète para aproximar las raíces.

Iteración de Dandelin-Graeffe

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 como raíces los cuadrados, ${\displaystyle x_{1}^{2},\cdots ,x_{n}^{2}}$

${\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 q ( x ) se puede calcular 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 uno separa p ( x ) en sus partes pares e impares:

${\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 el cuadrado de dos polinomios de sólo la mitad del grado y, por lo tanto, se utiliza en la mayoría de las implementaciones del método.

Al repetir este procedimiento varias veces, se separan las raíces con respecto a sus magnitudes. Al repetir 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 estaban separadas por algún factor , es decir, , entonces las raíces del k -ésimo iterado están separadas por un factor de rápido crecimiento ${\displaystyle \rho >1}$ ${\displaystyle |x_{k}|\geq \rho |x_{k+1}|}$

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

El método clásico de Graeffe

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 están suficientemente separadas, digamos por un factor , entonces las potencias iteradas de las raíces están separadas por el factor , que rápidamente se vuelve muy grande. ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle \rho >1}$ ${\displaystyle |x_{m}|\geq \rho |x_{m+1}|}$ ${\displaystyle y_{1},y_{2},...,y_{n}}$ ${\displaystyle \rho ^{2^{k}}}$

Los coeficientes del polinomio iterado pueden entonces aproximarse por 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}.}$

Por último, se utilizan los 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 han propuesto una multitud de métodos, siendo el más simple calcular sucesivamente la raíz cuadrada de una raíz (posiblemente compleja) de , m que va de k a 1, y comprobar cuál de las dos variantes de signo es una raíz de . Antes de continuar con las raíces de , podría ser necesario mejorar numéricamente la precisión de las aproximaciones de raíces para , por ejemplo mediante el método de Newton . ${\displaystyle q^{m}(y)}$ ${\displaystyle q^{m-1}(x)}$ ${\displaystyle q^{m-2}(x)}$ ${\displaystyle q^{m-1}(x)}$

El método de Graeffe funciona mejor para polinomios con raíces reales simples, aunque se puede adaptar 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 con multiplicidad d , las fracciones ${\displaystyle x_{\ell +1}=x_{\ell +2}=\dots =x_{\ell +d}}$

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

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

Desde un punto de vista numérico, este método es problemático, ya que los coeficientes de los polinomios iterados abarcan muy rápidamente muchos órdenes de magnitud, lo que implica graves errores numéricos. Una segunda preocupación, aunque menor, es que muchos polinomios diferentes conducen a las mismas iteraciones de Graeffe.

Método de Graeffe tangencial

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" con la propiedad definitoria . Entonces el polinomio tiene raíces , con potencias ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon ^{2}=0}$ ${\displaystyle p(x+\varepsilon )=p(x)+\varepsilon \,p'(x)}$ ${\displaystyle x_{m}-\varepsilon }$

${\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 se obtiene fácilmente como fracción ${\displaystyle x_{m}}$ ${\displaystyle x_{m}=-{\tfrac {2^{k}\,y_{m}}{{\dot {y}}_{m}}}.}$

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

Renormalización

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

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

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

donde es un número complejo de longitud unitaria y es un real positivo. Al descomponer la potencia en el exponente, se reduce el valor absoluto de c a la raíz diádica correspondiente. Como esto preserva la magnitud de los coeficientes iniciales (la representación de los mismos), este proceso se denominó renormalización. ${\displaystyle \alpha ={\frac {c}{|c|}}}$ ${\displaystyle r=-2^{-k}\log |c|}$ ${\displaystyle 2^{k}}$

La multiplicación de dos números de este tipo es sencilla, mientras que la suma se realiza siguiendo la factorización , donde se elige como el mayor de ambos números, es decir, . Por lo tanto ${\displaystyle c_{3}=c_{1}+c_{2}=|c_{1}|\cdot \left(\alpha _{1}+\alpha _{2}{\tfrac {|c_{2}|}{|c_{1}|}}\right)}$ ${\displaystyle c_{1}}$ ${\displaystyle r_{1}<r_{2}}$

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

Los coeficientes de la etapa final k de la iteración de Graeffe, para un valor razonablemente grande de k , se representan mediante pares , . Al identificar los vértices de la envolvente convexa del conjunto de puntos , se pueden determinar las multiplicidades de las raíces del polinomio. Al combinar 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. ${\displaystyle a_{0},a_{1},\dots ,a_{n}}$ ${\displaystyle (\alpha _{m},r_{m})}$ ${\displaystyle m=0,\dots ,n}$ ${\displaystyle \{(m,r_{m}):\;m=0,\dots ,n\}}$

Véase también

• Algoritmo de búsqueda de raíces

Referencias

1. Householder, Alston Scott (1959). "Dandelin, Lobačevskiǐ o Graeffe". The American Mathematical Monthly . 66 (6): 464–466. doi :10.2307/2310626. JSTOR  2310626.
2. Best, GC (1949). "Notas sobre el método Graeffe de raíz cuadrada". The American Mathematical Monthly . 56 (2): 91–94. doi :10.2307/2306166. JSTOR  2306166.

• 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.