ANALISIS_NUMERICO_BASICO_CON_PYTHON_0.pdf

7/25/2019 ANALISIS_NUMERICO_BASICO_CON_PYTHON_0.pdf

1/357

Escuela Superior Politcnica del Litoral

Facultad de Ciencias Naturales y MatemticasDepartamento de Matemticas

ANLISIS NUMRICO BSICOUn enfoque algortmico con el soporte de Python

Libro digitalVersin 4.0 - 2015

Luis Rodrguez Ojeda


2/357

2

ANLISIS NUMRICO BSICOUn enfoque algortmico con el soporte de Python

Prefacio

Esta obra es una contribucin dedicada a los estudiantes que toman un curso de AnlisisNumrico o Mtodos Numricos en carreras de ingeniera. El pre-requisito es haber tomadolos cursos de matemticas del ciclo bsico de nivel universitario y alguna experiencia previacon un programa computacional del tipo MATLAB, Mathematica, o Python para aprovecharel poder computacional en la aplicacin de los mtodos numricos de manera efectiva.

El contenido se basa en la experiencia desarrollada en varios aos impartiendo los cursosde Anlisis Numrico, Mtodos Numricos en las carreras de ingeniera. Esta obra pretendeser un texto complementario para estas materias. La orientacin principal del material es suaplicacin computacional, sin descuidar los conceptos matemticos y algortmicos bsicoscon los que se fundamentan los mtodos numricos.

Este texto contribuye tambin a difundir entre los estudiantes el uso del programa Pythonpara clculos, graficacin y manejo matemtico simblico como un soporte comn paratodos los cursos bsicos matemticos, incluyendo lgebra Lineal, Clculo Diferencial eIntegral, Ecuaciones Diferenciales, Anlisis Numrico y otros, como lo fue anteriormente ellenguaje MATLAB.

Python dispone de funciones en libreras especiales para su aplicacin en la solucin de unagran cantidad de problemas matemticos, sin embargo sera equivocado usarlas como unareceta sin el conocimiento de sus fundamentos matemticos y algortmicos. En este cursose desarrollan algunos mtodos alternativos a las que ofrecen las libreras de Python, y enalgunos casos, nuevos mtodos cuya programacin es instructiva para orientar a losestudiantes en el desarrollo de software para matemticas e ingeniera.

El segundo objetivo principal de esta obra es contribuir al desarrollo de textos digitales en laESPOL de tal manera que puedan ser usados en lnea e interactivamente, aunque tambinpuedan imprimirse, pero tratando de reducir al mnimo el uso de papel para contribuir alcuidado del medio ambiente. Otra ventaja importante de los textos digitales es que puedenser actualizados y mejorados continuamente sin costos de impresin. El texto ha sidocompilado en formato que permite controlar el tamao de la pantalla y se puede agregar unndice para bsqueda rpida de temas. Se pueden usar facilidades para resaltar y marcartexto, agregar comentarios, notas, enlaces, revisiones, etc.

Esta obra es de uso y distribucin libres y estar disponible para uso pblico en elrepositorio digital del Departamento de Matemticas de la Facultad de Ciencias Naturales yMatemticas en la pgina web de la ESPOL: www.espol.edu.ec

Luis Rodrguez Ojeda, MSc.Profesor

[email protected]


3/357

3

CONTENIDO1 Introduccin 8

1.1 Resolucin de problemas con el computador 81.2 Fuentes de error en la resolucin de un problema numrico 91.3 El modelo matemtico 10

1.4 Algoritmos numricos 101.5 Instrumentacin computacional 101.6 Un ejemplo inicial 111.7 Preguntas 13

2 Tipos de mtodos numricos 142.1 Mtodos iterativos 14

2.1.1 Convergencia de los mtodos iterativos 172.1.2 Error de truncamiento 172.1.3 Finalizacin de un proceso iterativo 182.1.4 Error de truncamiento y estimacin del error 192.1.5 Eficiencia de un mtodo iterativo 192.1.6 Eleccin del valor inicial 202.1.7 Preguntas 20

2.2 Mtodos directos 212.2.1 Error de redondeo 232.2.2 Error en la representacin de nmeros reales 242.2.3 Error de redondeo en las operaciones aritmticas 252.2.4 Propagacin del error de redondeo en operaciones aritmticas 272.2.5 Eficiencia de los mtodos directos 292.2.6 La notacin O( ) 312.2.7 Ejercicios 33

3 Races reales de ecuaciones no-lineales 343.1 Mtodo de la biseccin 34

3.1.1 Existencia de la raz real 343.1.2 Convergencia del mtodo de la biseccin 35

3.1.3 Algoritmo del mtodo de la biseccin 363.1.4 Eficiencia del mtodo de la biseccin 373.1.5 Instrumentacin computacional del mtodo de la biseccin 38

3.2 Mtodo del punto fijo 403.2.1 Existencia del punto fijo 403.2.2 Convergencia del mtodo del punto fijo 413.2.3 Unicidad del punto fijo 423.2.4 Algoritmo del punto fijo 423.2.5 Eficiencia del mtodo del punto fijo 46

3.3 Mtodo de Newton 473.3.1 La frmula de Newton 473.3.2 Algoritmo del mtodo de Newton 483.3.3 Interpretacin grfica de la frmula de Newton 51

3.3.4 Convergencia del mtodo de Newton 523.3.5 Una condicin de convergencia local para el mtodo de Newton 533.3.6 Prctica computacional 573.3.7 Instrumentacin computacional del mtodo de Newton 62

3.4 Ejercicios y problemas de ecuaciones no-lineales 65


4/357

4

3.5 Races reales de sistemas de ecuaciones no-lineales 713.5.1 Frmula iterativa de segundo orden para calcular races reales

de sistemas de ecuaciones no-lineales 713.5.2 Convergencia del mtodo de Newton para sistemas no-lineales 723.5.3 Algoritmo del mtodo de Newton para sistemas no-lineales 723.5.4 Prctica computacional 75

3.5.5 Instrumentacin computacional del mtodo de Newton pararesolver un sistema de n ecuaciones no-lineales 743.5.6 Obtencin de la frmula iterativa de segundo orden para calcular

races reales de sistemas de ecuaciones no-lineales 783.5.7 Ejercicios y problemas con sistemas de ecuaciones no lineales 80

4 Mtodos directos para resolver sistemas de ecuaciones lineales 814.1 Determinantes y sistemas de ecuaciones lineales 824.2 Mtodo de Gauss-Jordan 82

4.2.1 Formulacin del mtodo de Gauss-Jordan 844.2.2 Algoritmo de Gauss-Jordan bsico 864.2.3 Eficiencia del mtodo de Gauss-Jordan 874.2.4 Instrumentacin computacional del mtodo de Gauss-Jordan 88

4.2.5 Obtencin de la inversa de una matriz 904.3 Mtodo de Gauss 924.3.1 Formulacin del mtodo de Gauss 934.3.2 Algoritmo de Gauss bsico 944.3.3 Eficiencia del mtodo de Gauss 954.3.4 Instrumentacin computacional del mtodo de Gauss 964.3.5 Estrategia de pivoteo 974.3.6 Algoritmo de Gauss con pivoteo 984.3.7 Instrumentacin computacional del mtodo de Gauss con pivoteo 994.3.8 Funciones de Python para sistemas de ecuaciones lineales 1004.3.9 Clculo del determinante de una matriz 101

4.4 Sistemas mal condicionados 1024.4.1 Definiciones 104

4.4.2 Algunas propiedades de normas 1054.4.3 Nmero de condicin 1054.4.4 El nmero de condicin y el error de redondeo 1074.4.5 Funciones de Python para normas y nmero de condicin 111

4.5 Sistemas singulares 1124.5.1 Formulacin matemtica y algoritmo 1124.5.2 Instrumentacin computacional para sistemas singulares 116

4.6 Sistema tridiagonales 1224.6.1 Formulacin matemtica y algoritmo 1224.6.2 Instrumentacin computacional del mtodo de Thomas 124

5 Mtodos iterativos para resolver sistemas de ecuaciones lineales 1265.1 Mtodo de Jacobi 126

5.1.1 Formulacin matemtica 1265.1.2 Manejo computacional de la frmula de Jacobi 1285.1.3 Algoritmo de Jacobi 1295.1.4 Instrumentacin computacional del mtodo de Jacobi 1305.1.5 Forma matricial del mtodo de Jacobi 131


5/357

5

5.2 Mtodo de Gauss-Seidel 1335.2.1 Formulacin matemtica 1335.2.2 Manejo computacional de la frmula de Gauss-Seidel 1345.2.3 Instrumentacin computacional del mtodo de Gauss-Seidel 1355.2.4 Forma matricial del mtodo de Gauss-Seidel 136

5.3 Mtodo de relajacin 137

5.3.1 Formulacin matemtica 1375.3.2 Manejo computacional de la frmula de relajacin 1385.3.3 Forma matricial del mtodo de relajacin 139

5.4 Convergencia de los mtodos iterativos para sistemas lineales 1405.4.1 Matriz de transicin para los mtodos iterativos 141

5.5 Eficiencia de los mtodos iterativos 1455.6 Estimacin del error en los mtodos iterativos 1455.7 Instrumentacin computacional del mtodo de Jacobi con el radio 146

espectral5.8 Prctica computacional con los mtodos iterativos 1495.9 Ejercicios y problemas con sistemas de ecuaciones lineales 151

6 Interpolacin 161

6.1 El polinomio de interpolacin 1616.1.1 Existencia del polinomio de interpolacin 1626.1.2 Unicidad del polinomio de interpolacin con diferentes mtodos 164

6.2 El polinomio de interpolacin de Lagrange 1656.2.1 Algoritmo del polinomio de interpolacin de Lagrange 1666.2.2 Eficiencia del mtodo de Lagrange 1676.2.3 Instrumentacin computacional del mtodo de Lagrange 168

6.3 Interpolacin mltiple 1706.3.1 Instrumentacin computacional para dos variables 172

6.4 Error en la interpolacin 1736.4.1 Una frmula para aproximar el error en la interpolacin 175

6.5 Diferencias finitas 1766.5.1 Relacin entre derivadas y diferencias finitas 177

6.5.2 Diferencias finitas de un polinomio 1786.6 El polinomio de interpolacin de diferencias finitas 180

6.6.1 Prctica computacional 1826.6.2 Eficiencia del polinomio de interpolacin de diferencias finitas 1836.6.3 El error en el polinomio de interpolacin de diferencias finitas 1846.6.4 Forma estndar del polinomio de diferencias finitas 1866.6.5 Otras formas del polinomio de interpolacin de diferencias finitas 187

6.7 El polinomio de interpolacin de diferencias divididas 1886.7.1 El error en el polinomio de interpolacin de diferencias divididas 191

6.8 El polinomio de mnimos cuadrados 1926.9 Ejercicios y problemas con el polinomio de interpolacin 1956.10 El trazador cbico 199

6.10.1 El trazador cbico natural 200

