Polynom bez čtverců - Square-free polynomial - Wikipedia

v matematika, a polynom bez čtverců je polynomiální definované nad a pole (nebo obecněji a jedinečná faktorizační doména ), který nemá jako faktor žádný čtverecjednotka faktor. V důležitém případě univariantních polynomů nad polem k, tohle znamená tamto ${ displaystyle f in k [X]}$ je bez čtverce, právě když ${ displaystyle b ^ {2} nmid f}$ pro každý polynom ${ displaystyle b v k [X]}$ kladného stupně.^[1] V aplikacích ve fyzice a strojírenství se polynom bez čtverců běžně nazývá a polynom bez opakovaných kořenů. Takové polynomy se nazývají oddělitelný, ale přes oddělitelné dokonalé pole je stejné jako bez čtverce.

A rozklad bez čtverců nebo faktorizace bez čtverců polynomu je faktorizace na mocniny faktorů bez čtverce

${ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} cdots a_ {n} ^ {n} = prod _ {k = 1} ^ {n} a_ { k} ^ {k} ,}$

kde ti z A_k které se nerovnají 1 jsou dvojice coprime polynomy bez čtverců.^[1] Každý nenulový polynom s koeficienty v a pole připouští faktoraci bez čtverců, která je jedinečná až do násobení faktorů nenulovými konstantami. Faktorizace bez čtverců se počítá mnohem snadněji než celá faktorizace do neredukovatelné faktorů, a je proto často upřednostňována, když není nutná úplná faktorizace, jako u částečný zlomek rozklad a symbolická integrace z racionální zlomky. Faktorizace bez čtverců je prvním krokem polynomiální faktorizace algoritmy, které jsou implementovány v systémy počítačové algebry. Proto je algoritmus faktorizace bez čtverců základní počítačová algebra.

V případě univariate polynomy nad polem, jakýkoli vícenásobný faktor polynomu zavádí netriviální společný faktor F a jeho formální derivát F ′, Tedy dostatečná podmínka pro F být bez náměstí je to, že největší společný dělitel z F a F ′ Je 1. Tato podmínka je také nezbytná pro pole charakteristiky 0 nebo, obecněji, pro a perfektní pole, protože nad takovým polem je každý neredukovatelný polynom oddělitelný, a tudíž coprime s jeho derivátem.

Nad polem charakteristiky 0 je podíl ${ displaystyle f}$ jeho GCD s jeho derivátem je produktem ${ displaystyle a_ {i}}$ ve výše uvedeném rozkladu bez čtverců. Přes perfektní pole nenulové charakteristiky str, tento podíl je produktem ${ displaystyle a_ {i}}$ takhle i není násobkem str. Další výpočty GCD a přesné dělení umožňují výpočet bezfaktorové faktorizace (viz kvadratická faktorizace nad konečným polem ). V charakteristické nule je znám lepší algoritmus, Yunův algoritmus, který je popsán níže.^[1] Své výpočetní složitost je nanejvýš dvakrát větší než výpočet GCD vstupního polynomu a jeho derivace. Přesněji řečeno, pokud ${ displaystyle T_ {n}}$ je čas potřebný k výpočtu GCD dvou polynomů stupně ${ displaystyle n}$ a podíl těchto polynomů podle GCD ${ displaystyle 2T_ {n}}$ je horní mez pro čas potřebný k výpočtu čtvercového volného rozkladu.

Existují také známé algoritmy pro výpočet rozkladu vícerozměrných polynomů bez čtverců.^[2]

Yunův algoritmus

Tato část popisuje Yunův algoritmus pro rozklad čtverců bezrozměrných polynomů bez pole na pole charakteristika 0.^[1] Vychází z posloupnosti GCD výpočty a přesná rozdělení.

Vstup je tedy nenulový polynom Fa první krok algoritmu spočívá ve výpočtu GCD A₀ z F a jeho formální derivát F'.

Li

${ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} cdots a_ {k} ^ {k}}$

je požadovaná faktorizace, máme tedy

${ displaystyle a_ {0} = a_ {2} ^ {1} a_ {3} ^ {2} cdots a_ {k} ^ {k-1},}$

${ displaystyle f / a_ {0} = a_ {1} a_ {2} a_ {3} cdots a_ {k}}$

a

${ displaystyle f '/ a_ {0} = součet _ {i = 1} ^ {k} ia_ {i}' a_ {1} cdots a_ {i-1} a_ {i + 1} cdots a_ { k}.}$

Pokud jsme nastavili ${ displaystyle b_ {1} = f / a_ {0}}$, ${ displaystyle c_ {1} = f '/ a_ {0}}$ a ${ displaystyle d_ {1} = c_ {1} -b_ {1} '}$, máme to

${ displaystyle gcd (b_ {1}, d_ {1}) = a_ {1},}$

${ displaystyle b_ {2} = b_ {1} / a_ {1} = a_ {2} a_ {3} cdots a_ {n},}$

a

${ displaystyle c_ {2} = d_ {1} / a_ {1} = součet _ {i = 2} ^ {k} (i-1) a_ {i} 'a_ {2} cdots a_ {i- 1} a_ {i + 1} cdots a_ {k}.}$

Iterace tohoto procesu do ${ displaystyle b_ {k + 1} = 1}$ najdeme všechny ${ displaystyle a_ {i}.}$

Toto je formováno do algoritmu takto:

${ displaystyle a_ {0}: = gcd (f, f '); quad b_ {1}: = f / a_ {0}; quad c_ {1}: = f' / a_ {0}; quad d_ {1}: = c_ {1} -b_ {1} '; quad i: = 1;}$
opakovat
${ displaystyle a_ {i}: = gcd (b_ {i}, d_ {i}); quad b_ {i + 1}: = b_ {i} / a_ {i}; quad c_ {i + 1 }: = d_ {i} / a_ {i}; quad i: = i + 1; quad d_ {i}: = c_ {i} -b_ {i} ';}$
dokud ${ displaystyle b = 1;}$
Výstup ${ displaystyle a_ {1}, ldots, a_ {i-1}.}$

Stupeň ${ displaystyle c_ {i}}$ a ${ displaystyle d_ {i}}$ je o jeden menší než stupeň ${ displaystyle b_ {i}.}$ Tak jako ${ displaystyle f}$ je produktem ${ displaystyle b_ {i},}$ součet stupňů ${ displaystyle b_ {i}}$ je stupeň ${ displaystyle f.}$ Protože složitost výpočtů a dělení GCD roste s mírou více než lineárně, vyplývá z toho, že celková doba běhu smyčky „opakování“ je menší než doba běhu prvního řádku algoritmu a že celková doba běhu Yunův algoritmus je horně omezen dvojnásobkem času potřebného k výpočtu GCD ${ displaystyle f}$ a ${ displaystyle f '}$ a kvocient ${ displaystyle f}$ a ${ displaystyle f '}$ jejich GCD.

Odmocnina

Polynom obecně nemá číslo odmocnina. Přesněji řečeno, většinu polynomů nelze zapsat jako druhou mocninu jiného polynomu.

Polynom má druhou odmocninu právě tehdy, jsou-li všechny exponenty rozkladu bez odmocniny sudé. V tomto případě se druhá odmocnina získá dělením 2 těmito exponenty.

Problém rozhodování o tom, zda polynom má druhou odmocninu, a výpočtu, pokud existuje, je tedy zvláštním případem bezmocné faktorizace.

Reference