Algoritmo de Jenkins-Traub

Partiendo del polinomio actual P ( X ) de grado n , el objetivo es calcular la raíz más pequeña.${\displaystyle \alpha }$de P(x) . El polinomio se puede entonces dividir en un factor lineal y el factor polinómico restante.$${\displaystyle P(X)=(X-\alpha ){\bar {H}}(X)}$$Otros métodos de búsqueda de raíces se centran principalmente en mejorar la raíz y, por lo tanto, el primer factor. La idea principal del método Jenkins-Traub es mejorar gradualmente el segundo factor.

Para ello, se construye una secuencia de los llamados polinomios H. Estos polinomios son todos de grado n − 1 y se supone que convergen al factor  ${\displaystyle {\bar {H}}(X)}$de P ( X ) que contiene (los factores lineales de) todas las raíces restantes. La secuencia de polinomios H aparece en dos variantes, una variante no normalizada que permite una comprensión teórica sencilla y una variante normalizada de${\displaystyle {\bar {H}}}$polinomios que mantienen los coeficientes en un rango numéricamente razonable. La construcción de los polinomios H${\displaystyle \left(H^{(\lambda )}(z)\right)_{\lambda =0,1,2,\dots }}$está guiado por una secuencia de números complejos${\displaystyle (s_{\lambda })_{\lambda =0,1,2,\dots }}$denominados desplazamientos. Estos desplazamientos dependen, al menos en la tercera etapa, de los polinomios H anteriores. Los polinomios H se definen como la solución a la recursión implícita. $${\displaystyle H^{(0)}(z)=P^{\prime }(z)}$$y$${\displaystyle (X-s_{\lambda })\cdot H^{(\lambda +1)}(X)\equiv H^{(\lambda )}(X){\pmod {P(X)}}\ .}$$ Una solución directa a esta ecuación implícita es $${\displaystyle H^{(\lambda +1)}(X)={\frac {1}{X-s_{\lambda }}}\cdot \left(H^{(\lambda )}(X)-{\frac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}P(X)\right)\,,}$$ donde la división polinómica es exacta.

Algorítmicamente, se usaría la división larga por el factor lineal como en el esquema de Horner o la regla de Ruffini para evaluar los polinomios en${\displaystyle s_{\lambda }}$y obtener los cocientes al mismo tiempo. Con los cocientes resultantes p ( X ) y h ( X ) como resultados intermedios , se obtiene el siguiente polinomio H como$${\displaystyle \left.{\begin{aligned}P(X)&=p(X)\cdot (X-s_{\lambda })+P(s_{\lambda })\\H^{(\lambda )}(X)&=h(X)\cdot (X-s_{\lambda })+H^{(\lambda )}(s_{\lambda })\\\end{aligned}}\right\}\implies H^{(\lambda +1)}(z)=h(z)-{\frac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}p(z).}$$ Dado que el coeficiente de grado más alto se obtiene de P(X) , el coeficiente principal de${\displaystyle H^{(\lambda +1)}(X)}$es${\displaystyle -{\tfrac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}}$. Si se divide esto, el polinomio H normalizado es$${\displaystyle {\begin{aligned}{\bar {H}}^{(\lambda +1)}(X)&={\frac {1}{X-s_{\lambda }}}\cdot \left(P(X)-{\frac {P(s_{\lambda })}{H^{(\lambda )}(s_{\lambda })}}H^{(\lambda )}(X)\right)\\[1em]&={\frac {1}{X-s_{\lambda }}}\cdot \left(P(X)-{\frac {P(s_{\lambda })}{{\bar {H}}^{(\lambda )}(s_{\lambda })}}{\bar {H}}^{(\lambda )}(X)\right)\,.\end{aligned}}}$$

Dejar${\displaystyle \alpha _{1},\dots ,\alpha _{n}}$sean las raíces de P ( X ). Los llamados factores de Lagrange de P(X) son los cofactores de estas raíces, $${\displaystyle P_{m}(X)={\frac {P(X)-P(\alpha _{m})}{X-\alpha _{m}}}.}$$ Si todas las raíces son diferentes, entonces los factores de Lagrange forman una base del espacio de polinomios de grado como máximo n − 1. Mediante el análisis del procedimiento de recursión se encuentra que los polinomios H tienen la representación de coordenadas   $${\displaystyle H^{(\lambda )}(X)=\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}(\alpha _{m}-s_{\kappa })\right]^{-1}\,P_{m}(X)\ .}$$ Cada factor de Lagrange tiene coeficiente principal 1, de modo que el coeficiente principal de los polinomios H es la suma de los coeficientes. Los polinomios H normalizados son, por lo tanto, $${\displaystyle {\bar {H}}^{(\lambda )}(X)={\frac {\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}(\alpha _{m}-s_{\kappa })\right]^{-1}\,P_{m}(X)}{\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}(\alpha _{m}-s_{\kappa })\right]^{-1}}}={\frac {P_{1}(X)+\sum _{m=2}^{n}\left[\prod _{\kappa =0}^{\lambda -1}{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{m}-s_{\kappa }}}\right]\,P_{m}(X)}{1+\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{m}-s_{\kappa }}}\right]}}\ .}$$

