Dela cirkelmetoden

Inom matematiken är metoden med delning av cirkeln en numerisk algoritm för numerisk faktorisering av ett polynom och, i slutändan, för att hitta dess komplexa rötter . Det introducerades av Arnold Schönhage i hans 1982 uppsats The fundamental theorem of algebra in termer av beräkningskomplexitet (Teknisk rapport, Mathematisches Institut der Universität Tübingen). En reviderad algoritm presenterades av Victor Pan 1998. En implementering tillhandahölls av Xavier Gourdon 1996 för datoralgebrasystemen Magma och PARI/GP .

Allmän beskrivning

Den grundläggande idén med klyvningscirkelmetoden är att använda metoder för komplex analys , närmare bestämt restsatsen , för att konstruera faktorer av polynom. Med dessa metoder är det möjligt att konstruera en faktor för ett givet polynom $p(x)=x^{n}+p_{ n-1}x^{n-1}+\cdots +p_{0}$ för vilken region som helst av det komplexa planet med en bitvis jämn gräns. De flesta av dessa faktorer kommer att vara triviala, det vill säga konstanta polynom. Endast regioner som innehåller rötter av p(x) resulterar i icke-triviala faktorer som har exakt de rötter av p(x) som sina egna rötter, vilket bevarar mångfald.

I den numeriska realiseringen av denna metod använder man skivor D ( c , r ) (centrum c , radie r ) i det komplexa planet som regioner. Gränscirkeln för en skiva delar uppsättningen av rötter för p ( x ) i två delar, därav namnet på metoden. Till en given skiva beräknar man ungefärliga faktorer enligt den analytiska teorin och förfinar dem med hjälp av Newtons metod . För att undvika numerisk instabilitet måste man kräva att alla rötter är väl åtskilda från skivans gränscirkel. Så för att få en bra klyvningscirkel bör den vara inbäddad i en rotfri ring A ( c , r , R ) (centrum c , inre radie r , yttre radie R ) med en stor relativ bredd R/r .

Genom att upprepa denna process för de hittade faktorerna kommer man slutligen fram till en approximativ faktorisering av polynomet med en erforderlig precision. Faktorerna är antingen linjära polynom som representerar väl isolerade nollor eller högre ordningens polynom som representerar kluster av nollor.

Detaljer om den analytiska konstruktionen

Newtons identiteter är en bijektiv relation mellan de elementära symmetriska polynomen i en tupel av komplexa tal och dess summor av potenser. Därför är det möjligt att beräkna koefficienterna för ett polynom

$p(x)=x^{n}+p_{ n-1}x^{n-1}+\cdots +p_{0}=(x-z_{1})\cdots (x-z_{n})$

(eller av en faktor av den) från summorna av potenser av dess nollor

$t_{m}=z_{1}^{m}+\cdots +z_{n}^{m}$ , $m=0,1,\dots ,n$

genom att lösa det triangulära systemet som erhålls genom att jämföra potenserna av u i följande identitet av formella potensserier

$a_{n-1}+2\,a_{n-2 }\,u+\cdots +(n-1)\,a_{1}\,u^{n-2}+n\,a_{0}\,u^{n-1}$

$=-(1+a_{n-1}\,u+\cdots +a_{1}\,u^{n-1}+a_{0}\,u^{n})\cdot (t_ {1}+t_{2}\,u+t_{3}\,u^{2}+\dots +t_{n}\,u^{n-1}+\cdots ).$

Om $G\subset \mathbb {C}$ är en domän med bitvis jämn gräns C och om nollorna för p ( x ) är parvis distinkta och inte på gränsen C , då från restsatsen för residual kalkyl man får

