Clase 2

Algoritmo de Horner: evaluación de polinomios

El algoritmo de Horner es un algoritmo reconocido por su eficiencia para evaluar polinomios

utilizando un número mínimo de operaciones (sumas y productos).

21
Para fijar ideas veamos un ejemplo. Consideremos
p(x) = 2 + 4x − 5x2 + 2x3 − 6x4 + 8x5 + 10x6

20
Primero notemos que, dado x, el método usual para evaluar xk requiere (k − 1) productos:
xk = x| · .{z
. . · }x,

F
k
por ejemplo, si k = 2, se requiere 1 producto, si k = 3, se requieren 2 productos, etc.

A
Método 1: evaluar las potencias de la manera usual, multiplicar por la constante respectiva
y sumar los monomios. Es fácil ver que se requieren:

0+1+2+3+4+5+6 = ∑ i =
6
M 6(6 + 1)
2
= 21 productos, y por lo tanto, se tienen
A
i=1

# sumas = 6
-F

# productos = 21
Método 2: la idea consiste en evaluar las potencias de x en forma sucesiva:
o

x2 = x ∗ x, x3 = x ∗ x2 , x4 = x ∗ x3 , x5 = x ∗ x4 , x6 = x ∗ x5 ,
ic

teniendo en cuenta que cada potencia de x se debe multiplicar por un coeficiente, se tienen
0 + 1 + 2 + 2 + 2 + 2 + 2 = 11 productos, y por lo tanto
ér

# sumas = 6
# productos = 11
um

Método 3: conocido como método de Horner o multiplicación encajada. La idea consiste en

reescribir convenientemente el polinomio p(x) de modo de reducir el número de productos:

p(x) = 2 + x(4 + x(−5 + x(2 + x(−6 + x(8 + x · 10))))).

.N

Es fácil ver que ahora se requieren:

# sumas = 6
A

# productos = 6
Si el grado de p(x) es n, se requieren n(n + 1)/2 productos en el método 1, 2n − 1 en el
método 2 y sólo n en el método 3.
Si p(x) = a0 + a1 x + a2 x2 + · · · + an xn , con an 6= 0, la evaluación de p(x) en x = z se realiza
con los siguientes pasos:
bn−1 = an
bn−2 = an−1 + z ∗ bn−1
..
.
b0 = a1 + z ∗ b1
p(z) = a0 + z ∗ b0 .

1
 En forma más compacta, podemos escribir:

Algoritmo de Horner (multiplicación encajada)

Dados el polinomio p(x), de grado n, con coeficientes ai , para i = 0, . . . n, con an 6= 0 y un

número real z en el que se desea evaluar p(x).

21
input n; ai , i = 0, . . . , n; z
bn−1 ← an

20
for k = n − 1 to 0 step −1, do
bk−1 ← ak + z ∗ bk

F
end do

A
output bi , i = −1, . . . , n − 1
end
Notar que b−1 = p(z) M
A
-F

Fuentes de error y aritmética de la computadora

Una de las tareas más importantes en Análisis Numérico es estimar la precisión del resultado
en un cálculo numérico.
o

Los resultados numéricos están influenciados por diferentes tipos de errores. Algunos de
ic

estos pueden eliminarse, en otros se puede reducir su influencia, y otros son inevitables y
nada se puede hacer.
ér

Principales fuentes de error.

um

1. Errores en los datos de entrada (frecuentemente inevitables). Los datos de entrada

pueden ser el resultado de mediciones experimentales que podrían estar afectadas a
errores sistemáticos debido al equipamiento utilizado. También, se tienen los errores
.N

que se producen al representar un número real irracional con un número finito de

dígitos.
A

2. Errores de redondeo. Aparecen cuando los cálculos se realizan usando un número

finito de dígitos.

3. Errores de truncamiento. Aparecen cuando un proceso infinito es reemplazado por

un proceso finito. Ejemplos: aproximar una serie por una suma parcial, aproximar una
función por un polinomio (Taylor), aproximar una derivada por un cociente incremen-
tal, etc.

4. Errores humanos. Son frecuentes y a veces difíciles de detectar. Ejemplos: errores en

la formulación del problema, en los cálculos “a mano”, al escribir un programa en la
computadora, etc.

2
 Errores absolutos y relativos

Antes de analizar que ocurre al representar números en una computadoras y se realizan ope-
raciones, veremos algunos conceptos básicos que sirven en un contexto más general.

Definición 1 Cuando un número real r (valor exacto) es aproximado por otro número r̄, se
define el error por r − r̄. Llamaremos, respectivamente, a

21
Error absoluto: ∆r = |r − r̄|,
 r − r̄  ∆r

20
Error relativo: δ r =  = .
r  |r|
También se llama error (relativo) porcentual al producto 100 ∗ δ r.

F
En general, el error relativo y el error porcentual son más útiles que el error absoluto, porque
da una idea del error cometido relativo a la magnitud de la cantidad que se está considerando.

A
En términos prácticos no se conocen exactamente los valores de los errores absolutos y

M
relativos sino que se tienen cotas de
√ ellos. Siempre se trata que las cotas sean lo más ajustadas
posible. Así, por ejemplo, si r = 2 y r̄ = 1.414, entonces
√
A
∆r = |r − r̄| = | 2 − 1.414| = |0.0002135...| ≤ 0.00022
∆r |0.0002135...|
-F

