Resolución de sistemas de ecuaciones no lineales con bases de Gröbner

Índice

Introducción

Las bases de Gröbner son un conjunto finito de polinomios de múltiples variables. En el presente trabajo se hará uso de las bases de Gröbner para el caso particular de la resolución de las ecuaciones de consistencia de un método de Runge-Kutta explícito de orden 2 y 3.

Los sistemas de ecuaciones a resolver son los siguientes:

• Orden 2 con 2 etapas:

Sistema con dos ecuaciones y tres incógnitas.

• Orden 3 con 3 etapas:

Sistema con cuatro ecuaciones y seis incógnitas.

Ambos sistemas de ecuaciones cuentan con más incógnitas que ecuaciones, por lo que en principio, tienen infinitas soluciones. La opción más común para la resolución de estos sistemas podría ser resolverlo por sustitución y dejar el resultado en función de un parámetro en el primer caso y de dos en el segundo.

El resultado obtenido haciendo uso de las bases de Gröbner tiene que ser equivalente a cualquier otro resultado obtenido mediante cualquier otra técnica.

En general, el procedimiento de las bases de Gröbner consiste en generar un ideal que es un conjunto de ecuaciones que tiene la misma solución que el sistema original pero de más fácil solución.

Matriz de Silvester

Sean los siguientes polinomios de una variable y coeficientes en un cuerpo *,

f(x) = a0 + a1 ·x + … + ak · xk

g(x) = b0 + b1 · x + … + bl ·xl

con ak y bk no nulos, interesa conocer cuándo el sistema:

tiene solución. Una respuesta inmediata nos dice que el sistema admite solución si y sólo si el grado del máximo divisor de f(x) y g(x) es mayor o igual a uno. En efecto, si la solución x* existe, entonces x será primo común de f(x) y g(x). Además el polinomio x-x* dividirá a cada ecuación del sistema.

Se define la matriz de Silvester para los polinomios f(x) y g(x) de la siguiente manera :

Esta matriz es cuadrada y, por tanto, se puede calcular su determinante. De hecho, el determinante de esta matriz es conocido como el Resultante de los polinomios f(x) y g(x) y se expresa como Res(f,g).

Se puede demostrar que si Syl(f,g) es invertible, entonces f(x) y g(x) son primos entre sí. Por lo tanto no tienen raíces comunes. En este caso, el sistema no admite solución.

Si Syl(f,g) es singular, se pueden obtener dos polinomios p(x) y q(x) con grad(p)<grad(g) y grad(q)<grad(f) tales que p(x)f(x)+q(x)g(x) = 0. En este caso sí hay solución.

En general, el sistema no tiene solución si y sólo si existen los polinomios pi(x) tales que .

Esto se puede generalizar para un sistema de ecuaciones polinómicas de varias variables de la siguiente manera:

Dado un sistema de polinomios de la forma , es necesario y suficiente que existan unos polinomios , tales que:

para que el sistema no tenga solución.

Ordenación de monomios

El cálculo de las bases de Gröbner varía sustancialmente cuando se usan diferentes ordenaciones de los monomios que integran el sistema de ecuaciones original. Consideraremos polinomios en las variables x1,x2,...,xn. Para ordenar dichas variables, asumiremos que:

x1 > x2 > x3 > ... > xn

La ordenación lexicográfica (lex) se define como si y solo si el elemento más a la izquierda no nula en el vector es positivo. Se tomarán  y  como los vectores que contienen las potencias de los monomios en las variables incluidas en el sistema.

Ejemplo:

El monomio tiene un vector , el monomio tiene un vector =(3,4,3), por lo que = (2,-2,0). Como la primera componente del vector resta distinto de cero es mayor que cero, el primer monomio es mayor en una ordenación lexicográfica.

Reducción polinómica

La reducción polinómica es la piedra angular del algoritmo de las bases de Gröbner y es, de hecho, la parte que mayor complejidad computacional acarrea.

