Faktorizace polynomů

V matematice je faktorizace polynomu spočívá v psaní jako součin polynomů. Zajímavé jsou faktorizace, které umožňují zapsat počáteční polynom jako produkt několika neinvertibilních polynomů. Nevratný polynom, pro který žádná taková faktorizace neexistuje, se nazývá neredukovatelný polynom .

Rozklad polynomu na produkty neredukovatelných polynomů existuje a má vlastnost jedinečnosti (kromě invertibilního faktoru) pro jakýkoli polynom se skutečnými nebo složitými koeficienty. To stále platí, když jsou koeficienty ve faktoriálním kruhu , ať už má polynom jeden nebo více neurčitých. Tato vlastnost je pro množinu polynomů analogická základní teorému aritmetiky pro množinu celých čísel .

Hledání faktorizace je algoritmickým problémem proměnné obtížnosti v závislosti jednak za prvé na uvažovaném kruhu koeficientů, a zadruhé na velikosti těchto koeficientů a stupni polynomu.

Faktorování polynomu je užitečné pro rozložení racionálního zlomku na součet jednoduchých prvků .

Polynomy se skutečnými nebo složitými koeficienty

Polynomy se skutečnými koeficienty

Základní metody

Tyto pozoruhodné identity a majetkem distributivity násobení o přidávání poskytnout základní metody faktorizace polynomů

Příklady

$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} = (xb) (x + b)$
$\ forall n \ geq 1, \, x ^ {n} -r ^ {n} = (xr) (x ^ {{n-1}} + rx ^ {{n-2}} + \ cdots r ^ { k} x ^ {{n-1-k}} + \ cdots + r ^ {{n-1}})$

První z faktorizací nerozkládá polynom na produkt polynomů menšího stupně. Nabízí však tu výhodu, že představuje polynom, jehož koeficient termínu nejvyššího stupně je 1. O takových polynomech se říká, že jsou jednotné a používají se v rozkladech, aby byla zaručena jeho jedinečnost.

Poslední faktorizace nabízí způsob, jak dokázat, že lze zapsat libovolný polynom P s kořenem r

P (x) = (xr) Q (x)

kde Q je stupně menšího než stupeň P.

Demonstrace

Předchozí pozoruhodná identita to potvrzuje

\ forall k \ geq 1, x ^ {k} -r ^ {k} = (xr) p_ {k} (x)

kde je polynom stupně k-1 $p_ {k}$

Nechť P je polynom

P (x) = \ součet _ {{k = 0}} ^ {n} a_ {k} x ^ {k}

Protože r je kořen P, máme P (r) = 0, takže

P (x) = P (x) -P (r) = \ součet _ {{k = 1}} ^ {n} a_ {k} (x ^ {k} -r ^ {k}) = (xr) \ left (\ sum _ {{k = 1}} ^ {n} a_ {k} p_ {k} (x) \ right) = (xr) Q (x)

V praxi, když je známý kořen r, se však předchozí faktorizace vypočítá místo toho pomocí polynomiálního dělení nebo Hornerovy metody .

Neredukovatelné polynomy

Na libovolném poli jsou neredukovatelné polynomy polynomy, které nelze rozložit na součin dvou nekonstantních polynomů . Polynomy stupně 1 jsou proto vždy neredukovatelné.

Polynom stupně 2, který lze zapsat jako součin polynomů stupně 1, bude mít kořeny. Kontrapozicí je polynom stupně 2 bez kořene neredukovatelný. Na ℝ to platí pro všechny polynomy stupně 2, jejichž diskriminátor je negativní (viz článek Rovnice druhého stupně ).

Dokazujeme, že jediné polynomy se skutečnými neredukovatelnými koeficienty jsou tohoto typu (polynomy stupně 1 nebo polynomy stupně 2, jejichž diskriminátor je negativní). Tento výsledek je důsledkem d'Alembert-Gaussovy věty , která se týká polynomů se složitými koeficienty.

