PDF de programación - Programación: División sintética de un polinomio entre un binomio mónico

División de un polinomio entre un binomio mónico

Programación:

Objetivos. Escribir una función que divida un polinomio entre un binomio mónico. Vamos
a usar esta función en otras partes del curso. En este texto estamos suponiendo que los
índices de arreglos empiezan desde 1.

Requisitos. Ciclos, multiplicación de un polinomio por un binomio, representación de
listas (arreglos), representación de polinomios.

El algoritmo que vamos a estudiar tiene varios nombres: división sintética, algoritmo de
Horner, regla de Ruffini.

1. Guardar polinomios como listas de coeficientes en el orden ascendente. Como
antes, representamos polinomios como listas de sus coeficientes, empezando con el término
independiente. Por ejemplo, representamos el polinomio

f(x) = 5x3 − 7x2 + 1

como la siguiente lista:

,

,

El grado de este polinomio es
, y la lista de coeficientes es de longitud
Se dice que −7 es el coeficiente de la potencia

, 5.

.

?

?

?

?

?

.

x?



,

, . . . ,

En general, un polinomio a1 + a2x + a3x2 + . . . + anxn−1 se guarda como la lista de sus
coeficientes:

,
Si an = 0, entonces el grado del polinomio es
y la longitud de la lista de coeficientes es
Para cada índice k ∈ {1, . . . , n}, el número ak es el coeficiente de la potencia

?
.

,

.

.

?

?

?

?

?

Programación: División de un polinomio entre un binomio mónico, página 1 de 6

x?

Fórmulas para dividir un polinomio entre un binomio mónico
(se recomienda deducirlas antes de la clase práctica)

2. Polinomios mónicos (repaso). Un polinomio de una variable se llama mónico el
coeficiente de la mayor potencia en este polinomio es igual a 1. Por ejemplo, el polinomio
4 − 6x + x2 es mónico, y 7 − 5x − 4x2 no lo es.

3. Caso n = 5, construimos un sistema de ecuaciones. Vamos a dividir f(x) entre
g(x), donde f(x) es un polinomio de grado 4 y g(x) es un binomio mónico:

f(x) = a1 + a2x + a3x2 + a4x3 + a5x4,

g(x) = −b + x.

Dividir f(x) entre (x − b) significa encontrar un polinomio q(x) y un número r tales que

f(x) = (x − b)q(x) + r.

De la fórmula (x − b)q(x) = f(x) − r concluimos que

el producto (x − b)q(x) debe ser del mismo grado que f(x), esto es, de grado
Por eso el polinomio q(x) debe ser de grado

.

?

Denotemos sus coeficientes por c1, c2, c3, c4 y obtenemos la siguiente ecuación:

?

a1 + a2x + a3x2 + a4x3 + a5x4 = (−b + x)(c1 + c2x + c3x2 + c4x3) + r.

Igualamos los coeficientes de las potencias de x en ambos lados:

.

(1)

(2)

(3)

(4)

(5)

coeficiente de x0 :

coeficiente de x1 :

x2 :

x3 :

x4 :

a?

a?



a?

a?

?

=
=
=
=
=

?

?



?

?

;

?

;

+



.

;

;

Las incógnitas de este sistema de ecuaciones son c1, c2, c3, c4, r.

a?

?

Programación: División de un polinomio entre un binomio mónico, página 2 de 6

4. Caso n = 5, resolvemos el sistema de ecuaciones.
Estamos resolviendo el sistema de ecuaciones (1)–(5).

La



primera/última

ecuación del sistema tiene solamente una incógnita,

.

(6)



?

?

y esta incógnita ya está en la forma despejada:



=

,

?

,

c?

c?

c?

a?

a?

, etc.:

y

Ahora de la ecuación (
esto es, expresarla en términos de
Luego de la ecuación



) podemos despejar otra incógnita
,
despejamos
=
=
=
=

c?

c?

c?

?

?

;

c4 +



+
+
+

?

?

?

?

;

;

?

?

?

.

(7)

(8)

(9)

(10)

?

?

?

?