6.10.2 Algoritmo del trazador cbico natural 2036.10.3 Instrumentacin computacional del trazador cbico natural 2056.10.4 El trazador cbico sujeto 2086.10.5 Algoritmo del trazador cbico sujeto 2106.10.6 Instrumentacin computacional del trazador cbico sujeto 2116.10.7 Ejercicios con el trazador cbico 214


6/357

6

7 Integracin numrica 2157.1 Frmulas de Newton-Cotes 216

7.1.1 Frmula de los trapecios 2167.1.2 Error de truncamiento en la frmula de los trapecios 2187.1.3 Instrumentacin computacional de la frmula de los trapecios 2227.1.4 Frmula de Simpson 224

7.1.5 Error de truncamiento en la frmula de Simpson 2267.1.6 Instrumentacin computacional de la frmula de Simpson 2287.1.7 Error de truncamiento vs. Error de redondeo 229

7.2 Obtencin de frmulas de integracin numrica con el mtodo decoeficientes indeterminados 231

7.3 Cuadratura de Gauss 2327.3.1 Frmula de la cuadratura de Gauss con dos puntos 2327.3.2 Instrumentacin computacional de la cuadratura de Gauss 2357.3.3 Instrumentacin extendida de la cuadratura de Gauss 236

7.4 Integrales con lmites no acotados 2377.5 Integrales con rango no acotado 2387.6 Integrales mltiples 241

7.6.1 Instrumentacin computacional de la frmula de Simpson en

dos direcciones 2437.7 Casos especiales 2457.7.1 Integrales dobles con lmites variables 2457.7.2 Integrales dobles con puntos singulares 2457.7.3 Integrales dobles con puntos singulares y lmites variables 247

7.8 Ejercicios y problemas de integracin numrica 248

8 Diferenciacin numrica 2548.1 Obtencin de frmulas de diferenciacin numrica 2548.2 Una frmula para la primera derivada 2548.3 Una frmula de segundo orden para la primera derivada 2568.4 Una frmula para la segunda derivada 2588.5 Obtencin de frmulas de diferenciacin numrica con el mtodo

de coeficientes indeterminados 2588.6 Algunas otras frmulas de inters para evaluar derivadas 2598.7 Extrapolacin para diferenciacin numrica 2608.8 Ejercicios de diferenciacin numrica 261

9 Mtodos numricos para resolver ecuaciones diferenciales ordinarias 2629.1 Ecuaciones diferenciales ordinarias de primer orden con la condicin

en el inicio 2639.1.1 Existencia de la solucin 2649.1.2 Mtodo de la serie de Taylor 2659.1.3 Instrumentacin computacional del mtodo de Taylor 2679.1.4 Obtencin de derivadas de funciones implcitas 2709.1.5 Instrumentacin de un mtodo general para resolver una E.D.O.

con la serie de Taylor 2729.1.6 Frmula de Euler 2749.1.7 Error de truncamiento y error de redondeo 2759.1.8 Instrumentacin computacional de la frmula de Euler 2779.1.9 Frmula mejorada de Euler o frmula de Heun 2789.1.10 Instrumentacin computacional de la frmula de Heun 2809.1.11 Frmulas de Runge-Kutta 2829.1.12 Instrumentacin computacional de la frmula de Runge-Kutta 284


7/357

7

9.2 Sistemas de ecuaciones diferenciales ordinarias de primer ordencon condiciones en el inicio 2879.2.1 Frmula de Heun extendida a dos E. D. O. de primer orden 2879.2.2 Instrumentacin computacional de la frmula de Heun para

dos E. D. O. de primer orden 2899.2.3 Frmula de Runge-Kutta para dos E. D. O. de primer orden

y condiciones en el inicio 2919.2.4 Instrumentacin computacional de la frmula de Runge-Kuttapara dos E.D.O de primer orden 292

9.3 Ecuaciones diferenciales ordinarias de mayor orden y condicionesen el inicio 2949.3.1 Instrumentacin computacional 296

9.4 Ecuaciones diferenciales ordinarias no lineales 2999.5 Convergencia y estabilidad numrica 3009.6 Ecuaciones diferenciales ordinarias con condiciones en los bordes 301

9.6.1 Mtodo de prueba y error (mtodo del disparo) 3019.6.2 Mtodo de diferencias finitas 3049.6.3 Instrumentacin computacional del mtodo de diferencias finitas 3079.6.4 Ecuaciones diferenciales ordinarias con condiciones en

los bordes con derivadas 3099.6.5 Instrumentacin computacional con derivadas en los bordes 3109.6.6 Normalizacin del dominio de la E.D.O. 313

9.7 Ecuaciones diferenciales ordinarias con condiciones en el inicio:Frmulas de pasos mltiples 3149.7.1 Frmulas de pasos mltiples de prediccin 3149.7.2 Frmulas de pasos mltiples de correccin 3169.7.3 Mtodos de Prediccin Correccin 317

9.8 Ejercicios con ecuaciones diferenciales ordinarias 318

10 Mtodo de diferencias finitas para resolver ecuaciones diferenciales parciales 32110.1 Aproximaciones de diferencias finitas 32110.2 Ecuaciones diferenciales parciales de tipo parablico 322

10.2.1 Un esquema de diferencias finitas explcito 32310.2.2 Estabilidad del mtodo de diferencias finitas 32510.2.3 Instrumentacin computacional del mtodo explcito 32710.2.4 Un esquema de diferencias finitas implcito 32910.2.5 Instrumentacin computacional del mtodo implcito 33110.2.6 Prctica computacional 33310.2.7 Condiciones variables en los bordes 33310.2.8 Instrumentacin computacional con derivadas en los bordes 33510.2.9 Mtodo de diferencias finitas para EDP no lineales 338

10.3 Ecuaciones diferenciales parciales de tipo elptico 33910.3.1 Un esquema de diferencias finitas implcito 34010.3.2 Instrumentacin computacional de una E.D.P. tipo elptico 343

10.4 Ecuaciones diferenciales parciales de tipo hiperblico 348

10.4.1 Un esquema de diferencias finitas explcito para resolver la EDPhiperblica 348

10.4.2 Instrumentacin computacional de una E.D.P. tipo hiperblico 35110.5 Ejercicios con ecuaciones diferenciales parciales 355

Bibliografa 357


8/357

8

ANLISIS NUMRICOUn enfoque algortmico con el soporte de Python

1 INTRODUCCIN

Anlisis Numrico es una rama de la matemtica cuyo objetivo principal es el estudio demtodos para resolver problemas numricos complejos. El estudio de estos mtodos no esreciente, pero actualmente con el apoyo de la computacin se los puede usar con muchaeficiencia en la resolucin de problemas que antes no era posible.

En este curso se proporciona a los estudiantes el conocimiento matemtico bsico paraproveer soporte y formalidad a cada uno de los mtodos estudiados. Se desarrolla la formaalgortmica de los mtodos y finalmente se instrumenta su forma computacional usando lacapacidad de clculo, visualizacin y programacin de Python. Este componente prcticodel curso es desarrollado en un laboratorio de computacin.

El estudio de cada mtodo se complementa con el desarrollo de ejemplos y ejercicios quepueden resolverse con la ayuda de una calculadora. Sin embargo, el objetivo principal delcurso es la aplicacin de los mtodos para obtener respuestas con precisin controlada enla resolucin de algunos problemas de ingeniera que por su complejidad requieren usar elcomputador.

1.1 Resolucin de problemas con el computador

Suponer un problema que debemos resolver y que est en nuestro mbito de conocimiento.

En la etapa deAnlisises necesario estudiar y entender el problema. Sus caractersticas,las variables y los procesos que intervienen. Asimismo, debemos conocer los datos

requeridos y el objetivo esperado. En el caso de problemas de tipo numrico, el resultado deesta etapa ser un modelo matemtico que caracteriza al problema. Por ejemplo, unsistema de ecuaciones lineales.

En la etapa de Diseoprocedemos a elegir el mtodo numrico apropiado para resolver elmodelo matemtico. Debe suponerse que no se puede, o que sera muy laborioso, obtenerla solucin exacta mediante mtodos analticos. Los mtodos numricos permiten obtener


9/357

9

soluciones aproximadas con simplicidad. El resultado de esta etapa es la formulacinmatemtica del mtodo numrico y la elaboracin de un algoritmopara usarlo.En la etapa de Instrumentacin elegimos el dispositivo de clculo para la obtencin deresultados. En problemas simples, basta una calculadora. Para problemas complejos,requerimos el computador mediante funciones predefinidas y en algunos casos,

desarrollando programas y funcionesen un lenguaje computacional. Esta ltima opcin esimportante para la comprensin de los mtodos.

Este proceso debe complementarse con una revisin y retroalimentacin. Es preferibleinvertir ms tiempo en las primeras etapas, antes de llegar a la instrumentacin.

1.2 Fuentes de error en la resolucin de un problema numrico

En el Anlisis pueden introducirse errores debido a suposiciones inadecuadas,simplificaciones y omisiones al construir el modelo matemtico. Estos errores se denominanerrores inherentes.

En el Diseose pueden introducir errores en los mtodos numricos utilizados los cuales seconstruyen mediante frmulas y procedimientos simplificados para obtener respuestasaproximadas. Tambin se pueden introducir errores al usar algoritmos iterativos. Estoserrores se denominan errores de truncamiento.

En la Instrumentacin se pueden introducir errores en la representacin finita de losnmeros reales en los dispositivos de almacenamiento y en los resultados de lasoperaciones aritmticas. Este tipo de error se denomina error de redondeo. Tambin sepueden introducir errores de redondeo al usar datos imprecisos.

Los errores son independientes y su efecto puede acumularse. En el caso del error deredondeo el efecto puede incrementarse si los valores que se obtienen son usados en formaconsecutiva en una secuencia de clculos.

Debido a que los mtodos numricos en general permiten obtener nicamenteaproximaciones para la respuesta de un problema, es necesario definir alguna medida paracuantificar el error en el resultado obtenido. Normalmente no es posible determinarexactamente este valor por lo que al menos debe establecerse algn criterio para estimarloo acotarlo. Esta informacin es til para conocer la precisin de los resultados calculados.


10/357

10

1.3 El modelo matemtico

Al resolver un problema con el computador, la parte ms laboriosa normalmente es elanlisis del problema y la obtencin del modelo matemtico que finalmente se usar parallegar a la solucin.

El modelo matemtico es la descripcin matemtica del problema que se intenta resolver.Esta formulacin requiere conocer el mbito del problema y los instrumentos matemticospara su definicin.

1.4 Algoritmos numricos

Un algoritmo es una descripcin ordenada de los pasos necesarios para resolver unproblema. El diseo de un algoritmo para resolver un problema numrico requiere conoceren detalle la formulacin matemtica, las restricciones de su aplicacin, los datos y algncriterio para validar y aceptar los resultados obtenidos.

Esta descripcin facilita la instrumentacin computacional del mtodo numrico. Enproblemas simples puede omitirse la elaboracin del algoritmo e ir directamente a lacodificacin computacional.

1.5 Instrumentacin computacional

