Factorització dels polinomis

De Viquipèdia
Dreceres ràpides: navegació, cerca

La factorització d'un polinomi consisteix a escriure'l com a producte de polinomis. Les factoritzacions interessants són aquelles que permeten escriure el polinomi inicial com a producte de polinomis de grau inferior al grau del polinomi de sortida. Un polinomi per al qual no existeix cap factorització d'aquest tipus es diu un polinomi irreductible.

La descomposició d'un polinomi en producte de polinomis irreductibles existeix, i és única, per a tot polinomi amb coeficients reals o complexos. Això també és cert quan els coeficients són en un anell factorial (anomenat també domini de factorització única), tant si el polinomi és d'una o diverses variables. Aquesta propietat és, per al conjunt dels polinomis, equivalent al teorema fonamental de l'aritmètica per al conjunt dels enters.

La cerca d'una factorització és un problema algorísmic de dificultat variable en funció de, en primer lloc, l'anell de coeficients considerat, i en segon lloc, la mida d'aquests coeficients i el grau del polinomi.

La factorització d'un polinomi és útil per reduir una funció racional en un producte de fraccions parcials.

Polinomis amb coeficients reals o complexos[modifica | modifica el codi]

Polinomis amb coeficients reals[modifica | modifica el codi]

Mètodes elementals[modifica | modifica el codi]

Les identitats notables i la propietat de distributivitat de la multiplicació sobre l'addició subministren mètodes elementals de factorització de polinomis

Exemples

  • 3x^2+9 = 3(x^2+3)
  • 4x^2-8x=4x(x-2)
  • x^2+2ax+a^2=(x+a)^2
  • x^2-b^2=(x-b)(x+b)
  • \forall n \ge 1,\, x^n - r^n=(x-r)(x^{n-1}+rx^{n-2}+ \cdots r^kx^{n-1-k}+\cdots+ r^{n-1})

La primera de les factoritzacions no descompon el polinomi en producte de polinomis de grau menor. Però, ofereix l'avantatge de presentar un polinomi en el que el coeficient del terme de més alt grau és 1. Tals polinomis s'anomenen mònics i s'utilitzen en les descomposicions per garantir-ne la unicitat.

La darrera factorització ofereix un mitjà per provar que tot polinomi P que tingui r com a arrel es pot escriure

P(x)=(x-r)Q(x)

on Q és de grau inferior al grau de P.


Tanmateix, a la pràctica, quan es coneix una arrel r, la factorització precedent es calcula més fàcilment fent servir la divisió de polinomis o el mètode de Ruffini.

Polinomis irreductibles[modifica | modifica el codi]

Els polinomis irreductibles en \R són els polinomis que no es poden descompondre en producte de dos polinomis de graus superiors o iguals a un. En particular, els polinomis de grau 1 són irreductibles.

Un polinomi de grau 2 que es pugui escriure com a producte de polinomis de grau 1 ha de tenir les arrels reals. Per contraposició, un polinomi de grau 2 que no tingui cap arrel real és irreductible. És el cas de tots els polinomis de grau 2 el discriminant dels quals és negatiu.

Es demostra que els únics polinomis amb coeficient reals irreductibles són d'aquest tipus (polinomis de grau 1 o polinomis de grau 2 el discriminant dels quals és negatiu). Aquest resultat en general es veu com una conseqüència del teorema fonamental de l'àlgebra, que es basa en els polinomis amb coeficients complexos.

Així el polinomi

P(x)=x^4+4

Que no sembla pas factoritzable de manera senzilla i que no té cap arrel (real) no és pas irreductible.

P(x)=x^4+4x^2+4 - 4x^2 = (x^2+2)^2 - (2x)^2 = (x^2-2x+2)(x^2+2x+2)

El teorema fonamental de l'àlgebra també permet demostrar que tot polinomi P amb coeficients reals té una descomposició única de la forma següent:

P(x) = a_n(x-r_1)^{\alpha_1}\cdots (x-r_k)^{\alpha_k}

On les arrels r que no són reals apareixen sempre en parelles de complexos conjugats, al multiplicar els membres da cada una d'aquestes parelles queden polinomis de grau dos amb coeficients reals.

Arrels i factorització[modifica | modifica el codi]

La relació entre les arrels d'un polinomi i la seva factorització justifica els estudis sobre la cerca de les seves arrels. Les investigacions s'orienten en dues direccions : càlcul d'arrels exactes eventualment per incursió en els complexos i càlcul d'arrels aproximades.

