Uso de Gröbner bases para la resolución de ecuaciones polinómicas

Question

En mis intentos para entender cómo álgebra computacional los sistemas de "hacer cosas", traté de cavar a su alrededor un poco sobre las bases de Gröbner, que se describen en casi todas partes como "una generalización del algoritmo de Euclides y la eliminación Gaussiana". He tratado de buscar ejemplos de bases de Gröbner en la acción, pero han sido incapaces de encontrar cualquier (que puede ser fácilmente entendido).

Yo podría seguir adelante y acaba de pedir una explicación con ejemplos de la gente, pero voy a ir un paso más allá.

Plano General cónicas puede ser representada por la ecuación Cartesiana

$ax^2+2bxy+cy^2+dx+fy+g=0$

Un problema común en el trato con los cónicos es averiguar si dos cónicas se cruzan, y si es así, donde el punto de intersección(s). Generalmente, uno puede hacer todo esto mediante la eliminación de variables en consecuencia.

Ahora yo pregunto: ¿cómo sería, digamos, Buchberger del método, proceder a la determinación de si dos cónicas se cruzan y, a continuación, encontrar donde se intersectan?

Answer 1

Con el fin de encontrar las soluciones del sistema de cónicas que usted menciona, es suficiente para dar un procedimiento para encontrar la proyección de la simultánea desaparición de conjunto de las dos cónicas en algún eje, por ejemplo, el $$y-eje: las coordenadas de la proyección sobre el $$y-eje son los $$y-coordenadas de los puntos de intersección. Sabiendo que les permite sustituir de nuevo en las ecuaciones los valores de $ $ y$ y resolver un sistema de ecuaciones con una sola variable $x$, con lo que el problema más simple. En términos de ideales, supongamos que podemos encontrar un elemento no nulo de $r$ en el ideal generado por los dos cónicas, que sólo depende de una sola variable, por ejemplo $y$. Esto significa que todas las soluciones del sistema ha $y$-coordinar la satisfacción de las polinomio $r$. Así nos han limitado las opciones para el $$y-coordenadas de la intersección (es decir, que todos han de satisfacer el polinomio $r$) y, siempre que podemos, de hecho, resolver el polinomio $r$ en una variable, luego podemos sustituir los diversos valores de $$ y se encontró de nuevo en la inicial de ecuaciones y resolver para $x$, de nuevo, usando nuestro algoritmo para resolver polinomios de una sola variable. Tan lejos, tan buena, te esperamos!!! La pregunta es cómo producir el elemento $r$. Aquí es donde las bases de Gröbner vienen en.

Con el fin de hacer el cálculo de preguntar, uno tendría que elegir una adecuada monomio orden. Voy a pasar por alto esto, y simplemente "hacer lo obvio". Es un ejercicio para que usted pueda averiguar que el fin de utilizar de manera que el cómputo voy a hacer es en realidad un Gröbner bases de cálculo. Dispersos por todo el cálculo habrá también un par de casos especiales que no voy a tratar con: una vez más, usted puede tratar eso como ejercicios para usted!

