PDF de programación - Programación: Construcción del polinomio mónico de grado mínimo con raíces dadas

Programación: Construcción del polinomio
mónico de grado mínimo con raíces dadas

Objetivos. Escribir una función que calcule los coeficientes del polinomio mónico de
grado mínimo que tengas las raíces dadas.

Requisitos. Multiplicación de un polinomio por un binomio mónico, evaluación de un
polinomio en un arreglo de puntos, teorema del resto y sus corolarios.

Revisamos los requisitos

1. Representación de polinomios como arreglos de sus coeficientes (repaso).
Por ejemplo, representamos el polinomio 3x4 − 7x3 − 2x + 6 como [6; -2; 0; -7; 3].

2. Multiplicación de un polinomio por un binomio mónico (repaso). En clases
pasadas programamos una función mulpolbinom que multiplica un polinomio (dado por
el arreglo de sus coeficientes) por un binomio de la forma x + b dado por el número b.
Por ejemplo,

mulpolbinom([-2; 0; 6; 1; 5], 3) regresa [-6; -2; 18; 9; 16; 5].

3. Evaluación de un polinomio en un arreglo de puntos (repaso). En clases
pasadas programamos un función poleval que evalúa un polinomio (dado por el arreglo de
sus coeficientes) en un arreglo de puntos y regresa el arreglo de los valores correspondientes.
Por ejemplo,

poleval([-5; 3; 4; -2], [3; -2; 4]) regresa [-14; 21; -57].

Polinomio con raíces dadas: idea
4. Dados algunos puntos a1, a2, a3, a4 ∈ R, el polinomio

4

f(x) =

(x − aj) = (x − a1)(x − a2)(x − a3)(x − a4)

j=1

tiene raíces a1, a2, a3, a4 y es mónico. Si algunos de los puntos a1, a2, a3, a4 coinciden,
entonces son raíces múltiples de f. Por ejemplo, si a1 = a2, pero a1 = a3 y a1 = a4,
entonces

(x − a1)3 f(x).
Además f es el polinomio de grado mínimo con estas propiedades.

(x − a1)2 | f(x),

pero

Programación: Construcción del polinomio con raíces dadas, página 1 de 4

5. Fórmula general. Sean a1, . . . , an algunos números. Entonces el polinomio mónico
de grado mínimo con raíces a1, . . . , an es

???

f(x) =

(??? − ???).

j=???

6. Definición natural del producto vacío. Los productos
diante la fórmula recursiva

n+1

???



ck =

???

c???

k=1

k=1



(1)

se pueden definir me-

(2)

Queremos que esta fórmula sea correcta no solamente para n = 1, 2, 3, . . ., sino también
en el caso n = 0. Calculamos el lado izquierdo y el lado derecho en este caso:

L.I. =

, L.D. =

.

Para garantizar la igualdad L.I. = L.D. (para cada c1), ponemos

0

ck =

?

.

(3)

k=1

7. El caso de 0 puntos.

¿Qué polinomio está determinado por el lado derecho de (1) en el caso n = 0?

¿Cuál es el polinomio mónico de grado mínimo que no tiene raíces?

Estas dos preguntas tienen la misma respuesta, la cual nos ayuda iniciar bien el proceso
iterativo (el ciclo for) que realiza la fórmula (1).

8. Fórmulas iterativas. Sean a1, a2, a3, a4 algunos números dados. Calculamos por
pasos el polinomio (x − a1)(x − a2)(x − a3)(x − a4).

Empezamos con el polinomio neutro multiplicativo: f0(x) := 1x0.

Calculamos f1(x) como el producto del polinomio f0(x) por el binomio (x − a1).

f2(x) := f1(x)(x − a2).

f3(x) :=.

f4(x) :=.

Programación: Construcción del polinomio con raíces dadas, página 2 de 4

9. Cálculo del polinomio con raíces dadas, ejemplo. Constuir el polinomio mónico
de grado mínimo con raíces

Solución. Hay que calcular el producto de binomios

−2,

3,

3,

5.

f(x) = 1 · (x + 2) · (x − 3) · (x − 3) · (x − 5).

Usamos el algoritmo de multiplicación de un polinomio por un binomio:

1

2

1

2

− 3

− 5 −90

1

Respuesta:

f(x) = −90 + 33x + 17x2 − 9x3 + x4.

10. El polinomio constante 1. El polinomio 1x0 representamos como el arreglo [1]. En
algunos lenguajes de programación es lo mismo que el número 1, en otros lenguajes 1 y
[1] son objetos diferentes.

11. Programar una función que calcule los coeficientes del polinomio mónico
de grado mínimo que tenga raíces dadas. Escribir una función polfromroots de un
argumento vectorial a que calcule los coeficientes del polinomio

n

(x − aj),

j=1

donde denotamos la longitud de a por n. Usamos un ciclo for y la función mulpolbinom:

function [c] = polfromroots(a),

n = length(a);
c = ???;
for j = 1 : n,

??? = mulpolbinom(???, ???);

end

end

Programación: Construcción del polinomio con raíces dadas, página 3 de 4

12. Complejidad del algoritmo polfromroots. Calcular el número de operaciones de
multiplicación que se realizan en el algoritmo anterior, si el arreglo a tiene longitud n.
Recordamos que al ejecutar mulpolbinom(p, q), donde p es de longitud m, se realizan
m operaciones de multiplicación. Respuesta:

n



=

.

j=1

?

13. Una prueba pequeña de la función polfromroots. Hacemos una prueba de la
función polfromroots en el intérprete de GNU Octave, usando los datos del Ejemplo 9:

f = polfromroots([-2; 3; 3; 5])

La respuesta debe coincidir con la respuesta que calculamos a mano en el Ejemplo 9.
También verificamos que el polinomo f se anula en los puntos −2, 3, 3, 5:

poleval(f, [-2; 3; 3; 5])

14. Pruebas pseudoaleatorias de la función polfromroots. Guardamos la siguiente
función en un archivo con título testpolfromroots.m:

function [] = testpolfromroots(n, nrep),

rootsbase = randn(n, nrep);
maxerror = 0;
t1 = cputime();
for rep = 1 : nrep,

a = rootsbase(:, rep);
f = polfromroots(a);
v = poleval(f, a);
error = norm(v);
maxerror = max(error, maxerror);

end
t2 = cputime();
disp(t2 - t1);
disp(maxerror);

end

En el intérprete de GNU Octave ejecutamos

testpolfromroots();

Programación: Construcción del polinomio con raíces dadas, página 4 de 4