La primera via ha conduït a l'estudi dels coeficients dels polinomis, que segons las fórmules de Viète, s'expressen com a polinomis simètrics de les arrels. Aquesta via d'investigació, fructuosa sobre els polinomis de grau 3 i 4, i sobre certs polinomis de grau superior va fer creure que seria possible determinar totes les arrels d'un polinomi utilitzant només operacions de suma, producte, quocient i extracció d'arrels enèsimes, amb el preu de passar pels complexos. Si les arrels d'un polinomi s'escriuen efectivament així, es diu que és resoluble per radicals. En el segle XIX, Niels Henrik Abel demostrà que les equacions polinòmiques de grau superior o igual a 5 no són sempre resolubles per radicals (teorema d'Abel). Una classificació de les equacions resolubles per radicals ve donada per la teoria de Galois. Vegeu equació de segon grau, equació de tercer grau i equació de quart grau on hi ha les solucions per radicals que permeten trobar les arrels d'aquest polinomis. La segona via és la cerca d'arrels apropades dels polinomis. Són els algorismes de càlcul d'un zero d'una funció dels quals un dels clàssics és el mètode de Newton. Aquests mètodes requereixen determinar quantes arrels es troben en un interval donat. René Descartes amb la seva regla dels signes permet determinar el nombre de canvis de signe del valor d'un polinomi (i per tant el nombre d'arrels, ja que si el valor del polinomi passa de digne positiu a negatiu o viceversa en algun punt intermedi ha de valer zero) observant només el signe dels seus coeficients i pel mateix el nombre d'arrels. El teorema de Sturm permet determinar el nombre d'arrels simples (no conjugades i per tant en els polinomis amb coeficients reals arrels reals) d'un polinomi en un interval donat. Permet també separar les arrels en intervals diferents.

Polinomis amb coeficients complexos[modifica | modifica el codi]

Com s'ha indicat en la secció precedent, la investigació dels polinomis irreductibles amb coeficients reals i la factorització dels polinomis necessita una incursió en els complexos on les factoritzacions tenen una presentació simple.

En el conjunt dels complexos només els polinomis de grau 1 són irreductibles i tot polinomi P complex de grau n es descompon de manera única sota la forma següent :

P(x)= a_n\prod_{i=1}^k (x-r_i)^{\alpha_i}

amb \sum_{i=1}^k \alpha_i = n

L'arrel r_i es repeteix\alpha_i cops, és a dir és d'ordre \alpha_i.

Però persisteixen les mateixes dificultats a l'hora d'obtenir una factorització.

Exemples[modifica | modifica el codi]

Descompondre el polinomi X^4-1 \, amb coeficients en \ \R o en \mathbb{C}.

  • La identitat notable a^2-b^2 = (a+b)(a-b) \, dóna:
X^4-1=(X^2+1)(X^2-1) \,
i aplicant-la altre cop al segon terme:
\ X^4-1=(X^2+1)(X-1)(X+1).
Aquesta és la factorització en producte de factor irreductibles amb coeficients en \ \R.

Així es té que els signe de X^4-1 \, en funció de X és:

\begin{align}
 & x<-1\quad o\quad x>1\Rightarrow P\left( x \right)>0 \\ 
 & -1<x<1\Rightarrow P\left( x \right)<0 
\end{align}

  • La factorització en producte de factors irreductibles amb coeficients en \mathbb{C} és:
\ X^4-1 = (X+i)(X-i)(X-1)(X+1).

Més generalment, se sap factoritzar en \mathbb C després en \R, tot polinomi P de la forma X^n -a on a > 0. Si es nota

b=\sqrt[n]a

Les arrels e P són:

r_k=be^{i2k\pi/n}

i P té per descomposició en \mathbb C:

P(X)= \prod_{k_0}^{n-1}(X-be^{i2k\pi/n})

La descomposició en \R consisteix en agrupar les arrels conjugades. La descomposició és diferent segons que n sigui parell o senar

Polinomis amb coeficients en un anell[modifica | modifica el codi]

Quan els coeficients no són reals o complexos, els polinomis irreductibles poden ser de grau superior a 2 i no sempre hi ha unicitat de la factorització.

Polinomis irreductibles[modifica | modifica el codi]

S'anomena polinomi irreductible a tot polinomi de grau superior o igual a un els únics divistrs del qual són els polinomis de grau nul o els polinomis associats. En Altres Paraules

P és irreductible si i només si deg(P)\ge > 1 i \forall (Q,R) \in A[X]^2 \quad P=QR \Rightarrow deg(Q)=0 \or deg(R)=0

En un anell íntegre, els següents resultats són immediats:

  • Tot polinomi de grau u és irreductible
però no és el cas en un anell qualsevol. en efecte en  \Z/6\Z, P(x)=5x+1 = (2x+1)(3x+1)
  • Tot polinomi de grau dos és irreductible si no té arrel

Els polinomis reductibles en \R poden resultar irreductibles en \mathbb Q:

p(x)=x^2-2 és reductible en \R però no és reductible en \mathbb Q (perquè \sqrt{2} no és un nombre racional)

Le lema de Gauss permet permet afirmar que tot polinomi de \Z[X] irreductible en \Z[X] també ho és en \mathbb Q[X]

El criteri d'Eisenstein dona a una condició suficient perquè un polinomi de \Z[X] sigui irreductible: n'hi ha prou amb trobar un nombre primer que sigui divisor de tots els coeficients de P excepte el coeficient del terme de grau més alt i tal del que p^2 no sigui divisor del terme constant. Així

