Polynomfaktorisering

Inom matematik och datoralgebra innebär polynomfaktorisering att ett polynom delas upp som en produkt av faktorer som är enklast möjliga polynom. Idén är densamma som för uppdelning av ett sammansatt tal i primtalsfaktorer.

Exempel: ${\displaystyle x^{2}-7x+6=(x-6)(x-1)\,}$

Överblick

De polynom som är "enklast möjliga" kallas irreducibla polynom och är polynom som inte kan skrivas som en produkt av polynom av lägre grad, det vill säga de kan inte faktoriseras. Vilka polynom som är irreducibla beror på vilka tal man kan använda i sin faktorisering. Exempelvis är polynomet x² - 2 irreducibelt över de rationella talen, men kan faktoriseras över de reella talen.

Förstagradspolynom är alltid irreducibla. Algebrans fundamentalsats säger att över de komplexa talen är de även de enda irreducibla polynomen (mer allmänt gäller detta över en algebraiskt sluten kropp). Över de reella talen finns även andragradspolynom som är irreducibla, exempelvis x² + 1. Över de rationella talen och heltalen kan även polynom av högre grad vara irreducibla.

Faktorsatsen säger att ett polynom p(x) har ett nollställe i a om och endast om p(x) = (x - a)q(x) för något polynom q(x). Genom polynomdivision kan man, efter att ha hittat nollstället a, hitta q(x) och sedan fortsätta faktorisera detta polynom. Detta ger att ett polynom av grad 2 eller 3 är irreducibelt över talen man arbetar i om och endast om det saknar nollställen (i talen man arbetar i). Polynom av högre grad kan dock vara reducibla utan att ha något nollställe, exempelvis har x⁴ + 4x² + 3 endast imaginära nollställen men är faktoriserbart till (x² + 1)(x² + 3) över de reella talen (samt de rationella talen och heltalen).

Faktorisering över heltal och rationella tal

Det går att bevisa att faktorisering över rationella talen kan reduceras till faktorisering över heltalen. Detta är ett specifikt fall av det allmänna resultatet av Gauss lemma för polynom. Varje polynom kan faktoriseras i två delar, innehållet (ett rationellt tal) och ett primitivt polynom, exempelvis:

${\displaystyle {\frac {1}{3}}x^{5}+{\frac {7}{2}}x^{2}+2x+1={\frac {1}{6}}(2x^{5}+21x^{2}+12x+6)}$

eftersom ${\displaystyle \mathrm {SGD} (1,7,2,1)=1}$ och ${\displaystyle \mathrm {MGM} (3,2)=6}$.

Samma metod kan användas för alla polynom med rationella koefficienter. Innehållet är ett rationellt tal sådant att dess täljare är största gemensamma delare för koefficienternas täljare och nämnaren är minsta gemensamma multipel för koefficienternas nämnare, då man får ett heltalspolynom som är primitivt, dvs dess koefficienter saknar gemensamma delare. Detta polynom kan sedan, ifall det inte är irreducibelt, faktoriseras till mindre polynom över de rationella talen. Man kan nu dela upp faktorerna i dess innehåll och primitiva delar. Därmed kan faktorisering över rationella tal reduceras till faktorisering över heltal.

Andragradspolynom

Andragradsekvationer av formen ${\displaystyle ax^{2}+bx+c}$, där ${\displaystyle a}$, ${\displaystyle b}$ och ${\displaystyle c}$ är heltal, som är faktoriserbara över heltal, kan faktoriseras till

${\displaystyle (mx+p)(nx+q),\,\!}$

där

${\displaystyle mn=a,\ pq=c\,\!}$

och

${\displaystyle pn+mq=b.\,}$

Ur den faktoriserade formen av polynomet kan man se att polynomets nollställen fås genom att sätta vardera binomet lika med noll och lösa med avseende på x.

Ta till exempel 2x² − 5x + 2. Eftersom a = 2 och mn = a, bör endera m eller n vara 1 och den andra 2. Eftersom c = 2 och pq = c, är p och q antingen 1 och 2, eller −1 och −2. Genom att substituera de olika alternativen i pn + mq = b fås resultatet att 2x² − 5x + 2 kan faktoriseras i (2x − 1)(x − 2). Samtidigt fås polynomets nollställen x = {0.5, 2}.