Se dice que un polinomio g reduce a otro polinomio h módulo algún conjunto de polinomios F (expresado como ) si y sólo si LT(g) puede eliminarse por la sustracción de un múltiplo apropiado de: un polinomio f en F, un monomio u donde u=LM(g)/LM(f) y un escalar b=LC(g)/LC(f) obteniéndose h, donde:

LM(g) es el monomio principal de g: LM(g)=xmultigrado(g), siendo multigrado(g)= máx.

LC(f) es el coeficiente principal de f, definido como LC(f)= amultigrado(f)..

LT(g) es el término principal de g, definido como LM(g)·LC(g)

Un ejemplo de todos estas definiciones es:

Sea:

Si se ordena el polinomio lexicográficamente, se obtiene:

Ocurre que si y sólo si existe un f " F, b, y u tales que h=g-buf. En cualquier otro caso g es irreducible módulo F. Esto se puede expresar de la siguiente manera:

g es irreducible módulo G si ningún monomio principal de un elemento de F divide al monomio principal de g.

Por otra parte, si g es irreducible módulo F, entonces se puede restar de él un múltiplo de un elemento de F para eliminar su monomio principal y para obtener un nuevo monomio principal menor que el monomio principal de g. Este nuevo polinomio es equivalente a g con respecto al ideal generado por F.

Un ideal es un subconjunto I del anillo de polinomios K[x1, x2,..., xn] si satisface lo siguiente:

1.0 es un elemento de I

2.Si f y g son dos elementos cualesquiera de I, entonces f+g es también un elemento de I

3.Si f es un elemento de I, entonces para cualquier h en K[x1, x2,..., xn] h·f es también un elemento de I.

Un ejemplo de esto es:

Con:

Además:

Estos polinomios están ya ordenados lexicográficamente con x>y. Si se elige:

Entonces se obtiene el polinomio h=g-buf=, con lo que .

La definición de reducción de polinomio implica sólo al termino principal de g. Sin embargo es posible eliminar otros monomios de g para hacer la combinación lineal más pequeña. Esto conduce a la siguiente definición:

Un polinomio g es completamente reducible con respecto a F si ningún término de g es divisible por ninguno de los LT(fi) para todos los fi " F. Con un ejemplo:

Sea F={f1,f2) con:

Si g=, estando los polinomios ordenados lexicográficamente (con x>y), se ve claramente que g es reducible módulo F. Si se continúa con el proceso de reducción, se puede llegar fácilmente a que es irreducible módulo F. En este punto se dice que h es la forma normal de g.

Como se puede ver, una forma de reducir un conjunto de polinomios módulo polinómico consiste en generalizar el algoritmo de la división para todos los polinomios. Esto se puede expresar de la siguiente manera:

Si f,g "k[x1] y g"0, entonces existe unos únicos q y r "k[x1] tales que f=qg+r y ó r=0 o bien grad(r)<grad(g).

Para generalizar el algoritmo de la división se necesita dividir un polinomio f perteneciente al conjunto inicial de polinomios por un conjunto de polinomios F=f1,...,fs"k[x1,...xn]. Formalmente:

Sea F=(f1,...fs) una s-tupla ordenada de polinomios en k[x1,...,xn]. Entonces si f es un polinomio en k[x1,...,xn], entonces existen q1,...,qx, r " k[x1,...,xn] tales que f=q1f1+...+qsfs+r y, o r=0 o r es un polinomio completamente reducido.

Un término que cumple un rol esencial en la teoría de las bases de Gröbner es el concepto de los S-polinomios. Es sabido que el mínimo común múltiplo (m.c.m.) de dos monomios es el producto de todas las variables, cada una elevada a la potencia máxima que aparezca en ambos monomios. Entonces, dados dos polinomios, f y g, si J=m.c.m.{LM(f), LM(f)}, se definen los S-polinomios de f y g como:

S-poli(f,g)=

Como J/LT(f) y J/LT(g) son monomios, entonces el S-polinomio(f,g) es una combinación lineal con los coeficientes de f y g y pertenece al mismo ideal generado por f y g. Los S-polinomios son productos en cruz de los términos principales y se construyen para cancelar dichos términos: los términos principales de los dos componentes de S-poli(f,g) son iguales y se cancelan. Ejemplo:

