Analisis Numerico

Vista previa del material en texto

1. Introducción 1
Análisis Numérico
Julio C. Carrillo E.
Escuela de Matemáticas, UIS
Análisis Numérico
1. Introducción 2
Ser capaz de automatizar los cálculos con una computadora es una
habilidad esencial para los ingenieros, matemáticos y cient́ıficos. Aun-
que hay una amplia variedad de problemas prácticos en cuya solu-
ción las computadoras se utilizan, también hay un núcleo de ideas
comunes a muchos cálculos con computadoras y muchas disciplinas
profesionales.
1. Terminoloǵıa
La terminoloǵıa que a continuación se define, busca servir de gúıa,
más que ser un ejercicio de pureza semántica. Esta terminoloǵıa ser-
virá además para establecer el contexto en el cual se utilizaran las
definiciones de términos en el resto del curso.
Análisis Numérico
1. Introducción 3
1.1. Cálculo numérico y simbólico
Un cálculo numérico involucra números, a diferencia de los śımbolos
para los cuales los números son representados en una ecuación. En
cálculo numérico, por lo tanto, se produce un resultado numérico
y no una expresión matemática. Cuando se evalúa una expresión
numérica, se realizan cálculos numéricos. En contraste, un cálculo
simbólico involucra la manipulación de śımbolos matemáticos sin que
necesariamente ellos hagan referencia a los valores numéricos que
tales śımbolos puedan tomar. Aśı,
1,862 − 1
1,86− 1 = 2,86
es un cálculo numérico y
x2 − 1
x− 1 = x+ 1
es un cálculo simbólico que es cierto para cualquier x diferente de 1.
Análisis Numérico
1. Introducción 4
Un aspecto importante del cálculo numérico es el uso de aproxima-
ciones en lugar de valores numéricos exactos. De hecho, parte im-
portante del cálculo numérico consiste en obtener la aproximación
de cantidades que no se pueden calcular exactamente mediante un
número finito de d́ıgitos. Por ejemplo, la fracción 1/3 es una expre-
sión simbólica que representa la división del entero 1 por el entero
3. Cuando se evalúa esta expresión a mano, o mediante una compu-
tadora, se obtiene como resultado una expresión numérica truncada,
la cual depende de cuantos d́ıgitos decimales se permiten en la re-
presentación de tal resultado. Aśı, el resultado puede ser 0,333333,
0,33333333 o algún otro valor. Igualmente, el valor de π utilizado en
un programa de computadora será una aproximación truncada del
valor simbólico exacto. Cuando un humano o una computadora rea-
liza operaciones matemáticas con cantidades numéricas, tales como
0,33333 en lugar de 1/3, el proceso es llamado cálculo numérico. El
cálculo simbólico puede involucrar śımbolos, como x, números racio-
Análisis Numérico
1. Introducción 5
nales, como 1/3, o números trascendentes, como π, sin que exista
restricción alguna sobre el número de d́ıgitos asociados con estos
śımbolos.
Los cálculos numéricos son realizables con lenguajes de programación
tales como Fortran, Basic, Pascal, C, C++ y Java. La representación
de los cálculos numéricos en las computadoras se realizan mediante
una representación binaria (i.e., mediante 0 y 1). Aśı, cuando a una
variable se le asigna un valor numérico, la computadora lo convierte
a un número binario y de esta manera lo almacena en su memo-
ria. Como no todos los números decimales pueden ser representados
exactamente en base 2, el hecho de asignarle un valor numérico a una
variable introduce una aproximación. El error en esta aproximación
contribuye a subsecuentes errores en la evaluación de formulas que
utilizan esta variable. Los valores que surgen al trabajar con valo-
res numéricos son usualmente pequeños. En algunos casos, errores
numéricos pequeños pueden ser significativos.
Análisis Numérico
1. Introducción 6
Los cálculos simbólicos pueden ser realizados por programas de compu-
tadora (software) tales como ReduceR©, DeriveR©, MacsymaR©, y Mathe-
maticaR©. Tales cálculos pueden realizarse sin las aproximaciones que
son necesarias para el cálculo numérico. En general, esto hace que los
resultados numéricos sean obtenidos más rápidamente con un cálculo
numérico que con la evaluación numérica de un cálculo simbólico.
El cálculo simbólico es un aspecto complementario e importante
de la informática, sin embargo, los cálculos simbólicos son utiliza-
dos únicamente para resaltar el comportamiento fundamental de los
cálculos numéricos.
1.2. Métodos numéricos y algoritmos
Aunque “método numérico” suele considerarse como sinónimo de “al-
goritmo numérico”, no es aśı. Un método numérico es una descrip-
ción matemática de los cálculos a realizar; un algoritmo numérico es
Análisis Numérico
1. Introducción 7
una sucesión precisa de acciones para obtener un resultado que se
desea obtener. La distinción entre ellos reconoce impĺıcitamente que
un buen método (i.e., uno que tiene unas propiedades matemáticas
convenientes) puede ser implementado con diferentes algoritmos, es
posible que un algoritmo sea mejor, por alguna razón, que otro al-
goritmo que involucra el mismo método.
Muchas de las empresas humanas involucran algoritmos. Un propósito
espećıfico puede ser obtenido mediante diferentes métodos, y cada
método puede realizarse con diferentes algoritmos. Por ejemplo, exis-
ten varias formas de obtener una taza de cafe. Podŕıa utilizarse una
cafetera de filtro, una máquina de café expreso, o cualquier otro dis-
positivo. Una vez el “método mecánico” es elegido, uno puede utilizar
más de un algoritmo para elaborar el café. Por ejemplo, puede utili-
zar granos de café y otro café molido.
El que un algoritmo de elaboración del café haga o no una diferencia
significativa depende de la precisión y la exactitud del paladar. La
Análisis Numérico
1. Introducción 8
elección del algoritmo puede ser también influenciada por el uso que
se le de a la taza de café. Aśı, es posible que un algoritmo para
obtener un capuchino sea más apropiado para obtener una taza de
café cuando se consume un postre muy fino o un desayuno elegante,
mientras que un algoritmo para obtener una taza de café mediante
una cafetera de filtro es más apropiado cuando se estudia tarde en
la noche.
En general, la elección de un algoritmo la determina el balance al-
tamente subjetivo de tres criterios: fácil de entender, exactitud en
el logro del objetivo propuesto, y eficiencia en el uso de recursos
informáticos.
Una vez el algoritmo es escogido, debe ser implementado en un código
de computadora, o simplemente, código. Un código es la traducción
de un algoritmo es una sucesión de declaraciones en un lenguaje de
computadora (o lenguaje de programación) en particular. Al igual
que un método puede ser implementado por diferentes algoritmos,
Análisis Numérico
1. Introducción 9
también un algoritmo puede ser implementado mediante diferentes
códigos. La forma de obtener un código en un lenguaje de progra-
mación que sea eficaz, es un asunto que se debe discutir después.
1.3. Métodos numéricos y análisis numerico
El análisis numérico es el estudio de los métodos numéricos. Es po-
sible realizar el análisis numérico sin utilizar una computadora. De
hecho, muchas de las técnicas utilizadas hoy d́ıa fueron desarrolladas
mucho antes de la presente era digital. Cuando los matemáticos, inge-
nieros y cient́ıficos no pueden encontrar una solución anaĺıtica exacta
de un problema práctico, ellos desarrollan procedimientos secuen-
ciales para calcular aproximaciones de tal solución anaĺıtica. En la
época en que los cálculos se realizaban manualmente, la importancia
de minimizar esfuerzos mientras se maximiza la precisón permitió el
desarrollo del análisis numérico como una rama de las matemáticas.
Análisis Numérico
1. Introducción 10
El énfasis de análisis numérico es mas acerca de entender el com-
portamiento general de los métodos numéricosy menso sobre como
aplicar estos métodos a la solución de un problema en particular. La
invención de los computadores digitales modernos y sus aplicaciones
a todos los aspectos de las ciencias y la industria a aumentado la
importancia del análisis numérico.
Los resultados del análisis numérico ayudan a elegir un método apro-
piado y el algoritmo. Ellos también dan información a priori impor-
tante sombre las limitantes del método y una estimación de la pre-
cisión (accuracy) del resultado obtenido. Al usar los resultados del
análisis numérico, un programador pude incrementar la probabilidad
que el resultado obtenido este más cercano de la solución “verdade-
ra”. Sin el análisis numérico, los programadores podrán descubrir los
méritos de cada método por experimentación (ensayo y error), pero
también, el puede suceder que sea dif́ıcil generalizar el conocimiento
ganado durante el desarrollo de cualquier otro programa.
Análisis Numérico
1. Introducción 11
De acuerdo con esta perspectiva, este curso de análisis numérico bus-
ca ser intermedio entre el análisis numérico y la implementación de
técnicas numéricas. Por esto, los resultado del análisis numérico serán
utilizados para anticipar el desempeño de los métodos numéricos y
para explicar la diferencia entre los correspondiente métodos. Aun-
que la experimentación puede ser usada para motivar la comprensión,
esta nunca podrá ser un substituto del análisis.
2. Sistemas numéricos y errores de cálculo
Es necesario considerar los métodos para representar números en un
computador y los errores que se generan por esta representación.
También es necesario considerar las fuentes de los diferentes tipos de
errores computaciones y su subsecuente propagación.
Análisis Numérico
1. Introducción 12
2.1. Fuentes de error
Desde el punto de vista de los métodos numéricos, usualmente in-
teresa considerar las fuentes de error que puedan surgir debido a:
1. Errores de cómputo por hardware (misiles patriot, guerra
del Golfo Pérsico). Anterior a la era de los computadores estos
errores proveńıan de los cálculos numéricos realizados a mano;
en la actualidad, se refiere en especial al error que es producto
del diseño en la lógica de los procesadores de los computadores.
2. Datos cŕıticos incorrectos.
3. Errores en el software (Métodos numéricos y algorit-
mos) (bugs).
Análisis Numérico
1. Introducción 13
4. Errores debido al cálculo numérico o errores de máquina
(chopping and rounding errors): dado que la aritmética que rea-
liza una calculadora o una computadora (rep. decimal finita) es
distinta de la aritmética de los números reales con la cual esta-
mos acostumbrados a trabajar (rep. decimal finita o infinita).
Desde el punto de vista del análisis numérico, a parte de lo anterior,
también interesan las fuentes de error ocasionadas por,
1. Modelado de un problema f́ısico.
2. Errores de programación (Análisis numérico) (blunder )
3. Incertidumbre de los datos (inestabilidad numérica, ill con-
ditioned problems)
4. Errores de truncamiento (truncation error)
Análisis Numérico
1. Introducción 14
3. Representación de números en compu-
tadoras
En general, los computadores tienen un modo entero y un modo de
punto flotante para representar los números. El primero modo es uti-
lizado para representar números enteros y el segundo para represen-
tar números reales. La representación de punto flotante de números
reales es muy cercana a lo que es llamada la notación cient́ıfica.
Sea β que denota la base del número a ser usado en la computadoraa
Entonces un número no nulo x es almacenado en la computadora
esencialmente de la forma
x = σ · (.a1a2 · · · an)β · βe, (1)
aLos números utilizados por computadoras son decimales. Muchos compu-
tadores utilizan base 2 (binaria), o alguna de sus variantes como en base 8 (octal)
o base 16 (hexadecimal).
Análisis Numérico
1. Introducción 15
con σ = ±, 0 ≤ ai ≤ β − 1, e is an integer, and
(.a1a2 · · · an)β =
a1
β1
+
a2
β2
+ · · ·+ an
βn
.
El término σ es llamado el signo, e es llamado el exponente, y e es
llamado el exponente, o caracteŕıstica, y (.a1a2 · · · an)β es llamada
la mantisa del número de punto flotante x. El número β es llama-
do también radix y el punto precediendo a1 es el punto radix, por
ejemplo, el punto decimal cuando β = 10 y el punto binario cuando
β = 2. El entero n da el número de d́ıgitos base β en la representa-
ción. Siempre asumimos
a1 6= 0
dando la que es llamada la representación de punto flotante norma-
lizada. También asumimos que
L ≤ e ≤ U (2)
Análisis Numérico
1. Introducción 16
lo cual limita el posible tamaño de x.
Máquina S/D R/C β n L U δ M
IBM 3033 S C 16 6 −64 63 9.5E-7 1.66E7
IBM 3033 D C 16 6 −64 63 2.22.5E-16 9.01E15
S/D: precisión simple o doble, R/C: redondeo o recorte, δ: unidad de redondeo, M: cota exacta para enteros.
3.1. Recorte y redondeo
Muchos números reales x no pueden ser representados exactamente
mediante la representación de punto flotante definida anteriormente,
y por ello deben ser aproximados por un número representable en
la máquina, si es posible. Dado un número real arbitrario x, fl(x)
denotará su aproximación en la máquina, si esta existe. Existen dos
formas de obtener fl(x) a partir de x: recortando o redondeando.
Análisis Numérico
1. Introducción 17
Sea x un número real escrito de la forma
x = σ · (.a1a2 · · · anan+1 · · · )β · βe
con a1 6= 0 y asumimos que e satisface (2). La representación de
máquina recortada de x es
fl(x) = σ · (.a1a2 · · · an)β · βe.
La razón de introducir recorte es porque muchos computadores utili-
zan más recorte que redondeo después de cada operación aritmética.
Ejemplo 1. El número π tiene una representación decimal infinita de
la forma π = 3,14159265 · · · . Escrito en forma decimal normalizada es
π = 0.314159265 · · · × 101.
La forma de punto flotante de π usando recorte a 5 d́ıgitos es
fl(π) = 0.31415× 101 = 3.1415,
Análisis Numérico
1. Introducción 18
y usando redondeo a 5 d́ıgitos es
fl(π) = 0.31416× 101 = 3.1416.
La representación redondeada de x es dada como
fl(x) =



