Polynomiální rozklad - Polynomial decomposition

V matematice, a polynomický rozklad vyjadřuje a polynomiální F jako funkční složení ${ displaystyle g circ h}$ polynomů G a h, kde G a h mít stupeň větší než 1; je to algebraické funkční rozklad. Algoritmy jsou známé tím, že se rozkládají jednorozměrné polynomy v polynomiální čas.

Polynomy, které jsou tímto způsobem rozložitelné, jsou složené polynomy; ti, kteří nejsou, se nazývají nerozložitelné polynomy někdy primární polynomy.^[1] (nezaměňovat s neredukovatelné polynomy, což nemůže být zapracován do produktů polynomů ).

Zbytek tohoto článku pojednává pouze o jednorozměrných polynomech; Algoritmy také existují pro vícerozměrné polynomy libovolného stupně.^[2]

Příklady

V nejjednodušším případě je jeden z polynomů a monomiální. Například,

${ displaystyle f = x ^ {6} -3x ^ {3} +1}$

rozkládá se na

${ displaystyle g = x ^ {2} -3x + 1 { text {and}} h = x ^ {3}}$

od té doby

${ Displaystyle f (x) = (g circ h) (x) = g (h (x)) = g (x ^ {3}) = (x ^ {3}) ^ {2} -3 (x ^ {3}) + 1,}$

za použití symbol operátora prstenu ∘ naznačit složení funkce.

Méně triviálně,

${ displaystyle { begin {aligned} & x ^ {6} -6x ^ {5} + 21x ^ {4} -44x ^ {3} + 68x ^ {2} -64x + 41 = {} & (x ^ {3} + 9x ^ {2} + 32x + 41) circ (x ^ {2} -2x). End {zarovnáno}}}$

Jedinečnost

Polynom může mít odlišné dekompozice na nerozložitelné polynomy, kde ${ displaystyle f = g_ {1} circ g_ {2} circ cdots circ g_ {m} = h_ {1} circ h_ {2} circ cdots circ h_ {n}}$ kde ${ displaystyle g_ {i} neq h_ {i}}$ pro některé ${ displaystyle i}$. Omezení v definici na polynomy stupně většího než jeden vylučuje nekonečně mnoho možných rozkladů u lineárních polynomů.

Joseph Ritt dokázal to ${ displaystyle m = n}$a stupně komponent jsou stejné, ale možná v jiném pořadí; tohle je Rittova věta o polynomickém rozkladu.^[1][3] Například, ${ displaystyle x ^ {2} circ x ^ {3} = x ^ {3} circ x ^ {2}}$.

Aplikace

Polynomický rozklad může umožnit efektivnější vyhodnocení polynomu. Například,

${ displaystyle { begin {aligned} & x ^ {8} + 4x ^ {7} + 10x ^ {6} + 16x ^ {5} + 19x ^ {4} + 16x ^ {3} + 10x ^ {2} + 4x-1 = {} & (x ^ {2} -2) circ (x ^ {2}) circ (x ^ {2} + x + 1) end {zarovnáno}}}$

lze vypočítat pouze pomocí 3 násobení pomocí rozkladu, zatímco Hornerova metoda bude vyžadovat 7.

Polynomiální rozklad umožňuje výpočet symbolických kořenů pomocí radikály, dokonce i pro některé neredukovatelné polynomy. Tato technika se používá v mnoha systémy počítačové algebry.^[4] Například pomocí rozkladu

${ displaystyle { begin {aligned} & x ^ {6} -6x ^ {5} + 15x ^ {4} -20x ^ {3} + 15x ^ {2} -6x-1 = {} & (x ^ {3} -2) circ (x ^ {2} -2x + 1), end {zarovnáno}}}$

kořeny tohoto neredukovatelného polynomu lze vypočítat jako

${ displaystyle 1 pm 2 ^ {1/6}, 1 pm { frac { sqrt {-1 pm { sqrt {3}} i}} {2 ^ {1/3}}}}$.^[5]

I v případě kvartické polynomy, kde existuje explicitní vzorec pro kořeny, řešení pomocí rozkladu často dává jednodušší formu. Například rozklad

${ displaystyle { begin {aligned} & x ^ {4} -8x ^ {3} + 18x ^ {2} -8x + 2 = {} & (x ^ {2} +1) circ (x ^ {2} -4x + 1) end {zarovnáno}}}$

dává kořeny

${ displaystyle 2 pm { sqrt {3 pm i}}}$^[5]

ale přímá aplikace kvartický vzorec poskytuje rovnocenné výsledky, ale ve formě, která je obtížná zjednodušit a těžko pochopitelné:

${ displaystyle 2 - { frac { sqrt {{9 vlevo ({ frac {8 { sqrt {10}} i} {3 ^ {3/2}}} + 72 vpravo) ^ {2 / 3} +36 left ({ frac {8 { sqrt {10}} i} {3 ^ {3/2}}} + 72 right) ^ {1/3} +156} over { left ({ frac {8 { sqrt {10}} i} {3 ^ {3/2}}} + 72 right) ^ {1/3}}}} {6}} - {{ sqrt {- left ({ frac {8 { sqrt {10}} i} {3 ^ {3/2}}} + 72 right) ^ {1/3} - {{52} přes {3 left ( { frac {8 { sqrt {10}} i} {3 ^ {3/2}}} + 72 vpravo) ^ {1/3}}} + 8}} nad 2}}$.

Algoritmy

První algoritmus polynomiálního rozkladu byl publikován v roce 1985,^[6] ačkoli to bylo objeveno v roce 1976^[7] a implementováno v Macsyma počítačový algebraický systém.^[8] Tento algoritmus trvá exponenciální čas v nejhorším případě, ale funguje nezávisle na charakteristický podkladového pole.

Novější algoritmy běží v polynomiálním čase, ale s omezeními charakteristiky.^[9]

Nejnovější algoritmus počítá rozklad v polynomiálním čase a bez omezení charakteristiky.^[10]

Poznámky

Reference

• Joel S. Cohen, "Polynomiální rozklad", kapitola 5 z Počítačová algebra a symbolický výpočet, 2003, ISBN  1-56881-159-4