Tedy skutečný polynom

P (x) = x ^ {4} +4,

který se nezdá, že je faktorizovatelný jednoduchým způsobem (nemá kořen), není neredukovatelný (ve skutečnosti je to faktorizovatelné díky identitě Sophie Germain ).

P (x) = x ^ {4} + 4x ^ {2} + 4-4x ^ {2} = (x ^ {2} +2) ^ {2} - (2x) ^ {2} = (x ^ {2} -2x + 2) (x ^ {2} + 2x + 2).

Stejná d'Alembert-Gaussova věta také umožňuje dokázat, že rozklad (jedinečný v pořadí) libovolného polynomu se skutečnými koeficienty má tvar

a_ {n} (x-r_ {1}) ^ {{\ alpha _ {1}}} \ cdots (x-r_ {k}) ^ {{\ alpha _ {k}}} \ prod _ {{i = 1}} ^ {l} p_ {i} (x) ^ {{\ beta _ {i}}}

kde $p i$ jsou jednotkové neredukovatelné polynomy stupně 2.

Kořeny a faktorizace

Souvislost mezi kořeny polynomu a jeho faktorizací ospravedlňuje studium jeho kořenů. Výzkum se ubírá dvěma směry: hledání přesných kořenů pravděpodobně vpádem do komplexů a hledání přibližných kořenů.

První cesta vedla ke studiu koeficientů polynomů, které jsou podle Vièteovy věty vyjádřeny jako symetrické polynomy kořenů. Tato řada výzkumu, plodná na polynomech stupně 3 a 4 a na určitých polynomech vyššího stupně, vedla k domněnce, že by bylo možné určit všechny kořeny polynomu pouze pomocí operací součtu, součinu, kvocientu a n. extrakce kořenů, i když to znamená procházet komplexy. Pokud jsou kořeny polynomu skutečně zapsány takto, říkáme, že je řešitelný radikály. V průběhu XIX th století, Niels Henrik Abel ukazuje, že polynom rovnice studia větší nebo rovno 5, nejsou všechny řešitelné radikály ( věta Abel ). Klasifikace radikálově řešitelných rovnic je dána Galoisovou teorií .

Druhým způsobem je hledání přibližných kořenů polynomů. Jedná se o algoritmy pro nalezení nuly funkce, jednou z klasik je Newtonova metoda . Tyto metody vyžadují určení počtu kořenů v daném intervalu. Descartes podle svého právního značek umožňuje určit počet změn znamení polynom pozorováním pouze znak jeho koeficientů a stejným počtem kořenů. Sturm věta se používá k určení počtu kořenů v daném intervalu polynomu, který má pouze jednoduché kořeny. Umožňuje také rozdělení kořenů do samostatných intervalů.

Polynomy se složitými koeficienty

Jak je uvedeno v předchozí části, hledání neredukovatelných polynomů se skutečnými koeficienty a faktorizace polynomů vyžaduje invazi do komplexů, kde mají faktorizace jednoduchou prezentaci.

V sadě komplexů jsou jedinými neredukovatelnými polynomy polynomy stupně 1 a jakýkoli složitý polynom P stupně n se jedinečným způsobem rozkládá v následující podobě:

P (x) = a_ {n} \ prod _ {{i = 1}} ^ {k} (x-r_ {i}) ^ {{\ alpha _ {i}}}

s $\ sum _ {{i = 1}} ^ {k} \ alpha _ {i} = n$

O kořenu se říká, že je v pořádku . $r_i$ $\ alpha_i$

Stejné potíže však přetrvávají i při účinném zavedení faktorizace.

Demonstrace

Dovolit být neredukovatelný polynom stupně většího nebo rovného 2. $P \ in \ mathbb {R} [X]$

$P$ nepřipustí kořeny v , ale jak , připouští kořen v . Také je nesnížitelný v , . $\ mathbb {R}$ $P \ in {\ mathbb {C}} [X]$ $P$ $\ alfa$ $\ mathbb {C}$ $P$ $\ mathbb {R} [X]$ $\ alpha \ not \ in \ mathbb {R}$

