Împărțirea polinoamelor

Împărțirea polinoamelor este operația de împărțire cu un rest în inelul euclidian de polinoame într-o variabilă într-un anumit câmp . Algoritmul naiv care implementează această operație este o formă generalizată de împărțire a coloanei , care este ușor de implementat manual.

Pentru orice polinoame și , , există polinoame unice și astfel încât $f(x)$ $g(x)$ $g(x) \ne 0$ $q(x)$ $r(x)$

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

si are un grad mai mic decat . $r(x)$ $g(x)$

Scopul algoritmilor de împărțire polinomială este de a găsi câtul și restul pentru un divizibil dat și divizor diferit de zero [1] . $q(x)$ $r(x)$ $f(x)$ $g(x)$

Enunțul problemei

Problema împărțirii polinoamelor cu rest poate fi formulată în următoarele formulări echivalente [2] .

Coeficient și rest

Polinoamele de grad și grad sunt date de coeficienții lor. Este necesar să se găsească câtul și restul astfel încât [2] $S(x)=s_{0}+s_{1}x+\dots +s_{m}x^{m)$ $m$ $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}$ $R(x)=r_{0}+r_{1}x+\dots +r_{n-1}x^{n-1)$

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

(unu)

Polinoamele definite în acest fel și sunt unice - dacă presupunem că ecuația ( 1 ) are două soluții și , atunci $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),

din care rezultă că fie , ceea ce implică și , fie gradul nu este mai mic decât gradul , ceea ce este imposibil prin definiție [3] . $Q_{1}(x)=Q_{2}(x)$ $R_{1}(x)=R_{2}(x)$ $R_{1}(x)-R_{2}(x)$ $T(x)$ $R(x)$

Setarea matricei

Această problemă poate fi rescrisă sub formă de matrice, dacă presupunem că și sunt date , și trebuie să calculăm astfel încât [2] $s_{0},s_{1},\dots ,s_{m)$ $t_{0},t_{1},\dots,t_{n)$ $q_{0},q_{1},\dots,q_{mn)$ $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)

Matricea inversă Toeplitz

Datorită faptului că , pentru a rezolva problema, este suficient să găsim prin primele ecuații ale sistemului . Dacă luăm în considerare doar aceste ecuații, problema devine $R(x)=S(x)-T(x)Q(x)$ $q_{mn},\dots,q_{0)$ $m-n+1$

{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}t_{n}&\ puncte &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)

Matricea acestui sistem de ecuații este triunghiulară inferioară și Toeplitz , compusă din coeficienți conducători și zerouri, iar soluția sistemului este echivalentă cu găsirea inversului său [2] . $T(x)$

Modul polinom invers

Fie și polinoame obținute din și prin inversarea șirului de coeficienți. Sistemul de ecuații ( 3 ) poate fi formulat ca $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))},

unde , și înseamnă că resturile după împărțirea polinoamelor și la sunt egale. Împărțirea unui polinom prin poate fi reprezentată ca , deci restul este egal cu polinomul obținut din primii coeficienți , adică $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}.

Dacă polinoamele și sunt cunoscute, atunci , unde este polinomul invers din inelul de reziduuri modulo . Astfel, căutarea poate fi redusă la găsirea , astfel încât $S^{R}(x)$ $T^{R}(x)$ $Q^{R}(x)\equiv S^{R}(x)T^{R}(x)^{-1}{\pmod {x^{k)))$ $T^{R}(x)^{-1)$ $T^{R}(x)$ $x^{k}$ $Q(x)$ $V(x)=v_{0}+v_{1}x+\dots +v_{k}x^{k)$

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

(patru)

Această formulare permite, de asemenea, găsirea matricei inverse în sistem ( 3 ):

Fie matricea dimensiunilor din ( 3 ). Apoi este o matrice Toeplitz triunghiulară inferioară, a cărei prima coloană este , unde sunt coeficienții din ( 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)$

