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 , extendiendo 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 probar discos cada vez más pequeños para detectar la presencia o ausencia de raíces.
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 es definido por y su Schurtransform por
donde una barra denota conjugación compleja .
Así que si con , luego , con los términos cero iniciales , si los hay, eliminados. Los coeficientes de por tanto, puede expresarse directamente en los de y, dado que uno o más coeficientes principales se cancelan, tiene un grado menor que . Las raices de, , y se relacionan de la siguiente manera.
- Lema
Dejar ser un polinomio complejo y .
- Las raices de , incluyendo sus multiplicidades , son las imágenes bajo inversión en el círculo unitario de las raíces distintas de cero de.
- Si , luego , y comparten raíces en el círculo unitario, incluidas sus multiplicidades.
- Si , luego y tienen el mismo número de raíces dentro del círculo unitario.
- Si , luego y tienen el mismo número de raíces dentro del círculo unitario.
- Prueba
Para tenemos y en particular, por . También implica . De esto y de las definiciones anteriores se siguen las dos primeras declaraciones. Los otros dos enunciados son consecuencia del teorema de Rouché aplicado en el círculo unitario a las funciones y , dónde es un polinomio que tiene como raíces las raíces de en el círculo unitario, con las mismas multiplicidades. □
Para una representación más accesible del lema, dejemos , y denotar el número de raíces de dentro, dentro y fuera del círculo unitario respectivamente y de manera similar para . Además deja ser la diferencia en el grado de y . Entonces el lema implica que Si y Si (nótese el intercambio de y ).
Ahora considere la secuencia de polinomios , dónde y . La aplicación de lo anterior a cada par de miembros consecutivos de esta secuencia da el siguiente resultado.
- Teorema [prueba de Schur-Cohn]
Dejar ser un polinomio complejo con y deja ser el número más pequeño tal que . Además deja por y por .
- Todas las raíces de se encuentran dentro del círculo unitario si y solo si
, por , y .
- Todas las raíces de se encuentran fuera del círculo unitario si y solo si
por y .
- Si y si por (en orden creciente) y de lo contrario, entonces no tiene raíces en el círculo unitario y el número de raíces de dentro del círculo unitario está
- .
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 mediante la aplicación de la prueba de Schur-Cohn al polinomio 'desplazado y escalado' definido por .
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: para algunos o tiempo . Ahora, los coeficientes de los polinomios son polinomios en y dichas igualdades dan como resultado ecuaciones polinomiales para , que por lo tanto sólo se mantienen para un número finito de valores de . Por lo tanto, siempre se puede encontrar un factor de escala adecuado, incluso arbitrariamente cercano a.
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, usando la prueba nuevamente, los discos que no contienen raíz dese puede quitar. Con cada uno de los discos restantes, este procedimiento de recubrimiento y extracción se puede repetir y, por lo tanto, cualquier número de veces, lo que da como resultado un conjunto de discos arbitrariamente pequeños que en conjunto contienen todas las raíces de.
El mérito del método es que consiste en la repetición de un solo procedimiento y que todas las raíces se encuentran simultáneamente, ya sean reales o complejas, únicas, múltiples o agrupadas. Además, la deflación, es decir, la eliminación de las raíces ya encontradas, no es necesaria y cada prueba comienza con el polinomio original de precisión total. Y, sorprendentemente, este polinomio nunca ha de ser evaluado.
Sin embargo, cuanto más pequeños se vuelven los discos, más difieren en magnitud relativa los coeficientes de los polinomios "escalados" correspondientes. Esto puede provocar un desbordamiento o un desbordamiento de los cálculos informáticos, limitando así los radios de los discos desde abajo y, por tanto, la precisión de las raíces calculadas. [2] . [6] Para evitar un escalado extremo, o simplemente en aras de la eficiencia, se puede comenzar probando varios discos concéntricos para determinar el número de raíces incluidas y así reducir la región donde se encuentran las raíces a un número 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 dichos anillos. [7] Finalmente, cuando se encuentra un disco pequeño que contiene una sola raíz, esa raíz puede aproximarse aún más utilizando otros métodos, por ejemplo, el método de Newton .
Referencias
- ^ 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 .
- ^ a b 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 en rústica). Nueva York, etc .: John Wiley. págs. xv + 682. ISBN 0-471-60841-6.
- ^ Marden, Morris (1949). La geometría de los ceros de un polinomio en una variable compleja . Encuestas matemáticas. No. 3. Nueva York: American Mathematical Society (AMS). pag. 148.
- ^ Schur, I (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 .
- ^ Lehmer, DH (1961). "Un método de máquina para resolver ecuaciones polinomiales". J. Assoc. Computación. Mach . 8 : 151-162. doi : 10.1145 / 321062.321064 .
- ^ Stewart, GWIII (1969). "Sobre el método de Lehmer para encontrar los ceros de un polinomio". Matemáticas. Computación . 23 : 829–835. doi : 10.2307 / 2004970 .
- ^ Loewenthal, Dan (1993). "Mejora en el método de detección de raíces de Lehmer-Schur". J. Comput. Phys . 109 (2): 164–168. doi : 10.1006 / jcph.1993.1209 .