Existuje tedy něco takového . ${\ displaystyle Q \ v \ mathbb {C} [X]}$ $P = (X- \ alfa) Q$

V konjugátu je . Ale jak , . Takže je kořen . ${\ displaystyle \ mathbb {C} [X]}$ $P$ $\ overline {P} = \ left (X- \ overline {\ alpha} \ right) \ overline {Q}$ $P \ in \ mathbb {R} [X]$ $P = \ overline {P} = \ left (X- \ overline {\ alpha} \ right) \ overline {Q}$ $\ overline {\ alpha}$ $P$

Jako , je dělitelné . $\ alpha \ neq \ overline {\ alpha}$ $P$ $\ left (X- \ alpha \ right) \ left (X- \ overline {\ alpha} \ right) = X ^ {2} - (\ alpha + \ overline {\ alpha}) X + \ alpha \ overline {\ alpha} \ in \ mathbb {R} [X]$

Jak je neredukovatelné s . $P$ $P = \ lambda \ left (X ^ {2} - (\ alpha + \ overline {\ alpha}) X + \ alpha \ overline {\ alpha} \ right)$ $\ lambda \ in \ mathbb {R}$

Tudíž je stupeň 2, neexistuje tedy žádný neredukovatelný polynom stupně většího nebo rovného 3 palce . $P$ $\ mathbb {R} [X]$

Příklady

Uvažujme polynom s koeficienty v nebo . $X ^ {4} -1 \,$ $\ \ mathbb {R}$ $\ mathbb {C}$

Pozoruhodná identita dává: $a ^ {2} -b ^ {2} = (a + b) (ab) \,$

X ^ {4} -1 = (X ^ {2} +1) (X ^ {2} -1) \,

pak:

\ X ^ {4} -1 = (X ^ {2} +1) (X-1) (X + 1)

. Toto je produktová faktorizace neredukovatelných faktorů s koeficienty v .

\ \ mathbb {R}

Znaménko tedy máme jako funkci X (samozřejmě skutečné): $X ^ {4} -1 \,$

X <-1 nebo X> 1 ⇒ P (X)> 0

-1 <X <1 ⇒ P (X) <0

Produktová faktorizace neredukovatelných faktorů s koeficienty v je: $\ mathbb {C}$

\ X ^ {4} -1 = (X + i) (Xi) (X-1) (X + 1)

Obecněji řečeno, víme, jak faktor tehdy , jakékoliv polynomu P formě kde a> 0. Označíme $\ mathbb {C}$ $\ mathbb {R}$ $X ^ {n} -a$

b = {\ sqrt [{n}] a}

kořeny P jsou:

r_ {k} = be ^ {{i2k \ pi / n}}

a P má pro rozklad v : $\ mathbb {C}$

P (X) = \ prod _ {{k = 0}} ^ {{n-1}} (X-be ^ {{i2k \ pi / n}})

Rozklad spočívá ve seskupení kořenů konjugátu. Rozklad se liší podle toho, zda je n sudé nebo liché. $\ mathbb {R}$

Polynomy s koeficienty v kruhu

Pokud koeficienty nejsou skutečné nebo komplexní, neredukovatelné polynomy mohou být o stupeň větší než 2 a existence neredukovatelné polynomické součinnosti produktu není zaručena.

Neredukovatelné polynomy

Polynom se nazývá ireducibilní jakýkoli polynom P noninvertible jehož pouze dělitele jsou reversal polynomy a polynomy spojené s P . Jinými slovy

P je neredukovatelný, pokud je přesně jeden ze dvou faktorů Q nebo R invertibilní.

\ forall (Q, R) \ v A [X] ^ {2} \ quad P = QR \ Rightarrow

Dokonce i na kruhu integrity