Aunque sabemos el valor de la incógnita c4, no lo sustituimos en (7).
De manera similar, en (8) dejamos c3, etc.
Por supuesto, para n = 5 podríamos escribir c4, c3, . . . en términos de a1, . . . , a5 y b,
pero las fórmulas serían complicadas y no podríamos generalizarlas.
Preferimos escribir fórmulas recursivas porque son cómodas para generalizar y programar.

Notemos que las fórmulas (7), (8) y (9) tienen la misma estructura:

ck =



,

k = 3,

,

.

(11)

Las fórmulas (6) y (10) tienen otras expresiones en el lado izquierdo o en el lado derecho.

?

?

?

Programación: División de un polinomio entre un binomio mónico, página 3 de 6

5. Fórmulas para n general.
Ahora vamos a dividir f(x) entre g(x), donde f(x) es de grado n−1 y g(x) es un polinomio
mónico:

f(x) = a1 + a2x + a3x2 + . . . + anxn−1,

g(x) = −b + x.

Buscamos un polinomio q(x) y un número r tales que

El polinomio q(x) es de grado

f(x) = (−b + x)q(x) + r.

, es decir, tiene

coeficientes.

Se debe cumplir la siguiente igualdad de polinomios:

?

?

(−b + x)(c1 + c2x + . . . + cn−1xn−2) + r = a1 + a2x + a3x2 + . . . + anxn−1.

Generalizando los resultados del Ejercicio 4 se puede ver que los coeficientes incógnitos
c1, . . . , cn−1, r se pueden calcular de la siguiente manera:

;

?

c?


=
ck =


=

?



c?

+


.

?

k =

,

, . . . ,

;

?

?

?

,

?

?

Notemos que ck se expresa en términos de
así que k debe ir en el orden



c?

,



ascendente/descendente

desde



?



hasta



.



?

Programación: División de un polinomio entre un binomio mónico, página 4 de 6

6. Algoritmo divpolbinom (pseudocódigo).

función divpolbinom(a, b):

?

?

;

c?



variables locales: n, c, k;


n :=
c := lista nula de longitud


:=


para k :=
,

ck :=



:=
y
salida:

?

?

?

?

.

?

;



;



?

, . . . ,


;

?

:



;

?

?

7. Ciclos descendentes.

Los “ciclos descendentes” en Matlab o en GNU Octave se puede programar usando el
comando : (dos puntos) e indicando un paso negativo. Se recomienda ejecutar los siguientes
comandos (en Matlab se escribe end en vez de endfor):

for k = 100 : -10 : 60,

disp(k);

endfor

8. Ejemplo de una función en Matlab o GNU Octave que regresa dos objetos.
Se recomienda guardar la siguiente función en un archivo ab.m:

function [p, q] = ab(n),

p = n * n;
q = 7 * ones(n, 1);

endfunction

Luego se pueden hacer pruebas desde el intérprete:

ab(4)
[p, q] = ab(4)

Programación: División de un polinomio entre un binomio mónico, página 5 de 6

Programación de la división de un polinomio entre un binomio

9. Problema divpolbinom.
Traduzca el Algoritmo 6 a un lenguaje de programación. En otras palabras, escriba una
función que divida un polinomio f(x) entre un binomio x − b. Si se usa el lenguaje
Matlab o GNU Octave, entonces hay que guardar la función divpolbinom en el archivo
divpolbinom.m.

Entrada: el arreglo a de los coeficientes de f(x) y el número b.

Salida: el arreglo de los coeficientes del cociente y el residuo.

10. Comprobación. Es fácil ver que −11 + 8x − 5x2 + x3 = (−4 + x)(4 − x + x2) + 5.
Por eso [c, r] = divpolbinom([-11; 8; -5; 1], 4) debe regresar [4; -1; 1] y 5.

11. Comprobación. Divida el polinomio 2x3 − 5x2 + x − 7 entre el binomio x + 3 (haga
los cálculos en papel). Luego ejecute [c, r] = divpolbinom([-7; 1; -5; 2], -3).

12. Problema poleval.
Escriba una función que calcule el valor del polinomio f(x) con coeficientes dados en el
punto dado b. Sugerencia: haga una copia del programa divpolbinom y modifique el