Division av polynom

Division av polynom är operationen av division med en rest i den euklidiska ringen av polynom i en variabel över något fält . Den naiva algoritmen som implementerar denna operation är en generaliserad form av kolumndelning , som enkelt implementeras manuellt.

För alla polynom och , , Det finns unika polynom och sådant $f(x)$ $g(x)$ $g(x) \ne 0$ $q(x)$ $r(x)$

\frac{f(x)}{g(x)}=q(x) + \frac{r(x)}{g(x)}

och har en lägre grad än . $r(x)$ $g(x)$

Syftet med polynomdivisionsalgoritmer är att hitta kvoten och resten för en given delbar och icke-nolldelare [1] . $q(x)$ $r(x)$ $f(x)$ $g(x)$

Förklaring av problemet

Problemet med att dela polynom med resten kan formuleras i följande ekvivalenta formuleringar [2] .

Kvotient och återstod

Polynom av grad och grad ges av deras koefficienter. Det är nödvändigt att hitta kvoten och resten så att [2] ${\displaystyle S(x)=s_{0}+s_{1}x+\dots +s_{m}x^{m))$ $m$ ${\displaystyle T(x)=t_{0}+t_{1}x+\dots +t_{n}x^{n))$ $n$ $Q(x)=q_{0}+q_{1}x+\dots +q_{mn}x^{mn}$ ${\displaystyle R(x)=r_{0}+r_{1}x+\dots +r_{n-1}x^{n-1))$

S(x)=T(x)Q(x)+R(x).

(ett)

Polynomen definierade på detta sätt och är unika - om vi antar att ekvationen ( 1 ) har två lösningar och , då $Q(x)$ $R(x)$ $Q_{1}(x),R_{1}(x)$ $Q_{2}(x),R_{2}(x)$

T(x)\left(Q_{1}(x)-Q_{2}(x)\right)=R_{1}(x)-R_{2}(x),

därav följer att antingen , vilket också innebär , eller graden är inte mindre än graden , vilket är omöjligt per definition [3] . $Q_{1}(x)=Q_{2}(x)$ $R_{1}(x)=R_{2}(x)$ $R_{1}(x)-R_{2}(x)$ $T(x)$ $R(x)$

Matrisinställning

Detta problem kan skrivas om i matrisform, om vi antar att och är givna , och vi behöver beräkna så att [2] ${\displaystyle s_{0},s_{1},\dots ,s_{m))$ ${\displaystyle t_{0},t_{1},\dots ,t_{n))$ ${\displaystyle q_{0},q_{1},\dots ,q_{mn))$ ${\displaystyle r_{0},r_{1},\dots ,r_{n-1))$

{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\\s_{n-1}\\\vdots \\s_{0}\ end{bmatrix}}={\begin{bmatrix}t_{n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\\dots &\dots &t_{n}&0\\\dots & \dots &t_{n-1}&t_{n}\\\dots &\dots &t_{n-2}&t_{n-1}\\\vdots &\ddots &\vdots &\vdots \\0&\dots &0&t_ {0}\end{bmatrix}}{\begin{bmatrix}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}+{\begin{bmatrix}0\ \\vdots \\0\\0\\r_{n-1}\\\vdots \\r_{0}\end{bmatrix}}_{\textstyle .}

(2)

Invers Toeplitz-matris

På grund av det faktum att , för att lösa problemet, räcker det att hitta genom de första ekvationerna i systemet . Om vi bara betraktar dessa ekvationer blir problemet $R(x)=S(x)-T(x)Q(x)$ ${\displaystyle q_{mn},\dots ,q_{0))$ $m-n+1$

{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}t_{n}&\ dots &0&0\\\vdots &\ddots &\vdots &\vdots \\\dots &\dots &t_{n}&0\\\dots &\dots &t_{n-1}&t_{n}\end{bmatrix}} {\begin{bmatrix}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}_{\textstyle .}

(3)

Matrisen för detta ekvationssystem är lägre triangulär och Toeplitz , sammansatt av ledande koefficienter och nollor, och systemets lösning är likvärdig med att hitta dess invers [2] . $T(x)$

Invers polynom modulo