polynom stupně 0 nebo 1 není nutně neredukovatelný. Například v , a . $\ mathbb {Z} [X]$ $6 = 2 \ krát 3$ $6X = 2 \ krát (3x)$
neredukovatelný polynom stupně (větší než nebo) rovný 2 nemá kořen, ale polynom stupně 2 bez kořene není nutně neredukovatelný. Například , . $\ mathbb {Z} [X]$ $2X ^ {2} + 2 = 2 \ krát (X ^ {2} +1)$

Polynomy redukovatelné na mohou být neredukovatelné na : je redukovatelné na, ale neredukovatelné na . $\ mathbb {R}$ ${\ mathbb Q}$ $X ^ {2} -2$ $\ mathbb {R} [X]$ $\ mathbb {Q} [X]$

Lemma Gauss o tom, že jakékoli jiné než konstantní a ireducibilní polynom je také v . $\ mathbb {Z} [X]$ ${\ mathbb Q} [X]$

Kritérium Eisenstein poskytuje dostačující podmínkou pro primitivní polynomu P je nesnížitelný: stačí najít prvočíslo dělící všechny koeficienty P, pokud není termín koeficientu na nejvyšší úrovni a tak, že nerozděluje termín konstantní. Tak $\ mathbb {Z} [X]$ $p$ $p ^ {2}$

X ^ {4} -9X ^ {3} + 3X ^ {2} -6X + 15

je ireducibilní, protože 3 rozděluje všechny koeficienty kromě toho, že u termínu stupně 4 a 9 nedělí 15.

\ mathbb {Z} [X]

Factoring

Pokud A je integrální prstenec, jehož všechny prvky mají jedinečný neredukovatelný rozklad faktoru s výjimkou invertibilního, tj. Pokud A je faktoriální prstenec, pak jakýkoli polynom A [X] má také jedinečné polynomy rozkladu produktu neredukovatelné na invertibilní blízké.

Protože pole je příkladem faktoriálního prstence, jakýkoli nekonstantní polynom má jedinečný rozklad jako produkt neredukovatelných jednotkových polynomů vynásobených konstantou. ${\ mathbb K} [X]$

Polynomy v několika neurčitých

Pokud A je faktoriální kruh, A [X] je faktoriál, pak A [X] [Y] = A [X, Y] je také faktoriál, a tak je . Polynom s n neurčitým na faktoriálním prstenci je proto vždy jedinečným způsobem rozložitelný (s výjimkou invertibilního) na produkty neredukovatelných polynomů. $A [X_ {1}, X_ {2}, \ cdots, X_ {n}]$

Algoritmy rozkladu

V závislosti na povaze uvažovaného kruhu koeficientů mají algoritmy pro faktorování polynomů na neredukovatelné produkty různou obtížnost.

Polynomy se skutečnými nebo složitými koeficienty

V případě reálných nebo komplexních koeficientů je získání přesné faktorizace s koeficienty v desítkovém zápisu obecně nemožné, protože zápis kořene vyžaduje nekonečno desetinných míst. Mnoho algoritmů, z nichž nejznámější je Newtonova metoda , však umožňuje získat aproximace tak dobré, jak je požadováno. Takový iterační algoritmus může za dobrých počátečních podmínek zdvojnásobit (nebo dokonce lépe) počet desetinných míst získaných při každé iteraci. Přijatelné počáteční podmínky lze získat nejprve použitím algoritmů oddělení kořenů. Případ více kořenů nebo extrémně blízko u sebe vyžaduje zvláštní úvahy.

Polynomy s koeficienty v konečném poli

