En álgebra, el máximo común divisor (frecuentemente abreviado como MCD) de dos polinomios es un polinomio, del mayor grado posible, que es factor de ambos polinomios originales. Este concepto es análogo al máximo común divisor de dos números enteros.
En el caso importante de polinomios univariados sobre un campo, el MCD polinomial se puede calcular, como para el MCD entero, mediante el algoritmo euclidiano que utiliza división larga . El polinomio MCD se define sólo hasta la multiplicación por una constante invertible.
La similitud entre el MCD de números enteros y el MCD polinómico permite extender a polinomios univariados todas las propiedades que se pueden deducir del algoritmo euclidiano y de la división euclidiana . Además, el polinomio MCD tiene propiedades específicas que lo convierten en una noción fundamental en diversas áreas del álgebra. Normalmente, las raíces del MCD de dos polinomios son las raíces comunes de los dos polinomios, y esto proporciona información sobre las raíces sin calcularlas. Por ejemplo, las raíces múltiples de un polinomio son las raíces del MCD del polinomio y su derivada, y cálculos adicionales del MCD permiten calcular la factorización libre de cuadrados del polinomio, lo que proporciona polinomios cuyas raíces son las raíces de una multiplicidad dada de el polinomio original.
El máximo común divisor puede definirse y existe, de manera más general, para polinomios multivariados sobre un campo o anillo de números enteros, y también sobre un dominio de factorización único . Existen algoritmos para calcularlos tan pronto como se tiene un algoritmo MCD en el anillo de coeficientes. Estos algoritmos proceden mediante una recursividad sobre el número de variables para reducir el problema a una variante del algoritmo euclidiano. Son una herramienta fundamental en el álgebra informática , porque los sistemas de álgebra informática las utilizan sistemáticamente para simplificar fracciones. Por el contrario, la mayor parte de la teoría moderna del MCD polinomial se ha desarrollado para satisfacer la necesidad de eficiencia de los sistemas de álgebra informática.
Sean p y q polinomios con coeficientes en un dominio integral F , típicamente un campo o los números enteros. Un máximo común divisor de p y q es un polinomio d que divide p y q , y tal que cada divisor común de p y q también divide d . Cada par de polinomios (no ambos cero) tiene un MCD si y sólo si F es un dominio de factorización único .
Si F es un cuerpo y p y q no son ambos cero, un polinomio d es un máximo común divisor si y sólo si divide tanto a p como a q , y tiene el mayor grado entre los polinomios que tienen esta propiedad. Si p = q = 0 , el MCD es 0. Sin embargo, algunos autores consideran que no está definido en este caso.
El máximo común divisor de p y q generalmente se denota como " mcd( p , q ) ".
El máximo común divisor no es único: si d es un MCD de p y q , entonces el polinomio f es otro MCD si y sólo si hay un elemento invertible u de F tal que y En otras palabras, el MCD es único hasta la multiplicación por una constante invertible.
En el caso de los números enteros, esta indeterminación se ha saldado eligiendo, como MCD, el único que es positivo (hay otro, que es su opuesto). Con esta convención, el MCD de dos números enteros es también el máximo común divisor (para el orden habitual). Sin embargo, dado que no existe un orden total natural para los polinomios en un dominio integral, no se puede proceder de la misma manera aquí. Para polinomios univariados sobre un campo, también se puede exigir que el MCD sea mónico (es decir, que tenga 1 como coeficiente de mayor grado), pero en casos más generales no existe una convención general. Por lo tanto, igualdades como d = mcd( p , q ) o mcd( p , q ) = mcd( r , s ) son abusos comunes de notación que deben leerse " d es un MCD de p y q " y " p y q tienen el mismo conjunto de MCD que r y s ". En particular, mcd( p , q ) = 1 significa que las constantes invertibles son los únicos divisores comunes. En este caso, por analogía con el caso de los números enteros, se dice que p y q sonpolinomios coprimos .
Hay varias formas de encontrar el máximo común divisor de dos polinomios. Dos de ellos son:
Para encontrar el MCD de dos polinomios usando factorización, simplemente factoriza los dos polinomios por completo. Luego, toma el producto de todos los factores comunes. En esta etapa, no necesariamente tenemos un polinomio mónico, así que finalmente multiplíquelo por una constante para convertirlo en un polinomio mónico. Este será el MCD de los dos polinomios, ya que incluye todos los divisores comunes y es mónico.
Ejemplo uno: Encuentre el MCD de x 2 + 7 x + 6 y x 2 − 5 x − 6 .
Por tanto, su MCD es x + 1 .
Factorizar polinomios puede resultar difícil, especialmente si los polinomios tienen un grado grande. El algoritmo euclidiano es un método que funciona para cualquier par de polinomios. Hace uso repetido de la división euclidiana . Cuando se utiliza este algoritmo con dos números, el tamaño de los números disminuye en cada etapa. Con los polinomios, el grado de los polinomios disminuye en cada etapa. El último resto distinto de cero, convertido en mónico si es necesario, es el MCD de los dos polinomios.
Más específicamente, para encontrar el mcd de dos polinomios a ( x ) y b ( x ) , se puede suponer b ≠ 0 (de lo contrario, el mcd es a ( x ) ), y
La división euclidiana proporciona dos polinomios q ( x ) , el cociente y r ( x ) , el resto tales que
Un polinomio g ( x ) divide tanto a ( x ) como b ( x ) si y sólo si divide tanto a b ( x ) como a r 0 ( x ) . De este modo, se puede repetir la división euclidiana para obtener nuevos polinomios q 1 ( x ), r 1 ( x ), a 2 ( x ), b 2 ( x ) , etc. En cada etapa tenemos la secuencia eventualmente llegará a un punto en el que se obtiene el MCD:
Ejemplo: encontrar el MCD de x 2 + 7 x + 6 y x 2 − 5 x − 6 :
Dado que 12 x + 12 es el último resto distinto de cero, es un MCD de los polinomios originales y el MCD mónico es x + 1 .
En este ejemplo, no es difícil evitar introducir denominadores factorizando 12 antes del segundo paso. Esto siempre se puede hacer usando secuencias de pseudoresto, pero, sin cuidado, esto puede introducir números enteros muy grandes durante el cálculo. Por lo tanto, para el cálculo informático se utilizan otros algoritmos, que se describen a continuación.
Este método sólo funciona si se puede probar la igualdad a cero de los coeficientes que ocurren durante el cálculo. Entonces, en la práctica, los coeficientes deben ser números enteros , números racionales , elementos de un campo finito , o deben pertenecer a alguna extensión de campo finitamente generada de uno de los campos anteriores. Si los coeficientes son números de coma flotante que representan números reales que se conocen sólo aproximadamente, entonces se debe conocer el grado del MCD para tener un resultado de cálculo bien definido (es decir, un resultado numéricamente estable ; en estos casos se pueden utilizar otras técnicas). , generalmente basado en la descomposición de valores singulares .
El caso de polinomios univariados sobre un cuerpo es especialmente importante por varias razones. En primer lugar, es el caso más elemental y, por tanto, aparece en la mayoría de los primeros cursos de álgebra. En segundo lugar, es muy similar al caso de los números enteros, y esta analogía es la fuente de la noción de dominio euclidiano . Una tercera razón es que la teoría y los algoritmos para el caso multivariado y para coeficientes en un dominio de factorización único se basan fuertemente en este caso particular. Por último, pero no menos importante, los algoritmos MCD polinómicos y los algoritmos derivados permiten obtener información útil sobre las raíces de un polinomio, sin tener que calcularlas.
La división euclidiana de polinomios, que se utiliza en el algoritmo de Euclides para calcular MCD, es muy similar a la división euclidiana de números enteros. Su existencia se basa en el siguiente teorema: Dados dos polinomios univariados a y b ≠ 0 definidos sobre un cuerpo, existen dos polinomios q (el cociente ) y r (el resto ) que satisfacen y donde " deg(...) " denota el grado y el grado del polinomio cero se define como negativo. Además, q y r están definidos únicamente por estas relaciones.
La diferencia con la división euclidiana de los números enteros es que, para los números enteros, el grado se reemplaza por el valor absoluto, y que para tener unicidad hay que suponer que r no es negativo. Los anillos para los que existe tal teorema se denominan dominios euclidianos .
Al igual que con los números enteros, la división euclidiana de los polinomios puede calcularse mediante el algoritmo de división larga . Este algoritmo generalmente se presenta para cálculos con lápiz y papel, pero funciona bien en computadoras cuando se formaliza de la siguiente manera (tenga en cuenta que los nombres de las variables corresponden exactamente a las regiones de la hoja de papel en un cálculo con lápiz y papel de larga duración). división). En el siguiente cálculo, "deg" representa el grado de su argumento (con la convención deg(0) < 0 ), y "lc" representa el coeficiente principal, el coeficiente del grado más alto de la variable.
división euclidianaEntrada: a y b ≠ 0 dos polinomios en la variable x ; Salida: q , el cociente, yr , el resto;comenzar q := 0 r := a d := grados( b ) c := lc( b ) mientras grados( r ) ≥ d hacer s := (lc( r )/ c ) ⋅ x grados( r )− d q := q + s r := r − sb fin devolver ( q , r ) fin
La prueba de la validez de este algoritmo se basa en el hecho de que durante todo el ciclo " while ", tenemos a = bq + r y deg( r ) es un número entero no negativo que disminuye en cada iteración. Así, la prueba de la validez de este algoritmo también prueba la validez de la división euclidiana.
En cuanto a los números enteros, la división euclidiana nos permite definir el algoritmo de Euclides para calcular los MCD.
Partiendo de dos polinomios a y b , el algoritmo de Euclides consiste en sustituir recursivamente el par ( a , b ) por ( b , rem( a , b )) (donde " rem( a , b ) " denota el resto de la división euclidiana, calculado mediante el algoritmo de la sección anterior), hasta b = 0. El MCD es el último resto distinto de cero.
El algoritmo de Euclides puede formalizarse en el estilo de programación recursiva como:
En el estilo de programación imperativo, el mismo algoritmo se convierte en, dando un nombre a cada resto intermedio:
r 0 := a r 1 := segundopara ( i := 1; r i ≤ 0; i := i + 1) do r i +1 := rem( r i −1 , r i ) end dodevolver r yo -1 .
La secuencia de los grados de r i es estrictamente decreciente. Por lo tanto , después de, como máximo, pasos de grados ( b ) , se obtiene un resto nulo, digamos rk . Como ( a , b ) y ( b , rem( a , b )) tienen los mismos divisores, el algoritmo de Euclides no cambia el conjunto de los divisores comunes y, por lo tanto, todos los pares ( r i , r i +1 ) tienen el mismo conjunto de divisores comunes. Los divisores comunes de a y b son, por tanto, los divisores comunes de r k −1 y 0. Por tanto, r k −1 es un MCD de a y b . Esto no sólo prueba que el algoritmo de Euclides calcula los GCD, sino que también demuestra que los GCD existen.
La identidad de Bézout es un teorema relacionado con el MCD, inicialmente demostrado para los números enteros, que es válido para todo dominio ideal principal . En el caso de los polinomios univariados sobre un campo, se puede expresar de la siguiente manera.
y u = 1, v = 0 , o u = 0, v = 1 , o
El interés de este resultado en el caso de los polinomios es que existe un algoritmo eficiente para calcular los polinomios u y v . Este algoritmo difiere del algoritmo de Euclides por algunos cálculos más realizados en cada iteración del ciclo. Por eso se le llama algoritmo GCD extendido . Otra diferencia con el algoritmo de Euclides es que también utiliza el cociente, denominado "quo", de la división euclidiana en lugar de sólo el resto. Este algoritmo funciona de la siguiente manera.
Algoritmo GCD extendidoEntrada: a , b , polinomios univariadosSalida: g , el MCD de a y b u , v , como en la declaración anterior a 1 , b 1 , tal que a = g a 1 b = g b 1 Begin ( r 0 , r 1 ): = ( a , b ) ( s 0 , s 1 ) := (1, 0) ( t 0 , t 1 ) := (0, 1) para ( i := 1; r i ≠ 0; i := i +1) hacer q := quo( r i −1 , r i ) r i +1 := r i −1 − qr i s i +1 := s i −1 − qs i t i +1 := t i −1 − qt i end do g := r i −1 u := s i −1 v := t i −1 a 1 := ( −1) i −1 t i b 1 := (−1) i t i Fin
La prueba de que el algoritmo satisface su especificación de salida se basa en el hecho de que, para cada i tenemos la última igualdad que implica. La afirmación sobre los grados se deriva del hecho de que, en cada iteración, los grados de s i y ti aumentan como máximo. a medida que el grado de r i disminuye.
Una característica interesante de este algoritmo es que, cuando se necesitan los coeficientes de la identidad de Bezout, se obtiene gratis el cociente de los polinomios de entrada por su MCD.
Una aplicación importante del algoritmo GCD extendido es que permite calcular la división en extensiones de campos algebraicos .
Sea L una extensión algebraica de un campo K , generada por un elemento cuyo polinomio mínimo f tiene grado n . Los elementos de L suelen estar representados por polinomios univariados sobre K de grado menor que n .
La suma en L es simplemente la suma de polinomios:
La multiplicación en L es la multiplicación de polinomios seguida de la división por f :
La inversa de un elemento a distinto de cero de L es el coeficiente u en la identidad de Bézout au + fv = 1 , que puede calcularse mediante el algoritmo MCD extendido. (el MCD es 1 porque el polinomio mínimo f es irreducible). La desigualdad de grados en la especificación del algoritmo GCD extendido muestra que no se necesita una división adicional por f para obtener grados ( u ) < grados ( f ).
En el caso de los polinomios univariados, existe una fuerte relación entre el máximo común divisor y las resultantes . Más precisamente, la resultante de dos polinomios P , Q es una función polinómica de los coeficientes de P y Q que tiene el valor cero si y sólo si el MCD de P y Q no es constante.
La teoría de las subresultantes es una generalización de esta propiedad que permite caracterizar genéricamente el MCD de dos polinomios, y la resultante es el polinomio subresultante 0-ésimo. [1]
El i -ésimo polinomio subresultante Si ( P , Q ) de dos polinomios P y Q es un polinomio de grado como máximo i cuyos coeficientes son funciones polinómicas de los coeficientes de P y Q , y el i -ésimo coeficiente subresultante principal s i ( P , Q ) es el coeficiente de grado i de Si ( P , Q ) . Tienen la propiedad de que el MCD de P y Q tiene grado d si y sólo si
En este caso, S d ( P , Q ) es un MCD de P y Q y
Cada coeficiente de los polinomios subresultantes se define como el determinante de una submatriz de la matriz de Sylvester de P y Q. Esto implica que los subresultados se "especializan" bien. Más precisamente, los subresultantes se definen para polinomios sobre cualquier anillo conmutativo R y tienen la siguiente propiedad.
Sea φ un homomorfismo de anillo de R en otro anillo conmutativo S. Se extiende a otro homomorfismo, denotado también φ entre los anillos de polinomios sobre R y S. Entonces, si P y Q son polinomios univariados con coeficientes en R tales que y entonces los polinomios subresultantes y los coeficientes subresultantes principales de φ ( P ) y φ ( Q ) son la imagen por φ de los de P y Q .
Los subresultados tienen dos propiedades importantes que los hacen fundamentales para el cálculo en computadoras del MCD de dos polinomios con coeficientes enteros. En primer lugar, su definición a través de determinantes permite acotar, mediante la desigualdad de Hadamard , el tamaño de los coeficientes del MCD. En segundo lugar, este límite y la propiedad de una buena especialización permiten calcular el MCD de dos polinomios con coeficientes enteros mediante cálculo modular y el teorema del resto chino (ver más abajo).
Sean dos polinomios univariados con coeficientes en un campo K . Denotemos por el espacio vectorial K de dimensión i de polinomios de grado menor que i . Para un entero no negativo i tal que i ≤ my i ≤ n , sea el mapa lineal tal que
La resultante de P y Q es el determinante de la matriz de Sylvester , que es la matriz (cuadrada) de sobre las bases de las potencias de X. De manera similar, el polinomio i -subresultante se define en términos de determinantes de submatrices de la matriz de
Describamos estas matrices con mayor precisión;
Sea p i = 0 para i < 0 o i > m , y q i = 0 para i < 0 o i > n . La matriz de Sylvester es la matriz ( m + n ) × ( m + n ) tal que el coeficiente de la i -ésima fila y la j -ésima columna es p m + j − i para j ≤ n y q j − i para j > n : [nota 1]
La matriz T i de es la ( m + n − i ) × ( m + n − 2 i ) -submatriz de S que se obtiene eliminando las últimas i filas de ceros en la submatriz de las columnas 1 a n − i y n + 1 a m + n − i de S (es decir, eliminando i columnas en cada bloque y las i últimas filas de ceros). El principal coeficiente subresultante s i es el determinante de las m + n − 2 i primeras filas de T i .
Sea V i la matriz ( m + n − 2 i ) × ( m + n − i ) definida de la siguiente manera. Primero sumamos ( i + 1) columnas de ceros a la derecha de la matriz identidad ( m + n − 2 i − 1) × ( m + n − 2 i − 1) . Luego bordeamos la parte inferior de la matriz resultante con una fila que consta de ( m + n − i − 1) ceros seguidos de X i , X i −1 , ..., X , 1 :
Con esta notación, el i -ésimo polinomio subresultante es el determinante del producto matricial V i T i . Su coeficiente de grado j es el determinante de la submatriz cuadrada de T i que consiste en sus primeras filas m + n − 2 i − 1 y la ( m + n − i − j ) -ésima fila.
No es obvio que, tal como se definen, los subresultantes tengan las propiedades deseadas. Sin embargo, la demostración es bastante sencilla si se juntan las propiedades del álgebra lineal y las de los polinomios.
Tal como se define, las columnas de la matriz Ti son los vectores de los coeficientes de algunos polinomios pertenecientes a la imagen de . La definición del i -ésimo polinomio subresultante Si muestra que el vector de sus coeficientes es una combinación lineal de estos vectores columna y, por tanto, que Si pertenece a la imagen de
Si el grado del MCD es mayor que i , entonces la identidad de Bézout muestra que cada polinomio distinto de cero en la imagen de tiene un grado mayor que i . Esto implica que Si = 0 .
Si, por el contrario, el grado del MCD es i , entonces la identidad de Bézout permite nuevamente demostrar que los múltiplos del MCD que tienen un grado inferior a m + n − i están a imagen de . El espacio vectorial de estos múltiplos tiene la dimensión m + n − 2 i y tiene una base de polinomios de grados diferentes por pares, no menor que i . Esto implica que la submatriz de las primeras filas m + n − 2 i de la forma escalonada de columnas de Ti es la matriz identidad y, por lo tanto, que s i no es 0. Por lo tanto, S i es un polinomio en la imagen de , que es un múltiplo del MCD y tiene el mismo grado. Por tanto, es un máximo común divisor.
La mayoría de los algoritmos de búsqueda de raíces se comportan mal con polinomios que tienen múltiples raíces . Por lo tanto, es útil detectarlos y eliminarlos antes de llamar a un algoritmo de búsqueda de raíces. Un cálculo del MCD permite detectar la existencia de múltiples raíces, ya que las raíces múltiples de un polinomio son las raíces del MCD del polinomio y su derivada .
Después de calcular el MCD del polinomio y su derivada, los cálculos adicionales del MCD proporcionan la factorización completa sin cuadrados del polinomio, que es una factorización donde, para cada i , el polinomio f i es 1 si f no tiene ninguna raíz de la multiplicidad i o es un polinomio sin cuadrados (es decir, un polinomio sin raíz múltiple) cuyas raíces son exactamente las raíces de la multiplicidad i de f (ver el algoritmo de Yun ).
Por lo tanto, la factorización libre de cuadrados reduce la búsqueda de raíces de un polinomio con raíces múltiples a la búsqueda de raíces de varios polinomios libres de cuadrados de menor grado. La factorización sin cuadrados es también el primer paso en la mayoría de los algoritmos de factorización polinomial .
La secuencia de Sturm de un polinomio con coeficientes reales es la secuencia de restos proporcionada por una variante del algoritmo de Euclides aplicado al polinomio y su derivada. Para obtener la secuencia de Sturm, simplemente se reemplaza la instrucción del algoritmo de Euclides por
Sea V ( a ) el número de cambios de signos en la secuencia, cuando se evalúa en un punto a . El teorema de Sturm afirma que V ( a ) − V ( b ) es el número de raíces reales del polinomio en el intervalo [ a , b ] . Así, la secuencia de Sturm permite calcular el número de raíces reales en un intervalo dado. Al subdividir el intervalo hasta que cada subintervalo contenga como máximo una raíz, se proporciona un algoritmo que localiza las raíces reales en intervalos de longitud arbitrariamente pequeña.
En esta sección, consideramos polinomios sobre un dominio de factorización único R , típicamente el anillo de los números enteros, y sobre su campo de fracciones F , típicamente el campo de los números racionales, y denotamos R [ X ] y F [ X ] como anillos de polinomios en un conjunto de variables sobre estos anillos.
El contenido de un polinomio p ∈ R [ X ] , denotado " cont( p ) ", es el MCD de sus coeficientes. Se puede escribir un polinomio q ∈ F [ X ] donde p ∈ R [ X ] y c ∈ R : basta tomar para c un múltiplo de todos los denominadores de los coeficientes de q (por ejemplo su producto) y p = cq . El contenido de q se define como: En ambos casos, el contenido se define hasta la multiplicación por una unidad de R .
La parte primitiva de un polinomio en R [ X ] o F [ X ] está definida por
En ambos casos, es un polinomio en R [ X ] que es primitivo , lo que significa que 1 es un MCD de sus coeficientes.
Así, todo polinomio en R [ X ] o F [ X ] puede factorizarse como y esta factorización es única hasta la multiplicación del contenido por una unidad de R y de la parte primitiva por la inversa de esta unidad.
El lema de Gauss implica que el producto de dos polinomios primitivos es primitivo. Se deduce que y
Las relaciones de la sección anterior implican una fuerte relación entre los MCD en R [ X ] y en F [ X ] . Para evitar ambigüedades, la notación " gcd " estará indexada, a continuación, por el anillo en el que se calcula el MCD.
Si q 1 y q 2 pertenecen a F [ X ] , entonces
Si p 1 y p 2 pertenecen a R [ X ] , entonces y
Por lo tanto, el cálculo de MCD polinómicos es esencialmente el mismo problema sobre F [ X ] y sobre R [ X ] .
Para polinomios univariados sobre números racionales, se puede pensar que el algoritmo de Euclides es un método conveniente para calcular el MCD. Sin embargo, implica simplificar una gran cantidad de fracciones de números enteros y el algoritmo resultante no es eficiente. Por esta razón, se han diseñado métodos para modificar el algoritmo de Euclides para trabajar únicamente con polinomios sobre números enteros. Consisten en sustituir la división euclidiana, que introduce fracciones, por una llamada pseudodivisión , y sustituir la secuencia restante del algoritmo de Euclides por las llamadas secuencias pseudoresto (ver más abajo).
En la sección anterior hemos visto que el MCD de polinomios en R [ X ] se puede deducir de los MCD en R y en F [ X ] . Una mirada más cercana a la prueba muestra que esto nos permite probar la existencia de MCD en R [ X ] , si existen en R y en F [ X ] . En particular, si existen MCD en R , y si X se reduce a una variable, esto prueba que existen MCD en R [ X ] (el algoritmo de Euclid prueba la existencia de MCD en F [ X ] ).
Un polinomio en n variables puede considerarse como un polinomio univariado sobre el anillo de polinomios en ( n − 1 ) variables. Por lo tanto , una recursión en el número de variables muestra que si los MCD existen y pueden calcularse en R , entonces existen y pueden calcularse en cada anillo polinómico multivariado sobre R. En particular, si R es el anillo de los números enteros o un campo, entonces los MCD existen en R [ x 1 , ..., x n ] , y lo que precede proporciona un algoritmo para calcularlos.
La prueba de que un anillo polinomial sobre un dominio de factorización único es también un dominio de factorización único es similar, pero no proporciona un algoritmo, porque no existe un algoritmo general para factorizar polinomios univariados sobre un campo (hay ejemplos de campos para los cuales no existe ningún algoritmo de factorización para los polinomios univariados).
En esta sección, consideramos un dominio integral Z (típicamente el anillo Z de los números enteros) y su campo de fracciones Q (típicamente el campo Q de los números racionales). Dados dos polinomios A y B en el anillo polinómico univariante Z [ X ] , la división euclidiana (sobre Q ) de A por B proporciona un cociente y un resto que puede no pertenecer a Z [ X ] .
Porque, si se aplica el algoritmo de Euclides a los siguientes polinomios [2] y los sucesivos restos del algoritmo de Euclides son. Se ve que, a pesar del pequeño grado y el pequeño tamaño de los coeficientes de los polinomios de entrada, hay que manipular y simplificar fracciones enteras. de tamaño bastante grande.
ElSe ha introducido la pseudodivisión para permitir una variante del algoritmo de Euclides para el cual todos los restos pertenecen a Z [ X ].
Si y y a ≥ b , el pseudoresto de la pseudodivisión de A por B , denotado por prem( A , B ) es donde lc( B ) es el coeficiente principal de B (el coeficiente de X b ).
El pseudoresto de la pseudodivisión de dos polinomios en Z [ X ] pertenece siempre a Z [ X ] .
Una secuencia de pseudo-restos es la secuencia de los (pseudo) restos r i obtenidos reemplazando la instrucción del algoritmo de Euclides por donde α es un elemento de Z que divide exactamente cada coeficiente del numerador. Diferentes opciones de α dan diferentes secuencias de pseudoresiduos, que se describen en las siguientes subsecciones.
Como los divisores comunes de dos polinomios no cambian si los polinomios se multiplican por constantes invertibles (en Q ), el último término distinto de cero en una secuencia de pseudoresto es un MCD (en Q [ X ] ) de los polinomios de entrada. Por lo tanto , las secuencias de pseudoresto permiten calcular MCD en Q [ X ] sin introducir fracciones en Q.
En algunos contextos, es esencial controlar el signo del coeficiente principal del pseudoresto. Este suele ser el caso cuando se calculan resultantes y subresultantes , o cuando se utiliza el teorema de Sturm . Este control se puede realizar reemplazando lc( B ) por su valor absoluto en la definición del pseudoresto, o controlando el signo de α (si α divide todos los coeficientes de un resto, lo mismo ocurre con − α ) . [1]
La secuencia de restos más simple (de definir) consiste en tomar siempre α = 1 . En la práctica, no es interesante, ya que el tamaño de los coeficientes crece exponencialmente con el grado de los polinomios de entrada. Esto aparece claramente en el ejemplo de la sección anterior, para el cual los pseudorestos sucesivos son El número de dígitos de los coeficientes de los restos sucesivos se duplica con creces en cada iteración del algoritmo. Este es el comportamiento típico de las secuencias triviales de pseudoresto.
La secuencia primitiva de pseudoresto consiste en tomar por α el contenido del numerador. Por tanto, todos los r i son polinomios primitivos.
La secuencia de pseudoresto primitiva es la secuencia de pseudoresto, que genera los coeficientes más pequeños. Sin embargo, requiere calcular una cantidad de MCD en Z y, por lo tanto, no es lo suficientemente eficiente para usarse en la práctica, especialmente cuando Z es en sí mismo un anillo polinómico.
Con la misma entrada que en los apartados anteriores, los restos sucesivos, después de dividirlos por su contenido, se obtienen. El pequeño tamaño de los coeficientes oculta el hecho de que se han calculado varios números enteros MCD y divisiones por el MCD.
Una secuencia subresultante también se puede calcular con pseudorestos. El proceso consiste en elegir α de tal forma que todo r i sea un polinomio subresultante. Sorprendentemente, el cálculo de α es muy sencillo (ver más abajo). Por otro lado, la prueba de la corrección del algoritmo es difícil, porque debe tener en cuenta todas las posibilidades de diferencia de grados de dos restos consecutivos.
Los coeficientes de la secuencia subresultante rara vez son mucho mayores que los de la secuencia primitiva del pseudoresto. Como no se necesitan cálculos de MCD en Z , la secuencia subreresultante con pseudorestos proporciona el cálculo más eficiente.
Con la misma entrada que en los apartados anteriores, los restos sucesivos son Los coeficientes tienen un tamaño razonable. Se obtienen sin ningún cálculo MCD, sólo divisiones exactas. Esto hace que este algoritmo sea más eficiente que el de las secuencias primitivas de pseudoresto.
A continuación se proporciona el algoritmo que calcula la secuencia subresultante con pseudorestos. En este algoritmo, la entrada ( a , b ) es un par de polinomios en Z [ X ] . Los r i son los pseudo restos sucesivos en Z [ X ] , las variables i y d i son números enteros no negativos y las letras griegas denotan elementos en Z . Las funciones deg()
y rem()
denotan el grado de un polinomio y el resto de la división euclidiana. En el algoritmo, este resto siempre está en Z [ X ] . Finalmente las divisiones denotadas por / son siempre exactas y tienen su resultado en Z [ X ] o en Z .
r 0 := a r 1 := b para ( i := 1; r i ≠ 0; i := i +1) hacer d i := grados( r i −1 ) − grados( r i ) γ i : = lc( r i ) si i = 1 entonces β 1 := (−1) d 1 +1 ψ 1 := −1 si no ψ i := (− γ i −1 ) d i −1 / ψ i −1 re i −1 −1 β i := − γ i −1 ψ i re i final si r i +1 := rem( γ i d i +1 r i −1 , r i ) / β i final para
Nota: "lc" representa el coeficiente principal, el coeficiente del mayor grado de la variable.
Este algoritmo calcula no solo el máximo común divisor (el último r i distinto de cero ), sino también todos los polinomios subrasultantes: el resto r i es el (grado ( r i −1 ) − 1) -ésimo polinomio subresaliente. Si grados( r i ) < grados( r i −1 ) − 1 , el polinomio subresultante grados( r i ) -ésimo es lc ( r i ) grados ( r i −1 ) −grados ( r i )−1 r i . Todos los demás polinomios subresultantes son cero.
Se pueden utilizar pseudorestos para construir secuencias que tengan las mismas propiedades que las secuencias de Sturm . Esto requiere controlar los signos de los pseudorestos sucesivos, para tener los mismos signos que en la secuencia de Sturm. Esto se puede hacer definiendo un pseudoresto modificado de la siguiente manera.
Si y y a ≥ b , el pseudoresto modificado prem2( A , B ) de la pseudodivisión de A por B es donde | lc( B ) | es el valor absoluto del coeficiente principal de B (el coeficiente de X b ).
Para polinomios de entrada con coeficientes enteros, esto permite la recuperación de secuencias de Sturm que constan de polinomios con coeficientes enteros. La secuencia de pseudorestos subresultante se puede modificar de manera similar, en cuyo caso los signos de los restos coinciden con los calculados sobre los racionales.
Tenga en cuenta que el algoritmo para calcular la secuencia del pseudoresto subresultante dada anteriormente calculará polinomios subresultantes incorrectos si se usa en lugar de .
Si f y g son polinomios en F [ x ] para algún campo F finitamente generado , el algoritmo euclidiano es la forma más natural de calcular su MCD. Sin embargo, los sistemas de álgebra informática modernos solo lo usan si F es finito debido a un fenómeno llamado aumento de expresión intermedia . Aunque los grados siguen disminuyendo durante el algoritmo euclidiano, si F no es finito , entonces el tamaño de bits de los polinomios puede aumentar (a veces dramáticamente) durante los cálculos porque las operaciones aritméticas repetidas en F tienden a conducir a expresiones más grandes. Por ejemplo, la suma de dos números racionales cuyos denominadores están acotados por b conduce a un número racional cuyo denominador está acotado por b 2 , por lo que en el peor de los casos, el tamaño del bit podría casi duplicarse con una sola operación.
Para acelerar el cálculo, tome un anillo D para el cual f y g estén en D [ x ] y tome un I ideal tal que D / I sea un anillo finito. Luego calcule el MCD sobre este anillo finito con el algoritmo euclidiano. Utilizando técnicas de reconstrucción ( teorema chino del resto , reconstrucción racional , etc.) se puede recuperar el MCD de f y g a partir de su módulo de imagen de varios ideales I. Se puede probar [3] que esto funciona siempre que se descarten las imágenes modulares con grados no mínimos y se eviten los ideales I módulo en los que un coeficiente principal desaparece.
Supongamos que , y . Si tomamos entonces es un anillo finito (no un campo ya que no es máximo en ). El algoritmo euclidiano aplicado a las imágenes de in tiene éxito y devuelve 1. Esto implica que el MCD de in también debe ser 1. Tenga en cuenta que este ejemplo podría manejarse fácilmente mediante cualquier método porque los grados eran demasiado pequeños para que se produjera un aumento de expresión, pero ilustra que si dos polinomios tienen MCD 1, entonces es probable que el algoritmo modular termine después de un único ideal .