División de polinomios

La división de polinomios es la operación de división con resto en el anillo euclidiano de polinomios en una variable sobre algún campo . El algoritmo ingenuo que implementa esta operación es una forma generalizada de división de columnas , que se implementa fácilmente de forma manual.

Para cualquier polinomio y , , existen polinomios únicos y tales que $f(x)$ $g(x)$ $g(x) \ne 0$ $q(x)$ $r(x)$

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

y tiene un grado menor que . $r(x)$ $g(x)$

El propósito de los algoritmos de división de polinomios es encontrar el cociente y el resto de un divisor divisible y distinto de cero [1] . $q(x)$ $r(x)$ $f(x)$ $g(x)$

Planteamiento del problema

El problema de dividir polinomios con resto se puede formular en las siguientes formulaciones equivalentes [2] .

Cociente y resto

Los polinomios de grado y grado están dados por sus coeficientes. Es necesario encontrar el cociente y el resto tal que [2] ${\displaystyle S(x)=s_{0}+s_{1}x+\dots +s_{m}x^{m))$ $metro$ ${\displaystyle T(x)=t_{0}+t_{1}x+\dots +t_{n}x^{n))$ $norte$ $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))$

{\ estilo de visualización S (x) = T (x) Q (x) + R (x).}

(una)

Los polinomios así definidos y son únicos - si suponemos que la ecuación ( 1 ) tiene dos soluciones y , entonces $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),

de donde se sigue que o , lo que también implica , o el grado no es menor que el grado , lo cual es imposible por definición [3] . $Q_{1}(x)=Q_{2}(x)$ $R_{1}(x)=R_{2}(x)$ $R_{1}(x)-R_{2}(x)$ $T(x)$ $R(x)$

Ajuste de matriz

Este problema se puede reescribir en forma matricial, si asumimos que y se dan , y necesitamos calcular tal que [ 2] ${\displaystyle s_{0},s_{1},\puntos,s_{m))$ ${\displaystyle t_{0},t_{1},\puntos,t_{n))$ ${\displaystyle q_{0},q_{1},\dots,q_{mn))$ ${\displaystyle r_{0},r_{1},\puntos,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 & \puntos &t_{n-1}&t_{n}\\\puntos &\puntos &t_{n-2}&t_{n-1}\\\vpuntos &\dpuntos &\vpuntos &\vpuntos \\0&\puntos &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)

Matriz inversa de Toeplitz

Debido a que , para resolver el problema, basta encontrar por las primeras ecuaciones del sistema . Si consideramos solo estas ecuaciones, el problema se convierte en $R(x)=S(x)-T(x)Q(x)$ ${\displaystyle q_{mn},\puntos,q_{0))$ $m-n+1$

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

(3)

La matriz de este sistema de ecuaciones es triangular inferior y Toeplitz , compuesta por coeficientes principales y ceros, y la solución del sistema equivale a encontrar su inversa [2] . ${\ estilo de visualización T (x)}$

Módulo del polinomio inverso

Sean y polinomios obtenidos de y al invertir la secuencia de coeficientes. El sistema de ecuaciones ( 3 ) se puede formular como $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))},

donde , y significa que los residuos después de dividir los polinomios y por son iguales. La división de un polinomio por se puede representar como , por lo que el resto es igual al polinomio obtenido de los primeros coeficientes , es decir, $k=m-n+1$ ${\bmod {x}}^{mn}$ ${\ estilo de visualización 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}.

Si se conocen los polinomios y , entonces , ¿dónde está el polinomio inverso en el anillo de residuos módulo . Por lo tanto, la búsqueda puede reducirse a encontrar , tal que ${\ estilo de visualización 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+\puntos +v_{k}x^{k))$

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

(cuatro)

Esta formulación también permite encontrar la matriz inversa en el sistema ( 3 ):

Sea la matriz de tamaño de ( 3 ). Entonces es una matriz Toeplitz triangular inferior, cuya primera columna es , donde están los coeficientes de ( 4 ). $T$ $k$ $T^{-1}$ ${\begin{bmatrix}v_{k-1}&v_{k-2}&\dots &v_{0}\end{bmatrix}}^{T}$ $v_{0},\puntos,v_{k-1}$ $V(x)$

Prueba

El sistema ( 3 ) es equivalente a la ecuación . En consecuencia, el sistema ${\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} &\puntos &v_{mn-1}&v_{mn}\end{bmatrix}}{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{ bmatriz}}={\begin{bmatriz}q_{mn}\\\vdots \\q_{1}\\q_{0}\end{bmatriz}}

