lunes, 22 de febrero de 2016

Polinomios


 factorización de polinomios o factorización polinómica se refiere a factorizar un polinomio con coeficientes en uncampo dado o en los números enteros en factores irreducibles con coeficientes en el mismo dominio. Factorización polinómica es una de las herramientas fundamentales de los sistemas de álgebra computacional.
La historia de la factorización polinómica comienza con Hermann Schubert quien en 1793 describió el primer algoritmo de factorización de polinomios, y Leopold Kronecker, quien redescubrió el algoritmo de Schubert en 1882 y la amplió a polinomios multivariados y con coeficientes en una extensión algebraica. Pero la mayor parte de los conocimientos sobre este tema no es mayor que alrededor del año 1965 y los primeros sistemas de álgebra computacional. En una entrevista sobre el tema, Erich Kaltofen escribió en 1982 (véase la bibliografía):
Cuando los algoritmos de pasos finitos largo tiempo conocidos se pusieron por primera vez en los ordenadores, resultaron ser altamente ineficiente. El hecho de que casi cualquier polinomio uni o multivariado de hasta grado 100 y con coeficientes de tamaño moderado (hasta 100 bits) se puede factorizar mediante algoritmos modernos en unos pocos minutos indica el éxito con que este problema se ha atacado durante los últimos quince años.

Formulación

Anillos de polinomios sobre los enteros o sobre un campo son dominios de factorización única. Esto significa que cada elemento de estos anillos es el producto de una constante y el producto de polinomios irreducibles (aquellos que no son el producto de dos polinomios no constantes). Por otra parte, esta descomposición es única hasta la multiplicación de los factores por constantes invertibles.
La factorización depende del campo base. Por ejemplo, el teorema fundamental del álgebra, que establece que todo polinomio con coeficientes complejos tiene raíces complejas, implica que un polinomio con coeficientes enteros se puede factorizar (mediante algoritmos numéricos) en factores lineales sobre los números complejos. Del mismo modo, sobre los números reales, los factores irreducibles tienen grado a lo sumo dos, mientras que hay polinomios de cualquier grado que son irreducible sobre los números racionales.
La factorización polinómica sólo tiene sentido para coeficientes en un campo computable en donde cada elemento puede ser representado en una computadora y existan algoritmos para las operaciones aritméticas. Fröhlich y Shepherson han proporcionado ejemplos de estos campos para los que puede no existir ningún algoritmo de factorización.
Los campos de los coeficientes para los que se conocen algoritmos de factorización incluyen campos principales (es decir, los números racionales y la aritmética modular sobre primos) y sus extensiones de campo finito. Coeficientes enteros también son manejables: el método de Kronecker sólo es interesante desde un punto de vista histórico, los algoritmos modernos provienen de una sucesión de:
  • Factorización sin radicales
  • Factorización sobre campos finitos
y reducciones:
  • Desde el caso multivariado al univariado.
  • Desde coeficientes en una extensión puramente trascendental al caso multivariado sobre el campo base (véase más abajo)
  • Desde coeficientes en una extensión algebraica a coeficientes en el campo base
  • Desde coeficientes racionales a coeficientes enteros (véase más abajo)
  • Desde coeficientes enteros a coeficientes en un campo primo con p elementos, para cierto p.

Factorización primitiva basada en contenido

Véase también: Lema de Gauss
En esta sección, se muestra que la factorización sobre Q (los números racionales) y sobre Z (los enteros) es esencialmente el mismo problema.
El contenido de un polinomio p ∈ Z[X], denotado como "cont(p)", es, hasta su signo, el máximo común divisor de sus coeficientes. La parte primitiva de p es primpart(p)=p/cont(p), que es un polinomio primitivo con coeficientes enteros. Esto define una factorización de p como el producto de un número entero y un polinomio primitivo. Esta factorización es única hasta el signo del contenido. Es usual elegir el signo del contenido tal que el coeficiente principal de la parte primitiva sea positivo.
Por ejemplo,
-10x^2 + 5x + 5 = (-5)\cdot (2x^2 - x - 1) \,
es una factorización en el contenido y la parte primitiva.
Cada polinomio Q con coeficientes racionales puede ser escrito como
q = \frac{p}{c},
donde p ∈ Z[X] y C ∈ Z: basta con tomar para C un múltiplo de todos los denominadores de los coeficientes de Q (por ejemplo, su producto) y p = cq. El contenido deQ se define como:
\text{cont} (q) =\frac{\text{cont} (p)}{c},
y la parte primitiva de q es la de p. En cuanto a los polinomios con coeficientes enteros, esto define una factorización en un número racional y un polinomio primitivo con coeficientes enteros. Esta factorización es también única hasta la elección del signo.
Por ejemplo,
\frac{1}{3}x^5 + \frac{7}{2} x^2 + 2x + 1 = \frac{1}{6} ( 2x^5 + 21x^2 + 12x + 6)
es una factorización en el contenido y la parte primitiva.
Gauss demostró en primer lugar que el producto de dos polinomios primitivos también es primitivo (Lema de Gauss). Esto implica que un polinomio primitivo es irreducible sobre los racionales si y sólo si es irreducible sobre los números enteros. Además implica que la factorización sobre los números racionales de un polinomio con coeficientes racionales es la misma que la factorización sobre los números enteros de su parte primitiva. Por otro lado, la factorización sobre los números enteros de un polinomio con coeficientes enteros es el producto de la factorización de su parte primitiva por la factorización de su contenido.
En otras palabras, integer GDD computation permite reducir la factorización de un polinomio sobre los números racionales a la factorización de un polinomio primitivo con coeficientes enteros, y reducir la factorización sobre los números enteros a la factorización de un número entero y un polinomio primitivo.
Todo lo anterior se sigue cumpliendo si Z es sustituido por un anillo de polinomios sobre un campo F y Q se sustituye por un campo de cocientes racionales sobre F en las mismas variables, con la única diferencia de que "hasta un signo" debe sustituirse por "hasta la multiplicación por una constante invertible en F". Esto permite reducir la factorización sobre una extensión puramente trascendente de F a la factorización de polinomios multivariados sobre F.

