Análisis Numérico Notas de clase PDF

Preview

Summary

An´ alisis Num´ erico Notas de clase ——————————— An´ alisis Num´ erico Notas de clase ——————————— Jorge Vel´ asquez Zapateiro Virgilio Obeso Fern´ andez Ediciones Uninorte Barranquilla-Colombia 2007 Jorge Vel´asquez Zapateiro An´alisis Num´erico, Notas de clase Jorge Vel´ asquez Zapateiro, Virgilio ...

Description

An´ alisis Num´ erico Notas de clase ———————————

An´ alisis Num´ erico Notas de clase ———————————

Jorge Vel´ asquez Zapateiro Virgilio Obeso Fern´ andez

Ediciones Uninorte Barranquilla-Colombia 2007

Jorge Vel´ asquez Zapateiro An´ alisis Num´ erico, Notas de clase Jorge Vel´ asquez Zapateiro, Virgilio Obeso Fern´ andez. Barranquilla:Ediciones Uninorte,2007 195p ISBN:

c °Ediciones Uninorte,2007 c °Jorge Vel´ asquez Zapateiro y Virgilio Obeso Fern´ andez, 2007

Cordinaci´ on editorial Zoila Sotomayor O.

Editor Jorge Vel´ asquez Zapateiro.

Correcci´ on de textos xxxxxxxxxxxxxxxx.

Dise˜ no de portada yyyyyyyyyyyyyy.

Impreso y hecho en Colombia Cargraphics Worl Bogot´a

´Indice general 1. N´ umeros en la Computadora 1.1. Sistemas Decimal y Binario . . . . . . . 1.2. Del Sistemas Decimal al Sistema Binario 1.3. N´ umeros en Punto Flotante . . . . . . . 1.4. Notaci´on Cient´ıfica Normalizada . . . . . 1.5. Errores y Notaci´on fl(x) . . . . . . . . . 1.5.1. Norma Vector . . . . . . . . . . . 1.5.2. Error Absoluto y Relativo . . . . 1.6. An´alisis de Error . . . . . . . . . . . . . 1.7. Epsilon de la M´aquina . . . . . . . . . . 1.8. Notaci´on O de Landau . . . . . . . . . . 1.9. P´erdida de D´ıgitos Significativos . . . . .

. . . . . . . . . . .

3 3 4 7 9 11 11 12 15 15 16 19

. . . . . . . . . . .

25 26 27 36 37 37 43 45 49 52 56 59

Ecuaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67 68 70 73

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

2. Soluci´ on de Ecuaciones no lineales 2.1. Ratas de Convergencia . . . . . . . . . . . . . . 2.2. Punto Fijo . . . . . . . . . . . . . . . . . . . . . 2.3. An´alisis Gr´afico del M´etodo de Punto Fijo . . . 2.4. M´etodos de Localizaci´on de Ra´ıces . . . . . . . 2.4.1. M´etodo de Bisecci´on o B´ usqueda Binaria 2.5. M´etodo de Falsa Posici´on o Regula Falsi . . . . 2.6. M´etodo de Newton . . . . . . . . . . . . . . . . 2.6.1. Convergencia del M´etodo de Newton . . 2.7. M´etodo Modificado de Newton . . . . . . . . . 2.8. M´etodo de la Secante . . . . . . . . . . . . . . . 2.9. M´etodo ∆2 de Aitken . . . . . . . . . . . . . . . 3. Soluci´ on de Sistema de 3.1. Vectores y Matrices . 3.2. Matrices . . . . . . . 3.3. Determinantes . . . .

v

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

vi

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