P(x)=x^4 - 9x^3 +3x^2-6x+15 és irreductible en \Z[X] car 3 divideix tots els coeficients tret del terme de grau 4 i 9 no divideix pas 15.

Factorització[modifica | modifica el codi]

Article principal: anell factorial

En un anell íntegre, l'existència d'una descomposició d'un polinomi no constant en producte de polinomis irreductibles és una conseqüència immediata de la definició d'un polinomi irreductible. Una inducció completa ho prova fàcilment: els polinomis de grau 1 són irreductibles. Se suposa que tot polinomi de grau estrictament inferior a n és irreductible (és a dir descomponible en producte de polinomis irreductibles). Sigui llavors P un polinomi de grau n, és o bé irreductible o bé descomponible en producte de dos polinomis de grau estrictament inferiors a n ells mateixos producte de polinomis irreductibles.

Tanmateix la unicitat de la descomposició, no és verdadera més que sobre els anells factorials. I no és sempre possible descompondre'l en producte de polinomis unitaris multiplicat per una de constant.

P(x)= 6x^2-5x+1 = (2x-1)(3x-1) = (1-2x)(1-3x)

és una descomposició única a tret del factor (-1).

En un anell que no sigui factorial, per exemple \Z[i\sqrt 3], es poden trobar polinomis que tenen descomposició diferents: fixant-se que

4 = 2 \times 2 = (1+i\sqrt3)(1-i\sqrt3)=ab

Es pot escriure

P(x)= 4x^2-4 = (2x-2)(2x+2)=(ax-a)(bx+b)

qui dóna dues descomposicions diferents.

En tot cos, (com que és un cas particular d'anell factorial), tot polinomi no constant de  \mathbb K[X] té una descomposició única en forma de producte de polinomis unitaris irreductibles multiplicats per una constant.

Polinomis amb diverses variables[modifica | modifica el codi]

Si A és un anell factorial, A[X] és factorial, llavors A[X][Y] = A[X,Y] és també factorial i n'és igualment A[X_1,X_2,\cdots,X_n]. Un polinomi amb n variables sobre un anell factorial és doncs sempre descomponible de manera única en productes de polinomis irreductibles.

Algorismes de descomposició[modifica | modifica el codi]

Segons la naturalesa de l'anell dels coeficients considerat, els algorismes de factorització dels polinomis en producte de polinomis irreductibles són de dificultat variable.

En el cas de coeficients reals o complexos, l'obtenció d'una factorització exacta amb coeficients en escriptura decimal és en general impossible, ja que l'escriptura d'una arrel requereix una infinitat de decimals. Tanmateix nombrosos algorismes, dels quals el més cèlebre és el mètode de Newton, permeten obtenir aproximacions tan bones com es vulgui. Tal algorisme iteratiu, sota bones condicions de partida, pot doblar (fins i tot més que doblar) el nombre de decimals obtinguts a cada iteració. Condicions de sortida acceptables poden ser obtingudes utilitzant prèviament algorismes de separació de les arrels. El cas de les arrels múltiples, o extremadament pròximes, necessita consideracions particulars.

En el cas dels polinomis amb coeficients a cossos finits, per a un polinomi fixat, no existeix més que un nombre finit de divisors potencials, els polinomis de grau inferior. Un algorisme ingenu consisteix doncs a factoritzar un polinomi provant la seva divisibilitat pels polinomis de grau inferior, de manera anàloga a l'algorisme ingenu de divisió dels enters. Tanmateix, existeixen algorismes força més eficaços. Han estat descoberts entre la fi dels anys 1960 i el començament dels anys 1980, i són de complexitat polinòmica, determinista o probabilista, per exemple l'algorisme de Berlekamp, o el de Cantor-Zassenhaus.

De la factorització polinomis amb coeficients als cossos finits es dedueixen dels algorismes de factorització en altres dominis. En principi per als polinomis dels quals els coeficients són nombres p-adics, amb la restricció, com en el cas dels coeficients reals i complexos, que no es pot obtenir en tant que finit més que un nombre finit de termes d'un desenvolupament p-adic (els factors irreductibles poden ser de qualsevol grau, i no només de grau 1 o 2 com en els casos reals i complexos). Això es pot fer gràcies a una versió algorísmica del lema de Hensel. Llavors, per als polinomis amb coeficients racionals, o en cossos de nombres. El pas d'una factorització en l'àmbit dels coeficients p-adics a una factorització amb coeficients racionals és possible ja que la segona s'obté reagrupant convenientment els factors de la primera. És possible de provar totes aquestes combinacions, el que pot ser de complexitat algorítmica exponencial, o bé transformr aquest problema a un problema algorísmic d'àlgebra lineal de tipus problema de la motxilla. Aquests algorismes encara estan sent millorats als començaments dels anys 2000 (veure algorisme de Van Hoeij).

Finalment, aconseguir la factorització dels polinomis amb coeficients sencers és equivalent algorísmicament a aconseguir conjuntament factoritzar els enters i els polinomis amb coeficients racionals.

Vegeu també[modifica | modifica el codi]