Sistema de ecuaciones polinómicas

Un sistema de ecuaciones polinómicas (a veces simplemente un sistema polinómico ) es un conjunto de ecuaciones simultáneas f ₁ = 0, ..., f _h = 0 donde las f _i son polinomios en varias variables, digamos x ₁ , ..., x _n , sobre algún campo k .

Una solución de un sistema polinómico es un conjunto de valores para los xᵢ que pertenecen a alguna extensión de cuerpo _K de k , algebraicamente cerrada , y que hacen que todas las ecuaciones sean verdaderas. Cuando k es el cuerpo de los números racionales , generalmente se asume que K es el cuerpo de los números complejos , porque cada solución pertenece a una extensión de cuerpo de k , que es isomorfa a un subcuerpo de los números complejos.

Este artículo trata sobre los métodos para resolver problemas, es decir, encontrar todas las soluciones o describirlas. Dado que 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 que pertenezcan a un conjunto específico es un problema generalmente mucho más difícil, y 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 la ecuación diofántica .

Un ejemplo sencillo de un sistema de ecuaciones polinómicas es

${\displaystyle {\begin{aligned}x^{2}+y^{2}-5&=0\\xy-2&=0.\end{aligned}}}$

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 existen otras soluciones.

El objeto 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 polinómicas, o sistema polinómico, es una colección de ecuaciones.

${\displaystyle {\begin{aligned}f_{1}\left(x_{1},\ldots ,x_{m}\right)&=0\\&\;\;\vdots \\f_{n}\left(x_{1},\ldots ,x_{m}\right)&=0,\end{aligned}}}$

where each f_h is a polynomial in the indeterminatesx₁, ..., x_m, with integer coefficients, or coefficients in some fixed field, often the field of rational numbers or a finite field.^[1] Other fields of coefficients, such as the real numbers, are less often used, as their elements cannot be represented in a computer (only approximations of real numbers can be used in computations, and these approximations are always rational numbers).

A solution of a polynomial system is a tuple of values of (x₁, ..., x_m) that satisfies all equations of the polynomial system. The solutions are sought in the complex numbers, or more generally in an algebraically closed field containing the coefficients. In particular, in characteristic zero, all complex solutions are sought. Searching for the real or rational solutions are much more difficult problems that are not considered in this article.

The set of solutions is not always finite; for example, the solutions of the system

${\displaystyle {\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}}$

are a point (x,y) = (1,1) and a line x = 0.^[2] Even when the solution set is finite, there is, in general, no closed-form expression of the solutions (in the case of a single equation, this is Abel–Ruffini theorem).

The Barth surface, shown in the figure is the geometric representation of the solutions of a polynomial system reduced to a single equation of degree 6 in 3 variables. Some of its numerous singular points are visible on the image. They are the solutions of a system of 4 equations of degree 5 in 3 variables. Such an overdetermined system has no solution in general (that is if the coefficients are not specific). If it has a finite number of solutions, this number is at most 5³ = 125, by Bézout's theorem. However, it has been shown that, for the case of the singular points of a surface of degree 6, the maximum number of solutions is 65, and is reached by the Barth surface.

Un sistema es 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 cuerpo algebraicamente cerrado que contenga los coeficientes). Según el teorema de los ceros de Hilbert, esto significa que 1 es una combinación lineal (con polinomios como coeficientes) de los primeros términos de las ecuaciones. La mayoría ^, pero no todos, los sistemas sobredeterminados, cuando se construyen con coeficientes aleatorios, son inconsistentes. Por ejemplo, el sistema x³ – ¹ = 0, x² – 1 = 0 es sobredeterminado (tiene dos ecuaciones pero solo una incógnita), pero no es inconsistente ya que tiene la solución x = 1 .

Un sistema es subdeterminado si el número de ecuaciones es menor que el número de variables. Un sistema subdeterminado 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 ceros de Hilbert y el teorema del ideal principal de Krull .

