Source: https://www.scribd.com/document/44459243/An-123456
Timestamp: 2019-03-23 17:20:57+00:00

Document:
Uploaded by Wilber Angulo
Percy Antonio Ticona Centeno
Escuela Profesional de Matemáticas - UNSA
1. Nociones Básicas Sobre Errores 1
1.1. Factores que intervienen en la solución numérica de problemas . . . . . . . . . 1
1.1.1. Precisión de los datos de entrada . . . . . . . . . . . . . . . . . . . . . 1
1.1.2. Representación de los datos en el computador . . . . . . . . . . . . . . 2
1.1.3. Las operaciones numéricas efectuadas . . . . . . . . . . . . . . . . . . . 4
1.2. Errores Absolutos y Errores Relativos . . . . . . . . . . . . . . . . . . . . . . . 8
2. Ceros reales de funciones reales 11
2.1. Aislamiento de las Raíces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2. Refinamiento: Métodos Iterativos . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1. Método de Bisección . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2. Método de la Posición Falsa . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3. Método del Punto Fijo (MPF) . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.4. El Método de Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . 21
2.2.5. Método Secante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3. Comparación de los Métodos Iterativos . . . . . . . . . . . . . . . . . . . . . . 27
3. Resolución de Sistemas Lineales 29
3.1. Sistema General de Ecuaciones Lineales . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1. Conjunto Imagen de una Matriz A . . . . . . . . . . . . . . . . . . . . 30
3.1.2. Rango de una Matriz A . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2. Métodos para Resolver Sistemas de Ecuaciones Lineales . . . . . . . . . . . . . 31
3.2.1. Métodos Directos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2. Métodos Iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2.3. Comparación entre Métodos Directos e Iterativos . . . . . . . . . . . . 43
4. Introducción a Sistemas No Lineales 45
4.1. El Método de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.1. Convergencia y Rapidez del Método de Newton . . . . . . . . . . . . . 48
5. Interpolación y Aproximación 49
5.1. Interpolación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1.1. Interpolación Polinomial . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.1.2. Modos de Obtener el Polinomio pn . . . . . . . . . . . . . . . . . . . . 51
5.2. Aproximación: Caso Discreto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2.1. Método de Mínimos Cuadrados . . . . . . . . . . . . . . . . . . . . . . 56
. . . . . . . . . . 63 . . .1. .2. . . . . . . . . . . . . . . . . Integración numérica 61 6. . . 61 6. . Método de Simpson . . . . . . . . . . . .iv ÍNDICE GENERAL 6. . . . . . . . . . . . . . Método de los Trapecios . . . . . .
pues en su mayoría están construidos para tratar con problemas de grandes dimensiones. La importancia del estudio de métodos numéricos generales es indiscutible. ingenierías. algunas veces es posible garantizar la existencia de soluciones para esos modelos matemáticos. Estos mecanismos numéricos de cálculo deben caminar de la mano con el computador. las cuales son denominadas modelos matemáticos. pues gran parte de las investigaciones científicas en ciencias.Introducción La matemática está comprendida de varias partes. pero algunas también son fundamentales en diferentes disciplinas. recurren a técnicas numéricas para la obtención de resultados. cada una de ellas tiene importancia propia. o aproximaciones a las soluciones.. biología. Usando argumentos matemáticos teóricos. Estudiar métodos numéricos desde un punto de vista general nos permitirá analizar meca- nismos de cálculo capaces de otorgar soluciones. etc. allí donde las herramientas teóricas fracasaban. v . pero encontrar manualmente esas soluciones puede resultar extremadamente difícil y a veces imposible. Muchos problemas de la vida real pueden ser representados por formulaciones matemáticas.
vi INTRODUCCIÓN .
1. aunque todas las fases hayan sido ejecutadas correctamente. La forma cómo éstos son representados en el computador 3. ellos contienen una imprecisión inherente.Capítulo 1 Nociones Básicas Sobre Errores Existen diversas fases cuando intentamos resolver un problema mediante métodos numéricos. Precisión de los datos de entrada Cuando ingresamos los datos de un problema. La precisión de los datos de entrada 2. Las operaciones numéricas efectuadas 1. Factores que intervienen en la solución numérica de problemas Entre muchos factores. Puede suceder que los resultados finales obtenidos no sean justamente los esperados. El siguiente ejemplo aclara esta afirmación.1. los motivos pueden ser varios y los estu- diaremos a continuación. la siguiente figura esquematiza ese procedimiento. los resultados obtenidos al resolver un problema por métodos numéricos pueden depender de: 1. ya sea para calcular en un papel o trabajar en el computador. 1 . 1.1. quiere decir que no hay cómo evitarlos.
un número x en este sistema lo representaremos algunas veces. Representación de los datos en el computador Un número con representación decimal finita puede tener una representación infinita en el sistema binario. El valor de r quizá pueda ser conocido exactamente (r = 2).2 CAPÍTULO 1. cuando se usan los dígitos 14 dígitos decimales a la derecha del punto.00000000000001 + 1 y el resultado obtenido fue 1. tenemos que ingresar numérica- mente el radio r y el valor de π. el sistema de cómputo no comete error. Laboratorio 1.56 m2 Si consideramos 3.1 Sabemos que para calcular el área de un círculo. si el número de dígitos sobrepasa lo esperado.0000000000001. cuando se preste a confusión.14 × (2)2 = 12. Como un computador trabaja con el sistema binario y con una cantidad fija de dígitos. el sistema nos otorga una respuesta errada. por lo tanto no se obtendrán resultados finales exactos. necesariamente trabajará con una aproximación. 1.2. entonces el área será 3.000000000000001 + 1 y obtuvimos como respuesta 1. En el ejemplo anterior vimos que el mejor resultado se obtuvo en el último caso. El sistema con el que trabajamos comunmente es el decimal. lo cual es satisfactorio. aproximando el valor de π por 3. pero apenas podemos conocer una aproximación de π con un número finito de dígitos.566370616 m2 Claramente. Luego.141592654 × (2)2 = 12. hicimos: 0. ¿Qué sucedió? El ejemplo anterior nos hace ver que en el primer caso. las imprecisiones de los datos de entrada ocasionan imprecisiones en los resulta- dos. el área del círculo será: 3. cuan- do usamos un computador. si se usan 15 dígitos.2 Usando MatLab 6.0 en una PC de 32-bit con sistema operativo Windows XP.141592654. para corroborar los resultados obtenidos en el ejemplo 1. en nuestro caso 14. Por otro lado.1.1416. el . entonces el área del círculo estará dada por: 3. Mientras que. La razón se debe a que todo computador trabaja con un número finito y bien reducido de dígitos. NOCIONES BÁSICAS SOBRE ERRORES Ejemplo 1. por (x)10 . Ejemplo 1.2. hicimos la siguiente operación: 0. Pero.14. Así. dependiendo del sistema utilizado.1416 × (2)2 = 12.5664 m2 Pero si consideramos 3. ¿de cuántos dígitos decimales disponemos? El siguiente ejemplo intentará aclarar esta situación.1 Utilice un paquete o lenguaje de programación en un computador. el sistema lo trunca o redondea.
3. Pero.5 × 30000 = 15000 i=1 Después de implementar un pequeño programa en computador. para ai = (0. La representación de un número depende de la base elegida o disponible en la máquina en uso.11)10 . el resultado exacto debería ser S = (0.000111000010100011110101110000101000111101 2 Si el computador trabajara con 14 dígitos después del punto. Ejemplo 1. FACTORES QUE INTERVIENEN EN LA SOLUCIÓN NUMÉRICA DE PROBLEMAS3 sistema con el que trabaja un computador hoy en día es el binario. El siguiente ejemplo muestra cómo esta representación aparentemente inofensiva.1. respectivamente.5.1. el error ocurrido depende de la representación de los números en la máquina utilizada. un número puede tener representación finita con respecto a una base.3.5 1 = 0. y.11)10 . cuya representación en el sistema decimal es finita.3 Considere la siguiente sumatoria: X 30000 S= ai i=1 Para ai = 0. Sin embargo. La base decimal es la que empleamos . lo cual representa ya un error. Cualquier cálculo que envuelva números que no pueden ser representados a través de un número finito de dígitos.00000000063 ¿Cómo explicar la diferencia de resultados en este caso? Esto se debe a que el número (0. (5)10 y (101)2 representan el número 5 en el sistema decimal y binario. el resultado exacto debería ser X 30000 S = 0. no hay por qué preocuparse en este caso. haga un programa para ejecutar lo tratado en el ejemplo 1. no otorgará como resultado un valor exacto. Así por ejemplo. el número debería ser cortado o redondeado. Como vimos en el ejemplo 1. Por lo general. Laboratorio 1. un número y en este sistema será representado por (y)2 . mayor será la precisión obtenida. tiene una representación binaria infinita: ¡ ¢ 0. puede generar terribles errores cuando se trabaja en un computador. Todos los cálculos subsiguientes serán afectados por este hecho. Claramente. los resultados son los mismos. pero una representación infinita en otra base. el resultado obtenido por el computador fue S = 3300. Cuanto mayor sea el número de dígitos utilizados. del número máximo de dígitos usados en su representación. el resultado fue también 15000.11)10 × 30000 = 3300.2 Utilizando algún lenguaje de programación.
existen dígitos binarios d1 .. Los resultados finales serán convertidos para el sistema decimal y. Observe lo que pasa cuando un usuario interactúa con el computador: Los datos de entrada son enviados al computador por el usuario en el sistema decimal. tal que (0.125)10 = d1 × 2−1 + d2 × 2−2 + . Un computador opera normalmente en el sistema binario. (1.. dj . .4 CAPÍTULO 1.. 1.. esa información es convertida al sistema binario por el computador.. todas las operaciones son realizadas en ese sistema... finalmente.. (0. NOCIONES BÁSICAS SOBRE ERRORES generalmente. y. En términos generales. Por ejemplo.)2 será su representación binaria en la base 2.. + dj × 2−j + ..a2 a1 a0 )β .414213562. Todo este proceso es una fuente de errores que afecta el resultado final de los cálculos. .. Notemos que r tiene una representación finita. Por ejemplo: (10111)2 puede ser representado por 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20 Reordenando y resaltando la base 10 (10111)2 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20 ¡ ¢ = 2 23 + 2 + 3 = 2 × 101 + 3 × 100 = (23)10 ¿Cómo Convertir un Número Fraccionario de Representación Decimal a Binario? Consideremos ahora la conversión de un número fraccionario de base 10 para la base 2.. dado un número entre 0 y 1 en el sistema decimal. cualquier número entero en la base β... etc. Así.1) .3.. ... de la forma (aj aj−1 . puede ser escrito en la forma polinomial aj β j + aj−1 β j−1 + .d1 d2 . donde 0 ≤ ak ≤ β − 1 y k = 0. podemos convertir fácilmente un número entero representado en el sistema binario para el sistema decimal. Las operaciones numéricas efectuadas Pero errores no sólo ocurren el la imprecisión de los datos de entrada y su representación binaria.25.. d2 .. Conversión de Números en los Sistemas Decimal y Binario De un modo general. r = 1.. ¿cómo obtener su representación binaria? Considerando el número decimal fraccionario r = 0. serán transmitidos hacia el usuario. Errores ocurren también en las operaciones numéricas efectuadas por un sistema de cómputo (binario). pero antiguamente fueron empleadas otras bases.. s = 0.1. .. + a2 β 2 + a1 β 1 + a0 β 0 Mediante esa representación.. pero s y t tienen representaciones infinitas.dj .... t = 0. j.666. como la base 12 y la base 60.125.
1. Como la parte fraccionaria de 2 × 0.. El número (0. tendremos 0. 2 × 0. Aplicando ahora el mismo procedimiento para 0.250 = 0. haga un programa usando algún lenguaje de programación y verifique que: 1..250 = d2 × 2−1 + d3 × 2−2 + ..125..5 = d2 + d3 × 2−1 + d4 × 2−2 + . que es igual a 0.. de la forma cómo son realizadas las operaciones y del compilador utilizado... Implemente en algún lenguaje de programación el siguiente algoritmo que determina la precisión es el siguiente: ... mientras que d2 × 2−1 + d3 × 2−2 + .. total de dígitos en la mantisa.125 = d1 + d2 × 2−1 + d3 × 2−2 + . Este número depende totalmente del sistema de representación de la máquina: base numérica.5 = 1 = d3 + d4 × 2−1 + . puede ocasionar la ocurrencia de errores aparentemente inexplicables en los cálculos efectuados en sistemas computacionales binarios. tal que (1 + ε) > 1.3 Usando los procedimientos anteriores para convertir números enteros y frac- cionarios a binarios. de donde d3 = 1. para que sea usado como criterio de comparación para la detención del algoritmo..5 = d3 × 2−1 + d4 × 2−2 + . d2 = 0 y d3 = 1. debido a que sólo posee una cantidad fija de posiciones para guardar los dígitos de la mantisa de un número. Laboratorio 1. + dj × 2−j+3 + . de donde d2 = 0. tendremos 2 × 0. representa la parte fraccionaria de 2 × 0..... + dj × 2−j+1 + .. 2 × 0. el número (0.1..5 tenemos 0. Es importante conocer la precisión de la máquina porque en varios algoritmos se requiere ingresar como dato de entrada un valor positivo.125)10 = (0.1) por 2. Repitiendo el procedimiento para 0.125... Al ser esta aproximación usada para realizar los cálculos.1)2 2.11)10 .11)10 tiene una representación binaria infinita ¡ ¢ 0...001)2 Laboratorio 1. + dj × 2−j+1 + . d1 representa la parte entera de 2 × 0. Un computador que opera en el sistema binario. + dj × 2−j+1 + . El hecho de que un número no tenga representación finita en el sistema binario. En resumen tenemos: d1 = 0.. próximo de cero..5)10 tiene una representación binaria finita (0. que es 0.250. no puede esperarse un resultado exacto. necesariamente tendrá que almacenar una aproximación para (0.250.4 (Precisión de una máquina) La precisión de la máquina se define como el menor número ε > 0 en aritmética de punto flotante. + dj × 2−j+2 + .000111000010100011110101110000101000111101 2 3. FACTORES QUE INTERVIENEN EN LA SOLUCIÓN NUMÉRICA DE PROBLEMAS5 Multiplicando cada término de la expresión (1. el proceso de conversión termina.125)10 tiene representación finita en la base 2: (0. El número (0. Por tanto. Verifique cuántos dígitos el computador está considerando. Por lo tanto..5 es cero. + dj × 2−j+2 + .
el valor de u depende de la máquina con que se esté trabajando En una computadora.dt ) × β e donde β : La base en que la máquina opera t : El número de dígitos en la mantisa. Ejemplo 1.. es decir 99900 Ahora. 0 ≤ dj ≤ 9. +5] El menor número. si x = 235. u].999 × 10+5 . la representación será realizada por medio de truncamiento o redondeo.4 Considere una máquina que opera en el sistema β = 10.d1 d2 . hacer A A ← 2 S ← 1+A Paso 3: Hacer prec = 2A e imprimir prec...89 = 0.236×10+3 .6 CAPÍTULO 1. Aritmética de Punto Flotante Cualquier computador o calculadora representa un número en un sistema denominado arit- mética de punto flotante. en esta misma máquina. no nulo y en valor absoluto. NOCIONES BÁSICAS SOBRE ERRORES Paso 1: A ← 1. sólo una pequeña cantidad de números son representados exacta- mente. d1 6= 0 e : El exponente en el intervalo [1. En este sistema. el número r será representado en la forma: ± (. +5]. este número no será considerado de forma exacta en esta máquina. Debido a que t = 3.100 × 10−5 . entonces el número será representado como 0. S ← 2 Paso 2: Mientras S > 1. . t.235 × 10+3 . e ∈ [−5.23589 × 10+3 .. expresado en esta máquina será: m = 0. e ∈ [−5.. Los números representados en este sistema serán de la forma ± (.d1 d2 d3 ) × 10e . Si la máquina usa truncamiento. . d1 6= 0. j = 1. Este número posee 5 dígitos en la mantisa. consideremos el subconjunto de números reales caracterizados por: G = {x ∈ R : m ≤ |x| ≤ M} Pueden ocurrir varias cosas: 1. por lo general. Pero si la máquina usa redondeo. es decir 10−6 Mientras que el mayor número es: M = 0. t = 3. entonces el número será representado por 0. 0 ≤ dj ≤ β − 1. x ∈ G. Por ejemplo.
Por lo general. Algunos lenguajes de computador permiten que las variables sean declaradas en precisión dupla. al sumarlo al número y = 0. La adición en aritmética de punto flotante requiere el alineamiento de los puntos decimales de los dos números. x = 0. tal variable será representada en el sistema de aritmética de punto flotante de la máquina. se pueden perder dígitos significativos.9382 × 104 . pero con aproximadamente el doble de dígitos disponibles en la mantisa. tenemos x = 0. el tiempo de ejecución y requerimientos de memoria aumentan considerablemente. advierte la ocurrencia de overflow. se utiliza el menor exponente posible de la máquina. FACTORES QUE INTERVIENEN EN LA SOLUCIÓN NUMÉRICA DE PROBLEMAS7 2.3100 × 102 . En este caso.3134 × 102 = 0. si x = 0.937 × 104 y y = 0. La máquina en estas condiciones retorna una advertencia de underflow.0000 × 104 .3134 × 102 : 0. El cero puede representarse con una mantisa nula y cualquier exponente.0000 + 0.345×10−7 .938272 × 104 El resultado almacenado después del truncamiento será 0. Mientras que después del redondeo será 0.875 × 109 . Ejemplo 1.1. Ejemplo 1. Caso contrario.001272 × 104 Entonces. tal como muestra el siguiente ejemplo.6 Supongamos que tenemos una máquina que opera con base 10 y 4 dígitos en la mantisa.5 Sumar x = 0. Para eso. la mantisa de menor exponente debe ser desplazada para la derecha.003134 × 104 El resultado después del truncamiento sería 0.937 × 104 y y = 0. Si denotáramos al cero por 0.0000 × 104 + 0.1272 × 102 Alineando los puntos decimales. el exponente es mayor que 5 y la máquina no lo puede representar.003134) × 104 = 0.1. 3. x + y = (0. Este número no puede ser representado en esta máquina porque el exponente e es menor que −5. . si se usa cualquier exponente para denotar el cero. En este caso.003134 × 104 = (0.001272) × 104 = 0. |x| < m Por ejemplo. Debemos resaltar que en estas condiciones.0031 × 104 = 0. Esto significa que fueron perdidos 2 dígitos del valor exacto. |x| > M Por ejemplo.0000 × 104 + 0.9383 × 104 .937 + 0.
ya sea por desco- nocimiento nuestro o por la limitación del computador. tal como muestra el siguiente ejemplo. si usted gana un premio de S/. éste es conocido como error relativo. β = 10. observe que el error absoluto sigue siendo S/. Para el segundo caso. 10. con trucamiento 0. 10. El error relativo es definido como el valor absoluto dividido por el valor aproximado.01. probablemente no le agrade nada esta última situación. para . 1. Y así sucesivamente: −0. con redondeo 0. apenas el valor de x̄ es conocido.100 × 102 .314 × 10. es menor que 0.1 Represente los siguientes números en un sistema de aritmética de punto flotante (con redondeo y con truncamiento) de 3 dígitos. Ejemplo 1. pues apenas hay un error absoluto de S/.8 CAPÍTULO 1.100 × 102 . 3. en módulo.238 × 103 0. Ejemplo 1.271 × 10 0. podemos tomar para x̄ un valor dentro de este intervalo y tendremos que: |EAπ | = |π − x̄| < 0. lo que hace imposible obtener el error absoluto exacto.2.71828 0.272 × 10 underflow underflow overflow overflow Todo esto nos da una idea de los posibles errores que pueden suceder. con redondeo 0.053 − 238.314 × 10.7 Conociéndose que π ∈ h3. Por ejemplo.14 10. pero eso lo veremos en otra ocasión. sólo nos interesa la magnitud de este error. y cuando usted va a recogerlo le dicen que apenas tienen S/.01. En general. NOCIONES BÁSICAS SOBRE ERRORES Ejercicio 1. entonces a usted puede que no le importe la diferencia.82 Solución: Para el primer caso.238 × 103 −0. es decir: EAx x − x̄ ERx = = x̄ x̄ . 20 de premio.15i. en el proceso de la resolución numérica de problemas. en la práctica es mejor utilizar otro criterio para medir el error. Más aún. Lo que se puede hacer en ese caso es obtener una cota superior o una estimativa para el módulo del error absoluto. m = 10−4 y M = 10+4 : 3. 10.15 2. 9999990. con truncamiento 0. pues se trata de la mitad del premio. Debemos advertir que aún es posible realizar un análisis más completo del manejo de errores. a veces no es recomendable controlar algunos procesos basados en el error absoluto. y cuando va a recogerlo le dicen que sólo tienen S/. Pero qué pasa si usted ganó S/.000007 718235.8 En la práctica.14. Para evitar situaciones como la anterior. 10000000.01 En este caso diremos que el error absoluto de x̄ con respecto a π. diremos que el número x̄ está representado con presición menor que 0. Errores Absolutos y Errores Relativos Definimos el error absoluto como la diferencia entre el valor exacto de un número x y su valor aproximado x̄: EAx = x − x̄ Frecuentemente.
Delphi. Con la modificación del segundo ítem. 1. xk! . el valor usado en la serie será y = −x. 26 2.1101)2 Laboratorio 1. 1. experimente el cálculo de la serie con varios valores de n. ERRORES ABSOLUTOS Y ERRORES RELATIVOS 9 Frecuentemente.5 (Cálculo de ex ) Escriba un programa en un lenguaje conocido (Matlab. ¿Cuál sería el criterio para detener su programa e interrumpir el cálculo de la serie? .111111101)2 3.000001 9999990 Mientras que el error relativo respecto al segundo premio es 10 ER20 = =1 10 Con esto. Observe que el error relativo respecto al primer premio de S/. etc. Analice los resultados obtenidos. 3.) para calcular ex mediante la serie de Taylor con n términos.1. 1278 3. también se suele trabajar con el módulo de este valor. para cada valor de x. y en seguida. (101101)2 2. Experimente su programa con varios valores de x (x próximo de cero y distante de cero) y. (0. Estudie una manera de realizar esta operación de modo que k! no se sobrecargue. Para valores negativos de x. la serie de Taylor puede ser calculada con los términos que se desee. Visual C++. Intente combinar el cálculo del nume- rador con el del denominador y realizar divisiones intermedias. 2. (Dificultades con el cálculo del factorial) El cálculo de k! necesario en la serie de Taylor puede ser hecho de modo a evitar la ocurrencia de overflow. 1. Para esto es necesario k analizar cuidadosamente el k-ésimo término. 0. Pascal.10000000 es 10 ER10000000 = ≈ 0. (0. El valor de x y el número de términos n de la serie deben ser dados en la entrada de su programa. se calcula el valor de ex por medio de e1x . C. Ejercicio 1.2. digamos que en este caso se midió el error con más justicia. en la otra forma.3 Convierta los siguientes números binarios para su forma decimal. el programa debe calcular ex de dos formas: En una de ellas el valor de x es usado directamente en la serie de Taylor y.1217 Ejercicio 1.2 Convierta los siguientes números decimales para su forma binaria.
NOCIONES BÁSICAS SOBRE ERRORES .10 CAPÍTULO 1.
√ Ejemplo 2. Resolver tal ecuación significa encontrar ξ ∈ [a. Otra forma lo constituye el siguiente ejemplo. 2. Ejercicio 2. Gráfique. construimos una tabla de valores con el signo de f (x) para determinados valores de x: x 0 1 2 3 ··· f (x) − − + + · · · Analizando la tabla. 2i. qué casos podrían ocurrir. Determine los intervalos donde se encuentre por lo menos una raíz.1 Considere la siguiente función f (x) = x − 5e−x . b] ⊂ R 7→ R. Ejercicio 2. Aislamiento de las Raíces Consiste en obtener un intervalo que contenga la raíz deseada.1) donde f : [a.1. Algunas de las técnicas para resolver esta ecuación. b] de modo que f (ξ) = 0. se obtiene una aproximación de la raíz deseada (refinamiento). es decir. requieren de un procedimiento que comprende esencialmente dos fases. y este cero está en el intervalo h1.1 Si f (a) f (b) > 0. podemos analizar el signo de la derivada de f : 1 f 0 (x) = √ + 5e−x > 0.1) o simplemente un cero de f . vemos que f admite por lo menos un cero en el intervalo h1. 2i.2 Qué pasa si f (a) f (b) ≤ 0.3 Qué pasa si f (a) f (b) ≥ 0. encontrar una raíz de la ecuación (2. Para ver si ese cero es único en ese intervalo. En la segunda fase. Una alternativa es mediante una observación gráfica (probablemente con ayuda de un software). 11 . ∀x > 0 2 x Podemos concluir que f admite un único cero en todo su dominio. Solución: Tenemos que Df = R+ .Capítulo 2 Ceros reales de funciones reales En esta sección vamos a resolver la ecuación representada por f (x) = 0 (2. Ejercicio 2. En la primera fase un intervalo conteniendo la raíz es obtenido (ais- lamiento de las raíces).
12 CAPÍTULO 2. CEROS REALES DE FUNCIONES REALES
2.2. Refinamiento: Métodos Iterativos
Aquí veremos varios métodos numéricos de refinamiento de una raíz. Todos ellos pertenecen
a una clase de métodos iterativos. Por lo general, estos métodos sólo otorgan una aproximación
Cuando se use un método iterativo, debemos considerar un criterio para detener el algo-
ritmo respectivo. En los métodos que buscan una raíz, éstos se repetirán hasta que xk sea
próxima a la raíz exacta ξ con precisión ε > 0, esto ocurrirá si:
1. |xk − ξ| < ε
2. |f xk | < ε
Pero, ¿cómo efectuar 1 si no se conoce ξ? Una forma es reducir el intervalo que contiene a
la raíz en cada iteración. Al conseguirse un intervalo [a, b] tal que
ξ ∈ [a, b] y b−a<ε
entonces ∀x ∈ [a, b], |x − ξ| < ε. Por tanto, cualquier x ∈ [a, b] puede ser tomado como xk .
Figura 2.1: f (ξ) = 0
El orden de grandeza de los números con que trabajamos puede darnos poca información,
tal como mostraba el ejemplo 1.8, es aconsejable en estos casos utilizar el error relativo. Por
ejemplo, podemos considerar xk próximo de ξ si
|f (xk )|
donde L = |f (x) |, para algún x escogido en una vecindad de ξ.
Otro aspecto que debemos tener en cuenta es el máximo número de iteraciones permitidas
por el algoritmo. Esto ayuda a evitar que el programa en computador trabaje indefinidamente,
sobre todo en el caso cuando el algoritmo no converge.
Antes de más nada, debemos hacer una aclaración con respecto a método y algoritmo.
Entendemos por método a un procedimiento con las justificaciones matemáticas necesarias
2.2. REFINAMIENTO: MÉTODOS ITERATIVOS 13
para resolver un determinado problema. Mientras que por algoritmo, entendemos como el
resumen del método, una especie de receta.
Existen varios métodos numéricos para obtener un cero real de una función real, algunos
simplemente requieren que la función sea continua, mientras que otros requieren que la función
sea diferenciable. En lo que resta de este capítulo analizaremos cada uno de los métodos más
populares que existen hoy en día. En nuestro caso, analizar comprenderá la construcción del
método, estudiar las propiedades de convergencia y la rapidez del mismo.
Para estudiar la convergencia debemos dar las hipótesis para que el método garantice una
solución. Por otro lado, para analizar la rapidez del método, es necesario tener en consideración
El número de iteraciones: Dada la precisión deseada ε, determinar el número de itera-
ciones, k, para que el algoritmo respectivo se detenga.
La rapidez: Una vez garantizada la convergencia. Determinar cuál es la tasa o rapidez (ve-
locidad) de convergencia con que trabaja el algoritmo
Lo más deseable es obtener el número de iteraciones que un algoritmo requiere para resolver
el problema, al menos una cantidad aproximada de éste, pero no siempre es posible tal hazaña.
A veces es posible obtener sólo la tasa de convergencia del algoritmo, esto también dará
información sobre el desempeño del mismo, lo cual permitirá realizar comparaciones para
decidir por el algoritmo más eficiente para un determinado problema Los detalles relacionados
a estos conceptos serán explicados a medida que vayamos avanzando.
2.2.1. Método de Bisección
Sea f una función continua en el intervalo [a, b] tal que f (a) f (b) < 0. El objetivo de
este método es reducir la amplitud de este intervalo que contiene la raíz hasta alcanzarse una
precisión requerida, (b − a) < ε, usando para eso una sucesiva división de [a, b] a la mitad.
Figura 2.2: Método de bisección
Algoritmo 2.1 (Bisección) Dados a y b tales que f (a) f (b) < 0. Sea ε > 0 la presición
14 CAPÍTULO 2. CEROS REALES DE FUNCIONES REALES
1. Si (b − a) < ε. Elegir x̄ ∈ [a, b] y terminar el algoritmo. Caso contrario, ir al paso 2.
2. Hacer k = 1 e ir al paso 3.
3. Hacer c = 2
e ir al paso 4.
4. Si f (a) f (c) > 0, hacer a = c e ir al paso 5. Caso contrario, hacer b = c e ir al paso 5.
5. Si b − a < ε, elegir x̄ ∈ [a, b] y finalizar el algoritmo. Caso contrario, hacer k = k + 1 y
volver al paso 3.
Estudio de la Convergencia del Método de Bisección Bajo las hipótesis establecidas,
es claro que el método de la bisección construirá una sucesión {xk } que converge a una raíz.
Para probar esto analíticamente procedemos del siguiente modo.
Supongamos que [a0 , b0 ] sea el intervalo inicial y ξ la única raíz de f en el interior de ese
intervalo. El método de la bisección genera tres sucesiones:
La sucesión {ak }k∈N : No decreciente y acotada superiormente por b0 . Luego, existe r ∈ R
tal que lı́mk→∞ ak = r.
La sucesión {bk }k∈N : No creciente y limitada inferiormente por a0 . Luego, existe s ∈ R tal
que lı́mk→∞ bk = s.
ak +bk
La sucesión {ck }k∈N : Generada por ck = 2
, donde ak < ck < bk , para todo k = 1, 2, ....
Observe que el tamaño de cada intervalo es la mitad del intervalo anterior. Así, para
bk − ak =
(b0 − a0 )
lı́m (bk − ak ) = lı́m =0
k→∞ k→∞ 2k
Como {ak }k∈N y {bk }k∈N son convergentes:
lı́m bk − lı́m ak = 0 =⇒ s − r = 0
Por lo tanto, s = r. Sea λ = s = r el límite de las dos sucesiones. Dado que para todo
k = 1, 2, ... el punto ck ∈ hak , bk i, entonces
lı́m ck = λ
Resta probar apenas que λ es un cero de la función f , o sea, f (λ) = 0. Observe que en
cada iteración k = 1, 2, ... tenemos que f (ak ) f (bk ) < 0. Entonces, dado que hemos asumido
f continua en [a, b]:
0 ≥ lı́m f (ak ) f (bk ) = lı́m f (ak ) lı́m f (bk )
= f ( lı́m ak )f ( lı́m bk ) = f (r) f (s) = f (λ) f (λ)
= (f (λ))2
de donde concluimos que f (λ) = 0. Por tanto, lı́mk→∞ ck = λ es un cero de f , como habíamos
asumido que en el intervalo había una única raíz, tenemos que λ = ξ.
2. se desea encontrar una aproximación a un cero de la función definida por f (x) = x log x − 1 la cual está en el intervalo [2. x̄ ∈ [ak .1 En algún lenguaje de programación de su preferencia. REFINAMIENTO: MÉTODOS ITERATIVOS 15 Estimación del Número de Iteraciones Dada una precisión ε > 0 y un intervalo inicial [a. en el algoritmo 2.1. Conclusión 2. Converge lentamente. 2. b]. implemente el algo- ritmo de la bisección. bk ] Por tanto. .1 (sobre el método de bisección) Si f : R 7→ R es continua en el intervalo [a. x̄ es realmente una aproximación a la raíz ξ de f en [a. se debería obtener el valor k de tal forma que bk − ak < ε. bk−1 − ak−1 b0 − a0 bk − ak = = 2 2k Para que el algoritmo se detenga.1) hasta que se cumpla b − a < ε..2 Usando el algoritmo 2. 3] y con precisión ε = 10−2 . Cada iteración no requiere cálculos complicados. ¿Cuántas iteraciones como mínimo debería efectuar el algoritmo? Solución: Según (2.2) vemos que ¥ ¡ ¢¦ ¥ ¡ ¢¦ k ≥ log2 (3 − 2) − log2 10−2 + 1 = log2 1 − log2 10−2 + 1 ¥ ¡ ¢¦ = − log2 10−2 + 1 = 8 Luego. b] y f (a) f (b) < 0: El método de bisección genera una sucesión que converge a la raíz de f (x) = 0. el algoritmo debería detenerse con k = 8 iteraciones.1. esto se consigue mediante las reducciones suvesivas del intervalo de búsqueda hasta una precisión deseada.2) Por lo tanto.. a priori. o sea b0 − a0 <ε 2k Esto a su vez equivale a decir que b0 − a0 2k > ε Lo cual implica que k > log2 (b0 − a0 ) − log2 (ε) (2. . pruebe con varios ejemplares. Ejemplo 2. b].2. es posible saber. cuántas iteraciones serán efectuadas por el método de la bisección (algoritmo 2. Las hipótesis no son rigurosas. Vimos que para k = 1. Laboratorio 2. si el número de iteraciones k es por lo menos blog2 (b0 − a0 ) − log2 (ε)c + 1 el intervalo [ak . bk ] conteniendo a la raíz ξ verifica |x̄ − ξ| ≤ bk − ak < ε.
podemos tomarlo de la siguiente manera: a |f (b)| + b |f (a)| ck = |f (b)| + |f (a)| que en realidad es una media aritmética ponderada entre a y b. Luego.16 CAPÍTULO 2. con pesos |f (b)| y |f (a)|.2. Esto muestra que la sospecha puede estar totalmente errada. en la figura 2.4 Haga un algoritmo que resuma el método de la posición falsa.4. tal como se aprecia en la figura 2. pues el valor de |f (a)| puede ser pequeño y. en vez de tomar ck como el punto medio. Problema 2.3 se aprecia que al ser |f (a)| pequeño en comparación a |f (b)|. las cosas no son como parecen. Lamentablemente. de ahí el nombre. Figura 2. Por ejemplo.1 Analice la convergencia y el número de iteraciones requeridas del método de la posición falsa. lo que retrasaría la convergencia del método. en cada iteración. como lo hacía el método de bisección. CEROS REALES DE FUNCIONES REALES 2.3: Raíz cercana al lado izquierdo de [a. Podemos esperar conseguir una raíz aproximada usando las informaciones sobre los valores de x disponibles a cada iteración. Suponga que el intervalo ha. bi con- tiene una única raíz de la ecuación f (x) = 0. pruebe con varios ejemplares y compare el número de iteraciones con el método de bisección. b] Ejercicio 2. tenemos: af (b) − bf (a) ck = f (b) − f (a) Lo que resta del método de la posición falsa es análogo al método de bisección. podemos sospechar que la raíz se encuentra más cercana al punto a que al punto b. Método de la Posición Falsa Sea f : R 7→ R continua en [a. implemente el algo- ritmo de la posición falsa. Laboratorio 2. sin embargo. Después de unos cálculos.2. . la parte donde no se encuentra la raíz debería ser desechada y el intervalo debería ser reducido hasta una presición deseada. b] tal que f (a) f (b) < 0. la raíz puede estar muy lejos de a.2 En algún lenguaje de programación de su preferencia.
Algunas candidatas a función iteración son las siguientes: x2 1. la raíz buscada. más adelante veremos que esta idea trae ciertas ventajas. El Método del Punto Fijo consiste en lo siguiente: 1. x 6= −2 10 3. θ (ξ) = ξ. Ejemplo 2. θ (x) = 5 − 2 10 2. x = θ (x). 2. pueden existir muchas funciones iteración asociadas a una sola ecuación. resolver el problema de encontrar una raíz de una ecuación se convierte en un otro problema de hallar un punto fijo de una función.3.4: Raíz alejada de a y |f (a)| pequeño 2. si f (λ) = λ. punto fijo de θ. mediante la relación xk+1 = θ (xk ) Observe que la función θ debe ser una función que cumpla: f (ξ) = 0 si.2.3 Dada la ecuación x2 + 2x − 10 = 0. x 6= 0 La forma general de las funciones iteración está dada por θ (x) = x + A (x) f (x) con la condición que en ξ. REFINAMIENTO: MÉTODOS ITERATIVOS 17 Figura 2. Dado un punto inicial x0 ∈ R. La función θ con esa característica se denomina función iteración asociada a la ecuación f (x) = 0. θ (x) = x − 2.2. Naturalmente. Transformar la ecuación f (x) = 0 en una ecuación equivalente. se tenga A (ξ) 6= 0. De este modo. θ (x) = x+2 . . Aunque a simple vista no parezca. y sólo si.2. generar una sucesión {xk } de aproximaciones hacia ξ. Método del Punto Fijo (MPF) Se dice que λ es un punto fijo de una función f .
entonces ξ + A (ξ) f (ξ) = ξ implica que A (ξ) f (ξ) = 0. si x0 ∈ I. el método del punto fijo puede o no convergir a la solución de la ecuación f (x) = 0. claramente tenemos θ (ξ) = ξ. 1. desde (2. ( =⇒ ) Sea ξ tal que f (ξ) = 0. 2. 2. 1. como I está centrado en ξ. se tiene xk+1 = θ (xk ). entonces xk ∈ I. Prueba. la distancia entre xk+1 y ξ es menor que la distancia entre xk y ξ. xk < ck < ξ. 2. Teorema 2. 1. . claramente xk ∈ I para todo k = 1.. Por lo tanto.. vemos que si xk ∈ I entonces xk+1 ∈ I. La prueba consta de dos partes: 1. 2. por el teorema del valor medio. .18 CAPÍTULO 2. Para probar la segunda parte.. 2. 2. lı́mk→∞ xk = ξ Primero. Si 1... Prueba.. . El siguiente teorema establece las condiciones suficientes para que esta convergencia suceda. Además.3) vemos que: |x1 − ξ| ≤ M|x0 − ξ| |x2 − ξ| ≤ M|x1 − ξ| ≤ M 2 |x0 − ξ| . pues A (ξ) 6= 0 por definición...2 Sea ξ una raíz de la ecuación f (x) = 0.3) Es decir. esto a su vez implica que f (ξ) = 0. para todo k = 0. ( ⇐= ) Si θ (ξ) = ξ. para todo x ∈ I. 2.. se tiene que f (ξ) = 0 ⇐⇒ ξ = θ (ξ). . aislada en un intervalo abierto I centrado en ξ. k = 0. |xk − ξ| ≤ M k |x0 − ξ| de donde lı́mk→∞ |xk − ξ| = 0. Luego. |xk+1 − ξ| = |θ0 (ck ) ||xk − ξ| ≤ M|xk − ξ| < |xk − ξ| k = 0..1 Si θ es una función iteración de la ecuación f (x) = 0. lı́mk→∞ xk = ξ. . como ξ es una raíz exacta de la ecuación f (x) = 0. (2. desde aquí xk+1 − ξ = θ (xk ) − θ (ξ) Como θ es continua y diferenciable en I. Luego. converge hacia ξ. y sólo si. Estudio de la Convergencia del Método del Punto Fijo Dependiendo de la elección de la función iteración θ. .. para cualquier k = 0. θ y θ0 son funciones continuas en I. 1... 3. . CEROS REALES DE FUNCIONES REALES Teorema 2. lı́mk→∞ xk = ξ. pues 0 ≤ M < 1. existe ck . x0 ∈ I Entonces. entonces f (ξ) = 0 si. la sucesión {xk } generada por la regla xk+1 = θ (xk ). |θ0 (x) | ≤ M < 1. Si x0 ∈ I. 1. θ (ξ) = ξ. . tal que xk+1 − ξ = θ (xk ) − θ (ξ) = θ0 (ck ) (xk − ξ) k = 0. Como θ (ξ) = ξ + A (ξ) f (ξ). 2. Sea θ una función iteración para esta ecuación..
el algoritmo se detendrá cuando |f (xk )| < ε. finalizar el algoritmo 3.2.2.2 son satisfechas.4 Sea la función f (x) = x2 +2x−10 cuya raíz es ξ ≈ 2. hacer x̄ = x1 . x 6= −2 x+2 Observe que |θ01 (x) | = | − x| = |x| < 1 ⇐⇒ x ∈ h−1.2 no afirma nada con respecto de la convergencia de la sucesión {xk } generada por xk+1 = θ1 (xk ).1622i ∪ h1. pues θ1 no cumple la hipótesis. Suponer que las hipótesis suficientes del teorema 2. Observe que ¯ ¯ D E D√ E ¯ 10 ¯ √ |θ2 (x)| = ¯¯ 0 ¯ < 1 ⇐⇒ x ∈ −∞. no existe un intervalo I centrado en ξ tal que |θ01 (x) | < 1 para todo x ∈ I. Algoritmo 2. Datos iniciales: a) x0 . En este caso.1622. k = 1 4. La aproximación al punto fijo ξ (la raíz buscada) será x̄. tal que |θ02 (x)| < 1 para todo x ∈ I. existe un intervalo I centrado en ξ. cuando se usa como función iteración 10 θ3 (x) = − 2. x 6= 0 x Además.2 (Punto Fijo) Considere la ecuación f (x) = 0 y la ecuación equivalente x = θ (x). 1i Luego. Por otro lado.1622. Dada una precisión deseada ε > 0. si usamos la función iteración θ2 . −5.5 Analice el caso para la función f (x) = x2 + 2x − 10 cuya raíz es ξ ≈ 2. Si |θ (x1 )| < ε1 o si |x1 − x0 | < ε2 .3166. el teorema asegura la convergencia del MPF tomando x0 ∈ I. +∞ ≈ (x + 2)2 ¯ h−∞. finalizar el algoritmo . 1. REFINAMIENTO: MÉTODOS ITERATIVOS 19 Ejemplo 2. hacer x̄ = x0 . x1 = θ (x0 ) 5. la aproximación inicial b) ε1 y ε2 las precisiones deseadas 2. analice todos los casos cuando consideramos la otra raíz ξ ≈ −5. − 10 − 2 ∪ 10 − 2. +∞i Luego. Dadas las funciones iteración x2 θ1 (x) = 5 − 2 y 10 θ2 (x) = . la situación es diferente.3166. Si |f (x0 )| < ε1 . el método del punto fijo puede convergir o no cuando se utilice θ1 como función iteración. El teorema 2. Ejercicio 2.
Tasa de Convergencia del Método de Punto Fijo Cuando vimos el método de la bisección. © ª Definición 2. 1. Observe que el método diverge cuando usamos θ1 . Esto indica que para valores grandes de k0 y en las proximidades de r̄. Si P = 2 y β < ∞.20 CAPÍTULO 2. es claro que el error cometido en la iteración k + 1 es aproximadamente el cuadrado del error cometido en la iteración anterior. CEROS REALES DE FUNCIONES REALES 6. Pero eso no siempre es posible. ∀k ≥ k0 | {z } | {z } ek+1 ek Significa que el error ek+1 cometido en la iteración k + 1 es menor (linealmente) que el error ek en la iteración k.. el error ek+1 disminuye considerablemente con respecto a ek : ° (k+1) ° ° °2 °r − r̄° ≈ β °r(k) − r̄° . © ª Una manera natural de ver esta situación es la siguiente: supongamos que r(k) es una sucesión generada por un algoritmo la cual converge a la solución r̄. . así.1 (Tasa o rapidez de convergencia) Sea la sucesión r(k) generada por al- gún algoritmo. ∀k ≥ k0 | {z } | {z } ek+1 e2k Así. Si P ≥ 1 y β = 0. de modo que r(k) → r̄ cuando k → ∞. un algoritmo con tasa de convergencia súper lineal será más rápido que uno con tasa de convergencia lineal. . la sucesión tiene tasa de convergencia súper lineal. k = k + 1.4. En el caso de una tasa de convergencia cuadrática. la sucesión se dice que tiene una tasa de convergen- cia lineal (por lo menos lineal). la tasa de convergencia del algoritmo es el supremo P de los números no negativos p satisfaciendo: ° (k+1) ° °r − r̄° lı́m p = β < ∞ k→∞ kr (k) − r̄k Si P = 1 y el radio de convergencia β < 1. Laboratorio 2. pruebe con varios puntos iniciales e interprete los resultados. Eso nos permitirá calificar a un algoritmo como lento o rápido.. notamos que era posible obtener una cota inferior para el número de iteraciones a ser realizadas por el algoritmo. necesitamos de algunos parámetros que nos indiquen con qué rapidez la sucesión generada por un algoritmo converge a la solución deseada.3 En algún lenguaje de programación de su preferencia. un algoritmo con tasa de convergencia cuadrática convergirá con mayor rapidez hacia un punto de acumulación. cuando k0 es grande. que uno que posee tasa de convergencia súper lineal. Asumamos que r(k) 6= r̄ para todo k = 0.. donde el algoritmo presenta una tasa de convergencia lineal. 2. Volver al paso 4. implemente el MPF y ejecute el programa sobre el problema del ejemplo 2. x0 = x1 7. Por otro lado. entonces diremos que la sucesión tiene una tasa de convergencia cuadrática. entonces: ° (k+1) ° ° ° °r − r̄° ≈ β °r(k) − r̄°.
dada la ecuación f (x) = 0 cuya raíz es ξ. REFINAMIENTO: MÉTODOS ITERATIVOS 21 Proposición 2. |xk+1 − ξ| = |θ0 (ck ) | xk < ck < ξ. donde A (ξ) 6= 0. 1. esto se consigue escogiendo una función iteración de modo que θ0 (ξ) = 0.. ..2. tenemos |xk+1 − ξ| ¯ ³ ´¯ ¯ 0 ¯ lı́m = lı́m |θ (ck ) | = ¯θ lı́m ck ¯ = |θ0 (ξ)| = β ≤ M < 1 0 k→∞ |xk − ξ| k→∞ k→∞ Problema 2. k = 0..4. Consideramos la forma general de la función iteración θ (x) = x + A (x) f (x). donde I es un intervalo centrado en la raíz. θ (x) = x + A (x) f (x) =⇒ θ0 (x) = 1 + A0 (x) f (x) + A (x) f 0 (x) Luego. Hacia este objetivo. Una de las condiciones para la convergencia es que |θ0 (x) | ≤ M < 1. k = 0. la raíz. θ0 (ξ) = 1 + A0 (ξ) f (ξ) + A (ξ) f 0 (ξ) =⇒ θ0 (ξ) = 1 + A (ξ) f 0 (ξ) de donde 1 θ0 (ξ) = 0 ⇐⇒ 1 + A (ξ) f 0 (ξ) = 0 ⇐⇒ A (ξ) = − .2.2. Prueba. para todo x ∈ I. f 0 (ξ) 6= 0 f0 (ξ) .3). La segunda afirmación se debe al siguiente hecho: cuando analizamos la tasa de conver- gencia del MPF. notamos que: 1. Así. |xk − ξ| Tomando límites. por la continuidad de θ y θ0 . 2. Luego.2 Calcule la tasa de convergencia del método de la bisección.. El Método de Newton-Raphson Cuando estudiamos el método del punto fijo. . tenemos |xk+1 − ξ| = |θ0 (ck ) ||xk − ξ| xk < ck < ξ. con la nueva condición θ0 (ξ) = 0. entonces la tasa de convergencia es por lo menos lineal. se espera que la tasa de convergencia sea por lo menos súper-lineal. Observe que con esto. La convergencia del método será más rápida cuanto menor sea |θ0 (ξ) |. 2. 1. vimos que |xk+1 − ξ| lı́m = |θ0 (ξ) | < 1 |xk − ξ| Lo que intenta hacer el método de newton es acelerar la convergencia del MPF. 2. Desde (2. 2. más adelante veremos que ella alcanza a ser cuadrática.1 (Tasa de convergencia de MPF) Asumiendo que el Método del Punto Fijo genera una sucesión que converge a ξ.
donde L es una función lineal afín que es parecida. el problema difícil será hallar una raíz de la ecuación no lineal f (x) = 0.5) f 0 (xk ) Otro Enfoque del Método de Newton-Raphson Desde el punto de vista geométrico. 2.4) f 0 (x) Observe que 0 (f 0 (x))2 − f (x) f 00 (x) f (x) f 00 (x) θ (x) = 1 − = . 2. formando una sucesión {xk }∞ k=0 . donde f (xk ) xk+1 = xk − 0 .6). .. existe δ > 0 tal que f (x) ≈ L0 (x) = f (x0 ) + f 0 (x0 ) (x − x0 ) para todo x ∈ hx0 − δ. a la función no lineal f en torno al punto xk . mientras que el problema fácil asociado será resolver la ecuación Lk (x) = 0.. f (xk ) Bajo algunas hipótesis se consigue que lı́mk→∞ xk = ξ. 1. sea el problema (difícil) que consiste en hallar una raíz de f (x) = 0 y x0 ∈ R una aproximación inicial.. f 0 (xk ) 6= 0. . Así.6) fácilmente: f (x0 ) L0 (x) = 0 ⇐⇒ f (x0 ) + f 0 (x0 ) (x − x0 ) = 0 ⇐⇒ x = x0 − . Por el teorema de Taylor. esperamos que x1 sea una mejor aproximación que x0 a la raíz buscada. CEROS REALES DE FUNCIONES REALES Esto nos motiva a definir 1 A (ξ) = − f0 (ξ) Entonces. f 0 (x0 ) 6= 0 f 0 (x0 ) Sea x1 la solución del problema (2. dada la ecuación f (x) = 0. . 1. Luego.22 CAPÍTULO 2. al menos localmente. la función iteración deseada será de la forma: f (x) θ (x) = x − (2. el método de Newton es un caso particular del MPF y consiste en construir una sucesión definida por la regla f (xk ) xk+1 = θ (xk ) = xk − . k = 0. dado x0 ∈ R. Este procedimiento puede ser repetido iterativamente.. el método de Newton puede ser visto como la solución de un problema difícil. mediante la sucesiva resolución de problemas fáciles. k = 0. f 0 (x) 6= 0 (f 0 (x))2 (f 0 (x))2 y como f (ξ) = 0. (2. dada una aproximación inicial xk ∈ R a la raíz buscada. f 0 (xk ) 6= 0. Es decir. podemos resolver L0 (x) = 0 (2. x0 + δi. Por lo tanto. se tiene que θ0 (ξ) = 0.
f (xk ) xk+1 = xk − .. 1. son continuas y |θ0 (x) | < 1. f 0 y f 00 continuas en un intervalo abierto I que contiene en su interior la raíz ξ de f (x) = 0. centrado en ξ. θ y θ0 son continua en I¯ 2.. Así. θ0 (x) = f(f (x)f (x) 0 (x))2 y por hipótesis f 0 (ξ) 6= 0. Teorema 2. tal que: 1. Observe que el método de newton es en realidad un MPF con función iteración θ (x) = x − ff0(x) (x) . Así. Por lo tanto. . tal que si x0 ∈ I. entonces existe un intervalo abierto I¯ ⊂ I conteniendo ¯ la sucesión {xk } generada por la raíz ξ. tal que f 0 (x) 6= 0 para todo x ∈ I1 . centrado en ξ. f 0 (xk ) convergirá para ξ. f 0 y f 00 son continuas y f 0 (x) 6= 0. es posible obtener un intervalo abierto I1 ⊂ I. para probar la convergencia debemos probar que existe un I¯ ⊂ I.3 Sean f . ¯ la sucesión {xk } generada por la regla de 0 correspondencia xk+1 = xk − f (xk ) /f (xk ) converge hacia la raíz ξ de f (x) = 0. donde f 0 (ξ) 6= 0.2. para todo x ∈ I¯ 00 Vemos que θ (x) = x − ff0(x) (x) .5: Iteraciones Newton Convergencia del Método de Newton-Raphson A continuación damos las condiciones bajo las cuales se asegura la convergencia del método de Newton. 00 Como θ0 (x) = f(f(x)f (x) 0 0 0 (x))2 . 2. . en el intervalo I1 se tiene que f. θ y θ0 son continuas en I1 . Como f 0 es continua en I. Por lo tanto. ξ ∈ I1 . REFINAMIENTO: MÉTODOS ITERATIVOS 23 Figura 2.2. Prueba. ∀x ∈ I1 . ∀x ∈ I. |θ0 (x) | ≤ M < 1. si x0 ∈ I. k = 0. f 0 (xk ) 6= 0. hemos encontrado un intervalo abierto I¯ = I2 centrado en ξ donde θ y θ0 ¯ Así. θ es continua en I1 y θ (ξ) = 0. entonces es posible obtener otro intervalo abierto I2 ⊂ I1 . tal que |θ0 (x) | < 1 para todo x ∈ I2 .
Laboratorio 2. P = 2. ε2 > 0 las precisiones deseadas. CEROS REALES DE FUNCIONES REALES En pocas palabras. k = 1 2. Algoritmo 2. tenemos 1 0 = f (xk ) + f´0 (xk ) (ξ − xk ) + f 00 (ck ) (ξ − xk )2 2 de donde 1 f (xk ) = f 0 (xk ) (xk − ξ) − f 00 (ck ) (xk − ξ)2 2 . Compare sus resultados con los métodos anteriormente estudiados. es decir.1. Suponga que las hipótesis de suficiencia dadas en el teorema 2. Sea {xk } la sucesión generada por el método de newton. Caso contrario. Paso inicial: Sea x0 una aproximaxión inicial de ξ y ε1 . ese defecto se compensa con la rapidez con que converge el método. Debido a que el método de Newton es un caso particular de MPF.3 son satisfechas.24 CAPÍTULO 2. Tasa de Convergencia del Método de Newton-Raphson Dada ξ una raíz exacta de la ecuación f (x) = 0. tal que lı́mk→∞ xk = ξ. x1 = x0 − f (x0 ) /f 0 (x0 ) 3. Nosotros mostraremos que es mucho más que eso. Supongamos además que se satisfacen todas las hipótesis del teorema 2. Caso contrario. hacer x̄ = x0 y finalizar. ck está entre x y ck 2 Para x = ξ. El algoritmo otorgará una aproximación x̄ a las raíz ξ. hacer a) x0 = x1 b) k = k + 1. el método alcanzará una tasa cuadrática. Observe que f (xk ) f (xk ) f (xk ) xk+1 = xk − 0 =⇒ xk+1 − ξ = xk − ξ − 0 =⇒ ek+1 = ek − 0 f (xk ) f (xk ) f (xk ) donde ek = xk − ξ. lo que dice el teorema anterior es que el método de Newton converge sólo si el punto inicial es tomado lo suficientemente próximo de la solución ξ. Si |f (x1 ) | < ε1 o si |x1 − x0 | < ε2 . hacer x̄ = x1 y finalizar. Paso principal: Si |f (x0 ) | < ε1 . entonces debe tener por lo menos una tasa de convergencia lineal. implemente el al- goritmo de Newton y experiméntelo con diversos ejemplares.3 (Newton-Raphson) Dada la ecuación f (x) = 0. en la definción 2. esta propiedad se conoce como convergencia local. Volver al paso 2.4 En algún lenguaje de programación de su preferencia. Usando Taylor para f en torno al punto xk : 1 f (x) = f (xk ) + f´0 (xk ) (x − xk ) + f 00 (ck ) (x − xk )2 . Más adelante veremos que. debido a la condición θ0 (ξ) = 0.3. en cierta forma. la cual es una desventaja. hacer: 1.
7) al límite.5.2. la función iteración Newton queda establecida como f (xk ) θ (xk ) = xk − f (xk )−f (xk−1 ) xk −xk−1 f (xk ) (xk − xk−1 ) = xk − f (xk ) − f (xk−1 ) .2. Para este caso. REFINAMIENTO: MÉTODOS ITERATIVOS 25 Dividiendo entre f 0 (xk ). evaluar f 0 (xk ). 2. es decir. obtenemos f (xk ) f 00 (ck ) (xk − ξ)2 = (xk − ξ) − f 0 (xk ) 2f 0 (xk ) f 00 (ck ) e2k = ek − 2f 0 (xk ) Luego. Una manera de enfrentar esto es considerar una aproximación de la derivada: f (xk ) − f (xk−1 ) f 0 (xk ) ≈ . xk ≈ xk−1 xk − xk−1 donde xk y xk−1 son dos estimativas de la raíz exacta ξ. tenemos |ek+1 | |f 00 (ck ) | lı́m = lı́m k→∞ |ek | k→∞ |2f 0 (xk ) | 1 |f 00 (lı́mk→∞ ck ) | 1 |f 00 (ξ) | 1 = 0 = 0 = |θ00 (ξ) | = β 2 |f (lı́mk→∞ xk ) | 2 |f (ξ) | 2 Por lo tanto.2. vemos que ¡ ¢0 00 (f 0 (x))2 (f 0 (x) f 00 (x) + f (x) f 000 (x)) − (f (x) f 00 (x)) (f 0 (x))2 θ (x) = (f 0 (x))4 de donde θ00 es continua en ξ y f 00 (ξ) θ00 (ξ) = f 0 (ξ) Llevando (2.7) e2k 2f 0 (xk ) Después de unos cálculos. el método de Newton tiene una tasa de convergencia cuadrática. Método Secante Uno de los inconvenientes en el método de Newton es el cálculo de la derivada de f en cada iteración. f 00 (ck ) e2k f (xk ) 0 = ek − 0 = ek+1 2f (xk ) f (xk ) de donde ek+1 f 00 (ck ) e2k = (2.
6 Experimente y compare los métodos estudiados en este capítulo. hallando una raíz de la ecuación f (x) = 0.6.5 En algún lenguaje de programación de su preferencia.. x0 y x1 . Figura 2. Ejercicio 2. Una interpretación gráfica puede ser vista en la figura 2.7 Experimente y compare los métodos estudiados en este capítulo.6: Método secante Laboratorio 2.3 Investigue la tasa de convergencia del método secante. Se deja al estudiante averiguar los detalles de la convergencia de este método. lamentablemente el precio que se paga por esto es la disminución en la tasa de convergencia. hallando una raíz de la ecuación f (x) = 0. 3. . que es súper-lineal.8 Sea x2 f (x) = + x (ln (x) − 1) 2 Halle sus puntos críticos (puntos donde f 0 (x) = 0) usando un método iterativo estudiado en este capítulo. f (xk ) − f (xk−1 ) Las condiciones para la convergencia del método secante son prácticamente las mismas que las del método de Newton. Problema 2. CEROS REALES DE FUNCIONES REALES O si lo prefiere.. dadas dos estimativas iniciales para la raíz ξ de la ecuación f (x) = 0. donde f (x) = ex − 4x2 Ejercicio 2. donde f (x) = x − x ln (x) Ejercicio 2. Compare sus resultados con los métodos anteriormente estudiados. 2. k = 1.26 CAPÍTULO 2. el método secante consiste en construir una sucesión definida por f (xk ) (xk − xk−1 ) xk+1 = xk − . Si bien la dificultad del cálculo explícito de la derivada fue evitada. implemente el méto- do secante y experiméntelo con diversos ejemplares. .
El método secante puede ser práctico cuando el cálculo de la derivada es complicado. 2.7. Los métodos de punto fijo generales son más rápidos. Figura 2.2. Cada método tiene sus ventajas y desventajas. La complejidad de los cálculos. sobre todo para la derivada. el inconveniente está en que el número de iteraciones puede ser grande. . tal como se muestra en la figura 2. los más importantes son: 1. Comparación de los Métodos Iterativos El esfuerzo computacional para la ejecución de cada uno de los métodos depende de varios factores. pero en contraparte exigen muchas hipótesis para la convergencia. Ejercicio 2.7: Problema de las vigas 2.3. 20]. pero requiere el cálculo de la derivada y demanda. El más rápido es el método de newton. Observe que su tasa de convergencia es lineal.9 Halle un punto donde la función f (x) = x2 + x3 ∗ (log(x) − 3) + 850 alcanza un mínimo sobre el intervalo [10. COMPARACIÓN DE LOS MÉTODOS ITERATIVOS 27 Ejercicio 2. El número total de iteraciones 3.10 Considere las dos vigas de 30 m y 20 m cruzándose a una altura de 8 m del suelo.3. Determine el ancho del pasadizo. al igual que los métodos de punto fijo. Condiciones para la convergencia El método de la bisección y el método de la posición falsa exigen pocas condiciones para garantizar la convergencia. H. hipótesis rigurosas. Se puede concluir que la elección del método más eficiente depende de la ecuación que se intenta resolver. pero no es tan rápido como el método de Newton.
sea insignificante cuando se aplica a la resolución de una ecuación. después de llevar al computador cada uno de estos métodos y experimentarlos con diversos ejemplares. donde la pérdida de una fracción de segundo retrasaría el desempeño del método en su conjunto. pues estos métodos deben verse como subrutinas de otros métodos iterativos más sofisticados. CEROS REALES DE FUNCIONES REALES Como un comentario adicional. entre un programa y otro. para otro tipo de problemas. probablemente el estudiante halle que las diferencias de tiempo de ejecución.28 CAPÍTULO 2. . y ese afán por buscar el método más rápido parecería no tener sentido. Esa percepción es equivocada.
  a x + a x m. . . un punto que satisface ambas ecua- ciones al mismo tiempo deberá estar en la intersección de ambas rectas (figura 3..n xn = bm 29 .1.. de acuerdo al tipo de solución 1 . Ninguna solución ½ 2x1 − 2x2 = 8 x1 − x2 = 5 Gráficamente. Para el caso de 3 variables.2 x2 = b1 a2. Soluciones infinitas ½ · ¸ · ¸ 3x1 − 3x2 = 15 x̄1 5+t =⇒ = .n xn = b2 .Capítulo 3 Resolución de Sistemas Lineales Sistemas de ecuaciones lineales surgen en diversas áreas.2 x2 + · · · + a2. .2 x2 + · · · + a1. t∈R x1 − x2 = 5 x̄2 t 3. 3. Para el caso n-dimensional. . Considere el siguiente sistema de ecuaciones lineales compuesto de dos ecuaciones y dos variables: ½ a1. .1). Solución única ½ · ¸ · ¸ 3x1 + 2x2 = 10 x̄1 4 =⇒ = x1 − x2 = 5 x̄2 −1 2. una de las más importantes tal vez sea en la investigación de operaciones...2 2 + · · · + am. . un sistema de m ecuaciones lineales y n variables es la formulación matemática siguiente:    a1. . el conjunto definido por cada ecuación se denomina hiperplano. cada ecuación representa un plano. . . . . un punto que satisface tres ecuaciones de un sistema simultáneamente estará en la intersección de tres planos. (3.1 x1 + a2.1 x1 + a2... . podemos notar lo siguiente: x̄2 1. ..2 x2 = b2 · ¸ x̄ En sistemas simples como éste. . .n xn = b1   a2.1)   .. Sistema General de Ecuaciones Lineales Para un caso general.1 1 m. .1 x1 + a1. cada ecuación representa a una recta.1 x1 + a1. .
.. . definidas por:       a1.  am. Desde el punto de vista de las columnas de A ∈ Rm×n . .1 a1.n        b2   x2  A =  . b =  . 3.   ..   .  ..1  a2.2 · · · a1.n b1 x1  a2..1.. El sistema lineal no posee soluciones En álgebra lineal se sabe que una matriz representa una transformación lineal.. y = Ax} Ejercicio 3. Note que Xn Ax = aj xj j=1 donde a representa la j-columna de A y xj es la j-componente del vector x ∈ Rn .30 CAPÍTULO 3. el mismo sistema puede ser visto por Ax = b donde A ∈ Rm×n . xn que permitan escribir b ∈ Rm como combinación lineal de las columnas de A.1 Muestre que Im (A) es un subespacio vectorial de Rm .2 · · · a2. . Luego..n bm xn Una solución para el sistema (3. Conjunto Imagen de una Matriz A Dada una matriz A ∈ Rm×n .  y x =  . definimos la imagen de A. En un sistema lineal puede suceder lo siguiente: 1. El sistema lineal tiene única solución 2. .  . .. denotado por Im (A)..2 · · · am. es decir: b = a1 x1 + . . j resolver el sistema Ax = b significa obtener escalares x1 . RESOLUCIÓN DE SISTEMAS LINEALES Figura 3.1 am. El sistema lineal posee infinitas soluciones 3.. como el conjunto: Im (A) = {y ∈ Rm : ∃x ∈ Rn .1: Representación gráfica de sistemas de ecuaciones lineales Usando la notación matricial.1) es un vector x ∈ Rn el cual satisface simultáneamente cada una de las m ecuaciones que conforman el sistema. + an xn La dimensión de A está determinada por el máximo número de columnas linealmente inde- pendientes de A..1.. b ∈ Rm y x ∈ Rn es el vector de las variables o incógnitas.
debido a que es muy frecuente que b 6∈ Im (A). que involucra el cálculo de n + 1 determinantes de orden n. infinitas soluc.1: Soluciones de un sistema de ecuaciones lineales 3. esta sucesión converge a la solución. deficiente b 6∈ Im (A) incompatible incompatible incompatible Cuadro 3.3. el sistema Ax = b tiene solución única. denotado por rango (A). puede pasar lo siguiente 1) Si b ∈ Im (A). Iterativos: Dada una aproximación inicial x0 . solución única b 6∈ Im (A) in c o m p a tib le Rango b ∈ Im (A) infinitas soluc. MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 31 Matriz A ∈ Rm×n m<n m=n m>n rango (A) = n rango (A) = m rango (A) = n Rango completo b ∈ Im (A) so lu ció n ú n ica infinitas soluc. bajo algunas hipótesis.2. En estas condi- ciones. el sistema no admite solución. infinitas soluc.2. 3. generan una secesión de vectores {xk }∞ k=0 . Si la solución existe. es definido por rango (A) = dim (Im (A)) Podemos destacar lo siguiente: 1. 2) Si b 6∈ Im (A). otorgan la solución exacta del sistema lineal después de un número finito de operaciones. aunque rango (A) = n. Métodos Directos En esta clase están métodos como el de la “Regla de Cramer”. b) Si rango (A) < n. Rango de una Matriz A El rango de la matriz A. En estas condiciones. Métodos para Resolver Sistemas de Ecuaciones Li- neales Los métodos numéricos para resolver sistemas de ecuaciones pueden ser de dos tipos: Directos: Si la solución existe. se dice que el sistema es compatible determinado. . El cuadro 3.1. En estas condiciones. excepto errores de redondeo.1.2. se dice que el sistema es incompatible.1 esquematiza las soluciones de un sistema de ecuaciones lineales. puede pasar lo siguiente: a) Si rango (A) = n.2. el sistema Ax = b admitirá infinitas soluciones. el sistema puede no tener solución. Si m > n. 3. Si m = n. se dice que el sistema es compatible indeterminado. 2.
. cuántos años se requiere para resolver el sistema usando un computador que realiza 2000000000 operaciones por segundo? Claramente.1 x1 + a1.j det (A [1.n xn = b0n 0 El beneficio de esto es que se puede resolver el sistema triangular (3. . .2 x2 + · · · + a02. el número total de multiplicaciones necesarias para resolverlo mediante la regla de Cramer es 21 × 20! × 19..3 Muestre que en un sistema de orden n = 20. a un sistema triangular superior:    a01. el cual acepta una solución única.32 CAPÍTULO 3.2 2 n. xn−3 . existen métodos exactos eficientes como los que veremos a continuación.2 x2 + · · · + a1. . Ejercicio 3.n xn = b2 .2 El determinante de una matriz real cuadrada de orden n está definido por Xn det (A) = (−1)j+1 A1. xn−1 puede ser obtenido mediante b0n−1 − a0n−1.. .   a x + a x + ··· + a x = b n.. mientras que A [i. Muestre que el número de multiplicaciones necesarias para hallar det (A) es aproximadamente n!.2).1 . .. .n−1 Y así sucesivamente se obtiene xn−2 . es así que de la última ecuación de (3..1 1 n. pues desde el punto de vista computacional. j]) j=1 donde A1.. Método de Gauss Dado el sistema lineal de n × n    a1. . (3. . (3.n xn x1 = a01. RESOLUCIÓN DE SISTEMAS LINEALES Ejercicio 3.1 x1 + a2.3) de modo eficiente. .. ..3)   . .n Luego. . Pero se debe advertir que este procedimiento tiene sólo un valor teórico. ..n xn xn−1 = a0n−1. . . métodos como el anterior deben estar fuera de nuestro interés. . Dado un sistema lineal Ax = b de orden n.2 x2 + · · · + a01.2)   . . ... debido a que por lo general se requiere resolver sistemas que involucran un gran número de variables y ecuaciones..2 x2 − a01.n xn = b01   a02..1 x1 + a01.3 x3 − · · · − a01. . para fines prácticos. ¿Considerando sólo multiplicaciones.j es el elemento en la i-fila y j-columna de la matriz A. de un modo equivalente. j] es la submatriz obtenida al eliminar la i-fila y la j-columna de A. En contraparte. .. . .   an.n xn = b02 .n n n El método de Eliminación de Gauss consiste en transformar el sistema (3. . La solución puede ser obtenida haciendo x = A−1 b.2 x2 + · · · + a2. . . x2 y finalmente b01 − a01. ..n xn = b1   a2.3) tenemos b0 xn = 0 n an. ese procedimiento es considerado costoso por el número de operaciones involucradas.
j = ai. .k /ak. n − 1 Para i = k + 1..4.. Adicionar un múltiplo de una ecuación a otra ecuación obtenemos un nuevo sistema Āx = b̄. . en un sistema triangular superior equivalente. .. Los valores de las variables xn .j bi = bi − mbk 1 Equivalente.. con elementos de A sobre la diagonal no nulos.k = 0 Para j = k + 1..1 y el al- goritmo planteado en el ejercicio 3.. . Algoritmo 3.j xj xk = (bk − s) /ak. n ai. el cual es equivalente1 al sistema original Ax = b. Suponga que el elemento ak. 1 s=0 Para j = (k + 1) .1 y el algoritmo planteado en el ejercicio 3.k 6= 0 al inicio de la etapa k: Para k = 1. Ejercicio 3.3..j − mak. Multiplicar una ecuación por una constante no nula 3.2 Dado el sistema lineal Ax = b de n × n.. Aplicando sobre las ecuaciones de este sistema una sucesión de operaciones elementales: 1. multiplicaciones.1.2. .k ai. La conversión de un sistema de orden n a un sistema equivalente..5 ¿Cuántas operaciones elementales (sumas. x1 son obtenidos mediante: xn = bn /an.4? Laboratorio 3... implementar el algoritmo 3. restas.. Conversión de un Sistema de Ecuaciones Lineales a uno Triangular Superior El siguiente algoritmo usa la eliminación de Gauss y convierte un sistema de ecuaciones lineales Ax = b.. el cual ya está en la forma triangular superior. divisiones y comparaciones) son necesarias para la ejecución del algoritmo 3.4 Análogamente al algoritmo 3. x2 . y triangular superior.1 (Resolución de un sistema triangular superior) Dado un sistema tri- angular superior Ax = b de orden n.k Ejercicio 3.n Para k = (n − 1) . . diseñar un algoritmo que resuelva un sistema triangular inferior de orden n. es posible en virtud al siguiente teorema del álgebra lineal: Teorema 3.. MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 33 Resolviendo un Sistema Triangular El siguiente algoritmo resuelve un sistema de ecuaciones lineales de orden n...1 Sea Ax = b un sistema de ecuaciones lineales. Cambiar dos ecuaciones 2... Algoritmo 3.1 En algún lenguaje de programación. xn−1 . en el sentido que tienen las mismas soluciones . n s = s + ak. n m = ai.
n.k . n − 1 ak.1 1016 m2. donde ai. lo que ocasionará impresiciones en los cálculos siguientes.k = .34 CAPÍTULO 3.k /ak.1. vemos que · ¸ · ¸ 5 5 Ax = 6= b = 8.. pues el computador trabaja con precisión finita. escoger como pivote el elemento de k−1 k−1 mayor módulo entre los coeficientes: ai.1 El número ai. n. .2 y 3. Estrategia con pivotamiento total Estrategia con Pivotamiento Parcial Consiste en lo siguiente: En el inicio de la etapa k de la eliminación gaussiana.26691434300103 × 10−16 x= 2. k)-multiplicador de la matriz A.k introducido en el algoritmo 3..1 = 11.. Ejemplo 3.k mi.2.k 6= 0 en cada iteración.k . Observe que en estas condiciones.5 Al verificar si realmente es solución.1 (Sistema mal condicionado) Utilice algún lenguaje de programación para resolver. . k = 1. k)-componente en la iteración k − 1.5x2 = 9 Después de aplicar consecutivamente los algoritmos.k representa la (i.1 = = a1. .. es muy pequeño.1 = 1016 .. cuando comparado con A2. pues se necesita que ak.. 2 La matriz A tiende a ser no inversible en la práctica. obtuvimos como solución: · ¸ 7.1 11 es muy grande. usando los algoritmos 3. . si fuera necesario. Permutar la fila k e i. lo que puede ocasionar a su vez el mal condicionamiento2 del problema. Estrategia con pivotamiento parcial 2. Definición 3. i = 2. para i = k. el siguiente sistema de ecuaciones: ½ 11x1 + 2x2 = 5 1016 x1 + 0. Pero el simple hecho que ak. el multiplicador a2.. aunque en teoría lo sea..51691434300102 9 Este fenómeno se debe a que el pivote A1. lo denominaremos (i. k + 1.k sea pequeño puede ocasionar que el mul- tiplicador m tome valores inmensamente grandes.. RESOLUCIÓN DE SISTEMAS LINEALES Un inconveniente es el cálculo del multiplicador m = ai. Algunas de las estrategias para evitar este inconveniente son: 1.
1 1 · · · 0    L =  .. En contraste al pivoteamiento parcial. su uso no es cómun en la práctica pues requiere mucho esfuerzo computacional. la estrategia de pivoteamiento completo analiza toda matriz. existe otra estrategia denominada estrategia con pivoteamiento completo. Resolución de Sistemas de Ecuaciones Lineales Mediante la Descomposición LU Esta estrategia consiste en descomponer la matriz A como el producto de dos matrices factores: A = LU .2 · · · 1 . . .1 n..3.2 | = |a13. es decir.2 = =− −3 3 Así. Problema 3. . lo que evita la propagación de errores de redondeo.2 Considere un sistema de orden n. de donde obtenemos   3 2 1 −1 5 £ (1) (1) ¤ 0 −3 −5 7 7 A b =0 1  0 3 6 0 2 4 0 15 Observe que en este caso los multiplicadores respectivos serán: 1 1 m3. La estrategia con pivoteamiento parcial no elimina del todo los inconvenientes causados por el mal condicionamiento. . es decir   1 0 ··· 0  2. A pesar que en teoría esto elimina definitivamente las imprecisiones numéricas que puedan ocurrir.1 Investigue la estrategia de pivoteamiento completo. se consigue que los multiplicadores m. donde n = 4 y la iteración k = 2. Ahora.2 = =− −3 3 2 2 m4.  n. donde L es una matriz triangular inferior con unos sobre su diagonal. Cambiamos las líneas 2 y 3.2. . al escoger el mayor elemento en módulo entre los candidatos a pivote. MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 35 Ejemplo 3. .3. estén entre cero y uno. entonces el pivote es −3 2.   . Escoger el pivote: máxj=2.4 |a1j. que busca el mejor pivote en una porción de cada columna en cada iteración.. Observe que   3 2 1 −1 5 £ (1) (1) ¤ 0 1 0 3 6 A b =0 −3 −5 7  7 0 2 4 0 15 £ (1) (1) ¤ Note que A b representa la situación del sistema en la primera iteración. requiere muchas operaciones elementales (comparaciones) para su ejecución. en módulo.2 | = 3. . para el inicio de la segunda iteración 1.
n De ese modo.2 a03.2 · · · u2.2 a11.3 .2 a2.j = a01. bastaría resolver consecutivamente los sistemas triangulares: Ly = b Ux = y (3.1 = a02.1 a11.1 a03. RESOLUCIÓN DE SISTEMAS LINEALES y U es una matriz triangular superior   u1.   .1 a2.4) y (3.2 a12.3  0  A0 =  0 0   a2. 3..3  = A a03.1 a01. .1 a01. Ly = b 2.1 u1.1 /a01.5). Ux = y Una de las principales ventajas que tiene resolver sistemas mediante este método.4) y Ly = b0 Ux = y (3.. está basado en los multiplicadores mi.. es la siguiente: supongamos que se quiere resolver los sistemas Ax = b y Ax = b0 . .2 a01. 2. Supongamos que tenemos la matriz   a01. es equivalente a resolver consecuti- vamente: 1.1 = a03.n    U = .3 Primera iteración: Los respectivos multiplicadores están dados por m2.j i = 2.2 a3. los cuales son fáciles de resolver usando el algoritmo 3. una vez obtenidos tales factores L y U . Cálculo de los Factores L y U El cálculo de las matrices L y U de modo que A = LU. .1 para sistemas triangulares superiores.j introducidos en la eliminación gaussiana (definión 3.j − mi.n  0 u2. 3 y obtenemos   a11. j = 1.3   A1 =   0 a12. 3 a1i. hacemos a11.j = a0i. o sino LUx = b.1 /a01.2 · · · u1..1 para deshacernos de la variable x1 en las i-filas.5) Observe que los mismos factores L y U fueron usandos para resolver los sistemas (3. resolver el sistema Ax = b.  0 0 · · · un. 2.3   1 1 0 a3. ..j j = 1. . en con- traste con el método de Gauss.1 m3.1). para i = 2.36 CAPÍTULO 3. 3.
2 a12. donde   1 0 0 M 0 =  −m2.1 1 0  −m3.2 a22. calculamos el multiplicador m3.2.3 Observe que A2 = M 1 A1 donde   1 0 0 M1 =  0 1 0  0 −m3.j − m3.2 1      1 0 0 1 0 0 1 0 0 =  m2. 2. 3 a22.1 m3.3   0 0 a23.1 1 0   0 1 0  =  m2.j j = 1.j = = a13.2 = a13. 2. 3 a23.1 0 1 Segunda iteración: Para eliminar x2 de las restantes líneas. MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 37 Observe que A1 = M 0 A0 .1 0 1 0 m3.3.2 a21.2 1 de modo que A = LU.j = a12.j j = 2. 3 y obtenemos   a21. ¡ ¢−1 ¡ ¢−1 ¡ 1 ¢−1 A = M 1M 0 U = M0 M U y como  −1  −1 ¡ 0 ¢−1 ¡ 1 ¢−1 1 0 0 1 0 0 M M =  −m2.2 y hacemos a21.2 1 m3. .j j = 1.2 1 concluimos que la matriz triangular inferior debería ser   1 0 0 L =  m2. A2 es triangular superior y podemos definir U = A2 .1 1 0   0 1 0  −m3.j = a11.1 a21. Luego: ¡ ¢ ¡ ¢ ¡ ¢ U = M 1 A1 = M 1 M 0 A0 = M 1 M 0 A0 = M 1 M 0 A Es decir.3   A2 =   0 a22.1 1 0  m3.1 m3.2 1 Además.1 1 0  m3.1 0 1 0 −m3.2 /a12.
.2.1 1 0  A2 =  2 1 0   0 1 −7  = LU −1 2 1 m3. Suponga que det (Ak ) 6= 0 para k = 1.1 y el ejercicio 3.j ] tales que A = LU . es la descomposi- ción de Cholesky. A2 =  0 1 −7  0 0 32 Por lo tanto. y una única matriz triangular superior U = [ui. existe una única matriz triangular inferior L = [mi.un.6 Investigue la demostración del teorema 3. n. n−1. Ejercicio 3..4 para resolver sistemas triangulares. para i = 1..2 = 4.. A1 =  0 1 −7  0 4 4 y   1 2 3 m3.i = 1.. sobre todo en optimización.. Definición 3. Además.1 = −1.. det (A) = u1. sea la matriz Ak constituida de las primeras k líneas y k columnas de A. si xt Ax > 0.   1 2 3 m2. RESOLUCIÓN DE SISTEMAS LINEALES Teorema 3.2 (Matriz definida positiva) Se dice que una matriz A ∈ Rn×n simétrica y de orden n es definida positiva.3 Resolver el siguiente sistema de ecuaciones lineales utilizando la descomposición LU.2 1 −1 4 1 0 0 32 Puesto que Ax = b lo podemos expresar como (LU) x = b. Entonces.j ].1 u2. calculamos consecutivamente:   10 Ly = b =⇒ y =  0  16 y  3/2 Ux = y =⇒ x =  7/2  1/2 Descomposición de Cholesky Una estrategia que tiene suma importancia.n . . para todo x ∈ Rn y x 6= 0.1 = 2. con mi. Ejemplo 3.1 m3. m3..2 . .        1 2 3 1 0 0 1 0 0 1 2 3 A =  2 5 −1  =  m2.2 Dada una matriz cuadrada A de orden n. x1 + 2x2 + 3x3 = 10 2x1 + 5x2 − x3 = 20 −x1 + 2x2 + x3 = 6 Observe que     1 2 3 10 A =  2 5 −1  y b =  20  −1 2 1 6 Luego.38 CAPÍTULO 3. usando el algoritmo 3. .
1 gn..  .   .. .2 j = 3.n El factor G será obtenido de la ecuación matricial:      a1..1   g2.1 La columna 2:       a1. .n    A =  .n g1. tal que A = GGt Ejercicio 3.1 Como gj.. .1 = para j = 2.. .1 a2.   .2 =⇒ g2.2 · · ·  g2.2 =⇒ g1.1  a2. .2 · · · gn...7 Investigue la demostración del teorema 3. = .1 an. .1 + g3.2 · · · a2.1 + gn.n gn.  .   .1 g1.1 gn..1 a1.  an.2 = g2. .   . .n  a2.1          ..1 g2...1 g2.1 0 · · · 0    2 2     g2.   .2   g2.3.1 a2.1  a2.1 g1.1 = a1.  an. .1 0 · · · 0 g1. .2   a3.  . .1 g1. n g1.2  a2. .2 · · · gn.2        .2 0 gn...n   g2.  gn.. . . ..2 g1..n 0 0 · · · gn.1 g1.  . ..1 g1. n . = ..2   0       =  .2 · · · a1.  =  ..1 a1. ...  an. entonces existe una única matriz triangular inferior de orden n y con diagonal positiva.1 g2.2 · · · 0  0 g2. . .3. ..2 · · · gn..1 + g2.1 · · · gn.. ..2 = a2. .1 g1. .2 · · · gn.2 − g2.1 + gj.2 g2..   . MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 39 Teorema 3. Cálculo del factor de Cholesky Dada una matriz simétrica y definida positiva:   a1..1 g1.2 g2. .1 g2. .   .2 · · · 0  0   g2.2 de donde a1..2   .1 gn..n an.3 (Descomposición de Cholesky) Si A es una matriz de orden n...n La columna 1:        a1. simétrica y definida positiva...2 · · · an.. .   ..2 · · · a1.1 + g2. .1 y gj.1 g2. .  0 = g3.   . .1 = g1.   .2 g2. .n 0 gn... .2.   .1 0 · · · 0 g1.1 g2.1 gn. .2 g1..2   g1.2 · · · a2.2 · · · an.2  g1. .1 luego √ aj.1 = a1.1 an. .1 g2.2 = aj..2 = a2.2 g1. .1 q 2 2 2 g2.  .
k = r Para i = k + 1.  g1. .1 g2.k gk+1...k Por lo general. ... n... Para k = 1. ya fueron calculados. . Si en (*) se tiene que r ≤ 0..  an.. k − 1 suma = suma + gi.1 ) gj..k gk..k = ak.1 0 · · · 0  .... .k de donde Ã !1/2 X k−1 2 gk.k k = 2.... .k j = k + 1. i = 1. entonces la descomposición no .1  ak.k = gk.      .k = j = k + 1.k     ...2 + · · · + gj.1 + gk.i k....1 gk.. entonces (aj.k√− suma .. ..k   0   . n gk..       ak.i gj.   .2 − gj..k − suma) /gk. podemos usar el algoritmo de Cholesky para verificar si A es definida positiva.2 Columna k: Los elementos de la columna k de G son: £ ¤t 0 · · · 0 gk..k = (ai. n y como los elementos gi.. n suma = 0..k − k−1 g g i=1 j.k 0 tenemos 2 2 2 ak.(*) gk. Sin embargo. . ya fueron calculados. k − 1.. .k = gj.n  .2  .k Algoritmo 3.1 g2.2 gk.  gn.1 .k  =  .k . ver si una matriz simétrica es definida positiva usando la definición es una tarea prácticamente imposible. .. tenemos ³ P ´ aj. (k − 1) 2 suma = suma + gk.....j gi.j i=1 Y como aj. n g2.. j = 1. RESOLUCIÓN DE SISTEMAS LINEALES y los gj..1 gn.   gk.2     gk. .. . ..2 + · · · + gk. n suma = 0 Para j = 1..k · · · gn.40 CAPÍTULO 3. .k − gk...1 gk..1 + gj.   . .2 · · · 0  ..3 Sea A una matriz simétrica y definida positiva. ... n haciendo     ak. .2 · · · gn.j gk.. Para j = 1.j r = ak.   g2....    ak+1.2 = j = 3.
si xt Ax ≥ 0. . MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 41 es posible y A no es definida positiva. es posible resolver el sistema lineal asociado: Ax = b. Este número es aproximadamente la mitad del número de operaciones necesarias para la realización de la eliminación en la descomposición LU. del siguiente modo: como ¡ ¢ Ax = b ⇐⇒ GGt x = 0 entonces 1. Resolver Gy = b 2. pues ¡ ¢t ¡ ¢t C t = BtB = Bt Bt = BtB = C y ¡ ¢ xt Cx = xt B t B x = (Bx)t (Bx) = kBxk2 ≥ 0 donde k·k es la norma euclídea. ¿podría ser definida positiva una matriz la cual tiene algunas componentes negativas? Verifique si la matriz   27 12 10 24  12 9 16 11     10 16 42 −2  24 11 −2 137 es o no definida positiva (use el algoritmo). Lo recíproco no siempre es válido.11 Probar que. Ejercicio 3.10 Una matriz simétrica A ∈ Rn×n se llama semidefinida positiva. de un contraejemplo. Resolver Gt x = y Laboratorio 3. Probar que. solución: Observe que C ∈ Rm×m es simétrica. Caso contrario. devuelva la matriz triangular inferior G. implemente el algo- ritmo de Cholesky. Caso contrario. una vez conocido A = GGt .9 Una duda común es. Ejercicio 3. la matriz C = B t B es semidefinida positiva. el algoritmo otorga la matriz triangular inferior G tal que A = GGt . de modo que: cuando la matriz A sea definida positiva. verifique que la matriz   27 12 10 24  12 9 16 29     10 16 42 70  24 29 70 137 es realmente definida positiva. pues requería n3 /3. La descomposición de Cholesky requiere alrededor de n3 /6 operaciones de multiplicación para la descomposición.2. Ejercicio 3.8 Usando el algoritmo de Cholesky. si A ∈ Rn×n es definida positiva. Ejercicio 3. debería emitir un mensaje anunciando que A no es definida positiva. entonces A es inversible.3. Al igual que la descomposición LU. para todo x ∈ Rn .2 En algún lenguaje de programación de su preferencia. para cualquier matriz B ∈ Rm×n .
.n /a2..   .1 x1 + a2. ..1 x1  x2   b2 /a2.n −an. respectivamente: 1 x1 = (b1 − a1..n · · · 0 xn ..n xn ) a1.3 x3 − .2.6) donde A ∈ Rn×n y b ∈ Rn . n. . 1 xn = (bn − an. .n xn = bn Suponiendo que ai. Dado el sistema lineal de ecuaciones Ax = b (3. Así.1 1 x2 = (b2 − a2.7) donde D ∈ Rn×n y d ∈ Rn . .1 /a2.1 /an..6) en una ecuación matricial equivalente: x = Dx + d (3.  .2 · · · −a2.3 x3 − . ...1 x1 + a1. .1 x1 − an.2  x2          . .1 0 −a1.1 x1 + an.2   −a2. . x∗ debería ser también la solución del sistema original Ax = b.1 −a1. del siguiente modo: Sea el sistema original a1.. Métodos Iterativos La idea de los métodos iterativos para resolver sistemas de ecuaciones está inspirada en el método de punto fijo. despejamos las variables x1 .n −an. . ..   . ..n xn = b2 . . − a1.. xn de las n ecuaciones.. los métodos de este tipo construyen una sucesión {xk ∈ Rn }∞ k=0 definida por la regla xk+1 = θ (xk ) = Dxk + d Observe que.. an.. . . ..2 x2 + · · · + a2.  .2 x2 − a1.2 x2 + · · · + an.. + . .2..n /a1..1 x2 − a2.1 · · · −a1. .2 x2 + · · · + a1. Bajo ciertas condiciones. . ..n De esta forma tenemos        x1 b1 /a1.2 x2 − ....2 /a1. si lı́mk→∞ xk = x∗ .3 /a1.2 ..n xn = b1 a2.3 /a2.n −an. − a2.. . Los métodos iterativos consisten en expresar el sistema (3.n xn ) a2.  xn bn /an. .n−1 xn−1 ) an.2 /an.... . .i 6= 0 para i = 1..   . RESOLUCIÓN DE SISTEMAS LINEALES 3.42 CAPÍTULO 3. .  =  .3 /an. . entonces x∗ es un punto fijo de θ. . .2 0 −a2. Método de Gauss-Jacobi Este método se caracteriza por transformar el sistema Ax = b a la forma x = Dx + d. − an. Note que en este caso θ (x) = Dx + d es una función iteración n-dimensional. ..
a diferencia de los métodos directos...2 · · · −a2..1 xk2 − a2.por medio de la relación recursiva xk+1 = Dxk + d donde D y d están definidos en este caso por (3.1 /a2. 1 ¡ ¢ xk+1 n = bn − an. sea Pn j=1j6=i |ai. obtener x1 .. la cual converge a la solución del sistema lineal Ax = b.n · · · 0 bn /an..n xkn (3..2 xk2 − .n Una característica de los métodos iterativos.3.. no- tará que para operar el método de Gauss-Jacobi.3 /an.2 /an. sólo necesitamos almacenar en memoria la matriz A y el vector b. . .8)  .2   b2 /a2. el resto de cálculos no requieren la construcción de matrices auxiliares como en el método directo basado en la descomposición LU.3. .  y d= ..9) a2. − an.2. Criterio de convergencia para el método de Gauss-Jacobi Dado el sistema lineal Ax = b. una aproximación inicial a la solución del sistema lineal Ax = b. pues debemos tener en cuenta los errores de cál- culo del sistema de cómputo y el mal condicionamiento del sistema. .n −an.n El método de Gauss-Jacobi consiste en lo siguiente: dado x0 .1  −a2.2 xk2 − a1. encuentran la solu- ción exacta de cualquier sistema de ecuaciones..3 xk3 − .. independientemente de la elección del vector inicial x0 .3 xk3 − .3 /a1. 3...2 . .2 0 −a2. Es- to último parece tornarlos poco atractivos en la práctica.3 /a2. entonces el método de Gauss-Jacobi genera una sucesión de vectores xk k=0 .1 −a1.. .n−1 xkn−1 an.j | αi = y α = máx {αi } |ai. MÉTODOS PARA RESOLVER SISTEMAS DE ECUACIONES LINEALES 43 Es decir. . x2 .  −an.i | 1≤i≤n © ª∞ Si α < 1. − a2.. los métodos iterativos apenas convergen cuando son satisfechos algunos requerimientos. la función iteración quedaría establecido por x = θ (x) = Dx + d donde     0 −a1.n −an. .. .. .1 1 ¡ ¢ xk+1 2 = b2 − a2.8). En la práctica no es bien cierto esta última aformación. es que sólo convergen si algunas hipótesis son satisfechas.2      D= .n /a2. teóricamente.n xkn a1.   . pero debemos tener en cuenta el espacio requerido en memoria-computador.2 /a1.1 xk1 − an. desde que ésta exista.1 · · · −a1.1 b1 /a1.2.9). .1 /an..n /a1.. O sino: 1 ¡ ¢ xk+1 1 = b1 − a1.. − a1. observe por ejemplo la ecuación (3. xk .  (3. Por otro lado. Comparación entre Métodos Directos e Iterativos Convergencia: Los métodos directos son procesos finitos y.
en la triangularización hecha por el método de Gauss.2 Investigue la prueba del criterio de convergencia del método de Gauss-Jacobi. . adicionalmante a los errores cometidos por un sistema de cómputo. Problema 3. por ejemplo. los datos del problema original son alterados y la solución no es precisa desde un punto de vista computacional. Por otro lado.3 Investigue sobre el método iterativo de Gauss-Seidel. los métodos iterativos no modifican el sistema original y. RESOLUCIÓN DE SISTEMAS LINEALES Errores de redondeo: Métodos directos modifican el sistema original. los errores numéricos son menores a los cometidos por los métodos directos. Problema 3.44 CAPÍTULO 3. una vez asegurada la convergencia.
Este método es iterativo y.1) 6x1 + 2x2 − x3 + 34 = 0 Resolver problemas de este tipo no es un asunto fácil. sobre todo cuando el sistema en cuestión es de gran dimensión. se dice que el método tiene la propiedad de convergencia local. 3.2) f3 (x) = 0 donde fi : R3 7−→ R.3) es la forma en que nosotros identificaremos un sistema de ecuaciones no 45 .1) puede ser visto a su vez como F (x) = 0 (4. entonces el sistema de ecuaciones (4. tal requerimiento es muy discriminatorio y frecuentemente el método converge inclusive cuando el punto inicial está distante de la solución. i = 1. Observe que el sistema (4. 2. Un ejemplo de un sistema de 3 ecuaciones no lineales con 3 incógnitas es una expresión matemática de la siguiente forma 7x1 x2 + 5x2 − x23 sen x1 − 12 = 0 −x41 + cos2 x2 + 2x33 − 8 = 0 (4. en su versión básica. Si definimos   f1 (x) F (x) = f1 (x) f3 (x) donde F : R3 7−→ R3 . Cuando esto sucede. converge a una solución ξ del sistema sólo cuando el punto inicial x0 es tomado lo suficientemente próximo de ξ.1) puede ser representado por: f1 (x) = 0 f2 (x) = 0 (4.3) La ecuación (4.Capítulo 4 Introducción a Sistemas No Lineales En este capítulo revisaremos brevemente el clásico Método de Newton para resolver sis- temas de ecuaciones no lineales.
donde ε > 0 es una precisión deseada y k·k es alguna norma en Rn .    .. 1. 3.6) x1 = x0 + d0 (4. una iteración Newton consiste en calcular x1 previamente conocido x0 . es posible calcular x1 . 3. . sea x0 ∈ Rn una aproximación inicial a una solu- ción del sistema (problema difícil) F (x) = 0 definido en (4. . . k = 0. 2... .7) es que una vez conocido el paso de newton d0 . para todo x en una vecindad de x0 . n. (4. i.   . . si tomamos una función L0 tal que L0 (x) ≈ F (x).5) tiene solución única: x1 = x0 − J −1 (x0 )F (x0 ) Visto de otro modo. 4. Con esto. . INTRODUCCIÓN A SISTEMAS NO LINEALES lineal.5) Si J (x0 ) es inversible..7) Lo que dice (4. . podemos utilizar x1 como nuevo punto ° inicial 2 ¡ k ¢° y calcular x y repetir este procedimiento para k = 0.3). mediante la siguiente regla: xk+1 = xk − J −1 (xk )F (xk ). .8) ° ¡ ¢° hasta que °F xk ° < ε. denotado por F 0 (x) o J (x). entonces esperamos que la solución del sistema L0 (x) = 0 (problema fácil) sea una mejor aproximación que x0 para una solución de F (x) = 0.1. hasta que se cumpla °F x ° < ε.  ∂fn ∂fn ∂fn ∂x1 (x) ∂x2 (x) · · · ∂xn (x) ∂fi donde ∂x j : Rn 7→ R. está definido por  ∂f ∂f1 ∂f1  ∂x 1 (x) ∂x2 (x) · · · ∂xn (x)  1   ∂f2 (x) ∂f2 (x) · · · ∂f2 (x)  ∂x1 ∂x2 ∂xn  J(x) = F 0 (x) =   . son derivadas parciales y las asumiremos como funciones continuas en Rn . .. . entonces (4.4) El próximo punto. Así. es definido como la solución de L0 (x) = 0 (4.. el método de Newton puede ser visto del siguiente modo: calcular xk+1 una vez conocido xk .1 De un modo más directo. El método de Newton es de carácter iterativo y está basado en la aproximación lineal (según Taylor) de la función F en torno al punto actual x0 : L0 (x) = F (x0 ) + J(x0 )(x − x0 ) (4. .. Observación 4. j = 1. 2.. . El Método de Newton El método de Newton consiste en resolver un problema difícil mediante sucesivas resolu- ciones de un problema fácil. 1. El jacobiano de F en el punto x. x1 . se espera que cada solución del problema fácil sea una mejor aproximación para el problema difícil.46 CAPÍTULO 4. mediante la resolución consecutiva del sistema lineal: J(x0 )d0 = −F (x0 ) (4.
1 (Algoritmo Básico de Newton) Sea x0 ∈ Rn un punto inicial lo suficientemente cerca de la solución y ε > 0 el parámetro de precisión deseado: ° ° Paso 1: Si °F (xk )° < ε.. ir al paso 2.6) podrían usarse técnicas más baratas para resolver el sistema sin tener que calcular explícitamente J −1 (xk ). El siguiente algoritmo resume el método.23134959407946 x13 = −1.1 Consideremos el siguiente sistema de ecuaciones no lineales de 3 incógnitas y 3 ecuaciones: 7x1 x2 + 5x2 − x23 sen x1 − 12 = 0 −x41 + cos2 x2 + 2x33 − 8 = 0 (4. En conclusión. donde k·k es la norma euclídea.1 para que finalice después de un número determinado de iteraciones indicando la posibilidad de infactibilidad. Ir al paso 3. o la de Cholesky si J(xk ) es definida positiva. en (4. Paso 2: Resolver el sistema J(xk )dk = −F (xk ) y obtener el paso de newton dk . detenerse. donde F : Rn 7−→ Rn tiene funciones componentes fi . Caso contrario.8) debería ser evitado para fines computa- cionales. obtener xk+1 directamente desde (4. EL MÉTODO DE NEWTON 47 En realidad. Algoritmo 4. .. Esto indica que x13 es una buena aproximación para una raíz de F (x) = 0. una alternativa sería usar la el método de Gauss. Por otro lado. n. i = 1. la descomposición LU.1.9) 6x1 + 2x2 − x3 + 34 = 0 Observe que   7x1 x2 + 5x2 − x23 sen x1 − 12 F (x) =  −x41 + cos2 x2 + 2x33 − 8  6x1 + 2x2 − x3 + 34 y   7x2 − x23 cos x1 7x1 + 5 −2x3 sen x1 J(x) =  −4x31 −2 cos x2 sen x2 6x23  6 2 −1   10 Si usamos como punto inicial x = 20  y como parámetro de precisión ε = 10−9 . Ejemplo 4. . el sistema F (x) = 0 puede no tener solución.47684281234392 Es fácil verificar que kF (x13 )k ≈ 5.. el método de Newton es aplicado originalmente para resolver un sistema de ecuaciones F (x) = 0.4. las cuales admiten derivadas parciales continuas en Rn . xk es la aproximación buscada. Paso 3: Calcular xk+1 = xk + dk . entonces es posible modificar el algoritmo 4. ya que calcular J −1 (xk ) es considerado costoso.293308530720633 × 10−8 . Volver al paso 1. hacer k ←− k + 1. Naturalmente. una 0  −50 implementación computacional básica nos otorga:   −4.56752981158965 5.
Laboratorio 4. Esa tarea puede a veces ser considerada un inconveniente debido al esfuerzo de cálculo y al probable error humano. donde 1 f (x) = a + bt x + xt Qx 2 n×n donde Q ∈ R es simétrica y definida positiva. Laboratorio 4.9). Los detalles sobre este tema no serán tratados en este curso.10) Además de usar el método de Newton para resolver (4. . Encuentre un punto crítico de f .10). ¿Este punto es uno donde f alcanza un mínimo? ¿Por qué? Ejercicio 4.. una alternativa sería usar una aproximación mediante diferencias finitas.2 Conocer J(xk ) presupone el cálculo y evaluación de las primeras derivadas parciales de las funciones fi (xk ). . b ∈ Rn ¿Cuántas iteraciones debería hacer el método de Newton? ¿Por qué? Ejercicio 4. para i = 1.. entonces el método de Newton converge y lo hace con una tasa de convergencia cuadrática. donde f (x) = 1 2 kAx − bk2 y la norma es la euclídea.2 Al aplicar el método de Newton para resolver un sistema F (x) = 0. Ejercicio 4. Ejercicio 4. para caracterizar este hecho uno utiliza la siguiente expresión: el método de Newton tiene la propiedade de convergencia local. el cual resolvía sistemas de una ecuación con una variable. n.1.1.4 Sean     1 2 5 10  2 8 25   200       5 7 8   7  A=   y b=   1 2 3    6    3 5 9   12  6 7 1 15 Resolver 1 Minimizar kAx − bk2 2 x ∈ Rn Sugerencia: Basta hallar un punto crítico de f : Rn 7→ R. b ∈ Rn y a ∈ R. Frecuentemente.48 CAPÍTULO 4.. INTRODUCCIÓN A SISTEMAS NO LINEALES 4.1 Hallar dos raíces más del sistema no lineal dado en (4. A ∈ Rn×n . si el punto inicial x0 ∈ Rn es elegido lo sificientemente cerca de la solución del sistema F (x) = 0. un procedimiento analítico que debemos hacer siempre que sea posible.3 Sea f : Rn 7→ R una función cuyas derivadas parciales son continuas en Rn . resuelva ∇f (x) = 0. realice una función que ejecute el Algoritmo de Newton. Convergencia y Rapidez del Método de Newton El método de Newton para sistemas n-dimensionales posee propiedades similares al método estudiado con más detalle en el capítulo 2. donde F (x) = Ax − b. Observe que ∇f (x) = At Ax − At b (4. Resultados teóricos muestran que. es decir. use también un método directo para sistemas de ecuaciones lineales y compare sus resultados.1 En algún lenguaje de programación de su prefrencia.
(2. 3. Interpolación Interpolar una función consiste en aproximar una función f por otra función g. 3.44) . La función g es entonces usada en reemplazo de f . nos permite encontrar funciones que representen estos datos. x1 .47) . El precio del dólar en el tiempo t = 3. ci ) representa el precio del dólar ci (soles) en el tiempo ti (horas). La forma de interpolación de f que veremos a seguir consiste en 49 ..39) . resultados de observaciones: (0. escogida dentro de una clase definida de antemano y satisfaciendo algunas propiedades. La hora en que el precio del dólar esté en 3.3. . (4..465 soles El estudio de la interpolación y aproximación además de responder a estos requerimientos.49) . (6.. xn y los valores respectivos de f en esos puntos: f (x0 ) . Considere n + 1 puntos distintos: x0 .44 3.56) donde el par (ti . 3.46 3. 5. pero algunas también resultan de simples observaciones. esto a su vez nos permitirá menejar matemáticamente un problema que consistía de apenas algunos datos.3.39 3. lo primero que viene a nuestra mente es la siguiente pregunta ¿de dónde salió esa función? Algunas de estas funciones se obtienen de la solución de una ecuación diferencial que representa algún fenómeno físico. . (8.47 3. Suponga que disponemos de los siguientes datos. (9.. Estos datos pueden ser organizados del siguiente modo ti 0 1 2 3 4 5 6 7 8 9 ci 3.42) . (5.45) .48) . 3. f (xn ). 3.. (1.5 h 2. (7.1.42 3.5 3. estas funciones frecuentemente son continuas y hasta diferenciables.3. 3.49 3. 3.48 3. (3.46) . f (x1 ) .Capítulo 5 Interpolación y Aproximación Es frecuente encontrar en libros de cálculo elemental funciones representando el compor- tamiento de algún hecho real.45 3.5) ..56 Supóngase que se quiere calcular: 1.
tal que f (xk ) = p (xk ) .. n (5.. INTERPOLACIÓN Y APROXIMACIÓN determinar una función g tal que g (x0 ) = f (x0 ) g (x1 ) = f (x1 ) . al encontrar los valores an . p (xn ) = an xnn + an−1 xn−1 n + .... a0 conoceremos al polinomio pn . note que las variables son an . g (xn ) = f (xn ) Una manera práctica y muy utilizada es considerar la función interpolante g como un poli- nomio. Figura 5. . Usando la condi- ción (5.. an−1 . podemos preguntarnos ahora: ¿existe siempre un polinomio que satisface tales condiciones?. etc. g puede ser una función racional... .1.1) Naturalmente.. + a1 xn + a0 = f (xn ) .1.. + a1 x1 + a0 = f (x1 ) ... No obstante. ¿el polinomio es único? Para responder a esto. queremos aproximar f por un polinomio pn de grado menor o igual a n. trigonométrica.. representemos el polinomio p por p (x) = an xn + an−1 xn−1 + . .. (x1 .1: La función g interpolando f en 6 puntos 5.. (xn . f (x0 )) .. . a1 ..1 se muestra un ejemplo para el caso n = 5.. . y si existe. + a1 x + a0 Así. f (x1 )) . + a1 x0 + a0 = f (x0 ) n n−1 p (x1 ) = an x1 + an−1 x1 + .. 1. an−1 . a0 : p (x0 ) = an xn0 + an−1 xn−1 0 + .1) formamos el siguiente sistema lineal con n + 1 ecuaciones y n + 1 variables. ... k = 0. Interpolación Polinomial Dados n + 1 pares (x0 . f (xn )). En la figura 5..50 CAPÍTULO 5. a1 .
.2)..   . . pero la elección de una u otra depende de algunos factores. . 5. si x0 .. en consecuencia. .  y b= . pro- cedemos a ver las maneras cómo encontrarlo.. tales como la dificultad de los cálculos.  n n−1 xn xn · · · xn 1 a0 f (xn ) Note que α es el vector de incógnitas. x1 . 1.. j = 0. usando un polinomio p3 (x) = a3 x3 + a2 x2 + a1 x + a0 y los siguientes datos: xi −2 0 1 4 f (xi ) 6 4 5 8 Podemos calcular la matriz de Vandermonde directamente. Esto constituye la prueba del siguiente teorema.1. x2 = 1 y x3 = 4. la primera es mediante la solución directa del sistema lineal Aα = b. . y por lo tanto.5. Desde un punto de vista teórico. k 6= j. . el sistema lineal (5. No obstante. como la de Lagrange y de Newton.. INTERPOLACIÓN 51 Observe que el sistema anterior es de la forma Aα = b (5.   . Existen varias formas de realizar esta tarea.1 Existe un único polinomio pn de grado menor o igual a n. .1. x1 = 0.   . estabilidad del sistema lineal y tiempo de ejecución. Teorema 5.2. . . todas ellas llevan al mismo polinomio.. Modos de Obtener el Polinomio pn Una vez que sabemos las condiciones que garantizan la existencia y unicidad de pn . Obtención de pn Mediante la Resolución del Sistema Aα = b Consiste en resolver por algún método. Ejemplo 5. .. α= .1 Vamos a interpolar f en los puntos x0 = −2..2) tiene solución y ésta es única. directo o iterativo. tal que f (xk ) = pn (xk ) ..j≤n Esto significa que A es inversible y. pero vamos a repetir el proced- imiento: p3 (−2) = a3 (−2)3 + a2 (−2)2 + a1 (−2) + a0 = 6 = f (−2) p3 (0) = a3 (0)3 + a2 (0)2 + a1 (0) + a0 = 4 = f (0) p3 (1) = a3 (1)3 + a2 (1)2 + a1 (1) + a0 = 5 = f (1) p3 (4) = a3 (4)3 + a2 (4)2 + a1 (4) + a0 = 8 = f (4) . La matriz A se le conoce como matriz de Vandermonde.... n desde que xk 6= xj . . k. 1. . entonces Y det (A) = (xi − xj ) 6= 0 0≤i. k = 0. . n.2) donde       xn0 xn−1 0 · · · x0 1 an f (x0 )  xn1 xn−1 · · · x1 1   an−1   f (x1 )   1      A= .. existen otras formas. xn son todos distintos. .. el sistema de ecuaciones lineales dado en (5.
2 muestra la situación de este ejemplo. + yn Ln (x) donde los polinomios Lk son de grado n.52 CAPÍTULO 5. y1 = f (x1 )..yn = f (xn ). k = 0.... n Una forma simple de elegir Lk consiste en exigir la condición Lk (xj ) = 0 si k 6= j y Lk (xk ) = 1.. + yn Ln (xi ) = yi i = 0. Figura 5. Obtenimos     a3 −1/9  a2   5/9       a1  =  5/9  a0 4 de donde 1 5 5 p3 (x) = − x3 + x2 + x + 4 9 9 9 La figura 5. tal que interpola a f en los puntos x0 . Queremos que para cada i se cumpla la condición pn (xi ) = yi . xn ...... Sea pn un polinomio de grado menor o igual que n.. n. 1.. INTERPOLACIÓN Y APROXIMACIÓN Luego      (−2)3 (−2)2 (−2) 1 a3 6  (0)3 (0)2 (0) 1   a2   4  A=  (1)3 . donde y0 = f (x0 ). x1 ..... por cualquier técnica ya estudiada.. (x − xk−1 ) (x − xk+1 ) . (xk − xk−1 ) (xk − xk+1 ) .... . 1. . α=  y b=  (1)2 (1) 1   a1   5  (4)3 (4)2 (4) 1 a0 8 La solución puede ser obtenida resolviéndose el sistema lineal Aα = b. donde j. x1 ... (x − xn ) Lk (x) = (xk − x0 ) (xk − x1 ) . (xk − xn ) . xn .. . esto se consigue definiendo (x − x0 ) (x − x1 ) .. ...2: Polinomio p3 interpolando 4 puntos Obtención de pn Mediante la Forma de Lagrange Dados n + 1 puntos diferentes x0 . . es decir: pn (xi ) = y0 L0 (xi ) + y1 L1 (xi ) + . es posible representar pn en la forma pn (x) = y0 L0 (x) + y1 L1 (x) + . .
para xi .. µ 3 ¶ µ 3 ¶ µ 3 ¶ x − 8x2 + 15x x − 6x2 − x + 30 x − 3x2 − 10x p3 (x) = (−3) − +1 +4 − 70 30 30 µ 3 ¶ x − x2 − 6x +9 70 1 ¡ ¢ = 15x3 − 57x2 + 246x + 210 210 Observe la figura 5. y3 son conocidos. .2 La siguiente tabla resume los datos de alguna observación xi −2 0 3 5 yi = f (xi ) −3 1 4 9 Queremos interpolar f usando un polinomio interpolador según la forma de Lagrange. n. tenemos pn (xi ) = yi Li (xi ) = yi y vemos que pn realmente interpola f en tales puntos...3.1. INTERPOLACIÓN 53 Como el numerador de Lk es el producto de n factores (x − xi ).. Así. .. el polinomio buscado es p3 (x) = y0 L0 (x) + y1 L1 (x) + y2 L2 (x) + y3 L3 (x) Como y0 . L3 : (x − x1 ) (x − x2 ) (x − x3 ) (x − 0) (x − 3) (x − 5) x3 − 8x2 + 15x L0 = = =− (x0 − x1 ) (x0 − x2 ) (x0 − x3 ) (−2 − 0) (−2 − 3) (−2 − 5) 70 (x − x0 ) (x − x2 ) (x − x3 ) (x − (−2)) (x − 3) (x − 5) x3 − 6x2 − x + 30 L1 = = = (x1 − x0 ) (x1 − x2 ) (x1 − x3 ) (0 − (−2)) (0 − 3) (0 − 5) 30 (x − x0 ) (x − x1 ) (x − x3 ) (x − (−2)) (x − 0) (x − 5) x3 − 3x2 − 10x L2 = = =− (x2 − x0 ) (x2 − x1 ) (x2 − x3 ) (3 − (−2)) (3 − 0) (3 − 5) 30 (x − x0 ) (x − x1 ) (x − x2 ) (x − (−2)) (x − 0) (x − 3) x3 − x2 − 6x L3 = = = (x3 − x0 ) (x3 − x1 ) (x3 − x2 ) (5 − (−2)) (5 − 0) (5 − 3) 70 Por lo tanto. i 6= k.5. Más aún. 1. . .. Por tanto. .. i = 0. resta sólo conocer los polinomios L0 . 1.. como requerimos. entonces el polinomio Lk es de grado n.. n. el polinomio pn tiene grado menor o igual que n... la forma de Lagrange para el polinomio interpolador es: X n pn (x) = yk Lk (x) k=0 donde Qn i=0 (x − xi ) i6=k Lk (x) = Qn i=0 (xk − xi ) i6=k Ejemplo 5. i = 0.. Con esto.
Basándose en fundamentos teóricos del experimento que nos otorgaron las observaciones.3) se aproxime lo mejor posible a f . donde x1 . g2 (x) = sen x. Las funciones gi .. e esto se conoce con el nombre de extrapolación. .. .. .3: Polinomio p3 interpolando 4 puntos.. (xm . Surge la necesidad de buscar una función que sea una buena aproximación para los valores deseados y. n. por una función g previamente definida. INTERPOLACIÓN Y APROXIMACIÓN Figura 5. f (xm )).. sean ahora los puntos (x1 . Pero interpolar no es aconsejable cuando: 1. los cuales pueden contener errores inherentes. que en general no son previsibles. Así. b]. Es necesario obtener un valor aproximado de la función en algún punto fuera del intervalo de la tabla de definición. . que en cierto modo. .. + αn gn (x) (5. f (x1 )) .. pueden asumir formas no lineares. 2. b].. . xn .. etc. según Lagrange 5. Aproximación: Caso Discreto En la sección anterior vimos algunos métodos para interpolar una función f en los puntos x0 . .. xm ∈ [a. Por medio de este diagrama es posible identificar la curva...2. resuelva nuestro problema con un cierto margen de seguridad..... i = 1. 2. . El gráfico re- sultante se denomina diagrama de dispersión.. o una combinación lineal de curvas.. f (xm )) en el plano cartesiano. i = 1. (xm .... El prob- lema que intentamos resolver consiste en lo siguiente: una vez elegidas n funciones g1 ..54 CAPÍTULO 5. x1 .. . Graficar los puntos (x1 . Pero. que mejor se aproxime a nuestro problema. g3 (x) = x2 + log x.. tales como g1 (x) = ex .. αn tales que la función Φ (x) = α1 g1 (x) + . obtener n constantes a1 . ¿con qué criterio elegir las funciones gi . gn : R 7→ R continuas en [a. n? El procedimiento común consiste en lo siguiente: 1. f (x1 )) .. Los valores en la tabla de datos son resultados de algún experimento físico.
podemos elegir gi adecuadamente.5 −0. entonces encontrar los valores de α1 y α2 que determinan la función Φ (x) = α1 x2 + α2 .1 (5. V (voltaje) es una función lineal de .5 2 4 6 7 10 12 El diagrama de dispersión está dado en la figura 5.4: Diagrama de dispersión Ejemplo 5.5: Elección de gi mediante fundamenento teórico corriente eléctrica con la tensión: V = RI. APROXIMACIÓN: CASO DISCRETO 55 Ejemplo 5.65 2. Figura 5.5. Claramente.2. Es decir. una forma conveniente es elegir g1 (x) = x2 y g2 (x) = 1.4 (Elección de gi utilizando fundamentos teóricos) Si consideramos una ex- periencia donde fueron medidos varios valores de corriente eléctrica que pasan por una re- sistencia sometida a varias tensiones.4.4) f (x) 3 1 −1 −1. resultados de alguna observación: x −2 −1.8 3.5 0 1 1.colocando esos valores incialmente en el gráfico 5.2 2.3 (Elección de gi basado en el diagrama de dispersión) Considere los sigu- ientes datos.5 2.5: En este caso existe un fundamento teórico relacionado a la Figura 5.
. f (xm )). En resumen. . i = 1.. Análogamente a lo que vimos cuando estudiamos interpolación. donde las funciones g1 .. αn de modo que Φ (x) = α1 g1 (x) + . tal que Aᾱ ≈ b (Aᾱ próximo de b).1. esta diferencia es definida como el i-desvío: di = Φ (xi ) − f (xi ) .. de tal modo que: Φ (I) = α1 g1 (I) = α1 I Note que existe una sola incógnita. . (5. ...56 CAPÍTULO 5.3) fueron elegidas las funciones gi . f (x1 )) . Observe que si ai representa la i-fila de A. . (xm .. Al resolver este problema.. Esto sucede justamente porque m (el número de observaciones) es mucho mayor que n (las incógnitas).5) Φ (xm ) = α1 g1 (xm ) + . resta calcular las constantes que definen Φ (x) = α1 g1 (x) + ... n. desearíamos ahora que: Φ (x1 ) = α1 g1 (x1 ) + . Gustaríamos ahora de encontrar ᾱ ∈ Rn . gn : R 7→ R fueron elegidas de forma adecuada. + αn gn (x1 ) = f (x1 ) . .  y b= . Luego.. + αn gn (x). El Método de Mínimos Cuadrados consiste en calcular ᾱ del siguiente modo: ᾱ = mı́nn kAα − bk2 (5.. α1 . se tiene que m À n (m mucho mayor que n).7) α∈R donde k·k es la norma euclídea. 5. . al determinar α1 habremos ajustado ese diagrama a una curva lineal.6) donde       g1 (x1 ) · · · gn (x1 ) α1 f (x1 )  . INTERPOLACIÓN Y APROXIMACIÓN I (intensidad). . el valor que tome α1 será a su vez una aproximación a la resistencia R. es decir.2.. ...      A= . Nuestro objetivo es encontrar los valores de α1 . podemos nuevamente verlo matricialmente así: Aα = b (5... entonces ai α − bi representa Φ (xi ) − f (xi ). Método de Mínimos Cuadrados Dados los puntos conocidos (x1 . α =  . . 2. todo eso basado en un fundamento teórico.. .... por lo general... resulta prudente elegir g1 (I) = I. Una vez que en (5... En experimentos de este tipo. que no tiene solución. . αn variables.... A continuación veremos una de las formas más comunes. como Φ busca aproximar la tensión relacionada a esos datos.  g1 (xm ) · · · gn (xm ) αn f (xm ) Note que el sistema (5... + αn gn (x) se aproxime lo mejor posible a la supuesta función f . + αn gn (xm ) = f (xm ) Este sistema de m filas y α1 ..6) por lo general es incompatible.
5 Considere los siguientes datos vistos en (5. tal que . existe una única solución ᾱ para el sistema ∇q (α) = 0. de ahí el nombre del método (vea la figura 5. la sumatoria de los desvíos al cuadrado. si A tiene rango completo.8) puede resolverse utilizando la descomposición de Cholesky.4).8) o ¡ ¢−1 t α = At A Ab (5. . En estas condiciones. el sistema (5.6: Valor absoluto de la desviación di Para minimizar la función q : Rn 7→ R. donde ∇q (α) = At Aα − At b Así.. igualando a cero. Después de derivar parcialmente q.2. definida por la regla q (α) = kAα − bk2 .5. tenemos el siguiente sistema de n incógnitas y n ecuaciones: ∂q (α) = 0 ∂α1 . Luego. Después de elegir g1 (x) = x2 y g2 (x) = 1.6). utilizamos algunos resultados del cálculo diferencial. APROXIMACIÓN: CASO DISCRETO 57 Además. Ejemplo 5. la cual la obtenemos de resolver: At Aα = At b (5.9) Note que At A es una matriz cuadrada e inversible desde que A tenga rango completo. la matriz At A es simétrica y definida positiva. así. 2 X m 2 X m kAα − bk = (ai α − bi ) = d2i i=1 i=1 Pm Es decir.4. entonces At A es inversible. Figura 5. cuyo diagrama de dispersión asociado está dado en la figura 5. ∂q (α) = 0 ∂αn Esto es equivalente resolver ∇q (α) = 0. al minimizar kAα − bk2 estamos minimizando i=1 d2i .
8) = α1 (2.0000 1   2.2500 1   6. b=  y α=  1    4.1) = α1 (3.22449857738665 = α2 −0.5) = α1 (−1.1375 = 39.7.8400 1   10. es decir.0000 1 3.4400 .5)2 + α2 = 1 Φ (−0. procedemos a encontrar α1 y α2 exigiendo que: Φ (−2) = α1 (−2)2 + α2 = 3 Φ (−1.000 1   −1.2500 1   1.224498x2 − 0.1)2 + α2 = 12 y obteniendo el sistema lineal Aα = b. de la mejor manera.6625 10 α2 42.606667.606667482559783 La curva que se aproxima.3943 39.0000       7.0000  α1 A=  1. resolviendo At Aα = At b: · ¸· ¸ · ¸ 266.5000 tenemos · ¸ · ¸ α1 1. es Φ (x) = 1.8)2 + α2 = 10 Φ (3.2) = α1 (1.0000  9.5)2 + α2 = 6 Φ (2.0000 Resolviendo por mínimos cuadrados.0000    α2  6.5000      · ¸  1. donde:     4.65) = α1 (2. .0000  2.65)2 + α2 = 7 Φ (2.5)2 + α2 = −1 Φ (0) = α1 (0)2 + α2 = −1.5) = α1 (−0. el gráfico está dado en la figura 5.5) = α1 (2.0000       0.5 Φ (1) = α1 (1)2 + α2 = 2 Φ (1.0000       7.6625 α1 302.2500 1   −1.2)2 + α2 = 4 Φ (2.0000       0.58 CAPÍTULO 5.6100 1 12.0225 1   7. INTERPOLACIÓN Y APROXIMACIÓN Φ (x) = α1 x2 + α2 .
5.2. APROXIMACIÓN: CASO DISCRETO 59 Figura 5.7: Φ aproximando el diagrama de dispersión .
60 CAPÍTULO 5. INTERPOLACIÓN Y APROXIMACIÓN .
entonces tal función tiene antiderivada F en [a. xn = b (6. esto constituyó uno de los más grandes descubrimientos dentro del cálculo infinitesimal. x1 ]. el problema se resumiría a la integración de polinomios.. . xn−1 .. x1 ] está por encima del eje de las abscisas.. 6. sustituir la función f por polinomios que la aproximen razonablemente en el intervalo [a.1. x1 . b]. La idea básica de los métodos numéricos consiste en establecer una partición uniforme {x0 .1. lo cual es trivial. En este capítulo veremos algunos de los más populares métodos numéricos para calcular integrales definidas. Mientras más pequeño sea h.. 61 . Posteriormente. xn−1 .. b] y Z b f (x) dx = F (b) − F (a) a Sin lugar a dudas. Método de los Trapecios Si usamos la fórmula de Lagrange para aproximar f por un polinomio p1 de grado uno en x0 y x1 . x1 . . x ∈ [a. T puede ser inter- pretada como el área del trapecio mostrado en la figura 6. b]. la cual es una aproximación para el valor de la integral de f en [x0 . cuando f sobre [x0 . mejor será la aproximación. tenemos Z x1 Z x1 Z x1 µ ¶ x − x1 x − x0 f (x) dx ≈ p1 (x) dx = f (x0 ) + f (x1 ) dx x0 x0 x0 −h h h = (f (x0 ) + f (x1 )) = T 2 Observe que. es decir F 0 (x) = f (x) . b]. b]: a = x0 ..1) donde x0 < x1 < · · · < xn y h = x1 − x0 = x2 − x1 = · · · = xn − xn−1 = (b − a) /n.Capítulo 6 Integración numérica Sabemos que si una función f : R 7→ R es continua en el intervalo [a. xn } del intervalo de integración [a. Pero es casi improbable calcular la integral de una función arbitraria f . Así.
Para n = 10000.62 CAPÍTULO 6.00000004499998 R2 2 2.1 (Regla de los Trapecios) Dada la función f : R 7→ R continua en [a. calcule y verifique que: R2 1. for k=1:n I=I+f(a+(k-1)*h)+f(a+k*h). I=0. b]. Para n = 10000. se tiene 0 e−x dx ≈ 0. INTEGRACIÓN NUMÉRICA Figura 6.1: Podemos repetir ese procedimiento para cada uno de los subintervalos generados por la partición uniforme.b. Paso inicial: Definir n y calcular h = (b − a) /n Paso principal: Calcular hX n−1 I= {f (a + kh) + f (a + (k + 1) h)} 2 k=0 Rb I es una aproximación a a f (x) dx Una función en MatLab quedaría así: function I=trapecio(a. esto nos lleva al siguiente algoritmo. se tiene −1 x2 dx ≈ 3. así Z b n−1 Z xk+1 X X hX n−1 n−1 h f (x) dx = f (x) dx ≈ (f (xk ) + f (xk+1 )) = (f (xk ) + f (xk+1 )) a k=0 xk k=0 2 2 k=0 Note además que xk = x0 + kh = a + kh.n) h=(b-a)/n. end I=I*h/2. Algoritmo 6.1 Usando la función MatLab de arriba.681133991768069 . se tiene −3 sen (7x3 + sen (ln (x4 + x2 + 5))) dx ≈ 0. Ejemplo 6. Para n = 10000.882081390518215 R7 3.
2: Así. tenemos Z x2 h f (x) dx ≈ (f (x0 ) + 4f (x1 ) + f (x2 )) = S x0 3 Podemos tomar de tres en tres puntos de la partición y aplicar repetidamente esta regla.2).2. para eso requerimos que la partición sea definida por n par.6. Método de Simpson Consideremos la misma partición introducida en (6. x1 = x0 + h y x2 = x0 + 2h (vea la figura 6. Z b h f (x) dx ≈ {[f (x0 ) + f (xn )] + 4 [f (x1 ) + f (x3 ) + · · · + f (xn−1 )] a 3 +2 [f (x2 ) + f (x4 ) + · · · + f (xn−2 )]} Esto nos lleva al siguiente algoritmo. Luego: Z b Z xn n/2 Z x X 2k h f (x) dx = f (x) dx = f (x) dx ≈ {[f (x0 ) + 4f (x1 ) + f (x2 )] a x0 k=1 x2k−2 3 + [f (x2 ) + 4f (x3 ) + f (x4 )] + · · · + [f (xn−2 ) + 4f (xn−1 ) + f (xn )]} Más aún. . Figura 6. MÉTODO DE SIMPSON 63 6. Z x2 Z x2 Z f (x0 ) x2 f (x) dx ≈ p2 (x) dx = (x − x1 ) (x − x2 ) dx x0 x0 2h2 x0 Z Z f (x1 ) x2 f (x2 ) x2 − 2 (x − x0 ) (x − x2 ) dx + (x − x0 ) (x − x1 ) dx h x0 2h2 x0 Integrando. (x − x1 ) (x − x2 ) (x − x0 ) (x − x2 ) (x − x0 ) (x − x1 ) p2 (x) = f (x0 ) + f (x1 ) + f (x2 ) (−h) (−2h) (h) (−h) (2h) (h) Luego.2. Sea p2 el polinomio que interpola f en los puntos x0 . Podemos usar de nuevo la fórmula de Lagrange para obtener la fórmula de integración resultante de la interpolación de f por un polinomio de grado 2.1).
for k=1:2:n-1 S1=S1+f(a+k*h). b]. Paso inicial: Definir n y calcular h = (b − a) /n Paso principal: Calcular h S = {[f (a) + f (b)] + 4 [f (a + h) + f (a + 3h) + · · · + f (a + (n − 1) h)] 3 +2 [f (a + 2h) + f (a + 4h) + · · · + f (a + (n − 2) h)]} Rb S es una aproximación para a f (x) dx Una función en MatLab para este caso. obtuvimos Z 2 2 e−x dx ≈ 0. Problema 6.1 Haga un estudio de la estimativa de los errores cometidos por los métodos del Trapecio y Simpson.2 (Regla de Sipmson) Dada la función f : R 7→ R continua en [a. Para el caso de apenas n = 100. .n) S1=0. del ejemplo anterior.882081390111187 0 Observación 6.2 Implementamos el método de Simpson y lo usamos para calcular la misma in- R 2 −x2 tegral 0 e dx. una manera de medir analíticamente esto es por medio del estudio de error cometido. Ejemplo 6.b. estaría dada del siguiente modo: function S=simpson(a. el método de Simpson es más eficiente que el método del trapecio.64 CAPÍTULO 6. end for k=2:2:n-2 S2=S2+f(a+k*h). INTEGRACIÓN NUMÉRICA Algoritmo 6. end S=(h/3)*((f(a)+f(b))+4*S1+2*S2). S2=0.1 En la práctica. h=(b-a)/n.
Documents Similar To An 123456
ISC101.2-2-5-The-binary-system_OK.pdf
Números Binarios Informatica
Gabriel Maldonado Cedeño
Harold Alberto Santana Ordoñez
REDONDEO DE DATOS.docx
Diseño de amplificadores de potencia de audio - N. G. Muiño
Guia 2 Sistemas de información
Bits en decimal.txt
Ed Estribì
Silabo MD - 2014-II
04_matematica.pdf
Tabla de Contenidos Matematicas 4o
rt231089
MT02_15_04_13.pdf
Decimal f1
eno_1505
Examen Extraordinario Matematicas Tercero Septiembre
investigación numeros complejos e imaginarios
nmeroscomplexos-121024144837-phpapp02
xxxavs

References: Resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 RESOLUCIÓN 
 RESOLUCIÓN 
 RESOLUCIÓN 
 Resolución 
 RESOLUCIÓN 
 RESOLUCIÓN 
 RESOLUCIÓN 
 RESOLUCIÓN 
 RESOLUCIÓN 
 resolución 
 Resolución