Dělení polynomů

Divize polynomials je operace divize se zbytkem v Euclidean kruhu polynomials v jedné proměnné přes nějaké pole . Naivní algoritmus, který implementuje tuto operaci, je zobecněná forma dělení sloupců , kterou lze snadno implementovat ručně.

Pro všechny polynomy a , , existují jedinečné polynomy a takové, že $f(x)$ $g(x)$ $g(x) \ne 0$ $q(x)$ $r(x)$

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

a má nižší stupeň než . $r(x)$ $g(x)$

Účelem algoritmů polynomiálního dělení je najít podíl a zbytek pro daného dělitelného a nenulového dělitele [1] . $q(x)$ $r(x)$ $f(x)$ $g(x)$

Prohlášení o problému

Problém dělení polynomů se zbytkem lze formulovat v následujících ekvivalentních formulacích [2] .

Podíl a zbytek

Polynomy stupně a stupně jsou dány jejich koeficienty. Je nutné najít kvocient a zbytek takový, aby [2] ${\displaystyle S(x)=s_{0}+s_{1}x+\tečky +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).

(jeden)

Takto definované polynomy jsou jednoznačné -- pokud předpokládáme , že rovnice ( 1 ) má dvě řešení a , pak $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),

z čehož vyplývá, že buď , což také implikuje , nebo stupeň není menší než stupeň , což je z definice nemožné [3] . $Q_{1}(x)=Q_{2}(x)$ $R_{1}(x)=R_{2}(x)$ $R_{1}(x)-R_{2}(x)$ $T(x)$ $R(x)$

Nastavení matice

Tento problém lze přepsat do maticového tvaru, pokud předpokládáme, že a jsou dány , a potřebujeme vypočítat tak, že [2] ${\displaystyle s_{0},s_{1},\tečky ,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}&\tečky &0&0\\\vtečky &\dtečky &\vtečky &\vtečky \\\tečky &\tečky &t_{n}&0\\\tečky & \tečky &t_{n-1}&t_{n}\\\tečky &\tečky &t_{n-2}&t_{n-1}\\\vtečky &\dtečky &\vtečky &\vtečky \\0&\tečky &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)

Inverzní Toeplitzova matice

Vzhledem k tomu, že k vyřešení problému stačí najít podle prvních rovnic soustavy . Pokud vezmeme v úvahu pouze tyto rovnice, problém se stává $R(x)=S(x)-T(x)Q(x)$ ${\displaystyle q_{mn},\tečky ,q_{0))$ $m-n+1$

{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}t_{n}&\ tečky &0&0\\\vtečky &\dtečky &\vtečky &\vtečky \\\tečky &\tečky &t_{n}&0\\\tečky &\tečky &t_{n-1}&t_{n}\end{bmatrix}} {\begin{bmatrix}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}_{\textstyle .}

(3)

Matice této soustavy rovnic je dolní trojúhelníková a Toeplitzova , složená z vedoucích koeficientů a nul a řešení soustavy je ekvivalentní nalezení její inverzní [2] . $T(x)$

Inverzní polynom modulo

Nechť a být polynomy získané z a obrácením posloupnosti koeficientů. Soustavu rovnic ( 3 ) lze formulovat jako $S^{R}(x)=x^{m}S(x^{-1})=s_{m}+s_{m-1}x+\tečky +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))},

kde , a znamená, že se zbytky po dělení polynomů a tím rovnají. Dělení polynomu může být reprezentováno jako , takže zbytek se rovná polynomu získanému z prvních koeficientů , tj. $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}.

Pokud jsou polynomy a známy, pak , kde je inverzní polynom v kruhu zbytků modulo . Hledání tak může být redukováno na nalezení , takže $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))}.

(čtyři)

Tato formulace také umožňuje najít inverzní matici v systému ( 3 ):

Nechť je matice velikosti z ( 3 ). Pak je nižší trojúhelníková Toeplitzova matice, jejíž první sloupec je , kde jsou koeficienty z ( 4 ). $T$ $k$ $T^{-1}$ ${\begin{bmatrix}v_{k-1}&v_{k-2}&\tečky &v_{0}\end{bmatrix}}^{T}$ $v_{0},\tečky ,v_{k-1}$ $V(x)$

Důkaz

Soustava ( 3 ) je ekvivalentní rovnici . V souladu s tím systém ${\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}&\tečky &v_{mn}&0\\v_{0} &\tečky &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}}

může být reprezentováno jako , což je v případě ( 4 ) ekvivalentní systému ( 3 ). ■ ${\displaystyle V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k))))$

Vzhledem k libovolnosti polynomu definujícího prvky nám tato skutečnost umožňuje najít inverzní hodnotu k libovolné Toeplitzově dolní trojúhelníkové matici [2] . $T(x)$ $T$

Formální mocninná řada

Rovnice může být viděna nejen modulo , ale také jako rovnost v kruhu formálních mocninných řad . Dovolit a být formální mocninné řady shodující se s polynomy a . Pokud v takových termínech najdeme formální řadu $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)

pak jeho koeficienty u nižších mocnin budou odpovídat požadovanému polynomu . Tento přístup nám také umožňuje uvažovat problém ( 2 ) jako systém s nekonečně rozšířenou Toeplitzovou maticí a nekonečně rozšířeným sloupcem , ve kterém je vyloučen sloupec reziduí . Vyřešení prvních řádků takového systému dá první koeficienty řady , totiž . Přitom práce s mocninnými řadami obecně, ve kterých jsou zajímavé pouze první koeficienty řady (například kvůli omezené dostupné paměti), je ekvivalentní práci s polynomy, operace, na kterých se provádějí v modulo kruh zbytků [4] . Zejména hledání prvních koeficientů je ekvivalentní řešení rovnice [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))))$

