C alculo Num erico Avanzado - personales.unican.espersonales.unican.es/segurajj/CNA.pdf · ... condiciones de contorno Dirichlet y Neumann ... al programar unalgoritmo num erico,

Calculo Numerico Avanzado

J. Javier Segura Sala 1

February 25, 2004

1Depto. de Matematicas, Estadıstica y Computacion. Universidad de Cantabria

ii

Contents

1 La importancia de saber resolver numericamente ecuaciones diferenciales dela Fısica 31.1 Ejemplo 1: un pendulo para empezar . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Ejemplo 2: oscilaciones en un circuito electrico . . . . . . . . . . . . . . . . . . . 41.3 Ejemplo 3: distribucion de temperaturas en una placa . . . . . . . . . . . . . . . 51.4 Ejemplo 4: propagacion de la luz en un medio isotropo . . . . . . . . . . . . . . . 61.5 Ejemplo 5: ecuacion de Schrodinger dependiente del tiempo... . . . . . . . . . . . 81.6 ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.7 ...Ejemplo n:.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Sistemas de numeracion; errores y sus fuentes 92.1 Sistemas de numeros y conversiones . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1 Sistemas de numeracion en base q . . . . . . . . . . . . . . . . . . . . . . 92.1.2 Conversion de base decimal a base q . . . . . . . . . . . . . . . . . . . . . 102.1.3 Estandar IEEE de representacion de numeros enteros y en coma flotante . 12

2.2 Errores y sus causas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.1 Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2.2 Fuentes de errores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Propagacion de errores: condicion y estabilidad. . . . . . . . . . . . . . . . . . . . 182.4 Eficiencia de un algorıtmo numerico . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.1 Ejemplo: Evaluacion de polinomios, metodo de Horner . . . . . . . . . . . 21

Tema 1. La importancia de saber resolver ecuaciones diferenciales numericamente


1

La importancia de saber resolver

numericamente ecuaciones diferenciales

de la Fısica

Este curso de analisis numerico esta dedicado al estudio de metodos numericos para la reso-lucion de ecuaciones diferenciales ordinarias y ecuaciones diferenciales en derivadas parciales.¿Por que es importante su estudio en una licenciatura de Fısica?. La respuesta es obvia: lasecuaciones diferenciales son la expresion matematica (simplificada) de gran parte de fenomenosy problemas fısicos. Para nuestra desgracia la mayorıa de estas ecuaciones no se pueden resolveranalıticamente en terminos de funciones “sencillas”, de modo que debemos recurrir a metodosnumericos para su resolucion.

Como muestra, unos pocos ejemplos seleccionados cuya resolucion abordaremos en la partepractica del curso.

1.1 Ejemplo 1: un pendulo para empezar

El pendulo es probablemente el sistema dinamico mas estudiado de todos los tiempos. Laecuacion diferencial que describe su movimiento en ausencia de rozamiento y fuerzas externas es

mLd2θ

dt= −mg sin(θ) , (1.1)

siendo θ el angulo formado por el pendulo con respecto a la vertical, m su masa, L su longitudy g la aceleracion debida a la gravedad.

Habitualmente se estudia el pendulo aproximandolo por una simple ecuacion lineal (sin(θ) ≈θ), que es aproximadamente valido para pequenas amplitudes de oscilacion.

La ecuacion (1.1) se puede resolver analıticamente en terminos de integrales elıpticas, queson funciones para la que existen eficientes metodos numericos. El procedimiento es, en lugarde resolver directamente

d2θ

dt2+ ω2

0 sin(θ) , ω0 = g/L (1.2)

tener en cuenta que

E =1

2

(

dθ

dt

)2

− ω20 cos θ (1.3)

3


es una constante de movimiento. Integrando esta constante de movimiento podemos obtenerθ(t) en terminos de una integral conocida (integral elıptica) que el propio MATLAB incluye (asıcomo casi cualquier librerıa cientıfica).

Sin embargo, un pendulo moviendose en ausencia de rozamiento es una simplificacion excesivadel sistema. Si anadimos un termino de rozamiento y una fuerza externa, la ecuacion presentaahora el siguiente aspecto

mLd2θ

dt+ γ

dθ

dt+mg sin(θ) = A cos(2πfdt) , (1.4)

siendo γ la constante de rozamiento, A la amplitud de la fuerza y fd, la frecuencia de esta.

Esta ecuacion no puede ser resuelta, en general, de forma analıtica en terminos de unaintegral “simple” y deberemos acudir a alguno de los metodos numericos de resolucion de EDOsque estudiaremos en el curso.

1.2 Ejemplo 2: oscilaciones en un circuito electrico

La ecuacion de van der Pol es un modelo para un circuito electrico que formaba parte de lasradios antiguas. Este circuito se remonta a los dıas en que se utilizaban tubos de vacıo. Eltubo actua como un resistor normal cuando la corriente es elevada y lo hace como un resistornegativo cuando la corriente es baja. Por tanto, este circuito aumenta las pequenas oscilacionesy disminuye las grandes. Este comportamiento es caracterıstico de los denominados osciladoresde relajacion. La ecuacion que describe este sistema es:

d2i

dt2− µ

di

dt(1 − i2) + i = 0 (2.5)

siendo µ un parametro caracterıstico del sistema.