En este curso se usar el lenguaje computacional Python para instrumentar los algoritmoscorrespondientes a los mtodos numricos estudiados. La aplicacin computacional puederealizarse usando directamente la funcionalidad disponible en el lenguaje, sin embargo para

comprender y aplicar los mtodos numricos es preferible instrumentar el algoritmoconstruyendo funciones en el lenguaje computacional y tratando de que seanindependientes de los datos especficos de un problema particular, facilitando as sureutilizacin. Estas funciones pueden llamarse desde la ventana interactiva o mediante unprograma que contiene los datos del problema que se desea resolver.


11/357

11

1.6 Un ejemplo inicial

A continuacin se proporciona un ejemplo para seguir el procedimiento descrito en laresolucin de un problema con los mtodos numricos.

Problema. Se necesita un recipiente rectangular, sin tapa, de un litro de capacidad. Paraconstruirlo se debe usar una lmina rectangular de 32 cm de largo y 24cm de ancho. Elprocedimiento ser recortar un cuadrado idntico en cada una de las cuatro esquinas ydoblar los bordes de la lmina para formar el recipiente.

Determine la medida del lado del cuadrado que se debe recortar en cada esquina para queel recipiente tenga la capacidad requerida.

Anlisis

Para formular el modelo matemtico el problema debe entenderse detalladamente. En esteejemplo un dibujo facilita su elaboracin.

Sea: x: medida del lado de los cuadrados que se deben recortar para formar la caja

Lados de la caja (cm): x, (32 2x), (24 2x)

Volumen: 1 litro = 1000 cm3

Ecuacin: 1000 = (32 2x)(24 2x)x250 192x + 28x2 x3 = 0

El modelo matemtico es una ecuacin polinmica de tercer grado que no se puede resolverdirectamente con la conocida frmula de la ecuacin cuadrtica, por lo tanto se utilizar unmtodo numrico.

Algoritmo

Los clculos sern realizados directamente en la ventana interactiva de Python usando laslibreras necesarias.


12/357

12

Instrumentacin

Definicin y grfico de la ecuacin usando la librera Pylab>>>frompylabimport*

>>>x=arange(0,20,0.1)

>>>

f=250

192*x+28*x**2

x**3

>>>plot(x,f)

>>>grid(True)

>>>show()

Se observan tres respuestas reales positivas para la ecuacin.

Obtencin de la solucin con la libreraSymPy>>>fromsympyimport*

>>>x=Symbol('x')

>>>f=250192*x+28*x**2x**3

>>>r=solve(f)

>>>len(r) (r es un vector con tres soluciones)3

>>>r[0].evalf(10)

1.696276832+0.e17*I (el componente imaginario se debe a la imprecisin)>>>r[1].evalf(10)

8.09321954+0.e17*I

>>>r[2].evalf(10)

18.21050363 0.e16*I

Las tres son respuestas para la ecuacin. La tercera respuesta no es factible para elproblema, pues se obtendran valores negativos para las otras dimensiones de la caja. Laprimera respuesta pudiera ser descartada porque la caja tendra una apariencia muy planapor lo cual elegimos la segunda como la respuesta adecuada para el problema.

Respuesta: Lados de la caja en centmetros: 8.09, 15.81, 7.81 aproximadamente.


13/357

13

El traductor Pythonse lo puede descargar de la red internet del sitio oficial de Python:

www.python.org

La librera Pylab es til para graficar funciones. Esta librera est incluida en la librera

Matplotlib. Otras libreras de inters para aplicaciones en ingeniera, matemticas y otrasciencias son SymPy para manejo matemtico simblico, NumPy para manejo nmricoincluyendo muchas funciones para lgebra lineal, y SciPy para aplicaciones matemticasavanzadas.

Estas libreras se las puede descargar del sitio Web:

www.lfd.uci.edu/~gohlke/pythonlibs/

Python y las libreras son de uso pblico y pertenecen a la categora de software libre

Con los mtodos numricos desarrollados en este curso se puede construir una librera paraagregar o sustituir las funciones disponibles de los mtodos numricos y es la contribucinde este curso para los usuarios interesados en resolver computacionalmente muchosproblemas numricos con el lenguaje Python. Adicionalmente, es una actividad formativapara usuarios interesados en desarrollar software para matemticas e ingeniera.

Los usuarios interesados en complementar el conocimiento del lenguaje Python puedendescargar el texto digital Python Programacin de la pgina del Departamento deMatemticas de la Facultad de Ciencias Naturales y Matemticas en la pgina web de laESPOL, o revisar otras fuentes de informacin en la red internet:

www.espol.edu.ec

1.7 Preguntas

1.Cual etapa del proceso de resolucin de un problema numrico requiere ms atencin?

2.Qu conocimientos son necesarios para formular un modelo matemtico?

3.En el ejemplo de la caja Cual sera la desventaja de intentar obtener experimentalmentela solucin mediante prueba y error en lugar de analizar el modelo matemtico?

4.Que es ms crtico: el error de truncamiento o el error de redondeo?

5.Cul es la ventaja de instrumentar computacionalmente un mtodo numrico?

6.Por que es importante validar los resultados obtenidos?


14/357

14

2 TIPOS DE MTODOS NUMRICOS

Existen dos estrategias para disear mtodos numricos y es importante conocer suscaractersticas para elegirlos adecuadamente, as como su instrumentacin computacional

2.1 Mtodos iterativos

Los mtodos iterativos son procedimientos para acercarse a la respuesta medianteaproximaciones sucesivas. Estos mtodos incluyen frmulas que tienen la propiedad deproducir un resultado ms cercano a la respuesta a partir de un valor inicial estimado. Elresultado obtenido se puede usar nuevamente como valor anterior para continuar mejorandola respuesta.

Se deben considerar algunos aspectos tales como la eleccin del valor inicial, la propiedadde convergencia de la frmula y el criterio para terminar las iteraciones.

Estos mtodos son auto-correctivos. La precisin de la respuesta est dada por la distancia

entre el ltimo valor calculado y la respuesta esperada. Esto constituye el error detruncamiento.

El siguiente grfico describe la estructura de un mtodo iterativo

Cada ciclo se denomina iteracin. Si la frmula converge, en cada iteracin la respuestaestar ms cerca del resultado buscado. Aunque en general no es posible llegar a larespuesta exacta, se puede acercar a ella tanto como lo permita la aritmtica computacionaldel dispositivo de clculo.

Ejemplo. Instrumentar un mtodo iterativo para calcular la raz cuadrada r de un nmeroreal positivo n mediante operaciones aritmticas bsicas

Solucin

Se usar una frmula que recibe un valor estimado para la raz cuadrada y produce un valorms cercano a la respuesta. Si se usa repetidamente la frmula cada resultado tender a unvalor final que suponemos es la respuesta buscada. La obtencin de estas frmulas serealizar posteriormente.

Sean x: valor inicial estimado para la raz r

Frmula iterativa:1 n

y (x )2 x


15/357

15

Algoritmo

Algoritmo:Razcuadrada

Entra: n Dato

E Errorpermitido

x

Valor

inicial

Sale: y RespuestacalculadaconerrorE

1 ny (x )

2 x

Repetirmientras |x y| > E

xy

1 ny (x )

2 x

Fin

Ejemplo. Calcular r = 7 con la frmula iterativa anterior

Valor inicial: x = 3 c

Clculos en Python

>>>n=7

>>>x=3

>>>y=0.5*(x+n/x)

>>>print(y)

2.666666666666667

>>>x=y

>>>y=0.5*(x+n/x)

>>>print(y)

2.645833333333333

>>>x=y

>>>y=0.5*(x+n/x)

>>>print(y)

2.6457513123359577

>>>x=y

>>>y=0.5*(x+n/x)

>>>print(y)

2.6457513110645907

>>>x=y

>>>y=0.5*(x+n/x)

>>>print(y)

2.6457513110645907


16/357

16

El ltimo resultado tiene dicisis dgitos decimales que no cambian, por lo tanto podemossuponer que la respuesta tiene esa precisin. Se observa la rpida convergencia de lasucesin de nmeros generad. Sin embargo es necesario verificar si la solucin esaceptable pues si los nmeros convergen a un valor, no necesariamente es la respuestacorrecta

>>y**2

7.00000000000000

Se comprueba que el ltimo valor calculado es la raz cuadrada de 7

Ejemplo.Calcular r = 7 con la siguiente frmula iterativa:

ny 0.4(x )

x

>>>n=7

>>>x=3>>>y=0.4*(x+n/x)

>>>y

2.1333333333333337

>>>x=y

>>>y=0.4*(x+n/x)

>>>y

2.165833333333333

>>>x=y

>>>y=0.4*(x+n/x)

>>>y

2.1591382583044765

.

.

.

>>>x=y

>>>y=0.4*(x+n/x)

>>>y

2.1602468994692865

>>>x=y

>>>y=0.4*(x+n/x)

>>>y

2.160246899469287

>>>x=y

>>>y=0.4*(x+n/x)

>>>y

2.160246899469287

>>>y**2

4.666666666666668


17/357

17

La frmula converge pero el resultado final no es la raz cuadrada de 7. Esto plantea la

importancia de verificar la formulacin del mtodo numrico y la validacin de la

respuesta obtenida.

En general, los mtodos numricos se enfocan a resolver una clase o tipo de problemas. El

ejemplo anterior es un caso particular del problema general: la solucin de ecuaciones nolineales f(x)=0

2.1.1 Convergencia de los mtodos iterativos

Es la propiedad que tienen la formula iterativas de un mtodo numrico para producir

resultados cada vez ms cercanos a la respuesta esperada.

Definicin: Convergencia de una frmula iterativa

Sean r: Respuesta del problema (valor desconocido)

xi: Valor calculado en la iteracin i (valor aproximado)

Si la frmula iterativa converge, entonces

ii

x r

.

.

2.1.2 Error de truncamiento

La distancia entre la respuesta esperada y el valor calculado con una frmula iterativa se

denomina error de truncamiento.

Definicin: Error de truncamiento

Sean r: Respuesta del problema (valor desconocido)

xi: Valor calculado en la iteracin i (valor aproximado)

xi+1: Valor calculado en la iteracin i + 1 (valor aproximado)

Entonces

iE =r xi: Error de truncamiento en la iteracin i

i 1E =r xi+1: Error de truncamiento en la iteracin i + 1


18/357

18

2.1.3 Finalizacin de un proceso iterativo

Si la frmula iterativa converge, la distancia entre valores consecutivos se debe reducir y se

puede usar como una medida para el error de truncamiento. Con la definicin de

convergencia se puede establecer un criterio para finalizar el proceso iterativo.

Consideremos los resultados de dos iteraciones consecutivas: i i+1x , x

Si el mtodo converge, ii

x r

y tambin i 1i

x r

Restando estas dos expresiones: i 1 ii

x x 0

, se puede establecer un criterio de

convergencia

Definicin: Criterio para finalizar un proceso iterativo (error absoluto)

Sea Ealgn valor positivo arbitrariamente pequeo.

Si el mtodo converge, se cumplir que a partir de alguna iteracin i:

|xi+1- xi| < E .

