Polinomok faktorizációja

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

A matematikában a polinomok faktorizációja arra a módszerre utal amely során egy polinomot amelynek együtthatói egy adott testből származnak vagy egész számok, felbontunk tovább nem bontható úgynevezett irreducibilis polinomok szorzatára, amelyek együtthatói ugyanabból az előbb említett halmazból kerülnek ki.

A polinomok faktorizációjának története Hermann Schuberttel kezdődött aki 1793-ban először írt egy polinom faktorizációs algoritmust. Később Leopold Kronecker újra felfedezte Schubert algoritmusát 1882-ben és kiterjesztette többváltozós polinomokra. Ugyanakkor a legfontosabb ismeretek a témában nem túl régiek, mindössze 1965 után keletkeztek a számítógépes algebrai rendszerek megjelenésével. Egy kutatásában Erich Kaltofen azt írta 1982-ben, hogy:

Amikor a régen ismert véges algoritmusokat először alkalmazták számítógépekkel, kiderült, hogy ezen algoritmusok meglehetősen használhatatlanok. Az a tény, hogy manapság, majdnem minden egy- vagy kétváltozós polinom amelynek fokszáma nem nagyobb mint 100 és az együtthatói értelmes méretűek (maximum 100 biten ábrázolhatóak) faktorizálható modern algoritmusok segítségével kevesebb, mint néhány perc alatt számítógép segítségével rámutat arra, hogy milyen erővel és sikerességgel foglalkoztak ezzel a problémával [a matematikusok és számítástudósok] az elmúlt 50 évben.

Manapság[1] egy akár 1000 fokú egyváltozós polinomnak a faktorizálása, amelynek együtthatói akár több ezer számjegyűek is lehetnek, néhány pillanat alatt elvégezhető számítógéppel.

A probléma részletesen[szerkesztés]

Az egész számok feletti vagy egy tetszőleges test fölötti polinomgyűrűk elemei egyedi faktorizációval rendelkeznek. Ez azt jelenti, hogy a gyűrű minden eleme felírható egy konstans és irreducibilis polinomok szorzataként. Továbbá ez a felbontás egyedi, eltekintve a szorzás sorrendjétől és invertálható elemek szorzatától. (Ezek azok az elemek amelyeknek létezik multiplikatív inverze a polinomgyűrű alapját adó struktúrában, tehát például az egészeknél ezek az 1 és a -1; míg a valós számok testénél minden nemnulla elem invertálható elem. Ha akkor -ra is irreducibilis. Bővebben lásd: irreducibilis polinom.)

A faktorizáció az alap struktúrától függ. Például az algebra alaptételéből következően minden egész együtthatós polinom felbontható lineáris polinomok szorzatára ahol az együtthatók komplex számok. Egy valós együtthatós polinom esetén az irreducibilis elemek fokszáma maximum 2, míg a racionális számok felett az irreducibilis polinomok fokszáma bármilyen nagy lehet.

A polinomfaktorizáció csak olyan testek fölött értelmezhető amelyekkel számolni tudunk, vagyis amelyek elemei számítógéppel ábrázolhatóak és az aritmetikai műveletek elvégezhetőek számítógépen egy algoritmussal Fröhlich és Shepherson olyan testekre adtak példákat, amelyeken nem létezhet faktorizációs algoritmus.

Azon testekre amelyek fölötti polinomgyűrűknek létezik faktorizációs algoritmusuk, példa a prím testek (például a racionális számok teste ilyen) és ezek véges generált kiterjesztési. A mai modern algoritmusok általában a

  • Négyzetmentes felbontás vagy a
  • Véges testek fölötti faktorizációk

továbbfejlesztései, és olyan egyszerűsítési módszereket használnak, mint például:

  • Többváltozós esetek redukálása egyváltozós esetre.
  • A tisztán transzcendens testkiterjesztések esetén a többváltozós módszert alkalmazzák az eredeti test fölött. (lásd lent)
  • A testkiterjesztésből származó együtthatós polinom faktorizációja az eredeti test fölötti polinomgyűrűben (lásd lent)
  • A racionális együtthatós polinom faktorizációját visszavezetik egész együtthatós polinomok faktorizációjára. (lásd lent)
  • Az egész együtthatós polinomok faktorizációját visszavezetik prímtestek feletti faktorizációra. (lásd lent)