Si la condición${\displaystyle |\alpha _{1}-s_{\kappa }|<\min {}_{m=2,3,\dots ,n}|\alpha _{m}-s_{\kappa }|}$Se cumple para casi todas las iteraciones, los polinomios H normalizados convergerán al menos geométricamente hacia${\displaystyle P_{1}(X)}$.

Bajo la condición de que $${\displaystyle |\alpha _{1}|<|\alpha _{2}|=\min {}_{m=2,3,\dots ,n}|\alpha _{m}|}$$ uno obtiene las estimaciones asintóticas para

• etapa 1:$${\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\left|{\frac {\alpha _{1}}{\alpha _{2}}}\right|^{\lambda }\right).}$$
• para la etapa 2, si s está lo suficientemente cerca de${\displaystyle \alpha _{1}}$:$${\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\left|{\frac {\alpha _{1}}{\alpha _{2}}}\right|^{M}\cdot \left|{\frac {\alpha _{1}-s}{\alpha _{2}-s}}\right|^{\lambda -M}\right)}$$y$${\displaystyle s-{\frac {P(s)}{{\bar {H}}^{(\lambda )}(s)}}=\alpha _{1}+O\left(\ldots \cdot |\alpha _{1}-s|\right).}$$
• y para la etapa 3:$${\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\prod _{\kappa =0}^{\lambda -1}\left|{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{2}-s_{\kappa }}}\right|\right)}$$y$${\displaystyle s_{\lambda +1}=s_{\lambda }-{\frac {P(s)}{{\bar {H}}^{(\lambda +1)}(s_{\lambda })}}=\alpha _{1}+O\left(\prod _{\kappa =0}^{\lambda -1}\left|{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{2}-s_{\kappa }}}\right|\cdot {\frac {|\alpha _{1}-s_{\lambda }|^{2}}{|\alpha _{2}-s_{\lambda }|}}\right)}$$dando lugar a un orden de convergencia superior al cuadrático de${\displaystyle \phi ^{2}=1+\phi \approx 2.618}$, dónde${\displaystyle \phi ={\tfrac {1}{2}}(1+{\sqrt {5}})}$es la proporción áurea .

Todas las etapas del algoritmo complejo de Jenkins-Traub pueden representarse como el problema de álgebra lineal de determinar los valores propios de una matriz especial. Esta matriz es la representación de coordenadas de una aplicación lineal en el espacio n -dimensional de polinomios de grado n − 1 o menor. La idea principal de esta aplicación es interpretar la factorización.   $${\displaystyle P(X)=(X-\alpha _{1})\cdot P_{1}(X)}$$ con una raíz${\displaystyle \alpha _{1}\in \mathbb {C} }$y${\displaystyle P_{1}(X)=P(X)/(X-\alpha _{1})}$el factor restante de grado n − 1 como la ecuación del vector propio para la multiplicación con la variable X , seguido del cálculo del resto con el divisor P ( X ),   $${\displaystyle M_{X}(H)=(X\cdot H(X)){\bmod {P}}(X)\,.}$$ Esto transforma polinomios de grado como máximo n − 1 en polinomios de grado como máximo n − 1. Los valores propios de esta transformación son las raíces de P ( X ), ya que la ecuación del vector propio es:     $${\displaystyle 0=(M_{X}-\alpha \cdot id)(H)=((X-\alpha )\cdot H){\bmod {P}}\,,}$$ lo cual implica que${\displaystyle (X-\alpha )\cdot H=C\cdot P(X)}$, eso es,${\displaystyle (X-\alpha )}$es un factor lineal de P ( X ). En la base monomial, el mapeo lineal${\displaystyle M_{X}}$está representada por una matriz compañera del polinomio P , como $${\displaystyle M_{X}(H)=\sum _{m=0}^{n-1}H_{m}X^{m+1}-H_{n-1}\left(X^{n}+\sum _{m=0}^{n-1}a_{m}X^{m}\right)=\sum _{m=1}^{n-1}(H_{m-1}-a_{m}H_{n-1})X^{m}-a_{0}H_{n-1}\,,}$$La matriz de transformación resultante es $${\displaystyle A={\begin{pmatrix}0&0&\dots &0&-a_{0}\\1&0&\dots &0&-a_{1}\\0&1&\dots &0&-a_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\dots &1&-a_{n-1}\end{pmatrix}}\,.}$$ A esta matriz se le aplica la iteración de potencia inversa en sus tres variantes: sin desplazamiento, desplazamiento constante y desplazamiento de Rayleigh generalizado, en las tres etapas del algoritmo. Resulta más eficiente realizar las operaciones de álgebra lineal mediante aritmética polinómica que mediante operaciones matriciales; sin embargo, las propiedades de la iteración de potencia inversa se mantienen.