Este valor Ees el error absoluto y se usa como una medida para el error de la respuesta

calculada.

La precisin utilizada en los clculos aritmticos, debe ser coherente con la precisin del

mtodo numrico y con los exactitud del modelo matemtico y de los datos utilizados.

Adicionalmente, es necesario verificar que la respuesta final sea vlida para el modelo

matemticoy aceptable para el problema que se est resolviendo.

Ejemplo. Se desea que la respuesta calculada para un problema con un mtodo iterativo

tenga un error absoluto menor que 0.0001. Entonces el algoritmo deber terminar cuando

se cumpla que |xi+1 - xi| < 0.0001. Los clculos deben realizarse al menos con la misma

precisin.

Para que el criterio del error sea independiente de la magnitud del resultado, conviene usar

la definicin del error relativo:

Definicin: Criterio para finalizar un proceso iterativo (error relativo)

Seaealgn valor positivo arbitrariamente pequeo.

Si el mtodo converge, se cumplir que a partir de alguna iteracin i:

i 1 i

i 1

| x x |e

| x |

.


19/357

19

Este valor e es el error relativo y puede usarse como una medida para el error de larespuesta calculada, independiente de la magnitud. Para calcular el error relativo se toma elltimo valor como el ms cercano a la respuesta.

Ejemplo. Se desea que la respuesta calculada para un problema con un mtodo iterativo

tenga un error relativo menor que 0.1%. Entonces el algoritmo deber terminar cuando secumpla que

i 1 i

i 1

| x x |0.001

| x |

Tambin debera distinguirse entre errory precisin.

Ejemplo. Si el error es1%, la precisin es 99%.

2.1.4 Error de truncamiento y estimacin del error

Debe distinguirse entre estas dos medidas del error

r xi: Error de truncamiento cuyo valor es desconocido, pues r es la respuestaque se desea calcular

xi+1 xi: Estimacin del error de truncamiento en la iteracini. Es un valor que sepuede calcular y se usa como una estimacin para el error detruncamiento si el mtodo converge. Es necesario evaluar el modelo mate-mtico con el valor calculado.

2.1.5 Eficiencia de un mtodo iterativo

Sean iE , i 1E los errores de truncamiento en las iteraciones i, i+1 respectivamente. Se

supondr que estos valores son pequeos y menores a 1.

Si a partir de alguna iteracin i esta relacin puede especificarse como | i 1E | = k | iE |,

siendo kalguna constante positiva menor que uno, entonces se dice que la convergencia eslinealo de primer ordeny kes el factor de convergencia. Se puede usar la notacin O( )yescribir i 1 iE O(E ) para expresar de una manera simple el orden de esta relacin, y se lee

"orden de".

Si en un mtodo esta relacin es ms fuerte tal como 2i 1 iE O(E ) entonces el error se

reducir ms rpidamente y se dice que el mtodo tiene convergencia cuadrtica o desegundo orden.


20/357

20

Definicin: Orden de convergencia de un mtodo iterativo

Sean iE , i 1E los errores en las iteraciones consecutivas i, i + 1respectivamente

Si se pueden relacionar estos errores en la forma:n

i 1 iE O(E )

Entonces se dice que el mtodo iterativo tiene convergencia de orden n.

Si un mtodo iterativo tiene convergencia mayor que lineal, entonces si el mtodo converge,

lo har ms rpidamente. .

2.1.6 Eleccin del valor inicial

Los mtodos iterativos normalmente requieren que el valor inicial sea elegido

apropiadamente. Si es elegido al azar, puede ocurrir que no se produzca la convergencia.

Si el problema es simple, mediante algn anlisis previo puede definirse una regin deconvergencia tal que si el valor inicial y los valores calculados en cada iteracin

permanecen en esta regin, el mtodo converge.

2.1.7 Preguntas

Conteste las siguientes preguntas

1.Por que el error de redondeo no debe ser mayor que el error de truncamiento?

2. Una ventaja de los mtodos iterativos es que son auto-correctivos, es decir que si seintroduce algn error aritmtico en una iteracin, en las siguientes puede ser corregido.

Cuando no ocurrira esta auto-correccin?

3.El ejemplo del mtodo numrico para calcular 7 produce una secuencia numrica. Le

parece que la convergencia es lineal o cuadrtica?


21/357

21

2.2 Mtodos directos

Son procedimientos para obtener resultados realizando una secuencia finita de operacionesaritmticas. La cantidad de clculos aritmticos depende del tamao del problema. Elresultado obtenido ser exacto siempre que se puedan conservar en forma exacta losvalores calculados en las operaciones aritmticas, caso contrario se introducirn los errores

de redondeo.

Ejemplo. Instrumentar un mtodo directo para resolver un sistema triangular inferior deecuaciones lineales.

Modelo matemticoa1,1x1 = b1a2,1x1+ a2,2x2 = b2a3,1x1+ a3,2x2+ a3,3x3 = b3. . . .an,1x1+ an,2x2+ ax,3x3+ . . . + an,nxn = bn

En donde: ai,j: coeficientes (datos)bi: constantes (datos)xi: variables (resultados)

La formulacin matemtica del mtodo se obtiene despejando sucesivamente xi de laecuacin i

x1=1,1

1

a(b1)

x2=

2,2

1

a

(b2 - a2,1x1)

x3=3,3

1

a(b3 - a3,1x1 - a3,2x2)

. . .En general:

xi=i,i

1

a(bi - ai,1x1- ai,2x2- . . . - ai,i-1xi-1), i = 2, 3, . . . , n, ai,i 0


22/357

22

Algoritmo

Algoritmo:Triangular

Entra:n: Nmerodeecuaciones

ai,j Coeficientes

bi

Constantes

Sale:xi Solucincalculada

Para i=1,2,...,n

s0

Paraj=1,2,...,i1

ss+ai,jxj

Fin

xi(bis)/ai,i

Fin

Este algoritmo es un caso particular del problema general: sistema de n ecuaciones lineales.

Los mtodos numricos normalmente se desarrollan para resolver una clase o tipo generalde problemas. La instrumentacin puede hacerse mediante un programa, pero es ms

conveniente definirlo como una funcin en PYTHON para estandarizar la entrada y salida de

variables.

Instrumentacin computacional

La instrumentacin del mtodo numrico del ejemplo anterior se har mediante una funcin

en Python. Para que la instrumentacin sea general es preferible que el mtodo numrico

sea independiente de los datos de un problema particular. El lenguaje Python usa la

numeracin de ndices comenzando en cero. Este hecho debe ser considerado por el

programador, pero en general es transparente al usuario de los mtodos numricos.

El nombre para la funcin ser triangular. La funcin recibir como datos la matriz de

coeficientes ay el vector de constantesby producir como resultado el vector solucin x

deftriangular(a,b):

n=len(b)

x=[];

foriinrange(n):

s=0

forjinrange(i):

s=s+a[i][j]*x[j]

x=x+[(b[i]s)/a[i][i]]

returnx


23/357

23

Ejemplo.Escribir las instrucciones para resolver un ejemplo usando la funcin anterior

3x1 = 27x1+ 5x2 = 38x1+ 2x2+ 9x3 = 6

>>>fromtriangularimporttriangular

>>>a=[[3,0,0],[7,5,0],[8,2,9]]

>>>b=[2,3,6]

>>>x=triangular(a,b)

>>>print(x)

[0.6666666666666666, 0.3333333333333332,0.1481481481481481]

2.2.1 Error de redondeo

Los mtodos numricos operan con datos que pueden ser inexactos y con dispositivos pararepresentar a los nmeros reales. El error de redondeo se atribuye a la imposibilidad dealmacenar todas las cifras de estos nmeros y a la imprecisin de los instrumentos demedicin con los cuales se obtienen los datos.

Definicin: Error de redondeo absoluto

Sean X: Valor exacto (normalmente desconocido)

X : Valor aproximado (observado o calculado)

E = X X Error de redondeo .

Definicin: Error de redondeo relativo

Sean X: Valor exacto (normalmente desconocido)

X : Valor aproximado (observado o calculado)E: Error de redondeo

E Ee

X X : Error de redondeo relativo. (X, X diferentes de cero)

Debido a que normalmente no es posible calcular exactamente el valor de E, se debeintentar al menos acotar su valor.

A diferencia del error de truncamiento, se dispone solamente de un resultado para estimar elerror de redondeo. Igualmente, es necesario evaluar el modelo matemtico con el valorcalculado.


24/357

24

2.2.2 Error en la representacin de los nmeros reales

Las operaciones aritmticas pueden producir resultados que no se pueden representarexactamente en los dispositivos de almacenamiento. Si estos errores se producen en formarecurrente entonces el error propagado pudiera crecer en forma significativa dependiendo

de la cantidad de operaciones requeridas. Esta cantidad de operaciones est determinadapor la eficiencia del algoritmo.

Ejemplo. Suponga que un dispositivo puede almacenar nicamente los cuatro primerosdgitos decimales de un nmero real y trunca los restantes (esto es redondeo inferior).

Se requiere almacenar el nmero:X = 536.78

Primero expresemos el nmero en forma normalizada, es decir sin enteros y ajustando sumagnitud con potencias de 10:

X = 0.53678x10

3

Ahora descomponemos el nmero en dos partesX = 0.5367x103+ 0.00008x103

El valor almacenado es un valor aproximado

X = 0.5367x103

El error de redondeo por la limitacin del dispositivo de almacenamiento esE = 0.00008x103= 0.8x103 - 4= 0.8x10-1

En general, si nes la cantidad de enteros del nmero normalizado con potencias de 10, y mes la cantidad de cifras decimales que se pueden almacenar en el dispositivo, entonces sise truncan los decimales sin ajustar la cifra anterior, el error de redondeo absoluto estacotado por:

n m| E | 1 10

Mientras que el error relativo:n m

mn

max(| E |) 1 10| e | 10 10

min(| X |) 0.1 10

(Solo depende del almacenamiento)


25/357

25

2.2.3 Error de redondeo en las operaciones aritmticas

En los mtodos directos debe considerarse el error que se propaga en las operacionesaritmticas, el cual puede ser significativo cuando la cantidad de clculos requeridos esgrande. A continuacin se analizan la suma y el producto

a) Error de redondeo en la suma

Sean X, Y : Valores exactos

X ,Y : Valores aproximados

Con la definicin de error de redondeo

EX= X - X , EY= Y - Y S = X + Y

S = ( X + EX) + (Y + EY) = ( X + Y ) + (EX+ EY)

S = X + Y Valor que se almacena

Error de redondeo absoluto en la suma

EX+Y= EX+ EY

|EX+Y| |EX| + |EY|

Error de redondeo relativo en la suma

X Y X Y X YX Y

E E E E Ee

X Y X Y X Y X Y

X YX Y

E EX Ye

X Y X X Y Y

X Y x YX Y

e e eX Y X Y

X YX Y

E E| e | | | | |

X Y X Y

X Y x YX Y

| e | | e | | e |X Y X Y

Se puede extender a la resta

EX - Y= EX- EY

|EX - Y| |EX| +|-EY|