Låta och vara polynom erhållna från och genom att vända koefficientsekvensen. Ekvationssystemet ( 3 ) kan formuleras som $S^{R}(x)=x^{m}S(x^{-1})=s_{m}+s_{m-1}x+\dots +s_{0}x^{m }$ $T^{R}(x)=x^{n}T(x^{-1})=t_{n}+t_{n-1}x+\dots +t_{0}x^{n }$ $S(x)$ $T(x)$

S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k))},

där , och betyder att resten efter att ha dividerat polynomen och med är lika. Delingen av ett polynom med kan representeras som , så resten är lika med polynomet som erhålls från de första koefficienterna , det vill säga, $k=m-n+1$ ${\bmod {x}}^{mn}$ $S^{R}(x)$ $T^{R}(x)Q^{R}(x)$ $x^{k}$ $P(x)$ $x^{k}$ $P(x)=x^{k}Q(x)+R(x)$ $R(x)$ $k$ $P(x)$

R(x)=p_{0}+p_{1}x+\dots +p_{k-1}x^{k-1}.

Om polynomen och är kända, då , Där är det inversa polynomet i ringen av rester modulo . Således kan sökningen reduceras till att hitta , så att $S^{R}(x)$ $T^{R}(x)$ ${\displaystyle Q^{R}(x)\equiv S^{R}(x)T^{R}(x)^{-1}{\pmod {x^{k))))$ ${\displaystyle T^{R}(x)^{-1))$ $T^{R}(x)$ $x^{k}$ $Q(x)$ ${\displaystyle V(x)=v_{0}+v_{1}x+\dots +v_{k}x^{k))$

V^{R}(x)\equiv T^{R}(x)^{-1}{\pmod {x^{k))}.

(fyra)

Denna formulering gör det också möjligt att hitta den inversa matrisen i systemet ( 3 ):

Låt vara storleksmatrisen från ( 3 ). Sedan är en lägre triangulär Toeplitz-matris, vars första kolumn är , var är koefficienterna från ( 4 ). $T$ $k$ $T^{-1}$ ${\begin{bmatrix}v_{k-1}&v_{k-2}&\dots &v_{0}\end{bmatrix}}^{T}$ $v_{0},\dots ,v_{k-1}$ $V(x)$

Bevis

System ( 3 ) är ekvivalent med ekvationen . Följaktligen systemet ${\displaystyle S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k))))$

{\begin{bmatrix}v_{mn}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\v_{1}&\dots &v_{mn}&0\\v_{0} &\dots &v_{mn-1}&v_{mn}\end{bmatrix}}{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{ bmatrix}}={\begin{bmatrix}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}

kan representeras som , vilket i fallet ( 4 ) motsvarar system ( 3 ). ■ ${\displaystyle V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k))))$

På grund av godtyckligheten hos polynomet som definierar elementen , tillåter detta faktum oss att hitta inversen till en godtycklig Toeplitz nedre triangulär matris [2] . $T(x)$ $T$

Formell maktserie

Ekvationen kan ses inte bara modulo , utan också som en likhet i ringen av formella effektserier . Låta och vara formell potensserier som sammanfaller med polynomen och . Om vi i sådana termer finner den formella serien $S^{R}(x)=T^{R}(x)Q^{R}(x)$ ${\displaystyle x^{mn))$ $s(x)$ $t(x)$ $S^{R}(x)$ $T^{R}(x)$

q(x)={\frac {s(x)}{t(x)))),

(5)

då kommer dess koefficienter vid lägre potenser att motsvara det erforderliga polynomet . Detta tillvägagångssätt tillåter oss också att betrakta problem ( 2 ) som ett system med en oändligt utökad Toeplitz-matris och en oändligt utökad kolumn , i vilken kolumnen av residualer är exkluderad . Att lösa de första raderna i ett sådant system kommer att ge de första koefficienterna i serien , nämligen . Samtidigt är att arbeta med potensserier i allmänhet, där endast de första koefficienterna i serien är av intresse (till exempel på grund av begränsat tillgängligt minne), likvärdigt med att arbeta med polynom, på vilka operationer utförs i modulo ring av rester [4] . I synnerhet är sökningen efter de första koefficienterna ekvivalent med att lösa ekvationen [2] . $m-n+1$ $Q^{R}(x)$ $q$ $r$ $h$ $h$ $q(x)$ $q_{mn},q_{mn-1},\dots ,q_{mn-h+1}$ $h$ ${\displaystyle x^{h))$ $h$ $q(x)$ ${\displaystyle s(x)\equiv t(x)q(x){\pmod {x^{h))))$

