Un sistema de ecuaciones polinómicas (a veces simplemente un sistema polinómico ) es un conjunto de ecuaciones simultáneas f 1 = 0, ..., f h = 0 donde las f i son polinomios en varias variables, digamos x 1 , ..., x n , sobre algún campo k .
Una solución de un sistema polinómico es un conjunto de valores para x i s que pertenecen a alguna extensión de campo algebraicamente cerrada K de k y hacen que todas las ecuaciones sean verdaderas. Cuando k es el cuerpo de números racionales , generalmente se supone que K es el cuerpo de números complejos , porque cada solución pertenece a una extensión de cuerpo 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 da énfasis a los campos k en los cuales el cálculo (incluidas las pruebas de igualdad) es fácil y eficiente, es decir, el campo de los números racionales y los campos finitos .
Buscar soluciones que pertenezcan a un conjunto específico es un problema generalmente mucho más difícil, y está fuera del alcance de este artículo, excepto en el caso de las soluciones en un campo finito determinado. Para el caso de soluciones en las que todos los componentes son 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 pueden comprobarse fácilmente mediante sustitución, pero se necesita más trabajo para demostrar que no existen otras soluciones.
El tema de este artículo es el estudio de generalizaciones de dichos ejemplos y la descripción de los métodos que se utilizan para calcular las soluciones.
Un sistema de ecuaciones polinomiales, o sistema polinómico, es un conjunto 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 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 (sólo se pueden utilizar 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 campo algebraicamente cerrado que contiene los coeficientes. En particular, en la característica cero se buscan todas las soluciones complejas . Buscar 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 recta x = 0 . [2] Incluso cuando el conjunto de soluciones es finito, en general no existe una expresión cerrada de las soluciones (en el caso de una ecuación única, 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 polinomial reducido a una sola ecuación de grado 6 en 3 variables. En la imagen son visibles algunos de sus numerosos puntos singulares . Son las soluciones de un sistema de 4 ecuaciones de grado 5 en 3 variables. Un sistema tan sobredeterminado 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 , según 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 lo alcanza 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 solución compleja (o, si los coeficientes no son números complejos, no tiene solución en un campo algebraicamente cerrado que contiene los coeficientes). Según 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, aunque 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á subdeterminado 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 campo algebraicamente cerrado que contiene los coeficientes de las ecuaciones). Este es un resultado no trivial del álgebra conmutativa que involucra, en particular, el Nullstellensatz de Hilbert y el teorema 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 que se comporta bien cuyas ecuaciones tienen grados d 1 , ..., d n tiene como máximo soluciones d 1 ⋅⋅⋅ d n . Este límite es agudo. 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 polinomiales y explica por qué hay pocos solucionadores que sean capaces de resolver automáticamente sistemas con un límite de Bézout superior a, digamos, 25 (tres ecuaciones de grado 3 o cinco ecuaciones de grado 2 están más allá de este límite). [ cita necesaria ]
Lo primero que hay que hacer para resolver un sistema polinomial es decidir si es inconsistente, de dimensión cero o de dimensión positiva. Esto se puede hacer calculando 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 monomial (que es 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 tanto, no es posible enumerarlos. De ello se deduce que, en este caso, resolver puede significar sólo "encontrar una descripción de las soluciones de la cual las propiedades relevantes de las soluciones sean fáciles de extraer". No existe una descripción de este tipo comúnmente aceptada. De hecho, existen muchas "propiedades relevantes" diferentes, que involucran casi todos los subcampos de la geometría algebraica .
Un ejemplo natural de una pregunta de este tipo sobre sistemas de dimensiones positivas es el siguiente: decidir si un sistema polinomial sobre números racionales tiene un número finito de soluciones reales y calcularlas . Una generalización de esta pregunta 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 en ejemplos muy pequeños.
Para sistemas de dimensión cero, la resolución consiste en calcular todas las soluciones. Hay dos formas diferentes de generar las soluciones. La forma más común es posible sólo para soluciones reales o complejas y consiste en generar aproximaciones numéricas de las soluciones. Esta solución se llama numérica . Una solución está certificada si se le proporciona un límite de error de las aproximaciones y si este límite separa las diferentes soluciones.
La otra forma de representar las soluciones se dice algebraica . Utiliza el hecho de que, para un sistema de dimensión cero, las soluciones pertenecen a la clausura algebraica del campo k de los coeficientes del sistema. Hay varias formas de representar la solución en una clausura algebraica, que se analizan a continuación. Todos ellos permiten calcular una aproximación numérica de las soluciones resolviendo 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 sin( x ) y cos( x ) por dos nuevas variables s y c y sumando 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 única solución x de la ecuación tal que 0 ≤ x < 2 π .
En el caso de este sencillo ejemplo, puede que no quede claro si el sistema es más fácil de resolver que la ecuación o no. En ejemplos más complicados, faltan métodos sistemáticos para resolver directamente la ecuación, mientras que hay software disponible para resolver automáticamente el sistema correspondiente.
Al resolver un sistema sobre un campo finito k con q elementos, uno está interesado principalmente en 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 , sumar la ecuación x i q – x i = 0 para cada variable x i .
Los elementos de un campo numérico algebraico generalmente se representan como polinomios en un generador del campo que satisface alguna ecuación polinómica univariada. 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 sumar la ecuación del generador a las ecuaciones del sistema. Por lo tanto, resolver un sistema polinomial sobre un cuerpo numérico se reduce a resolver otro sistema sobre números racionales.
Por ejemplo, si un sistema contiene , se obtiene un sistema sobre 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 cuerpo finito, la misma transformación permite suponer siempre que el campo k es de orden primo.
La forma habitual de representar las soluciones es mediante cadenas regulares de dimensión cero. Tal cadena consta de una secuencia de polinomios f 1 ( x 1 ) , f 2 ( x 1 , x 2 ) , ..., f n ( x 1 , ..., x n ) tal que, para cada i tal que 1 ≤ i ≤ n
A dicha cadena regular está asociado un sistema triangular de ecuaciones.
Las soluciones de este sistema se obtienen resolviendo la primera ecuación univariada, sustituyendo las soluciones en las otras ecuaciones, luego resolviendo la segunda ecuación que ahora es univariada, y así sucesivamente. La definición de cadenas regulares implica que la ecuación univariada obtenida de fi tiene grado d i y por tanto que el sistema tiene d 1 ... d n soluciones, siempre que no exista una 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. Es posible que se necesiten 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 polinómico arbitrario (no necesariamente de dimensión cero) [4] en cadenas regulares (o sistemas semialgebraicos regulares ).
También existe un algoritmo que es específico para el caso de dimensión cero y que es competitivo, 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 los coeficientes racionales hay que 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 de la entrada. sistema, 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 generalmente se resuelve generando cadenas regulares de una forma especial, a veces llamada lema de forma , para las cuales todos los d i excepto el primero son iguales a 1 . Para obtener cadenas tan regulares, es posible que sea necesario agregar una variable adicional, llamada variable de separación , a la que se le asigna el índice 0 . La representación univariada racional , que se describe a continuación, permite calcular una cadena regular especial que satisfaga el límite de Dahan-Schost, comenzando desde una cadena regular o una base de Gröbner.
La representación racional univariada o RUR es una representación de las soluciones de un sistema polinomial de dimensión cero sobre los números racionales que ha sido introducida por F. Rouillier. [10]
Un 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 polinómico de dimensión cero sobre 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
El RUR se define de forma única para una variable de separación determinada, independientemente de cualquier algoritmo, y preserva las multiplicidades de las raíces. Ésta es una diferencia notable con las descomposiciones triangulares (incluso la descomposición equiproyectable), que, en general, no conservan multiplicidades. El RUR comparte con la descomposición equiproyectable la propiedad de producir una producción 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 univariado 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 univariado h ( x 0 ) del RUR puede factorizarse, y esto da un RUR para cada factor irreducible. Esto proporciona la descomposición primaria 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 multiplicidades altas.
A diferencia de las descomposiciones triangulares y las descomposiciones equiprojectables, 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 polinomiales. Sin embargo, generalmente se preferirán los métodos específicos, ya que los métodos generales generalmente no permiten 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 haya solución.
Sin embargo, aquí merecen mencionarse dos métodos.
Este es 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 espectacularmente 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 tiene que ser lo más agudo posible. Por lo tanto, se calcula mediante al menos cuatro métodos diferentes y se mantiene el mejor valor, digamos .
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 .
Entonces se considera 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 la homotopía consiste en deformar el parámetro de 0 a 1 y seguir las soluciones durante esta deformación. Esto proporciona las soluciones deseadas para . Lo siguiente significa que, si , las soluciones de se deducen de las soluciones de 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 un camino de solución a otro. Demasiado pequeño y el número de pasos ralentiza el método.
Deducir los valores numéricos de las soluciones a partir de un RUR parece fácil: basta con calcular las raíces del polinomio univariado y sustituirlas en las demás ecuaciones. Esto no es tan fácil porque la evaluación de un polinomio en las raíces de otro polinomio es muy inestable.
Por lo tanto, las raíces del polinomio univariado deben calcularse con una precisión alta que puede no definirse de una vez por todas. Hay dos algoritmos que cumplen este requisito.
Hay al menos cuatro paquetes de software que pueden resolver sistemas de dimensión cero automáticamente (automáticamente, uno significa que no se necesita intervención humana entre la entrada y la salida y, por lo tanto, no se necesita ningún conocimiento del método por parte del usuario). También existen otros paquetes de software que pueden resultar útiles para resolver sistemas de dimensión cero. Algunos de ellos aparecen enumerados después de los solucionadores automáticos.
La función Maple RootFinding[Isolate] toma como entrada cualquier sistema polinómico sobre números racionales (si algunos coeficientes son números de punto flotante , se convierten a números racionales) y genera las soluciones reales representadas (opcionalmente) como intervalos de números racionales o como aproximaciones en coma flotante de precisión arbitraria. Si el sistema no tiene 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 Univariada de la que se deduce la aproximación requerida de las soluciones. Funciona de forma rutinaria para sistemas que tienen hasta unos cientos de soluciones complejas.
La representación racional univariada se puede calcular con la función Maple Groebner[RationalUnivariateRepresentation] .
Para extraer todas las soluciones complejas de una representación univariante racional, 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 altamente 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 polinomiales 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 la 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 dimensiones positivas.
El cuarto solucionador es la biblioteca Maple RegularChains , escrita por Marc Moreno-Maza y colaboradores. Contiene diversas funciones para la resolución de sistemas polinomiales mediante cadenas regulares .
