Polynomien jako

Polynomien jako on jakooperaatio polynomien euklidisen renkaan jäännöksellä yhdessä muuttujassa jonkin kentän yli . Tämän toiminnon toteuttava naiivi algoritmi on yleistetty sarakejaon muoto , joka on helppo toteuttaa manuaalisesti.

Kaikille polynomeille ja , , On olemassa ainutlaatuisia polynomeja ja sellaisia, että $f(x)$ $g(x)$ $g(x) \ne 0$ $q(x)$ $r(x)$

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

ja sen tutkinto on alempi kuin . $r(x)$ $g(x)$

Polynomijakoalgoritmien tarkoitus on löytää osamäärä ja jäännös tietylle jaolliselle ja nollasta poikkeavalle jakajalle [1] . $q(x)$ $r(x)$ $f(x)$ $g(x)$

Ongelman selvitys

Ongelma polynomien jakamisesta jäännöksellä voidaan muotoilla seuraavilla ekvivalenteilla formulaatioilla [2] .

Osamäärä ja jäännös

Asteen ja asteen polynomit saadaan kertoimillaan. Osamäärä ja jäännös on löydettävä siten, että [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+\pisteet +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).

(yksi)

Tällä tavalla määritellyt polynomit ovat ainutlaatuisia - jos oletetaan, että yhtälöllä ( 1 ) on kaksi ratkaisua ja $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),

josta seuraa, että joko , mikä tarkoittaa myös , tai aste ei ole pienempi kuin aste , mikä on määritelmän mukaan mahdotonta [3] . $Q_{1}(x)=Q_{2}(x)$ $R_{1}(x)=R_{2}(x)$ $R_{1}(x)-R_{2}(x)$ $T(x)$ $R(x)$

Matriisiasetus

Tämä ongelma voidaan kirjoittaa uudelleen matriisimuotoon, jos oletetaan, että ja on annettu , ja meidän on laskettava siten, että [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}&\pisteet &0&0\\\vpisteet &\ddots &\vdots &\vdots \\\pisteet &\pisteet &t_{n}&0\\\pisteet & \pisteet &t_{n-1}&t_{n}\\\pisteet &\pisteet &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)

Käänteinen Toeplitz-matriisi

Johtuen siitä, että ongelman ratkaisemiseksi riittää löytää järjestelmän ensimmäisten yhtälöiden avulla . Jos tarkastelemme vain näitä yhtälöitä, ongelma tulee $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}&\ pisteet &0&0\\\vpisteet &\dpisteet &\vpisteet &\vpisteet \\\pisteet &\pisteet &t_{n}&0\\\pisteet &\pisteet &t_{n-1}&t_{n}\end{bmatrix}} {\begin{bmatrix}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}_{\textstyle .}

(3)

Tämän yhtälöjärjestelmän matriisi on alakolmio ja Toeplitz , joka koostuu johtavista kertoimista ja nollia, ja järjestelmän ratkaisu vastaa sen käänteisen löytämistä [2] . $T(x)$

Käänteinen polynomimoduuli

Olkoon ja polynomeja, jotka on saatu kertoimien sarjasta ja käänteisillä. Yhtälöjärjestelmä ( 3 ) voidaan muotoilla seuraavasti $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))},

jossa , ja tarkoittaa, että jakojäännökset polynomien ja arvon jakamisen jälkeen ovat yhtä suuret. Polynomin jako voidaan esittää muodossa , joten jäännös on yhtä suuri kuin ensimmäisistä kertoimista saatu polynomi , eli $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+\pisteet +p_{k-1}x^{k-1}.

Jos polynomit ja tunnetaan, niin , Missä on käänteinen polynomi jäännösten renkaassa modulo . Siten haku voidaan lyhentää löytämiseen siten, että $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))}.

(neljä)

Tämä muotoilu mahdollistaa myös käänteisen matriisin löytämisen järjestelmästä ( 3 ):

Olkoon kokomatriisi alkaen ( 3 ). Sitten on alempi kolmiomainen Toeplitz-matriisi, jonka ensimmäinen sarake on , missä ovat kertoimet kohdasta ( 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)$

Todiste

