Apuntes programacion

[pic 2]

INSTITUTO POLITECNICO NACIONAL´

Escuela Superior de C´omputo

Apuntes de Programaci´on II

autor:

M en C. Benjam´ın Luna Benoso

        M´exico, D. F.        Diciembre 2008

Introducci´on

Este libro est´a estructurado tomando como referencia el temario para el curso de Programacio´n II impartido en la Escuela Superior de C´omputo del Instituto Polit´ecnico Nacional. Los temas analizados difieren so´lo un poco en el nombre y en el orden en que son presentados en el temario correspondiente.

El estudio del ana´lisis num´erico se basa en buscar alternativas para resolver problemas cuya soluci´on es dif´ıcil usando m´etodos directos, para ello, el ana´lisis num´erico se basa en la alternativa de m´etodos num´ericos.

En varias ´areas de la ingenier´ıa y las ciencias, se busca resolver problemas utilizando herramientas del ´algebra lineal o de las ecuaciones diferenciales; estos problemas, por ejemplo, suponen que se trabajan sobre funciones continuas, que para efectos pra´cticos de ejemplificacio´n, se obtiene lo que se desea, sin embargo, en la vida real, varios problemas de los que se plantean, no se conocen muy bien su naturaleza, generalmente se conocen o se obtienen mediciones por medio de aparatos y estos son registrados. Por ejemplo, un f´ısico experimental, en un laboratorio registra datos de un experimento el cual repite varias veces, registra sus datos y ahora lo que le interesa conocer, es una funci´on continua de tal manera, que si se restringe a los puntos que ´el registro, exactamente se comporte como en el experimento realizado. De esta´ manera, pasamos de los problemas continuos a los totalmente discretos, que es como se obtienen mediciones y a partir de estas mediciones discretas, pasamos nuevamente al espacio continuo, de ah´ı la importancia del ana´lisis num´erico.

Otra problem´atica interesante donde se puede notar la importancia del ana´lisis num´erico es la siguiente: en un curso de C´alculo, se hace notar que la recta esta compuesto por una√ infinidad de nu´meros, y que nu´meros como π, e y 2 (nu´meros irracionales) no tienen una representacio´n finita en su notaci´on decimal, esto significa que a ninguna persona le bastar´ıa su vida completa para escribir en notaci´on decimal alguno de estos nu´meros, entonces, como lo hace una computadora. La parte que nos interesa de una computadora, es aquella donde almacena la informaci´on para hacer ca´lculos, para representar nu´meros, sumas, etc., la parte que nos interesa es la memoria. Si finalmente una computadora est´a compuesta en su totalidad de circuitos, con una cantidad finita de estos, entonces como le hace para almacenar un nu´mero irracional como los presentados si su representaci´on es infinita y la computadora so´lo puede guardar nu´meros binarios (ceros y unos). En realidad una computadora, no es capaz de almacenar todos los nu´meros reales tal y como se conocen en su abstraccio´n. Si una computadora requiere almacenar un nu´mero irracional como π, este lo hace utilizando algu´n m´etodo de truncamiento que se vera´ posteriormente y en realidad la computadora no estara´ almacenando el nu´mero irracional π, si no mas bien, una aproximaci´on a dicho valor.

Si una computadora esta realizando c´alculos num´ericos donde ha utilizado valores aproximados a nu´meros reales, esto podr´ıa generar una serie de errores que vendr´ıan generandose en cada operaci´on. Obteniendo finalmente una aproximaci´on al valor real de la operacio´n que se deseaba conocer. Una problem´atica importante en este aspecto es el error que se va obteniendo y saber decidir si es aceptable o no. Esto es algo que tambi´en es tratado en el ana´lisi num´erico.

Los ejemplos anteriores, muestran la importancia que tiene el ana´lisis num´erico dentro de las areas de la ciencias y la ingenier´ıa.

Contenido

Introduccio´n        ii

1. Aritm´etica de Punto Flotante        1

1. Nu´meros de Punto Flotante . . . . . . . . . . . . . . . . . . . . . . . . . . .        1

1. Sistemas de Nu´meraci´on . . . . . . . . . . . . . . . . . . . . . . . . .        1
2. Representaci´on Binaria de Nu´meros Negativos . . . . . . . . . . . . .        7
3. Norma IEEE 754 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        9

1. Errores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        14

1. Error Relativo y Error Absoluto . . . . . . . . . . . . . . . . . . . . .        14
2. Aritm´etica de Punto Flotante . . . . . . . . . . . . . . . . . . . . . .        16
3. Errores de Representacio´n . . . . . . . . . . . . . . . . . . . . . . . .        16
4. Reducci´on de Errores . . . . . . . . . . . . . . . . . . . . . . . . . . .        20
5. Propagaci´on de Errores . . . . . . . . . . . . . . . . . . . . . . . . . .        23
6. Nu´mero de Condicion . . . . . . . . . . . . . . . . . . . . . . . . . . .        24

1. Algoritmos para dar Soluci´on a la Ecuacio´n de Una Variable        25

1. Algoritmos Para Bu´squeda de Ra´ıces . . . . . . . . . . . . . . . . . . . . . .        25

1. Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        25
2. M´etodo de la Biseccio´n . . . . . . . . . . . . . . . . . . . . . . . . . .        26
3. Iteraci´on de Punto Fijo . . . . . . . . . . . . . . . . . . . . . . . . . .        28
4. M´etodo de Newton-Raphson y de la Secante . . . . . . . . . . . . . .        30

1. Ra´ıces de Polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        33

1. Algoritmos de Interpolaci´on        37

1. Algoritmos de Interpolaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . .        37

1. Polinomio de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . .        38
2. M´etodo de Neville        . . . . . . . . . . . . . . . . . . . . . . . . . . . .        40
3. Diferencias Divididas de Newton        . . . . . . . . . . . . . . . . . . . .        41

1. Algoritmos de Ajuste de Curvas . . . . . . . . . . . . . . . . . . . . . . . . .        44

1. Ajuste por M´ınimos Cuadrados a una Recta . . . . . . . . . . . . . .        45
2. Ajuste por M´ınimos Cuadrados a un Polinomio de Grado n . . . . . .        47

CONTENIDO

1. Algoritmos para Derivacio´n e Integracio´n Num´erica        49

1. Algoritmos para Derivacio´n        . . . . . . . . . . . . . . . . . . . . . . . . . . .        49
2. Algoritmos de Integracio´n        . . . . . . . . . . . . . . . . . . . . . . . . . . . .        51

1. Algoritmos Num´ericos Utilizados en Algebra Lineal        55

1. Eliminacio´n Gaussiana con Sustitucio´n hacia Atra´s        . . . . . . . . . . . . . .        55
2. Algoritmos Basados en T´ecnicas Iterativas . . . . . . . . . . . . . . . . . . .        58

1. Normas de Vectores y Matrices        . . . . . . . . . . . . . . . . . . . . .        58
2. Algoritmo de Jacobi        . . . . . . . . . . . . . . . . . . . . . . . . . . .        59
3. Algoritmo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . .        61

6 Algoritmos para dar Soluci´on Num´erica a Ecuaciones Diferenciales Ordi-

        narias        63

        6.1        Algoritmos por M´etodos de Taylor        . . . . . . . . . . . . . . . . . . . . . . .        63

        6.1.1        M´etodo de Euler        . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        63

        6.1.2        M´etodo de Taylor de Orden N . . . . . . . . . . . . . . . . . . . . . .        64

        6.2        Algoritmo de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . . . . . .        65

        6.2.1        Algoritmo de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . .        65

...