Sea:

Con:

Ordenados lexicográficamente con x>y>z

Entonces LM(f1)=xy2z y LM(f2)=x2yz, por lo que J=m.c.m.{ xy2z, x2yz}=x2y2z. Con esto:

Definición de base de Gröbner

A continuación se definirán las bases de Gröbner. Existen diferentes definiciones, por supuesto equivalentes.

Según Buchberger, dado un conjunto finito de polinomios, F, es una base de Gröbner si y sólo si para todo g, h1 y h2 si h1 y h2 son formas normales de g módulo F, entonces h1= h2.

Un generador G de un ideal se llama base de Gröbner si y sólo si "f " se tiene que . Esta es otra forma de definir una base de Gröbner.

Si F es un conjunto finito de polinomios e I el ideal generado por F, las siguientes afirmaciones son equivalentes:

• F es una base de Gröbner

• "fi,fj"F: S-poli(fi,fj) se reduce a cero módulo F

• Toda reducción de un f perteneciente a I con respecto a F da siempre cero

De hecho, este criterio es el que proporciona la potencia a las bases de Gröbner como método para la resolución de sistemas de ecuaciones polinómicas. Para comprobar si una base es de Gröbner, todo lo que se tiene que hacer es calcular S-poli(fi,fj) y ver si se reduce a cero o no.

Otra utilidad de esto es que se obtienen las herramientas para construir las bases de Gröbner. Si un S-polinomio no se reduce a cero, todavía se puede añadir a la base sin modificar el ideal. Esto es porque es una combinación lineal de dos polinomios de la base. Una vez que se añade a la base, entonces se reducirá a cero.

Sin embargo, aparecerán nuevos S-polinomios. Este proceso es finito y es la esencia del algoritmo de Buchberger para el cálculo de las bases de Gröbner.

Algoritmo de Buchberger

El siguiente algoritmo para calcular las bases de Gröbner fue propuesto por Buchberger en su tesis doctoral. Desde entonces este algoritmo ha sido mejorado. Más adelante se expondrá una versión más reciente.

Algoritmo de Buchberger

Entrada: un conjunto de polinomios F={f1,...fn} que genera un ideal I

Salida: una base de Gröbner G={g1,...,g2} que es generada por I

Inicio

G ! F

M ! {{fi,fj}| fi,fj " G y fi " fj}

Repetir

{p,q} ! un par de M

M ! M - {(p,q)}

S ! S - poli(p,q)

h !FormaNormal(S,G)

Si h " 0 entonces

M ! M " {g,h} "g "G}

G ! G " {h}

hasta M = 0

fin

La idea del algoritmo es clara: se inicializa la base de Gröbner, G, con el conjunto inicial de polinomios. Se forma el conjunto M con todos los pares de polinomios en G. Se toma un par {p,q} de M y se calcula el S-polinomio de dicho par. Se reduce dicho S-polinomio módulo G quedando el polinomio h. Si h no es cero, se actualiza el conjunto de pares, M, añadiéndole el nuevo par {h,g} para todo g "G y se añade h a la base de Gröbner. Este proceso se repite hasta que cualquier h calculado sea nulo.

Un ejemplo de esto es:

Sea:

Donde:

Estos polinomios se han ordenado lexicográficamente con x > y > z.

Se hace: G = F. Así .

El conjunto M está formado por todos los pares posibles, en este caso: M ={(g1,g2)}. El único par que se puede tomar es (g1,g2), por lo que se elimina de M.

S-poli(g1,g2) = -12x2z4 - 7y3z y se reduce a g3=-21z3y2 - 7y3z, módulo .

Como g3 no es cero, se incluye en el conjunto generador, actualizándose M en este momento: M ={(g1,g2), (g2,g3)} y G ={g1,g2,g3)