σ · (.a1a2 · · · an)β · βe si 0 ≤ an+1 < β2
σ · [(.a1a2 · · · an)β + (.0 · · · 01)β ] · βe, si β2 ≤ an+1 < β,
donde (.0 · · · 01)β = β−n.
Análisis Numérico
1. Introducción 18-1
3.2. Almacenamiento
Los computadores almacenan un número no con precisión infinita sino
más bien de una manera aproximada que le permita empaquetarlo en un
número fijo de bits (d́ıgitos binarios) o bytes (grupos de 8 bites). Casi
todos los computadores le permiten al programador elegir entre diferentes
representaciones o tipos de datos. El tipo de datos puede diferir en el
número de bits utilizados (longitud de la palabra), pero también en si
el número almacenado es representado en formato de punto fijo (int o
long) o en formato de punto flotante (float o double).
Un número entero tiene representación exacta. La aritmética de números
en representación entera exacta es también exacta, con la aclaración de
que (i) la respuesta no puede estar por fuera del rango de enteros (usual-
mente con signo) que puedan ser representados, y (ii) que la división
es representada mediante un resultado entero, sin considerar cualquier
residuo entero.
En representación de punto flotante, un número es representado inter-
namente por un bit con signo s (interpretado como mas o menos) ,
un exponente entero exacto e, y una mantisa entera positiva exacta M .
Análisis Numérico
1. Introducción 18-2
Juntas representan el número
s ·M · βe−E (3)
donde nuevamente β es la base de la representación (usualmente es β = 2,
pero algunas veces β = 16), y E es el sesgo del exponente (para la repre-
sentación adecuada de números con magnitud pequeña), una constante
entera fija para cualquier máquina y representación dada. Como ejem-plo, ver la siguiente tabla. Por ejemplo, la representación de 1/2 en un
formato de t́ıpico de 32 bits (4 bytes), o de precisión simple, se escribe
de la forma
1
2
=
s
︷︸︸︷
0
e
︷ ︸︸ ︷
1 0 0 0 0 0 0 0
M
︷ ︸︸ ︷
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .
En representación binaria, este sistema de representación da un número
de punto flotante de la forma
s · 2e−1023 ·M,
Análisis Numérico
1. Introducción 18-3
donde 1023 = 210 − 1 es la magnitud del mayor número de 10 bits que
se puede representar en base 2. Aśı, la mayor magnitud del número en
base 10 que se puede expresar en doble precisión es
21023 ∼ 9× 10307
Tipo de dato Fortan Rango
Entero −32768 ≤ I ≤ 32767
−3,40× 1038 ≤ x ≤ −1,18× 10−38
Simple precisión o
1,18× 10−38 ≤ x ≤ 3,40× 1038
−1,8× 10308 ≤ x ≤ −2,23× 10−308
Doble precisión o
2,23× 10−308 ≤ x ≤ 1,80× 10308
Complejo a+ bi, donde i =
√
−1 y
a y b son valores en simple precisión
Análisis Numérico
1. Introducción 18-4
Para la mayoŕıa de números reales x, se tiene que fl(x) 6= x. En este
caso puede demostrarse que
x− fl(x)
x
= −ǫ (error relative)
donde
−β−n+1 ≤ ǫ ≤ 0 fl(x) recortado (4)
− 1
2
β−n+1 ≤ ǫ ≤ 1
2
β−n+1 fl(x) redondeado (5)
Esta fórmula es escrita de la forma equivalente
fl(x) = (1 + ǫ)x
con ǫ dado por (4) y (5). En consecuencia, fl(x) se puede considerar como
una pequeña perturbación de x. Esta fórmula de fl(x) también permite
tratar precisamente con los efectos de error por recorte o redondeo en
operaciones aritméticas en computadoras. La definición de fl(x) se debe
a Wilkinson, y es ampliamente usada en el análisis de los efectos de error
por redondeo.
Análisis Numérico
1. Introducción 18-5
3.3. Exactitud (accuracy) de la representación de punto flotan-
te
Se van a definir dos tipos de medida
Análisis Numérico
1. Introducción 18-6
Tipo
bit del
signo
bits del
exponente
bits de la
mantisa
Total de
bits
sesgo del
exponente
Media1 1 5 10 16 15
Simple 1 8 23 32 127
Doble 1 11 52 64 1023
Extendida 1 15 112 128 16383
Cuadro 1: Formatos binarios del estándar IEEE 754.
Análisis Numérico