Un sistema es cero-dimensional si tiene un número finito de soluciones complejas (o soluciones en un cuerpo 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 denomina de dimensión positiva .

_{Se dice a veces que} un sistema cero-dimensional con tantas ecuaciones como variables es bien comportado . ^{[ 3 ]} El teorema de Bézout afirma que un sistema bien comportado cuyas ecuaciones tienen grados d₁ , _... , dₙ tiene como máximo d₁ ... _{dₙ soluciones} . Esta cota es óptima. Si todos los grados son iguales a d , esta cota se convierte en ^dₙ 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é existen pocos solucionadores capaces de resolver automáticamente sistemas con un límite de Bézout superior a, por ejemplo, 25 (tres ecuaciones de grado 3 o cinco ecuaciones de grado 2 superan este límite).

Lo primero que hay que hacer para resolver un sistema polinómico es determinar si es inconsistente, cero-dimensional o de dimensión positiva. Esto se puede hacer calculando una base de Gröbner de los segundos miembros de las ecuaciones. El sistema es inconsistente si esta base de Gröbner se reduce a 1. El sistema es cero-dimensional si, para cada variable, existe un monomio principal de algún elemento de la base de Gröbner que es una potencia pura de dicha variable. Para esta prueba, el mejor orden de monomios (es decir, el que generalmente conduce al cálculo más rápido) suele ser el orden lexicográfico inverso graduado (grevlex).

Si el sistema es de dimensión positiva , tiene infinitas soluciones. Por lo tanto, no es posible enumerarlas. En consecuencia, en este caso, resolverlo puede significar simplemente "encontrar una descripción de las soluciones a partir de la cual sea fácil extraer las propiedades relevantes de las mismas". No existe una descripción de este tipo comúnmente aceptada. De hecho, existen muchas "propiedades relevantes" diferentes, que abarcan casi todos los subcampos de la geometría algebraica .

Un ejemplo natural de este tipo de problema en sistemas de dimensión positiva es el siguiente: determinar si un sistema polinómico sobre los números racionales tiene un número finito de soluciones reales y calcularlas . Una generalización de este problema consiste en encontrar al menos una solución en cada componente conexa del conjunto de soluciones reales de un sistema polinómico . El algoritmo clásico para resolver este problema es la descomposición algebraica cilíndrica , que tiene una complejidad computacional doblemente exponencial y, por lo tanto, no puede utilizarse en la práctica, salvo en ejemplos muy pequeños.

Para sistemas de dimensión cero, la resolución consiste en calcular todas las soluciones. Existen dos maneras diferentes de obtener las soluciones. La más común, posible solo para soluciones reales o complejas, consiste en obtener aproximaciones numéricas de las soluciones. Dicha solución se denomina numérica . Una solución se certifica si se proporciona una cota para el error de las aproximaciones y si esta cota separa las diferentes soluciones.

The other way of representing the solutions is said to be algebraic. It uses the fact that, for a zero-dimensional system, the solutions belong to the algebraic closure of the field k of the coefficients of the system. There are several ways to represent the solution in an algebraic closure, which are discussed below. All of them allow one to compute a numerical approximation of the solutions by solving one or several univariate equations. For this computation, it is preferable to use a representation that involves solving only one univariate polynomial per solution, because computing the roots of a polynomial which has approximate coefficients is a highly unstable problem.

A trigonometric equation is an equation g = 0 where g is a trigonometric polynomial. Such an equation may be converted into a polynomial system by expanding the sines and cosines in it (using sum and difference formulas), replacing sin(x) and cos(x) by two new variables s and c and adding the new equation s² + c² – 1 = 0.

For example, because of the identity

${\displaystyle \cos(3x)=4\cos ^{3}(x)-3\cos(x),}$

solving the equation

${\displaystyle \sin ^{3}(x)+\cos(3x)=0}$

is equivalent to solving the polynomial system

${\displaystyle {\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}}$

For each solution (c₀, s₀) of this system, there is a unique solution x of the equation such that 0 ≤ x < 2π.

In the case of this simple example, it may be unclear whether the system is, or not, easier to solve than the equation. On more complicated examples, one lacks systematic methods for solving directly the equation, while software are available for automatically solving the corresponding system.

When solving a system over a finite field k with q elements, one is primarily interested in the solutions in k. As the elements of k are exactly the solutions of the equation x^q – x = 0, it suffices, for restricting the solutions to k, to add the equation x_i^q – x_i = 0 for each 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 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 añadir su ecuación 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 = 0 y reemplazando por r ₂ en las demás ecuaciones. ${\displaystyle {\sqrt {2}}}$${\displaystyle {\sqrt {2}}}$

En el caso de un campo finito, la misma transformación permite suponer siempre que el campo k tiene un orden primo.

La forma habitual de representar las soluciones es mediante cadenas regulares de dimensión cero. Dicha cadena consiste en una secuencia de polinomios f ₁ ( x ₁ ) , f ₂ ( x ₁ , x ₂ ) , ..., f _n ( x ₁ , ..., x _n ) tales que, para cada i tal que 1 ≤ i ≤ n

• f _i es un polinomio en x ₁ , ..., x _i solamente, que tiene un grado d _i > 0 en x _i ;
• El coeficiente de x _i ^{d _i} en f _i es un polinomio en x ₁ , ..., x _{i −1} que no tiene ningún cero común con f ₁ , ..., f _{i − 1} .

A dicha cadena regular se le asocia un sistema triangular de ecuaciones.

${\displaystyle {\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}}$

Las soluciones de este sistema se obtienen resolviendo la primera ecuación univariada, sustituyendo las soluciones en las demás 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 a partir de f _i tiene grado d _i y, por lo tanto, que el sistema tiene d ₁ ... d _n soluciones, siempre que no haya raíces múltiples 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 ocurre en el siguiente sistema, que tiene tres soluciones.

${\displaystyle {\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}}$

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 ).

