Un sistema de ecuaciones polinomiales (a veces simplemente un sistema polinomial ) es un conjunto de ecuaciones simultáneas f 1 = 0, ..., f h = 0 donde f i son polinomios en varias variables, digamos x 1 , ..., x n , sobre algún cuerpo k .
Una solución de un sistema polinómico es un conjunto de valores para las x i s que pertenecen a alguna extensión de campo algebraicamente cerrada K de k , y que hacen que todas las ecuaciones sean verdaderas. Cuando k es el campo de los números racionales , generalmente se supone que K es el campo de los números complejos , porque cada solución pertenece a una extensión de campo de k , que es isomorfa a un subcampo de los números complejos.
Este artículo trata sobre los métodos para resolver, es decir, encontrar todas las soluciones o describirlas. Como estos métodos están diseñados para ser implementados en una computadora, se hace hincapié en los campos k en los que el cálculo (incluida la comprobación de igualdad) es fácil y eficiente, es decir, el campo de los números racionales y los campos finitos .
La búsqueda de soluciones pertenecientes a un conjunto específico es un problema que, en general, es mucho más difícil y que queda fuera del alcance de este artículo, salvo en el caso de las soluciones en un cuerpo finito dado. Para el caso de soluciones cuyos componentes son todos números enteros o racionales, véase ecuación diofántica .
Un ejemplo simple de un sistema de ecuaciones polinómicas es
Sus soluciones son los cuatro pares ( x , y ) = (1, 2), (2, 1), (-1, -2), (-2, -1) . Estas soluciones se pueden comprobar fácilmente mediante sustitución, pero se necesita más trabajo para demostrar que no hay otras soluciones.
El tema de este artículo es el estudio de las generalizaciones de tales ejemplos y la descripción de los métodos que se utilizan para calcular las soluciones.
Un sistema de ecuaciones polinómicas, o sistema polinomial , es una colección de ecuaciones
donde cada f h es un polinomio en los indeterminados x 1 , ..., x m , con coeficientes enteros, o coeficientes en algún campo fijo , a menudo el campo de los números racionales o un campo finito . [1] Otros campos de coeficientes, como los números reales , se utilizan con menos frecuencia, ya que sus elementos no se pueden representar en una computadora (solo se pueden usar aproximaciones de números reales en los cálculos, y estas aproximaciones son siempre números racionales).
Una solución de un sistema polinómico es una tupla de valores de ( x 1 , ..., x m ) que satisface todas las ecuaciones del sistema polinómico. Las soluciones se buscan en los números complejos o, más generalmente, en un cuerpo algebraicamente cerrado que contiene los coeficientes. En particular, en la característica cero se buscan todas las soluciones complejas . La búsqueda de las soluciones reales o racionales son problemas mucho más difíciles que no se consideran en este artículo.
El conjunto de soluciones no siempre es finito; por ejemplo, las soluciones del sistema
son un punto ( x , y ) = (1,1) y una línea x = 0 . [2] Incluso cuando el conjunto de soluciones es finito, en general, no existe una expresión en forma cerrada de las soluciones (en el caso de una sola ecuación, este es el teorema de Abel-Ruffini ).
La superficie de Barth , mostrada en la figura, es la representación geométrica de las soluciones de un sistema polinómico reducido a una única ecuación de grado 6 en 3 variables. En la imagen se pueden ver algunos de sus numerosos puntos singulares . Son las soluciones de un sistema de 4 ecuaciones de grado 5 en 3 variables. Un sistema sobredeterminado de este tipo no tiene solución en general (es decir, si los coeficientes no son específicos). Si tiene un número finito de soluciones, este número es como máximo 5 3 = 125 , por el teorema de Bézout . Sin embargo, se ha demostrado que, para el caso de los puntos singulares de una superficie de grado 6, el número máximo de soluciones es 65, y se alcanza mediante la superficie de Barth.
Un sistema está sobredeterminado si el número de ecuaciones es mayor que el número de variables. Un sistema es inconsistente si no tiene una solución compleja (o, si los coeficientes no son números complejos, no tiene una solución en un cuerpo algebraicamente cerrado que contenga los coeficientes). Por el Nullstellensatz de Hilbert esto significa que 1 es una combinación lineal (con polinomios como coeficientes) de los primeros miembros de las ecuaciones. La mayoría de los sistemas sobredeterminados, pero no todos, cuando se construyen con coeficientes aleatorios, son inconsistentes. Por ejemplo, el sistema x 3 – 1 = 0, x 2 – 1 = 0 está sobredeterminado (tiene dos ecuaciones pero solo una incógnita), pero no es inconsistente ya que tiene la solución x = 1 .
Un sistema está indeterminado si el número de ecuaciones es menor que el número de variables. Un sistema indeterminado es inconsistente o tiene infinitas soluciones complejas (o soluciones en un cuerpo algebraicamente cerrado que contiene los coeficientes de las ecuaciones). Este es un resultado no trivial del álgebra conmutativa que involucra, en particular, el teorema de los Nullstellensatz de Hilbert y el teorema del ideal principal de Krull .
Un sistema es de dimensión cero si tiene un número finito de soluciones complejas (o soluciones en un campo algebraicamente cerrado). Esta terminología proviene del hecho de que la variedad algebraica de las soluciones tiene dimensión cero. Un sistema con infinitas soluciones se dice que es de dimensión positiva .
A veces se dice que un sistema de dimensión cero con tantas ecuaciones como variables se comporta bien . [3] El teorema de Bézout afirma que un sistema de comportamiento adecuado cuyas ecuaciones tienen grados d 1 , ..., d n tiene como máximo d 1 ⋅⋅⋅ d n soluciones. Este límite es preciso. Si todos los grados son iguales a d , este límite se convierte en d n y es exponencial en el número de variables. (El teorema fundamental del álgebra es el caso especial n = 1 .)
Este comportamiento exponencial dificulta la resolución de sistemas polinómicos y explica por qué hay pocos solucionadores capaces de resolver automáticamente sistemas con un límite de Bézout mayor que, digamos, 25 (tres ecuaciones de grado 3 o cinco ecuaciones de grado 2 están más allá de este límite). [ cita requerida ]
Lo primero que hay que hacer para resolver un sistema polinómico es decidir si es inconsistente, de dimensión cero o de dimensión positiva. Esto se puede hacer mediante el cálculo de una base de Gröbner de los lados izquierdos de las ecuaciones. El sistema es inconsistente si esta base de Gröbner se reduce a 1. El sistema es de dimensión cero si, para cada variable, hay un monomio principal de algún elemento de la base de Gröbner que es una potencia pura de esta variable. Para esta prueba, el mejor orden de monomios (es decir, el que conduce generalmente al cálculo más rápido) suele ser el lexicográfico inverso graduado (grevlex).
Si el sistema es de dimensión positiva , tiene infinitas soluciones. Por lo tanto, no es posible enumerarlas. De ello se deduce que, en este caso, resolver puede significar únicamente "encontrar una descripción de las soluciones de la que las propiedades relevantes de las soluciones sean fáciles de extraer". No existe una descripción comúnmente aceptada de este tipo. De hecho, hay muchas "propiedades relevantes" diferentes, que involucran casi todos los subcampos de la geometría algebraica .
Un ejemplo natural de una cuestión de este tipo en relación con los sistemas de dimensión positiva es el siguiente: decidir si un sistema polinomial sobre los números racionales tiene un número finito de soluciones reales y calcularlas . Una generalización de esta cuestión es encontrar al menos una solución en cada componente conexo del conjunto de soluciones reales de un sistema polinomial . El algoritmo clásico para resolver estas cuestiones es la descomposición algebraica cilíndrica , que tiene una complejidad computacional doblemente exponencial y, por lo tanto, no se puede utilizar en la práctica, excepto para ejemplos muy pequeños.
Para sistemas de dimensión cero, la resolución consiste en calcular todas las soluciones. Hay dos formas diferentes de obtener las soluciones. La forma más común es posible solo para soluciones reales o complejas y consiste en obtener aproximaciones numéricas de las soluciones. Dicha solución se denomina numérica . Una solución está certificada si se proporciona con un límite para el error de las aproximaciones y si este límite separa las diferentes soluciones.
La otra forma de representar las soluciones se denomina algebraica . Utiliza el hecho de que, para un sistema de dimensión cero, las soluciones pertenecen a la clausura algebraica del cuerpo k de los coeficientes del sistema. Existen varias formas de representar la solución en una clausura algebraica, que se analizan a continuación. Todas ellas permiten calcular una aproximación numérica de las soluciones mediante la resolución de una o varias ecuaciones univariadas. Para este cálculo, es preferible utilizar una representación que implique resolver solo un polinomio univariado por solución, porque calcular las raíces de un polinomio que tiene coeficientes aproximados es un problema altamente inestable .
Una ecuación trigonométrica es una ecuación g = 0 donde g es un polinomio trigonométrico . Una ecuación de este tipo se puede convertir en un sistema polinómico expandiendo los senos y cosenos que contiene (usando fórmulas de suma y diferencia ), reemplazando sen( x ) y cos( x ) por dos nuevas variables s y c y agregando la nueva ecuación s 2 + c 2 – 1 = 0 .
Por ejemplo, debido a la identidad
Resolviendo la ecuación
es equivalente a resolver el sistema polinomial
Para cada solución ( c 0 , s 0 ) de este sistema, existe una solución única x de la ecuación tal que 0 ≤ x < 2 π .
En el caso de este ejemplo sencillo, puede que no quede claro si el sistema es o no más fácil de resolver que la ecuación. En los ejemplos más complicados, no se dispone de métodos sistemáticos para resolver directamente la ecuación, mientras que sí se dispone de software para resolver automáticamente el sistema correspondiente.
Al resolver un sistema sobre un cuerpo finito k con q elementos, lo que interesa principalmente son las soluciones en k . Como los elementos de k son exactamente las soluciones de la ecuación x q – x = 0 , basta, para restringir las soluciones a k , añadir la ecuación x i q – x i = 0 para cada variable x i .
Los elementos de un cuerpo numérico algebraico se representan habitualmente como polinomios en un generador del cuerpo que satisface alguna ecuación polinómica univariante. Para trabajar con un sistema polinómico cuyos coeficientes pertenecen a un cuerpo numérico, basta con considerar este generador como una nueva variable y añadir la ecuación del generador a las ecuaciones del sistema. De este modo, resolver un sistema polinómico sobre un cuerpo numérico se reduce a resolver otro sistema sobre los números racionales.
Por ejemplo, si un sistema contiene , se obtiene un sistema sobre los números racionales sumando la ecuación r 2 2 – 2 = 0 y reemplazando por r 2 en las otras ecuaciones.
En el caso de un campo finito, la misma transformación permite suponer siempre que el campo k tiene orden primo.
La forma habitual de representar las soluciones es mediante cadenas regulares de dimensión cero. Dicha cadena consiste en una sucesión de polinomios f 1 ( x 1 ) , f 2 ( x 1 , x 2 ) , ..., f n ( x 1 , ..., x n ) tales que, para cada i tal que 1 ≤ i ≤ n
A dicha cadena regular se le asocia un sistema triangular de ecuaciones
Las soluciones de este sistema se obtienen resolviendo la primera ecuación univariante, sustituyendo las soluciones en las otras ecuaciones, resolviendo luego la segunda ecuación que ahora es univariante, y así sucesivamente. La definición de cadenas regulares implica que la ecuación univariante obtenida a partir de f i tiene grado d i y por tanto que el sistema tiene d 1 ... d n soluciones, siempre que no haya raíz múltiple en este proceso de resolución ( teorema fundamental del álgebra ).
Todo sistema de ecuaciones polinómicas de dimensión cero es equivalente (es decir, tiene las mismas soluciones) a un número finito de cadenas regulares. Pueden ser necesarias varias cadenas regulares, como es el caso del siguiente sistema que tiene tres soluciones.
Existen varios algoritmos para calcular una descomposición triangular de un sistema polinomial arbitrario (no necesariamente de dimensión cero) [4] en cadenas regulares (o sistemas semialgebraicos regulares ).
Existe también un algoritmo específico para el caso de dimensión cero y que compite, en este caso, con los algoritmos directos. Consiste en calcular primero la base de Gröbner para el orden lexicográfico inverso graduado (grevlex) , luego deducir la base lexicográfica de Gröbner mediante el algoritmo FGLM [5] y finalmente aplicar el algoritmo Lextriangular [6] .
Esta representación de las soluciones es totalmente conveniente para coeficientes en un cuerpo finito. Sin embargo, para coeficientes racionales, se deben tener en cuenta dos aspectos:
El primer problema ha sido resuelto por Dahan y Schost: [7] [8] Entre los conjuntos de cadenas regulares que representan un conjunto dado de soluciones, hay un conjunto para el cual los coeficientes están explícitamente acotados en términos del tamaño del sistema de entrada, con un límite casi óptimo. Este conjunto, llamado descomposición equiproyectable , depende únicamente de la elección de las coordenadas. Esto permite el uso de métodos modulares para calcular eficientemente la descomposición equiproyectable. [9]
El segundo problema se resuelve generalmente generando cadenas regulares de una forma especial, a veces llamada lema de forma , para la cual todos los d i excepto el primero son iguales a 1. Para obtener dichas cadenas regulares, puede ser necesario agregar una variable adicional, llamada variable separadora , a la que se le asigna el índice 0. La representación univariante racional , descrita a continuación, permite calcular una cadena regular especial de este tipo, que satisface el límite de Dahan-Schost, comenzando desde una cadena regular o una base de Gröbner.
La representación univariante racional o RUR es una representación de las soluciones de un sistema polinomial de dimensión cero sobre los números racionales que fue introducida por F. Rouillier. [10]
Una RUR de un sistema de dimensión cero consiste en una combinación lineal x 0 de las variables, llamada variable separadora , y un sistema de ecuaciones [11]
donde h es un polinomio univariado en x 0 de grado D y g 0 , ..., g n son polinomios univariados en x 0 de grado menor que D .
Dado un sistema polinomial de dimensión cero sobre los números racionales, el RUR tiene las siguientes propiedades.
Por ejemplo, para el sistema de la sección anterior, cada combinación lineal de la variable, excepto los múltiplos de x , y y x + y , es una variable separadora. Si se elige t = x - y/2 como variable separadora, entonces el RUR es
La RUR se define de forma única para una variable separadora dada, independientemente de cualquier algoritmo, y preserva las multiplicidades de las raíces. Esta es una diferencia notable con las descomposiciones triangulares (incluso la descomposición equiproyectable), que, en general, no preservan las multiplicidades. La RUR comparte con la descomposición equiproyectable la propiedad de producir una salida con coeficientes de tamaño relativamente pequeño.
Para sistemas de dimensión cero, el RUR permite recuperar los valores numéricos de las soluciones resolviendo un único polinomio univariante y sustituyéndolos en funciones racionales. Esto permite la producción de aproximaciones certificadas de las soluciones con cualquier precisión dada.
Además, el polinomio univariante h ( x 0 ) del RUR puede factorizarse, y esto da un RUR para cada factor irreducible. Esto proporciona la descomposición primal del ideal dado (es decir, la descomposición primaria del radical del ideal). En la práctica, esto proporciona una salida con coeficientes mucho más pequeños, especialmente en el caso de sistemas con altas multiplicidades.
A diferencia de las descomposiciones triangulares y equiproyectables, el RUR no está definido en dimensión positiva.
Los algoritmos numéricos generales diseñados para cualquier sistema de ecuaciones no lineales también funcionan para sistemas polinómicos. Sin embargo, generalmente se preferirán los métodos específicos, ya que los métodos generales no suelen permitir encontrar todas las soluciones. En particular, cuando un método general no encuentra ninguna solución, esto no suele ser una indicación de que no exista solución.
Sin embargo, aquí merecen mencionarse dos métodos.
Se trata de un método seminumérico que supone que el número de ecuaciones es igual al número de variables. Este método es relativamente antiguo, pero ha mejorado notablemente en las últimas décadas. [13]
Este método se divide en tres pasos. Primero se calcula un límite superior para el número de soluciones. Este límite debe ser lo más preciso posible. Por lo tanto, se calcula mediante al menos cuatro métodos diferentes y se conserva el mejor valor, por ejemplo .
En el segundo paso se genera un sistema de ecuaciones polinómicas que tiene exactamente soluciones fáciles de calcular. Este nuevo sistema tiene el mismo número de variables y el mismo número de ecuaciones y la misma estructura general que el sistema a resolver .
Se considera entonces una homotopía entre los dos sistemas. Consiste, por ejemplo, en la línea recta entre los dos sistemas, pero se pueden considerar otros caminos, en particular para evitar algunas singularidades, en el sistema.
La continuación de homotopía consiste en deformar el parámetro de 0 a 1 y seguir las soluciones durante esta deformación. Esto da las soluciones deseadas para . Seguir significa que, si , las soluciones para se deducen de las soluciones para mediante el método de Newton. La dificultad aquí es elegir bien el valor de Demasiado grande, la convergencia de Newton puede ser lenta e incluso puede saltar de una vía de solución a otra. Demasiado pequeño, y el número de pasos ralentiza el método.
Deducir los valores numéricos de las soluciones a partir de una ecuación univariante parece fácil: basta con calcular las raíces del polinomio univariante y sustituirlas en las demás ecuaciones. Esto no es tan fácil porque la evaluación de un polinomio a partir de las raíces de otro polinomio es altamente inestable.
Por lo tanto, las raíces del polinomio univariante deben calcularse con una precisión elevada que no puede definirse de una vez por todas. Existen dos algoritmos que cumplen este requisito.
Existen al menos cuatro paquetes de software que pueden resolver sistemas de dimensión cero de forma automática (por "automática" se entiende que no se necesita intervención humana entre la entrada y la salida y, por lo tanto, que el usuario no necesita conocer el método). También existen otros paquetes de software que pueden resultar útiles para resolver sistemas de dimensión cero. Algunos de ellos se enumeran después de los solucionadores automáticos.
La función de Maple RootFinding[Isolate] toma como entrada cualquier sistema polinómico sobre los números racionales (si algunos coeficientes son números de punto flotante , se convierten a números racionales) y genera como salida las soluciones reales representadas (opcionalmente) como intervalos de números racionales o como aproximaciones de punto flotante de precisión arbitraria. Si el sistema no es de dimensión cero, esto se indica como un error.
Internamente, este solucionador, diseñado por F. Rouillier, calcula primero una base de Gröbner y luego una representación racional univariante de la que se deduce la aproximación requerida de las soluciones. Funciona de manera rutinaria para sistemas que tienen hasta unos pocos cientos de soluciones complejas.
La representación univariante racional se puede calcular con la función de Maple Groebner[RationalUnivariateRepresentation] .
Para extraer todas las soluciones complejas de una representación racional univariante, se puede utilizar MPSolve , que calcula las raíces complejas de polinomios univariados con cualquier precisión. Se recomienda ejecutar MPSolve varias veces, duplicando la precisión cada vez, hasta que las soluciones permanezcan estables, ya que la sustitución de las raíces en las ecuaciones de las variables de entrada puede ser muy inestable.
El segundo solucionador es PHCpack, [13] [16] escrito bajo la dirección de J. Verschelde. PHCpack implementa el método de continuación de homotopía. Este solucionador calcula las soluciones complejas aisladas de sistemas polinómicos que tienen tantas ecuaciones como variables.
El tercer solucionador es Bertini, [17] [18] escrito por DJ Bates, JD Hauenstein, AJ Sommese y CW Wampler. Bertini utiliza la continuación de homotopía numérica con precisión adaptativa. Además de calcular conjuntos de soluciones de dimensión cero, tanto PHCpack como Bertini son capaces de trabajar con conjuntos de soluciones de dimensión positiva.
El cuarto solucionador es la biblioteca RegularChains de Maple , escrita por Marc Moreno-Maza y colaboradores. Contiene varias funciones para resolver sistemas polinómicos mediante cadenas regulares .