Como ocurrıa con el oscilador forzado del ejemplo 1, esta ecuacion no es resoluble analıticamentesi µ 6= 0. De hecho, la influencia del parametro µ en el comportamiento de las soluciones de estaEDO es muy acusada. Veremos que esta ecuacion es prototipo de los denominados problemasstiff (rıgidos) cuando los valores de µ son grandes. Este tipo de problemas requeriran metodosespecıficos para que puedan resolverse de forma eficiente.



1.3 Ejemplo 3: distribucion de temperaturas en una placa

Supongamos que nos interesa encontrar la distribucion de temperaturas u(x, y) en la placa quese muestra en la figura:

−1.5 −1 −0.5 0 0.5 1 1.5−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

R1

con unas condiciones de contorno determinadas (por ejemplo, temperatura constante T en losbordes superior e inferior (BS,BI) y sin perdidas de calor en los bordes laterales (BL)) y conuna fuente de calor f(x, y) en el interior de la placa (I).

El problema a resolver se aproxima por la siguiente ecuacion en derivadas parciales:

∂2u∂x2 + ∂2u

∂y2 = f(x, y) en I

u = T en BS, BI∂u∂n

= 0 en BL

(3.6)

siendo n la direccion normal al borde en cuestion.

Este es un problema de tipo elıptico con condiciones de contorno Dirichlet y Neumann. Esun problema estatico: asumimos que no hay dependencia temporal en las variables del sistema.Dada la geometrıa regular del sistema, veremos que un metodo numerico apropiado para resolveresta EDP sera un esquema de diferencias finitas.

En la siguiente figura se muestra la resolucion de uno de estos problemas estaticos de tem-peraturas para un caso en el que se puede encontrar solucion analıtica (lo que no es lo habitual).

5 Calculo Numerico Avanzado. J. Segura


Sobre este caso volveremos en las clases practicas.

Si la placa tuviese una geomeotrıa irregular, como la que se muestra en la siguiente figura,optaremos por el metodo de elementos finitos. Al estudio de este metodo dedicaremos una parteimportante del curso.

−1.5 −1 −0.5 0 0.5 1 1.5−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

P1

1.4 Ejemplo 4: propagacion de la luz en un medio isotropo

La luz monocromatica en un medio isotropo con una permitividad ε que varıa poco, se describemediante la ecuacion de Helmholtz:

−∆E = k20εE (4.7)

donde E representa cualquier componente del campo electrico y k0 = 2π/λ es el numero de



ondas del vacıo. Supongamos que E es, de forma aproximada, una onda plana que se propagaen una direccion que llamaremos z, de forma que podamos escribir

E(t, x, y, z) = u(x, y, z)eiβz−iωt

En estas condiciones, sustituyendo en (4.7) y asumiendo que se puede despreciar el termino enuzz obtenemos:

iuz =−uxx − uyy + (β2 − εk2

0)u

2β(4.8)