3.3.1. Norma Matriz . . . . . . . . . . . . . . . . . . 3.4. Sistema de Ecuaciones Lineales . . . . . . . . . . . . 3.4.1. Sistemas Triangulares Superior . . . . . . . . 3.5. Eliminaci´on de Gauss y Pivoteo . . . . . . . . . . . . 3.5.1. Transformaciones Elementales . . . . . . . . . 3.5.2. Operaciones Elementales en los Renglones . . 3.6. Estrategias de Pivoteo . . . . . . . . . . . . . . . . . 3.6.1. Pivoteo Trivial . . . . . . . . . . . . . . . . . 3.6.2. Pivoteo Parcial . . . . . . . . . . . . . . . . . 3.6.3. Pivoteo Parcial Escalado . . . . . . . . . . . . 3.7. Factorizaci´on LU . . . . . . . . . . . . . . . . . . . . 3.8. M´etodo de Jacobi . . . . . . . . . . . . . . . . . . . . 3.9. M´etodo de Gauss- Saidel . . . . . . . . . . . . . . . . 3.10. Sistema de Ecuaciones no Lineales . . . . . . . . . . . 3.10.1. M´etodo de Newton . . . . . . . . . . . . . . . 3.10.2. Ventajas y Desventajas de M´etodo de Newton 3.10.3. M´etodo de Punto Fijo . . . . . . . . . . . . . 4. Interpolaci´ on Polinomial 4.1. Interpolaci´on de Lagrange . . . . . . . . . . . 4.2. Cotas de Error . . . . . . . . . . . . . . . . . 4.3. Polinomio Interpolador de Newton . . . . . . 4.4. Polinomios de Hermite . . . . . . . . . . . . . 4.5. Aproximaci´on de Pad´e . . . . . . . . . . . . . 4.6. Interpolaci´on a Trozos . . . . . . . . . . . . . 4.6.1. Interpolaci´on Lineal a Trozos . . . . . 4.6.2. Interpolaci´on C´ ubica o Cercha C´ ubica 4.7. Aproximaci´on con Polinomios Trigonom´etricos

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

74 76 77 80 80 80 83 83 83 84 85 88 91 93 93 97 97

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

105 . 107 . 111 . 114 . 119 . 125 . 129 . 130 . 131 . 150

5. Derivaci´ on e Integraci´ on Num´ erica 5.1. Derivaci´on Num´erica . . . . . . . . . . . . . . . . . 5.1.1. An´alisis de Error . . . . . . . . . . . . . . . 5.2. Extrapolaci´on de Richardson . . . . . . . . . . . . . 5.3. Integraci´on Num´erica . . . . . . . . . . . . . . . . . 5.4. Integraci´on Compuesta . . . . . . . . . . . . . . . . 5.4.1. Regla Compuesta del Trapecio . . . . . . . . 5.4.2. Regla Compuesta de Simpson . . . . . . . . 5.4.3. Regla Compuesta de los 38 Simpson . . . . . 5.4.4. Cotas de Error para las Reglas Compuestas 5.5. M´etodo de Integraci´on de Romberg . . . . . . . . . 5.6. Cuadratura Adaptativa . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

´INDICE GENERAL

. . . . . . . . .

. . . . . . . . .

161 161 174 175 180 193 193 196 199 201 206 211

vii

An´ alisis Num´ erico. Notas de clase

