Polinomok felosztása

A polinomok osztása a polinomok euklideszi gyűrűjének maradékával való osztás művelete egy változóban valamely mező felett . A műveletet végrehajtó naiv algoritmus az oszloposztás általánosított formája , amely könnyen megvalósítható manuálisan.

Bármely polinomhoz és , , vannak egyedi polinomok és olyanok, amelyek $f(x)$ $g(x)$ $g(x) \ne 0$ $q(x)$ $r(x)$

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

és alacsonyabb fokozata van, mint . $r(x)$ $g(x)$

A polinomiális osztási algoritmusok célja egy adott osztható és nem nulla osztó hányadosának és maradékának megtalálása [1] . $q(x)$ $r(x)$ $f(x)$ $g(x)$

A probléma leírása

A polinomok maradékkal való osztásának problémája a következő ekvivalens megfogalmazásokban fogalmazható meg [2] .

Hányados és maradék

A fok és fok polinomjait együtthatóikkal adjuk meg. Meg kell találni a hányadost és a maradékot úgy, hogy [2] ${\displaystyle S(x)=s_{0}+s_{1}x+\dots +s_{m}x^{m))$ $m$ ${\displaystyle T(x)=t_{0}+t_{1}x+\pontok +t_{n}x^{n))$ $n$ $Q(x)=q_{0}+q_{1}x+\pontok +q_{mn}x^{mn}$ ${\displaystyle R(x)=r_{0}+r_{1}x+\pontok +r_{n-1}x^{n-1))$

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

(egy)

Az így definiált polinomok egyediek - ha feltételezzük, hogy az ( 1 ) egyenletnek két megoldása van , és akkor $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),

amiből az következik, hogy vagy , ami egyben azt is jelenti , vagy a fok nem kisebb, mint a fok , ami definíció szerint lehetetlen [3] . $Q_{1}(x)=Q_{2}(x)$ $R_{1}(x)=R_{2}(x)$ $R_{1}(x)-R_{2}(x)$ $T(x)$ $R(x)$

Mátrix beállítás

Ez a probléma mátrix alakban átírható, ha feltételezzük, hogy és adottak , és úgy kell kiszámítanunk , hogy [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}\ vége \pontok &t_{n-1}&t_{n}\\\pontok &\pontok &t_{n-2}&t_{n-1}\\\vpontok &\dpontok &\vpontok &\vpontok \\0&\pontok &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)

Inverz Toeplitz mátrix

Tekintettel arra , hogy a feladat megoldásához elegendő a rendszer első egyenleteivel megtalálni a . Ha csak ezeket az egyenleteket vesszük figyelembe, akkor a probléma válik $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}&\ pontok &0&0\\\vpontok &\dpontok &\vpontok &\vpontok \\\pontok &\pontok &t_{n}&0\\\pontok &\pontok &t_{n-1}&t_{n}\end{bmátrix}} {\begin{bmatrix}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}_{\textstyle .}

(3)

Ennek az egyenletrendszernek a mátrixa alsó háromszög és Toeplitz , vezető együtthatókból és nullákból áll, és a rendszer megoldása ekvivalens az inverze megtalálásával [2] . $T(x)$

Inverz polinomi modulo

Legyen és az együtthatók sorozatának megfordításával kapott polinomok . A ( 3 ) egyenletrendszer úgy fogalmazható meg $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+\pontok +t_{0}x^{n }$ $S(x)$ $T(x)$

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

ahol , és azt jelenti, hogy a maradékok a polinomok és -val való elosztása után egyenlőek. Egy polinom osztása -vel ábrázolható , így a maradék egyenlő az első együtthatókból kapott polinomdal , azaz $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+\pontok +p_{k-1}x^{k-1}.

Ha a és polinomok ismertek, akkor , ahol az inverz polinom a maradékok gyűrűjében modulo . Így a keresés a megtalálásra redukálható, úgy , hogy $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))}.

(négy)

Ez a megfogalmazás lehetővé teszi az inverz mátrix megtalálását is a rendszerben ( 3 ):