X Y X Y X YX Y

E E E E Ee

X Y X Y X Y X Y

X YX Y

E E| e | | | | |

X Y X Y

X Y x YX Y

| e | | e | | e |X Y X Y


26/357

26

b) Error de redondeo en la multiplicacin

P = X Y

P = ( X + EX) (Y + EY) = X Y + X EY+Y EX+ EXEY

P = X Y + X EY+Y EX El ltimo trmino se descarta por ser muy pequeo

P = X Y Valor que se almacena

Error de redondeo absoluto en la multiplicacin

EXY = X EY+ Y EX

|EXY| | X EY| + |Y EX|

La magnitud del error de redondeo en la multiplicacin puede ser tan grande como la sumade los errores de redondeo de los operandos ponderada por cada uno de sus respectivosvalores.

Error de redondeo relativo en la multiplicacin

XY Y X Y X Y XXY

E XE YE XE YE E Ee

XY XY XY XY Y X

XY x Ye e e

|XY x Y| e | | e | e |

En general, si los valores de los operandos tienen ambos el mismo signo y son valoresmayores que 1, se puede concluir que la operacin aritmtica de multiplicacin puedepropagar ms error de redondeo que la suma.

Adicionalmente, si el resultado de cada operacin aritmtica debe almacenarse, hay queagregar el error de redondeo debido a la limitacin del dispositivo de almacenamiento.


27/357

27

2.2.4 Propagacin del error de redondeo en las operaciones aritmticas

Ejemplos de aplicacin

1) Error de redondeo en mediciones

La velocidad de una partcula es constante e igual a 4 m/s, medida con un error de 0.1 m/sdurante un tiempo de recorrido de 5 seg. medido con error de 0.1 seg. Determine el errorabsoluto y el error relativo en el valor de la distancia recorrida.

v = 4, Ev= 0.1 (velocidad)t = 5, Et= 0.1 (tiempo)d = vt (distancia recorrida)

Ed= v Et+ t Ev= 4(0.1) + 5(0.1) = 0.9 (Error absoluto)

d = vt = 20 con un rango de variacin: 19.1 d 20.9

tvd

EE 0.1 0.1e 0.045 4.5%

4 5v t

(Error relativo)

2) Resta de nmeros con valores muy cercanos

Suponer que se deben restar dos nmeros muy cercanos X=578.1, Y=577.8 con error deredondeo en el segundo decimal: EX= EY= 0.05 aproximadamente. Ambos errores puedenser del mismo signo o de diferente signo, depende de la forma como se obtuvieron los datos

X YX Y

E Ee 0.000086 0.0086% , e 0.000086 0.0086%

X Y (Errores relativos)

Cota para el error de redondeo relativo:

X Y X Y X YX Y

E E E E Ee

X Y X Y X Y X Y

X YX Y

E E| e | | | | |

X Y X Y

X Y0.05 0.05

| e | | | | | 0.3333 33.33%578.1 577.8 578.1 577.8

El aumento en la cota del error en el resultado es muy significativo con respecto a losoperandos. Se concluye que se debe evitar restar nmeros cuya magnitud sea muycercana pues el cociente al ser muy pequeo, har que el error relativo sea significativo.

Adicionalmente habra que agregar el efecto del error de redondeo al almacenar elresultado.


28/357

28

3) Suma de nmeros de diferente magnitud

Es suficiente considerar tres nmeros: X, Y, Z. Suponer por simplicidad que los datos sonvalores positivos exactos, por lo tanto eX = 0, eY = 0, ez = 0

S = X + Y + Z, con X > Y > Z

Suponer que la suma se realiza en el orden usual:

S = (X + Y) + Z

X Y X Y 1X Y

e e e r X Y X Y

= r1 r1: error de redondeo al almacenar la suma

1 2(X Y) Z X Y Z 2 1 2

(X Y)r (X Y Z)r X Y Z X Ye e e r r r

X Y Z X Y Z X Y Z X Y Z

r2: error de redondeo al almacenar la suma

Si cada resultado se almacena en un dispositivo que tiene m cifras, su cota de error deredondeo:

m1 2| r ,r | 10 10

m

(X Y) Z(2X 2Y Z)10 10

| e |X Y Z

Si la suma se hiciera en orden opuesto, se obtendra

m

(Z Y) X(2Z 2Y X)10 10

| e |Z Y X

Si X > Z , se puede concluir que la suma de los nmeros debe realizarse comenzando conlos nmeros de menor magnitud, pues la cota del error ser menor.


29/357

29

2.2.5 Eficiencia de los mtodos directos

La eficiencia de un algoritmo y su programacin est relacionada con el tiempo necesariopara obtener la solucin. Este tiempo depende de la cantidad de operaciones que se debenrealizar. As, si se tienen dos algoritmos para resolver un mismo problema, es ms eficiente

el que requiere menos operaciones para producir el mismo resultado.

Sea n el tamao del problema, y T(n) una funcin que mide la eficiencia del algoritmo(cantidad de operaciones requeridas). Para obtener T(n)se pueden realizar pruebas en elcomputador con diferentes valores de nregistrando el tiempo real de ejecucin. Este tiempoes proporcional a la cantidad de operaciones que se realizaron, por lo tanto se puede usarpara estimar la funcin T(n).

Esta forma experimental para determinar T(n) tiene el inconveniente de usar lainstrumentacin computacional del algoritmo para realizar las pruebas. Es preferible conocerla eficiencia del algoritmo antes de invertir el esfuerzo de la programacin computacional

para preveer que sea un algoritmo aceptable.

Para determinar la eficiencia de un algoritmo antes de su instrumentacin se puede analizarla estructura del algoritmo o realizar un recorrido del mismo en forma abstracta.

Ejemplo. El siguiente algoritmo calcula la suma de los primeros n nmeros naturales.Encontrar T(n)

Sea T la cantidad de sumas que se realizan...

s=0

for

i

in

range(n):

s=s+i

La suma est dentro de una repeticin que se realiza n veces, por lo tanto,

T(n) = n

Ejemplo.El siguiente algoritmo suma los elementos de una matriz cuadrada a de orden n.Encontrar T(n)

Sea T la cantidad de sumas...

s=0

for

i

in

range(n):

forjinrange(n):

s=s+a[i][j]

La suma est incluida en una repeticin doble. La variable i, cambia n veces y para cadauno de sus valores, la variablej cambia n veces. Por lo tanto.

T(n) = n2


30/357

30

Ejemplo. El siguiente algoritmo es una modificacin del anterior. Suponga que se deseasumar nicamente los elementos de la sub-matriz triangular superior. Obtener T(n)

...

s=0

foriinrange(n):

for

j

in

range(i,n):

s=s+a[i][j]

Si no es evidente la forma de T(n), se puede recorrer el algoritmo y anotar la cantidad desumas que se realizan

Valor Cantidad de ciclosi j0 n1 n-12 n-2

... ...n-1 1

Entonces, T(n) = 1 + 2 + ... + n =2n n n

(n 1)2 2 2

(suma de una serie aritmtica)

Otra manera de obtener la funcin T(n) consiste en programar el conteo de los ciclos de unalgoritmo para obtener puntos de su eficiencia.

Ejemplo. Programa para conteo de ciclos para el ejemplo anterior

n=int(input('Ingresen:'))

c=0foriinrange(n):

forjinrange(i,n):

c=c+1

print(c)

Debido a que son dos ciclos, T(n) debe ser un polinomio algebraico de segundo grado.Para obtener este polinomio son suficientes tres puntos (n, c):

Se realizaron tres pruebas del programa de conteo y se obtuvieron los resultados :>>>

Ingresen:410

>>>

Ingresen:5

15

>>>

Ingresen:6

21


31/357

31

Con estos resultados se puede construir el polinomio de interpolacin que representa aT(n).Este polinomio se lo puede obtener manualmente o con un mtodo computacional.

El resultado que se obtiene es:

T(n) = t2

/2

+

t/2

Resultado que coincide con el obtenido anteriormente con un conteo directo manual

Para registrar el tiempo real de ejecucin de un proceso (programa o funcin) se puede usarla funcin clock()de la librera time:

>>>fromtimeimport*

>>>t1=clock();...proceso...;t2=clock();print(t2t1)

2.2.6 La notacin O( )

Supongamos que para resolver un problema se han diseado dos algoritmos: A y B, coneficiencias TA(n) = 10n+2, TB(n) = 2n2 + 3, respectivamente. Cual algoritmo es mseficiente?.

Para valores pequeos de n, TB(n) < TA(n), pero para valores grandes de n, TB(n) > TA(n).Es de inters prctico determinar la eficiencia de los algoritmos para valores grandes de n,por lo tanto el algoritmo Aes ms eficiente que el algoritmo Bcomo se puede observar en elsiguiente grfico:

Si T(n) incluye trminos de n que tienen diferente orden, es suficiente considerar el trminode mayor orden pues es el que determina la eficiencia del algoritmo cuando n es grande.Para compararlos, no es necesario incluir los coeficientes y las constantes.


32/357

32

n [log(n)] n [n log(n)] n2 n3 2n n!

1 0 1 0 1 1 2 13 1 3 3 9 27 8 6

5 1 5 8 25 125 32 1207 1 7 13 49 343 128 50409 2 9 19 81 729 512 3.62x105

11 2 11 26 121 1331 2048 3.99x107

13 2 13 33 169 2197 8192 6.22x109

15 2 15 40 225 3375 32768 1.30x1012

17 2 17 48 289 4913 1.31x105 3.55x1014

19 2 19 55 361 6859 5.24x105 1.21x1017

21 3 21 63 441 9261 2.09x106 5.10x1019

23 3 23 72 529 12167 8.38x106 2.58x1022

25 3 25 80 625 15625 3.35x107 1.55x102550 3 50 195 2500 125000 1.12x1015 3.04x1064

100 4 100 460 10000 1000000 1.26x1030 9.33x10157

Ejemplo.Suponga T(n) = n2+ n + 10. Evaluar T para algunos valores de n

T(2) = 4 + 2 + 10

T(5) = 25 + 5 + 10

T(20) = 400 + 20 + 10

T(100) = 10000 + 100 + 10

Se observa que a medida que ncrece, T depende principalmente del trmino dominante n2.

Este hecho se puede expresar usando la notacin O( ) la cual indica el orden de la

eficiencia del algoritmo, y se puede escribir: T(n) =O(n2) lo cual significa que la eficiencia

es proporcional a n2, y se dice que el algoritmo tiene eficiencia de segundo orden.

En general, dado un problema de tamao n, la medida de la eficiencia T(n)de un algoritmo

se puede expresar con la notacin O(g(n))siendo g(n)alguna expresin tal como: n, n2, n3,

..., log(n), n log(n), ..., 2n, n!,...etc, la cual expresa el orden de la cantidad de operaciones

que requiere el algoritmo.

Es de inters medir la eficiencia de los algoritmos antes de su instrumentacin

computacional. En el siguiente cuadro se ha tabulado T(n) con algunos valores de n y para

algunas funciones tpicas g(n).