V případě polynomů s koeficienty v konečných polích existuje pro pevný polynom pouze konečný počet potenciálních dělitelů, polynomy nižšího stupně. Naivní algoritmus proto spočívá ve faktorování polynomu testováním jeho dělitelnosti polynomy nižšího stupně, analogickým způsobem jako naivní algoritmus pro dělení celých čísel. Existují však mnohem efektivnější algoritmy. Byly objeveny mezi koncem 60. a začátkem 80. let a mají polynomiální, deterministickou nebo pravděpodobnostní složitost , například Berlekampův algoritmus nebo Cantor-Zassenhaus . O faktorizaci polynomů s koeficienty v konečných polích jsou odvozeny z algoritmů faktorizace v jiných oborech. Nejprve pro polynomy, jejichž koeficienty jsou p -adická čísla , s omezením, jako je tomu v případě reálných a komplexních koeficientů, že lze v konečném čase získat pouze konečný počet členů vývojové p-adic (lze redukovat neredukovatelné faktory jakéhokoli stupně, nejen stupně 1 nebo 2, jako ve skutečných a složitých případech).

Polynomy s celočíselnými nebo racionálními koeficienty

Vynásobením polynomu s racionálními koeficienty jmenovatelem společným pro všechny jeho koeficienty se vrátíme k polynomu s celočíselnými koeficienty., Faktorizace v nebo v je tedy ekvivalentní. ${\ displaystyle \ mathbb {Q} [X]}$ ${\ displaystyle \ mathbb {Z} [X]}$

Algoritmy faktorizace polynomů s celočíselnými koeficienty nejprve provedou faktorizaci v konečném poli díky algoritmu Berlekampa a jdou nahoru ve větším konečném poli pomocí Henselova lematu . Faktorizace se potom získá seskupením faktorů. Nejjednodušší metoda pak spočívá v testování všech možností, ale tato má exponenciální složitost. Další metodou je snížit tento problém na problém typu batoh a poté jej vyřešit pomocí algoritmu LLL. ${\ mathbb {F}} _ {{p}}$ ${\ displaystyle \ mathbb {Z} / _ {p ^ {k} \ mathbb {Z}}}$ ${\ displaystyle \ mathbb {Z} [X]}$

Konkrétně myšlenka algoritmu je následující: Dáme sami polynom , který můžeme považovat bez ztráty obecnosti jednotky bez čtverečních faktory, a my to faktor v s prime, které byly vybrány tak, že zbývající bez hranatých faktorů. Tento rozklad se potom znovu sestaven v se volí tak, aby $P$ ${\ displaystyle P = GH}$ ${\ mathbb {F}} _ {{p}}$ $p$ $P$ ${\ displaystyle P = {\ hat {G}} {\ hat {H}}}$ ${\ displaystyle \ mathbb {Z} / _ {p ^ {k} \ mathbb {Z}}}$ $k$ ${\ displaystyle || P || ^ {2n-1} \ cdot n ^ {\ dfrac {n} {2}} \ cdot {\ begin {pmatrix} n-1 \\\ left \ lfloor {\ dfrac {n -1} {2}} \ right \ rfloor \ end {pmatrix}} ^ {n} \ cdot 2 ^ {\ dfrac {n (n-1)} {2}} <p ^ {kl}}$

kde je stupeň a že . Poté uvažujeme základ sítě, který redukujeme pomocí LLL. Podmínka on pak zajistí, že pokud je první vektor redukované báze prvočíselný , pak je neredukovatelný a pokud ne, jejich GCD je nekonstantní faktor . Pak zbývá pouze iterovat algoritmus, aby se úplně rozložil . $ne$ $P$ $l$ $G$ ${\ displaystyle \ {p ^ {k} X ^ {i} | 0 \ leq i <l \} ~ \ bigcup ~ \ {{\ hat {G}} X ^ {i} | 0 \ leq i <nl \ }}$ $k$ $P$ $P$ $P$ $P$

Tato metoda má polynomiální složitost, ale v praxi je delší než metoda exponenciální. Od počátku dvacátých let však van Hoeijovy algoritmy tuto metodu vylepšily a umožnily faktorizovat polynomy, které byly dříve nepřístupné.

Podívejte se také

Související články

Bibliografie

(en) Victor V. Prasolov, Polynomials , Springer ,2010( 1 st ed. 2004) ( číst on-line ) , str. 49-50, 71-73 a 279-288