Ahora hay que volver a calcular los S-polinomios de una pareja en M, por ejemplo, (g1,g3). S- poli(g1,g3) = 49y5 + 84x2y2z3 que se reduce a g4= 49y5 + 1323y2z6 módulo G ={g1,g2,g3}.Como g4 tampoco es cero, se incluye en el conjunto generador.

En este punto, G ={g1,g2,g3) y M ={(g2,g3), (g1,g4),(g2,g4),(g3,g4)}.

Volvemos a calcular los S-polinomios de las parejas (g2,g3), (g1,g4), (g2,g4) y (g3,g4). Si una vez hecho esto se reducen módulo G, se llega a la conclusión de que todos se reducen a cero módulo G.

Una vez llegados a este punto, termina el algoritmo, estando definida la base de Gröbner por: G ={g1,g2,g3,g4}

Se observa que el cálculo de los S-polinomios es inmediato, no siendo así el cálculo de la forma normal. Para este segundo caso existen numerosos algoritmos de cálculo, siendo uno de los más comunes el algoritmo de la división generalizada. Hay que hacer notar que este algoritmo no tiene varias de las propiedades que sí tiene el algoritmo de la división para el caso de una única variable, como son:

• El resto no está caracterizado únicamente por el requerimiento de que si no es cero, entonces uno de sus términos es divisible por LT(fi) para toda i.

• Los qi no son únicos y cambian si los fi son reordenados

• No resuelve el problema de la determinación de la pertenencia al ideal.

El algoritmo de la división generalizada es:

Entrada: un conjunto de polinomios F={f1,...,fs} y un polinomio distinto de cero, f.

Salida: El resto, r, de dividir f por F

Los cocientes q1,...,qs tales que f=q1f1+...+qsfs+r con r = 0 o bien r un polinomio completamente reducido respecto a F.

Inicio

qi ! 0 desde i=1 hasta s

r ! 0

p ! f

Repetir

i ! 1

dividir ! verdadero