Dovada

Sistemul ( 3 ) este echivalent cu ecuaţia . În consecință, sistemul $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}}

poate fi reprezentat ca , care în cazul ( 4 ) este echivalent cu sistemul ( 3 ). ■ $V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k))}$

Datorită caracterului arbitrar al polinomului care definește elementele , acest fapt ne permite să găsim inversul unei matrice triunghiulare inferioară Toeplitz arbitrară [2] . $T(x)$ $T$

Seria de putere formală

Ecuația poate fi privită nu numai modulo , ci și ca o egalitate în inelul seriei de puteri formale . Fie și serii de puteri formale care coincid cu polinoamele și . Dacă în asemenea termeni găsim seria formală $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)

atunci coeficienții săi la puteri mai mici vor corespunde polinomului necesar . Această abordare ne permite de asemenea să considerăm problema ( 2 ) ca un sistem cu o matrice Toeplitz infinit extinsă și o coloană infinit extinsă , în care coloana de reziduuri este exclusă . Rezolvarea primelor rânduri ale unui astfel de sistem va da primii coeficienți ai seriei și anume . În același timp, lucrul cu serii de puteri în general, în care interesează doar primii coeficienți ai seriei (de exemplu, din cauza memoriei disponibile limitate), echivalează cu lucrul cu polinoame, operații asupra cărora sunt efectuate în modulo. inel de reziduuri [4] . În special, căutarea primilor coeficienți este echivalentă cu rezolvarea ecuației [2] . $m-n+1$ $Q^{R}(x)$ $q$ $r$ $h$ $h$ $q(x)$ $q_{mn},q_{mn-1},\dots,q_{mn-h+1}$ $h$ $x^{h)$ $h$ $q(x)$ $s(x)\equiv t(x)q(x){\pmod {x^{h))}$

Metode de rezolvare

Divizarea coloanelor

În cursul algoritmului, coeficienții la puteri mai mari sunt zero succesiv scăzând din acesta înmulțit cu o putere cu coeficienți, care formează apoi câtul . Inițial, coeficientul este determinat egal cu . Dacă ne extindem , atunci $S x)$ $T(x)$ $X$ $Q(x)$ $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).

Prin înlocuirea , această ecuație ia forma $S'(x)=S(x)-q_{mn}x^{mn}T(x)$

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

similar cu ecuația ( 1 ). În acest caz, al- lea coeficient , prin definiție , este egal cu , deci gradul va fi mai mic decât gradul . Procedura se repetă până când gradul devine mai mic decât gradul , ceea ce va însemna că următorul este egal cu acesta [3] . $m$ $S'(x)$ $q_{mn)$ $0$ $S'(x)$ $S x)$ $S'(x)$ $T(x)$ $S'(x)$ $R(x)$ $Q'(x)=0$

Exemplu

Lasă și . Pentru polinoame date, împărțirea coloanei cu poate fi scrisă ca $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 {alb}+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}}

În acest fel,

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

adică polinomul este un cot și a este restul. $Q(x)=x^{2}-9x-27$ $R(x)=-123$

Algoritmul Sieveking-Kohn

În 1972, Malte Zieveking a propus un algoritm pentru găsirea unei soluții la o ecuație pentru date și [5] . În 1974 Kong Xiangzhong a arătat că pentru , algoritmul este o iterație a metodei lui Newton pentru [6] . Cu această abordare, iterația ia forma $B(x)$ $A(x)\cdot B(x)=C(x){\pmod {x^{n+1)))$ $Topor)$ $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},}

Unde denotă derivata funcției în punctul . Pentru a evalua acuratețea algoritmului, se poate estima diferența $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},}