También existe un algoritmo específico para el caso cero-dimensional que, en este caso, compite 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 de Gröbner lexicográfica mediante el algoritmo FGLM ^{[ 5 ]} y, finalmente, aplicar el algoritmo Lextriangular ^{[ 6 ] .}

Esta representación de las soluciones resulta muy conveniente para coeficientes en un campo finito. Sin embargo, para coeficientes racionales, hay que tener en cuenta dos aspectos:

• El resultado puede contener números enteros muy grandes, lo que puede dificultar el cálculo y el uso del resultado.
• Para deducir los valores numéricos de las soluciones a partir de la salida, hay que resolver polinomios univariados con coeficientes aproximados, lo cual es un problema altamente inestable.

El primer problema fue resuelto por Dahan y Schost: ^{[ 7 ] [ 8 ]} Entre los conjuntos de cadenas regulares que representan un conjunto dado de soluciones, existe un conjunto cuyos coeficientes están explícitamente acotados en función del tamaño del sistema de entrada, con una cota casi óptima. Este conjunto, denominado descomposición equiprojectable , depende únicamente de la elección de las coordenadas. Esto permite el uso de métodos modulares para calcular eficientemente la descomposición equiprojectable. ^{[ 9 ]}

The second issue is generally solved by outputting regular chains of a special form, sometimes called shape lemma, for which all d_i but the first one are equal to 1. For getting such regular chains, one may have to add a further variable, called separating variable, which is given the index 0. The rational univariate representation, described below, allows computing such a special regular chain, satisfying Dahan–Schost bound, by starting from either a regular chain or a Gröbner basis.

The rational univariate representation or RUR is a representation of the solutions of a zero-dimensional polynomial system over the rational numbers which has been introduced by F. Rouillier.^[10]

A RUR of a zero-dimensional system consists in a linear combination x₀ of the variables, called separating variable, and a system of equations^[11]

${\displaystyle {\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}}$

where h is a univariate polynomial in x₀ of degree D and g₀, ..., g_n are univariate polynomials in x₀ of degree less than D.

Given a zero-dimensional polynomial system over the rational numbers, the RUR has the following properties.

• All but a finite number linear combinations of the variables are separating variables.
• When the separating variable is chosen, the RUR exists and is unique. In particular h and the g_i are defined independently of any algorithm to compute them.
• The solutions of the system are in one-to-one correspondence with the roots of h and the multiplicity of each root of h equals the multiplicity of the corresponding solution.
• The solutions of the system are obtained by substituting the roots of h in the other equations.
• If h does not have any multiple root then g₀ is the derivative of h.

For example, for the system in the previous section, every linear combination of the variable, except the multiples of x, y and x + y, is a separating variable. If one chooses t = ⁠x – y/2⁠ as a separating variable, then the RUR is

${\displaystyle {\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}}$

La RUR se define de forma única para una variable separadora dada, independientemente de cualquier algoritmo, y conserva las multiplicidades de las raíces. Esta es una diferencia notable con las descomposiciones triangulares (incluso la descomposición equiprojectable), que, en general, no conservan las multiplicidades. La RUR comparte con la descomposición equiprojectable la propiedad de producir un resultado con coeficientes de tamaño relativamente pequeño.

Para sistemas de dimensión cero, el método RUR permite recuperar los valores numéricos de las soluciones resolviendo un único polinomio univariado y sustituyéndolos en funciones racionales . Esto permite obtener aproximaciones certificadas de las soluciones con cualquier precisión.

Además, el polinomio univariado h ( x₀ ) de la RUR puede factorizarse, lo que proporciona una RUR para cada factor irreducible. Esto ofrece la descomposición prima del ideal dado (es decir, la _{descomposición} primaria del radical del ideal). En la práctica, esto proporciona un resultado con coeficientes mucho menores, especialmente en el caso de sistemas con multiplicidades elevadas.

