Algoritmo de Lehmer-Schur

En matemáticas , el algoritmo de Lehmer-Schur (llamado así por Derrick Henry Lehmer e Issai Schur ) es un algoritmo de búsqueda de raíces para polinomios complejos , que extiende la idea de encerrar raíces como en el método de bisección unidimensional al plano complejo. Utiliza la prueba de Schur-Cohn para comprobar la presencia o ausencia de raíces en discos cada vez más pequeños.

Algoritmo de Schur-Cohn

Este algoritmo permite encontrar la distribución de las raíces de un polinomio complejo con respecto al círculo unitario en el plano complejo. ^{[1] [2] [3]} Se basa en dos polinomios auxiliares, introducidos por Schur. ^[4]

Para un polinomio complejo de grado, su polinomio adjunto recíproco está definido por y su transformada de Schur por ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p^{*}}$ ${\displaystyle p^{*}(z)=z^{n}{\overline {p({\bar {z}}^{-1})}}}$ ${\displaystyle Tp}$

${\displaystyle Tp={\overline {p(0)}}p-{\overline {p^{*}(0)}}p^{*},}$

donde una barra denota conjugación compleja .

Entonces, si es con , entonces , con los términos cero iniciales , si los hay, se eliminan. Por lo tanto, los coeficientes de pueden expresarse directamente en los de y, dado que uno o más coeficientes principales se cancelan, tiene un grado menor que . Las raíces de , y están relacionadas de la siguiente manera. ${\displaystyle p(z)=a_{n}z^{n}+\cdots +a_{1}z+a_{0}}$ ${\displaystyle a_{n}\neq 0}$ ${\displaystyle p^{*}(z)={\bar {a}}_{0}z^{n}+{\bar {a}}_{1}z^{n-1}+\cdots +{\bar {a}}_{n}}$ ${\displaystyle Tp}$ ${\displaystyle p}$ ${\displaystyle Tp}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p^{*}}$ ${\displaystyle Tp}$

Lema

Sea un polinomio complejo y . ${\displaystyle p}$ ${\displaystyle \delta =(Tp)(0)}$

• Las raíces de , incluidas sus multiplicidades , son las imágenes bajo inversión en el círculo unitario de las raíces distintas de cero de . ${\displaystyle p^{*}}$ ${\displaystyle p}$
• Si , entonces , y comparten raíces en el círculo unitario, incluidas sus multiplicidades. ${\displaystyle \delta \neq 0}$ ${\displaystyle p,\,p^{*}}$ ${\displaystyle Tp}$
• Si , entonces y tienen el mismo número de raíces dentro del círculo unitario. ${\displaystyle \delta >0}$ ${\displaystyle p}$ ${\displaystyle Tp}$
• Si , entonces y tienen el mismo número de raíces dentro del círculo unitario. ${\displaystyle \delta <0}$ ${\displaystyle p^{*}}$ ${\displaystyle Tp}$

Prueba

Para nosotros y, en particular, para . También implica . De esto y de las definiciones anteriores se siguen las dos primeras afirmaciones. Las otras dos afirmaciones son consecuencia del teorema de Rouché aplicado sobre el círculo unitario a las funciones y , donde es un polinomio que tiene como raíces las raíces de sobre el círculo unitario, con las mismas multiplicidades. □ ${\displaystyle z\neq 0}$ ${\displaystyle p^{*}(z)=z^{n}{\overline {p(z/|z|^{2})}}}$ ${\displaystyle |p^{*}(z)|=|p(z)|}$ ${\displaystyle |z|=1}$ ${\displaystyle \delta \neq 0}$ ${\displaystyle |p(0)|\neq |p^{*}(0)|}$ ${\displaystyle {\overline {p(0)}}p(z)/r(z)}$ ${\displaystyle -{\overline {p^{*}(0)}}p^{*}(z)/r(z)}$ ${\displaystyle r}$ ${\displaystyle p}$

