Computaci´on Cient´ıﬁca I, 2006 Gu´ıa No 1 Valpara´ıso...

Universidad Tecnica “Federico Santa Marıa”Departamento de InformaticaValparaıso–Santiago

Computacion Cientıfica I,1 2006

Guıa No 1Valparaıso–Santiago, 15.03.20062

Analisis de Errores, Condicionamiento y Numeros de Condicion.

1. “Precision”, “Accuracy”, “Resolution”, “Discrimination”, “Repeatability”.

La correspondencia entre dos lenguas distintas como el Ingles y el Castellano, raramente esbiunıvoca, lo que puede coducir a equıvocos notables. Uno de estos equıvocos se refiere ala palabra anglosajona “assessment” cuyo significado basico nada tiene que ver con “asegu-ramiento” que a veces erroneamente se le atribuye. Por ejemplo, frecuentemente se traducela inofensiva frase inglesa “quality assessment” por la frase castellana “aseguramiento de lacalidad”, de connotaciones un tanto faroleras.3 La voz inglesa “assessment”, de acuerdo conel “Webster’s Revised Unabridged Dictionary” (Copyright 1996, 1998 MICRA, Inc.), tieneque ver, originalmente, con el acto de estimar , avaluar, o valorar un bien, propiedad, un danoo perjuicio, o un impuesto, con el objeto de determinar una cantidad a ser pagada. Por exten-sion tambien se aplica, mas recientemente, a la estimacion o valoracion de alguna cualidad,metodo o procediento. Ası, “quality assessment” puede traducirse, mas modestamente, comoestimacion o valoracion de la calidad de algun procedimiento, tecnica o producto.

La sabidurıa popular italiana ha acunado la frase “traduttore, tradittore” que grafica bienla situacion en que puede encontrarse, sin quererlo, el traductor que quiere tender puentesentre dos lenguas. Una situacion semejante la constituyen ciertos vocablos que encontramosen la teorıa de los errores, tales como: “accuracy”, “precision”, “resolution”, “discrimina-tion”, “repeatability”. En el contexto de instrumentacion y las mediciones instrumentales nosproponemos aherir a los siguientes significados:

Precision. (En ingl. precision) Es la finura4 de detalle con que se representa un numeroo medida; corresponde a las cifras significativas. Este concepto se relaciona con el tamanode las unidades usadas para hacer una medicion. Mientras mas pequena sea la unidad, masprecisa sera la medicion. Por ejemplo, la medicion, del largo de un objeto, efectuada con unaregla milimetrica es mas precisa que la misma medicion hecha con una huincha que solo tienemarcados los cenımetros.

Exactitud. (En ingl. accuracy) Es la diferencia entre una medicion y el valor “real” oaceptado como correcto. Cuanto mayor sea la diferencia, menos exacta sera la medicion.La diferencia aludida se denomina error de medicion. Los errores de medicion son sujetosde analisis estadısticos para estimar la calidad (quality asessment! ) de un instrumento. Eneste ultimo sentido, y por extension, tambien se denomina exactitud a la medida del errorestadıstico de unas mediciones, debido a las imperfecciones del instrumento.

1Proyecto UTFSM-DGIP 2006-2007 Desarrollo de Textos Docentes.2 c© Luis Salinas Carrasco, Valparaıso, 15 de abril de 2006. De antemano se agradece toda correccion,

crıtica o comentario que el amable lector tenga a bien hacer llegar a [email protected], ra. (De farol , 3a. acep.) adj. fig. y fam. Vano, ostentoso, amigo de llamar la atencion y de

hacer lo que no le toca. Diccionario de la Lengua Espanola, RAE.4En Castellano hay clara diferencia entre los vocablos finura y fineza. En la vigesima segunda edicion del