5.7. Integraci´on Gauss-Legendre . . . . . . . . . . . . . . . . . . . 216 5.8. Integrales Impropias . . . . . . . . . . . . . . . . . . . . . . . 221 5.9. Integraci´on Doble . . . . . . . . . . . . . . . . . . . . . . . . . 226 6. Ecuaciones Diferenciales Ordinarias con Condiciones Iniciales 239 6.1. Ecuaciones Diferenciales de Primer Orden con Condiciones Iniciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 6.2. M´etodos de Euler y de Taylor . . . . . . . . . . . . . . . . . . 243 6.2.1. M´etodo de Euler . . . . . . . . . . . . . . . . . . . . . 245 6.2.2. Cotas de Error . . . . . . . . . . . . . . . . . . . . . . 246 6.2.3. M´etodo de Taylor . . . . . . . . . . . . . . . . . . . . . 248 6.3. M´etodos de Runge-Kuta . . . . . . . . . . . . . . . . . . . . . 252 6.4. M´etodos Expl´ıcitos de Adams- Bashforth . . . . . . . . . . . . 257 6.4.1. M´etodo de Adams- Bashforth de dos pasos . . . . . . . 257 6.4.2. M´etodo de Adams- Bashforth de tres pasos . . . . . . . 257 6.4.3. M´etodo de Adams- Bashforth de cuatro pasos . . . . . 258 6.5. M´etodos de Adams-Moulton . . . . . . . . . . . . . . . . . . . 260 6.5.1. M´etodo se Adams-Moulton de dos pasos . . . . . . . . 260 6.5.2. M´etodo se Adams-Moulton de tres pasos . . . . . . . . 261 6.6. M´etodos Predictor-Corrector . . . . . . . . . . . . . . . . . . . 264 6.6.1. M´etodo de Milne-Simpson . . . . . . . . . . . . . . . . 266 6.7. Sistema de Ecuaciones Diferenciales . . . . . . . . . . . . . . . 269 6.7.1. Aproximaci´on Num´erica . . . . . . . . . . . . . . . . . 270 6.8. Ecuaciones Diferenciales de Orden Superior . . . . . . . . . . 272 Bibliograf´ıa.........................................................................

´INDICE GENERAL

279

viii

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

´INDICE GENERAL

1

An´ alisis Num´ erico. Notas de clase

0pt0.4pt

´INDICE GENERAL

2

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

´INDICE GENERAL

Cap´ıtulo 1

N´ umeros en la Computadora La aparici´on de los computadores ha hecho posible la soluci´on de problemas, que por su tama˜ no antes eran excluidos. Desafortunadamente los resultados son afectados por el uso de la Aritm´ etica de Precisi´ on Finita, en la cual para cada n´ umero se puede almacenar tantos d´ıgitos como lo permita el dise˜ no del computador. As´ı por ejemplo, de nuestra experiencia √ esperamos tener siempre expresiones 2 verdaderas como 2 + 2 = 4, 3 = 9, ( 5)2 = 5, pero en la aritm´etica de √ umero fijo y finito, que lo representa. precisi´on finita 5 no tiene un solo n´ √ Como 5 no tiene una representaci´on de d´ıgitos finitos, en el interior del computador se le da un valor aproximado cuyo cuadrado no es exactamente 5, aunque con toda probabilidad estar´a lo bastante cerca a ´el para que sea aceptable.

1.1.

Sistemas Decimal y Binario

El sistema num´erico de uso frecuente es el sistema decimal. La base del sistema decimal sabemos es 10. Ahora bien la mayor´ıa de las computadoras no usan el sistema decimal en los c´alculos ni en la memoria, sino que usan el sistema binario que tiene base 2, y su memoria consiste de registros magn´eticos, en los que cada elemento solo tiene los estados encendido o apagado. La base de un sistema num´erico recibe el nombre de ra´ız. Para el sistema decimal como se dijo es 10 y para el binario es 2. La base de un n´ umero se denota por un sub´ındice as´ı que (3.224)10 es 3.224 en base 10, (1001.11)2 es 1001.11 en base 2.

3

4

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

El valor de un n´ umero base r es (abcdef g.hijk)r y se calcula como a×r6 +b×r5 +c×r4 +d×r3 +e×r2 +f ×r1 +g×r0 +h×r−1 +i×r−2 +j×r−3 +k×r−4

1.2.

Del Sistemas Decimal al Sistema Binario

Consideremos el n´ umero 17 en base 10 (de aqu´ı en adelante se omite la base si ´esta es 10) este se puede escribir en base 2 de la siguiente forma (17)10 = (10001)2 en efecto 1 × 24 + 0 × 23 + 0 × 22 + 0 × 21 + 1 × 20 = 16 + 1 = 17, o tambi´en 427.325 ≈ (110101011.0101001)2