Obs: Ett snabbt sätt att kolla ifall den andra termen i binomet skall vara positiv eller negativ, är genom att kolla tecknen (+ eller −) i ursprungspolynomet. Om alla tecken i ursprungspolynomet är positiva, är även alla tecken i binomen positiva. Ifall den andra termen i ursprungspolynomet är positiv, men den sista är negativ, är någondera av binomens andra term negativ. Vilkendera som är negativ kan konstateras genom att prova de båda alternativen. Om däremot den andra termen i ursprungspolynomet är negativ, men både sista och första är positiva, är binomens båda andra termer negativa.

Ett lätt sätt att kolla om ett andragradspolynom med heltalskoefficienter går att faktorisera över heltal ${\displaystyle \mathbb {Z} }$ är genom att kolla dess diskriminant. Ifall diskriminanten är en kvadrat, kommer faktorisering över heltalen att vara möjlig.

Faktorisering genom utbrytning

I fallet att konstanttermen saknas i andragradspolynomet kan faktorisering trivialt ske genom utbrytning. Ifall en gemensam delare för termerna kan hittas, bryts den största gemensamma delaren ut till faktor och som andra faktor bildas en parentes som innehåller restprodukterna från polynomet.

Till exempel

${\displaystyle 2x^{2}+3x=x(2x+3).\,\!}$

Faktorisering med kvadreringsreglerna

Vissa andragradspolynom kan faktoriseras till två identiska binom. Detta sker genom de så kallade kvadreringsreglerna som ser ut som följande:

${\displaystyle a^{2}+2ab+b^{2}=(a+b)^{2},\,\!}$

och

${\displaystyle a^{2}-2ab+b^{2}=(a-b)^{2}.\,\!}$

Faktorisering med konjugatregeln

En annan typ av andragradspolynom går att faktorisera med hjälp av konjugatregeln. Det är en tillämpning av följande regel

${\displaystyle a^{2}-b^{2}=(a+b)(a-b),\,\!}$

som faktoriserar ett polynom till två termer, vare sig de är kvadrater eller inte. Ifall den andra termen i ursprungspolynomet är positiv blir de andra termerna i binomen irrationella. Då ser regeln ut som följande:

${\displaystyle a^{2}+b^{2}=(a+bi)(a-bi).\,\!}$

Till exempel kan ${\displaystyle 4x^{2}+49}$ faktoriseras till ${\displaystyle (2x+7i)(2x-7i)}$.

Övriga polynom

Faktorisering genom binomialsatsen

Kvadreringsreglerna är ett specialfall av binomialsatsen. Faktorisering genom binomialsatsen är möjlig på samma sätt som enligt kvadreringsreglerna. Till exempel för tredjegradspolynom gäller:

${\displaystyle a^{3}+b^{3}=(a+b)(a^{2}-ab+b^{2}),\,\!}$

och

${\displaystyle a^{3}-b^{3}=(a-b)(a^{2}+ab+b^{2}).\,\!}$

Faktorisering genom gruppering

Ibland kan faktorisering ske enkelt genom gruppering. Detta görs genom att gruppera polynomets termer till två eller flera grupper som sedan kan faktoriseras enligt känd metod. Resultatet av dessa faktoriseringar kan sedan eventuellt leda till ett steg till av faktorisering som förenklar uttrycket ytterligare. Exempelvis kan man gruppera om

${\displaystyle x^{4}+3x^{3}-5x-15\,}$

till

${\displaystyle (x^{4}-5x)+(3x^{3}-15)\,}$

Genom att faktorisera största gemensamma delaren,

${\displaystyle x(x^{3}-5)+3(x^{3}-5)\,}$

kan sedan parentesen faktoriseras, så att uttrycket blir

${\displaystyle (x^{3}-5)(x+3)\,}$.

Denna metod kan också tillämpas på flervariabelpolynom.

Kroneckers metod

Ett allmännare sätt att faktorisera polynom över heltal är genom Kroneckers metod som baserar sig på att ett, över heltal faktoriserbart, polynom f(x) med grad n, n ≥ 2, kan faktoriseras till två polynom g(x) och h(x) varav någondera högst har graden n / 2. För ett polynom med grad n / 2 krävs n / 2 + 1 st värden för att explicit definiera polynomet och genom att välja lämpliga värden ur f(x) kan man begränsa alternativens antal. Det slutliga polynomet fås sedan genom att prova sig fram bland dessa värden.