que es la ecuacion de Fresnel. Suponemos que conocemos u(x, y, 0) = u0(x, y) y queremosobtener u(x, y, z) en z. Esta ecuacion (de tipo parabolico) es un prototipo de problema depropagacion. La siguiente grafica muestra la resolucion de uno de estos problemas (sin con-siderar propagacion en el eje y. Representamos la amplitud en funcion de x y z (direccion depropagacion).

Otro ejemplo prototipo de este tipo de problemas es, como veremos, la ecuacion del calorT = κ∆T , donde T (t,x) representa un campo de temperaturas. Se asume que el dato T (0,x) =T 0(x) es conocido y se desea obtener T (t,x) para t > 0. Un aspecto importante a tener en cuentasera, como estudiaremos, los resultados de estabilidad para algunos algoritmos de metodos endiferencias aplicados a estas EDPs. Este analisis de estabilidad, debido a Von Neumann, nospermitira entender el comportamiento numerico de estos algoritmos y nos ayudara en la seleccionde aquellos que resulten mas adecuados para el problema a abordar.



1.5 Ejemplo 5: ecuacion de Schrodinger dependiente del tiempo...

La ecuacion de Schrodinger dependiente del tiempo:

i∂ψ(x, t)

∂t=

(

− 1

2m

d2

dx2+ V (x)

)

ψ(x, t) (5.9)

donde utilizamos unidades naturales para no escribir la constante de Planck, es “manejable”analıticamente para casos ideales (potenciales simples y combinacion de pocos autoestados deenergıa), pero en general son necesarios metodos numericos para estudiar cuantitativamente lapropagacion de paquetes de ondas.

Ver [4] para una interesante discusion sobre la resolucion de la evolucion temporal de unpaquete de ondas. Ver tambien [6]

1.6 ...

1.7 ...Ejemplo n:....


2

Sistemas de numeracion; errores y sus

fuentes

En este tema se introducen los distintos sistemas de numeracion y se describe como realizar laconversion entre distintos sistemas, ası como el estandar IEEE de representacion de numerosen el sistema binario. A continuacion, se introducen las nociones de error absoluto y relativoy se analizan las causas mas frecuentes de error en un calculo computacional, ilustrandolo conejemplos. Finalmente, se introducen los conceptos de (in)estabilidad y condicion.

2.1 Sistemas de numeros y conversiones

Es necesario conocer como se representan los numeros enteros y decimales en formato digital paraentender las limitaciones intrınsecas que nos encontraremos al programar un algoritmo numerico,tanto en cuanto a la mayor precision alcanzable como en cuanto al rango de valores admisibles.Veremos ademas como un mınimo conocimiento del sistema de representacion estandar sirvepara evitar la aparicion de desastrosos errores de programacion (como bucles infinitos).

2.1.1 Sistemas de numeracion en base q

El sistema de numeracion decimal es el sistema posicional de numeracion mas utilizado, queutiliza como base de numeracion el 10 (dıgitos 0...9). Como es bien sabido, se puede utilizarcualquier numero natural mayor que 1 como base de numeracion.

Un numero en base q se denota como (anan−1...a1a0.b1b2...bk...)q donde ai y bj pertenecen alconjunto de los q dıgitos elementales. Estos q dıgitos representaran valores desde 0 hasta q − 1.La conversion a decimales es, por definicion:

(anan−1...a1a0.b1b2...bk...)q = anqn + an−1q

n−1 + ...+ a1q + a0q0

+b1q−1 + b2q

−2 + ...+ bkq−k + ...

(1.1)

El sistema natural de numeracion digital es el binario (base 2), utilizando solo los dıgitos 0y 1.

Ejemplo 2.1 Decimal: (123.25)10 = 1 × 102 + 2 × 101 + 3 × 100 + 2 × 10−1 + 5 × 10−2.

Binario (base 2) con 2 dıgitos 0 y 1: 0 + 1 = 1, 1 + 1 = 10.

9

Tema 2. Sistemas de numeracion. Errores y sus fuentes.

(1011.01)2 = 1 × 23 + 0 × 22 + 1 × 21 + 1 × 20 + 0 × 2−1 + 1 × 2−2 = 11.25.

Hexadecimal (base 16) tiene 16 dıgitos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F , que re-presentan los valores desde 0 hasta 15 respectivamente. Por tanto:

(7B.4)15 = 7 × 161 +B × 160 + 4 × 16−1 = 123.25.

Los sistemas de numeracion octal y hexadecimal, tambien son muy utilizados, en partedebido a que es muy sencilla su conversion a binario con la ventaja de que un mismo numero serepresenta con menos cifras cuanto mayor es la base.

2.1.2 Conversion de base decimal a base q

Ya sabemos como convertir un numero en base q a base decimal (1.1). La conversion de basedecimal a base q se base en el hecho de que, acudiendo a la definicion (1.1) observamos que(eliminamos el subındice 10 para numeros en base decimal):

(anan−1...a1a0.b1b2...bk...)q × q = (anan−1...a1a0b1.b2b3...bk...)q

(anan−1...a1a0.b1b2...bk...)q × q−1 = (anan−1...a1.a0b1b2...bk...)q(1.2)

Utilizaremos esto para obtener la conversion de un numero en base 10 a base 2. Para esto,conviene separar la conversion de la parte entera (antes del punto decimal) de la fraccionaria(despues del punto); observemos que un numero entero es necesariamente entero en cualquierbase y que un numero fraccionario lo es en cualquier base.

Conversion entera

De (1.2) deducimos que:

(an...a0)q−1 = (an...a1)q + (.a0)q

es decir, que

(an...a0)q = (an...a1)q × q + (.a0)q × q = (an...a1)q × q + (a0)q (1.3)

que es una identidad entre numeros, que podemos evaluar en cualquier base, y en particularen base 10 (observese que de hecho mezclamos base numeros en distintas bases). Vemos puesque al dividir un numero entero entre q el resto es el dıgito menos significativo del numero enbase q. Dividiendo sucesivamente (hasta llegar al cociente 0) obtenemos los sucesivos dıgitos delnumero en base q.



Conversion fraccionaria

A partir de (1.2) vemos que:

(.b1b2...bk)q × q = (b1)q + (.b2...bk)q

Vemos pues que la parte entera del resultado de multiplicar nuestro numero por q es elprimer dıgito tras el punto decimal. Reteniendo la parte fraccionaria que resulta en cada pasoy repitiendo sucesivamente el proceso, vamos obteniendo el resto de cifras tras el punto.

Ejemplo 2.2 Escribamos (26.1)10 en base 2.

1. Parte entera. Dividiendo sucesivamente, tenemos que:

26 = 2 × 13 + 0 ; 13 = 2 × 6 + 1 ; 6 = 2 × 3 + 0 ; 3 = 2 × 1 + 1 ; 1 = 2 × 0 + 1

Leyendo de izquierda a derecha los numeros subrayados: (26)10 = (11010)2

2. Parte fraccionaria. Multiplicando sucesivamente por dos y separando la parte fraccionaria:

0.1 × 2 = 0.2 ; 0.2 × 2 = 0.4 ; 0.4 × 2 = 0.8 ; 0.8 × 0.2 = 1.6 ; 0.6 × 2 = 1.2 ; 0.2 × 2 = ...

Leyendo de izquierda a derecha tenemos los dıgitos de la parte fraccionaria (subrayados)luego:

(0.1)10 = (0.00011)2

donde las cifras subrayadas son las cifras periodicas.

Observese que el numero 0.1 tiene infinitas cifras distintas de cero cuando se escribe enbase 2 (se repiten indefinidamente desde la segunda a la quinta cifra fraccionaria).

Sumando los resultados de la parte entera y la fraccionaria tenemos que

(26.1)10 = (11010.00011)2

En el anterior ejemplo hemos aprendido que un numero fraccionario con un numero finito dedıgitos en cierta base no tiene por que tener un numero finito en otra base. En efecto, (0.1)10

es un numero periodico con infinitas cifras cuando se escribe en base 2. Esto es importantepuesto que en un procesador digital los numeros se almacenar en binario utilizando un numerofinito de cifras. Esto quiere decir que el numero 0.1 no se representa exactamente en un orde-nador. Esto hay que tenerlo en cuenta para evitar errores que conduzcan a bucles que se repitenindefinidamente. El siguiente algoritmo en Matlab es un ejemplo de bucle infinito,

Algoritmo 2.3 Bucle infinito en precision finita binaria:x=0;while x∼=10 (Nota: en Matlab esto significa x 6= 0)

x=x+0.1;end



Esto nos deberıa prevenir de utilizar bucles que terminan cuando se alcanza cierto valorconcreto de una variable que involucra numeros no enteros.

Ejercicio 2.4 Si en la tercera lınea del anterior algoritmo cambiamos 0.1 por 0.125, ¿seguirıamosteniendo un bucle infinito?.

2.1.3 Estandar IEEE de representacion de numeros enteros y en coma flotante

Numeros enteros

Asumamos, como es comun en la mayor parte de los procesadores, que cada palabra tiene unalongitud de 32 bits, es decir, que cada numero vendra representado por 32 dıgitos binarios. Laforma mas sencilla de representar un numero entero es asignando uno de los 32 bits para designarel signo (0 para +, 1 para menos) y utilizando las 31 restantes posiciones para representar losdıgitos del modulo del numero entero. En consecuencia, el mayor numero entero que se puederepresentar es 231 − 1.

Este es el estandar IEEE salvo porque, por lo general, no se suele reservar un bit para el signo,sino que se utiliza una ordenacion distinta para guardar los enteros negativos. Sin embargo, enla practica una y otra prescripcion son practicamente equivalentes.

Tambien pueden utilizarse enteros en longitud doble, utilizando dos palabras de 32 bits, conlo que se aumenta el rango de enteros admisibles.

Numeros no enteros

Para representar numeros con parte fraccionaria se utiliza el formato de punto (o coma) flotante.Esta representacion es la correspondiente version binaria de la conocida notacion cientıfica oexponencial para los numeros decimales:

±M × 10E , 1 ≤M < 10

pero utilizando base 2:

x = ±M × 2E , 1 ≤M < 2

donde M es la mantisa y E el exponente. Inevitablemente el numero de dıgitos que se puedenalmacenar de la mantisa y exponente es limitado. Hay dos tipos de precision, la simple y ladoble, que difieren en el numero de bits de los que se dispone para almacenar las cifras; ladistribucion estandar es:

1. Precision simple: 32 bits, de los cuales:

(a) uno corresponde al signo,

(b) 8 al exponente, luego −128 ≤ E ≤ 127 (2 × 128 = 28)

(c) 23 a la mantisa



2. Precision doble

(a) uno para el signo

(b) 11 al exponente (−1022 ≤ E ≤ 1023)

(c) 52 para la mantisa

Ejemplo 2.5 Veamos de forma simplificada como se guardarıa el numero 5.5 en precisionsimple. Primero lo pasamos a binario: 5.5 = (101.1)2 y normalizamos para que la mantisa1 < M ≤ 2, de forma que 5.5 = (1.011)2 × 22, que tiene exponente E = 2 (que se guardara enbinario), signo + (bit 0) y mantisa 1.011. Normalmente, salvo para el caso del numero cero,que se almacenan de distinta forma, el numero delante del punto sera siempre 1, por lo que nose suele almacenar.

Ejemplo 2.6 El anterior es un ejemplo de un numero decimal que se puede guardar de formaexacta en una palabra de 32 bits. Un ejemplo en el que esto no serıa ası es el ya conocido caso de0.1 = (0.00011)2 = (1.1001)2×2−4, que necesariamente ha de redondearse antes de almacenarse;esquematicamente (sin entrar en detalles de como se almacena el exponente), tendrıamos, enprecision simple, la representacion (recordemos que el 1 antes del punto decimal no se suelealmacenar)

0|E = −4|10011001100110011001101

donde la 23a cifra tras el punto se ha redondeado a 1 porque la siguiente era 1. De esta forma,lo que realmente se almacena es:

(1.10011001100110011001101)2 × 24 = 0.10000000149011611938

Esto muestra explıcitamente que, efectivamente, el algoritmo 2.3 es un bucle infinito.

Debemos resaltar que la especificacion del numero de bits que se utilizan para almacenarmantisa y exponente es lo unico que necesitamos para determinar cuales son los mayores ymenores numeros que se pueden almacenar en coma flotante ası como la maxima precision quese puede obtener. Veamos como obtener estos parametros en el caso de doble precision (que esla precision utilizada por Matlab).

Ejemplo 2.7 Obtener los numeros de “overflow” y “underflow” ası como la precision maquinaen doble precision, es decir:

1. Obtener el mayor numero entero positivo representable en formato de coma flotante en elcaso de doble precision (lımite de “overflow”)

Puesto que el mayor exponente es 1023, el mayor numero representable es (1.1....1)2 ×21023 ' 1.8 × 10308 (hay 52 unos detras del punto “decimal”).



2. Obtener el menor numero entero positivo representable en formato de coma flotante enel caso de doble precision (lımite de “overflow”). El menor decimal representable con 52dıgitos significativos binarios es (1.00...01)2 × 10−1022 ' 2.23 × 10−308. Sin embargo, elestandar IEEE admites numeros mas pequenos, aunque tengan menos cifras significativas(es lo que llaman numeros sub-normales); estrictamente el numero mas pequeno repre-sentable en coma flotante es: (0.00..01)2 × 2−1022 = 2−1074 ' 4.94 × 10−324 (52 dıgitostras la coma decimal). Para no perder dıgitos significativos es mejor moverse en el rango(1/Nov , Nov), donde Nov es el numero de overflow Nov ' 2.23 × 10−308.

3. Obtener la diferencia entre 1 y el menor numero positivo mayor que 1 en coma flotante(epsilon-maquina). Obtener asimismo la diferencia entre 1 y el mayor numero positivomenor que 1.

El numero que se nos pide es (1.0...01)2 − (1.0...0)2 = (0.0...01)2 = 2−52 ' 2.2 × 10−16.Este numero representa el mejor error relativo que se puede manejar en doble precision(definimos este conocido concepto a continuacion). Este valor de epsilon-maquina significaque todos los numeros con 15 cifras significativas se pueden guardar de forma exacta endoble precision y que ocurre lo mismo para la mayor parte de los numeros de 16 cifras.

En cuanto a la diferencia entre 1 y el mayor numero positivo menor que 1, esta es:(1.0..0)2 − (1.1...1)2 × 2−1 = 2−53 ' 1.1 × 10−16

Nota 2.8 Es importante tener en cuenta que Matlab trabaja en doble precision aunque pordefecto solo muestre 5 cifras significativas. Para que el sistema muestre mas cifras se puedeutilizar el comando “format long”.

Ademas de los detalles senalados hay otras caracterısticas fundamentales del estandar IEEEque no describiremos como son:

1. Redondeo correcto de la aritmetica (volveremos mas adelante sobre este punto)1.

2. Tratamiento de excepciones. Es decir, que un operacion del tipo log(0.0) no da error einterrumpe la ejecucion del programa, sino que se asigna un valor especial para representaresta excepcion (para significar −∞).

3. Compatibilidad entre procesadores. Esta es por supuesto, una de las grandes ventajas delos estandares.

2.2 Errores y sus causas

El analisis numerico trata de la construccion de metodos discretos para la resolucion de pro-blemas continuos. Esta discretizacion, que se presenta tanto en la representacion numerica en

1Un error en el “hardware” de punto flotante de los Intel Pentium (1994) le dio una considerable mala publicidada la companıa. El problema fue solventado reemplazando los procesadores defectuosos



un ordenador como en los propios algoritmos de calculo, necesariamente implica la aparicion deerrores cuyo origen y propagacion debemos estudiar 2.

2.2.1 Definiciones

Si xA es una aproximacion del verdadero valor xT , definimos entonces:

Error absoluto: Eabs = |xT − xA|

Error relativo: Erel = |1 − xA

xT|, si xT 6= 0.

Tambien se pueden utilizar estas definiciones con signo (es decir, sin el valor absoluto).

El error relativo en ocasiones se expresa tambien en tanto por ciento. El error relativo mideel numero de cifras significativas exactas de xA. Ası, si

2Erel < 10−m , m ∈ N

se dira que xA tiene m cifras significativas exactas.

2.2.2 Fuentes de errores

Las fuentes de error en un calculo numerico pueden ser de variada naturaleza, algunas de ellasindependientes del metodo numerico empleado.

1. Un metodos numerico para resolver determinado problema cientıfico puede dar lugar aresultados erroneos si el modelo no es una fiel descripcion de la realidad.

2. Un algoritmo numerico puede depender de ciertos datos de entrada (por ejemplo, datosfısicos) afectados de cierto error. Se debe vigilar que el metodo numerico no sea cru-cialmente dependiente de la exactitud de tales valores de entrada y que la precision deestos valores sea suficiente para nuestros propositos. En el caso en que el propio mod-elo fısico/matematico sea muy sensible a estos parametros, tendremos un problema malcondicionado e imposible de resolver numericamente de forma estable.

3. Los errores de programacion son practicamente inevitables durante la construccion de unmetodo numerico. Una vez construido un algoritmo numerico que en apariencia funcionacorrectamente es necesario certificar su funcionamiento mediante todos los tests que estena nuestro alcance.

2No por ello se debe adoptar la vision reduccionista consistente en definir el analisis numerico como el area dela matematica que analiza los errores de calculo



4. Errores en la aritmetica de punto flotante: errores de redondeo, perdida de cifras signi-ficativas por cancelaciones, problemas de “underflow/overflow”. Estos son los problemasderivados de la representacion en punto flotante, en la cual se dispone de un numero finitode bits para representar la mantisa y el exponente. Como ya vimos, esto limita tanto lamejor precision relativa alcanzable (15-16 dıgitos decimales en doble precision) como elrango de valores disponible.

Aunque la segunda de las limitaciones no suele presentar graves problemas, es necesarioevitar la evaluacion de cantidades demasiado grandes o pequenas.

La limitacion de la precision tiene por lo general mayores consecuencias. Por ejemplo,cuando se sustraen cantidades muy parecidas, el error relativo empeora drasticamente porperdida de cifras significativas.

5. Errores de truncamiento o de discretizacion, inherentes al hecho de aproximar un prob-lema continuo mediante una aproximacion discreta. Por ejemplo, veremos que la reglatrapezoidal sirve para aproximar integrales mediante:

∫ b

a

f(x)dx ≈ h

2(f(a) + f(b)) + h

N−1∑

k=1

f(a+ kh) ≡ S(h) , donde h =b− a

N, h = (b− 1)/N

El significado de “≈” es “aproximadamente”, lo cual significa que

∫ b

a

f(x)dx = S(h) + ε(h)

donde ε(h) es el error de truncamiento, que es de esperar que sea menor cuanto menorsea h (N ∈ N lo mayor posible). Un calculo explıcito de los errores de truncamiento esal menos igual de difıcil que el calculo del problema original. Nos conformaremos con unconocimiento cualitativo de estos errores y con buscar acotaciones lo mas finas posible.

Trataremos de estimar los errores de truncamiento en cada algoritmo numerico que se pre-sente.

Discutamos en este punto acerca de los errores debidos a las limitaciones en la representacionde punto flotante, en particular por lo que respecta a la precision limitada del sistema

Redondeo y perdida de cifras significativas

Puesto que la representacion en coma flotante es limitada en cuanto al numero de cifras signi-ficativas que se pueden almacenar, los numeros reales se redondearan a un determinado numerode cifras (siempre utilizando el sistema de numeracion binario) cuando el valor verdadero tengamas cifras de las que se pueden almacenar.



Asimismo, tras cada operacion aritmetica se vuelve a redondear el resultado. En el estandarIEEE esto se hace de la mejor manera posible en el sentido de que el resultado de la operacionaritmetica esta redondeado de forma que se almacena el valor mas proximo al resultado exacto.Ası, por ejemplo, supongamos que, para simplificar, la precision fuese de tres dıgitos binariostras el punto (y no consideremos limitacion en el exponente), si se suman los numeros en puntoflotante x = (1.010)2, y = (1.001)2 ×2−4 tenemos que el resultado exacto es (1.0101001)2 que noserıa un numero en punto flotante (solo disponemos de 3 posiciones tras el punto). El resultadoIEEE serıa redondear la ultima cifra, aumentandola si la siguiente fuese 1 y dejandola como estaen otro caso. Ası, x+ y se almacenarıa como (1.011)2.

Otra posibilidad (menos recomendable) es, sin mas, eliminar las cifras que no quepan (trun-camiento). Esta desafortunada prescripcion se utilizaba en los supercomputadores Cray, peroesta en total deshuso.

Aun cuando en el estandar IEEE se redondea al numero en coma flotante mas cercano, quees la opcion mas conveniente, es necesario estudiar como pueden afectar sucesivos redondeos alresultado de un algoritmo numerico.

Por otra parte, la limitacion en el numero de bits para la mantisa tiene como consecuenciala posible perdida de cifras significativas en ciertos calculos donde dos cantidades tienden acancelarse entre sı 3. Para evitar este tipo de errores, es recomendable:

a) O bien reescribir la formula en cuestion de modo que se eviten las restas de cantidades dela misma magnitud.