Tabulacin de T(n) con algunos valores de n para algunas funciones tpicas g(n)

Los algoritmos en las dos ltimas columnas son de tipo exponencial y factorial

respectivamente. Se puede observar que an con valores relativamente pequeos de nel

valor T(n) es extremadamente alto. Los algoritmos con este tipo de eficiencia se denominan

no factibles pues ningn computador actual pudiera calcular la solucin en un tiempo

aceptable para valores de n grandes. La mayora de los algoritmos que corresponden a los

mtodos numricos son de tipo polinomial con g(n) = n, n2, n3


33/357

33

2.2.7 Ejercicios

1.Encuentre la cota del error relativo en la siguiente operacin aritmtica:T = X(Y Z)

El error de redondeo relativo de los operandos es respectivamente eX, eY, ez, y el error

de redondeo relativo en el dispositivo de almacenamiento es rm

a) Primero se realiza la multiplicacin y luego la restab) Primero se realiza la resta y luego la multiplicacin

2. Suponga que tiene tres algoritmos: A, B, C con eficiencia respectivamente:TA(n) = 5n + 50TB(n) = 10n ln(n) + 5TC(n) = 3n2+ 1

a) Determine na partir del cual A es ms eficiente que B

b) Determine na partir del cual B es ms eficiente que Cc) Coloque los algoritmos ordenados segn el criterio de eficiencia establecido

3.Exprese la eficiencia de los algoritmos A, B, C con la notacin O( )

4.Los computadores actuales pueden realizar 100 millones de operaciones aritmticas enun segundo. Calcule cuanto tiempo tardara este computador para resolver un problema detamao n=50si el algoritmo es de tipo:

a) Polinomial de tercer gradob) Exponencialc) Factorial

5.Determine la funcin de eficiencia T(n) del algoritmo triangularincluido en el captulo 1 yexprsela con la notacin O( ).Suponga que es de inters conocer la cantidad total de ciclosque se realizan.

6.Dado el siguiente algoritmoLeern

Mientrasn>0repita

dmod(n,2) Produce el residuo entero de la divisin n/2

nfix(n/2) Asigna el cociente entero de la divisin n/2Mostrard

fin

a) Recorra el algoritmo con n = 73b) Suponga que T(n) representa la cantidad de operaciones aritmticas de divisin que serealizan para resolver el problema de tamao n. Encuentre T(n)y exprsela con la notacinO( ) Para obtener T(n) observe el hecho de que en cada ciclo el valor de n se reduceaproximadamente a la mitad.


34/357

34

3 RACES REALES DE ECUACIONES NO-LINEALES

Seaf: RR. Dada la ecuacin f(x) = 0, se debe encontrar un valor real r tal quef(r) =0.Entonces res una raz real de la ecuacin

Si no es posible obtener la raz directamente, entonces se debe recurrir a los mtodosnumricos iterativos para calcular ren forma aproximada con alguna precisin controlada.Se han creado muchos mtodos numricos para resolver este problema clsico, pero con eluso de computadoras para el clculo, conviene revisar solamente algunos de estos mtodosque tengan caractersticas significativamente diferentes.

3.1 Mtodo de la biseccin

Seaf: RR.Suponer quef es continua en[a, b], y queadems f(a) y f(b) tienen signosdiferentes.

3.1.1 Existencia de la raz real

Si una funcin f es continua en un intervalo [a, b] y f(a) tiene signo diferente que f(b),entonces existe por lo menos un punto ren (a, b)tal que f(r)=0.Si adems f'(x)no cambiade signo en el intervalo [a, b], entonces la solucin es nica.

La validez de esta proposicin se basa en el Teorema del Valor Intermedio.

El mtodo de la biseccin es un mtodo simple y convergente para calcular r. Consiste encalcular el punto medio c=(a+b)/2del intervalo [a, b] y sustituirlo por el intervalo [a, c] [c,b] dependiendo de cual contiene a la raz r. Este procedimiento se repite hasta que ladistancia entre ay b sea muy pequea, entonces el ltimo valor calculado c estar muy

cerca de r.

Interpretacin grfica del mtodo de la biseccin

En la figura se puede observar que luego de haber calculado c, para la siguiente iteracindebe sustituirse el intervalo [a, b]por [c, b]debido a que f(a)y f(c)tienen igual signo y porlo tanto la raz estar en el intervalo [c, b]


35/357

35

3.1.2 Convergencia del mtodo de la biseccin

Sean ai, bi, ci los valores de a, b, cen cada iteracin i=1, 2, 3, . . . respectivamente

El mtodo de la biseccin genera a partir de un intervalo inicial [a, b] una sucesin de

intervalos[a1, b1], [a2, b2], , [ai, bi], en donde se ha sustituido ai o bi por ci tales quea a1 a2 a i constituyen una sucesin creciente y b b1 b2, biuna sucesindecreciente conai < bi. Ademspor definicin del mtodo: ci, r [ai, bi] en cada iteracin i

Sean di= bi ai longitud del intervalo [ai, bi] en la iteracin i=1, 2, 3, . . .d = b a longitud del intervalo inicial

Recorrido de las iteraciones

Iteracin Longitud del intervalo1 d1= d /22 d2= d1/2 = d/22

3 d3= d2/2 = d/23

. . . . . .i di= d/2i

Entonces

i i i i ii

i i ii

d0 d 0 a b c r | c r | E

2

i>0 para cualquier ER+

Suponer que se desea que el ltimo valor calculado citenga error E = 0.001, entonces si elalgoritmo termina cuando bi ai < E, se cumplir que |ci r| < E y ci ser unaaproximacin para rcon un error menor que 0.0001

Se puede predecir el nmero de iteraciones que se deben realizar con el mtodo de laBiseccin para obtener la respuesta con error permitido E:

En la iteracin i: di= d/2iSe desea terminar cuando: di< E

Entonces se debe cumplir d/2i< E

De donde se obtiene:log(d/E)

ilog(2)


36/357

36

Ejemplo. La ecuacin f(x) = x ex- = 0 tiene una raz real en el intervalo [0, 2]. Determinecuantas iteraciones deben realizarse con el mtodo de la biseccin para obtener unresultado con error E=0.0001. Por simple inspeccin f(0) < 0, f(2) > 0 y fes contnua en[0, 2]

El nmero de iteraciones que debern realizarse es:

i > log(2/0.0001)/log(2) i >14.287 15 iteraciones

3.1.3 Algoritmo del mtodo de la biseccin

Calcular una raz rreal de la ecuacin f(x) = 0 con errorE.fes contnua en un intervalo [a, b]tal que f(a) y f(b)tienen signos diferentes

Algoritmo:Biseccin

Restriccin:Novalidaelintervaloinicial

Entra: f,a,b,ESale: c (aproximacinalarazr,conerrorE)

Mientrasba>E

c(a+b)/2

Sif(c)=0

Terminar

Sino

Sisignof(c)=signof(a)

ac

Sino

bc

Fin

Fin

Fin

El ltimo valor calculado c estar a no ms de una distancia E de la raz r.

Ejemplo. Calcule una raz real de f(x) = x ex- = 0 en el intervalo [0, 2] con error 0.01

Solucin

La funcin f es continua y adems por simple inspeccin: f(0)0, por lo tanto la

ecuacin f(x) = 0 debe contener alguna raz real en el intervalo [0, 2]

Cantidad de iteraciones

log(d/E) log(2/ 0.01)i 7.6439 8 iteraciones

log(2) log(2)


37/357

37

Tabulacin de los clculos para obtener la raz con el mtodo de la Biseccin

iteracin a b c sign(f(a)) sign(f(c))inicio 0 2 1 - -

1 1 2 1.5 - +

2 1 1.5 1.25 - +3 1 1.25 1.125 - +4 1 1.125 1.0625 - -5 1.0625 1.125 1.0938 - +6 1.0625 1.0938 1.0781 - +7 1.0625 1.0781 1.0703 - -8 1.0703 1.0781 1.0742

En la octava iteracin:

b a = 1.0781-1.0703 = 0.0078 |r c|


38/357

38

3.1.5 Instrumentacin computacional del mtodo de la Biseccin

Calcular una raz rreal de la ecuacin f(x) = 0.fes contnua en un intervalo [a, b] tal que

f(a) y f(b)tienen signos diferentes

Para instrumentar el algoritmo de este mtodo se escribir una funcin en Python. Elnombre ser biseccin. Recibir como parmetros f, a, b, y entregar c como

aproximacin a la raz r.

Criterio para salir: Terminar cuando la longitud del intervalo sea menor que un valor

pequeo e especificado como otro parmetro para la funcin. Entonces el ltimo valor c

estar aproximadamente a una distancia e de la raz r.

defbiseccion(f,a,b,e):

whileba>=e:

c=(a+b)/2

if

f(c)==0:

returnc

else:

iff(a)*f(c)>0:

a=c

else:

b=c

returnc

Ejemplo. Desde la ventana interactiva de Python use la funcinbiseccinpara calcular una

raz real de la ecuacin f(x) =xex

-

=0. Suponer que se desea que el error sea menorque 0.000001.

Por simple inspeccin se puede observar que f es continua y adems f(0) < 0, f(2) > 0. Por

lo tanto se elije como intervalo inicial: [0, 2]. Tambin se puede previamente graficar f.

En la ventana interactiva de Python:

>>>frommathimport*

>>>frombiseccionimportbiseccion

>>>deff(x):returnx*exp(x)pi

>>>c=biseccion(f,0,2,0.000001)

Resultado con E=0.000001

>>>c

1.0736589431762695

>>>f(c)

4.540916178063729e06 Verificar en la ecuacin


39/357

39

Ejemplo. Encontrar las intersecciones en el primer cuadrante de los grficos de lasfunciones:f(x) = 4 + cos(x+1), g(x)=exsen(x).

Graficar las funciones para visualizar las intersecciones:

>>>

from

pylab

import*

>>>x=arange(0,3.5,0.1)

>>>f=4+x*cos(x+1)

>>>g=exp(x)*sin(x)

>>>plot(x,f,'b')

>>>plot(x,g,'r')

>>>grid(True)

>>>show()

Las intersecciones son las races de la ecuacin h(x) = g(x)-f(x) = 0

El clculo de las races se realiza con el mtodo de la Biseccin con E= 0.000001

>>>frombiseccionimport*

>>>frommathimport*

>>>defh(x):returnexp(x)*sin(x)4x*cos(x+1)

>>>r=biseccion(h,1,1.5,0.000001)

>>>

r

1.233719825744629

>>>r=biseccion(h,3,3.2,0.000001)

>>>r

3.0406669616699213


40/357

40

3.2 Mtodo del punto fijo

Sea f: RR. Dada la ecuacin f(x) = 0, encuentre r tal quef(r) = 0

El mtodo del punto fijo, tambin conocido como mtodo de la Iteracin funcional es elfundamento matemtico para construir mtodos eficientes para el clculo de races reales

de ecuaciones no lineales.

