Embed Size (px)
Citation preview
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Analisis Numerico: Artimetica de unaComputadora
Computacion / Matematicas
MA2008
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Introduccion
El objetivo de esta lectura es tener una idea aproximada decomo se realiza la aritmetica de punto flotante en unacomputadora. Esta idea debera poner sobre aviso de laspotenciales dificultades de algunos calculos numericos con el finde evitar hasta donde sea posible sorpresas numericas. Es muyrecomendable la lectura del artıculo de David Goldberg (WhatEvery Computer Scientist Should Know About Floating-PointArithmetic) para abundar sobre el tema.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Idea: Proceso involucrado en la
aritmetica
Mundo Matematicox op y
→ fl(fl(x) op fl(y))
Computadora
Datos y Programas Resultados
ControlMemoria
fl(x), fl(y)fl(fl(x) op fl(y))
ALU
fl(x) op fl(y)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Idea: Proceso involucrado en la
aritmetica
Mundo Matematicox op y
→ fl(fl(x) op fl(y))
Computadora
Datos y Programas Resultados
ControlMemoria fl(x), fl(y)
fl(fl(x) op fl(y))
ALU
fl(x) op fl(y)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Idea: Proceso involucrado en la
aritmetica
Mundo Matematicox op y
→ fl(fl(x) op fl(y))
Computadora
Datos y Programas Resultados
ControlMemoria fl(x), fl(y)
fl(fl(x) op fl(y))
ALU fl(x) op fl(y)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Idea: Proceso involucrado en la
aritmetica
Mundo Matematicox op y
→ fl(fl(x) op fl(y))
Computadora
Datos y Programas Resultados
ControlMemoria
fl(x), fl(y)
fl(fl(x) op fl(y))
ALU fl(x) op fl(y)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Idea: Proceso involucrado en la
aritmetica
Mundo Matematicox op y → fl(fl(x) op fl(y))
Computadora
Datos y Programas Resultados
ControlMemoria
fl(x), fl(y)
fl(fl(x) op fl(y))
ALU fl(x) op fl(y)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
La aritmetica que realiza una computadora es diferente de laaritmetica de los cursos de matematicas.
Para cada computadora hay una cifra positivallamada el epsilon (ε) de la computadora que es lacantidad positiva mas grande tal que
1 + ε = 1
Su existencia hace que la propiedad de asociatividadde la suma no se cumpla siempre.
(1 + ε) + ε 6= 1 + (ε+ ε)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
• La aritmetica del mundo matematico admite la existenciade numeros con una cantidad infinita de dıgitos. Porejemplo, los fraccionarios con expansion decimal que serepite en bloques como 1/2 o 1/3, o los numerosirracionales que no tienen esta caracterıstica como
√2 o π
o e.
• En las computadoras, no importa cual, la representacionde los numeros debe ser finita. Esta representacion originael error de redondeo.
• En 1985, la IEEE publica el informe Binary Floating PointArithmetic Standar 754-1985. El proyecto Arianne 3fracaso por un problema de interaccion de modulos sin unestandar numerico.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Precision sencillaPara PCs los numeros reales largos la representacionnormalizada se realiza mediante una cadena de 32 bits. Elprimer bit s tiene el signo del numero; los siguientes 8 bitscodifican en binario un entero llamado la caracterıstica c lacual es exponente al cual habra que restarle 127; los restantes23 bits codifican una fraccion binaria llamada la mantisa f :
(−1)s 2c−127 (1 + f )
EjemploPara la siguiente cadena:
12345678901234567890123456789012s123456781234567890123456789012301000001110111001000100000000000
s = 0
c = 1 · 27 + 0 · 26 + · · · + 0 · 22 + 1 · 21 + 1 · 20 = 128 + 2 + 1 = 131
f = 1 ·(
12
)1+ 1 ·
(12
)3+ 1 ·
(12
)4+ 1 ·
(12
)5+ 1 ·
(12
)8+ 1 ·
(12
)12
El numero representado es:
(−1)s · 2c−127 · (1 + f ) = 27.56640625
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Precision doblePara PCs los numeros reales largos la representacionnormalizada se realiza mediante una cadena de 64 bits. Elprimer bit s tiene el signo del numero; los siguientes 11 bitscodifican en binario un entero llamado la caracterıstica c lacual es exponente al cual habra que restarle 1023; los restantes52 bits codifican una fraccion binaria llamada la mantisa f :
(−1)s 2c−1023 (1 + f )
EjemploPara la siguiente cadena:
1234567890123456789012345678901234567890123456789012345678901234s1234567890112345678901234567890123456789012345678901234567890120100000000111011100100010000000000000000000000000000000000000000
s = 0
c = 1 · 210 + 0 · 29 + · · · + 0 · 22 + 1 · 21 + 1 · 20 = 1024 + 2 + 1 = 1027
f = 1 ·(
12
)1+ 1 ·
(12
)3+ 1 ·
(12
)4+ 1 ·
(12
)5+ 1 ·
(12
)8+ 1 ·
(12
)12
El numero representado es:
(−1)s · 2c−1023 · (1 + f ) = 27.56640625
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Ejemplo
(Continuacion)El siguiente numero a X que puede ser representado es:
27.5664062500000035527136788005009293556213378906250000000000
Mientras que el anterior a X y que puede ser representado es:
27.5664062499999964472863211994990706443786621093750000000000
Es decir, nuestra cadena representa aproximadamente al siguiente intervalo:
[27.5664062499999982236431605997495353221893310546875,27.5664062500000017763568394002504646778106689453125)
El menor numero positivo representable es:
0.111253692925360093857793927928947412039400442434185209780657 × 10−307
Resultados de numeros positivos menores el generaran el resultado de underflow o subdesbordamiento.Mientras que el mayor numero representable es:
0.359538626972463141629054847463408713596141135051689993197835 × 10309
Resultados mayores que este generaran el mensaje de overflow o desbordamiento.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
En lugar de la notacion binaria normalizada utilizaremos laforma de punto decimal normalizada para numerosdiferentes de cero:
±0.d1d2 . . . dk × 10n, 1 ≤ d1 ≤ 9, y 0 ≤ di ≤ 9 para 2 ≤ i ≤ k
los numeros de esta forma se llaman numeros de maquinadecimales con k dıgitos.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Cualquier numero real positivo se puede normalizar como
y = 0.d1d2d3 . . . dkdk+1dk+2 . . .× 10n
La forma de punto flotante (representacion) de y a k dıgitosque simbolizaremos por fl(y) se obtiniene de la mantisa de ydeterminando k cifras decimales. Hay dos formas de haceresto:
• Por TruncamientoQue consistira en cortar los dıgitos dk+1dk+2 . . . paraobtener
fl(y) = 0.d1d2 . . . dk × 10n
• Por RedondeoQue consiste en revisar el dıgito dk+1: Si dk+1 < 5,entonces se procede como en el caso de truncamiento. Sidk+1 ≥ 5, entonces se suma 5× 10n−(k+1) a y paraposteriormente truncar a k dıgitos el resultado.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Ejemplo 2
El numero e, la base de los logaritmos naturales o neperianos(John Napier of Merchiston (155 - 4 Abril 1617)) tiene undesarrollo infinito
e = 2.7182818284590452353602874713526624977 . . .
Escrito en forma decimal normalizada queda:
e = 0.27182818284590452353602874713526624977 . . .× 101
La forma de punto flotante de e con truncamiento a 5 cifrasqueda
fl(e) = 0.27182× 101 = 2.7182
mientras que la forma de punto flotante con redondeo a 5cifras es
fl(e) = 0.27183× 101 = 2.7183
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Definicion
El error que resulta de sustituir un numero por suforma de punto flotante es el error de redondeo (sinimportar si se usa truncamiento o redondeo). Si p∗ esuna aproximacion del numero p, el error absoluto es|p − p∗| y el el error relativo es |(p − p∗)/p|, siempreque p 6= 0.
EjemploPor ejemplo, si aproximamos e = 2.7182 . . . por e∗ = 2.71entonces el error absoluto es:
errabs = |e − e∗| = 0.00828182845 . . .
mientras que el error relativo es
errrel =errabs|e|
=0.00828182845 . . .
2.7182 . . .= 0.00304671 . . .
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Definicion
El numero p∗ aproxima a p con t cifras significativassi t es el mayor entero no negativo para el cual∣∣∣∣p − p∗
p
∣∣∣∣ < 5× 10−t
EjemploPor ejemplo, si aproximamos e = 2.7182 . . . por e∗ = 2.71entonces el error relativo es
err = errrel = 0.003046 . . .
Tenemos que para t = 1, xt=1 = 5× 10−1 = 0.5, para t = 2x2 = 0.05; para t = 3, x3 = 0.005; y para t = 4, x4 = 0.0005.Observamos que err > x4 pero err < x3. Por tanto, para t = 3se tiene el mayor entero tal que err < 5× 10−t . Por tanto,e∗ = 2.71 aproxima a e con 3 cifras decimales.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Ejemplo
Si queremos aproximar a e = 2.7182 . . . con 4 cifras entonces∣∣∣∣e − e∗
e
∣∣∣∣ < 5× 10−4
Entonces se debe cumplir
|e − e∗| < |e| · 5× 10−4
Por tanto
−e·5×10−4 < e−e∗ < e·5×10−4 → e−e·5×10−4 < e∗ < e+e·5×10−4
Por consiguiente, los valores de e∗ que aproximan a e con 4cifras decimales deben estar aproximadamente en el intervalo
[2.71692268, 2.71964096]
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Modelo Ilustrativo de las operacionesUn modelo que permite ilustrar la problematica ocasionada porla representacion finita normalizada usa las siguientesdefiniciones:
• x ⊕ y = fl(fl(x) + fl(y))
• x ⊗ y = fl(fl(x)× fl(y))
• x y = fl(fl(x)− fl(y))
• x � y = fl(fl(x)/fl(y))
La suma y resta requieren previamente alineamiento (igualacional exponente mayor).
La version que realizan las computadoras puede ser consultadaen M. Mano: Computer System Architecture. Prentice Hall.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
EjemploTome x = 1
3 , y = 57 , u = 0.714251, v = 98765.9 y
w = 0.111111× 10−4 y asuma representacion en base 10 con unamantisa a 5 dıgitos y truncamiento. Calcule:
Valor Error Error Cıfras
Operacion Resultado Real Absoluto Relativo Significativas
x ⊕ y 22/21 0.10476 × 101 0.19047 × 10−4 0.18181 × 10−4 5x yx ⊗ yx � yu ⊕ vy u
(y u)� w(y u)⊗ v
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
x ⊕ y
• x = 1/3 = 0.33333 . . .→ fl(x) = x∗ = 0.33333× 100
• y = 5/7 = 0.714285714285 . . .→ fl(y) = y∗ =0.71428× 100
• x + y = 1.047619047619
• x∗+ y∗ = 0.33333× 100 + 0.71428× 100 = 1.04761× 100
• fl(x∗ + y∗) = 0.10476× 101
• eabs = |x + y − fl(x∗ + y∗)| = 0.0000190476 . . .
• erel = eabs|x+y | = 0.0000181818 . . .
• 5 cıfras significativas en la aproximacion de x + y porfl(x∗ + y∗)
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Algunas reglas a tomar en cuenta
• La suma de un numero grande con un numero pequenoproduce un error absoluto grande pero no un gran errorrelativo.
• La resta entre dos numeros parecidos dan un errorabsoluto pequeno pero un gran error relativo. Las cıfrassignificativas se pierden en un solo calculo!
• La multiplicacion por numeros grandes amplifica el errorabsoluto pero no modifica el error relativo.
• La division entre numeros pequenos amplifica el errorabsoluto pero no modifica el error relativo.
¿En que situaciones puede ocurrir la peor situacion? ¿Seransituaciones a las cuales, en general, no nos enfrentaremos comopara tomar previsiones?
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
EjemploAplique la formula general para resolver la ecuacion cuadratica
a x2 + b x + c = 0
Para a = 1, b = −105 y c = 1 usando una aritmetica decimalcon una mantisa de 8 cıfras.
AnalisisNumerico:
Artimetica deuna
Computadora
Computacion/
Matematicas
Intro
Idea
IEEE estandar
Errores
Aproximacion
Operaciones
Reglasempıricas
La ecuacioncuadratica
Correccion en la solucion de una cuadraticaFormulas alternativas deducidas multiplicando por elconjugado:
x1 = −b+√b2−4 a c
2 a = −b+√b2−4 a c
2 a · (−b−√b2−4 a c)
(−b−√b2−4 a c)
= 2 c−b−
√b2−4 a c
x2 = −b−√b2−4 a c
2 a = −b−√b2−4 a c
2 a · (−b+√b2−4 a c)
(−b+√b2−4 a c)
= 2 c−b+
√b2−4 a c
x1 =−b +
√b2 − 4 a c
2 ao x1 =
2 c
−b −√
b2 − 4 a c
x2 =−b −
√b2 − 4 a c
2 ao x2 =
2 c
−b +√
b2 − 4 a c
REGLA: Si b > 0 usar las azules; si b < 0 usar las rojasObserve que eludimos una resta que puede ser peligrosa parab2 � 4 a c!