Para una representación más accesible del lema, sea , y denote el número de raíces dentro, dentro y fuera del círculo unitario, respectivamente, y de manera similar para . Además, sea la diferencia de grado de y . Entonces el lema implica que si y si (obsérvese el intercambio de y ). ${\displaystyle n_{p}^{-},n_{p}^{0}}$ ${\displaystyle n_{p}^{+}}$ ${\displaystyle p}$ ${\displaystyle Tp}$ ${\displaystyle d}$ ${\displaystyle p}$ ${\displaystyle Tp}$ ${\displaystyle (n_{p}^{-},\;n_{p}^{0},\;n_{p}^{+})=(n_{Tp}^{-},\;n_{Tp}^{0},\;n_{Tp}^{+}+d)}$ ${\displaystyle \delta >0}$ ${\displaystyle (n_{p}^{-},\;n_{p}^{0},\;n_{p}^{+})=(n_{Tp}^{+}+d,\;n_{Tp}^{0},\;n_{Tp}^{-})}$ ${\displaystyle \delta <0}$ ${\displaystyle ^{+}}$ ${\displaystyle ^{-}}$

Ahora considere la secuencia de polinomios , donde y . La aplicación de lo anterior a cada par de miembros consecutivos de esta secuencia da el siguiente resultado. ${\displaystyle T^{k}p}$ ${\displaystyle (k=0,1,\ldots )}$ ${\displaystyle T^{0}p=p}$ ${\displaystyle T^{k+1}p=T(T^{k}p)}$

Teorema[Prueba de Schur-Cohn]

Sea un polinomio complejo con y sea el número más pequeño tal que . Además, dejemos por y por . ${\displaystyle p}$ ${\displaystyle Tp\neq 0}$ ${\displaystyle K}$ ${\displaystyle T^{K+1}p=0}$ ${\displaystyle \delta _{k}=(T^{k}p)(0)}$ ${\displaystyle k=1,\ldots ,K}$ ${\displaystyle d_{k}=\deg T^{k}p}$ ${\displaystyle k=0,\ldots ,K}$

• Todas las raíces de se encuentran dentro del círculo unitario si y sólo si ${\displaystyle p}$

${\displaystyle \delta _{1}<0}$, Para y . ${\displaystyle \delta _{k}>0}$ ${\displaystyle k=2,\ldots ,K}$ ${\displaystyle d_{K}=0}$

• Todas las raíces de se encuentran fuera del círculo unitario si y sólo si ${\displaystyle p}$

${\displaystyle \delta _{k}>0}$Para y . ${\displaystyle k=1,\ldots ,K}$ ${\displaystyle d_{K}=0}$

• Si y si para (en orden creciente) y de otra manera, entonces no tiene raíces en el círculo unitario y el número de raíces dentro del círculo unitario es ${\displaystyle d_{K}=0}$ ${\displaystyle \delta _{k}<0}$ ${\displaystyle k=k_{0},k_{1}\ldots k_{m}}$ ${\displaystyle \delta _{k}>0}$ ${\displaystyle p}$ ${\displaystyle p}$

${\displaystyle \sum _{i=0}^{m}(-1)^{i}d_{k_{i}-1}}$.

De manera más general, la distribución de las raíces de un polinomio con respecto a un círculo arbitrario en el plano complejo, digamos uno con centro y radio , se puede encontrar aplicando la prueba de Schur-Cohn al polinomio 'desplazado y escalado' definido por . ${\displaystyle p}$ ${\displaystyle c}$ ${\displaystyle \rho }$ ${\displaystyle q}$ ${\displaystyle q(z)=p(c+\rho \,z)}$

Sin embargo, no se permiten todos los factores de escala, ya que la prueba de Schur-Cohn se puede aplicar al polinomio solo si no se produce ninguna de las siguientes igualdades: for some o while . Ahora bien, los coeficientes de los polinomios son polinomios en y dichas igualdades dan como resultado ecuaciones polinómicas para , que por lo tanto sólo son válidas para un número finito de valores de . Por lo tanto, siempre se puede encontrar un factor de escala adecuado, incluso arbitrariamente cercano a . ${\displaystyle q}$ ${\displaystyle T^{k}q(0)=0}$ ${\displaystyle k=1,\ldots K}$ ${\displaystyle T^{K+1}q=0}$ ${\displaystyle d_{K}>0}$ ${\displaystyle T^{k}q}$ ${\displaystyle \rho }$ ${\displaystyle \rho }$ ${\displaystyle \rho }$ ${\displaystyle 1}$