Ahora (1001.11101)2 = 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20 + 1 × 2−1 + 1 × 2−2 + 1 × 2−3 + 0 × 2−4 + 1 × 2−5 = 9.90625. En general si N es un n´ umero natural entonces existen cifras a0 , a1 , a2 , a3 , . . . , aK ∈ {0, 1} tales que N = aK × 2K + aK−1 × 2K−1 + aK−2 × 2K−2 + · · · + a1 × 21 + a0 × 20 . Un algoritmo para encontrar la representaci´on binaria de un n´ umero natural N , se puede establecer si dividimos la expresi´on anterior entre dos teniendo entonces que N a0 = aK × 2K−1 + aK−1 × 2K−2 + aK−2 × 2K−3 + · · · + a1 × 20 + , 2 2 si llamamos P0 = aK × 2K−1 + aK−1 × 2K−2 + aK−2 × 2K−3 + · · · + a1 × 20 , entonces

N a0 = P0 + , 2 2 luego a0 es el resto que resulta de dividir a N entre dos, dividiendo ahora a P0 entre dos se tiene que a1 P0 = aK × 2K−2 + aK−1 × 2K−3 + aK−2 × 2K−4 + · · · + a3 × 21 + a2 × 20 + , 2 2 ´ CAP´ITULO 1. NUMEROS EN LA COMPUTADORA

5

An´ alisis Num´ erico. Notas de clase

con lo que

P0 a1 = P1 + , 2 2

donde P1 = aK × 2K−2 + aK−1 × 2K−3 + aK−2 × 2K−4 + · · · + a3 × 21 + a2 × 20 o sea que a1 es el resto de dividir a P0 entre dos, y se continua este procedimiento hasta que se encuentre un n´ umero K, tal que PK = 0, de lo anterior se tiene el siguiente algoritmo N = 2P0 + a0 P0 = 2P1 + a1 . . . PK−2 = 2PK−1 + aK−1 PK−1 = 2PK + aK

PK = 0

Ejemplo 1.2.1. Utilizar el algoritmo anterior para escribir a 1357 en notaci´on binaria. Soluci´ on 1357 = 678 × 2 + 1,

a0 = 1

678 = 339 × 2 + 0,

a1 = 0

339 = 169 × 2 + 1,

a2 = 1

169 = 84 × 2 + 1,

a3 = 1

84 = 42 × 2 + 0,

a4 = 0

42 = 21 × 2 + 0,

a5 = 0

21 = 10 × 2 + 1,

a6 = 1

10 = 5 × 2 + 0,

a7 = 0

5 = 2 × 2 + 1,

a8 = 1

2 = 1 × 2 + 0,

a9 = 0

1 = 0 × 2 + 1,

a10 = 1

1.2. DEL SISTEMAS DECIMAL AL SISTEMA BINARIO

6

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

luego 1357 = a10 a9 a8 a7 a6 a5 a4 a3 a2 a1 a0 = (10101001101)2 ¥ Supongamos ahora se tiene Q ∈ R con 0 < Q < 1, entonces existen, b1 , b2 , b3 , b4 · · · ∈ {0, 1}, tal que Q = 0.b1 b2 b3 b4 b5 . . . , y por tanto Q = b1 × 2−1 + b2 × 2−2 + b3 × 2−3 + · · · + bk × 2−k + . . . si multiplicamos a Q por dos se tiene que 2Q = b1 + b2 × 2−1 + b3 × 2−2 + · · · + bk × 2−k+1 + . . . si F1 = f rac(2Q), donde f rac(x) es la parte fraccionaria de x, y b1 = [|2Q|], donde [|x|], es la parte entera de x, entonces F1 = b2 × 2−1 + b3 × 2−2 + · · · + bk × 2−k+1 + . . . , multiplicando ahora a F1 por dos se tiene que 2F1 = b2 + b3 × 2−1 + · · · + bk × 2−k+2 + · · · = b2 + F2 , donde F2 = f rac(2F1 ), y b2 = [|2F1 |], continuando este proceso formamos dos sucesiones {bk } y {Fk }, dadas por bk = [|2Fk−1 |] y Fk = f rac(2Fk−1 ), con b1 = [|2Q|] y F1 = f rac(2Q) se tiene entonces que la representaci´on binaria de Q es ∞ X Q= bi 2−i i=1