En primer lugar, voy a elegir una base genérica, de modo que el primero tiene la forma cónica $$ x^2 + \alpha x + \beta , $$ donde $\alpha$ y $\beta$ son polinomios en $$ y solo (estoy tratando de simplificar la notación tanto como sea posible; la única "suposición de que he hecho es que el coeficiente de $x^2$ es distinto de cero, que puede ser organizado a menos que el "cónica" es definida por un polinomio de grado a lo más uno).

En base a esto, la segunda ecuación se puede asumir que no tienen $x^2$ plazo (de hecho, la eliminación de la $x^2$ plazo, utilizando la primera ecuación sería el primer paso en cualquier razonable de Gröbner base de cálculo en el que el término $x^2$ es el mayor plazo a la vista). Por lo tanto voy a escribir la segunda cónica como $$ \gamma x + \delta $$ donde, como antes, $\gamma$ y $\delta$ son polinomios en $$ y solo. De nuevo, sólo para revisión en un caso concreto, voy a asumir que el polinomio $\gamma$ es distinto de cero. (Si $\gamma$ cero, entonces tendríamos un polinomio en el ideal generado por los dos cónicas que sólo depende de $ $ y$: este era nuestro objetivo al principio de todos modos! Obviamente, usted debe preocuparse el caso de que $\gamma=\delta=0$, pero yo no.)

Para calcular una base de Gröbner, ahora tendría que calcular S-polinomios: vamos a hacerlo aquí también. Voy a probar a eliminar el $x^2$ el término de la primera ecuación, utilizando la segunda ecuación. Esto es fácil: multiplicar la primera ecuación por $\gamma$ y el segundo por $x$ y tomar la diferencia: nos quedamos con la ecuación $$ (\alpha \gamma \delta) x + \beta \gamma . $$ Ahora vamos a eliminar la $x$ plazo de esta última ecuación, utilizando de nuevo la segunda ecuación: multiplicar la segunda ecuación por $(\alpha \gamma \delta)$, la última ecuación por $\gamma$ y restar para obtener $$ \delta^2 - \alpha \gamma \delta + \beta \gamma^2 . $$ Hemos encontrado una expresión independiente de $x$!! Hemos terminado... siempre que esta expresión no es idéntica a cero. Usted puede averiguar lo que esto significa y lo que sucede en este caso. Tenga en cuenta también que la expresión final es lo que hubiéramos obtenido si, al principio, le había "resuelto" $x=-\frac{\delta}{\gamma}$ usando la segunda ecuación, se sustituye en la primera ecuación y despejamos el denominador.

Espero que este "híbrido" cálculo se explica lo que está pasando: las bases de Gröbner y el algoritmo de Buchberger son una forma sistemática de "resolver" los sistemas de ecuaciones. Usted no tiene que hacer cualquier pensamiento, una vez configurado el problema. Pero es necesario establecer el problema, por lo que calcula lo que desea. En este caso, se podría haber utilizado varios atajos para llegar a la respuesta, sin seguir todos los pasos. En las situaciones más complicadas, el algoritmo de Buchberger podría ser la mejor manera de mantener un seguimiento de todos los pasos a seguir.

Permítanme comentar también que, excepto en el caso en el que usted tiene una computadora haciendo los cálculos para usted, es muy poco probable que las bases de Gröbner le va a ayudar con una pregunta específica, a menos que usted también podría haber encontrado trucos simples para resolver de inmediato.

Answer 2

Usted tiene ro leer el libro[David R. Cox, John B. Poco y No O'Shea, los Ideales, las Variedades, los Algoritmos].

En cualquier caso, si usted comienza con un sistema de ecuaciones polinómicas y calcular una base de Groebner del ideal que generan, se obtiene un "máximo triangular" sistema de ecuaciones es equivalente a la original---es por eso bases de Groebner generalizar eliminación Gaussiana.

Permítanme hacer un ejemplo simple del uso de Macaulay 2. Consideremos el anillo de $\mathbb Q[x,y,z]$:

i1 : R = QQ[x, y, z, MonomialOrder => Lex]

o1 = R

o1 : PolynomialRing

el Fermat quintic superficie de $x^5+y^5+z^5=1$, cuyo ideal es

i2 : surface = ideal (x^5 + y^5 + z^5 - 1)

             5    5    5
o2 = ideal(x  + y  + z  - 1)

o2 : Ideal of R

y la curva de $x^2=y^2$, $y^3+1=z^3$:

i3 : curve = ideal (x^2 - y^2, z^3 - y^3 - 1)

             2    2     3    3
o3 = ideal (x  - y , - y  + z  - 1)

o3 : Ideal of R

El ideal de la intersección de la superficie y la curva es la suma de los ideales de la intersecands:

i4 : intersection = curve + surface

              2    2     3    3       5    5    5
o4 = ideal (x  - y , - y  + z  - 1, x  + y  + z  - 1)

o4 : Ideal of R

El número de puntos en la intersección, contando multiplicidades, es el grado de la ideal:

i5 : degree intersection

o5 = 30

si podemos ahora calcular el grado del radical del ideal, se obtiene un número menor, por lo que no todos los puntos son simples:

i6 : degree radical intersection

o6 = 25

Ahora mira en el lexicográfica de base de Groebner del ideal de la intersección:

i7 : ideal gens gb intersection

              17      16      15      14      13      12       11       10      9      8       7       6      5      4      3  
o7 = ideal (9z   + 27z   + 54z   + 50z   + 15z   - 63z   - 104z   - 108z   - 35z  + 35z  + 108z  + 104z  + 63z  - 15z  - 50z  -
     ----------------------------------------------------------------------------------------------------------------------------
        2                 5            16      15      14      13      12       11      10      9       8      7       6       5
     54z  - 27z - 9, 20y*z  - 20y + 27z   + 18z   + 45z   - 75z   - 35z   - 164z   + 79z   - 10z  + 230z  - 10z  + 119z  - 164z 
     ----------------------------------------------------------------------------------------------------------------------------
          4       3      2              3    3                                       16        15        14        13        12  
     - 35z  - 155z  + 45z  + 18z + 67, y  - z  + 1, 50x*z - 50x + 50y*z - 50y + 1242z   + 2718z   + 4770z   + 2220z   - 1235z   -
     ----------------------------------------------------------------------------------------------------------------------------
          11        10        9        8        7        6        5        4        3        2                 2    2
     7979z   - 7481z   - 6010z  + 1810z  + 5240z  + 9394z  + 5346z  + 1240z  - 4030z  - 4005z  - 2657z - 583, x  - y )

o7 : Ideal of R

El primer generador sólo depende de a $z$. La segunda y la tercera, sólo en $z$ y $y$, y el cuarto depende (linealmente) en $x$. Este es un "triangular" sistema de ecuaciones, a partir de la cual usted puede calcular los 30 puntos de intersección, suponiendo que llegar a resolver la primera ecuación para $z$, que es de grado 17...

Answer 3

El ejemplo que proponemos es un poco demasiado general para servir como una introducción pedagógica ejemplo (compárese, por ejemplo, el famoso Kahan SIGSAM problema 9 de la determinación de las condiciones para una elipse que estar dentro del círculo unidad). En su lugar, comenzar con uno de los primeros ejemplos históricos: de Gauss, la prueba de que cada simétrica polinomio se puede escribir de manera única como un polinomio en la primaria simétrica polinomios. Esta es una de la primera y la más simple de las aplicaciones de la reescritura de la reducción a través de una orden lexicographic. Para una buena presentación, consulte el Capítulo 7 de la Cox, Poco, O'Shea: los Ideales, las Variedades y los Algoritmos. También presentan generalizaciones para el anillo de invariantes de una matriz finita grupo $\rm G \subgrupo de GL(n,k)$. Usted puede encontrar en línea de los ejemplares de dicho libro a través de varios de ebook bases de datos.

Answer 4

Esta es una visión simplista de la versión de la base de Gröbner de cálculo y complementa Mariano respuesta. La idea detrás del algoritmo de Buchberger es construir una base, por lo que son para ser capaz de hacer "única división" entre no lineal de los polinomios. Esto se hace mediante el cálculo de (lo que se llama el) S-polinomio entre cualquiera de los 2 dados los polinomios hasta que no hay más producido.

Decide some ordering (grlex, lex, revlex)
Initialize I = <f1, f2> 
where we use the polynomials you gave above.
f_1=ax^2+2bxy+cy^2+dx+fy+g
f_2=ax^2+2bxy+cy^2+dx+fy+g
Set n=2

Repeat the following in a loop
    Iteratively choose any two polynomials ( f_i, f_j ) from set I 
    n = n + 1
    Compute f[n] = S-polynomial( f_i, f_j )
Until all S-polynomials return 0

Al final de la computación, usted tendrá un conjunto I = {f1,f2, ..., fk} tales que uno de los polinomios será en un solo término (es decir, 'x'). Resolver la ecuación para obtener la coordenadas de la intersección, y luego trabajar hacia arriba a través del resto de los polinomios.

La pregunta general es la relativa a la Eliminación de la teoría, y AFAIK hay tres métodos básicos ( no puedo hablar de su complejidad )

1. Gröbner base, como se ha visto anteriormente
2. Uso Resultantes (ejemplo abajo)
3. Wu método de los conjuntos de características, que no puedo decir mucho acerca de.

Si desea utilizar resultantes para encontrar la intersección de decir

E={f1(x, y,z), f2(x, y, z), f3(x, y, z)},

primero se debe calcular

E1 = {g1 = Resultant_in_x (f1, f2), g2 = Resultant_in_x(f2, f3)} 

y, a continuación,

E2 = { h1 = Resultant_in_y(g1, g2} }

El último polinomio h1 sería en una variable y susceptible de solución.

Answer 5

CIMAT conferencias de conferencia 3 de James Carlson de valor así como otro material en esta página puede encontrar:

http://www.Math.Utah.edu/~Carlson/CIMAT/