Primitív rész–az együtthatók egyszerűsítése[szerkesztés]

Ebben a részben azt mutatjuk meg, hogy a Q racionális számok feletti polinomok felbontása és a Z vagyis az egész számok fölötti polinomok felbontása gyakorlatilag ugyanaz a probléma.

Egy pZ[X] polinom együtthatóinak a legnagyobb közös osztóját jelöljük cont(p)-vel. A p polinom primitív része primpart(p)=p/cont(p), amely egy primitív polinom és az együtthatói egészek. Ekkor a p felbontható a cont(p) és a primitív rész szorzatára. Ez a faktorizáció egyedi, eltekintve cont(p) előjelétől. Általában a cont(p) előjelét úgy választják meg, hogy a primitív rész főegyütthatója pozitív legyen.

Például:

egy faktorizáció a polinom primitív és a konstans részének szorzatára..

Minden q racionális együtthatós polinom felírható

alakban, ahol pZ[X] és cZ. A c konstanst válasszuk az eredeti polinom együtthatóinak a nevezőinek szorzatának. Ekkor cont(q)-t a következőképpen definiáljuk:

és q primitív része p. Hasonlóan az egész együtthatós polinomokhoz itt is felbonthatjuk a q polinomot egy racionális szám és egy primitív, egész együtthatós polinom szorzataként. Ez a faktorizáció szintén egyértelmű a racionális szám előjelétől eltekintve.

Például a

faktorizáció felbontja a polinomot egy konstans és a primitív részének szorzatára.

Gauss volt az első aki bebizonyította, hogy két primitív polinom szorzata szintén primitív. (lásd Gauss-lemma). Ez azt jelenti, hogy egy primitív polinom irreducibilis a racionális számok felett akkor és csak akkor, ha a primitív része irreducibilis az egész számok felett. Ez pedig azt jelenti, hogy a racionális együtthatós polinomok faktorizációja visszavezethető egész együtthatós polinomok faktorizációjára (konkrétan a polinom primitív részének faktorizációjára). Viszont az egész együtthatós polinomok faktorizációja megegyezik a primitív részük faktorizációjával és a kiemelt rész szorzatával.

Négyzetmentes faktorizáció[szerkesztés]

Ha egy polinom két vagy több faktora megegyezik (vagyis ha a polinomnak többszörös gyökei vannak), akkor a polinom felbontásában az adott faktor a négyzeten vagy általánosan annyiadik hatványon jelenik meg, ahányszoros gyöke az eredeti polinomnak a faktor gyöke (vagyis ha az adott faktor x−c, ha c az eredeti polinomnak 2, 3, 4, ... n szeres gyöke, akkor ennek a polinomnak a felbontásában az x−c a 2., 3., 4., ... n. hatványán szerepel). Ilyen eseteben (vagyis ha egy faktor a felbontásban 2 vagy magasabb hatványon szerepel), akkor az adott faktor osztja nem csak az adott polinomot, hanem annak deriváltját (többváltozós polinom esetén, bármelyik változó szerinti deriváltat) is. Racionális együtthatós (vagy általánosan 0 karakterisztikus testből származó együtthatós) egyváltozós polinomok esetén Yum algoritmusa a fenti tulajdonságot felhasználva képes hatékonyan előállítani egy polinomnak olyan faktorizációját, amelynek minden faktora négyzetmentes. Az eredeti polinom faktorizációját megkaphatjuk a már négyzetmentes részek faktorizációjával. Így látható, hogy a polinomok négyzetmentes faktorizációja a legtöbb faktorizáció első lépése.

Yum algoritmusa kiterjeszthető a többváltozós polinomok esetére úgy, hogy a polinomot egyváltozós polinomnak tekintjük.

Abban az esetben ha a polinom együtthatói egy véges testből származnak, Yum algoritmusa csak akkor működik ha polinom fokszáma kisebb mint a test karakterisztikája, mivel különben a nemnulla polinomok deriváltja zérus lehet. Egy másik algoritmus a négyzetmentes faktorizáció előállítására lehet a legnagyobb közös osztó egymásutáni alkalmazása, először a polinomra és annak deriváltjára; lásd: Véges test fölötti polinomfaktorizáció.