El método de Lehmer.

El método de Lehmers es el siguiente. ^[5] Para un polinomio complejo dado , con la prueba de Schur-Cohn se puede encontrar un disco circular lo suficientemente grande como para contener todas las raíces de . A continuación, este disco se puede cubrir con un conjunto de discos más pequeños superpuestos, uno de ellos colocado de forma concéntrica y los restantes distribuidos uniformemente sobre el anillo aún por cubrir. De este conjunto, utilizando la prueba nuevamente, se pueden eliminar los discos que no contienen raíz . Con cada uno de los discos restantes, este procedimiento de cobertura y eliminación se puede repetir tantas veces como desee, lo que da como resultado un conjunto de discos arbitrariamente pequeños que juntos contienen todas las raíces de . ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

Las ventajas del método son que consiste en la repetición de un único procedimiento y que se encuentran todas las raíces simultáneamente, ya sean reales o complejas, únicas, múltiples o agrupadas. Además, no es necesaria la deflación, es decir, la eliminación de raíces ya encontradas, y cada prueba comienza con el polinomio original de total precisión. Y, sorprendentemente, este polinomio nunca ha sido evaluado.

Sin embargo, cuanto más pequeños se vuelven los discos, más diferirán en magnitud relativa los coeficientes de los polinomios 'escalados' correspondientes. Esto puede causar un desbordamiento o un desbordamiento insuficiente de los cálculos de la computadora, limitando así los radios de los discos desde abajo y, por lo tanto, la precisión de las raíces calculadas. ^[2] . ^[6] Para evitar un escalamiento extremo, o simplemente por razones de eficiencia, se puede comenzar probando una cantidad de discos concéntricos para determinar la cantidad de raíces incluidas y así reducir la región donde se producen las raíces a una cantidad de anillos concéntricos estrechos. Repitiendo este procedimiento con otro centro y combinando los resultados, dicha región se convierte en la unión de intersecciones de tales anillos. ^[7] Finalmente, cuando se encuentra un disco pequeño que contiene una única raíz, esa raíz puede aproximarse aún más utilizando otros métodos, por ejemplo, el método de Newton .

Referencias

1. Cohn, A (1922). "Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise". Matemáticas. Z.​ 14 : 110-148. doi :10.1007/BF01215894. hdl : 10338.dmlcz/102550 . S2CID  123129925.
2. Henrici, Peter (1988). Análisis complejo aplicado y computacional. Volumen I: Serie de potencias-integración-mapeo conforme-ubicación de ceros (Repr. del original, publ. 1974 por John Wiley \& Sons Ltd., edición de bolsillo). Nueva York, etc.: John Wiley. págs. xv + 682. ISBN 0-471-60841-6.
3. Marden, Morris (1949). La geometría de los ceros de un polinomio en una variable compleja . Encuestas Matemáticas. No. 3. Nueva York: Sociedad Matemática Estadounidense (AMS). pag. 148.
4. Schur, yo (1917). "Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind". Journal für die reine und angewandte Mathematik . 1917 (147): 205–232. doi :10.1515/crll.1917.147.205. S2CID  199546483.
5. Lehmer, DH (1961). "Un método automático para resolver ecuaciones polinómicas". Revista de la Asociación de Maquinaria de Computación . 8 (2): 151–162. doi : 10.1145/321062.321064 . S2CID  17667943.
6. Stewart, GWIII (1969). "Sobre el método de Lehmer para encontrar los ceros de un polinomio". Matemáticas. Computación . 23 (108): 829–835. doi :10.2307/2004970. JSTOR  2004970.
7. Loewenthal, Dan (1993). "Mejora del método de detección de raíces de Lehmer-Schur". J. Computación. Física . 109 (2): 164-168. Código Bib : 1993JCoPh.109..164L. doi :10.1006/jcph.1993.1209.