Analisis de errores

Acceder a la precision de los resultados de los calculos es una metaimportante en el analisis numerico. Podemos distinguir variasclases de error que pueden limitar esta precision:

Errores en los datos de entrada, provocados por limitacionesy/o imperfecciones de los instrumentos fsicos;

Errores de redondeo, por el calculo de numeros que estanrepresentados con un numero finito de dgitos;

Errores de aproximacion, cuando aproximamos la solucion deun problema P resolviendo un problema P. Un ejemplo deesto es la aproximacion de una suma infinita por otra finita;

e 1 + 11!

+1

2!+ + 1

N !

El error resultante de aproximacion es llamado comunmente errorde truncamiento. Lo que hacemos es discretizar un problema: porejemplo cocientes diferenciales son aproximados por cocientes dediferencias, integrales definidas por sumas finitas, etc. En dichoscasos, el error de aproximacion es llamado error de discretizacion.En este captulo se analizaran los dos primeros tipos de errores.

Representacion de numeros

Se tienen dos tipos de maquinas para representar los numeros:

1 Computadoras analogicas, se caracterizan por resolver unproblema matematico simulandolo por un problema fsico,resolviendolo por medicion y retornando un resultado. Losnumeros son representados por cantidades fsicas, como porejemplo, la longitud de una barra o la intensidad de unvoltaje. Es claro que la precision de los dispositivos analogicosse encuentra directamente limitada por las mediciones fsicasque emplean.

2 Computadoras digitales, entre las cuales tenemos las PCs;expresan los dgitos de la representacion de un numero poruna secuencia discreta de cantidades fsicas. Un ejemplo deesto es la representacion del numero binario 11010110 conuna secuencia de ocho diodos: el 1 se representa con el diodoencendido, y el 0 con el diodo apagado.

La representacion de dgitos en computadoras digitales no requieretanta precision como la representacion de numeros en lascomputadoras analogicas. Nosotros estudiaremos este tipo decomputadoras.

Un numero entero N se puede representar como

N = (npn + n1pn1 + + 0)

donde p N, p > 1 es la base del sistema de numeracion yi

{0, 1, . . . , (p 1)} ,

i = 0, 1, . . . , n

Ejemplo

El numero 18 (base 10) admite la descomposicion en base 2:

18 = 1 24 + 0 23 + 0 22 + 1 21 + 0 20 = 10010(2)Un numero arbitrario se puede representar, en particular, en base 2,como:

x = (n2n + n12n1 + + o20 + 121 + 222 + )

donde i {0, 1}. Para cualquier otra base se puede realizar estode manera analoga.

En las computadoras digitales se ha de representar los numeros conun numero finito de lugares, la longitud de palabra. Larepresentacion de punto fijo especifica un numero fijo n1 de lugaresantes de y un numero fijo n2 de lugares despues del punto decimal(binario), tales que n = n1 + n2 = longitud de palabra(usualmente n1 = 0 o n1 = n). De este modo, un numero x serepresenta en la maquina como (en base 2)

x = (n112n11 + n122n12 + + 020 + 121 + 222 + + n22n2)

Ejemplo

Para n = 10, n1 = 4, n2 = 6

145,6132 0145 613200

En esta representacion, la posicion del punto decimal (binario) esfija.

Representacion de numeros con punto flotante

Mas importante es la representacion de punto flotante. Aqu elpunto decimal (binario) no se encuentra fijo. Esto es hecho con unexponente. Cada numero puede ser representado en la forma

x = a 10b(x = a 2b) con |a| < 1, b entero

Ejemplo

30,421 = 0,30241 102.

El exponente b indica la posicion del punto decimal con respecto ala mantisa a. Rutishauser propuso la notacion : 0,30241102En cada computadora existen, por supuesto, numeros finitos t y e,n = t+ e, de lugares disponibles para la representacion de mantisay exponente, respectivamente.

Ejemplo