Este mtodo consiste en re-escribir la ecuacin f(x) = 0 en la forma x = g(x). Esta nuevaecuacin debe ser equivalente a la ecuacin original en el sentido que debe satisfacerse conla misma raz, es decir la existencia de un punto fijo rde la ecuacin x = g(x)es equivalentea encontrar una raz realrde la ecuacin f(x) = 0: r = g(r) f(r)=0 como muestra elgrfico:

3.2.1 Existencia del punto fijo

Sea guna funcin continua en un intervalo [a, b] tal que g(a) > a y g(b) < b.Entonces la ecuacin x = g(x)tiene al menos un punto fijo en [a, b]

Demostracin

Sea h(x) = g(x) - x una funcin, tambin continua, en el intervalo [a, b]Entonces:

h(a) = g(a) - a > 0h(b) = g(b) - b < 0

Por la continuidad de hexiste algn valor r en el intervalo [a, b], tal que h(r) = 0. Entoncesg(r) - r = 0. Por lo tanto res un punto fijo de x=g(x) y r es una raz real de f(x) = 0

0 0.5 1 1.5 2-1

-0.5

0

0.5

1

1.5

2

x

sin(x)-exp(x)+2

f(x)

Raiz r

0 0.5 1 1.5 2-1

-0.5

0

0.5

1

1.5

2log(sin(x)+2)

x

g(x)

Punto fijo r


41/357

41

3.2.2 Convergencia del mtodo del punto fijo

Sea guna funcin continua en un intervalo [a, b] tal que g(a) > a y g(b) < b y sea r un

punto fijo en [a, b]. Si x(a,b)(|g(x)|


42/357

42

Se puede extender al caso en el cual g tiene pendiente negativa y deducir la condicinnecesaria de convergencia del mtodo del punto fijo: |g(x)| < 1.

3.2.3 Unicidad del punto fijo

Sea run punto fijo de x = g(x). Si g(x)existe en el intervalo [a, b]y x[a,b](|g(x)|


43/357

43

Ejemplo. Calcule una raz real de f(x) = ex- x = 0 con el mtodo del punto fijo.

Un grfico de fnos muestra que la ecuacin tiene dos races reales en el intervalo [0, 2]

Re-escribir la ecuacin en la forma x = g(x).

Tomando directamente de la ecuacin (puede haber varias opciones)

a) x = g(x) = ex/

b) x = g(x) = ln(x)

c) x = g(x) = ex x + x, etc

Usaremos la primera

Escribir la frmula iterativa:

xi+1 = g(xi) = ixe /, i = 0, 1, 2, 3, . . .

Elegir un valor inicial x0= 0.6 (cercano a la primera raz, tomado del grfico)

Calcular los siguientes valores

x1= g(x0) = 0xe / = 0.6e / = 0.5800

x2= g(x1) = 1xe / = 0.5800e / = 0.5685

x3= g(x2) =0.5685e / = 0.5620

x4= g(x3) =0.5620e / = 0.5584

x5= g(x4) =0.5584e / = 0.5564

x6 = g(x5) =0.5564e / = 0.5552

. . .La diferencia entre cada par de valores consecutivos se reduce en cada iteracin. En los

ltimos la diferencia est en el orden de los milsimos, por lo tanto podemos considerar que

el mtodo converge y el error est en el orden de los milsimos.


44/357

44

Para calcular la segunda raz, usamos la misma frmula iterativa:

xi+1 = g(xi) = ixe /, i = 0, 1, 2, 3, . . .

El valor inicial elegido es x0= 1.7 (cercano a la segunda raz, tomado del grfico)

Calcular los siguientes valoresx1= g(x0) = 0xe / = 1.7e / = 1.7424

x2= g(x1) = 1xe / = 1.7424e / = 1.8179

x3= g(x2) = 1.8179e / = 1.9604

x4= g(x3) = 1.9604e / = 2.2608

x5= g(x4) = 2.2608e / = 3.0528

x6 = g(x5) = 3.0528e / = 6.7399

x6 = g(x5) = 6.7399e / = 269.1367

. . .La diferencia entre cada par de valores consecutivos aumenta en cada iteracin. Seconcluye que el mtodo no converge.

En el ejemplo anterior, las races reales de la ecuacin f(x)=0son las intersecciones de fcon el eje horizontal. En el problema equivalente x=g(x), las races reales son lasintersecciones entre g y la recta x:

En el clculo de la primera raz, la pendiente de g es menor que la pendiente de x y seobserva que la secuencia de valores generados tiende a la raz. La interpretacin grfica del

proceso de clculo se describe en la siguiente figura.


45/357

45

Para la segunda raz, la pendiente de g es mayor que la pendiente de x y se puedeconstatar que la secuencia de valores generados se aleja de la raz.

Ejemplo. Encuentre el intervalo de convergencia para para calcular las races de la

ecuacin anterior: f(x) = ex-

x = 0 con el mtodo del punto fijo.

Ecuacin equivalente:

x = g(x) = ex/

Condicin de convergencia: |g(x)| < 1

g(x) = ex/ |ex/| < 1 x < ln()

Intervalo de convergencia: ( , ln( ))

Con lo que se concluye que la segunda raz no se puede calcular con esta frmula.

Ejemplo. Calcule una raz real de la misma ecuacin f(x) = ex- x = 0 con el mtodo delpunto fijo con otra forma de la ecuacin de recurrencia x=g(x).

Para este ejemplo se decide usar la segunda forma: x = g(x)=ln(x)

0.5 0.52 0.54 0.56 0.58 0.6 0.620.5

0.51

0.52

0.53

0.54

0.55

0.56

0.57

0.58

0.59

0.6

x

x

g(x)

x

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

x

x

x

g(x)

Segn la condicin deconvergencia establecida, elgrfico muestra que ser imposiblecalcular la primera raz. Lasegunda raz si podr sercalculada, lo cual se puedeverificar numricamente.


46/357

46

Ejemplo. Calcular con Python la segunda raz de la ecuacin: f(x)=exp(x)-x mediante la

frmula de recurrencia: x=g(x)=ln(x)

>>>frommathimport*

>>>defg(x):returnlog(pi*x)

>>>x=1.6 Valor inicial para la segunda raz>>>x=g(x)

>>>print(x)

1.6147335150951356

>>>x=g(x)

>>>print(x)

1.6238998227759673

>>>x=g(x)

>>>print(x)

1.62956044020348

...

...

>>>x=g(x)

>>>print(x)

1.6385043042098606

>>>x=g(x)

>>>print(x)

1.6385137019235614 Valor luego de 15 iteraciones

3.2.5 Eficiencia del mtodo del punto fijo

El mtodo del punto fijo tiene convergencia lineal o de primer orden debido a que Eiy Ei+1

estn relacionados directamente mediante el factor de convergencia: i 1 iE g'(z) E , por lotanto este mtodo tiene convergencia lineal: i 1 iE O(E ) y g'(z) es el factor de

convergencia. Si la magnitud de g'(z) permanece mayor a 1, el mtodo no converge.


47/357

47

3.3 Mtodo de Newton

Sean f: RR, y la ecuacin f(x) = 0. Sea r tal quef(r) = 0,entonces r es una raz real dela ecuacin.

El mtodo de Newton es una frmula iterativa eficiente para encontrar r. Es un caso

especial del mtodo del punto fijo en el que la ecuacin f(x) = 0se re-escribe en la forma x =g(x) eligiendo gde tal manera que la convergencia sea de segundo orden.

3.3.1 La frmula de Newton

Suponer que ges una funcin diferenciable en una regin que incluye a la raz ry al valor xi(calculado en la iteracin i). Desarrollando con la serie de Taylor:

g(xi) = g(r) + (xi- r) g(r) + (xi- r)2g(r)/2! + . . .

Con las definiciones del mtodo del punto fijo:

r = g(r)xi+1= g(xi), i = 0, 1, 2, 3, . . .

Se obtiene:xi+1= r + (xi- r) g(r) + (xi- r)2g(r)/2! + . . .

Si se define el error de truncamiento de la siguiente forma:

iE = xi- r: Error en la iteracin i

i 1E

= xi+1- r: Error en la iteracin i + 1

Finalmente se obtiene:

i 1E

= iE g(r) +2iE g(r)/2! + . . .

Si se hace que g(r) = 0, y si g(r) 0, entonces se tendr:

i 1E

= O( 2iE ),

Con lo que el mtodo tendr convergencia cuadrtica.

El procedimiento para hacer que g(r) = 0, consiste en elegir una forma apropiada para g(x):

Sea g(x) = x - f(x) h(x), en donde h es alguna funcin que deber especificarse

Es necesario verificar que la ecuacin x = g(x)se satisface con la raz r de f(x) = 0

Si f(r) = 0, yh(r) 0: g(r) = r - f(r) h(r) = r g(r) = r


48/357

48

Derivar g(x)y evaluar en r

g(x) = 1 - f(x) h(x) - f(x) h(x)g(r) = 1 - f(r) h(r) - f(r) h(r) = 1 - f(r) h(r)

Para que la convergencia sea cuadrtica se necesita que g(r) = 0

g(r) = 0 0 = 1 - f(r) h(r) h(r) = 1/f(r) h(x) = 1/f(x), f'(x)0

Con lo que h(x)queda especificada para que la convergencia sea cuadrtica.

Al sustituir en la frmula propuesta se obtiene x = g(x) = x - f(x)/f(x), y se puede escribir lafrmula iterativa de Newton:

Definicin: Frmula iterativa de Newton

ii 1 i i

i

f (x )x x , f '(x ) 0

f '(x )

, i = 0, 1, 2, . . .

3.3.2 Algoritmo del mtodo de Newton

Para calcular una raz rreal de la ecuacin f(x) = 0 con errorEse usa la frmula iterativa .

ii 1 i i

i

f(x )x x , f '(x ) 0

f '(x )

. Comenzando con un valor inicial x0 se genera una sucesin de

valores xi , i = 0, 1, 2, 3, ... esperando que converja a un valor que satisfaga la ecuacin.

Algoritmo:Newton

Restriccin:Nodetectadivergencia

Entra: f Ecuacinaresolver

x Valorinicial

E Errorqueseesperaenlarespuesta

Sale: r AproximacinalarazconerrorE

rxf(x)/f(x)

Mientras|rx|>E

xr

rxf(x)/f(x)

Fin

Mostrar(r)


49/357


50/357

50

A diferencia del mtodo del Punto Fijo, la frmula de Newton converge a ambas races. Paraentender este importante comportamiento, una interpretacin grfica de la frmula nosmuestra la transformacin geomtrica que permite la convergencia en ambas races:

Grfico de la frmula de Newton interpretada como frmula del Punto Fijo para el ejemploanterior:

i

i

xi i

i 1 i i i xi

f(x ) e xx g(x ) x x

f '(x ) e

Grfico de x y g(x) con la frmula de Newton para el ejemplo anterior

Se observa que en la vecindad de cada raz, |g(x)|


51/357

51

3.3.3 Interpretacin grfica del mtodo de Newton

Sea f(x) = 0 la ecuacin que se desea resolver. La siguiente interpretacin grfica es tilpara comprender el proceso de clculo con la frmula de Newton.