Legyen a ( 3 ) méretmátrix . Ezután egy alsó háromszög alakú Toeplitz-mátrix, amelynek első oszlopa , ahol a ( 4 ) együtthatók vannak . $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)$

Bizonyíték

A ( 3 ) rendszer ekvivalens az egyenlettel . Ennek megfelelően a rendszer ${\displaystyle S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k))))$

{\begin{bmatrix}v_{mn}&\pontok &0&0\\\vpontok &\dpontok &\vpontok &\vpontok \\v_{1}&\pontok &v_{mn}&0\\v_{0} &\pontok &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}}

ként ábrázolható , ami a ( 4 ) esetben egyenértékű a ( 3 ) rendszerrel. ■ ${\displaystyle V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k))))$

Az elemeket meghatározó polinom tetszőlegessége miatt ez a tény lehetővé teszi, hogy megtaláljuk egy tetszőleges Toeplitz alsó háromszögmátrix inverzét [2] . $T(x)$ $T$

Formális hatványsorozat

Az egyenlet nem csak modulo , hanem a formális hatványsorok gyűrűjében lévő egyenlőségként is felfogható . Legyen és formális hatványsor, amely egybeesik az és polinomokkal . Ha ilyen kifejezésekkel találjuk meg a formális sorozatot $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)

akkor az alacsonyabb hatványokon lévő együtthatói megfelelnek a szükséges polinomnak . Ez a megközelítés azt is lehetővé teszi, hogy a ( 2 ) problémát egy végtelenül kiterjesztett Toeplitz-mátrixú és egy végtelenül kiterjesztett oszlopú rendszernek tekintsük , amelyben a maradékok oszlopa ki van zárva . Egy ilyen rendszer első sorait megoldva megkapjuk a sorozat első együtthatóit , nevezetesen . Ugyanakkor a hatványsorokkal végzett munka általában, amelyekben csak a sorozat első együtthatói érdekesek (például a korlátozott memória miatt), egyenértékű a polinomokkal való munkával, amelyek műveleteit a modulban hajtják végre. maradékok gyűrűje [4] . Különösen az első együtthatók keresése egyenértékű a [2] egyenlet megoldásával . $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))))$

Megoldási módszerek

Oszlopfelosztás

Az algoritmus során a nagyobb teljesítményű együtthatókat szekvenciálisan nullázzuk úgy, hogy abból kivonunk valamilyen hatványt együtthatókkal, amelyek aztán a hányadost alkotják . Kezdetben az együtthatót egyenlőnek kell meghatározni . Ha bővítjük , akkor $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).

Cserélésével ez az egyenlet alakot ölt $S'(x)=S(x)-q_{mn}x^{mn}T(x)$

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

hasonló az ( 1 ) egyenlethez. Ebben az esetben a th-edik együttható definíció szerint egyenlő -val , tehát a fok kisebb lesz, mint a fok . Az eljárást addig ismételjük, amíg a fok kisebb lesz, mint a fok , ami azt jelenti, hogy a következő egyenlő vele [3] . $m$ $S'(x)$ ${\displaystyle q_{mn))$ $0$ $S'(x)$ $S(x)$ $S'(x)$ $T(x)$ $S'(x)$ $R(x)$ $Q'(x)=0$

Példa

Hagyjuk és . Adott polinomokra az oszloposztást a következőképpen írhatjuk fel $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}}

Ily módon

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

vagyis a polinom hányados, a pedig a maradék. $Q(x)=x^{2}-9x-27$ $R(x)=-123$

Sieveking-Kohn algoritmus

1972-ben Malte Zieveking egy algoritmust javasolt egy adott és [5] egyenletének megoldására . 1974-ben Kong Xiangzhong kimutatta, hogy az algoritmus a Newton-módszer iterációja [6] számára . Ezzel a megközelítéssel az iteráció felveszi a formát $B(x)$ ${\displaystyle A(x)\cdot B(x)=C(x){\pmod {x^{n+1))))$ $Fejsze)$ $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},}

Ahol jelöli a függvény deriváltját a pontban . Az algoritmus pontosságának értékeléséhez megbecsülhetjük a különbséget ${\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},}