Para t = 4, e = 2, el numero 5420 en el sistema decimal se expresa:

0 5420 10 04

o bien5420 04

Representacion de numeros normalizada

Una representacion de punto flotante es normalizada si el primerdgito de la mantisa es distinto de 0. Entonces |a| 101 (|a| 21). Los dgitos significativos (bits) de un numero son losdgitos de la mantisa sin contar ceros al principio.En lo que sigue, consideraremos solamente representaciones depunto flotante y su aritmetica de punto flotante correspondiente.Los numeros t y e, junto con la base B, determinan el conjuntoA R de los numeros reales que pueden ser representadosexactamente con una computadora dada. Los elementos de A sonllamados numeros de maquina.

Errores de redondeo y aritmetica de punto flotante

El conjunto A de numeros de maquina es finito. Luego surgen laspreguntas: Como representar un numero x / A ? Ademas, dadosdos numeros de maquina, es posible que su suma o su producto nosean numeros de maquina.Es natural postular que la aproximacion de cualquier numerox / A por un numero de maquina rd(x) deba cumplir la condicion

x rd(x) |x g|, para todo g A.

Ejemplo

Para t = 4

rd(0,14285100) = 0,1429100rd(3,14159100) = 0,3142101

En general se procede como sigue: x / A se normaliza primero ax = a 10b, donde |a| 101. Supongamos que la representaciondecimal de |a| es dada por

|a| = 0.12 . . . ii+1 . . . , 0 i 9, 1 6= 0.

Entonces se forma