Factorización sin radicales (Square-free factorization)

Si dos o más factores de un polinomio son idénticos entre sí, entonces el polinomio es un múltiplo de la raíz de este factor. En el caso de polinomios univariantes, esto resulta en raíces múltiples. En este caso, el factor múltiple es también un factor de las derivadas del polinomio (con respecto a cualquiera de las variables), que a su vez es un polinomio de menor grado. En el caso de los polinomios univariantes sobre los racionales (o en general, sobre un campo de característica cero), el algoritmo de Yun explota esta característica al factorizar eficientemente el polinomio en factores que no son múltiplos de una raíz, por lo que son llamados sin radicales (square-free). Para factorizar el polinomio inicial, basta con factorizar cada factor sin radicales. Por tanto, este algoritmo es el primer paso de casi todos los algoritmos de factorización de polinomios.
El algoritmo de Yun se extiende fácilmente al caso multivariado considerando un polinomio multivariante como un polinomio univariado sobre un anillo de polinomios.
En el caso de un polinomio sobre un campo finito, el algoritmo de Yun sólo se aplica si el grado es menor que la característica, porque, de lo contrario, la derivada de un polinomio distinto de cero puede ser cero (sobre el campo con p elementos, la derivada de una polinomio en xp es siempre cero). Sin embargo, una sucesión de cálculos GCD, a partir del polinomio y su derivada, permite calcular la descomposición sin radicales.
La mayoría de los algoritmos de factorización, incluyendo los más eficientes, comienzan por una factorización sin radicales.

Métodos clásicos

Esta sección describe los métodos clásicos que resultan conveniente cuando se calcula a mano. Estos métodos no se utilizan para los cálculos por ordenador, ya que utilizan la factorización sobre enteros , que tiene una complejidad mucho mayor que la factorización polinómica.

Obteniendo factores lineales

Todos los factores lineales con coeficientes racionales se pueden encontrar utilizando el Teorema de la raíz racional. Si el polinomio a factorizar es a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0, entonces todos los posibles factores (lineales) son de la forma b_1x-b_0, donde b_1 es un factor entero de a_0 y b_0 es un factor entero de a_n. Todas las posibles combinaciones de factores enteros pueden ser verificadas, y cada combinación válida puede ser factorizada usando la división polinomial. Si el polinomio original es el producto de varios factores, de los cuales al menos dos tienen grado 2 o superior, esta técnica sólo proporciona una factorización parcial, de lo contrario la factorización es completa. Tenga en cuenta que en el caso de un polinomio cúbico, si el cubo es factorizable, el Teorema de la raíz racional ya sea en un factor lineal y un factor cuadrático irreducible, o en tres factores lineales.

Método de Kronecker

Dado que polinomios enteros deben factorizar en factores polinomiales enteros, y la evaluación de polinomios enteros a valores enteros deben producir números enteros, los valores enteros de un polinomio deben tenerse en cuenta sólo en número finito de formas, y producen sólo un número finito de posibles factores polinómicos.
Por ejemplo, considere
f(x) = x^5 + x^4 + x^2 + x + 2.
Si estos factores polinómicos están sobre Z, entonces al menos uno de ellos debe tener grado dos o inferior. Se necesitan tres valores para encontrar un polinomio único de segundo grado. Usaremos f(0) = 2, f(1) = 6 y f(-1) = 2. Tenga en cuenta que si alguno de estos valores es 0, entonces ya se ha encontrado una raíz (y por consiguiente un factor). Si ninguno es 0, entonces cada uno tiene una cantidad finita de divisores. Ahora, 2 sólo puede factorizarse como
1×2, 2×1, (−1)×(−2), o (−2)×(−1).
Por lo tanto, si existe un factor polinómico entero de segundo grado existe, debe tomar uno de los valores
1, 2, −1, ó −2
en x=0, y asimismo en x=-1. Hay ocho formas diferentes de Factor 6 (uno para cada divisor de 6), por lo que hay
4×4×8 = 128
combinaciones posibles, de las cuales la mitad se puede desechar como los negativos de la otra mitad, que corresponden a 64 posibles polinomios enteros de segundo grado que deben ser comprobados. Estos son los únicos posibles factores de polinomios enteros de f(x). Probándolos de forma exhaustiva se comprueba
p(x) = x^2 + x + 1
construido a partir de p(0)=1, p(1)=3 y p(-1)=1, factorizando f(x).
Dividiendo f por p da el otro factor q(x) = x^3 - x + 2, tal que f = pq. Ahora se puede probar de forma recursiva para encontrar factores de p y q. Resulta que ambos son irreducible sobre los números enteros, de manera que la factorización irreductible de f es
f(x) = p(x)q(x) = (x^2 + x + 1)(x^3 - x + 2)
(Van der Waerden, Secciones 5.4 y 5.6)