Järjestelmä ( 3 ) vastaa yhtälöä . Vastaavasti järjestelmä ${\displaystyle S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k))))$

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

voidaan esittää muodossa , joka tapauksessa ( 4 ) vastaa järjestelmää ( 3 ). ■ ${\displaystyle V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k))))$

Alkiot määrittävän polynomin mielivaltaisuudesta johtuen tämä tosiasia mahdollistaa käänteisarvon mielivaltaiselle Toeplitzin alemmalle kolmiomatriisille [2] . $T(x)$ $T$

Muodollinen tehosarja

Yhtälöä voidaan tarkastella paitsi modulon myös tasa-arvona muodollisten potenssisarjojen kehässä . Antaa ja olla muodollinen potenssisarja, joka vastaa polynomeja ja . Jos näillä termeillä löydämme muodollisen sarjan $S^{R}(x)=T^{R}(x)Q^{R}(x)$ $x^{mn}$ $s(x)$ $t(x)$ $S^{R}(x)$ $T^{R}(x)$

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

(5)

silloin sen kertoimet pienemmillä tehoilla vastaavat vaadittua polynomia . Tämän lähestymistavan avulla voimme myös tarkastella ongelmaa ( 2 ) järjestelmänä, jossa on äärettömästi laajennettu Toeplitz-matriisi ja äärettömästi laajennettu sarake , jossa jäännössarake on jätetty pois . Sellaisen järjestelmän ensimmäisten rivien ratkaiseminen antaa sarjan ensimmäiset kertoimet , nimittäin . Samanaikaisesti työskentely yleisesti potenssisarjoilla, joissa vain sarjan ensimmäiset kertoimet kiinnostavat (esimerkiksi rajoitetun muistin vuoksi), vastaa työskentelyä polynomien kanssa, joiden toiminnot suoritetaan modulossa. jäännösrengas [4] . Erityisesti ensimmäisten kertoimien etsiminen vastaa yhtälön [2] ratkaisemista . $m-n+1$ $Q^{R}(x)$ $q$ $r$ $h$ $h$ $q(x)$ $q_{mn},q_{mn-1},\dots ,q_{mn-h+1}$ $h$ ${\näyttötyyli x^{h))$ $h$ $q(x)$ ${\displaystyle s(x)\equiv t(x)q(x){\pmod {x^{h))))$

Ratkaisumenetelmät

Sarakejako

Algoritmin aikana suuremmilla tehoilla olevat kertoimet nollataan peräkkäin vähentämällä siitä kerrottuna jollain potenssilla kertoimilla, jotka sitten muodostavat osamäärän . Aluksi kerroin määritetään yhtä suureksi kuin . Jos laajennetaan , niin $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).

Korvaamalla tämä yhtälö saa muodon $S'(x)=S(x)-q_{mn}x^{mn}T(x)$

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

samanlainen kuin yhtälö ( 1 ). Tässä tapauksessa th kerroin määritelmän mukaan on yhtä suuri kuin , joten aste on pienempi kuin aste . Toimenpide toistetaan, kunnes aste on pienempi kuin aste , mikä tarkoittaa, että seuraava on yhtä suuri kuin se [3] . $m$ $S'(x)$ ${\displaystyle q_{mn))$ $0$ $S'(x)$ $S(x)$ $S'(x)$ $T(x)$ $S'(x)$ $R(x)$ $Q'(x)=0$

Esimerkki

Anna ja . Tietyille polynomeille sarakkeen jako voidaan kirjoittaa muodossa $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}}

Tällä tavalla,

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

eli polynomi on osamäärä ja a on jäännös. $Q(x)=x^{2}-9x-27$ $R(x)=-123$

Sieveking-Kohn-algoritmi

Vuonna 1972 Malte Zieveking ehdotti algoritmia ratkaisun löytämiseksi yhtälöön annetuille ja [5] . Vuonna 1974 Kong Xiangzhong osoitti, että , algoritmi on iteraatio Newtonin menetelmästä [ 6] . Tällä lähestymistavalla iteraatio saa muodon $B(x)$ ${\displaystyle A(x)\cdot B(x)=C(x){\pmod {x^{n+1))))$ $Kirves)$ $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},}