a :={

0.12 . . . t si 0 t+1 4,0.12 . . . t + 10

t si t+1 5

Finalmente se coloca

rd(x) := sign(x) a 10b.

Nota

Cuando se aproxima un numero real x mediante otro numero x elerror que resulta es (x x). El error absoluto es |x x| y el errorrelativo es

x x

x

x x

x

si x 6= 0.El error relativo de aproximar x por rd(x) es (recordar que|a| 101)

rd(x) xx

5 10(t+1)|a| 5 10t.

Con la abreviacion eps = 5 10t podemos escribir

rd(x) = x(1 + ), con || eps .

La cantidad eps = 5 10t es llamada precision de la maquina.En el sistema binario, podemos definir todo lo anterioranalogamente.

Siempre que rd(x) A, se podra definir correctamenterd(x) := rd(x). Sin embargo, esto no siempre ocurre como semuestra en el siguiente ejemplo.

Ejemplo

Para t = 4, e = 2 tenemos

rd(0,3197410110) = 0,319710110 / Ard(0,999971099) = 0,100010100 / Ard(0,01234510 99) = 0,123510 100 / Ard(0,5432110 110) = 0,543210 110 / A

En el primer y segundo caso el exponente es muy grande para elespacio: entonces tenemos un overflow de exponente (sobreflujo).El tercer y cuarto casos son instancias de un underflow, esto es, elexponente del numero representado es muy negativo. En estoscasos podemos prevenir el underflow definiendo

rd(0,01234510 99) = 0,012310 99 A.

rd(0,5432110 110) = 0 A.

Como el overflow y el underflow son poco frecuentes y requierenun tratamiento especial, para simplificar la teora asumiremos enadelante que e = . De este modo tendremos rd := rd, yaseguraremos que

rd : R Ard(x) = x(1 + ) con || eps, x R.

Como los resultados de las operaciones aritmeticas no sonnecesariamente numeros de maquina, requeriremos definiroperaciones de punto flotante, +,, , /, las cuales sondefinidas como:

x+ y := rd(x+ y),x y := rd(x y),x y := rd(x y),x/y := rd(x/y),

para x, y A,

lo cual implica

x+ y := (x+ y)(1 + 1)x y := (x y)(1 + 2)x y := (x y)(1 + 3)x/y := (x/y)(1 + 4)

|i| eps .

De lo anterior se observara que las operaciones de punto flotanteno satisfacen las leyes conocidas para las operaciones aritmeticasusuales. Por ejemplo,

x+ y = x, si |y| < epsB|x|, x, y A

La precision de maquina eps puede tambien definirse entoncescomo

eps = mn{g A/1 + g > 1 g > 0}.

Ademas, las operaciones de punto flotante no son asociativas odistributivas.Ejemplo:t = 8 Con

a := 0,2337125810 4,b := 0,33678429102,c := 0,33677811102.

a+ (b+ c) = 0,2337125810 4 + 0,6180000010 3,= 0,6413712610 3,

(a+ b) + c = 0,33678452102 0,33677811102,= 0,6410000010 3.

El resultado exacto es

a+ b+ c = 0,64137125810 3.

Propagacion de errores

Para expresar el resultado de operaciones de punto flotante, unanotacion ha sido ampliamente aceptada, y la usaremosfrecuentemente: dada una expresion E a calcular, fl(E) denota elvalor de la expresion obtenida por aritmetica de punto flotante.

Ejemplo

fl(x y) := x yfl(a+ (b+ c)

):= a+ (b+ c)

fl((a+ b) + c

):= (a+ b) + c

fl(cos(x)

):= cos(x)

fl(

x)

:=x

Las operaciones +,, , /, cos,, junto con algunas otras (queposean substitutos ) seran llamadas operaciones elementales.Como se vio, dos diferentes pero matematicamente equivalentesmaneras de evaluar la misma expresion a+ b+ c pueden llevar adiferentes resultados, cuando usamos aritmetica de punto flotante.Para propositos numericos es necesario distinguir entre distintosesquemas de evaluacion incluso si ellos son matematicamenteequivalentes. Llamaremos algoritmo a una secuencia finita deoperaciones elementales (dadas como instrucciones decomputadora) que prescriben como calcular la solucion de unproblema a partir de una entrada de datos dada.Formalizemos un poco la nocion de algoritmo. Supongamos que elproblema consiste en calcular los numeros reales y1, . . . , ym apartir de las entradas x1, . . . , xn.

Si introducimos los vectores

x =

x1...xn

, y =

y1...ym

,

entonces resolver el problema significa determinar el valory = (x) donde

: D Rm, D Rn,yi = i(x1, . . . , xn), i = 1, . . . ,m.

En cada paso del calculo hay un conjunto de operandos denumeros. Una sola operacion calcula un nuevo numero a partir deuno o mas operandos del conjunto de operandos. El nuevo numeroes un resultado intermedio o el final.Una operacion corresponde a una transformacion del conjunto deoperandos. Escribiendo estos consecutivamente como vectores,

x(i) =

x

(i)1...

x(i)ni

Rni ,

podemos asociar a cada operacion elemental un mapeo elemental

(i) : Di Rni+1 , Di Rni ,

tal que(i)

(x(i)

)= x(i+1).

Dado un algoritmo, entonces su secuencia de operacioneselementales da lugar a la descomposicion de en una secuencia demapeos elementales

(i) : Di Di+1, i = 0, 1, . . . , r, Dj Rnj , = (r) (r1) (0), D0 = D, Dr+1 Rnr+1 = Rm,

que caracteriza al algoritmo.

Ejemplo

Para (a, b, c) = a+ b+ c, consideremos los dos algoritmos := a+ b, y := c+ y := b+ c, y := a+ . Lasdescomposiciones son:

(0)(a, b, c) :=

[a+ bc

] R2, (1)(u, v) := u+ v R

y

(0)(a, b, c) :=

[a

b+ c

] R2, (1)(u, v) := u+ v R.

Ejemplo

Para (a, b) := a2 b2 se tienen los algoritmos Algoritmo 1:

1 := a a,2 := b b,y := 1 2,

Ejemplo

Algoritmo 2:

1 := a+ b,2 := a b,y := 1 2.

Sus descomposiciones correspondientes sonAlgoritmo 1:

(0)(a, b) :=

[a2

b

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

[uv2

], (2)(u, v) := u v.

Algoritmo 2:

(0)(a, b) :=

aba+ b

, (1)(a, b, u) :=

[u

a b], (1)(a, b, u) := uv.

Notese que las descomposiciones de los algoritmos pueden sersimplificadas:

Algoritmo 1: (0)(a, b) :=[a2

b2

], (1)(u, v) := u v.

Algoritmo 2: (0)(a, b) :=[a+ ba b

], (1)(u, v) := u v.

Estrictamente hablando, los mapeos (0) no son elementales. Sinembargo lo mas importante al hacer las descomposiciones es quelas componentes de los mapeos intermedios sean elementales, parapoder hacer as el analisis de error que se estudiara a continuacion.bf Ejemplo:y := a+ b+ c,

y := rd((a+ b) + c)= rd(a+ b) + c= (a+ b)(1 + 1) +

c= [(a+ b)(1 + 1) + c](1 + 2)

= (a+ b+ c)

[1 +

a+ b

a+ b+ c1(1 + 2) + 2

].

Despreciamos el termino 12 por ser de grado superior; luego elerror relativo (al haber calculado primero (a+ b)) es

y :=y yy

=y

y 1 a+ b

a+ b+ c1 + 2,

el cual es pequeno si (a+ b) es pequeno.

Si se hubiese calculado primero (b+ c) tendriamos

y b+ ca+ b+ c

1 + 2,

que es pequeno si (b+ c) es pequeno.

Vamos a hacer ahora un analisis diferencial de error de unalgoritmo para calcular y := (x) si esta funcion esta dada por ladescomposicion:

= (r)o(r1)o . . . o (0).

Para este fin necesitamos investigar como los errores de entrada,as como los errores por redondeo acumulados durante el curso delalgoritmo afectan el resultado final. Iniciamos esta investigacionconsiderando solamente los errores de entrada x.

Supongamos que la funcion

: D Rm, =

1(x1, . . . , xn)

...m(x1, . . . , xn)

,

esta definida en un conjunto abierto D de Rn, y que sus funcionescomponentes i, i = 1, 2, . . . , n, poseen derivadas continuas en D.Sea x un valor aproximado de x.

Entonces denotamos por

xi := xi xi, x := x x,

al error absoluto xi y x, respectivamente. El error relativo de xi esdefinido como la cantidad

xi :=xi xixi

si xi 6= 0.

Reemplazando x por x obtenemos el resultado y := (x) en vez dey = (x). Expandiendo en series de Taylor y despreciando losterminos de mayor orden, tenemos

yi := yi yi = i(x) i(x) n

j=1

(xj xj)i(x)xj

=n

j=1

i(x)

xjxj, i = 1, . . . ,m,

de donde

y =

y1...

ym

1(x)

x1. . .

1(x)

xn...

...m(x)

x1. . .

m(x)

xn

x1...

xn

= D(x)x,

con la matriz jacobiana D(x).

La cantidadi(x)

xjrepresenta la sensitividad con que yi reacciona

a las perturbaciones xj de xj.Si yi 6= 0 para i = 1, . . . ,m y xj 6= 0 para j = 1, . . . , n entonces setiene:

yi =yi yiyi

n

j=1

i(x)

xj

xj xjyi

=n

j=1

(xjyi

i(x)

xj

)xj xjxj

=

nj=1

(xjyi

i(x)

xj

)xj .

Numero de condicion

Los factores de amplificacion (xj/i)i/xj para el error relativoson llamados numeros de condicionamiento. Si alguno de estosnumeros es en valor absoluto muy grande, se dice que el problemaes mal condicionado. En otro caso, se dice que esta biencondicionado. Como se puede observar, la condicion del problemaesta descrita por mn numeros. Por estas razones, hay una maneramas practica de definir la condicion del problema. En algebralineal, usando una norma conveniente , el numero de condicionc debera satisfacer

(x) (x)(x) c

x xx .

Ejemplo

Para (a, b, c) := a+ b+ c se tiene

y ay

(a, b, c)

aa +

b

y

(a, b, c)

bb +

c

y

(a, b, c)

cc

=a

a+ b+ ca +

b

a+ b+ cb +

c

a+ b+ cc.

El problema estara bien condicionado cuando los sumandos a, b, csean pequenos comparados con a+ b+ c (por ejemplo, cuandotodos tengan el mismo signo).

Ejemplo

Para y = (a, b) := a+a2 + b,

y ay

(1 + a

a2 + b

)a +

b

y

1

2a2 + b

b

aa2 + b

a +a+

a2 + b

2a2 + b

b.

Desde que

aa2 + b 1,

a+

a2 + b

2a2 + b

1 para b > 0;

tendremos que es bien condicionado si b > 0, y malcondicionado si b a2.

Cuando se substraen dos numeros x, y A del mismo signo, unodebe tener cuidado con la cancelacion (esto es, cuando los numerostienen valores absolutos casi iguales). Por ejemplo, para calcular

y =x2 + 1 1

cuando el valor de x es cercano a cero, se sugiere calcularequivalentemente

y = (x2 + 1 1)

x2 + 1 + 1x2 + 1 + 1

=x2

x2 + 1 + 1.

Para evitar desbordamientos (overflow, underflow)

z :=x2 + y2x4 + y4

en caso |x| < |y|, hacemos t := xy(|t| < 1). Entonces calculamos

z =t2 + 1t4 + 1

.h

Para las operaciones aritmeticas (x 6= 0, y 6= 0)

(x, y) := x y xy x + y(x, y) := x/y x/y x y(x, y) := x y xy x

x y x +y

x y y si x y 6= 0(x) :=

x x 12x

Se sigue que la multiplicacion, division, y raz cuadrada no sonpeligrosas. Si los operandos son del mismo signo, la adicion no espeligrosa.

En efecto, tendremos que

|x+y| max{|x|, |y |}

Si los operandos tienen signos distintos, entonces almenos uno de

los factores

xx+ y o

yx+ y es mayor que uno; entonces los

errores seran amplificados, y drasticamente amplificados si x y.

Un algoritmo para calcular la funcion : D Rm, D Rn, paraun dado x = (x1, . . . , xn)

T D corresponde a la descomposicionde en mapeos elementales (i), i = 0, 1, . . . , r. Luego y = (x)se obtiene por una cadena de resultados intermedios

x(0) := x (0)(x(0)) = x(1) (r)(x(r)) = x(r+1) = y.

Suponemos de nuevo que cada (i) es continuamente diferenciableen Di, y denotemos por

(i) el mapeo remanente

(i) = (r) (r1) (i) : Di Rm, i = 0, 1, 2, . . . , r.

Entonces (0) .

De la regla de la cadena, tenemos

D(x) = D(r)(x(r)) D(r1)(x(r1)) D(0)(x),

D(x(i)) = D(r)(x(r))D(r1)(x(r1)) D(i)(x(i)), i = 0, 1, . . . , r.

En el calculo con punto flotante bajo la influencia de los errores deentrada y los errores por redondeo en lugar de los resultadosintermedios x(i) se obtienen valores aproximados x(i) conx(i+1) = fl((i)(x(i))).De esto se obtiene, para los errores absolutos x(i) = x(i) x(i),

x(i+1) = [fl((i)(x(i))) (i)(x(i))] + [(i)(x(i)) (i)(x(i))].

Usando series de Taylor, y despreciando terminos de orden superior:

(i)(x(i)) (i)(x(i)) D(i)(x(i))x(i).

Como (i) es elemental, o bien involucra solo operacioneselementales independientes, tenemos que

fl((i)(u)) = rd((i)(u)).

Notese ahora que (i) : Di Di+1 Rni+1 es un vector defunciones componentes

(i)j : Di R,

(i)(u) =

(i)1 (u)

...

(i)ni+1(u)

.

As, podemos trabajar con las componentes. De este modo:

fl((i)j (u)) = rd(

(i)j (u)) = (1 + j)

(i)j (u),

|j | eps, j = 1, 2, . . . , ni+1Entonces podemos simplemente escribir

fl((i)(u)) = (I +Ei+1) (i)(u).

Con la matriz identidad I y la matriz diagonal de error

Ei+1 =

1 0 00 2 0...

. . ....

0 0 ni+1

, |j | eps .

Esto nos da

fl((i)(x(i))) (i)(x(i)) = Ei+1 (i)(x(i)),

pero Ei+1 (i)(x(i)) Ei+1 (i)(x(i)) (despreciando terminos deorden superior). Por consiguiente

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

Por lo anterior, x(i+1) puede ser expresado con una aproximacionde primer orden como

x(i+1) i+1 +D(i)(x(i)) x(i)= Ei+1 x(i+1) +D(i)(x(i)) x(i), para i 0, x(0) := x.

Luego

x(1) D(0)(x) x+ 1x(2) D(1)(x(1)) [D(0)(x)x+ 1] + 2

...

y = x(r+1) D(r) D(0) x+D(r) D(1) 1 + + r+1.

Finalmente, llegamos a la formula que describe el efecto de loserrores de entrada x y los errores de redondeo i en el resultadoy = x(r+1) = (x):

y D(x) x+D(1)(x(1)) 1 + +D(r)(x(r)) r + r+1= D(x) x+D(1)(x(1)) E1 x(1) + +D(r)(x(r)) Er x(r) +Er+1 y.

Ejemplo

Para los dos algoritmos que calculan y = (a, b) = a2 b2 dadostenemos:Algoritmo 1:

x = x(0) =

[ab

], x(1) =

[a2

b

], x(2) =

[a2

b2

], x(3) = y = a2 b2,

(1)(u, v) = u v2, (2)(u, v) = u v,D(x) = (2a,2b)

D(1)(x(1)) = (1,2b), D(2)(x(2)) = (1,1),

1 =

[1a

2

0

], E1 =

[1 00 0

],

pues

fl((0)(x(0))) (0)(x(0)) =[a ab

]

[a2

b

].

Tambien

2 =

[02b

2

], E2 =

[0 01 0

].

3 = 3(a2 b2), |i| eps para i = 1, 2, 3.

Con x =

[ab

],

y 2aa 2bb+ a21 b22 + (a2 b2)3.

Analogamente para el algoritmo 2:

x = x(0) =

[ab

], x(1) =

[a+ ba b

], x(2) = y = a2 b2,

(1)(u, v) = u v,D(x) = (2a,2b), D(1)(x(1)) = (a b, a+ b),

1 =

[1(a+ b)2(a b)

], 2 = 3(a

2b2), E1 =[1 00 2

], |i| eps .

Por tanto

y 2aa 2bb+ (a2 b2)(1 + 2 + 3).

Estabilidad de un algoritmo

Un algoritmo es llamado numericamente mas estable que otro paracalcular (x) si, para un conjunto dado de datos x, el efecto totalde redondeo del primero es menor que el del otro.

Ejemplo

En el ejemplo anterior, el efecto total por redondeo usando elAlgoritmo 1 es

a21 b22 + (a2 b2)3 (a2 + b2 + |a2 b2|) eps,y usando el Algoritmo 2

|(a2 b2)(1 + 2 + 3)| 3|a2 b2| eps .

Esto muestra que el algoritmo 2 es numericamente mas estableque el algoritmo 1 siempre que 13 < |a/b|2 < 3; en otro caso elalgoritmo 1 es mas estable.