Métodos modernos

Algoritmo LLL

El primer algoritmo de complejidad temporal polinomial para factorizar polinomios racionales fue descubierto por Lenstra, Lenstra and Lovász. Usualmente llamado "para factorizar polinomios racionales LLL". (Lenstra, Lenstra y Lovász, 1982) A pesar de que, teóricamente, es más rápido en caso peor, el algoritmo no es eficiente en la práctica.
Sin embargo el algoritmo LLL es utilizado por algoritmos de factorización más rápidos para generar una factorización modular para una factorización sobre los números enteros.

Método de Trager

Podemos factorizar un polinomio p(x) \in K[x] , donde K es una extensión de campo finita de \mathbb{Q}. Primero, usando factorización sin radicales, podemos suponer que el polinomio no tiene radicales. A continuación escribimos L= K[x]/p(x) explícitamente como un álgebra sobre \mathbb{Q}. A continuación escogemos un elemento aleatorio \alpha \in L. Por el teorema del elemento primitivo, \alpha genera L sobre \mathbb{Q} con una alta probabilidad. Si este es el caso, podemos calcular el polinomio minimal, q(y)\in \mathbb{Q}[y] de \alpha sobre \mathbb{Q}. Factorizando
q(y) = \prod_{i=1}^{n} q_i(y)
sobre \mathbb{Q}[y], determinamos que
L = \mathbb{Q}[\alpha] = \mathbb{Q}[y]/q(y) = \prod_{i=1}^n \mathbb{Q}[y]/q_i(y)
(nótese que L es un anillo reducido dado que p(x) es libre de radicales), donde \alpha corresponde al elemento (y,y,\ldots,y). Tenga en cuenta que esta es la única descomposición de L como un campo de productos. Por lo tanto esta descomposición es el mismo que
\prod_{i=1}^m K[x]/p_i(x)
donde
p(x) = \prod_{i=1}^m p_i(x)
es la factorización de p(x) sobre K[x]. Al escribir x\in L y generadores de K como polinomios en \alpha, podemos determinar las incrustaciones de x y K en las componentes \mathbb{Q}[y]/q_i(y)=K[x]/p_i(x). Al encontrar el polinomio mínimo de x en este anillo, hemos calculado p_i(x), y por lo tanto factorizar p(x) sobre K.


Teorema del resto. Factorización de polinomios

Factorización de polinomios, dividir polinomios por Ruffini, teorema del resto, formas de factorizar un polinomio.

División de polinomios: regla de Ruffini

Se deben colocar todos los coeficientes del dividendo ordenados de mayor a menor grado y si falta el de algún grado intermedio colocar un 0.
División por Ruffini


Factorizar un polinomio
Factorizar consiste en descomponer un polinomio como producto de otros más simples. Cuando un polinomio no se puede poner como producto de otros más simples se dice que es irreducible.
Para factorizar un polinomio hallamos su raíces, si a es una raíz de P(x), entonces P(x)=(x-a)·P1(x), así hemos descompuesto P como producto de dos polinomios, reiteramos el proceso, ahora con P1y seguimos hasta que nos encontremos con un polinomio irreducible. 
Factoriza el polinomio P(x)=2x5 -3x3 +4x2 -9x + 6
Usamos la regla de Ruffini, los candidatos a raíz serán los divisores de 6, es decir, 1, -1, 2, -1, 3, -2, 6, -6.
Vamos probando hasta que encontremos un valor cuyo resto es 0, repetimos el proceso con los coeficientes del polinomio cociente hasta que no podamos continuar, porque lleguemos a un polinomio irreducible.
En el ejemplo hemos llegado a un momento en el que no hemos encontrado raíces enteras 2x2 +3, con este polinomio podemos continuar planteando una ecuación de segundo grado, aún así no tiene raíces reales por tanto es irreducible. En la figura de la derecha se observa el proceso.
La factorización queda: 
2x5 -3x3 +4x2 -9x + 6 =(x-1)2(x+2)(2x2 +3)
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)