se puede representar como , que en el caso ( 4 ) es equivalente al sistema ( 3 ). ■ ${\displaystyle V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k))))$

Debido a la arbitrariedad del polinomio que define los elementos , este hecho nos permite encontrar la inversa de una matriz triangular inferior arbitraria de Toeplitz [2] . $T(x)$ $T$

Serie de potencia formal

La ecuación se puede ver no sólo en módulo , sino también como una igualdad en el anillo de series formales de potencia . Sean y series de potencias formales coincidentes con los polinomios y . Si en tales términos encontramos la serie formal $S^{R}(x)=T^{R}(x)Q^{R}(x)$ $x^{mn}$ ${\ estilo de visualización s (x)}$ $t(x)$ ${\ estilo de visualización S ^ {R} (x)}$ $T^{R}(x)$

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

(5)

entonces sus coeficientes a potencias más bajas corresponderán al polinomio requerido . Este enfoque también nos permite considerar el problema ( 2 ) como un sistema con una matriz de Toeplitz infinitamente extendida y una columna infinitamente extendida , en la que se excluye la columna de residuos . Resolver las primeras filas de dicho sistema dará los primeros coeficientes de la serie , a saber . Al mismo tiempo, trabajar con series de potencias en general, en las que solo interesan los primeros coeficientes de la serie (por ejemplo, debido a la memoria disponible limitada), es equivalente a trabajar con polinomios, cuyas operaciones se realizan en el módulo anillo de residuos [4] . En particular, la búsqueda de los primeros coeficientes equivale a resolver la ecuación [2] . $m-n+1$ $Q^{R}(x)$ $q$ $r$ $h$ $h$ $q(x)$ $q_{mn},q_{mn-1},\dots,q_{mn-h+1}$ $h$ ${\ estilo de visualización x ^ {h}}$ $h$ $q(x)$ ${\displaystyle s(x)\equiv t(x)q(x){\pmod {x^{h))))$

Métodos de solución

División de columnas

En el curso del algoritmo, los coeficientes a potencias más altas se ponen a cero secuencialmente al restar multiplicado por alguna potencia con coeficientes, que luego forman el cociente . Inicialmente, el coeficiente se determina igual a . Si ampliamos , entonces $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).

Reemplazando , esta ecuación toma la forma $S'(x)=S(x)-q_{mn}x^{mn}T(x)$

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

similar a la ecuación ( 1 ). En este caso, el coeficiente th , por definición , es igual a , por lo que el grado será menor que el grado . El procedimiento se repite hasta que el grado sea menor que el grado , lo que significará que el siguiente es igual a él [3] . $metro$ ${\ estilo de visualización S' (x)}$ ${\ Displaystyle q_ {mn}}$ ${\ estilo de visualización 0}$ ${\ estilo de visualización S' (x)}$ $S(x)$ ${\ estilo de visualización S' (x)}$ $T(x)$ ${\ estilo de visualización S' (x)}$ $R(x)$ $Q'(x)=0$

Ejemplo

Sea y . Para polinomios dados, la división de columnas por se puede escribir como $S(x)=x^{3}-12x^{2}-42$ ${\ estilo de visualización T (x) = x-3}$ $S(x)$ $T(x)$

{\begin{matriz}{rr}-{\begin{matriz}{llll}x^{3}&-12x^{2}&{\color {blanco}+0x}&-42\\x ^{3}&-3x^{2}&&\\\hlínea \end{matriz}}&{\begin{matriz}{|l}x-3\\\hlínea x^{2}-9x-27\ end{matriz}}\\-{\begin{matriz}{lll}-9x^{2}&&-42\\-9x^{2}&+27x&\\\hline \end{matriz}}&\\ -{\begin{matriz}{ll}-27x&-42\\-27x&+81\\\hlínea \end{matriz}}&\\-123\end{matriz}}

De este modo,

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

es decir, el polinomio es un cociente y a es el resto. $Q(x)=x^{2}-9x-27$ $R(x)=-123$

Algoritmo de tamizado-Kohn

En 1972, Malte Zieveking propuso un algoritmo para encontrar una solución a una ecuación dada y [5] . En 1974 , Kong Xiangzhong mostró que para , el algoritmo es una iteración del método de Newton para [6] . Con este enfoque, la iteración toma la forma $B(x)$ ${\displaystyle A(x)\cdot B(x)=C(x){\pmod {x^{n+1))))$ $Hacha)$ $C(x)$ ${\ estilo de visualización 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},}