Till exempel polynomet

${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$.

Som, om det är faktoriserbart över heltalen, måste ha en faktorer med lägre grad än två. För att explicit definiera polynomet behövs alltså 3 värden. Ur ursprungspolynomet fås värdena f(0) = 2, f(1) = 6 och f(-1) = 2. 2 kan endast faktoriseras till

1×2, 2×1, (−1)×(−2) eller (−2)×(−1).

vilket innebär att den sökta faktorn måste få värdet

1, 2, −1, eller −2

vid x = 0 och x = 1. 6 i sin tur kan faktoriseras på 8 olika sätt, vilket innebär att det finns

4×4×8 = 128

olika alternativ. Hälften av dessa är dock den negativa motsvarigheten till den andra halvan, vilket leder oss till 64 möjliga heltalspolynom av andra graden som måste testas. Dessa är de enda möjliga heltalspolynomsfaktorer till f(x). Genom att kolla dem alla hittas den riktiga faktorn till f(x)

${\displaystyle g(x)=x^{2}+x+1,\,}$

genom ${\displaystyle g(0)=1}$, ${\displaystyle g(1)=3}$ och ${\displaystyle g(-1)=1}$.

LLL-algoritmen

LLL-algoritmen var den första polynomtidsalgoritmen för faktorisering av rationella polynom. Den använder sig av Lenstra–Lenstra–Lovász gitterbasreduktionsalgoritm.

Faktorisering över kroppar

En mer allmän beskrivning fås genom att studera polynomfaktorisering över algebraiska kroppar.

Andragradspolynom

Alla andragradspolynom i kroppen av komplexa tal (med formen ${\displaystyle ax^{2}+bx+c}$ där a, b och c är komplexa) kan faktoriseras till ett uttryck av formen ${\displaystyle a(x-\alpha )(x-\beta )\ }$ genom att använda rotformeln. Metoden är följande:

${\displaystyle {\begin{aligned}ax^{2}+bx+c&=a(x-\alpha )(x-\beta )\\&=a\left(x-{\frac {-b+{\sqrt {b^{2}-4ac}}}{2a}}\right)\left(x-{\frac {-b-{\sqrt {b^{2}-4ac}}}{2a}}\right),\end{aligned}}}$

där ${\displaystyle \alpha }$ och ${\displaystyle \beta }$ är polynomets två rötter eller nollställen av polynomet.

Övriga polynom

Generellt kan konstateras att polynom kan faktoriseras med hjälp av dess nollställen. Polynomet f(x) av graden n, n ≥ 2 kan alltså faktoriseras till

${\displaystyle k\prod _{i=1}^{n}(x-a_{i})}$

där a_i , i = 1, 2, ... , n är polynomets nollställen. Dock är det inte garanterat att nollställena ligger i samma kropp som koefficienterna i polynomet, om inte kroppen är algebraiskt sluten. I allmänhet måste man använda en kroppsutvidgning som är algebraiskt sluten, eller åtminstone en kropp som innehåller alla nollställen till polynomet, polynomets splittringskropp.

Bibliografi

• Bernard Beauzamy, Per Enflo, Paul Wang (3 november 1994). ”Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation”. Mathematics Magazine "67" (4): ss. 243–257. http://www.jstor.org/stable/2690843.  (läsbar för läsare som har studerat matematik på högskolenivå)
• Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics. "138". Berlin, New York: Springer-Verlag. MR1228206. ISBN 978-3-540-55640-4 
• Knuth, Donald E (1997). ”4.6.2 Factorization of Polynomials”. Seminumerical Algorithms. The Art of Computer Programming. "2" (Third). Reading, Massachusetts: Addison-Wesley. sid. 439–461, 678–691. ISBN 0-201-89684-2 
• Lenstra, A. K. (3 november 1982). ”Factoring polynomials with rational coefficients”. Mathematische Annalen "261" (4): ss. 515–534. doi:10.1007/BF01457454. MR682664. ISSN 0025-5831. 
• Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.
• Svensson, Per-Anders (2001). Abstrakt algebra. Studentlitteratur. ISBN 91-44-01262-4