Ejemplo 1.2.2. Utilizar el algoritmo anterior para escribir a 0.234 en notaci´on binaria. Soluci´ on Sea Q = 0.234, entonces 2Q = 0.468,

b1 = [|0.468|] = 0

F1 = f rac(0.468) = 0.468

2F1 = 0.936,

b2 = [|0.936|] = 0

F2 = f rac(0.936) = 0.936

2F2 = 1.872,

b3 = [|1.872|] = 1

F3 = f rac(1.872) = 0.872

´ CAP´ITULO 1. NUMEROS EN LA COMPUTADORA

7

An´ alisis Num´ erico. Notas de clase

2F3 = 1.744,

b3 = [|1.744|] = 1

F4 = f rac(1.744) = 0.744

2F4 = 1.488,

b5 = [|1.488|] = 1

F5 = f rac(1.488) = 0.488

2F5 = 0.976,

b6 = [|0.976|] = 0

F6 = f rac(0.976) = 0.976

2F6 = 1.952,

b7 = [|1.952|] = 1

F7 = f rac(1.952) = 0.952

. . de lo anterior se tiene que Q = 0.234 = (0.0011101 . . . )2 ¥

1.3.

N´ umeros en Punto Flotante

Definici´ on 1.3.1. Los n´ umeros en punto flotante son n´ umeros reales de la forma ±α × β e donde α tiene un n´ umero de d´ıgitos limitados, β es la base y e es el exponente que hace cambiar de posici´ on al punto decimal. Definici´ on 1.3.2. Un n´ umero real x tiene una representaci´on punto flotante normalizada si x = ±α × β e con

1 β

< |α| < 1

En el caso que x tenga representaci´on punto flotante normalizada entonces x = ±0, d1 d2 ...dk × β e donde si x 6= 0, d1 6= 0, 0 ≤ di < β, i = 1, 2, 3, ....k y L ≤ e ≤ U . Definici´ on 1.3.3. El conjunto de los n´ umeros en punto flotante se le llama, conjunto de n´ umeros de m´aquina. El conjunto de n´ umero de m´aquina es finito, ya que si x = ±0.d1 d2 d3 d4 · · · dt × β e , con d1 6= 0, 0 ≤ di ≤ β − 1, L ≤ e ≤ U , entonces para asignarle valor a d1 , hay β − 1 posibles valores y para di , i = 2, 3, 4, . . . t hay β posibles asignaciones, luego, entonces existir´an ´ 1.3. NUMEROS EN PUNTO FLOTANTE

8

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

(β − 1) ββ · · · β = (β − 1)β t−1 , fracciones positivas. | {z } t−1 factores

Pero, como el n´ umero de exponentes es U − L + 1 en total habr´an (β − 1)β t−1 (U − L + 1) n´ umeros de m´aquina positivos y tomando los n´ umeros m´aquina negativos, el total de n´ umeros de m´aquina es 2(β − 1)β t−1 (U − L + 1) + 1, teniendo en cuenta que el cero es tambi´en un n´ umero de m´aquina. Esto significa que cualquier n´ umero real debe ser representado por t−1 uno de los 2(β − 1)β (U − L + 1) + 1 n´ umero de m´aquina. Ejemplo 1.3.1. Como ejemplo, tomemos β = 2, t = 3, L = −2 y U = 2, en este caso, las mantisas ser´ıan (0.100)2 , (0.101)2 , (0.110)2 y (0.111)2 los 1 5 3 y cuales son la representaci´on en base dos de los n´ umeros reales , , 2 8 4 7 respectivamente, el total de n´ umeros es m´aquina aparecen en la siguiente 8 tabla -2 (0.100)2 × 2−2 (0.101)2 × 2−2 (0.110)2 × 2−2 (0.111)2 × 2−2

-1 (0.100)2 × 2−1 (0.101)2 × 2−1 (0.110)2 × 2−1 (0.111)2 × 2−1