Hagyományos módszerek[szerkesztés]

Az ebben a részben bemutatott "tankönyvi" módszerek hasznosak lehetnek, ha kézzel szeretnénk faktorizálni, ugyanakkor ezek az algoritmusok nem használatosak számítógépes rendszerekben, mivel prímfaktorizációra épülnek, ami a jelen pillanatban nagyobb komplexitású feladat (tehát "nehezebb"), mint a polinomok faktorizációja.

A lineáris elemek kiszámítása[szerkesztés]

Minden lineáris faktor megtalálható a polinomok racionális gyökeire vonatkozó tétel segítségével.[megj 1] Ha a faktorizálni kívánt polinom , alakú, akkor minden lineáris faktora , alakú, ahol egész szám és osztója -nek, pedig egész és osztója -nak. A megtalált lineáris faktorok ezután kiemelhetőek a polinomból polinomosztás segítségével. Ha az eredeti polinom olyan elemek szorzata amelyek közül legalább kettő legalább másodfokú, akkor ez a módszer csak részleges faktorizációt szolgáltat, különben a faktorizáció teljesen végigvihető.

Kronecker módszere[szerkesztés]

Mivel az egész együtthatós polinomok faktorainak is egész együtthatós polinomoknak kell lenniük, és egy egész együtthatós polinom helyettesítési értéke egész pontokban, egész (mivel egész számok véges szorzata, véges összege egész, vagyis az az egész számok zártak szorzásra és összeadásra), így polinom értékeinek prímfaktorizációját felhasználva, véges számú elemre redukálhatjuk a lehetséges (polinom)faktorokat.

Például, vegyük az

.

polinomot. Ha ez a polinom felbontható az egész számok felett, akkor legalább az egyik faktorának első vagy másodfokúnak kell lennie (lásd az algebra alaptételének egy megfelelő változatát). Három értékre van szükségünk ahol, hogy egy legfeljebb másodfokú polinomot egyértelműen meg tudjunk határozni. Legyenek ezek a pontok az , és az. Ha a 3 közül bármelyik érték 0 akkor máris találtunk egy gyököt és így a faktorizációs tétel alapján egy faktort is. Ha viszont egyik sem 0 akkor mindegyiknek csak véges mennyiségű osztója van. Például 2 egész számok segítségével csak a következőképpen írható:

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

Vagyis ha másodfokú faktor létezik akkor annak

1, 2, −1, vagy −2

értékűnek kell lennie az pontban, és az pontban. Mivel 6-ot 8-féleképpen lehet felbontani így összesen

4×4×8 = 128

kombinációs lehetőség van, amelynek fele csak előjelben különbözik így ezeket elhagyva csak 64 másodfokú polinom marad, amit le kell tesztelni. Csak ezek a lehetséges faktorai -nek. Ezek tesztelése szerint

amit úgy kaptunk, hogy , és , osztja -et a megfelelő pontokban.

Az polinomot -vel osztva megkapjuk a másik faktort: , így . Mivel kiderül. hogy mind és irreducibilis így irreducibilis faktorizációja:

(Van der Waerden, 5.4-es és 5.6-os szakasz)

Modern módszerek[szerkesztés]

Faktorizáció véges testek fölött[szerkesztés]

Egyváltozós polinomok faktorizációja az egész számok felett[szerkesztés]


A szócikk egy része még lefordítandó. Segíts te is a fordításban!

Algebrai kiterjesztések feletti faktorizáció (Trager-módszer)[szerkesztés]


A szócikk egy része még lefordítandó. Segíts te is a fordításban!

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Factorization of polynomials című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

Jegyzetek[szerkesztés]

  1. Szendrei János "Algebra és számelmélet" könyve ezt a tételt Rolle-tétel néven tartalmazza, ugyanakkor ez nem azonos az analízisben használt Rolle-tétellel. Angolul lásd: Rational root theorem

Források[szerkesztés]

  1. An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).

További információk[szerkesztés]