Missä tarkoittaa funktion derivaatta pisteessä . Algoritmin tarkkuuden arvioimiseksi voidaan arvioida ero ${\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},}

josta seuraa, että jos se on jaollinen (mikä vastaa sitä tosiasiaa, että ensimmäiset kertoimet on määritelty oikein), niin se on jaollinen . Näin ollen, kun otetaan huomioon alkuehto , jokainen iteraatio kaksinkertaistaa tarkasti määriteltyjen kertoimien määrän . Siksi iteraatiot ovat riittäviä laskentaan . Nopean Fourier-muunnoksen soveltaminen polynomien kertolaskuun yllä olevassa kaavassa johtaa lopulliseen ajoaikaan , mikä parantaa merkittävästi estimaattia tavalliselle pitkälle kertolaskulle [7] . $V_{k}-B$ ${\näyttötyyli 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)$

Esimerkki

Anna ja . Kohdan ( 4 ) vuoksi on tarpeen löytää . Käänteispolynomia etsitään seuraavasti: $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))))$

Alkuperäinen approksimaatio määritellään ; ${\textstyle V_{0}={\frac {1}{T^{R}(0)))=1}$
Ensimmäinen approksimaatio määritellään ; $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$
Toinen approksimaatio määritellään . $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+ 9x^{2}+3x+1$

Newtonin menetelmän ominaisuuksista johtuen ensimmäiset kertoimet määritetään oikein. Koska lisälaskelmia tehdään modulo , suurempien tehojen kertoimet voidaan hylätä. Täältä $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}}},

jonka nojalla . $Q(x)=x^{2}-9x-27$

Algoritmien analyysi

Eri menetelmien tehokkuuden arvioimiseksi käytetään aritmeettisen piirin monimutkaisuutta - algoritmin toiminnan aikana suoritettavien yhteen-, kerto-, vähennys- ja jakolaskuoperaatioiden kokonaismäärä kompleksilukujen kentässä. Arvioidaan myös algoritmin moniprosessoritoteutukseen tarvittavien rinnakkaisten vaiheiden määrä olettaen , että jokainen prosessori missä tahansa vaiheessa voi suorittaa enintään yhden toiminnon [7] .

Jokainen jakoalgoritmin iteraatio koostuu offsetin vähentämisestä jollain määrällä arvosta , mikä voidaan tehdä kohdassa . Koska aste , joka on alun perin yhtä suuri kuin , pienenee, kunnes siitä tulee pienempi kuin , algoritmin kokonaisajoaika voidaan arvioida muodossa , jossa [2] . $T(x)$ $S(x)$ $Päällä)$ $S(x)$ $m$ $n$ $O(kn)$ $k = mn$

Katso myös

Muistiinpanot

↑ Skanavi M. I. Alkeinen matematiikka. - 2. painos, tarkistettu. ja ylimääräisiä - M .: Nauka, 1972. - S. 142-147. — 592 s.
↑ 1 2 3 4 5 6 7 Bini, Pan, 1986 , s. 184-186
↑ 12 Knuth , 1997 , s. 420-421
↑ Knuth, 1997 , s. 525-533
↑ Seulonta, 1972
↑ Kung, 1974
↑ 1 2 Bini, Pan, 1986 , s. 186-188

Kirjallisuus

Bini D., Pan V. Polynomijako ja sen laskennallinen monimutkaisuus (englanniksi) // Journal of Complexity - Elsevier BV , 1986. - Voi. 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 (Englanti) : Puolinumeeriset algoritmit - 3 - Addison-Wesley , 1997. - Voi. 2. - 784 s. — ISBN 978-0-201-89684-8
Kung H. T. Potenttisarjojen käänteisten laskemisesta (englanniksi) // Numero. Math / F. Brezzi - Springer Science + Business Media , 1974. - Voi. 22, Iss. 5. - s. 341-348. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01436917
Sieveking M. Algoritmi tehosarjojen jakamiseen (englanniksi) // Computing - Springer Science + Business Media , 1972. - Voi. 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 (englanti) // Algorithms Seminar, 2000-2001 / F. Chyzak - Institut National de Recherche en Informatique en Informatique et en Automatique , 2001. - P. 81-84. - 197 s.