Donde denota la derivada de la función en el punto . Para evaluar la precisión del algoritmo, se puede estimar la diferencia ${\displaystyle f'(V_{k})=-V_{k}^{-2))$ ${\ estilo de visualización f (V)}$ $V_{k}$

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

de donde se sigue que si es divisible por (lo que equivale a que los primeros coeficientes estén bien definidos), entonces será divisible por . Así, dada la condición inicial , cada iteración duplica el número de coeficientes definidos con precisión . Por lo tanto, las iteraciones son suficientes para el cálculo . La aplicación de la transformada rápida de Fourier a la multiplicación de polinomios en la fórmula anterior conduce al tiempo de ejecución final , lo que mejora significativamente la estimación para la multiplicación larga habitual [7] . $V_{k}-B$ ${\ estilo de visualización x ^ {t}}$ $t$ $V_{k}$ $V_{k+1}-B$ ${\ estilo de visualización 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)$

Ejemplo

Sea y . Debido a ( 4 ), es necesario encontrar . El polinomio inverso se busca de la siguiente manera: $S(x)=x^{3}-12x^{2}-42$ ${\ estilo de visualización 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))))$

La aproximación inicial se define como ; ${\textstyle V_{0}={\frac {1}{T^{R}(0)))=1}$
La primera aproximación se define como ; $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$
La segunda aproximación se define como . $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+ 9x^{2}+3x+1$

Debido a las propiedades del método de Newton, los primeros coeficientes se determinan correctamente. Dado que los cálculos adicionales se realizan en módulo , los coeficientes a potencias más altas pueden descartarse. De aquí $2^{2}=4$ ${\ Displaystyle 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}}},

en virtud del cual . $Q(x)=x^{2}-9x-27$

Análisis de algoritmos

Para evaluar la efectividad de varios métodos, se utiliza la complejidad del circuito aritmético : el número total de operaciones de suma, multiplicación, resta y división sobre el campo de números complejos que deben realizarse durante la operación del algoritmo. También se estima el número de pasos paralelos requeridos para la implementación multiprocesador del algoritmo, asumiendo que cada procesador en cualquier paso no puede realizar más de una operación [7] .

Cada iteración del algoritmo de división consiste en restar el desplazamiento por alguna cantidad de , lo que se puede hacer en . Dado que el grado , inicialmente igual a , disminuye hasta que se vuelve menor que , el tiempo total de ejecución del algoritmo se puede estimar como , donde [2] . $T(x)$ $S(x)$ $En)$ $S(x)$ $metro$ $norte$ ${\ Displaystyle O (kn)}$ $k=mn$

Véase también

teorema de bezout
la regla de Ruffini
base de Gröbner
polinomios
División sintética

Notas

↑ Skanavi M. I. Matemáticas elementales. - 2ª ed., revisada. y adicional - M. : Nauka, 1972. - S. 142-147. — 592 pág.
↑ 1 2 3 4 5 6 7 Bini, Pan, 1986 , págs. 184-186
↑ 12 Knuth , 1997 , págs. 420-421
↑ Knuth, 1997 , págs. 525-533
↑ Tamizado, 1972
↑ Kung, 1974
↑ 1 2 Bini, Pan, 1986 , págs. 186-188

Literatura

Bini D., Pan V. División polinomial y su complejidad computacional (inglés) // Journal of Complexity - Elsevier BV , 1986. - vol. 2, edición. 3.- Pág. 179-203. — ISSN 0885-064X ; 1090-2708 - doi:10.1016/0885-064X(86)90001-4
Knuth D. El arte de la programación informática (inglés) : algoritmos seminuméricos - 3 - Addison-Wesley , 1997. - vol. 2. - 784 pág. — ISBN 978-0-201-89684-8
Kung H. T. Sobre el cálculo de recíprocos de series de potencias (inglés) // Numer. Matemáticas / F. Brezzi - Springer Science + Business Media , 1974. - Vol. 22, edición. 5.- Pág. 341-348. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01436917
Sieveking M. Un algoritmo para la división de powerseries (inglés) // Informática - Springer Science + Business Media , 1972. - Vol. 10, edición. 1-2. - Pág. 153-156. — ISSN 0010-485X ; 1436-5057 - doi:10.1007/BF02242389
Schönhage A. Variaciones sobre el cálculo de recíprocos de series de potencias (inglés) // Seminario de algoritmos, 2000-2001 / F. Chyzak - Institut National de Recherche en Informatique en Informatique et en Automatique , 2001. - P. 81-84. — 197p.