b) O bien utilizar (cuando sea posible) un desarrollo de Taylor para aproximar la formula hastala precision requerida.

Veamos algunos ejemplos en los que se da perdida de cifras significativas

Ejemplo 2.9 Obtener las raıces de x2 − 106x+ 1.En una modesta calculadora con 10 decimales y aplicando la archiconocida formula x =

−b±√

b2 − 4ac2a , vamos obteniendo los resultados:

x =106 ±

√

1012 − 4

2' 106 ± 106

2

que da x = 106 para la mayor raız y x = 0 para la menor. Es evidente que hemos perdido todaslas cifras significativas para la menor raız. De hecho, la famosa formula deberıa ser desterradade cualquier metodo numerico. Es mucho mejor reescribir la solucion de la ecuacion de segundogrado como:

x1 = L/2a , x2 = 2c/L , L = −b− signo(b)√

b2 − 4ac

3Un famoso y lamentable error de este tipo fue el que motivo le fallo de los misiles Patriot para derribarlos misiles Skud iraquıes durante la guerra del golfo: se medıan intervalos de tiempo restando tiempos desde elreinicio del sistema con la consiguiente perdida progresiva de precision



De esta forma la mayor raız es como antes y en la calculadora la menor saldrıa x = 10−6, cuyoerror relativo respecto a la solucion verdadera es ∼ 10−12.