mientras (i"s) y (dividir=verdadero) hacer

si LT(fi) divide a LT(p) entonces

u ! LT(p)/LT(fi)

qi ! qi + u

p ! p-u·fi

dividir ! falso

en otro caso

i ! i + 1

si (dividir=verdadero) entonces

r ! r + LT(p)

p ! p-LT(p)

hasta (p = 0)

Este algoritmo procede como el clásico. Mientras que el término principal de un divisor divide al término principal de un dividendo intermedio, el algoritmo procede como en el caso de una variable. En otro caso, el algoritmo elimina el término principal del dividendo intermedio y lo añade al resto.

Mejora al algoritmo de cálculo de las bases de Gröbner

El algoritmo de Buchberger expuesto es correcto para el cálculo de las bases de Gröbner. Sin embargo, el propio Buchberger apreció que, con ciertas modificaciones, se podía reducir el número de cálculos necesarios a la vez que el resultado obtenido era más compacto.

Partiendo de que si LM(gi) divide a LM(gj) entonces gj se puede eliminar de la base y que una vez que el S-polinomio se reduce a cero siempre se reducirá a cero siendo innecesario recalcular y reducirlo en las subsecuentes pasadas del bucle, Buchberger expuso tres criterios muy efectivos a la hora de reducir el tiempo de cálculo:

• Criterio I: En el proceso de elegir un par {fi,fj} elegirlo de tal manera que el mínimo común múltiplo de LM(fi) y LM(fj) sea mínimo entre todos los pares.

• Criterio II: Si LM(fi) y LM(fj) son primos entre sí, entonces el S-poli(fi,fj) se reduce a cero y puede ser eliminado. Así, elegir un par tal que LM(fi) y LM(fj) no son primos entre sí.

• Criterio III: Si hay un elelmento fk de la base tal que LM(fk) divide al mínimo común múltiplo de LM(fi) y LM(fj) y si el S-poli(fi,fk) y S-poli(fj,fk) ya han sido considerados, entonces S-poli(fi,fj) se reduce a cero y puede ser eliminado.

Se expresarán los criterios según sigue:

Criterio I: (fi,fj) ! LCM(LM(fi),LM(fj)) es de grado mínimo

Criterio II: (fi,fj) ! LCM(LM(fi),LM(fj)) " LM(fi)·LM(fj)

Criterio III: (fi,fj,G) ! "fk " G tales que fi " fk y fj " fk, LCM(LM(fi),LM(fj)) es múltiplo de LM(fk), S-poli(fi,fk) y S-poli(fj,fk) han sido anteriormente considerados.

Entonces el algoritmo modificado de Buchberger es:

Entrada: un conjunto de polinomios F={f1,...fn} que genera un ideal I

Salida: una base de Gröbner G={g1,...,g2} que es generada por I

Inicio

G ! F

t ! s

Reducir G y formar M ! {{fi,fj}| 1 " i " j " s}

Repetir

{fi,fj} ! un par de M con el criterio I

Si (criterioII(fi,fj) y no criterioIII(fi,fj,G)) entonces

S ! S - poli(fi,fj)

h !FormaNormal(S,G)

Si h " 0 entonces

t ! t + 1

ft ! h

M ! M " {{fi,fj} "1 " i " t-1}

G ! G " {ft}

M ! M-{{fi,fj}}

reducir G y actualizar M

hasta M = 0

fin

Esta modificación del algoritmo reduce sustancialmente el coste computacional con respecto a la primera versión del mismo.

Hay que hacer notar que en el caso de sistemas de varias variables, el algoritmo de las bases de Gröbner, cuando se usa la ordenación lexicográfica, elimina sucesivamente las variables en las ecuaciones resultantes de manera análoga a como hace la eliminación gaussiana.

Resolución de las ecuaciones de consistencia para un método de Runge-Kutta mediante bases de Gröbner.

Hasta ahora se ha presentado el método de reducción de sistemas de ecuaciones mediante bases de Gröbner. Es el momento de aplicar lo visto al problema que nos atañe. Como se expuso en el capítulo introductorio, los sistemas de ecuaciones a resolver son los siguientes:

• Orden 2 con 2 etapas:

Sistema con dos ecuaciones y tres incógnitas.

• Orden 3 con 3 etapas:

Sistema con cuatro ecuaciones y seis incógnitas.

Resolución del problema de segundo orden

Para la resolución del problema se hará uso del programa informático Mathematica en su versión 3.0 que incluye una función para el cálculo simbólico de las bases de Gröbner. La orden GroebnerBasis está basada en el algoritmo de Buchberger convenientemente adaptado y optimizado.

En el primer caso, Runge-Kutta explícito de orden 2, la solución al sistema es obvia. Al ser un sistema con dos ecuaciones y tres incógnitas, existen infinitas soluciones y estas pueden expresarse en función de un único parámetro.

Al ejecutar la orden GroebnerBasis, el programa devuelve el mismo conjunto de polinomios. Esto indica que el ideal está formado por esos mismos polinomios y no cabe una mayor simplificación. Se obtiene el mismo resultado si se llevan a cabo las operaciones de manera manual, obviamente.

Para encontrar una solución única, se podría aumentar el número de ecuaciones haciendo uso de la formulación de Runge-Kutta de orden tres con dos etapas también e integrando una de las ecuaciones en el sistema original. En este caso, haciendo uso de Mathematica se obtiene dicha ecuación “extra”:

Empleando la orden GroebnerBasis, Mathematica devuelve:

La solución de este sistema de ecuaciones es única y muy fácil de obtener:

Resolución del problema de tercer orden

Éste caso es un poco más complicado. Para la resolución se actuará de manera totalmente análoga al caso anterior.

Con tercer orden y tres etapas se obtiene un sistema de cuatro ecuaciones con seis incógnitas. Aparecen, por tanto, infinitas soluciones (si es que existen). Para la caracterización del sistema de soluciones, se pueden emplear dos parámetros.

El paquete informático Mathematica proporciona la siguiente base de Gröbner para este sistema:

Aunque parezca un poco aparatoso, la resolución de este sistema de ecuaciones es muy sencilla si se toman como parámetros a32 y b3.

Mathematica puede resolver simbólicamente este sistema con la orden Solve de manera análoga a como se hizo en el apartado anterior. El resultado obtenido por este programa es el siguiente:

Se obtienen dos parejas de soluciones. Igual que en el caso anterior, para obtener una solución concreta se puede hacer uso de un método de Runge-Kutta de orden mayor y mismo número de etapas. Operando igualmente con el paquete informático se añaden al sistema original las siguientes ecuaciones:

Si se añaden dos de estas ecuaciones a la orden de cálculo de las bases de Gröbner hacen que el resultado de esta operación sea (añadiendo la primera y la tercera):

Y la solución es, por tanto:

Conclusiones

Ha quedado patente que el método de bases de Gröbner para reducir la complejidad de un sistema de ecuaciones es útil en casos en los que los sistemas están compuestos por polinomios en varias variables teniendo, a priori, una solución engorrosa de calcular mediante los métodos tradicionales.

No se ha de olvidar que el cálculo de las bases de Gröbner con el algoritmo de Buchberger es relativamente tedioso pero, gracias al uso de los computadores, esta tarea puede llevarse a cabo con relativa facilidad.

Sin embargo, una de las limitaciones del método propuesto por Gröbner consiste en la limitación de su uso a sistemas de ecuaciones polinómicas en varias variables. No es posible su uso en sistemas que contengan ecuaciones que no sean polinómicas teniendo, en ese caso que elegirse un método alternativo.

Anexo 1: Sobre la existencia de soluciones en los sistemas de ecuaciones polinómicos planteados.

Es interesante realizar un estudio acerca de existencia o no de soluciones en los sistemas de ecuaciones no lineales que se han planteado. El problema que se plantea es relativamente sencillo cuando los polinomios implicados sólo contienen una variable. Sin embargo, cuando se ven envueltos polinomios con más de una variable, se deben aplicar métodos más complejos para aclarar la existencia o no de soluciones.

El proceso que se debe seguir es el siguiente:

Plantear el sistema de ecuaciones a resolver

Comprobar si existen tantas ecuaciones como incógnitas.

• Si es así, aplicar algún criterio para conocer la existencia o no de soluciones

• Si existen más incógnitas que ecuaciones, aplicar algún criterio que permita conocer cuáles son las variables que se deben tomar como parámetros para asegurar, en la medida de lo posible, la existencia de una solución.

Encontrar dicha solución

Existen varios criterios que permiten dilucidar si un sistema de ecuaciones no lineales tiene o no solución. Entre ellos está el empleo de la matriz de Sylvester, como se indicó en el aparatado correspondiente.

La definición de esta matriz es la siguiente:

El resultante de dos polinomios se define como:

Con el teorema de eliminación de Kronecker se puede generalizar el resultado obtenido para polinomios de una variable a polinomios de varias variables de manera que la invertibilidad de la matriz de Sylvester define la existencia de las soluciones.

Desde este punto de vista, para el caso Runge-Kutta de orden dos con dos etapas, explícito, se tiene:

Para mayor facilidad de lectura se hará la siguiente sustitución de variables que, obviamente no afecta en nada al problema:

El sistema será, por tanto:

Calculamos la matriz de Sylvester:

El determinante de esta matriz es:

Igualando a cero obtenemos una condición para que el sistema original tenga solución:

Se obtiene como condición una de las ecuaciones de partida. Esto es debido a la simplicidad del sistema del que se parte. Igualmente se puede proceder con las otras variables del sistema:

Con la x:

La condición resultante también coincide con una de las ecuaciones de partida, lo cual era de esperar debido a la simplicidad del sistema.

Con la y:

Para encontrar una solución a este sistema, basta con usar una de las variables como parámetro.

Para el sistema de ecuaciones correspondiente al método de Runge-Kutta de tercer orden y tres etapas,

se precisan dos parámetros. En este caso habrá que dilucidar cuáles de las variables serán apropiadas como parámetros para llegar a una solución.

19