Wielomian bezkwadratowy - Square-free polynomial

W matematyce , A kwadratowy wolne wielomianu jest wielomianem określona przez pola (lub, bardziej ogólnie, z integralną dziedzinie ), które nie mają postaci dzielnika dowolnego kwadratu o niestałej wielomianu . Jednowymiarowej wielomian kwadratu wolne wtedy i tylko wtedy, gdy nie ma wiele pierwiastek w algebraicznie zamkniętego pola zawierające odpowiednie współczynniki. To uzasadnia, że ​​w zastosowaniach w fizyce i inżynierii wielomian bez kwadratu jest powszechnie nazywany wielomianem bez powtarzających się pierwiastków .

W przypadku jednowymiarowych wielomianów The zasada produktu sugeruje, że jeśli p ² dzieli C , a następnie p dzieli formalne pochodną f '  o f . Odwrotność jest również prawdziwa w charakterystyce zera i dla wielomianów nad ciałem skończonym (lub ogólniej nad ciałem idealnym ). Oznacza to, że w tych przypadkach wielomian jest bezkwadratowy wtedy i tylko wtedy, gdy 1 jest największym wspólnym dzielnikiem wielomianu i jego pochodnej.

Kwadratowy wolne rozkładu lub kwadratowy wolne faktoryzacji wielomianu jest na czynniki w kompetencji kwadratowy wolnych wielomianów

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

gdzie te z a _k , które są nie-stałe są parami względnie pierwsze kwadratowych wolne wielomiany (tutaj dwa wielomiany są uważane względnie pierwsze jest ich największy wspólny dzielnik stałe, innymi słowy, że jest coprimality na polu frakcji współczynników to jest brane pod uwagę). Każdy niezerowy wielomian to faktoryzacja bezkwadratowa, która jest unikalna aż do mnożenia i dzielenia czynników przez niezerowe stałe. Kwadratowy wolne faktoryzacji jest znacznie łatwiejsze do obliczenia niż całkowita faktoryzacji w nieredukowalnych czynników, i jest zatem często korzystne, gdy kompletny faktoryzacji nie jest naprawdę potrzebny, a na ułamki proste i symbolicznych integracji z racjonalnych frakcji . Faktoryzacja bezkwadratowa jest pierwszym krokiem algorytmów faktoryzacji wielomianowej , które są implementowane w systemach algebry komputerowej . Dlatego algorytm bezkwadratowej faktoryzacji jest podstawowym elementem algebry komputerowej .

Nad ciałem o charakterystyce 0 iloraz przez jego NWD z jego pochodną jest iloczynem powyższego rozkładu bezkwadratowego. Po idealnym polu o niezerowej charakterystyce p iloraz ten jest iloczynem takiego, że i nie jest wielokrotnością p . Dalsze obliczenia GCD i dokładne dzielenie pozwalają na obliczenie faktoryzacji bez kwadratów (patrz faktoryzacja bez kwadratów po skończonym polu ). W charakterystyce zero znany jest lepszy algorytm, algorytm Yuna, który opisano poniżej. Jego złożoność obliczeniowa jest co najwyżej dwa razy większa od złożoności obliczeń GCD wielomianu wejściowego i jego pochodnej. Dokładniej, jeśli jest czas potrzebny do obliczenia NWD dwóch wielomianów stopnia i ilorazu tych wielomianów przez NWD, to jest to górna granica czasu potrzebnego do obliczenia rozkładu bezkwadratowego. ${\displaystyle f}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle T_{n}}$${\ Displaystyle n}$${\ Displaystyle 2T_ {n}}$

Znane są również algorytmy obliczania bezkwadratowego rozkładu wielomianów wielowymiarowych , które zasadniczo opierają się na uznaniu wielomianu wielowymiarowego za wielomian jednowymiarowy ze współczynnikami wielomianu i zastosowaniu rekurencyjnego algorytmu jednowymiarowego.

Algorytm Yuna

Ten rozdział opisuje algorytm Yuna do bezkwadratowego rozkładu wielomianów jednowymiarowych po ciele o charakterystyce 0 . Polega na kolejnych obliczeniach GCD i dokładnych dzieleniach.

Wejście jest więc niezerowym wielomianem f , a pierwszy krok algorytmu polega na obliczeniu NWD a ₀ z f i jego formalnej pochodnej f' .

Gdyby

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

jest pożądana faktoryzacja, mamy więc

${\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}}$

oraz

${\ Displaystyle f '/a_ {0}= \ suma _ {i = 1} ^ {k} ia_ {i} 'a_ {1} \ cdots a_ {i-1} a_ {i + 1} \ cdots a_ { k}.}$

Jeśli ustawimy , i otrzymamy to ${\displaystyle b_{1}=f/a_{0}}$${\displaystyle c_{1}=f'/a_{0}}$${\displaystyle d_{1}=c_{1}-b_{1}'}$

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

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

oraz

${\ Displaystyle c_ {2} = d_ {1} / a_ {1} = \ suma _ {i = 2} ^ {k} (i-1) a_ {i} 'a_ {2} \ cdots a_ {i- 1}a_{i+1}\cdots a_{k}.}$

Powtarzaj ten proces, aż znajdziemy wszystkie${\displaystyle b_{k+1}=1}$${\displaystyle a_{i}.}$

Jest to sformalizowane w algorytmie w następujący sposób:

${\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;}$
powtarzaj aż do wyjścia
${\ 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}';}$
${\displaystyle b=1;}$
${\displaystyle a_{1},\ldots,a_{i-1}.}$

Stopień i jest o jeden mniejszy niż stopień As jest iloczynem sumy stopni jest stopniem Ponieważ złożoność obliczeń i podziałów GCD rośnie bardziej niż liniowo wraz ze stopniem, wynika z tego, że całkowity bieg czas wykonania pętli „powtórzenia” jest krótszy niż czas działania pierwszego wiersza algorytmu, a całkowity czas działania algorytmu Yun jest ograniczony od góry przez dwukrotność czasu potrzebnego do obliczenia GCD z i oraz ilorazu i przez ich GCD. ${\displaystyle c_{i}}$${\displaystyle d_{i}}$${\displaystyle b_{i}.}$${\displaystyle f}$${\displaystyle b_{i},}$${\displaystyle b_{i}}$${\displaystyle fa.}$${\displaystyle f}$${\displaystyle f'}$${\displaystyle f}$${\displaystyle f'}$

Pierwiastek kwadratowy

Ogólnie rzecz biorąc, wielomian nie ma pierwiastka kwadratowego . Dokładniej, większości wielomianów nie można zapisać jako kwadratu innego wielomianu.

Wielomian ma pierwiastek kwadratowy wtedy i tylko wtedy, gdy wszystkie wykładniki rozkładu bezkwadratowego są parzyste. W tym przypadku pierwiastek kwadratowy uzyskuje się dzieląc przez 2 te wykładniki.

Zatem problem decydowania, czy wielomian ma pierwiastek kwadratowy, i obliczania go, jeśli istnieje, jest szczególnym przypadkiem faktoryzacji bezkwadratowej.

Uwagi

Bibliografia