din care rezultă că dacă este divizibil cu (ceea ce echivalează cu faptul că primii coeficienți sunt definiți corect), atunci va fi divizibil cu . Astfel, având în vedere condiția inițială , fiecare iterație dublează numărul de coeficienți definiți cu precizie . Prin urmare, iterațiile sunt suficiente pentru calcul . Aplicarea transformării rapide Fourier la înmulțirea polinoamelor în formula de mai sus conduce la timpul final de rulare , ceea ce îmbunătățește semnificativ estimarea pentru înmulțirea lungă obișnuită [7] . $V_{k}-B$ $x^{t)$ $t$ $V_{k}$ $V_{k+1}-B$ $x^{2t)$ ${\displaystyle V_{0}=b_{0}=a_{0}^{-1))$ $B(x)$ $A(x)^{-1}{\pmod {x^{n+1)}}$ $O(\log n)$ $O(n\log n)$

Exemplu

Lasă și . Datorită ( 4 ), este necesar să se găsească . Polinomul invers se caută după cum urmează: $S(x)=x^{3}-12x^{2}-42$ $T(x)=x-3$ $Q^{R}(x)=(-42x^{3}-12x+1)(-3x+1)^{-1}{\pmod {x^{3)))$ $V(x)=(-3x+1)^{-1}{\pmod {x^{3)))$

Aproximația inițială este definită ca ; ${\textstyle V_{0}={\frac {1}{T^{R}(0)))=1}$
Prima aproximare este definită ca ; $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$
A doua aproximare este definită ca . $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+ 9x^{2}+3x+1$

Datorită proprietăților metodei lui Newton, primii coeficienți sunt determinați corect. Deoarece calculele suplimentare se fac modulo , coeficienții la puteri mai mari pot fi aruncați. De aici $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}}},

în virtutea căreia . $Q(x)=x^{2}-9x-27$

Analiza algoritmilor

Pentru a evalua eficacitatea diferitelor metode, se folosește complexitatea circuitului aritmetic - numărul total de operații de adunare, înmulțire, scădere și împărțire pe câmpul de numere complexe care trebuie efectuate în timpul funcționării algoritmului. Numărul de pași paraleli necesari pentru implementarea algoritmului multiprocesor este de asemenea estimat, presupunând că fiecare procesor la orice pas poate efectua nu mai mult de o operație [7] .

Fiecare iterație a algoritmului de împărțire constă în scăderea offset-ului cu o anumită sumă din , ceea ce se poate face în . Deoarece gradul , inițial egal cu , scade până când devine mai mic decât , timpul total de rulare al algoritmului poate fi estimat ca , unde [2] . $T(x)$ $S x)$ $Pe)$ $S x)$ $m$ $n$ $O(kn)$ $k=mn$

Vezi și

teorema lui Bezout
regula lui Ruffini
baza Gröbner
polinoame
Diviziune sintetică

Note

↑ Skanavi M. I. Matematică elementară. - Ed. a II-a, revizuită. si suplimentare - M . : Nauka, 1972. - S. 142-147. — 592 p.
↑ 1 2 3 4 5 6 7 Bini, Pan, 1986 , p. 184-186
↑ 12 Knuth , 1997 , pp. 420-421
↑ Knuth, 1997 , pp. 525-533
↑ Sieveking, 1972
↑ Kung, 1974
↑ 1 2 Bini, Pan, 1986 , pp. 186-188

Literatură

Bini D., Pan V. Polynomial division and its computational complexity (engleză) // 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. The Art of Computer Programming (engleză) : Seminumerical Algorithms - 3 - Addison-Wesley , 1997. - Vol. 2. - 784 p. — ISBN 978-0-201-89684-8
Kung H. T. Despre calculul reciprocelor serii de putere (engleză) // Numer. Math / F. Brezzi - Springer Science + Business Media , 1974. - Vol. 22, Iss. 5. - P. 341-348. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01436917
Sieveking M. An algorithm for division of powerseries (engleză) // 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 (engleză) // Algorithms Seminar, 2000-2001 / F. Chyzak - Institut National de Recherche en Informatique en Informatique et en Automatique , 2001. - P. 81-84. — 197p.