0 (0.100)2 × 20 (0.101)2 × 20 (0.110)2 × 20 (0.111)2 × 20

1 (0.100)2 × 21 (0.101)2 × 21 (0.110)2 × 21 (0.111)2 × 21

2 (0.100)2 × 22 (0.101)2 × 22 (0.110)2 × 22 (0.111)2 × 22

TABLA 1 que corresponden respectivamente a los n´ umeros reales de la siguiente tabla

4 32

8 32

16 32

32 32

64 32

5 32

10 32

20 32

40 32

80 32

6 32

12 32

24 32

48 32

96 32

7 32

14 32

28 32

56 32

112 32

´ CAP´ITULO 1. NUMEROS EN LA COMPUTADORA

9

An´ alisis Num´ erico. Notas de clase

TABLA 2 El total de n´ umeros de m´aquina es 2(2 − 1) × 22 (2 + 2 + 1) + 1 = 41 los cuales son 4 5 6 7 8 10 12 14 16 20 24 0, ± , ± , ± , ± , ± , ± , ± , ± , ± , ± , ± 32 32 32 32 32 32 32 32 32 32 32 32 40 48 56 64 80 96 112 28 ± ,± ,± ,± ,± ,± ,± ,± ,± 32 32 32 32 32 32 32 32 32

1.4.

Notaci´ on Cient´ıfica Normalizada

En la secci´on anterior, hablamos de representaci´on punto flotante y punto flotante normalizado, de acuerdo a eso si x ∈ R est´a en base 10 este se puede normalizar tomando x = ±r × 10n con 0.1 ≤ r < 10 y n un entero. Obviamente si x = 0 entonces r = 0

Ejemplo 1.4.1. 1) 732.5051 se puede representar como punto flotante normalizado escribiendo 732.5051 = 0.7325051 × 103 . 2) De la misma manera −0.005612 = −0.5612 × 10−2 Por otro lado si x est´a en el sistema binario, se puede representar en punto flotante normalizado si se escribe de la forma x = ±q × 2m , donde 0.5 ≤ q < 1 y m es un entero. Ejemplo 1.4.2. 1) (101.01)2 = 0.10101 × 23 2) (0.0010111)2 = 0.10111 × 2−2 Nota: (0.1)2 = 1 × 2−1 = 0.5. En una computadora los n´ umeros se representan de la manera anteriormente comentada, pero con ciertas restricciones sobre q y m impuestas por la longitud de la palabra. Si suponemos se tiene una computadora hipot´etica, la cual llamaremos NORM-32, y si adem´as suponemos que tiene una longitud de palabra de 32 bits (1bit = 1Binary digital), estos se distribuyen de la manera siguiente:

´ CIENT´IFICA NORMALIZADA 1.4. NOTACION

10

J Vel´ asquez Zapateiro/ V. Obeso Fern´ andez

donde los dos primeros espacios son reservado para los signos, asign´andole cero si el signo es positivo y uno si es negativo, los siguientes siete espacios para el exponente y los restantes para la mantisa. Dado que un n´ umero real distinto de cero x = ±q × 2m , siempre puede normalizarse de tal manera que 21 ≤ q < 1, podemos suponer que el primer bit en q es 1, y por lo tanto no requiere almacenamiento esto es, si se quiere almacenar en NORM-32 el n´ umero 0.828125 el cual es equivalente 0 a (0.110101)2 × 2 esto se hace de la forma indicada. 0

0

0

0

0

0

0

0

0

1

0

1

0

1

.

.

.

.

.

.

0

Ejemplo 1.4.3. Representar y almacenar en punto flotante normalizado -0.125 Soluci´ on Se tiene que 0.125 × 2 = 0.25 | 0 0.25 × 2 = 0.5 | 0 0.5 × 2 = 1 | 1,

entonces

−0.125 = (−0.001)2 = (−0.1)2 × 2−2 .

Adem´as

2 = (10)2 , as´ı que su representaci´on es 1

1

0

0

0

...