Ejemplo 2.10 Consideremos por ejemplo f(x) = (√x+ 1 − √

x) para x > 0. Cuando x esgrande, se producen errores de redondeo importantes puesto que los valores de

√x+ 1 y

√x se

aproximan considerablemente. ¿Como evitarıamos esta fuente de error?. Lo que podemos haceres reescribir f(x) del siguiente modo:

f(x) = (√x+ 1 −

√x)

√x+ 1 +

√x√

x+ 1 +√x

=1√

x+ 1 +√x.

En la expresion resultante podemos apreciar que no se producen cancelaciones de cantidadesde la misma magnitud.

Ejemplo 2.11 Consideremos g(x) =1 − cos(x)

x2 . Cuando se evalua g(x) para |x| << 1 se

produce una perdida considerable de cifras significativas. En este caso, para remediar el problemaconsideramos el desarrollo de Taylor de cos(x) entorno a 0. De este modo:

g(x) =1 − [1 − x2/2! + x4/4! + ...]

x2≈ 1

2− x2

4!+x4

6!.

Esta expresion es apropiada entonces para evaluar g(x) cuando x << 1.

Errores de overflow /underflow

Aunque los lımites de overflow/underflow son considerablemente generosos, conviene escribirlas expresiones que se utilicen de manera que se minimice esta posibilidad. Por ejemplo, espreferible calcular el modulo de un numero complejo, z = x+ iy, |z| =

