Metoda dzielonego koła

W matematyce metoda podziału okręgu jest algorytmem numerycznym do numerycznego rozkładu na czynniki wielomianu i ostatecznie do znajdowania jego pierwiastków zespolonych . Został wprowadzony przez Arnolda Schönhage'a w jego artykule z 1982 r. Podstawowe twierdzenie algebry w kategoriach złożoności obliczeniowej (raport techniczny, Mathematisches Institut der Universität Tübingen). Poprawiony algorytm został przedstawiony przez Victora Pana w 1998 roku. Implementację dostarczył Xavier Gourdon w 1996 roku dla Systemy algebry komputerowej Magma i PARI/GP .

Ogólny opis

Podstawową ideą metody rozszczepionego okręgu jest wykorzystanie metod analizy zespolonej , a dokładniej twierdzenia o resztach , do konstruowania czynników wielomianów. Za pomocą tych metod można skonstruować współczynnik danego wielomianu dla dowolnego obszaru płaszczyzny zespolonej z fragmentarycznie gładką granicą. Większość z tych czynników będzie trywialna, czyli stałe wielomiany. Tylko regiony, które zawierają pierwiastki p(x) dają nietrywialne czynniki, które mają dokładnie te pierwiastki p(x) jako własne pierwiastki, zachowując wielość.

W numerycznej realizacji tej metody wykorzystuje się krążki D ( c , r ) (środek c , promień r ) na płaszczyźnie zespolonej jako obszary. Okrąg graniczny dysku dzieli zbiór pierwiastków p ( x ) na dwie części, stąd nazwa metody. Do danego dysku oblicza się przybliżone współczynniki zgodnie z teorią analityczną i udoskonala je metodą Newtona . Aby uniknąć niestabilności liczbowej, należy wymagać, aby wszystkie pierwiastki były dobrze oddzielone od okręgu granicznego dysku. Tak więc, aby uzyskać dobry okrąg łupania, należy go osadzić w wolnym od korzeni pierścieniu A ( c , r , R ) (środek c , promień wewnętrzny r , promień zewnętrzny R ) o dużej względnej szerokości R/r .

Powtarzając ten proces dla znalezionych czynników, ostatecznie dochodzi się do przybliżonego rozkładu wielomianu na czynniki z wymaganą dokładnością. Czynnikami są albo wielomiany liniowe reprezentujące dobrze izolowane zera, albo wielomiany wyższego rzędu reprezentujące skupiska zer.

Szczegóły konstrukcji analitycznej

Tożsamości Newtona to bijektywna relacja między elementarnymi wielomianami symetrycznymi krotki liczb zespolonych i jej sumami potęg. Dlatego możliwe jest obliczenie współczynników wielomianu

(lub jego czynnika) z sum potęg jego zer

,

rozwiązując układ trójkątny, który uzyskuje się przez porównanie potęg u w następującej tożsamości formalnych szeregów potęgowych

Jeśli jest dziedziną z fragmentarycznie gładką granicą jeśli zera p x ) znajdują się na granicy C , to z twierdzenia o resztach resztkowych rachunek różniczkowy

Tożsamość lewej i prawej strony tego równania obowiązuje również dla zer z krotnościami. Korzystając z tożsamości Newtona, można obliczyć z tych sum potęg współczynnik

z p ( x ) odpowiadające zerom p ( x ) wewnątrz G . Przez dzielenie wielomianowe otrzymuje się również drugi czynnik g ( x ) w p ( x ) = f ( x ) g ( x ).

Powszechnie używanymi regionami są okręgi na płaszczyźnie zespolonej. Każde koło daje podbicie do podziału wielomianu p ( x ) na czynniki f ( x ) i g ( x ). Powtarzanie tej procedury na czynnikach przy użyciu różnych okręgów daje coraz drobniejsze rozkłady na czynniki. Ta rekurencja zatrzymuje się po skończonej liczbie właściwych podziałów, przy czym wszystkie czynniki są nietrywialnymi potęgami wielomianów liniowych.

Wyzwanie polega teraz na przekształceniu tej procedury analitycznej w algorytm numeryczny o dobrym czasie działania. Całkowanie jest aproksymowane skończoną sumą metodą całkowania numerycznego, wykorzystującą szybką transformatę Fouriera do oceny wielomianów p ( x ) i p '( x ). Wynikowy wielomian f ( x ) będzie tylko współczynnikiem przybliżonym. Aby upewnić się, że jego zera są bliskie zerom p wewnątrz G i tylko do nich należy wymagać, aby wszystkie zera p były daleko od granicy C obszaru G .