${\frac {1}{2\pi \,i}}\oint _{C}{\frac {p'(z)}{p(z)}}z^{m}\,dz= \sum _{z\in G:\,p(z)=0}{\frac {p'(z)z^{m}}{p'(z)}}=\summa _{z\in G :\,p(z)=0}z^{m}.$

Identiteten för vänster till höger sida av denna ekvation gäller även för nollor med multipliciteter. Genom att använda Newton-identiteterna kan man beräkna faktorn från dessa summor av potenser

$f(x):=\prod _{z\in G:\,p(z)=0}(xz )$

av p ( x ) som motsvarar nollorna i p ( x ) inuti G . Genom polynomdivision får man även den andra faktorn g ( x ) i p ( x ) = f ( x ) g ( x ).

De vanligaste områdena är cirklar i det komplexa planet. Varje cirkel ger upphov till en uppdelning av polynomet p ( x ) i faktorerna f ( x ) och g ( x ). Att upprepa denna procedur på faktorerna med hjälp av olika cirklar ger finare och finare faktoriseringar. Denna rekursion upphör efter ett ändligt antal korrekta delningar, där alla faktorer är icke-triviala potenser av linjära polynom.

Utmaningen består nu i att omvandla denna analytiska procedur till en numerisk algoritm med bra körtid. Integrationen approximeras av en ändlig summa av en numerisk integrationsmetod, med användning av den snabba Fouriertransformen för utvärderingen av polynomen p ( x ) och p '( x ). Polynomet f ( x ) som blir resultatet kommer bara att vara en ungefärlig faktor. För att säkerställa att dess nollor är nära nollorna för p inuti G och endast till dem, måste man kräva att alla nollor för p är långt borta från gränsen C för regionen G .

Grundläggande numerisk observation

(Schönhage 1982) Låt $p\in \mathbb {C} [X]$ vara ett polynom av grad n som har k nollor inom cirkeln med radien 1/2 och de återstående nk nollorna utanför cirkeln med radie 2 . Med N=O(k) tillräckligt stor resulterar approximationen av konturintegralerna med hjälp av N punkter i en approximation $f_{0}$ av faktorn f med fel

$\|f-f_{0}\|\leq 2^{2k-N}\,nk\,100/98$ ,

där normen för ett polynom är summan av modulerna för dess koefficienter.

Eftersom nollorna i ett polynom är kontinuerliga i dess koefficienter, kan man göra nollorna för $f_{0}$ så nära nollorna för f som önskas genom att välja N tillräckligt stora. Men man kan förbättra denna approximation snabbare med en Newton-metod. Division av p med resten ger en approximation $g_{0}$ av den återstående faktorn g . Nu

$p-f_{0}g_{0}=(f-f_{0} )g_{0}+(g-g_{0})f_{0}+(f-f_{0})(g-g_{0})$ ,

så om man kasserar den sista andra ordningens termen måste man lösa $p-f_{0}g_{0}=f_{0}\Delta g+g_{0}\ Delta f$ använder valfri variant av den utökade euklidiska algoritmen för att erhålla de inkrementerade approximationerna $f_{1}=f_{0}+\Delta f$ och ${\ displaystyle g_{1}=g_{0}+\Delta g}$ . Detta upprepas tills stegen är noll i förhållande till den valda precisionen.

Graeffe iteration

Det avgörande steget i denna metod är att hitta en ring med relativ bredd 4 i det komplexa planet som inte innehåller några nollor av p och innehåller ungefär lika många nollor av p inuti som utanför det. Vilken annulus som helst med denna egenskap kan omvandlas, genom translation och skalning av polynomet, till annulus mellan radierna 1/2 och 2 runt origo. Men inte varje polynom medger en sådan delande annulus.

För att råda bot på denna situation tillämpas Graeffe-iterationen . Den beräknar en sekvens av polynom

$p_{0}=p,\qquad p_{j+1}( x)=(-1)^{\deg p}p_{j}({\sqrt {x}})\,p_{j}(-{\sqrt {x}}),$

där rötterna till $p_{j}(x)$ är de $2^{j}$ -:e dyadiska potenserna av rötterna till det initiala polynomet p . Genom att dela $p_{j}(x)=e(x^{2})+x\,o(x^{2} )$ i jämna och udda delar erhålls det efterföljande polynomet genom rent aritmetiska operationer som $p_{j+1}(x)=(-1)^{\deg p}(e(x)^{2}-x\,o(x)^{2})$ . Förhållandena för rötternas absoluta moduler ökar med samma potens $2^{j}$ och tenderar alltså till oändligheten. Väljer man j tillräckligt stor finner man slutligen en klyvningsring med relativ bredd 4 runt origo.

Den ungefärliga faktoriseringen av $p_{j}(x)\approx f_{j}(x)\,g_{j}(x)$ är ska nu lyftas tillbaka till det ursprungliga polynomet. För detta ändamål används en växling av Newton-steg och Padé-approximationer . Det är lätt att kontrollera det

${\frac {p_{j-1}(x)}{g_{j }(x^{2})}}\approx {\frac {f_{j-1}(x)}{g_{j-1}(-x)}}$

håller. Polynomen på vänster sida är kända i steg j , polynomen på höger sida kan erhållas som Padé approximanter av motsvarande grader för potensserieexpansionen av bråket på vänster sida.

Att hitta en bra cirkel

Genom att använda Graeffe-iterationen och alla kända uppskattningar för det absoluta värdet av den största roten kan man hitta uppskattningar R av detta absoluta värde med vilken precision som helst. Nu beräknar man uppskattningar för de största och minsta avstånden $R_{j}>r_{j}>0$ av någon rot av p ( x ) till någon av de fem mittpunkterna 0, 2 R , −2 R , 2 Ri , −2 Ri och väljer den med störst förhållande $R_{j}/r_{j}$ mellan de två. Genom denna konstruktion kan det garanteras att $R_{j}/r_{j}>e^{0{.}3}\approx 1.35$ för minst en center. För ett sådant centrum måste det finnas en rotfri ring med relativ bredd $\textstyle e^{0{.}3/n}\approx 1+{\frac {0{.}3}{n}}$ . Efter $\textstyle 3+\log _{2}(n)$ Graeffe-iterationer har motsvarande annulus av det itererade polynomet en relativ bredd som är större än 11 ​​> 4, vilket krävs för initial delning som beskrivs ovan (se Schönhage (1982)). Efter $\textstyle 4+\log _{2}(n)+\log _{2}(2+\ log _{2}(n))$ Graeffe-iterationer, motsvarande annulus har en relativ bredd som är större än $\textstyle 2^{13{.}8}\cdot n^{6{.}9}>(64\cdot n^{3})^{2}$ , vilket möjliggör en mycket förenklad initial uppdelning (se Malajovich/Zubelli (1997))

För att lokalisera den bästa rotfria ringen använder man en konsekvens av Rouché-satsen : För k = 1, ..., n − 1 är polynomekvationen

$\,0=\sum _{j\neq k}|p_{j}|u^{j}-|p_{k}|u^{k},$

u > 0, har enligt Descartes regel om tecken noll eller två positiva rötter $u_{k}<v_{k}$ . I det senare fallet finns det exakt k rötter inuti den (stängda) disken $D(0,u_{k})$ och $A( 0,u_{k},v_{k})$ är en rotfri (öppen) ring.

• Schönhage, Arnold (1982): Algebras grundläggande teorem i termer av beräkningskomplexitet. Preliminär rapport, Math. Inst. Univ. Tübingen (1982), 49 sidor. (ps.gz)
• Gourdon, Xavier (1996). Combinatoire, Algoritmique et Geometrie des Polynomes . Paris: Ecole Polytechnique.
• VY Pan (1996). "Optimala och nästan optimala algoritmer för att approximera polynomnollor" . Comput. Matematik. Appl . 31 (12): 97–138. doi : 10.1016/0898-1221(96)00080-6 .
• VY Pan (1997). "Lösa en polynomekvation: Viss historia och senaste framsteg". SIAM recension . 39 (2): 187–220. doi : 10.1137/S0036144595288554 .
• Gregorio Malajovich och Jorge P. Zubelli (1997). "En snabb och stabil algoritm för att dela polynom" . Datorer och matematik med applikationer . 33. Nr 3 (2): 1–23. doi : 10.1016/S0898-1221(96)00233-7 .
• Pan, Victor (1998). Algoritm för att approximera komplexa polynomnollor
• Pan, Victor (2002). Univariata polynom: nästan optimala algoritmer för numerisk faktorisering och rotsökning
• Magma dokumentation. Verkliga och komplexa fält: Elementoperationer .