Lösningsmetoder

Kolumnindelning

Under algoritmens gång nollställs koefficienterna vid högre potenser sekventiellt genom att subtrahera från den multiplicerat med någon potens med koefficienter, som sedan bildar kvoten . Inledningsvis bestäms koefficienten lika med . Om vi expanderar , alltså $S(x)$ $T(x)$ $x$ $Q(x)$ ${\displaystyle q_{mn))$ ${\textstyle {\frac {s_{m}}{t_{n}}}}$ $Q(x)=q_{mn}x^{mn}+Q'(x)$

S(x)=T(x)(q_{mn}x^{mn}+Q'(x))+R(x).

Genom att ersätta , tar denna ekvation formen $S'(x)=S(x)-q_{mn}x^{mn}T(x)$

S'(x)=T(x)Q'(x)+R(x),

liknande ekvation ( 1 ). I det här fallet är den e koefficienten , per definition , lika med , så graden kommer att vara mindre än graden . Proceduren upprepas tills graden blir mindre än graden , vilket kommer att innebära att nästa är lika med den [3] . $m$ $S'(x)$ ${\displaystyle q_{mn))$ $0$ $S'(x)$ $S(x)$ $S'(x)$ $T(x)$ $S'(x)$ $R(x)$ $Q'(x)=0$

Exempel

Låt och . För givna polynom kan kolumndelning med skrivas som $S(x)=x^{3}-12x^{2}-42$ $T(x)=x-3$ $S(x)$ $T(x)$

{\begin{array}{rr}-{\begin{array}{llll}x^{3}&-12x^{2}&{\color {white}+0x}&-42\\x ^{3}&-3x^{2}&&\\\hline \end{array}}&{\begin{array}{|l}x-3\\\hline x^{2}-9x-27\ end{array}}\\-{\begin{array}{lll}-9x^{2}&&-42\\-9x^{2}&+27x&\\\hline \end{array}}&\\ -{\begin{array}{ll}-27x&-42\\-27x&+81\\\hline \end{array}}&\\-123\end{array}}

På det här sättet,

{\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}} ,

det vill säga polynomet är en kvot och a är resten. $Q(x)=x^{2}-9x-27$ $R(x)=-123$

Sieveking-Kohn algoritm

1972 föreslog Malte Zieveking en algoritm för att hitta en lösning på en ekvation för givna och [5] . 1974 visade Kong Xiangzhong att för , algoritmen är en iteration av Newtons metod för [6] . Med detta tillvägagångssätt tar iterationen formen $B(x)$ ${\displaystyle A(x)\cdot B(x)=C(x){\pmod {x^{n+1))))$ $Yxa)$ $C(x)$ $C(x)=1$ $f(V)=V^{-1}-A$