√

x2 + y2, como

|z| = |x|√

1 + (y/x)2

De esta forma, no hay que elevar al cuadrado numeros que pueden ser muy grandes. De lamisma forma, hay que tomar precauciones para calcular la argumento de un numero complejode manera que no se produzcan “overflows/underflows” en el calculo de y/x.

Ejercicio 2.12 Escribir un programa en Matlab que obtenga la representacion polar de unnumero complejo dado z = reiθ, 0 ≤ θ < 2π, eliminando el riesgo de problemas de overflow-underflow.

2.3 Propagacion de errores: condicion y estabilidad.

Un error en un calculo numerico contamina las sucesivas evaluaciones. Esta propagacion del errorpuede describirse en terminos de dos conceptos relacionados, los de (in)estabilidad y condicion.



La condicion de una funcion f(x) mide la sensibilidad de los valores de f(x) a pequenoscambios en x y se define como

C =

∣

∣

∣

∣

Erel(f(x))

Erel(x)

∣

∣

∣

∣

donde Erel(f(x)) es el error relativo de f(x) para un error relativo Erel(x) en x.Entonces, como 4

f(xT ) − f(xA) ' f ′(xt)(xT − xA) → Erel(f(x)) ' f ′(xT )

f(xT )(xT − xA)

luego

