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:

Ö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 x2 - 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 x2 + 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 x4 + 4x2 + 3 endast imaginära nollställen men är faktoriserbart till (x2 + 1)(x2 + 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:

eftersom  och .

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 , där ,  och  är heltal, som är faktoriserbara över heltal, kan faktoriseras till

där
 
och
 

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 2x2 − 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 2x2 − 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  ä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

Faktorisering med kvadreringsreglerna

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

och

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

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:

Till exempel kan  faktoriseras till .

Ö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:

och

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

till

Genom att faktorisera största gemensamma delaren,

kan sedan parentesen faktoriseras, så att uttrycket blir
.
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

.

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)

genom ,  och .

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  där a, b och c är komplexa) kan faktoriseras till ett uttryck av formen  genom att använda rotformeln. Metoden är följande:

där  och  ä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
 
där ai , 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
  (läsbar för läsare som har studerat matematik på högskolenivå)

 Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.

Polynom