Estimad@ lector/a,
muy probablemente recordarás con cierto estupor aquellas soporíferasclases de matemáticas en los primeros años de la educación secundariadedicadas a la división de polinomios.Estoy seguro de que tu gusto por las matemáticas no se debeprecisamente a la división de polinomios. ¡Cuánto tiempo dedicado amultiplicar y dividir potencias de la variable independiente x! ¡Yaquellos fastidiosos cambios de signo en los coeficientes! Recordarásademás aquella estupenda regla de Ruffini (tambiénconocida como algoritmo de Horner) que, entre otras muchas cosas,permitía realizar de modo inmediato divisiones de polinomios en las queel polinomio divisor era de grado uno.
Con este algoritmo tan maravilloso a nuestra disposición, es muy probable que tú mism@ te preguntaras por qué no se nos facilitaba en clase un algoritmo similar para realizar las tediosas divisiones de polinomiossin tener que recurrir a las potencias de la dichosa variable x y a losincordios cambios de signo en los coeficientes que surgen en elalgoritmo usual de la división. ¡Cuántas veces habremos cometidoerrores inocentes en este proceso, echando al traste parte del trabajorealizado anteriormente!
Con este artículo pretendemos que aprendas a dividir polinomios engeneral por medio de un método algorítmico que generaliza de modonatural la regla de Ruffini.
A modo de ejemplo introductorio consideremos la división (2x3-x2+x-5):(x+2) (cociente de grado 2 y resto de grado 0) por medio de la regla de Ruffini
que, como es sabido, nos da un cociente C(x)=2x2-5x+11 y un resto R(x)=-27.
Pues bien, presentamos ahora un algoritmo general al estilo de la regla de Ruffini que permite realizar divisiones de polinomios cualesquiera con un costo computacional bajo.
Antes de justificar teóricamente el algoritmo general, presentamoscinco ejemplos como ilustración del algoritmo. En todo momentoasumiremos, sin pérdida de generalidad, que el polinomio divisor tienecoeficiente director igual a 1 (en otro caso, bastaría con dividirtodos los coeficientes del polinomio dividendo y del polinomio divisorpor el valor de dicho coeficiente).
Aconsejamos la realización paso a paso de las tablasque aparecen abajo para una mejor comprensión del algoritmo. Si sesimultanea la realización de las tablas con el proceso de división depolinomios usual se entenderá la relación que existe entre el procesousual y las diagonales inversas de las tablas.
Tal vez los detalles que sean de mayor complejidad en la configuraciónde las tablas son las posiciones nulas (cuadros negros) que aparecen enlas mismas. En general, a la hora de configurar las tablas paradesarrollar el algoritmo de división, notaremos que si el divisor tienegrado k+1, con k≥0, entonces deben ubicarse k(k+1) posiciones vacías (o nulas), separadas simétricamente en dos grupos triangulares de k(k+1)/2cuadros, que no deben tenerse en cuenta a la hora de realizaroperaciones en la tabla. En particular, si el divisor es de grado 1entonces no se insertarán posiciones vacías en la tabla. La realizaciónde las divisiones por el proceso usual nos hace ver por qué debenaparecer estas posiciones nulas en las tablas.
Ejemplo 1: Dividir (3x2-4x+1):(x2-3x+2)
Sabemos a priori que el proceso nos conducirá a un resto de grado 1 y a un cociente de grado 0.
Formamos entonces una tabla al estilo Ruffini, en cuya fila superior secolocan los coeficientes del dividendo (de mayor grado a menor grado) yen cuya primera columna se colocan los coeficientes del divisorcambiados de signo (de menor grado a mayor grado), exceptuando elcoeficiente director (que vale 1). A continuación se inicia el procesousual de la regla de Ruffini.
En caso de que el grado del divisor sea mayor o igual que 2, notamosque al realizar la tabla quedan posiciones vacías en las primerascolumnas. Estas posiciones deben situarse simétricamente en el tablero(es decir, también habrán posiciones vacías en las últimas columnas detablero) y no deben considerarse a efectos operacionales.
Se comprueba entonces que efectivamente el cociente de la división es C(x)=3 y el resto R(x)=5x-5.
Ejemplo 2: Dividir (x3+x-1):(x2+1)
Sabemos que el proceso nos conducirá a un resto de grado 1 y a un cociente de grado 1.
Colocamos los coeficientes convenientemente en la tabla y realizamos elmismo proceso anterior. Observemos la disposición simétrica de lascasillas nulas en la tabla.
Así, el cociente será C(x)=1x+0=x, y el resto R(x)=0x-1=-1.
Ejemplo 3: Dividir (5x5-4x4+3x3-2x2+x):(x3-7x2+6x-2)
En este caso, el proceso nos conducirá a un resto de grado 2 y a un cociente de grado 2.
Podemos comprobar que efectivamente el resto de la división es R(x)=1152x2-1077x+380, mientras que el cociente viene dado porC(x)=5x2+31x+190.
Ejemplo 4: Dividir (3x5-4x4+2x2-x-1):(x4-3x3+x-2)
El proceso debe conducirnos a un resto de grado 3 y a un cociente de grado 1.
El proceso indica que el cociente es C(x)=3x+5, mientras que el resto viene dado por R(x)=15x3-x2+9.
Ejemplo 5: Dividir (2x7-3x6+x4-x3+2x2-3x+1):(x5-3x4+x2-3x+3)
El algoritmo nos conducirá a un resto de grado 4 y a un cociente de grado 2.
De esta manera el cociente será C(x)=2x2+3x+9, y el resto R(x)=26x4+2x3-4x2+15x-26.
Esperamos que estos ejemplos hayan ilustrado convenientemente elalgoritmo de división. Aún así recomendamos la realización paso a pasode cada una de las tablas que aparecen en los ejemplos. Este algoritmono es nada casual y está basado en un desarrollo de los coeficientesque van apareciendo en cada paso de la división general de polinomiospor el método usual. A continuación justificamos teóricamente elalgoritmo presentado anteriormente. Para ello nos acercaremos alalgoritmo general estudiando previamente los casos en los que eldivisor tiene grado 1, 2 y 3.
En lo que sigue consideramos un polinomio dividendo de grado n de la forma:
p(x)=pnxn+pn-1xn-1+...+p2x2+p1x+p0,
y supondremos, sin pérdida de generalidad, que el polinomio divisor es mónico (coeficiente director igual a 1) y tiene grado k+1, con k≥0:
q(x)=xk+1+qkxk+qk-1xk-1+...+q2x2+q1x+q0,
con la condición de que n≥k+1.
- Divisor de grado 1: q(x)=x+q0.
En este caso, asumimos n≥1, con lo cual se obtiene un cociente de grado n-1 y un resto de grado 0 de la forma:
C(x)=Dnxn-1+Dn-1xn-2+...+D2x+D1
R(x)=D0
Si efectuamos el proceso de división usual, comprobaremos que los coeficientes Dj's se calculan a través de la recurrencia
Dn= pn
Dj= pj - Dj+1*q0, j=n-1, n-2,...,2,1,0,
o equivalentemente
Dn+1=0
Dj= pj - Dj+1*q0, j=n,n-1,...2,1,0. (1)
El algoritmo (1) no es otra cosa sino la regla de Ruffini clásica. Vemos además que su costo computacional se reduce a n productos y n sumas/restas.
- Divisor de grado 2: q(x)=x2+q1x+q0.
En este caso, asumimos n≥2, con lo cual se obtiene un cociente de grado n-2 y un resto de grado 1 de la forma:
C(x)=Dnxn-2+Dn-1xn-3+...+D3x+D2
R(x)=D1x+D0
De nuevo, efectuando la división con coeficientes genéricos comprobamos que los coeficientes Dj's se calculan recursivamente como
Dj= pj - Dj+1*q1 - Dj+2*q0, j=n,n-1,...2,1. (2)
D0= p0 - D2*q0
Este es el algoritmo correspondiente a los ejemplos 1 y 2 anteriores.
La excepción hecha en (2) para el cálculo de D0 (y la aparición de un segundo coeficiente Dn+2 nulo) equivale a las dos (k*(k +1) = 2, sik+1=2) posiciones nulas que aparecen distribuidas simétricamente en la tabla de Ruffini para divisores degrado 2. En este caso la regla nos da un costo computacional de 2*(n-1) sumas y productos.
- Divisor de grado 3: q(x)=x3+q2x2+q1x+q0.En este caso, asumimos n≥3, con lo cual se obtiene un cociente de grado n-3 y un resto de grado 2 de la forma:C(x)=Dnxn-3+Dn-1xn-4+...+D4x+D3
R(x)=D2x2+D1x+D0donde los coeficientes Dj's se calculan recursivamente como:
Dn+1=Dn+2=Dn+3=0
Dj= pj - Dj+1*q2 - Dj+2*q1 - Dj+3*q0, j=n,n-1,...3,2. (3)
D1= p1 - D3*q1 - D4*q0
D0= p0 - D3*q0
Este algoritmo es el que se aplica al ejemplo 3.
La excepción hecha en (3) para el cálculo de D0 y D1 (y la aparición de los coeficientes Dn+2 y Dn+3 nulos) equivale a las seis (k*(k+1)=6, sik+1=3)posiciones nulas que aparecen distribuidas simétricamente en la tablade Ruffini para divisores de grado 3. En este caso la regla nos da uncosto computacional de 3*(n-2) sumas y productos.
Con estos tres casos preliminares vislumbramos el mecanismo general quenos permite calcular los coeficientes del cociente y resto de ladivisión:
- Divisor de grado k+1: q(x)=xk+1+qkxk+qk-1xk-1+...+q2x2+q1x+q0, k≥0.
Ya el lector habrá advertido a partir de los tres casos iniciales queel proceso sigue un patrón común. En este caso se obtendrá un resto degrado k y un cociente de grado n-(k+1), siendo n≥k+1, de la forma:
C(x)=Dnxn-(k+1)+Dn-1xn-(k+2)+...+Dk+2x+Dk+1
R(x)=Dkxk+Dk-1xk-1+...+D2x2+D1x+D0
Otra vez, efectuando la división con coeficientes genéricos comprobamos que los coeficientes Dj's se calculan a través de la recurrencia:
Dn+1=Dn+2=...=Dn+k+1=0
Dj= pj - Dj+1*qk - Dj+2*qk-1 - Dj+3*qk-2-...- Dj+k*q1 - Dj+k+1*q0, j=n,n-1,...k+1,k. (4)
Dk-1= pk-1 - Dk+1*qk-1 - Dk+2*qk-2 -...- D2k-1*q1 - D2k*q0
Dk-2= pk-2 - Dk+1*qk-2 -...- D2k-2*q1 - D2k-1*q0
.....................................................................................................................
D1= p1 - Dk+1*q1 - Dk+2*q0
D0= p0 - Dk+1*q0
En definitiva vemos que para el cómputo de los coeficientes Dj's , con j<k, sólo puede recurrirse a los coeficientes ql, con l<j.
De nuevo, la excepción hecha en (4) para el cálculo de D0, D1, ...,Dk-1 (y la aparición de los coeficientes Dn+2, Dn+3,..., Dn+k+1 nulos) equivale a las k*(k+1) posiciones nulas que aparecen distribuidas simétricamente en la tabla de Ruffini para divisores de grado k+1.
En el caso general la regla nos da un costo computacional de (k+1)*(n-k) sumas y productos.
Concluimos con una propuesta de código (basado en Mathematica) quepermite obtener el cociente y resto de la división de dos polinomios p(x) y q(x)en base al algoritmo anterior.
No hay comentarios:
Publicar un comentario