δr = = √ ≤ 0.00016
|r| 2
y el error porcentual es 0.016 %.
Las siguientes notaciones son equivalentes:
o

r̄ = 1.414, ∆r ≤ 0.22 10−3

ic

r = 1.414 ± 0.22 10−3

ér

1.41378 ≤ r ≤ 1.41422
um

Redondeo y truncado

Existen dos maneras de escribir un número real reduciendo el número de dígitos: redondeo
y truncado.
.N

Redondeo. Veamos algunos ejemplos de redondeo a 3 dígitos (decimales):

0.774432 → 0.774
A

1.23767 → 1.238
0.3225 → 0.323

En general, la aproximación por redondeo a n dígitos decimales r̃ de un número r es un

número de n dígitos decimales (después del punto decimal) que coinciden con los de r si el
dígito (n + 1) de r es 0, 1, 2, 3 o 4. Por otro lado, si el dígito (n + 1) de r es 5, 6, 7, 8 o 9,
entonces para definir r̃ se suma una unidad al n-ésimo dígito de r. Así se cumple que:
1 −n
|r − r̃| ≤ 10 . (1)
2
Para fijar ideas veamos un ejemplo muy sencillo, con n = 1:

3
 si r = 0.11 entonces r̃ = 0.1 y |r − r̃| = 0.01 ≤ 0.05 = 5 10−2 = 12 10−1 ;

si r = 0.16 entonces r̃ = 0.2 y |r − r̃| = 0.04 ≤ 0.05 = 5 10−2 = 12 10−1 .

Truncado. Veamos algunos ejemplos de truncado a 3 dígitos (decimales):

0.774432 → 0.774

21
1.23767 → 1.237
0.3225 → 0.322

20
En general, la aproximación por truncado (o truncamiento) a n dígitos decimales r̂ de un
número r es un número de n dígitos decimales (después del punto decimal) que coinciden
con los n primeros dígitos de r. Así se cumple que:

F
|r − r̂| ≤ 10−n , (2)

A
Para fijar ideas veamos un ejemplo muy sencillo, con n = 1:

M
si r = 0.11 entonces r̂ = 0.1 y |r − r̂| = 0.01 ≤ 0.1 = 10−1 ;
A
si r = 0.19 entonces r̂ = 0.1 y |r − r̂| = 0.09 ≤ 0.1 = 10−1 .
-F

En general, las computadoras trabajan con el sistema de redondeo y no el truncado.

Es importante observar que, si bien el error absoluto que introduce el redondeo depende de
la magnitud del número, el error relativo, que es el más significativo, por ser independiente
o

de la magnitud, está controlado en términos de la cantidad de dígitos con la que se trabaja.

Así vamos a definir el número de dígitos significativos en términos del error relativo.
ic

Definición 2 El número r̄ aproxima a r con m dígitos significativos si

ér

∆r
δr = ≤ 5 10−m .
um

|r|

Esto dice que el error relativo es del orden de 10−m .

.N

Así, en los ejemplos anteriores tenemos

r r̃ ∆r δr díg. signif.
0.774432 0.774 0.00043 0.00056(< 5 10−3 ) 3
A

−4
1.23767 1.238 0.00033 0.00027(< 5 10 ) 4
0.3225 0.322 0.0005 0.0015(< 5 10 ) −3 3

Errores en las operaciones

Analizaremos los errores que se introducen en las operaciones básicas (suma, resta, multi-
plicación y división). Más específicamente, nos centraremos en las dos primeras.
Sean x1 , x2 ∈ R, y x¯1, x¯2 aproximaciones de x1 y x2 respectivamente.
Sean y = x1 + x2 , ȳ = x¯1 + x¯2 .

4
 El error en la operación suma está dado por:

y − ȳ = (x1 + x2 ) − (x¯1 + x¯2 ) = (x1 − x¯1 ) + (x2 − x¯2 ),

por lo tanto el error absoluto

∆y = |y − ȳ| ≤ |x1 − x¯1 | + |x2 − x¯2 |

21
∆y ≤ ∆x1 + ∆x2

y el error relativo
∆y ∆x1 + ∆x2

20
δy = ≤ .
|y| |x1 + x2 |
n n
En general, si y = ∑ xi entonces ∆y ≤ ∑ ∆xi .

F
i=1 i=1

A
El caso de la resta es similar. Sean y = x1 − x2 , ȳ = x¯1 − x¯2 . Entonces el error absoluto se
obtiene haciendo

M
∆y = |y − ȳ| = |(x1 − x2 ) − (x¯1 − x¯2 )| = |(x1 − x¯1 ) − (x2 − x¯2 )|
∆y ≤ ∆x1 + ∆x2
A
y el error relativo
-F

∆y ∆x1 + ∆x2
δy = ≤ .
|y| |x1 − x2 |
o

Es posible estimar cotas de errores para la multiplicación y la división definiendo y = x1 ∗

x2 , ȳ = x¯1 ∗ x¯2 , z = x1 /x2 , z̄ = x¯1 ∗ x¯2 . Se puede deducir que:
ic

∆y ∆x1 ∆x2
∆y / |x2 |∆x1 + |x1 |∆x2 δy = / +
ér

|y| |x1 | |x2 |

y que
um

1 |x1 | ∆z ∆x1 ∆x2

∆z / ∆x1 + 2 ∆x2 δz = / +
|x2 | |x2 | |z| |x1 | |x2 |
.N
A