C '∣

∣

∣

∣

xTf ′(xT )

f(xT )

∣

∣

∣

∣

Utilizaremos esta ultima expresion como definicion de condicion para funciones f(x) de unavariable real. Definimos entonces los numeros de condicion como

C(x) =

∣

∣

∣

∣

xf ′(x)

f(x)

∣

∣

∣

∣

Cuando para un x dado 0 < C(x) < 1 para ese x se dira que el problema (calculo de f)esta bien condicionado (y cuanto menor sea C mejor condicionado), mientras que si C(x) > 1el problema estara mal condicionado. Si C(X) = 1, el error relativo se mantiene.

Ejemplo 2.13 La funcion f(x) =√x esta bien condicionada, pues C(x) = 1/2, luego el error

relativo se reduce.

En cambio f(x) = x2 − 1 esta mal condicionada para x ' 1 pues C(x) =

∣

∣

∣

∣

2x2

x2 − 1

∣

∣

∣

∣

El concepto de condicionamiento se puede extender a situaciones mas generales que la deuna funcion de una variable continua. Por ejemplo, un problema clasico que involucra funcionesde una variable discreta, es el estudio del condicionamiento de relaciones de recurrencia:

Ejemplo 2.14 Las funciones de Bessel Jn(x) satisfacen la relacion de recurrencia: Jn+1(x) =

−Jn−1(x) + 2nx Jn(x), pero como las funciones de Bessel de segunda especia cumplen la misma

relacion y limn→∞ Jn(x)/Yn(x) = 0, el calculo de las funciones Jn a partir de J0 y J1 esta malcondicionado, pues una pequena perturbacion en los datos iniciales J0 y J1 contamina nuestrasecuencia de funciones {Jn} con la secuencia {Yn}, que crece mas rapido con n.

Ası, por ejemplo, empezando con los valores en precision simple J0(2) = 0.22389078 yJ1(2) = 0.57672481, y aplicando la recurrencia obtenemos J8(2) = 4.00543213 × 10−5 que notiene bien ni siquiera un cifra significativa: J8(2) = 2.2180 × 10−5.

4Recordemos el teorema del valor medio: Si g(x) continua en [a, b] y derivable en (a, b) entonces ∃c ∈ (a, b) :f(b) − f(a) = f ′(c)(b − a)



Un concepto relacionado, que no equivalente, es el de (in)estabilidad de un algoritmo, quedescribe la sensibilidad de un metodo numerico especıfico respecto a los inevitables errores deredondeo cometidos durante su ejecucion en aritmetica de precision finita. Observemos quela condicion no depende de errores de redondeo pero que la estabilidad de un algoritmo sıdepende del condicionamiento de la funcion que queramos evaluar. Un ejemplo puede servirpara distinguir estos dos conceptos relacionados:

Ejemplo 2.15 Dada la funcion f(x) =√x+ 1 −√

x, su numero de condicion es:

C(x) =

∣

∣

∣

∣

xf ′(x)

f(x)

∣

∣

∣

∣

=x

2√x√x+ 1

y vemos que C(x) < 1/2 para x > 0, luego la funcion esta bien condicionada (su error relativoes menor que el error relativo en x).

Sin embargo, el algorıtmo para calcular x consistente en ir realizando las operaciones impli-cadas en f(x) =

√x+ 1 −√

x, a saber:

1. Input: x

2. y = x+ 1

3. f1 =√x+ 1