Diccionario de la Lengua Espanola, de la Real Academia Espanola (http://www.rae.es/) se define:Finura. 1. f. Cualidad de fino.Fineza. (De fino). 1. f. Pureza y bondad de algo en su lınea. 2. f. Accion o dicho con que alguien da

a entender el amor y benevolencia que tiene a otra persona. 3. f. Actividad y empeno amistoso a favor dealguien. 4. f. Dadiva pequena y de carino. 5. f. Delicadeza y primor.

UTFSM, L. Salinas + O. Orellana + G. Hernandez, 2006 2

De un pasaje del Libro de Reyes de la Biblia [1, Reyes, I, 7, 23, p. 305] puediera colegirseque el cuociente entre el largo de una circunferencia y su diametro, hoy dıa denotado por laletra griega π, es 3.5 Si exageraramos diciendo que la Biblia declara que π = 3, 000 000 000(¡que no lo hace!), tendrıamos una medicion muy precisa pero bastante inexacta. Un valormas precisos pero todavıa no muy exacto es, por ejemplo, el que se encuentra en el llamadopapiro de Ahmes (Egipto) hacia el 1650 A.C. con π ≈ 3, 16. Menos exacto pero mas precisoes el valor que se asigna en la llamada tablilla de Susa (Babilonia) hacia el 1600 A.C. conπ ≈ 3, 125.

Resolucion. (Del ingl. resolution) Es el menor incremento de una cantidad que puede serpercibido por un instrumento de medicion.

Repetibilidad. (En ingl. repeatability) Error en las lecturas debidas a una combinacion delinstrumento y su uso. La repetibilidad no puede ser mejor que la exactitud, pero puede sermucho peor. Por ejemplo, un micrometro de tornillo puede tener una resolucion de 0.01 mm,segun su escala de divisiones. La exactitud esta limitada por la calidad del maquinado delhilo del tornillo del micrometro, la histeresis6 del tornillo, la posicion del cero y la lectura delinstrumento. Los errores producidos por los dos ultimos conceptos (posicion del cero y lecturadel instrumento) no pueden ser menores que la resolucion del instrumento, de modo que, auncuando las demas fuentes de error fueren despreciables, la exactitud del intrumento no puedeser mejor que 0.02 mm.

2. Algunos Preliminares Conceptuales. [2]

• Problema, solucion matematica y solucion computacional o algoritmo. Losproblemas que aborda la Computacion Cientıfica pueden reducirse, muy grosso modo,al computo de funciones matematicas (i.e., ideales) de la forma f : R

n → Rm. En esta

vision, Rn serıa el dominio de los datos y R

m el dominio de los resultados. La solucion deun problema tipificado por f : R

n → Rm, consistira en la construccion de un algoritmo

que permita el computo de la funcion f : Rn → R

m. De este modo, tambien el algoritmo

puede interpretarse como una funcion f : Rn → R

m que no necesariamente coincide con

f : Rn → R

m, esto es, para muchos valores x de la data se tendra f(x) 6= f(x). No

5Desde luego que en la Biblia no aparece ninguna formula como “π = 3”. Solo podemos inferir que eseera el valor que parece haber asignado a π el desconocido escritor del pasaje de la Biblia que describe la obrade Hiram, artesano, arquitecto y constructor de Tiro llamado por Salomon para erigir su celebre templo. Enefecto, en [1, Reyes, I, 7, 20-23, p. 305] podemos leer que Hiram comienza por construir dos columnas debronce, bellamente ornamentadas:

“20 Los capiteles de sobre las dos columnas tenıan 200 granadas en dos hileras, encima de la parte abultada

del capitel que estaba encima de la red, tanto en el primer capitel como en el segundo.21 Entonces erigio las columnas en el portico del templo. Cuando erigio la columna del sur, llamo su nombre

Jaquın; y cuando erigio la columna del norte, llamo su nombre Boaz.22 Puso en la parte superior de las columnas un motivo de lirios. Ası concluyo la obra de las columnas.23 Hizo tambien la fuente de broce fundido que tenıa 10 codos de borde a borde. Era circular

y tenıa 5 codos de alto, y una circunferencia de 30 codos.” [1, p. 305]El relato continua dando mayores detalles de la obra arquitectonica de Salomon e Hiram. De las medidas

que aparecen en el texto citado se infiere que para los constructores del templo de Salomon, π se tomabasimplemente como 30

10= 3, aunque, para tener mayor seguridad, habrıa que consultar a los textos (¡si es que

existen!) de los geometras de esa epoca y lugar.Reyna y Valera nos informan en [1, p. 305] que Jaquın significa establecera, Boaz , fortaleza, y que un codo

equivale aproximadamente a 0, 45 metros.6Histeresis. (Del gr. υστ ǫρησιζ, retraso). 1. f. Biol. y Fıs. Fenomeno por el que el estado de un material

depende de su historia previa. Se manifiesta por el retraso del efecto sobre la causa que lo produce. Diccionariode la Lengua Espanola, RAE.

L. Salinas + O. Orellana + G. Hernandez/ Computacion Cientıfica I/15 de abril de 2006


obstante, de un buen algoritmo se espera que ‖f(x) − f(x)‖, donde ‖ · ‖ es una normaapropiada, sea pequeno para todos los x relevantes.

• Problemas bien planteados . Se dice que un problema esta bien planteado ssi:– posee solucion;– la solucion es unica;– la solucion depende continuamente de los datos del problema.

La solucion puede ser mas o menos sensible a las perturbaciones en los datos de entrada,pero los algoritmos que resuelven el problema no deben empeorar la sensibilidad.

• Aproximacion . En la practica, cuando se aborda un problema de Computacion Cientıfi-ca —en el dominio que sea— es inevitable incurrir en aproximaciones simplificatorias.Antes del trabajo computacional propiamente tal, las aproximaciones pueden surgir en:

– el modelado del problema;– las mediciones empıricas de los datos;– los computos previos que sean necesarios.

Durante la computacion, las aproximaciones pueden aparecer por:– truncamiento o discretizacion;– redondeo.

La exactitud del resultado final dependera de todas estas aproximaciones.Ejemplo. El calculo del area de la superficie de la Tierra usando la formula A = 4πR2

involucra varias aproximaciones:– modelado de la Tierra como una esfera, lo que dista bastante de la realidad;– valor del radio R de la Tierra estimado mediante mediciones y calculos geodesicos

previos;– truncamiento necesario para almacenar el numero transcendente π;– valor de los datos de entrada y resultados de las operaciones aritmeticas redondea-

das por el computador.• Error absoluto y error relativo.

Error Absoluto = Valor Aproximado − Valor Verdadero ,

Error Relativo =Error Absoluto

Valor Verdadero,

Valor Aproximado = Valor Verdadero ×(1 + Error Relativo

).

El “Valor Verdadero” que aparece en las formulas es usualmente desconocido, de modoque hay que recurrir a estimaciones o cotas apropiadas.

• Error computacional y error propagado a partir de los errores de la data . Unproblema tıpico consiste en la evaluacion de una funcion f : R → R para un argumentodado. Sean:

x = valor verdadero de la entrada ,

x = valor aproximado de la entrada ,

f = funcion verdadera que se desea calcular ,

f = funcion aproximada (algoritmo) que efectivamente se calcula .

Entonces se tiene:

Error total = f(x) − f(x) =[f(x) − f(x)

]︸︷︷︸

Errorcomputacional

+[f(x) − f(x)

]︸︷︷︸Error propagadoa partir de los

errores de la data

.



En sıntesis:

Error computacional := f(x) − f(x) ,

Error propagado a partir de los errores de la data := f(x) − f(x) .

• Error de truncamiento y error de redondeo. El error de truncamiento es la dife-rencia entre el resultado veradero (para una entrada dada) y el resultado producido porun algoritmo especıfico usando aritmetica exacta. Este error se debe a aproximacionestales como el truncamiento de series infinitas o la interrupcion prematura de sucesionesiteradas (antes de su convergencia).El error de redondeo es la diferencia entre el resultado producido por un algoritmo da-do ejecutado con aritmetica exacta, y el resultado producido por el mismo algoritmoejecutado con aritmetica de precision limitada.El error computacional se define como:

Error computacional = Error de truncamiento + Error de redondeo

Ejemplo. Consideremos el problema de calcular computacionalmente el valor de la de-rivada de una funcion f en un punto x. Una aproximacion usual para f ′(x) mediantediferencias finitas es:

f ′(x) ≈ f(x+ h) − f(x)

h.

Esta aproximacion exhibe el compromiso entre error de redondeo y error de truncamiento.Observese que el valor verdadera a calcular es f ′(x) y el algoritmo para calcularlo esel cuociente diferencial anotado. En este ejemplo no consideraremos la aproximacion x(podrıamos decir que x es un numero que admite una representacion exacta en el sistemacomputacional empleado).En estas condiciones, mediante el desarrollo de Taylor del numerador del cuociente dife-rencial, se observa que el error de truncamiento viene dado por:

Error de truncamiento =f(x+ h) − f(x)

h− f ′(x)

=f ′(x) h+ 1

2f ′′(x) h2

h− f ′(x)

= f ′(x) +1

2f ′′(x) h− f ′(x)

=1

2f ′′(x) h− f ′(x) .

Luego, si M es una cota superior para |f ′′(t)| cuando t esta en una vecindad de x, resultaque: ∣∣∣∣Error de truncamiento

∣∣∣∣ ≤M h

2. (1)

Para el error de redondeo se tiene, en cambio:

Error de redondeo =

[f(x+ h) − f(x)

h

]

AE

−[f(x+ h) − f(x)

h

]

APL

=1

h

[([f(x+ h)

]AE

−[f(x+ h)

]APL

)︸︷︷︸

≤ ε

−([f(x)

]AE

−[f(x)

]APL

)︸︷︷︸

≤ ε

],



donde AE denota “Aritmetica Exacta”, APL, “Aritmetica de Precision Limitada”, ylos errores en la representacion de los valores de la funcion estan acotados por ε. Deconsiguiente: ∣∣∣∣Error de redondeo

∣∣∣∣ ≤2 ε

h. (2)

Como se ve, los errores de redondeo y de truncamiento son muy diferentes: por ejemplo,(1) muestra que la cota para el error de truncamiento es directamente proporcional ah y, en cambio, de (2) se sigue que la cota para el error de redondeo es inversamenteproporcional a la misma cantidad h.

• Errores hacia adelante y errores hacia atras .7 Supongase que queremos calculary = f(x), para una funcion f : R

n → Rm y un x ∈ R

n dado, aplicando un algoritmo

f : Rn → R

m. Al aplicar el algoritmo obtenemos el valor y = f(x) ∈ Rm que puede ser

diferente de y = f(x) ∈ Rm. Entonces se define:

Error hacia adelante = ∆y := y − y ∈ Rm ,

Error hacia atras = ∆x := x− x ∈ Rn , donde x es tal que f(x) = y .

Observese que en el caso del error hacia atras, a x se aplica la funcion matematica ideal

f y no la funcion algoritmo f .Analogamente se define los errores relativos hacia adelante y hacia atras:

Error relativo hacia adelante =

∥∥∆y∥∥

Rm∥∥y∥∥

Rm

, (3)

Error relativo hacia atras =

∥∥∆x∥∥

Rn∥∥x∥∥

Rn

. (4)

Para n = m = 1 estas expresiones se reducen al valor absoluto de los cuocientes respec-tivos.Ejemplo. (Con n = m = 1) Considerese el problema de evaluar la funcion f(x) =

√2

para x = 2. Para hacerlo usamos un algoritmo f como el descrito en el ejercicio 11. ynos detenemos en la cifra de las decimas. Entonces tenemos:

y =√

2 = 1,41421 35623 . . . y = 1,4 ,

y observamos que para x = 1,96 se tiene:

y = f(1,96) =√

1,96 = 1,4 .

Luego:

|Error hacia adelante| = |∆y| := |y − y| = |1,4 − 1,41421 35623 . . . | ≈ 0,0142 ,

|Error hacia atras| = |∆x| := |x− x| ,= |1,96 − 2| = 0,04 .

Se observa que los errores hacia adelante y hacia atras son bien diferentes. Los corres-pondientes errores relativos son ∆y/y ≈ 1 % y ∆x/x = 2 %, respectivamente.Ejemplo. (Con n = m = 1) Interesa evaluar la funcion f(x) = tg x en x = 1 [radianes]mediante un algoritmo que consiste en truncar el desarrollo de Maclaurin:

tan x = x+1

3x3 +

2

15x5 +

17

315x7 +

62

2835x9 + · · ·+ . . . (5)

7“Forward” y “backward error”, respectivamente.



inmediatamente despues del termino cubico.8 De este modo, el algoritmo que se deseautilizar viene dado por:

f(x) = x+x3

3.

El error hacia adelante se obtiene inmediatamente:

∆y = y − y = f(x) − f(x) = x+x3

3− tg x .

Para el error hacia atras se requiere hallar un valor x tal que f(x) = tg x = y = f(x).Evidentemente, restringiendo el valor de x al intervalo ] − π/2 , π/2[, tal x viene dadopor:

x = arc tg y = arc tg f(x) = arc tg

(x+

x3

3

),

con lo que el error hacia atras queda:

∆x = x− x = arc tg

(x+

x3

3

)− x .

Por ejemplo, para x = 1,5 < π/2 se tiene:

∆y =

[x+

x3

3− tg x

]

x=1,5

≈ −11,4764 ,

∆x =

[arc tg

(x+

x3

3

)− x

]

x=1,5

≈ −0,293183 ,

de modo que la diferencia entre los errores absolutos hacia adelante y hacia atras, essimplemente enorme. No obstante, dado que:

y = tg(1,5) ≈ 14,1014 , x =

[arc tg

(x+

x3

3

)x

]

x=1,5

≈ 1,20682 ,

para los errores relativos hacia adelante y hacia atras se tiene:

∆y

y≈ −11,4764

14,1014≈ −0,813849 ,

∆x

x≈ −0,293183

1,20682≈ −0,242939 ,

lo que de todos modos representa una gran diferencia.

8El termino general en (5) es:

22n(22n − 1

)|Bn|

(2n)| x2n−1 , n ∈ N ,

donde Bn denota el n-esimo numero de Bernoulli. Hay varias definiciones para los numeros de Bernoulli. Unade ellas corresponde a la relacion de recurrencia:

B0 = 1 , (n + 1)Bn = −n−1∑

k=0

(n + 1

k

)Bk , n ∈ N.

Los numeros de Bernoulli verifican:t

et − 1=

∞∑

n=0

Bn

n!tn .

Un buen ejercicio para el estudiante interesado en estas cuestiones, consiste en demostrar (5) y las formulasde esta nota.



• Sensibilidad y Condicionamiento. Se dice que un problema esta bien condiciona-do o que es relativamente insensible a pequenas perturbaciones en la data si variacionesrelativas pequenas en la data de entrada producen variaciones relativas de magnitud com-parable en la salida. Si esto9 no se cumple, se dice que el problema esta mal condicionadoo que es sensible a las perturbaciones de la data.Conceptualmente se define el numero de condicion de un problema mediante la expresion:

Numero de condicion =

∥∥variacion relativa en la solucion∥∥

Rm∥∥variacion relativa en la data de entrada∥∥

Rn

=‖f(x) − f(x)‖Rm/‖f(x)‖Rm

‖x− x‖Rn/‖x‖Rn

=‖∆y‖Rm/‖y‖Rm

‖∆x‖Rn/‖x‖Rn

=Error relativo hacia adelante

Error relativo hacia atras.

Mediante el numero de condicion se puede precisar la nocion de problema mal condicio-nado: se dice que un problema es sensible a las perturbaciones de la data o que esta malcondicionado si:

Numero de condicion ≫ 1 .

Recordando que el error relativo hacia adelanteDe la ultima igualdad en la formula precedente se observa que el numero de condiciones un factor de amplificacion que relaciona los errores relativos hacia adelante y haciaatras:

Error relativo hacia adelante = Numero de condicion × Error relativo hacia atras .

A menudo no se conoce exactamente el numero de condicion sino solamente una esti-macion o una cota superior 0 < C < ∞. En este caso la ecuacion precedente adopta laforma:

Error relativo hacia adelante ≤ C × Error relativo hacia atras ,

que todavıa representa una buena informacion acerca del problema.Ejemplo. Consideremos el problema de evaluar una funcion diferenciable f : R → R enuna abscisa x ∈ R en la situacion en que el sistema computacional solo permite trabajarcon una aproximacion x de x, de modo que ∆x = x− x. Entonces se tiene:

Error relativo hacia adelante =|f(x+ ∆x) − f(x)|

|f(x)| ≈ |f ′(x) ∆x||f(x)| ,

Error relativo hacia atras =|∆x||x| ,

Numero de condicion ≈∣∣∣∣f ′(x) ∆x/f(x)

∆x/x

∣∣∣∣ =xf ′(x)

f(x)

9Demostrativos: este, esta, estos, estas, ese, esa, esos, esas, aquel, aquella, aquellos, aquellas. Seacentuan si son pronombres: “Le han visto estos.” No se acentuan si son adjetivos: “Le han visto es-

tos chicos.” Nunca se acentuan esto, eso, aquello. Son siempre pronombres y no dan lugar a dudas.(http://html.rincondelvago.com/acentos-en-el-castellano.html).



• Consideremos el problema de evaluar una funcion diferenciable f : Rn → R en un punto

x = (x1, . . . , xn) ∈ Rn cuando el sistema computacional disponible solo permite una

aproximacion x = (x1, . . . , xn). Entonces:

∆x = (∆x1, . . . ,∆xn) , donde ∆k = xk − xk , k = 1 : n .

Sea y = f(x). La nocion de numero de condicion se puede refinar de modo que exprese elefecto en la variable dependiente y producido por eventuales perturbaciones en cada unade las variables xk. Para el error absoluto hacia adelante ∆y se tiene, evidentemente, laestimacion:

∆y ≈n∑

k=1

∂f

∂xk

(x) ∆xk ,

de modo que el error relativo hacia adelante vendra estimado por:

∆y

y≈

n∑

k=1

xk

y

∂f

∂xk

(x)∆xk

xk

=n∑

k=1

xk

f(x)

∂f

∂xk

(x)∆xk

xk

,

que es una expresion lineal en los errores relatios hacia atras en cada una de las variablesindependientes que intervienen. Se acostumbra a definir:

εy :=∆y

y, εxk

:=∆xk

xk

, κk :=xk

f(x)

∂f

∂xk

(x) , k = 1 : n .

El error relativo en la variable dependiente, εy, corresponde al error relativo hacia ade-lante. El error relativo en la variable independiente, εxk

, corresponde al error relativohacia atras con respecto a la k-esima variable. κk es el numero de condicion o factor deamplificacion del error relativo en la k-esima variable.

3. Sea y = p(x) := x3 − 4x2 + 2x− 2,2 y x0 = 2,4142136 .(a) Calcule y en x0 de manera exacta.(b) Calcule y en x0 redondeando a cinco decimales; determine los errores absolutos y relativosresultantes en y.(c) Calcule y en x0 truncando a cinco decimales; determine los errores absolutos y relativosresultantes en y.(d) Si el valor de x0 tiene un error relativo de 0.018% y los coeficientes de p(x) tienen erroresabsolutos de 0.325%, determine los errores absolutos y relativos resultantes en y.

4. [5, p. 33, ex. 2] Sean a, b, c numeros de coma fija con N decimales tras la coma. ¿Es estoposible? Suponga que 0 < a, b, c < 1. Se define un producto alternativo a ∗ b de la siguiente

forma: se suma10N

2al producto exacto ab y luego se elimina todos los dıgitos a partir del

(N + 1)-esimo.(a) Obtenga una (buena) cota para |(a ∗ b) ∗ c− abc|.(b) ¿En cuantas unidades del N -esimo lugar tras la coma pueden diferir (a∗b)∗c y a∗(b∗c)?5. Para cada una de las formulas:

z = z(p, q) :=

(√p+

1

q−√p− 1

q

)−1

, p, q ≫ 1 ,

z = z(p, q) :=(√

ep2 + e−q2 −√ep2 − e−q2

)−1

, |p|, |q| ≫ 1 ,

z = z(p, q) :=

(√tg p+

1

tg q−√

tg p− 1

tg q

)−1

, 0 < |p− π/2|, |q − π/2| ≪ 1 ,



estudie las siguientes tareas:(a) Determine los numeros condicionantes de z en terminos de p, q. ¿Hay alguna simetrıa quele permita ahorrar trabajo?(b) ¿Esta bien condicionado el problema del calculo de z en terminos de p, q? Justifique.(c) Describa dos algoritmos diferentes que permitan calcular z en funcion de p, q, de tal modoque uno de ellos (que llamaremos algoritmo astuto) garantice un buen control de los erroresdurante todo el calculo, y el otro (que llamaremos algoritmo ingenuo) que no lo asegure.(d) Suponga que los valores de p, q se conocen con errores relativos εp y εq, respectivamente,lo que se traduce en un error relativo εz en el calculo de z. Sobre la base de estos erroresrelativos se definen los factores de amplificacion κp = |εz| / |εp| , κq = |εz| / |εq| . Obtengasendas formulas para estimar los factores de amplificacion κp y κq para ambos algoritmosdescritos en (c).(e) Suponiendo que p = 10−3 y q = 0, 18 × 10−2, respectivamente, p = 106 y q = 0, 18 × 104,determine los valores aproximados de los factor de amplificacion κp y κq para los algoritmosdescritos en (c).

6. Considere la formula:

z = z(p, q) :=

(√p+

1

q−√p− 1

q

)−1

, p, q ≫ 1 .

(a) Determine los numeros de condicion de z en terminos de p, q.(b) ¿Esta bien condicionado el problema del calculo de z en terminos de p, q? Justifique.(c) Suponga que los valores de p, q se conocen con errores relativos εp y εq, respectivamente,lo que se traduce en un error relativo εz en el calculo de z. Sobre la base de estos erroresrelativos se definen los factores de amplificacion κp = |εz| / |εp| , κq = |εz| / |εq| . Obtenga unaestimacion de los factores de amplificacion κp y κq. Nota: En este ejercicio muy simplificado,puede Ud. suponer que los calculos intermedios de su algoritmo no introducen errores. Evi-dentemente, esta es una situacion muy poco real. En ejercicio 2. se estudia el caso en que loscalculos intermedios efectivamente introducen errores.(d) Suponiendo que p = 106 y q = 0, 18×108, determine los valores aproximados de los factorde amplificacion κp y κq.

Desarrollo. (a) Primeramente conviene simplificar la expresion para z = z(p, q):

z =1√

p+ 1q−√p− 1

q

=

√q√

pq + 1 −√pq − 1

=1

2

√q(√

pq + 1 +√pq − 1

)

Los numeros condicionantes se obtienen directamente a partir de sus definiciones mediantetransformaciones algebraicas elementales:

κp :=p

z

∂z

∂p=

1

2

pq√p2q2 − 1

=1

2

1√1 − 1

p2q2

,

κq :=q

z

∂z

∂q=

1

2+

1

2

pq√p2q2 − 1

=1

2+

1

2

1√1 − 1

p2q2

.

(b) En vista que p, q ≫ 1, se observa que κp ≈ 1/2 y κq ≈ 1. Luego, el calculo de z(p, q)esta bien condicionado con respecto a perturbaciones en p y q, respectivamente. En (c) seobtienen mejores aproximaciones para κp y κq.



(c) Los factores de amplificacion son precisamente los (valores absolutos de los) numeroscondicionantes obtenidos en (a). Aplicando aproximaciones estandar resulta entonces:

κp ≈ 1

2

(1 +

1

2p2q2

)=

1

2+

1

4p2q2, κp ≈

1

2+

1

2

(1 +

1

2p2q2

)= 1 +

1

4p2q2.

(d) En vista de los calculos precedentes y que los valores p = 106 y q = 0, 18×108 son bastantegrandes, se puede decir que los factores de amplificacion son κp ≈ 1/2 y κq ≈ 1, con un errordel orden de 10−12 (!).

7. La formula de Cardano (Geronimo Cardanus, 1501-1576) para determinar la raız realx0 de la ecuacion de tercer grado x3 + 3px + 2q = 0 , p, q ∈ R, cuando la discriminanteD := q2 + p3 es estrictamente positiva, viene dada por:

x0 = u+ v , u = 3√−q + t , v = 3

√−q − t , t = 2

√q2 + p3 . (6)

Suponga que p, q son dos numeros positivos .(a) Determine los numeros condicionantes de x0 en terminos de p y q.(b) ¿Esta bien condicionado el problema del calculo de x0 en terminos de p y q? Justifique.(c) Describa un algoritmo que permita calcular t en funcion de p & q, y luego x0 en terminosde q & t, manteniendo un buen control de los errores durante todo el calculo.(d) Suponga que el valor de q se conoce exactamente, i.e. con un un error relativo εq = 0, yque el calculo de t involucra un error relativo εt, lo que se traduce en un error relativo εx0 enel calculo de x0. Sobre la base de estos errores relativos se define el factor de amplificacionκ ≡ κ(x0, t) = |εx0/εt| . Obtenga una formula para estimar este factor de amplificacion κ(x0, t)para su algoritmo.(e) Suponiendo que p = 103 y q = 0, 18× 10−2 determine los valores aproximado de su factorde amplificacion κ(x0, t).

8. La raız cuadrada ±(u + iv) de un numero complejo x+ iy con y 6= 0, i2 = −1, se puedecalcular mediante la formula:

u = ±√

1

2

(x+

√x2 + y2

), v =

y

2u.

(a) Demuestre la formula precedente.(b) Discuta los casos x ≥ 0 y x < 0 con respecto a magnitud de los errores absolutos resultantescuando los valores de x e y se conocen con errores de, a lo mas, ∆x y ∆y, respectivamente.(c) Proponga un algoritmo que minimice el error absoluto en el calculo de la raız cuadradade un numero complejo.(d) Programe su algoritmo (c) en MATLAB y verifıquelo con algunos experimentos numericos.

9. La teorıa de las fracciones concatenadas juega un importante papel en el analisis y disenode los filtros digitales y analogico de la Ingenierıa Electronica.10 En este contexto considerela funcion de transferencia:

H0(s) =s+ a2

(s+ a1)(s+ a3), donde a1 = 1 , a2 = 2 , a3 = 3 . (7)

10Ref.: Louis Weinberg. “Network Analysis and Synthesis”, McGraw-Hill Book Company, Inc., New York,1962, Example 5-2, p. 197.



Considere, ademas, las siguientes fracciones concatenadas:

H1(s) =1

s+

1

−s2

2+

1

− 4

5 s+

1

−25 s2

6+

1

− 1

5 s

, H2(s) =1

s+1

1

2+

1

4s+1

1

6

. (8)

(a) Demuestre o refute (y en este ultimo caso corrija) las igualdades H0(s) = H1(s) = H2(s).(b) Suponga que los valores de las constantes a1, a2, a3 se conocen con un error relativo del5%. ¿Que error relativo maximo es dable esperar en H0(1/2), respectivamente, en H1(1/2) yen H2(1/2)?(c) Si tuviera que elegir el mejor metodo para calcular H0(1/2), bajo las mismas condicionesde (b), ¿cual formula elegirıa y por que?(c) En las mismas condiciones de (b), ¿que error relativo maximo es dable esperar en H0(s),respectivamente, en H1(s) y en H2(s), cuando s recorre libremente toda la recta real R?(d) Programe las formulas para H0(s), H1(s) y H2(s), en MATLAB y verifique experimental-mente sus predicciones concernientes a los errores relativos en (c).

10. Resuelva el sistema de ecuaciones:{

x + 400,0031415926 y = 801. ,200. x + 8,0027182818× 104 y = 600. ,

(a) en forma exacta,(b) redondeando en todas las operaciones a siete cifras (decimales) significativas,(c) truncando en todas las operaciones tras el septimo decimal.(d) Suponga que las constantes 801 y 600 son solo aproximaciones con un error absolutoinferior a 5,414284 la primera y 7,502723 la segunda. Suponga, ademas, que las constantes dela matriz del sistema son exactas. ¿Con que precision puede Ud. garantizar los valores de lassoluciones x e y ?(e) Suponga que las constantes de la matriz del sistema y las del vector de datos solo estangarantizadas con un error relativo del 1,675 %. ¿Con que precision puede Ud. garantizar ahoralos valores de las soluciones x e y ?(f) Calcule los numeros de condicion de este problema con respecto a todas las “constantes”que intervienen en el.

11. 11 Durante la vigencia del legendario sistema de Escuelas Primarias en la Republicade Chile, antes del advenimiento de las calculadoras electronicas y de las sucesivas refor-mas escolares,12 los alumnos utilizaba un astuto metodo (lamentablemente hoy dıa olvidadopor alumnos y preceptores) para para extraer la raız cuadrada de un numero real positivoutilizando solo lapiz y papel.

En lo que sigue, se describe el metodo con relacion a un numero c ∈ R tal que 1 ≤ c < 100.La extension del metodo a todo R

+ es inmediata.

11Ref.: Benedikta Ruscheweyh: “Algorithmen des Wurzelziehens”. Franken-Landschulheim Schloß Gaibach,Kollegstufe, Abiturjahrgang 1998/2000, Februar 2000.

12El lector estudioso no desperdiciara la oportunidad de investigar la historia de la educacion basica y mediaen Chile desde los (no tan) lejanos dıas de la Colonia hasta el presente, y de hacer un estudio comparativocrıtico de los logros escolares en las diversas epocas del sistema educativo chileno.



El metodo consiste en la construccion de una sucesion de {an}n∈N0en N0, y una sucesion

{bn}n∈N0en {0, . . . , 9}, tales que:

an = 10 an−1 + bn−1 , con a0 6= 0 , a20 ≤ c < (a0 + 1)2 .,

100n+1c− 100 a2n = 100

(100nc− (10 an−1 + bn−1)

2) ≥ 0 ,

100(100nc− (10 an−1 + bn−1 + 1)2) < 0 .

(9)

De (9) resulta:

a2n

100n≤ c <

(an + 1)2

100n, i.e., 0 ≤

√c− an 10−n < 10−n , (10)

de donde se obtiene lımn→∞

an 10−n =√c, ademas de una cota para el error en la n-esima

iteracion.

La ventaja del metodo descrito estriba en que los numeros dn = 100n+1c− 100 a2n se pueden

calcular recursivamente mediante:

dn = 100 [dn−1 − (20 an−1 + bn)] . (11)

Luego, el metodo requiere solo operaciones aritmeticas simples (multiplicacion por 20 enlugar de cuadraturas). Ademas, las operaciones aritmeticas se pueden limitar siempre a laparte entera del numero 100n+1c actual ya que los a2

n son siempre numeros enteros.

En lo que sigue se describe el algoritmo mediante un ejemplo concreto. Supongase que sedesea calcular x =

√6. Como se ha explicado mas arriba, el metodo consiste en hallar la

mejor aproximacion por defecto de los sucesivos numeros enteros no negativos que generael algoritmo. Ası, a0 debe ser el mayor entero no negativo cuyo cuadrado no supera c =6. Evidentemente se tiene entonces a0 = 2. Para obtener b0, se calcula la diferencia d0 =[c− a2

0] × 100 = [6 − 4] × 100 = 200; entonces b0 es el mayor entero no negativo tal qued0 − (20 a0 + b0) b0 = 200 − (20 × 2 + b0) b0 ≥ 0. En vista de que:

d0

20 a0

=[c− a2

0] × 100

20 a0

= b0 +b20

20 a0

, (12)

una cota superior para b0 viene dada por⌊d0

20 a0

⌋=

⌊[c− a2

0] × 100

20 a0

⌋. (13)

Notese que la cota (13) puede ser estrictamente mayor que b0. En efecto, en el ejemplo

analizado la cota (13) resulta

⌊d0

20 a0

⌋=

200

40= 5, lo que conducirıa a un valor demasiado

grande para b0:

(20 a0 + b0) b0 = (20 × 5 + 5) × 5 = 225 > 200 = d0 . (14)

Recien con b0 = 4 se logra cumplir la condicion discutida. Habiendo determinado b0 se puedeobtener ahora a1 mediante a1 = 10 a0 + b0 = 10 × 2 + 4 = 24. A continuacion se forma lasegunda diferencia,

d1 = [d0 − (20 a0 + b0) b0]×100 = [200−(20×2+4)4]×100 = [200−176]×100 = 2,400 . (15)

El procedimiento se repite y se obtiene b1 = 4 y con ello, a2 = 244. Ya que el radicando c no esun cuadrado de un numero racional, el algoritmo no se interrumpe. Si se obtuviera a2

n = 102ncpara algun n, entonces obviamente x =

√c = 10−nan y el algoritmo terminarıa. El algoritmo

se registra(ba!), usualmente, en la siguiente forma tabular:



√6,0000 = 2,4494 . . .

a20 = 22 −→ 4

d0 = [c− a20] × 100 −→ 2 00 : 4 4 = 4

(20 a0 + b0) b0 = (20 × 2 + 4) × 4 −→ 1 76

d1 = [d0 − (20 a0 + b0) b0] × 100 −→ 2400 : 48 4 = 4(20 a1 + b1) b1 = (20 × 24 + 4) × 4 −→ 1936

d2 = [d1 − (20 a1 + b1) b1] × 100 −→ 46400 : 488 9 = 9(20 a2 + b2) b2 = (20 × 244 + 9) × 9 −→ 44001

d3 = [d2 − (20 a2 + b2) b2] × 100 −→ 239900 : 4998 4 = 4(20 a3 + b3) b3 = (20 × 2449 + 4) × 4 −→ 195936

d4 = [d3 − (20 a3 + b3) b3] × 100 −→ 43964... : 49988 x = x. . . . . . . . . . . . . . . . . .

La tarea consiste ahora en implementar computacionalmente este algoritmo. En esencia setrata de un estudio de virtuosismo computacional (¡parecido a los ejercicios de piano o de cual-quier otro instrumento musical que el lector probablemente sufrio/disfruto en su infancia!).Como aquellos ejercicios, este tambien vale la pena. Probablemente el lector preferira pro-gramar el algoritmo en C/C++ antes que en MATLAB. Serıa interesante explorar ambasposibilidades. Sin perdida de generalidad se puede suponer siempre que 1 < c < 100. Why? .

(a) De una regla heurıstica para estimar a0 y el numero de decimales de la parte entera de c.

(b) Obtenga una formula para estimar los errores absoluto y relativo de la raız cuadrada√c

de c ∈ R+ en funcion del numero n de iteraciones. ¿Permite el algoritmo que haya alguna

incertidumbre en el valor de los an’s o de los bn’s?

(c) Construya un programa (C/C++ o MATLAB), basado en el algoritmo discutido en esteejercicio (¡y no otro please!) que permita calcular la raız cuadrada de cualquier numero c ∈ R

+

con una precision dada.

(d) Sea N su numero de R.U.T., excluyendo el dıgito verificador. Perfeccione su programa demodo que sea capaz de calcular las raıces cuadradas de los numeros N + k, k ∈ N, k ≤ 10,con 50 (cincuenta) cifras decimales significativas (debe Ud. garantizar el valor de todos losdıgitos hasta el quincuagesimo decimal). Note que la condicion “cincuenta cifras decimalessignificativas” puede superar la capacidad estandar de su “software” y/o “hardware”. Luego,su trabajo debe mostrar claramente como aborda y como resuelve esta dificultad.

(e) Usando el algoritmo de redondeo y su algoritmo de radicacion, calcule la raız de orden210 del numero N de la parte (d), con 50 (cincuenta) cifras decimales significativas (debe Ud.garantizar los dıgitos hasta el quincuagesimo decimal). El mismo comentario de (d) es validoen este punto.

(f) De una fundamentacion teorica de la validez de este algoritmo.

12. Considere el problema de calcular la raız de menor valor absoluto y = ϕ(p, q) de laecuacion cuadratica:

y2 + 2py − q = 0 , p >> q > 0 (p >> q significa “p mucho mayor que q”).

Como se sabe, y = ϕ(p, q) = −p +√p2 + q.

(a) Determine los numeros de condicion de y. ¿Esta bien condicionado este problema?

(b) Suponga que los errores relativos en los datos p y q son εp y εq, respectivamente, con|εp|, |εq| ≤ eps, donde eps es el maximo error relativo admisible. Determine el error relativoεy y obtenga cotas (inferior y superior) para este en terminos de eps.



(c) Considere los siguientes algoritmos:

Algoritmo 1: s := p2 ; t := s+ q ; u :=√t ; y := −p + u ;

Algoritmo 2: s := p2 ; t := s+ q ; u :=√t ; v := p+ u ; y = p/v .

¿Conducen ambos algoritmos al mismo resultado? En particular, ¿permite alguno de ellos (o,quizas, los dos) calcular y = ϕ(p, q) ?

(d) Discuta la propagacion de errores en ambos algoritmos aplicando operaciones de comaflotante. Obtenga las cotas de error relativo para y en funcion de los errores relativos de losdatos de entrada p y q. Sobre esta base, ¿cual de estos dos algoritmos es mejor?

(e) Programe ambos algoritmos en MATLAB y verifique experimentalmente todas sus aser-ciones.

13. La impedancia de entrada de cierto circuito electrico viene dada por la expresion:

R =1

1 − 1

1 − 1

1 − p

p−√p2 + q

(16)

donde p y q son parametros reales positivos tales que p >> q. El celebre electricista IbrahimIbn-Nadel, natural de Erehwon, nella Valle di Giammai , propone el siguiente algoritmo paracalcular R:

x1 = p ∗ p , x2 = q + x1 , x3 =√x2 , x4 = p− x3 , x5 = p/x4 , x6 = 1 − x5 ,

x7 = 1/x6 , x8 = 1 − x7 , x9 = 1/x8 , x10 = 1 − x9 , x11 = 1/x10(17)

(a) ¿Calcula el algoritmo (17) el valor de R en funcion de los parametros p, q ?



Solucion: El algoritmo (17) produce el siguiente “output”:

x1 = p2 , x5 =p

p−√p2 + q

, x9 =1

1 − 1

1 − p

p−√p2 + q

,

x2 = p2 + q , x6 = 1 − p

p−√p2 + q

, x10 = 1 − 1

1 − 1

1 − p

p−√p2 + q

,

x3 =√p2 + q , x7 =

1

1 − p

p−√p2 + q

, x11 =1

1 − 1

1 − 1

1 − p

p−√p2 + q

.

x4 = p−√p2 + q , x8 = 1 − 1

1 − p

p−√p2 + q

,

Se observa que x11 coincide con R, i.e., el algoritmo (17) efectivamente calcula R.

(b) Si p = 103 y x4 = −0,00005, donde estos valores solo pueden garantizarse con un errorrelativo del 3 % (tres por ciento), ¿con que precision se puede garantizar el valor de x6 ?

Solucion: En (a) se observa que x6 = 1 − p/x4, donde x4 = x4(p, q) = p −√p2 + q. No

obstante la dependencia de x4 de p y q, y puesto que aquı se da el valor de x4 y su errorrelativo, se puede considerar que p y x4 son variables independientes. Entonces se tiene:

∆x6 =∂x6

∂p∆p +

∂x6

∂x4∆x4 = − 1

x4∆p +

p

x24

∆x4

∆x6

x6= − p

x6

1

x4

∆p

p+x4

x6

p

x24

∆x4

x4= − p

1 − p/x4

1

x4

∆p

p+

x4

1 − p/x4

p

x24

∆x4

x4

ǫx6 = − p

x4 − pǫp +

p

x4 − pǫx4

|ǫx6 | ≤ |p||x4 − p| (|ǫp| + |ǫx4 |) ≤

103

| − 0,5 × 10−4 − 103| (0,03 + 0,03) ≤ 0,06 .

Luego, x6 se puede garantizar, a lo mas, con una precision de 6%.

(c) Determine el valor algebraico de x11 en la forma de una fraccion simple, i.e., solo con unnumerador y un denominador.



Solucion:

x1 = p2 , x5 =p

p−√p2 + q

, x9 =

√p2 + q

p,

x2 = p2 + q , x6 =

√p2 + q

−p +√p2 + q

, x10 =p−

√p2 + q

p,

x3 =√p2 + q , x7 =

−p +√p2 + q√

p2 + q, x11 =

p

p−√p2 + q

.

x4 = p−√p2 + q , x8 =

p√p2 + q

,

(d) Sobre la base de (c), proponga un algoritmo mas astuto que el de Ibrahim para calcularel valor de R en funcion de los parametros p, q.

Solucion: Un algoritmo algo mas astuto (pero no mucho mas) que el de Ibrahim serıa elsiguiente:

y1 = p ∗ p , y2 = q + y1 , y3 =√y2 , y4 = p− y3 , y5 = p/y4 . (18)

Sin embargo, en vista de que p >> q > 0, este algoritmo tiene el problema que incluye unadivision por un numero muy pequeno de signo indeterminado a consecuencias de los eventualeserrores en las operaciones elementales. Un algoritmo algo mas astuto puede basarse en lasiguiente identidad:

R =p

p−√p2 + q

· p+√p2 + q

p+√p2 + q

= −pq

(p+

√p2 + q

). (19)

Este algoritmo quedarıa ası:

z1 = p ∗ p , z2 = q + z1 , z3 =√z2 , z4 = p+ z3 , z5 = p ∗ z4 . z6 = −z5/q . (20)

Este ultimo algoritmo tambien incluye una division por un numero pequeno, q, pero ahora susigno esta claramente definido, a saber, q > 0. Si ǫq es el error relativo en q, donde usualmente|ǫq| << 1, entonces el denominador siempre sera mayor que (1 − |ǫq|)q > 0, de modo que lainfluencia del error ǫq en el valor de R = z6 estara perfectamente acotada.

(e) Con referencia a (d) determine los factores de amplificacion de los errores (relativos) en py q.

Solucion: Con referencia al algoritmo (18) en (d), que generaR1 = R1(p, q) :=p(

p−√p2 + q

) ,

se tiene ǫR1 =p

R1

∂R1

∂pǫp +

q

R1

∂R1

∂qǫq , donde:

∂R1

∂p= − 1

q

(2p+

2p2 + q√p2 + q

),

∂R1

∂q=

p

2√p2 + q

(p−

√p2 + q

)2 ,

y por consiguiente:

κ1,p =p

R1

∂R1

∂p= 1 +

p√p2 + q

, κ1,q =p

R1

∂R1

∂p= − 1

2− p

2√p2 + q

.



Con referencia al algoritmo (20) en (d), que genera R2 = R2(p, q) := − p

q

(p+

√p2 + q

), se

tiene ǫR2 =p

R2

∂R2

∂pǫp +

q

R2

∂R2

∂qǫq , donde:

∂R2

∂p= − 1

q

(2p+

2p2 + q√p2 + q

),

∂R2

∂q=

p

2q2

(2p+

2p2 + q√p2 + q

),

y por consiguiente:

κ2,p =p

R1

∂R1

∂p= 1 +

p√p2 + q

, κ2,q =p

R1

∂R1

∂p= − 1

2− p

2√p2 + q

.

Se observa que κ1,p = κ2,p y κ1,q = κ2,q, i.e., los factores de amplificacion correspondientes aambos algoritmos coinciden, lo que era de esperarse, pues ambos algoritmos definen la mismafuncion.

(f) [Tarea post-certamen.] Usando el algoritmo (17) para calcular R = R(p, q), deter-mine los factores de amplificacion κp y κq en la expresion ǫR = κpǫp + κqǫq para p = 1000 yq = 0,1.

Solucion: κp = 2, κq = −1.

(g) [Tarea post-certamen.] Investigue que circuito electrico podrıa dar origen a una ex-presion como (16).

Solucion: Corresponde a las llamadas “ladder-networks” con elementos concentrados acti-vos y pasivos. Investigue en algun texto contemporaneo de analisis de circuitos electricos yelectronicos.

14. [4, S. 15–22] Propagacion de Errores.

(1) Introduccion. Un algoritmo consiste, en general, de una sucesion de operacioneselementales que permite calcular la solucion de un problema a partir de ciertos datosde entrada. Para precisar esta nocion (vaga todavıa) recurriremos al formalismo de los

espacios vectoriales. Grosso modo, un algoritmo calcula la solucion y := [y1, . . . , ym]T ∈R

m de un problema dado a partir de una data x := [x1, . . . , xn]T ∈ D ⊆ Rn, donde D es

un subconjunto de Rn donde supondremos que la solucion del problema es unica. Esta

correspondencia define una funcion:

y = ϕ(x) , ϕ : D → Rm , D ⊆ R

n . (21)

El calculo de y = ϕ(x) se realiza mediante una sucesion de computos elementales de laforma:x1...xn

≡

x

(0)1...

x(0)n0

ϕ(0)

7−→

x

(1)1...

x(1)n1

ϕ(1)

7−→ . . .

. . .ϕ(i−1)

7−→

x

(i)1...

x(i)ni

ϕ(i)

7−→

x

(i+1)1...

x(i+1)ni+1

ϕ(i+1)

7−→ . . .ϕ(r−1)

7−→

x

(r)1...

x(r)nr

ϕ(r)

7−→

x

(r+1)1...

x(r+1)nr+1

≡

y1...ym

Luego, ϕ es la composicion:

ϕ = ϕ(r) ◦ ϕ(r−1) ◦ . . . ϕ(1) ◦ ϕ(0) (22)



de r + 1 aplicaciones elementales ϕ(i) de la forma:

Rni ⊇ Di ∋

x

(i)1...

x(i)ni

= x(i) ϕ(i)

7−→ x(i+1) = ϕ(i)(x(i)) =

ϕ(i)1

(x

(i)1 , . . . , x

(i)ni

)

...

ϕ(i)ni+1

(x

(i)1 , . . . , x

(i)ni

)

∈ Di+1 ⊆ R

ni+1 ,

para i = 0 : r, con n0 = n, nr+1 = m. En lo que sigue supondremos que todas lasfunciones ϕ(i) son de clase C1.

(2) Recapitulacion de Algunas Nociones del Calculo Diferencial. Utilizare-mos la siguiente notacion: x(i) ∈ R

ni sera un vector que aproxima al vector x(i) ∈ Rni,

donde los errores absoluto y relativo de la j-esima componente vienen dados, respectiva-mente, por:

∆x(i)j = x

(i)j − x(i) = fl(x

(i)j ) − x(i) , ǫ

(i)j =

x(i)j − x

(i)j

x(i)j

. (23)

Aplicando la teorıa de las diferenciales obtenemos entonces:

∆x(i+1)j = ϕ

(i)j

(x(i))− ϕ

(i)j

(x(i))

⊜

ni∑

l=1

∂ϕ(i)j

∂x(i)ℓ

(x(i)) (

x(i)ℓ − x

(i)ℓ

)=

ni∑

l=1

∂ϕ(i)j

∂x(i)ℓ

(x(i))

∆x(i)ℓ ,

donde el sımbolo “⊜” denota una aproximacion de primer orden, i.e., con un error delorden O

(||∆x(i)||2

). Introduciendo la matriz derivada:

Dϕ(i)(x(i))

=

[∂ϕ

(i)j

∂x(i)ℓ

(x(i))]cols: ℓ=1:ni

rows: j=1:ni+1

∈M(ni+1 × ni,R), (24)

la ecuacion precedente se escribe simplemente como:

∆x(i+1)j ⊜ Dϕ(i)

(x(i)).∆x(i) (25)

Con estos antecedentes podemos estudiar ahora la propagacion de los errores al desa-rrollar el algoritmo. La propagacion de los errores vendra modelada por las funcionescompuestas:

ϕ := ϕ(r) ◦ ϕ(r−1) ◦ · · · ◦ ϕ(1) ◦ ϕ(0) : D → Rm , D ⊂R

n ,

ψ(i) := ϕ(r) ◦ ϕ(r−1) ◦ · · · ◦ ϕ(i−1) ◦ ϕ(i) : Di → Rm , Di ⊂R

ni , i = 0 : r .

Evidentemente, ψ(0) = ϕ, x(0) = x, x(r+1) = y. En vista de la identidad

D(f ◦ g)(x) = Df(g(x))Dg(x)

para funciones diferenciables cualesquiera f, g, tenemos:

Dϕ(x) = Dϕ(r)(x(r))Dϕ(r−1)

(x(r−1)

). . . Dϕ(1)

(x(1))Dϕ(0) (x) ,

Dψ(i)(x) = Dϕ(r)(x(r))Dϕ(r−1)

(x(r−1)

). . . Dϕ(i−1)

(x(i−1)

)Dϕ(i)

(x(i)).

Conviene tener presente que las derivadas que aparecenen las expresiones precedentesvienen representadas, en general, por matrices.



(3) Estimacion de los Errores Propagados en el i-esimo Paso. En aritmetica depunto flotante, bajo la influencia de un error de entrada ∆x y de los errores de redondeo,en lugar del valor exacto x(i), obtenemos el valor aproximado:

x(i+1) = fl(ϕ(i)

(x(i))).

Luego:

∆x(i+1) = x(i+1) − x(i+1) = fl(ϕ(i)

(x(i)))

− ϕ(i)(x(i))

=[fl(ϕ(i)

(x(i)))

− ϕ(i)(x(i))]

︸︷︷︸=:A

+[ϕ(i)

(x(i))− ϕ(i)

(x(i))]

︸︷︷︸=:B

.

La estimacion de B es inmediata:

B ⊜ Dϕ(i)(x(i)).∆x(i) .

Para estimar A supondremos que ϕ(i) es suficientemente simple como para que:

fl(ϕ(i)(u)

)= rounding

(ϕ(i)(u)

)∈ R

ni+1 .

Entonces, para la j-esima componente de ϕ(i) se tiene:

fl(ϕ

(i)j (u)

)= rounding

(ϕ

(i)j (u)

)= (1 + εj) ϕ

(i)j (u) ∈ R ,

donde |εj| ≤ eps, j = 1 : ni+1, es el error de redondeo inducido por el calculo de laj-esima componente de ϕ(i) en aritmetica de punto flotante. Escribiendo matricialmenteeste resultado se tiene:

fl(ϕ(i)(u)

)=

1 + ε1 0 . . . 00 1 + ε2 . . . 0...

.... . .

...0 0 . . . 1 + εni+1

ϕ(i)1 (u)

ϕ(i)2 (u)...

ϕ(i)ni+1(u)

= (I + Ei+1) .ϕ

(i)(u) ∈ Rni+1 ,

donde I denota la matriz identidad de ni+1 × ni+1 y E = diag(ε1, . . . , εni+1

). De este

modo, la componente A del error queda:

fl(ϕ(i)

(x(i)))

= (I + Ei+1) ϕ(i)(x(i))

= Ei+1 ϕ(i)(x(i))

⊜ Ei+1 ϕ(i)(x(i)).

La aproximacion “⊜” de la formula precedente queda justificada por el hecho que eltermino de error en que difieren las componentes de ϕ(i)

(x(i))

y ϕ(i)(x(i))

queda multi-plicado por los terminos en la diagonal de Ei+1, lo que da origen a terminos de error deorden superior. Entonces para A se tiene:

A ⊜ Ei+1ϕ(i)(x(i))

= Ei+1.x(i+1) =: αi+1 .

Reuniendo todos los resultados parciales obtenemos finalmente:

∆x(i+1)⊜ A+B = αi+1 +Dϕ(i)

(x(i)).∆x(i) = Ei+1.x

(i+1) +Dϕ(i)(x(i)).∆x(i),

para i = 0 : r, con ∆x(0) = ∆x.



(4) Concatenacion de todos los Errores. Aplicando recursivamente esta formulaobtenemos:

∆x(1)⊜ Dϕ(0)

(x(0)).∆x(0) + α1

∆x(2)⊜ Dϕ(1)

(x(1)).∆x(1) + α2

= Dϕ(1)(x(1)).[Dϕ(0)

(x(0)).∆x(0) + α1

]+ α2

= Dϕ(1)(x(1)).Dϕ(0)

(x(0)).∆x(0) +Dϕ(1)

(x(1)).α1 + α2

. . . . . . . . . . . .

∆y = ∆x(r+1)⊜ Dϕ(r)

(x(r)).∆x(r) + αr

= Dϕ(r)(x(r)).Dϕ(r−1)

(x(r−1)

). . .Dϕ(1)

(x(1)).Dϕ(0)

(x(0)).∆x(0)

+Dϕ(r)(x(r)).Dϕ(r−1)

(x(r−1)

). . .Dϕ(1)

(x(1)).α1


(x(r−1)

). . .Dϕ(2)

(x(2)).α2

. . . . . . . . . . . .


(x(r−1)

).αr−1

+Dϕ(r)(x(r)).αr

+αr+1

Por consiguiente se tiene:

∆y ⊜ Dϕ(x).∆x+Dψ(1)(x(1)).α1 +Dψ(2)

(x(2)).α2 + · · ·+Dψ(r)

(x(r)).αr + αr+1 ,

esto es:

∆y ⊜ Dϕ(x).∆x+

r∑

i=1

Dψ(i)(x(i)).Ei.x

(i) + Er+1.y (26)

Por consiguiente, el punto mas crıtico para el efecto de los errores de redondeo intermediosαi o Ei en el resultado final es el tamano de Dψ(i)

(x(i)).

(5) Observacion. Si se elige otro algoritmo para calcular y = ϕ(x) ∈ Rm, x ∈ R

n, esto es,otra descomposicion de ϕ en transformaciones elementales ϕ(i), entonces Dϕ no cambiapero las matrices Dψ(i) que controlan la propagacion de los errores de redondeo, sı puedenhacerlo y, en consecuencia, tambien puede cambiar el efecto total de todos los errores deredondeo, que viene dado por:

Dψ(1).α1 + · · ·+Dψ(r).αr + αr+1 . (27)

Se dice que un algoritmo A es numericamente mas estable que otro algoritmo A′ paracalcular la misma expresion y = ϕ(x), si el efecto total de los errores de redondeo produ-cido por el algoritmo A es menor que el efecto total de los errores de redondeo producidopor el algoritmo A′

(6) Observacion. En la ecuacion (26), para el ultimo termino αr+1 = Er+1.y, se tiene laestimacion:

|αr+1| = |Er+1.y| ≤ eps |y| , (28)

independientemente del algoritmo utilizado para calcular y = ϕ(x). Por consiguiente, concualquier algoritmo es necesario contar con un error del orden de eps |y|.

(7) Observacion. En este apartado (y en particular en la ecuacion (28)), los valoresabsolutos de vectores, matrices, etc., deben entenderse por componentes. Por ejemplo,|y| = [ |y1|, . . . , |ym| ]T ,

∣∣[aij ]m×n

∣∣ = [ |aij | ]m×n.



(8) Observacion. Por otro lado, si se utiliza una maquina con palabras de t celdas, elsimple redondeo de los datos de entrada [x1, . . . , xn]T a t celdas ya produce un error deentrada ∆(0) con:

|∆(0)x| ≤ eps |x| ,excepto cuando los datos de entrada pueden representarse exactamente mediante las pala-bras disponibles. Por esta razon, en el calculo de y = ϕ(x) mediante el algoritmo que sea,tambien habra que tener inevitablemente en cuenta un error del orden de |Dϕ(x)| |x| eps.Por consiguiente, independientemente del algoritmo elegido, un error del orden de:

∣∣∆(0)y∣∣ := eps [ |Dϕ(x)| |x| + |y| ] . (29)

sera siempre inevitable. ∆(0)y se llama error inevitable de y.(9) Observacion. Puesto que un error del orden de (29) siempre estara presente en los

calculos, no serıa juicioso exigir, por ejemplo, que:

|αi| ≪∣∣∆(0)y

∣∣

15. Considere el siguiente algoritmo:

x = x(0) =

[ab

]ϕ(0)

−→ x(1) =

[a/bb

]ϕ(1)

−→ x(2) =

[a/b

b− a/b

]ϕ(2)

−→ x(3) =a/b

b− a/b= y

(a) Estudie el problema de la propagacion de los errores en un sistema computacional conerror de maquina eps, tal como lo discutimos en clases. Mas especıficamente, obtenga unaexpresion para ∆y en terminos de ∆a, ∆b, la derivada Dϕ en el punto (a, b) ∈ R

2, y lasderivadas Dψ(k) en los puntos correspondientes.

Preste atencion al hecho que las operaciones computacionales a∗

/b y a∗− b no coinciden con las

operaciones aritmeticas a/b y a − b, respectivamente. Note que el algoritmo incluye divisionpor b, de modo que se debe suponer b 6= 0.

(b) Grafique cualitativamente el efecto total de redondeo TER en funcion de a/b, especialmentepara valores pequenos de b

Desarrollo. (a) De la definicion del algoritmo puede leerse directamente:

ϕ(0)(u, v) =

[u/vv

], ϕ(1)(u, v) =

[u

v − u

], ϕ(2)(u, v) =

u

v,

ϕ(u, v) = ϕ(2) ◦ ϕ(1)(u, v) ◦ ϕ(0)(u, v) =u/v

v − u/v=

u

v2 − u,

ψ(1)(u, v) = ϕ(2) ◦ ϕ(1)(u, v) =u

v − u, ψ(2)(u, v) = ϕ(2)(u, v) =

u

v,

Dϕ(a, b) =

[b2

(b2 − a)2, − 2ab

(b2 − a)2

],

Dψ(1)(a/b, b) =

[b3

(b2 − a)2, − ab

(b2 − a)2

], Dψ(2)(a/b, b− a/b) =

[b

b2 − a, − b2

(b2 − a)2

],

En los calculos que siguen se requiere de una estimacion de u∗

/v y v − u. Primeramenteobservemos que para |ε| ≤ eps ≪ 1/2 se tiene:

1 − 2|ε| ≤ 1 − |ε| ≤ 1

1 + |ε| ≤1

1 + ε≤ 1

1 − |ε| ≤ 1 + 2|ε| .



Luego, para |ε•| ≤ eps ≪ 1/2 se tiene:

u∗

/v = (1 + εdiv)(1 + εu)u

(1 + εv)v≥ (1 − eps)2 (1 − 2 eps)

u

v≈ (1 − 4 eps)

u

v,

u∗

/v = (1 + εdiv)(1 + εu)u

(1 + εv)v≤ (1 + eps)2 (1 + 2 eps)

u

v≈ (1 + 4 eps)

u

v,

de modo que podemos escribir:

u∗

/v = (1 + ε1)u

vcon |ε1| ≤ 4eps . (30)

El analisis de u∗− v es similar. Estudiaremos aquı solo el caso (1 − eps)u > (1 + eps)v > 0.

Los demas casos se analizan de manera similar. Se observa que:

u∗− v = (1 + εres) ((1 + εu)u− (1 + εv)v) = (1 + εres)

(1 +

εu u+ εv v

u− v

)(u− v) .

Definiendo:

ε∗ =εu u+ εv v

u− v,

podemos escribir:

u∗− v = (1 + εres) (1 + ε∗) (u− v) ≈ (1 + εres + ε∗) (u− v) = (1 + ε2) (u− v) , (31)

donde ε2 := εres + ε∗. Notese que ε∗ y, en consecuencia el error relativo ε2, pueden ser muygrandes pues la diferencia u−v > 0 puede ser arbitrariamente pequena. Sin embargo, el errorabsoluto ε2 permanece bien acotado:

|ε2 (u− v)| = |εres + ε∗| |u− v|≤ |εres| |u− v| + |ε∗| |u− v|≤ |εres| |u− v| + |εu u+ εv v|≤ eps |u− v| + eps |u| + eps |v|≤ eps (|u− v| + |u| + |v|) .

Esto significa que la operacion u− v hace perder control sobre los errores relativos cuando ladiferencia u−v es muy pequena. No obstante, los errores absolutos se mantienen bajo control.



Sobre la base de los resultados precedentes (30) y (31) podemos calcular ahora:

fl(ϕ(0)(a, b)

)− ϕ(0)(a, b) =

[a∗

/bb

]−[a/bb

]

=

[a∗

/b− a/b0

]=

[ε1 a/b

0

]=

[ε1 00 0

] [a/bb

]=: E1 x

(1) , (32)

fl(ϕ(1)(a/b, b)

)− ϕ(1)(a/b, b) =

[a/b

b∗− a/b

]−[

a/bb− a/b

]

=

[0

(b∗− a/b) − (b− a/b)

]=

[0

ε2 (b− a/b)

]=

[0 00 ε2

] [0

b− a/b

]=: E2 x

(2) , (33)

fl(ϕ(2)(a/b, b− a/b)

)− ϕ(2)(a/b, b− a/b) = (a/b)

∗

/(b− a/b) − (a/b)/(b− a/b)

= (1 + ε1)a/b

b− a/b− (a/b)/(b− a/b) = ε1

a/b

b− a/b=: α3 . (34)

Reuniendo los resultados (32),(33) y (34) con las expresiones obtenidas para Dϕ y Dψ(i)

podemos escribir la expresion pedida ∆y:

∆y = Dϕ(a, b).∆x+Dψ(1)(x(1)).E1.x(1) +Dψ(2)(x(2)).x(2) + α3

=

[b2

(b2 − a)2, − 2ab

(b2 − a)2

] [∆a∆b

]+

[b3

(b2 − a)2, − ab

(b2 − a)2

] [ε1 a/b

0

]

+

[b

b2 − a, − b2

(b2 − a)2

] [0

ε2 (b− a/b)

]+ ε1

a/b

b− a/b

=b2 ∆a

(b2 − a)2− 2ab∆b

(b2 − a)2+ ε1

b3

(b2 − a)2

a

b− ε2

b2

(b2 − a)2(b− a/b) + ε1

a/b

b− a/b

=∆a

(b− a/b)2− 2(a/b) ∆b

(b− a/b)2+ ε1

a

(b− a/b)2− ε2

b− a/b+ ε1

a/b

b− a/b.

El TER (total effect of rounding) queda explicitado en la expresion anterior:

TER = ε1a

(b− a/b)2− ε2

b− a/b+ ε1

a/b

b− a/b.

La grafica de TER en funcion del parametro a/b es “straightforward”.

Aritmetica de Punto Flotante.

16. Hurgando en la web dimos con la siguiente interesante contribucion de Steve Hollasch.Estudiela crıticamente, ası como el texto de Stallings en el cual se basa.

IEEE Standard 754 Floating Point Numbers. By Steve Hollasch (2003.Jan.02).http:// research.microsoft.com/~hollasch/cgindex/coding/ieeefloat.html

http://standards.ieee.org/

IEEE Standard 754 floating point is the most common representation today for real numberson computers, including Intel-based PC’s, Macintoshes, and most Unix platforms. This articlegives a brief overview of IEEE floating point and its representation. Discussion of arithmeticimplementation may be found in the book mentioned at the bottom of this article.



What Are Floating Point Numbers? There are several ways to represent real numberson computers. Fixed point places a radix point somewhere in the middle of the digits, andis equivalent to using integers that represent portions of some unit. For example, one mightrepresent 1/100ths of a unit; if you have four decimal digits, you could represent 10,82, or00,01. Another approach is to use rationals, and represent every number as the ratio of twointegers.

Floating-point representation –the most common solution– basically represents reals in scien-tific notation. Scientific notation represents numbers as a base number and an exponent. Forexample, 123,456 could be represented as 1,23456× 102. In hexadecimal, the number 123.abcmight be represented as 1,23abc× 162.

Floating-point solves a number of representation problems. Fixed-point has a fixed windowof representation, which limits it from representing very large or very small numbers. Also,fixed-point is prone to a loss of precision when two large numbers are divided.

Floating-point, on the other hand, employs a sort of “sliding window” of precision appropriateto the scale of the number. This allows it to represent numbers from 1,000,000,000,000 to0.0000000000000001 with ease.

Storage Layout. IEEE floating point numbers have three basic components: the sign, theexponent, and the mantissa. The mantissa is composed of the fraction and an implicit leadingdigit (explained below). The exponent base (2) is implicit and need not be stored.

The following figure shows the layout for single (32-bit) and double (64-bit) precision floating-point values. The number of bits for each field are shown (bit ranges are in square brackets):

Sign Exponent Fraction Bias

Single Precision 1 [31] 8 [30-23] 23 [22-00] 127

Double Precision 1 [63] 11 [62-52] 52 [51-00] 1023

The Sign Bit. The sign bit is as simple as it gets. 0 denotes a positive number; 1 denotesa negative number. Flipping the value of this bit flips the sign of the number.

The Exponent. The exponent field needs to represent both positive and negative expo-nents. To do this, a bias is added to the actual exponent in order to get the stored exponent.For IEEE single-precision floats, this value is 127. Thus, an exponent of zero means that 127is stored in the exponent field. A stored value of 200 indicates an exponent of (200-127), or73. For reasons discussed later, exponents of -127 (all 0s) and +128 (all 1s) are reserved forspecial numbers. For double precision, the exponent field is 11 bits, and has a bias of 1023.

The Mantissa. The mantissa, also known as the significand, represents the precision bitsof the number. It is composed of an implicit leading bit and the fraction bits.

To find out the value of the implicit leading bit, consider that any number can be expressedin scientific notation in many different ways. For example, the number five can be representedas any of these:

5,00 × 100 0,05 × 102 5000 × 10−3

In order to maximize the quantity of representable numbers, floating-point numbers are ty-pically stored in normalized form. This basically puts the radix point after the first non-zerodigit. In normalized form, five is represented as 5,0 × 100.



A nice little optimization is available to us in base two, since the only possible non-zero digitis 1. Thus, we can just assume a leading digit of 1, and don’t need to represent it explicitly.As a result, the mantissa has effectively 24 bits of resolution, by way of 23 fraction bits.

Putting it All Together. So, to sum up:

(1) The sign bit is 0 for positive, 1 for negative.(2) The exponent’s base is two.(3) The exponent field contains 127 plus the true exponent for single-precision, or 1023 plus

the true exponent for double precision.(4) The first bit of the mantissa is typically assumed to be 1.f , where f is the field of fraction

bits.

Ranges of Floating-Point Numbers. Let’s consider single-precision floats for a second.Note that we’re taking essentially a 32-bit number and re-jiggering the fields to cover a muchbroader range. Something has to give, and it’s precision. For example, regular 32-bit integers,with all precision centered around zero, can precisely store integers with 32-bits of resolution.Single-precision floating-point, on the other hand, is unable to match this resolution with its24 bits. It does, however, approximate this value by effectively truncating from the lower end.For example:

11110000 11001100 10101010 00001111 32-bit integer=+1.1110000 11001100 10101010 ×231 Single-precision float= 11110000 11001100 10101010 00000000 Corresponding value

This approximates the 32-bit value, but doesn’t yield an exact representation. On the otherhand, besides the ability to represent fractional components (which integers lack comple-tely), the floating-point value can represent numbers around 2127, compared to 32-bit integersmaximum value around 232.

The range of positive floating point numbers can be split into normalized numbers (whichpreserve the full precision of the mantissa), and denormalized numbers (discussed later) whichuse only a portion of the fractions’s precision.

Single Precision Double Precision

Denormalized ±2−149 to (1 − 2−23) × 2−126 ±2−1074 to (1 − 2−52) × 2−1022

Normalized ±2−126 to (2 − 2−23) × 2127 ±2−1022 to (2 − 2−52) × 21023

Approximate Decimal ∼ ±10−44,85 to ∼ 1038,53 ∼ ±10−323,3 to ∼ 10308,3

Since the sign of floating point numbers is given by a special leading bit, the range for negativenumbers is given by the negation of the above values.

There are five distinct numerical ranges that single-precision floating-point numbers are notable to represent:

(1) Negative numbers less than −(2 − 2−23) × 2127 (negative overflow)(2) Negative numbers greater than −2−149 (negative underflow)(3) Zero(4) Positive numbers less than 2−149 (positive underflow)(5) Positive numbers greater than (2 − 2−23) × 2127 (positive overflow)

Overflow means that values have grown too large for the representation, much in the sameway that you can overflow integers. Underflow is a less serious problem because is just denotesa loss of precision, which is guaranteed to be closedly approximated by zero.



Operation Result

n/±∞ 0

±∞×±∞ ±∞±nonzero/0 ±∞∞ + ∞ ∞±0/± 0 NaN

∞−∞ NaN

±∞/±∞ NaN

±∞× 0 NaN

Figura 1. Table on operations on special numbers.

Here’s a table of the effective range (excluding infinite values) of IEEE floating-point numbers:

Binary Decimal

Single ±(2 − 2−23)127 ∼ ±1038,53

Double ±(2 − 2−52)1023 ∼ ±10308,25

Note that the extreme values occur (regardless of sign) when the exponent is at the maximumvalue for finite numbers (2127 for single-precision, 21023 for double), and the mantissa is filledwith 1’s (including the normalizing 1 bit).

Special Values. IEEE reserves exponent field values of all 0’s and all 1’s to denote specialvalues in the floating-point scheme.

Zero. As mentioned above, zero is not directly representable in the straight format, due tothe assumption of a leading 1 (we’d need to specify a true zero mantissa to yield a value ofzero). Zero is a special value denoted with an exponent field of zero and a fraction field ofzero. Note that −0 and +0 are distinct values, though they both compare as equal.

Denormalized. If the exponent is all 0’s, but the fraction is non-zero (else it would beinterpreted as zero), then the value is a denormalized number, which does not have an assumedleading 1 before the binary point. Thus, this represents a number (−1)s × 0.f × 2−126, wheres is the sign bit and f is the fraction. For double precision, denormalized numbers are of theform (−1)s × 0.f × 2−1022. From this you can interpret zero as a special type of denormalizednumber.

Infinity. The values +∞ and −∞ are denoted with an exponent of all 1’s and a fraction ofall 0’s. The sign bit distinguishes between negative infinity and positive infinity. Being ableto denote infinity as a specific value is useful because it allows operations to continue pastoverflow situations. Operations with infinite values are well defined in IEEE floating point.

Not A Number. The value NaN (Not a Number) is used to represent a value that does notrepresent a real number. NaN’s are represented by a bit pattern with an exponent of all 1’sand a non-zero fraction. There are two categories of NaN’s: QNaN (Quiet NaN ) and SNaN(Signalling NaN ).



A QNaN is a NaN with the most significant fraction bit set. QNaN’s propagate freely throughmost arithmetic operations. These values pop out of an operation when the result is notmathematically defined.

An SNaN is a NaN with the most significant fraction bit clear. It is used to signal an exceptionwhen used in operations. SNaN’s can be handy to assign to uninitialized variables to trappremature usage.

Semantically, QNaN’s denote indeterminate operations, while SNaN’s denote invalid opera-tions.

Special Operations. Operations on special numbers are well-defined by IEEE. In thesimplest case, any operation with a NaN yields a NaN result. Other operations are presentedin Figure 1.

Summary. To sum up, the corresponding values for a given representation are presentedin Figure 2.

References. A lot of this stuff was observed from small programs I (Hollash) wrote to goback and forth between hex and floating point (printf-style), and to examine the results ofvarious operations. The bulk of this material, however, was lifted from Stallings’ book.

[1 ] William Stallings. Computer Organization and Architecture. Macmillan PublishingCompany, ISBN 0-02-415480-6. Pp. 222–234.Version en Castellano: Organizacion y Arquitectura de Computadores. Quinta edicion.Traduccion: Antonio Canas Vargas, Julio Ortega Lopera, Francisco Jose Pelayo Valle,Beatriz Prieto Campos; coordinacion y revision tecnica: Alberto Prieto Espinosa; todosdel Departamento de arquitectura y tecnologıa de computadores de la Universidad deGranada. Pearson Educacion S.A./Prentice Hall, Madrid, 2000.

[2 ] IEEE Computer Society (1985). IEEE Standard for Binary Floating-Point Arithmetic.IEEE Std 754-1985.

[3 ] Intel Architecture Software Developer’s Manual, Volume 1: Basic Architecture (a PDFdocument downloaded from intel.com).

[4 ] IEEE Standards Site

c©2003, Steve Hollasch

17. [6, p. 101, exc. 13.1] En el sistema aritmetico IEEE, ¿cuantos numeros de doble precisionhay entre dos numeros no nulos adyacentes de precision simple? Recuerde que el sistemaidealizado de numeros de punto flotante se define como:

F = {0} ∪{±(m/βt)βe : m ∈ N, βt−1 ≤ m ≤ βt − 1 , e ∈ Z

},

donde la base β es tıpicamente 2 (en general, β ≥ 2) y la precision t, en el sistema aritmeticoIEEE, es 24 para precision simple y 53 para precision doble.

18. [6, p. 101, exc. 13.2] (slightly modified!). El sistema de punto flotante F contiene muchosenteros pero no todos ellos. (a) Obtenga una formula exacta para el menor entero positivo nque no pertenece a F.(b) Calcule n para las aritmeticas de precision IEEE simple y doble, respectivamente.(c) Determine

∑0<k∈F

1/k y∑

0<k∈Z\F

1/k.

(d) Sea {nk}k∈Nla sucesion (estrictamente creciente) de todos los numeros naturales con las

propiedades nk − 1 ∈ F y nk 6∈ F. Determine∑k∈N

1/nk .



Float Values (b = bias)Sign Exponent (e) Fraction (f) Value

0 00 . . . 00 00 . . . 00 +000 . . . 01 Positive Denormalized Real

0 00 . . . 00... 0.f × 2(−b+1)

11 . . . 1100 . . . 01 Positive Normalized Real

0... XX . . .XX 1.f × 2(e−b)

11 . . . 100 11 . . . 11 00 . . . 00 +∞

00 . . . 01

0 11 . . . 11... SNaN

01 . . . 1110 . . . 00

0 11 . . . 11... QNaN

11 . . . 111 00 . . . 00 00 . . . 00 −0

00 . . . 01 Negative Denormalized Real

1 00 . . . 00... −0.f × 2(−b+1)

11 . . . 1100 . . . 01 Negative Normalized Real

1... XX . . .XX −1.f × 2(e−b)

11 . . . 101 11 . . . 11 00 . . . 00 −∞

00 . . . 011 11 . . . 11 . . . SNaN

01 . . . 1110 . . . 00

1 11 . . . 11... QNaN

11 . . . 11

Figura 2. Float Values (b =bias).

19. [6, p. 101, exc. 13.3] (slightly modified!). Obtenga sendas estimaciones L y U para elinfimum y el supremum de la expresion

A = (x−2)9 −x9 +18x8 −144x7 +672x6−2016x5 +4032x4−5376x3 +4608x2−2304x+512 ,

sobre el intervalo [−1, 920; 2, 080 ] computando mediante un sistema aritmetico IEEE deprecision simple. ¿Podrıa disminuir el valor de la diferencia U − L si calcula el polinomioexpandido mediante el esquema de Horner?

20. [3, Ch. 1, Sec. 2, pp. 17–21] Los errores aritmeticos estan inevitablemente presentes en loscalculos efectuados mediante computadores digitales. La llamada aritmetica de punto flotantees una de las formas estandar de la computacion numerica. Aunque los computadores digi-tales usualmente representan los numeros en forma binaria, (la mayor parte de) los humanospensamos (hoy dıa) en terminos de una representacion decimal. Por esta razon, el presente



ejercicio esta planteado en terminos “decimales”. No obstante, el (la) estudiante despierto(a)no dejara pasar la oportunidad de: (i) investigar que pasa si se sustituye la base decimalβ = 10 por una base cualquiera 2 ≤ β ∈ N, (ii) investigar mas detenidamente la normadel IEEE relativa a la representacion interna de numeros en los computadores digitales de lapresente generacion, en particular lo concerniente a representaciones de precision simple (24bits) y precision doble (53 bits).

Si a 6= 0 tiene una representacion decimal exacta:

a = ±0.d1d2d3 · · · × 10q q ∈ Z , di ∈ N0 , 0 ≤ di ≤ 9 , d1 6= 0 , (35)

entonces la representacion decimal de punto flotante de a con t dıgitos o, brevemente, elflotante del a tiene la forma:

fl(a) = ±0.δ1δ2δ3 . . . δt × 10q q ∈ Z , δi ∈ N0 , 0 ≤ δi ≤ 9 , δ1 6= 0 t ∈ N . (36)

El numero 0.δ1δ2δ3 . . . δt se llama mantisa y q exponente de fl(a). En discusiones teoricasse supone a menudo que el exponente q puede adoptar cualquier valor entero, aunque esto,obviamente, no es muy realista. En la practica, usualmente, q satisface una restriccion de laforma:

−N ≤ q ≤M , N,M ∈ N “grandes”. (37)

Si para un numero a 6= 0 se tiene q 6∈ [−N,M ] , entonces el flotante de a no esta definido. Si enel curso de una computacion se obtiene q < −N , se habla de “underflow” y si q > M se diceque ha ocurrido un “overflow”. Hay dos maneras populares de obtener los dıgitos flotantes δia partir de los dıgitos exactos di: truncamiento y redondeo. Para el truncamiento se tiene:

δi = di , i = 1, 2, . . . , t , (38)

es decir, simplemente se omiten todos los dıgitos con ındice mayor que t. Para el redondeo setiene:

δ1δ2δ3 . . . δt = [d1d2d3 . . . dt . dt+1 + 0,5] , (39)

donde [x] denota la parte entera de x ∈ R (note la ubicacion del punto decimal en el miembroderecho de (39)). En ambos casos se puede obtener una cota para el error introducido. Enefecto:

Lema 1. El error (absoluto) en la representacion de punto flotante de un numero decimala 6= 0 con mantisa de t dıgitos viene acotado por:

|a− fl(a)| ≤{

5|a|10−t , caso de redondeo ,|a|10−t+1 , caso de truncamiento .

(40)

(a) Demuestre (o corrija) el Lema 1.

Supongamos ahora que la unidad aritmetica del computador ideal con el que trabajamos,es capaz de realizar internamente las operaciones basicas con 2t dıgitos correctos y luego lostransfiere al buffer de salida como un numero de punto flotante de t dıgitos, ya sea redondeandoo bien truncando. Entonces se tiene:

fl(a± b) = (a± b)(1 + η10−t) ,fl(ab) = ab(1 + η10−t) ,

fl(ab

)=a

b(1 + η10−t) ,

, donde

{0 ≤ |η| ≤ 5 , caso de redondeo ,0 ≤ |η| ≤ 10 , caso de truncamiento ,

(41)(b) Demuestre (o corrija) (41).



En muchos calculos, particularmente en los concernientes a sistemas lineales se requiere laacumulacion de productos parciales (e.g., en el calculo del producto interno de dos vectores). Sise supone que tras cada multiplicacion ocurre redondeo o truncamiento, al igual que despues decada suma sucesiva, entonces el flotante del producto interno de dos vectores a = (a1, . . . , an),b = (b1, . . . , bn), se puede expresar recursivamente mediante la formula:

fl

(n∑

i=1

aibi

)= fl

[fl

(n−1∑

i=1

aibi

)+ fl(anbn)

]. (42)

El resultado de tales calculos se puede representar como un producto interno exacto alterandolevemente, por ejemplo, los ai’s:

Lema 2. Supongase que la dimension n de los vectores y el numero t de dıgitos de las mantisasen nuestro computador ideal satisfacen:

n 101−t ≤ 1 . (43)

Entonces, para el producto interno de punto flotante (42) computado mediante redondeo sis-tematico en todas las operaciones se tiene:

fl

(n∑

i=1

aibi

)=

n∑

i=1

(ai + δai)bi , (44)

donde|δai| ≤ n|ai|101−t , |δai| ≤ (n− i+ 2)|ai|101−t , i = 2, 3 . . . , n . (45)

(c) Demuestre (o corrija) (44), (45). Investigue que ocurre si se en el Lema 2 se sustituye“redondeo” por “truncamiento”.

21. [3, Ch. 1, Sec. 2, p. 21, probl. 2]

(a) Obtenga una representacion (¡formula!) para fl

(n∑

i=1

ci

)(en terminos de los fl(ci) ).

(b) Si c1 > c2 > . . . > cn > 0 , ¿en que orden habrıa que calcular fl

(n∑

i=1

ci

)para minimizar

los efectos de redondeo (resp., truncamiento)?

Referencias

[1] Casiodoro de Reina and Cipriano de Valera. Santa Biblia. Antiguo y Nuevo Testamentos. Editorial MundoHispano, El Paso, TX 79914, USA, 1990. Breve nota historica. Se trata de la version Reina-Valera actuali-zada. En los primeros siglos de nuestra era, estaban en uso hasta cuatro traducciones, o versiones, griegasdel Antiguo Testamento, y varias traducciones de ambos testamentos en latın, arameo y otros idiomas. Sinembargo, durante la Edad Media las autoridades eclesiasticas no permitıan hacer revisiones, de modo quela Vulgata (traduccion latina cuyo nombre expresa su proposito de llegar al vulgo, o sea al pueblo comun)y la Peshita (traduccion aramea cuyo nombre significa ”sencilla”) dejaron gradualmente de ser entendidas.En cuanto a las versiones de la Biblia en Castellano, Reina hizo la primera de toda la Biblia, basada enlos idiomas originales, hacia 1569. Pero utilizo las parciales que ya existıan (del Nuevo Testamento o delAntiguo Testamento, o parte de ellos), como las de Juan Perez, de Ferrara y de Santes Pagnino. Despuesde diez anos, Cipriano de Valera se aboco a la tarea de revisar la obra de Reina, y el resultado de su laborfue publicado en 1602 bajo su nombre. Durante 300 anos su obra y las revisiones subsecuentes llevabansolo el nombre de Valera. Pero las publicaciones del siglo XX asocian su labor con la de Reina, por lo queahora se la llama Version de Reina-Valera de la Biblia. (Cf. Introduccion, pag. v, de la misma obra.).

[2] M. T. Heath. Scientific Computing. An Introductory Survey. McGraw-Hill, New York, 2002.[3] E. Isaacson and H.B. Keller. Analysis of Numerical Methods. John Wiley and Sons, New York, 1966. There

is a more recent edition by Dover, NewYork, 1994.[4] J. Stoer. Numerische Mathematik 1. Springer Verlag, Berlin-Heidelberg, 7. edition, 1994.

L. Salinas + O. Orellana + G. Hernandez/ Computacion Cientıfica I/15˜de abril de˜2006


[5] J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer Verlag, Berlin-Heidelberg, 1993. Arather advanced but very good book indeed!

[6] L.N. Trefethen and D. Bau III. Numerical Linear Algebra. Society for Industrial and Applied Mathematics(SIAM), Philadelphia, 1997. A very good book indeed! More advanced than Strang’s book.

LSC/lsc, 15 de abril de 2006


Computaci´on Cient´ıﬁca I, 2006 Gu´ıa No 1 Valpara´ıso...

Documents

Transcript of Computaci´on Cient´ıﬁca I, 2006 Gu´ıa No 1 Valpara´ıso...