amiből az következik, hogy ha osztható -val (ami ekvivalens azzal, hogy az első együtthatók helyesen vannak definiálva), akkor osztható lesz -vel . Így a kezdeti feltétel mellett minden iteráció megkétszerezi a pontosan meghatározott együtthatók számát . Ezért az iterációk elegendőek a számításhoz . A gyors Fourier-transzformáció alkalmazása polinomok szorzására a fenti képletben a végső futási időt eredményezi , ami jelentősen javítja a szokásos hosszú szorzás becslését [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)$

Példa

Hagyjuk és . A ( 4 ) miatt meg kell találni . Az inverz polinomban a következőképpen keresünk: $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))))$

A kezdeti közelítés definíciója: ; ${\textstyle V_{0}={\frac {1}{T^{R}(0)))=1}$
Az első közelítés definíciója: ; $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$
A második közelítés definíciója: . $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+ 9x^{2}+3x+1$

A Newton-módszer tulajdonságai miatt az első együtthatók helyesen vannak meghatározva. Mivel a további számításokat modulo végezzük , a nagyobb teljesítményű együtthatók elvethetők. Innen $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}}},

melynek értelmében . $Q(x)=x^{2}-9x-27$

Algoritmusok elemzése

A különféle módszerek hatékonyságának értékeléséhez az aritmetikai áramkör bonyolultságát használják - az összeadási, szorzási, kivonási és osztási műveletek teljes számát a komplex számok területén, amelyeket az algoritmus működése során végre kell hajtani. Az algoritmus többprocesszoros megvalósításához szükséges párhuzamos lépések számát is megbecsüljük, feltételezve, hogy minden egyes processzor bármely lépésben legfeljebb egy műveletet tud végrehajtani [7] .

Az osztási algoritmus minden iterációja abból áll, hogy az eltolást valamilyen összeggel levonjuk -ból , ami a -ban tehető meg . Mivel a mérték , amely kezdetben egyenlő -val , addig csökken, amíg kisebb lesz, mint , az algoritmus teljes futási ideje így becsülhető meg , ahol [2] . $T(x)$ $S(x)$ $Tovább)$ $S(x)$ $m$ $n$ $O(kn)$ $k=mn$

Lásd még

Bezout tétele
Ruffini szabálya
Gröbner alapon
polinom
Szintetikus felosztás

Jegyzetek

↑ Skanavi M. I. Alapfokú matematika. - 2. kiadás, átdolgozva. és további - M . : Nauka, 1972. - S. 142-147. — 592 p.
↑ 1 2 3 4 5 6 7 Bini, Pan, 1986 , pp. 184-186
↑ 12 Knuth , 1997 , pp. 420-421
↑ Knuth, 1997 , pp. 525-533
↑ Szitálás, 1972
↑ Kung, 1974
↑ 1 2 Bini, Pan, 1986 , pp. 186-188

Irodalom

Bini D., Pan V. Polynomial division and its computational complexity (angol) // Journal of Complexity - Elsevier BV , 1986. - Vol. 2, Iss. 3. - P. 179-203. — ISSN 0885-064X ; 1090-2708 - doi:10.1016/0885-064X(86)90001-4
Knuth D. A számítógép-programozás művészete (angol) : Seminumerical Algorithms - 3 - Addison-Wesley , 1997. - Vol. 2. - 784 p. — ISBN 978-0-201-89684-8
Kung H. T. A hatványsorok reciprokáinak kiszámításáról (angol) // Numer. Math / F. Brezzi - Springer Science + Business Media , 1974. - 1. évf. 22, Iss. 5. - P. 341-348. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01436917
Sieveking M. Algorithm for division of powerseries (angol) // Computing - Springer Science + Business Media , 1972. - Vol. 10, Iss. 1-2. - P. 153-156. — ISSN 0010-485X ; 1436-5057 - doi:10.1007/BF02242389
Schönhage A. Variations on Computing Reciprocals of Power Series (angol) // Algorithms Seminar, 2000-2001 / F. Chyzak - Institut National de Recherche en Informatique en Informatique et en Automatique , 2001. - P. 81-84. — 197 p.