{\textstyle V_{k+1}=V_{k}-{\frac {f(V_{k})}{f'(V_{k))}}=2V_{k}-AV_{k}^{ 2},}

Där betecknar derivatan av funktionen i punkten . För att utvärdera algoritmens noggrannhet kan man uppskatta skillnaden ${\displaystyle f'(V_{k})=-V_{k}^{-2))$ $f(V)$ $V_{k}$

{\textstyle V_{k+1}-B=A(2V_{k}A^{-1}-V_{k}^{2}-A^{-2})=-A(V_{k}- B)^{2},}

av vilket det följer att om den är delbar med (vilket motsvarar det faktum att de första koefficienterna är korrekt definierade), så kommer den att vara delbar med . Med tanke på det initiala villkoret fördubblar varje iteration således antalet exakt definierade koefficienter . Därför räcker iterationer för beräkningen . Att tillämpa den snabba Fouriertransformen på multiplikationen av polynom i formeln ovan leder till den slutliga körtiden , vilket avsevärt förbättrar uppskattningen för den vanliga långa multiplikationen [7] . $V_{k}-B$ ${\displaystyle x^{t))$ $t$ $V_{k}$ $V_{k+1}-B$ ${\displaystyle x^{2t))$ ${\displaystyle V_{0}=b_{0}=a_{0}^{-1))$ $B(x)$ ${\displaystyle A(x)^{-1}{\pmod {x^{n+1))))$ $O(\log n)$ $O(n\log n)$

Exempel

Låt och . På grund av ( 4 ) är det nödvändigt att hitta . Det inversa polynomet söks på följande sätt: $S(x)=x^{3}-12x^{2}-42$ $T(x)=x-3$ ${\displaystyle Q^{R}(x)=(-42x^{3}-12x+1)(-3x+1)^{-1}{\pmod {x^{3))))$ ${\displaystyle V(x)=(-3x+1)^{-1}{\pmod {x^{3))))$

Den initiala approximationen definieras som ; ${\textstyle V_{0}={\frac {1}{T^{R}(0)))=1}$
Den första approximationen definieras som ; $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$
Den andra approximationen definieras som . $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+ 9x^{2}+3x+1$

På grund av egenskaperna hos Newtons metod bestäms de första koefficienterna korrekt. Eftersom ytterligare beräkningar görs modulo , kan koefficienterna vid högre potenser förkastas. Härifrån $2^{2}=4$ $V_{2}(x)$ $x^{3}$

Q^{R}(x)\equiv (-12x+1)(9x^{2}+3x+1)\equiv -108x^{3}-27x^{2}-9x+1\equiv -27x^{2}-9x+1{\pmod {x^{3}}},

i kraft av vilken . $Q(x)=x^{2}-9x-27$

Analys av algoritmer

För att utvärdera effektiviteten av olika metoder används den aritmetiska kretsens komplexitet - det totala antalet additions-, multiplikations-, subtraktions- och divisionsoperationer över fältet av komplexa tal som måste utföras under driften av algoritmen. Antalet parallella steg som krävs för multiprocessorimplementeringen av algoritmen uppskattas också, förutsatt att varje processor i vilket steg som helst inte kan utföra mer än en operation [7] .

Varje iteration av divisionsalgoritmen består i att subtrahera förskjutningen med något belopp från , vilket kan göras i . Eftersom graden , initialt lika med , minskar tills den blir mindre än , kan den totala körtiden för algoritmen uppskattas som , där [2] . $T(x)$ $S(x)$ $På)$ $S(x)$ $m$ $n$ $O(kn)$ $k=mn$

Se även

Bezouts teorem
Ruffinis regel
Gröbner grund
polynom
Syntetisk division

Anteckningar

↑ Skanavi M. I. Elementär matematik. - 2:a uppl., reviderad. och ytterligare - M . : Nauka, 1972. - S. 142-147. — 592 sid.
↑ 1 2 3 4 5 6 7 Bini, Pan, 1986 , s. 184-186
↑ 12 Knuth , 1997 , s. 420-421
↑ Knuth, 1997 , s. 525-533
↑ Sieveking, 1972
↑ Kung, 1974
↑ 1 2 Bini, Pan, 1986 , s. 186-188

Litteratur

Bini D., Pan V. Polynomindelning och dess beräkningskomplexitet (engelska) // Journal of Complexity - Elsevier BV , 1986. - Vol. 2, Iss. 3. - S. 179-203. — ISSN 0885-064X ; 1090-2708 - doi:10.1016/0885-064X(86)90001-4
Knuth D. The Art of Computer Programming (engelska) : Seminumerical Algorithms - 3 - Addison-Wesley , 1997. - Vol. 2. - 784 sid. — ISBN 978-0-201-89684-8
Kung H. T. On computing reciprocals of power series (engelska) // Numer. Math / F. Brezzi - Springer Science + Business Media , 1974. - Vol. 22, Iss. 5. - s. 341-348. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01436917
Sieveking M. An algorithm for division of powerseries (engelska) // Computing - Springer Science + Business Media , 1972. - Vol. 10, Iss. 1-2. - S. 153-156. — ISSN 0010-485X ; 1436-5057 - doi:10.1007/BF02242389
Schönhage A. Variations on Computing Reciprocals of Power Series (engelska) // Algoritmseminarium, 2000-2001 / F. Chyzak - Institut National de Recherche en Informatique en Informatique et en Automatique , 2001. - S. 81-84. — 197 sid.