4. f2 =√x

5. f = f1 − f2

es inestable para x grande por culpa del paso 5 (hay cancelaciones entre numeros similares).Como sabemos, un algoritmo estable lo proporciona la siguiente reescritura de la funcion:

f(x) =1√

x+ 1 +√x

2.4 Eficiencia de un algorıtmo numerico

Por supuesto, cualquier algoritmo numerico sensato debe evitar ser inestable. Por otra parte,si existieran varios metodos para evaluar una misma funcion, entonces convendra adoptar aquelmetodo que sea mas eficiente, es decir, mas rapido. Con la mejora en proporcion geometrica dela velocidad de los procesadores, podrıamos estar tentados en despreocuparnos por la rapidezde calculo. Esta es, sin embargo, una pesima filosofıa: se trata de aprovechar los recursos parapoder resolver problemas mas complejos y no para resolver peor problemas simples. La eficienciaes y siempre sera de importancia capital en el desarrollo de buenos metodos numericos.

La diferencia en tiempos de ejecucion pueden llegar a ser muy considerables si ciertas op-eraciones elementales, que se pueden repetir miles y miles de veces, no se realizan con cuidado.



Por ejemplo, para calcular x4 para cierto valor de x, es muy mala idea calcular x4.0 (exponenteen coma flotante); hay que tener cuidado en utilizar un exponente entero ya que los metododosde exponenciacion en coma flotante son distintos que los de enteros y mucho mas lentos; aun esmejor idea considerar el calculo en dos pasos: x2 = x ∗ x, x4 = x2 ∗ x2, con lo que se economizarun producto frente a x4 = x ∗ x ∗ x ∗ x.

2.4.1 Ejemplo: Evaluacion de polinomios, metodo de Horner

Otro ejemplo notable (y por desgracia no suficientemente) conocido es la evaluacion de poli-nomios. Por ejemplo, supongamos que nos planteamos evaluar el polinomio

P (x) = 2 + 4x− 5x2 + 2x3 − 6x4 + 8x5 + 10x6

Contando con que cada potencia de exponente k entero cuente como k−1 productos, tendrıamosque el numero total de productos para evaluar el polinomio de forma directa es:

1 + 2 + 3 + 4 + 5 + 6 = 21

y el numero de sumas es 6.

Una forma mejor de proceder es ir calculando primero las potencias de forma sucesiva:

x2 = xx , x3 = xx2 , x4 = xx3 , x5 = xx4 , x6 = xx5

con lo que solo se anade una nueva multiplicacion por potencia, par un total de

1 + 2 + 2 + 2 + 2 + 2 = 11

Pero aun se puede hacer mejor reescribiendo

P (x) = 2 + x(4 + x(−5 + x(2 + x(−6 + x(8 + x10)))))

con lo que solo necesitamos 6 multiplicaciones (y el numero de sumas no cambia). Vemos puesque para evaluar un polinomio de grado n en el que ninguno de los coeficientes es cero, senecesitan n(n+ 1)/2 multiplicaciones por el primer metodo, 2n− 1 por el segundo y n para eltercero. De forma que se debe procurar utilizar el ultimo metodo, particularmente cuando n esgrande.

Este metodo es ademas sencillo de programa, en efecto:

Algoritmo 2.16 (Algoritmo de Horner o de division sintetica)



Algoritmo de HornerDado el polinomio

P (x) = a0 + a1 x+ ...+ an xn , an 6= 0

la evaluacion de P (x) para cierto valor x = z se puede realizar en n pasosmediante

(1) bn = an

(2) bn−1 = an−1 + z ∗ bn

(3) bn−2 = an−2 + z ∗ bn−1

...

(n) b0 = a0 + z ∗ b1

donde P (z) = b0.

Es facil programa este algoritmo en forma de bucle, sobretodo si no nos interesan los calculosintermedios. Ası, se puede escribir:

(1) b = an

(2) Repetir mientras n > 0

(3) n = n− 1

(4) b = an + z ∗ b

(5) Volver a (2)

(6) p(z) = b.

Esta forma de evaluar polinomios es mucho mejor que el metodo directo, especialmente paraordenes grandes. Dependiendo del orden de un polinomio y las veces que se repita el calculo,sera importante aplicar el metodo de Horner.


Bibliography

[1] Atkinson, K., Elementary Numerical Analysis (2nd. Ed), John Wiley & Sons, 1993.

[2] Acton, F. S., Numerical Methods that work, Washington: The Mathematical Association ofAmerica, 1990.

[3] Conte, S. D., de Boor, C., Elementary Numerical Analysis (An Algorithmic Approach),McGraw-Hill, 1981.

[4] Koonin, S.E., D.C. Meredith, Computational Physics ( Fortran version), Addison-Wesley,1990.

[5] Press, W. H., S.A: Teukolsky, W.T. Vetterling y B.P. Flannery, Numerical recipes in Fortran77, Cambridge University Press, 1992.

[6] Segura, J., Fernandez de Cordoba, P. Estudio numerico de la evolucion de un paquete deondas en mecanica cuantica. Revista Espanola de Fısica 7 (1993) 57–61.

23

Documents

C alculo Num erico Avanzado - personales.unican.espersonales.unican.es/segurajj/CNA.pdf · ... condiciones de contorno Dirichlet y Neumann ... al programar unalgoritmo num erico,