A diferencia de las descomposiciones triangulares y las descomposiciones equiprojectables, la RUR no se define 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 prefieren los métodos específicos, ya que los generales no suelen permitir encontrar todas las soluciones. En particular, cuando un método general no encuentra ninguna solución, esto no suele indicar que no exista ninguna.

Sin embargo, cabe mencionar aquí dos métodos.

• El método de Newton puede utilizarse si el número de ecuaciones es igual al número de variables. No permite hallar todas las soluciones ni demostrar que no existe ninguna. Sin embargo, es muy rápido cuando se parte de un punto cercano a una solución. Por lo tanto, constituye una herramienta fundamental para el método de continuación homotópica que se describe a continuación.
• La optimización rara vez se utiliza para resolver sistemas polinómicos, pero alrededor de 1970 logró demostrar que un sistema de 81 ecuaciones cuadráticas con 56 variables no es inconsistente. ^{[ 12 ]} Con los demás métodos conocidos, esto sigue estando fuera del alcance de la tecnología moderna, a fecha de 2022. Este método consiste simplemente en minimizar la suma de los cuadrados de las ecuaciones. Si se encuentra cero como mínimo local, entonces se alcanza en una solución. Este método funciona para sistemas sobredeterminados, pero no produce información si todos los mínimos locales encontrados son positivos.

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 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, digamos . ${\displaystyle N}$

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, el mismo número de ecuaciones y la misma estructura general que el sistema a resolver . ${\displaystyle g_{1}=0,\,\ldots ,\,g_{n}=0}$${\displaystyle N}$${\displaystyle n}$${\displaystyle n}$${\displaystyle f_{1}=0,\,\ldots ,\,f_{n}=0}$

Luego 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.

${\displaystyle (1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0}$.

La continuación homotópica 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 . Si es demasiado grande, la convergencia de Newton puede ser lenta e incluso puede saltar de una ruta de solución a otra. Si es demasiado pequeño, el número de pasos ralentiza el método. ${\displaystyle t}$${\displaystyle N}$${\displaystyle t=1}$${\displaystyle t_{1}<t_{2}}$${\displaystyle t=t_{2}}$${\displaystyle t=t_{1}}$${\displaystyle t_{2}-t_{1}:}$

Deducir los valores numéricos de las soluciones de una ecuación diferencial recurrente parece sencillo: basta con calcular las raíces del polinomio univariado y sustituirlas en las demás ecuaciones. Sin embargo, esto no es tan fácil, ya que la evaluación de un polinomio en las raíces de otro polinomio es altamente inestable.

Por lo tanto, las raíces del polinomio univariado deben calcularse con alta precisión, la cual no siempre se define de una sola vez. Existen dos algoritmos que cumplen con este requisito.

• El método de Aberth , implementado en MPSolve , calcula todas las raíces complejas con cualquier precisión.
• El algoritmo de Uspensky de Collins y Akritas ^{[ 14 ]} , mejorado por Rouillier y Zimmermann ^{[ 15 ]} y basado en la regla de los signos de Descartes , calcula las raíces reales, aisladas en intervalos de ancho arbitrariamente pequeño. Está implementado en Maple (funciones fsolve y RootFinding[Isolate] ).

Existen al menos cuatro paquetes de software capaces de resolver sistemas de dimensión cero automáticamente (por automático, se entiende que no se requiere 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 ser útiles para resolver sistemas de dimensión cero. Algunos de ellos se enumeran después de los solucionadores automáticos.

La función RootFinding[Isolate] de Maple toma como entrada cualquier sistema polinómico sobre los números racionales (si algunos coeficientes son números de coma flotante , se convierten a números racionales) y devuelve las soluciones reales representadas (opcionalmente) como intervalos de números racionales o como aproximaciones de coma flotante de precisión arbitraria. Si el sistema no es de dimensión cero, 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 univariada racional, a partir de la cual se deduce la aproximación requerida de las soluciones. Funciona de forma rutinaria para sistemas con hasta varios cientos de soluciones complejas.

La representación univariada racional se puede calcular con la función Groebner[RationalUnivariateRepresentation] de Maple .

Para extraer todas las soluciones complejas de una representación univariada 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 en cada iteración, hasta que las soluciones se estabilicen, 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 homotópica. Este solucionador calcula las soluciones complejas aisladas de sistemas polinomiales con 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 homotópica 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 polinomiales mediante cadenas regulares .

• Teoría de la eliminación
• Sistemas de desigualdades polinómicas
• Descomposición triangular
• Método de Wu para el conjunto de características