Podstawowe obserwacje numeryczne

(Schönhage 1982) Niech wielomianem stopnia n ma o promieniu 1/2 a pozostałe nk zer na okrąg o promieniu 2 . Przy N = O ( k ) , aproksymacja całek konturowych za pomocą N punktów daje przybliżenie współczynnika f z błędem

,

gdzie norma wielomianu jest sumą modułów jego współczynników.

w swoich współczynnikach, można ustawić zera z tak blisko zer z , wybierając wystarczająco duże N. fa Jednak przybliżenie to można poprawić szybciej, stosując metodę Newtona. Dzielenie p z resztą przybliżenie pozostałego czynnika . Teraz

,

więc odrzucając ostatni składnik drugiego rzędu, trzeba rozwiązać przy użyciu dowolnego wariantu rozszerzonego algorytmu euklidesowego w celu uzyskania przyrostowych przybliżeń i . Jest to powtarzane, aż przyrosty będą równe zeru względem wybranej dokładności.

iteracja Graeffe'a

Kluczowym krokiem w tej metodzie jest znalezienie pierścienia o względnej szerokości 4 w płaszczyźnie zespolonej, który nie zawiera zer p i zawiera w przybliżeniu tyle samo zer p wewnątrz, co na zewnątrz. Każdy pierścień o tej charakterystyce można przekształcić, poprzez translację i skalowanie wielomianu, w pierścień między promieniami 1/2 i 2 wokół początku układu współrzędnych. Ale nie każdy wielomian dopuszcza taki rozszczepiający się pierścień.

Aby zaradzić tej sytuacji, stosuje się iterację Graeffe . Oblicza ciąg wielomianów

pierwiastki to _ _ _ jot na części parzyste i nieparzyste, kolejny wielomian uzyskuje się za pomocą operacji czysto arytmetycznych, ponieważ . Stosunki modułów bezwzględnych pierwiastków rosną o tę samą potęgę a zatem dążą do nieskończoności. Wybierając j , w końcu znajdujemy rozszczepiający się pierścień o względnej szerokości 4 wokół początku układu współrzędnych.

Przybliżona faktoryzacja wynosi } teraz zostać zniesionym z powrotem do pierwotnego wielomianu. W tym celu stosuje się naprzemienne kroki Newtona i przybliżenia Padé . Łatwo to sprawdzić

posiada. Wielomiany po lewej stronie są znane w kroku j , wielomiany po prawej stronie można otrzymać jako przybliżenia Padé odpowiednich stopni dla rozwinięcia szeregu potęgowego ułamka po lewej stronie.

Znalezienie dobrego kręgu

Korzystając z iteracji Graeffe'a i dowolnego znanego oszacowania wartości bezwzględnej największego pierwiastka, można znaleźć oszacowania R tej wartości bezwzględnej dowolnej precyzji. Teraz oblicza się szacunki dla największych i najmniejszych odległości dowolnego pierwiastka z p ( { \ R_ , −2 R , 2 Ri , −2 Ri i wybiera ten, który ma największy stosunek między nimi. Dzięki tej konstrukcji można zagwarantować, że dla co najmniej jednego centrum. Dla takiego środka musi istnieć pierścień bez korzeni o względnej szerokości } Po odpowiedni pierścień iterowanego wielomianu ma względną szerokość większą niż 11 wstępne rozszczepienie opisane powyżej (patrz Schönhage (1982)). Po Graeffe iteracje, odpowiedni pierścień ma szerokość względna większa niż , pozwalając na znacznie uproszczony początkowy podział (patrz Malajovich/Zubelli (1997))

Aby zlokalizować najlepszy pierścień bez korzeni, wykorzystuje się konsekwencję twierdzenia Rouchégo : Dla k = 1, ..., n - 1 równanie wielomianowe

u > 0 ma, zgodnie z regułą znaków Kartezjusza, zero lub dwa dodatnie pierwiastki . W tym drugim przypadku wewnątrz ) dysku jest dokładnie k i jest pierścieniem wolnym od korzeni (otwartym).