Suponer que f(x) tiene el siguiente grfico:

Se elige un valor aproximado inicial para la raz r, y se lo designa x0

Se traza una tangente a f(x)en el punto f(x0). El punto de interseccin con el eje horizontalestar ms cerca de r, y se lo designa x1, mientras que el ngulo de interseccin se lodesigna como como se muestra en el grafico:

El valor dex1se lo puede encontrar con la siguiente definicin:

0 00 0 1 0

0 1 0

f(x ) f(x )tan( ) f '(x ) x x

x x f '(x )

El procedimiento anterior se puede repetir. Se traza una tangente a f(x)en el punto f(x1). Elpunto de interseccin con el eje horizontal estar ms cerca de r, y se lo designa x2,mientras que el ngulo de interseccin ser como se muestra en el siguiente grfico


52/357

52

El valor de x2se lo puede encontrar con la siguiente definicin:

1 11 1 2 1

1 2 1

f(x ) f(x )tan( ) f '(x ) x x

x x f '(x )

Si el procedimiento anterior se lo aplica repetdamente, se puede generalizar y escribir la

frmula iterativa:i i

i i i 1 ii i 1 i

f(x ) f(x )tan( ) f '(x ) x x

x x f '(x )

Es la frmula iterativa de Newton-Raphson:

ii 1 i

i

f(x )x x , i 0,1,2,...

f '(x )

La interpretacin grfica permite observar que la secuencia de valores calculados con lafrmula de Newton sigue la trayectoria de las tangentesaf(x) en los puntos x0, x1, x2, ...Sihay convergencia, esta secuencia tiende a la raz r. En la siguiente seccin se analiza lapropiedad de convergencia de ste mtodo.

3.3.4 Convergencia del mtodo de Newton

Se estableci en el mtodo del punto fijo que la ecuacin recurrente x=g(x)tiene la siguientepropiedad de convergencia: i 1 i| E | | g'(z) || E | , i = 0, 1, 2, 3, . . . La convergencia se

produce si se cumple que |g(x)|


53/357

53

3.3.5 Una condicin de convergencia local para el mtodo de Newton

Obtener un intervalo de convergencia de la definicin |g(x)| < 1para el mtodo de Newton

con:2

f(x)f''(x)g'(x)

[f'(x)] normalmente es un problema complicado. En esta seccin se

describe un procedimiento simple para obtener un intervalo de convergencia para algunoscasos de f(x).

Dada la ecuacin f(x)=0. Suponer que f(x), f(x), f(x) son continuas y limitadas en unintervalo [a, b]que contiene a la raz rcomo se muestra en el siguiente grfico:

Para este caso, f(x) tiene las siguientes propiedades

a) f(x) > 0, x(r, b]b) f(x) > 0, x(r, b]

c) f(x) > 0, x(r, b]

Partiendo de estas premisas se demuestra que la frmula de Newton converge paracualquier valor inicial x0 elegido en el intervalo (r, b].

Demostracin

1) Las premisas a) y b) implican que i 1 ix x :

En la frmula de Newton

ii 1 i

i

f(x )x x

f '(x ) i 1 ix x (1)

El enunciado es vlido pues f(x), f'(x) son positivos y se suma un trmino positivo a laderecha

2) La premisa c) implica que i 1r x

:

Desarrollamos f(x)con tres trminos de la serie de Taylor alrededor de ix 2i i i if(r) f(x ) (r x )f '(x ) (r x ) f ''(z) / 2!

i i if(r) f(x ) (r x )f '(x ) i i i0 f(x ) (r x )f '(x ) i i ir x f(x ) / f '(x ) i 1r x

(2)

El enunciado es vlido pues siendo f''(x)positivo, se resta un trmino positivo a la derecha


54/357

54

Combinando los resultados (1) y(2)se tiene

i 1 ir x x , i = 0, 1, 2,...

Este resultado define una sucesin numrica decreciente que tiende a r y prueba la

convergencia de la frmula iterativa de Newton: ii x r

Si se dispone del grfico de fes fcil reconocer visualmente si se cumplen las condicionesa), b) yc) como el caso anterior y se puede definir un intervalo para la convergencia delmtodo.

Si f tiene otra forma, igualmente se pueden enunciar y demostrar las condiciones para quese produzca la convergencia en cada caso.

Ejemplo. Determine la convergencia del mtodo de Newton si f tuviese la siguiente forma

Su geometra se puede describir con:a) f(x)>0, x[a, r)

b) f(x)0, x

[a, r)

Con un desarrollo similar al anterior, se puede probar que el mtodo converge paracualquier valor inicial x0elegido en el intervalo [a, r), (a la izquierda de la raz r).

El uso de esta propiedad es simple si se dispone de un grfico de la ecuacin. Se eligecomo intervalo de convergencia aquella regin en la que se observa que la trayectoria de lastangentes produce la convergencia a la raz. Si se elije un valor inicial arbitrario no se puedeasegurar que el mtodo converge.


55/357

55

Ejemplo.Una partcula se mueve en el espacio con el vector de posicin R(t) = (2cos(t),sen(t), 0). Se requiere conocer el tiempo en el que el objeto se encuentra ms cerca delpunto P(2, 1, 0). Utilice el mtodo de Newton con cuatro decimales de precisin.

Solucin

Distancia entre dos puntos:

dt 2cost 2 sent 10 0Modelo matemtico: f(t) = d(t) = 0

ft dt 2cost sent 14sent2cost 222cost 2 sent 1 0ft cost sent 1 4sent cost 1 0

3sent cost 4sent cost 0

ft 4 cost sent 3cost 3sent

Grfico de f(t)

Frmula de Newton

ii 1 i

i

f(t )t t , i 0,1,2,...

f '(t )

Sustitur las frmulas anteriores en la frmula de Newton y calcular:

t0= 0.5 Estimacin tomada del grfico

t1= 0.5 938t2= 0.5873t3= 0.5 872t4= 0.5 872

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

-1

0

1

2

3

4

5

t


56/357


57/357

57

3.3.6 Prctica computacional

En esta seccin se describe el uso de Python para usar el mtodo de Newton. Se lo hardirectamente en la ventana interactiva.

Para calcular una raz debe elegirse un valor inicial cercano a la respuesta esperada deacuerdo a la propiedad de convergencia estudiada para este mtodo.

Para realizar los clculos se usa la frmula de Newton en notacin algortmica:

ii 1 i

i

f(x )x x

f '(x ) , i = 0, 1, 2, 3,

x0 es el valor inicialx1, x2, x3, son los valores calculados

En los lenguajes computacionales como Python no se requieren ndices para indicar que elvalor de una variable a la izquierda es el resultado de la evaluacin de una expresin a la

derecha con un valor anterior de la misma variable.

La ecuacin se puede definir como una expresin matemtica usando con la librera SympyLa variable independiente se declara con Symbol. La derivada se obtiene con la funcin diffy con la funcin floatse evalan las expresiones matemticas.

Uso computacional de la frmula de Newton en Python:

>>>fromsympyimport*

>>>x=Symbol('x')

>>>f=

>>>df=diff(f,x)>>>r=rfloat(f.subs(x,r))/float(df.subs(x,r))

En donde r es una estimacin de la raz de f(x)=0 y es sucesivamente modificada. Lafrmula se la puede utilizar repetidamente para obtener los siguientes resultados y observarla convergencia o divergencia.

Ejemplo. Calcule en la ventana interactiva de Python las races reales de f(x) = ex- x = 0con la frmula de Newton.

Es conveniente graficar la ecuacin

>>>fromsympyimport*

>>>x=Symbol('x')

>>>f=exp(x)pi*x

>>>plot(f,(x,0,2))


58/357

58

En el grfico se observan dos races reales

>>>df=diff(f,x) Obtencin de f(x)>>>r=0.5 Valor inicial del grfico>>>r=rfloat(f.subs(x,r))/float(df.subs(x,r)) float evala la expresin>>>r

0.552198029112459

>>>r=rfloat(f.subs(x,r))/float(df.subs(x,r))

>>>r

0.5538253947739784


>>>r

0.5538270366428404


>>>r

0.5538270366445136


>>>r

0.5538270366445136

>>>float(f.subs(x,r)) Verificar si f(r) = 01.5192266539886956e17

El ltimo resultado tiene dieciseis decimales fijos.

Se puede observar la rapidez con la que el mtodo se acerca a la respuesta duplicandoaproximadamente, la precisin en cada iteracin. Esto concuerda con la propiedad deconvergencia cuadrtica.

Finalmente, es necesario verificar que este resultado satisface a la ecuacin:


59/357

59

Si se comienza con r = 1.5 se puede calcular la otra raz real:

>>>r=1.5

...

.

.

.

...


>>>r

1.6385284199703636

>>>float(f.subs(x,r)) Verificar si f(r) = 04.591445985947165e16

Ejemplo. Se propone el siguiente modelo para describir la demanda de un producto, endonde x es tiempo enmeses:

0.075x

d(x) 20x e

Encuentre el menor valor de x para el cual la demanda alcanza el valor de 80 unidades. Useel mtodo de Newton para los clculos. Elija el valor inicial del grfico y muestre los valoresintermedios.

La ecuacin a resolver es: 0.075xf(x) 20x e 80 0

>>>fromsympyimport*

>>>x=Symbol('x')

>>>f=20*x*exp(0.075*x)80

>>>plot(f,(x,0,50))

>>>r=5

>>>df=diff(f,x)


>>>r

6.311945053556488


>>>r

6.520455024943886


>>>r

6.525360358429756


>>>r6.525363029068741


>>>r

6.525363029069533


>>>r

6.525363029069533


60/357


61/357

61

Ejemplo. Encuentre una interseccin de las siguientes ecuaciones en coordenadas polares

r = 2+cos(3*t), r = 2 et

Ecuacin a resolver: f(t) =2+cos(3*t) (2 et) = 0

>>>frompylabimport*>>>t=arange(pi,2*pi,0.01)

>>>r=2+cos(3*t)

>>>polar(t,r) Grfico en coordenadas polares>>>grid(True)

>>>show()

>>>fromsympyimport*

>>>t=Symbol('t')

>>>f=2+cos(3*t)(2exp(t))

>>>r=1

>>>df=diff(f)

>>>r=rfloat(f.subs(t,r))/float(df.subs(t,r))

>>>r

0.21374870355715347


>>>r

0.8320496091165962


>>>r

0.6696807111120446


>>>r

0.696790503081824



62/357

62

>>>r

0.6973288907051911


>>>r

0.6973291231341587

>>>

r=r

float(f.subs(t,r))/float(df.subs(t,r))

>>>r

0.6973291231342021


>>>r

0.6973291231342021 (ngulo: 39.95.grados)

>>>2+cos(3*r)

1.50208660521455 (radio)

3.3.7 Instrumentacin computacional del mtodo de Newton

Para evitar iterar desde la ventana interactiva, se puede instrumentar una funcin que reciba

la ecuacin a resolver f, la variable independiente v

Documents

ANALISIS_NUMERICO_BASICO_CON_PYTHON_0.pdf