Metody řešení

Dělení sloupců

V průběhu algoritmu se koeficienty u vyšších mocnin postupně nulují tak, že se od nich odečítají vynásobené nějakou mocninou s koeficienty, které pak tvoří kvocient . Na začátku je koeficient určen rovný . Pokud se rozšíříme , pak $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).

Nahrazením získá tato rovnice tvar $S'(x)=S(x)-q_{mn}x^{mn}T(x)$

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

podobná rovnici ( 1 ). V tomto případě je tý koeficient podle definice roven , takže stupeň bude menší než stupeň . Postup se opakuje, dokud není stupeň menší než stupeň , což bude znamenat, že další se mu rovná [3] . $m$ $S'(x)$ ${\displaystyle q_{mn))$ $0$ $S'(x)$ $S(x)$ $S'(x)$ $T(x)$ $S'(x)$ $R(x)$ $Q'(x)=0$

Příklad

Nechte a . Pro dané polynomy lze dělení sloupců podle zapsat jako $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}}

Takto,

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

to znamená, že polynom je kvocient a a je zbytek. $Q(x)=x^{2}-9x-27$ $R(x)=-123$

Sieveking-Kohnův algoritmus

V roce 1972 navrhl Malte Zieveking algoritmus pro nalezení řešení rovnice pro dané a [5] . V roce 1974 Kong Xiangzhong ukázal, že pro , algoritmus je iterací Newtonovy metody pro [6] . S tímto přístupem má iterace formu $B(x)$ ${\displaystyle A(x)\cdot B(x)=C(x){\pmod {x^{n+1))))$ $Sekera)$ $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},}

Kde označuje derivaci funkce v bodě . Pro vyhodnocení přesnosti algoritmu lze odhadnout rozdíl ${\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},}

z čehož vyplývá, že pokud je dělitelný (což je ekvivalentní tomu, že první koeficienty jsou definovány správně), pak bude dělitelný . Při dané počáteční podmínce tedy každá iterace zdvojnásobí počet přesně definovaných koeficientů . Pro výpočet tedy stačí iterace . Použití rychlé Fourierovy transformace na násobení polynomů ve výše uvedeném vzorci vede ke konečné době běhu , což výrazně zlepšuje odhad pro obvyklé dlouhé násobení [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říklad

Nechte a . Kvůli ( 4 ) je nutné najít . Inverzní polynom se hledá následovně: $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))))$

Počáteční aproximace je definována jako ; ${\textstyle V_{0}={\frac {1}{T^{R}(0)))=1}$
První aproximace je definována jako ; $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$
Druhá aproximace je definována jako . $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+ 9x^{2}+3x+1$

Vzhledem k vlastnostem Newtonovy metody jsou první koeficienty určeny správně. Vzhledem k tomu, že další výpočty se provádějí modulo , mohou být koeficienty při vyšších výkonech vyřazeny. Odtud $2^{2}=4$ $V_{2}(x)$ $x^{3}$

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

na základě kterého . $Q(x)=x^{2}-9x-27$

Analýza algoritmů

Pro hodnocení účinnosti různých metod se používá aritmetický obvod složitost - celkový počet operací sčítání, násobení, odčítání a dělení nad polem komplexních čísel , které je nutné provést při operaci algoritmu. Odhaduje se také počet paralelních kroků potřebných pro víceprocesorovou implementaci algoritmu za předpokladu, že každý procesor v kterémkoli kroku nemůže provést více než jednu operaci [7] .

Každá iterace algoritmu dělení spočívá v odečtení offsetu o nějakou částku od , což lze provést v . Protože stupeň , zpočátku rovný , klesá, dokud není menší než , lze celkovou dobu běhu algoritmu odhadnout jako , kde [2] . $T(x)$ $S(x)$ $Na)$ $S(x)$ $m$ $n$ $O(kn)$ $k=mn$

Viz také

Bezoutova věta
Ruffiniho pravidlo
Gröbnerův základ
polynomů
Syntetické dělení

Poznámky

↑ Skanavi M. I. Elementární matematika. - 2. vyd., přepracováno. a doplňkové - M .: Nauka, 1972. - S. 142-147. — 592 s.
↑ 1 2 3 4 5 6 7 Bini, Pan, 1986 , str. 184-186
↑ 12 Knuth , 1997 , s. 420-421
↑ Knuth, 1997 , pp. 525-533
↑ Sieveking, 1972
↑ Kung, 1974
↑ 1 2 Bini, Pan, 1986 , pp. 186-188

Literatura

Bini D., Pan V. Polynomial division and its computational complexity (anglicky) // 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 (anglicky) : Seminumerical Algorithms - 3 - Addison-Wesley , 1997. - Vol. 2. - 784 s. — ISBN 978-0-201-89684-8
Kung H. T. On computing reciprocal of power series (anglicky) // Numer. Matematika / F. Brezzi - Springer Science + Business Media , 1974. - Sv. 22, Iss. 5. - S. 341-348. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01436917
Sieveking M. Algorithm for division of powerseries (anglicky) // 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 (anglicky) // Algorithms Seminar, 2000-2001 / F. Chyzak - Institut National de Recherche en Informatique en Informatique et en Automatique , 2001. - S. 81-84. — 197p.