Source: http://slideplayer.es/slide/2351217/
Timestamp: 2019-09-18 01:26:27+00:00

Document:
Métodos Iterativos para la resolución de ecuaciones en una variable - ppt video online descargar
Publicada porMayte Adames Modificado hace 5 años
Presentación del tema: "Métodos Iterativos para la resolución de ecuaciones en una variable"— Transcripción de la presentación:
1 Métodos Iterativos para la resolución de ecuaciones en una variable
En este tema, trataremos la resolución aproximada de ecuaciones no lineales de una variable del tipo f(x)=0. Suponemos que f es una función continua y que tratamos de hallar sus ceros, los valores de x que anulan f, o sea, las raíces de la ecuación f(x)=0. Si no es fácil despejar x en la ecuación anterior, recurrimos a un método iterativo. La idea no es más que una formalización del método de tanteo, en el que vamos probando valores de x cada vez más próximos a la solución, o que hagan cada vez más pequeño el valor de f(x). Los distintos métodos iterativos se caracterizan por la forma en que eligen la nueva estimación, en función del resultado de anteriores aproximaciones. En teoría, la solución se alcanza tras infinitos pasos del método, pero, en la práctica, nos conformamos con obtener una aproximación de la solución exacta dentro de cierto margen de tolerancia, que llamaremos tol. Además, limitaremos el número máximo de iteraciones para evitar problemas debidos a que el método no converja a la solución o que converja demasiado lentamente. Aplicaremos en primer lugar los métodos de Punto Fijo, Bisección y Regula-Falsi, completando este estudio de los métodos elementales de resolución de ecuaciones con los métodos de Newton y de la secante.
2 Métodos Iterativos para la ecuación f(x)=0
Estimación inicial x0 tal que 0 Proceso iterativo x1, x2,..., xk, x* : f(x*)=0 Criterio de parada |f(xk)| < tol ó dk = |xk+1 - xk| < tol Tipos de convergencia Error del paso k ek = |xk - x*|  |xk - xk-1| Convergencia lineal ek+1 / ek cte Convergencia cuadrática ek+1 / ek cte La idea para la resolución de ecuaciones por métodos iterativos es: 1. Obtener una estimación inicial x0 de la solución. En ella se resume la información previa de que disponemos. A falta de información (lo que es raro en la práctica), disparamos a ciegas. 2. Refinar iterativamente la aproximación, obteniendo valores x1, x2, x3,… que (idealmente) convergen a la solución x* de la ecuación. 3. Establecer un criterio de parada. Dependiendo del método utilizado, exigiremos que las iteraciones varíen poco o que la ecuación se satisfaga con aproximación suficiente. Conviene limitar también el número máximo de iteraciones, en previsión de que el algoritmo diverja, oscile indefinidamente o converja muy lentamente. Cuando el algoritmo converge, nos interesa que lo haga lo más rápidamente posible. Medimos el error por la distancia del iterado a la solución. El error exacto no se puede calcular si no conocemos la solución exacta (y si la conocemos, no necesitamos el método iterativo). En la práctica, estimaremos el error mediante la distancia entre dos iteraciones consecutivas. Si el método converge, esperamos que el error decrezca en progresión aritmética. Entonces, el cociente de errores consecutivos es aproximadamente igual a una constante r. Cuando ocurre esto, decimos que hay convergencia lineal de razón r. En un proceso con convergencia lineal, en cada paso, el error se divide aproximadamente por la razón. Cuanto más próxima a 0 esté, más rápida será la convergencia. Cuanto más próxima a 1, más lenta. Un hito importante es lograr una convergencia más rápida que la lineal. Así, si el error de cada paso es proporcional al cuadrado del error del paso anterior, decimos que hay convergencia cuadrática. Hablando en términos generales, en un algoritmo con convergencia lineal, cada tantos pasos conseguimos una cifra decimal exacta más en la solución aproximada. Cuando hay convergencia cuadrática, cada cierto número de pasos se duplica el número de cifras exactas.
3 (Clave: Teorema de Bolzano)
Método de Bisección Determinar un intervalo [a,b] tal que f(a) tiene signo distinto de f(b) y f continua en [a,b]. Hallar el punto medio c del intervalo. Elegir, entre [a,c] y [c,b], un intervalo en el que la función cambie de signo. Repetir los pasos 2 y 3 hasta conseguir un intervalo con la precisión deseada (f(c) <tol) (Clave: Teorema de Bolzano) El método de bisección nos ofrece la garantía absoluta de convergencia, a costa tal vez de una mayor lentitud. Este método es el óptimo para adivinar un número con el solo dato de si es menor o mayor que la conjetura hecha. En el caso de funciones, dado un intervalo en el que la función f cambia de signo, lo dividimos en dos subintervalos por su punto medio y nos quedamos con aquel en el que se produce el cambio de signo. El proceso se repite hasta obtener un intervalo suficientemente pequeño que contenga a la raíz. El fundamento teórico de este método es el llamado Teorema de Bolzano que afirma que si una función continua cambia de signo en un intervalo, entonces se anula en algún punto del mismo. La bisección es un proceso sistemático para buscar ese punto. Construimos el algoritmo de bisección En primer lugar, tenemos en cuenta que buscamos la raíz de la ecuación f(x)=0. Proporcionaremos como dato de entrada los extremos del intervalo en el que f cambia de signo. En código Matlab a primera línea del fichero biseccio.m puede quedar así: [c, iter] = biseccio(a,b,tol,maxiter) Tomamos la amplitud del intervalo como indicador de convergencia. Por tanto, el bucle comienza con while (b-a > tol) & (iter < maxiter)
4 Teorema de Bolzano Sea f:A continua y sean a,bA
con f(a)f(b) < 0. Entonces, existe c [a,b] con f(c) = 0. f(a) b a f(b)
5 Algoritmo de Bisección
c =(a+b)/2; if f(a)*f(c)<=0 %elige [a,c] b=c; end if f(c)*f(b)<=0 %elige [c,b] a=c; El paso de bisección consiste en dividir en dos el intervalo actual y elegir uno de los subintervalos. Precisamente aquel en el que la función f cambia de signo. Si c es el punto medio del intervalo actual, [a,b], y la función cambia de signo en [a,c], nos quedamos con este semiintervalo. Para ello basta actualizar la variable b, que contiene el extremo derecho del intervalo actual, dándole el valor c. Si el cambio de signo se produce en el semiintervalo derecho, [c,b], daremos a la variable a, que contiene el extremo izquierdo, el valor c. Así, tras cada paso, [a,b] es un intervalo en el que la función cambia de signo. Además, su longitud es la mitad de la del paso anterior. Dando suficiente número de pasos, localizamos la raíz con la precisión deseada. El método de bisección es totalmente seguro, pero no se puede variar su velocidad de convergencia, que es lineal de razón 1/2. Incluso a veces ocurre que el punto medio del intervalo es peor estimación de la raíz que uno de los extremos. Esto es debido a que el método no tiene en cuenta los valores de la función en los extremos, sino sólo el signo de los mismos. Veamos a continuación una modificación del método que intenta subsanar estos detalles. Teorema: El método de la bisección genera una sucesión {xn} que converge a una raíz  de f con xn-   (b-a)/2n.
6 Método de Regula-Falsi
Determinar un intervalo [a,b] tal que f(a) tiene signo distinto de f(b). Hallar el punto c que divide el intervalo [a,b] en partes proporcionales a f(a) y f(b). Sea Elegir, entre [a,c] y [c,b], un intervalo en el que la función cambie de signo. Repetir los pasos 2 y 3 hasta conseguir la precisión deseada. El método de Regula Falsi parte, como él de bisección, de un intervalo en el que la función cambia de signo y lo divide en dos partes. La diferencia es que los subintervalos ahora son proporcionales a los valores de la función en los extremos. El nombre del algoritmo proviene de que el punto c de división es el corte con el eje OX de la recta que pasa por los puntos de la gráfica (a, f(a)) y (b, f(b)). El método converge generalmente con más rapidez que la bisección, pero no garantiza que el intervalo de búsqueda de la raíz se haga pequeño. Típicamente, un extremo queda fijo mientras que el otro se acerca a la raíz. Usaremos de nuevo la variable incr que mide la distancia entre dos c's consecutivos como medida de la precisión alcanzada. a c b
7 Bisección Regula Falsi
Convergencia lineal de razón 1/2. Cota de la raíz: (b-a)/2n. La aproximación obtenida puede ser peor que la del paso anterior. Más rápido al principio. Convergencia lineal. Error estimado por: |xn-xn-1| Se aproxima a la raíz por un lado.
8 Método del Punto Fijo Transformar la ecuación f(x) = 0 en una ecuación equivalente de punto fijo: x = g(x). Tomar una estimación inicial x0 del punto fijo x* de g [x* punto fijo de g si g(x*) = x*]. Para k=1, 2, 3, … hasta que converja, iterar xn+1 = g(xn). Como veremos a continuación, la convergencia del método de punto fijo depende del valor de la derivada de la función. Demostremos el teorema de la transparencia. El apartado a) es consecuencia inmediata del teorema de Bolzano. Para el apartado b) aplicamos el Teorema del Valor Medio a la función g en el intervalo [x0, x*], donde x* es el punto fijo. se obtiene que g(x0) - g(x*) = g'(x0)(x0 - x*) para cierto x0 del intervalo ]x0, x*[. Por definición de las iteraciones y por ser x* punto fijo, queda x1 - x* = g'(x0)(x0 - x*) Tomando valor absoluto y usando la acotación de la derivada tenemos |x1 - x*| = |g'(x0)|·|x0 - x*| < K·|x0 - x*|. Aplicamos de nuevo el TVM al intervalo [x1, x*] y obtenemos |x2 - x*| = |g'(x0)|·|x1 - x*| < K·|x1 - x*| Teniendo en cuenta la desigualdad anterior |x2 - x*| < K·|x1 - x*| < K2·|x0 - x*|. Repitiendo este proceso, para cada n = 1, 2, 3, … pruebamos que |xn - x*| < Kn·|x0 - x*|. Al ser K<1, Kn tiende a 0 y, por tanto, xn tiende a x*, como queríamos demostrar. En términos numéricos, el error decrece al menos geométricamente con razón K: en+1 < Ken por lo que hay convergencia lineal. Teorema del punto fijo: Sea g:[a,b]  [a,b] continua, entonces: a) g posee almenos un punto fijo. b) Si además g’(x) k<1, x [a,b], entonces el punto fijo es único y si tomamos x0 [a,b], la sucesión xn+1 = g(xn) converge al punto fijo de g(x).
9 Convergencia del Método del Punto Fijo
Aplicar el método del punto fijo a: g(x) = cos x, x0 g(x) = 2/x2, x0=1 g(x) = sqrt(2/x) , x0=1 y analizar los resultados. Sugerencia: Usar la orden ITERATES(g(x), x, x0, n) de DERIVE y comparar los dos últimos con 2^(1/3). Tomando x0 cercano al punto fijo x* si |g’(x*)| < 1 los iterados convergen linealmente a x*. si |g’(x*)| > 1 los iterados no convergen a x*. si g’(x*) = 0 los iterados convergen cuadráticamente a x*. Si aplicamos la función coseno a un valor inicial cualquiera, luego hallamos el coseno del resultado, y así repetidas veces, observamos que los valores obtenidos se estabilizan entorno a Hemos localizado un valor que no varía al aplicarle el coseno … es un punto fijo de la función coseno. En general, x* es punto fijo de una función g si g(x*)=x*. Dicho de otro modo, x* es solución de la ecuación g(x)=x. En el ejemplo del altar de Apolo teníamos que resolver la ecuación x3 = 2. La clave para aplicar el método del punto fijo es transformar la ecuación f(x)=0 en otra equivalente de la forma g(x)=x. Esto puede hacerse de muchas formas, y no siempre funciona, como comprobamos en dicho ejemplo. La razón de este comportamiento puede adivinarse a partir de la representación gráfica. Como aplicación práctica del teorema anterior, si g tiene un punto fijo de derivada menor que 1 en valor absoluto, los iterados convergerán a dicho punto fijo. La convergencia es lineal. Si la derivada es mayor que 1 en valor absoluto, los iterados divergen, aún cuando tomemos una estimación inicial muy cercana al punto fijo. En el extremo opuesto, si la derivada en un punto fijo es cero, la convergencia es más rápida, al menos cuadrática. Esto se demuestra matemáticamente como en el teorema anterior, utilizando en lugar del teorema del valor medio, el desarrollo de Taylor de g en torno a x*, en el que se anulan los términos de las derivadas de g nulas en x*. g(x)=sqrt(2/x) g(x)=2/x2 0.5 1 1.5 2 0.8 1 1.2 1.4 1.6 1.8 2 2.2 0.4 0.6
10 Algoritmo de Punto Fijo
Datos Estimación inicial: x0 Precisión deseada: tol Tope de iteraciones: maxiter Proceso: mientras no converja repetir Nueva estimación: x = g(x0) Incremento: incr = |x - x0| Actualización: x0 = x Resultado Estimación final: x Detallemos un poco más el método para determinar las variables a utilizar y los pasos que debe realizar el algoritmo. Los datos de entrada serán la estimación inicial x0 y la precisión con la que deseamos obtener la solución, tol. Ponemos tope al número de iteraciones con la variable maxiter. Las iteraciones para calcular la nueva estimación x aplicando g a la antigua x0 constituyen el núcleo del algoritmo. En esta parte, además, controlamos la variación incr de una estimación a otra y contamos el número de iteraciones, iter. Repetimos el proceso mientras se cumplan dos condiciones: que la variación sea mayor que la tolerancia: incr > tol que no se supere el máximo de iteraciones: iter < maxiter Utilizamos sólo dos variables para almacenar la estimación previa x0 y la estimación nueva x. En cada paso, una vez calculado el incremento, almacenamos en x0 el nuevo valor x para aplicar la siguiente iteración. Esta operación se llama actualizar el valor de x0. Como resultado, obtendremos la estimación final de la solución x. También interesa conocer el valor de incr para estimar la precisión alcanzada y el número de iteraciones. Es posible que el programa termine por haber superado el máximo de iteraciones, pero con una variación mayor que la tolerancia. En este caso no hay convergencia al punto fijo. Para programar el método de punto fijo en MATLAB, utilizamos la instrucción while … end, que define un bucle controlado por una condición. El programa que obtendremos proporciona un modelo aplicable a otros procesos iterativos.
11 Método de Newton Ecuación de la tangente Intersección con OX
Paso genérico (x0, f (x0)) x1 f(x) La idea del método de Newton-Raphson para resolver la ecuación f(x)=0 es aproximar localmente la función f por una función lineal l(x) y resolver la ecuación l(x)=0. Tomamos esta solución como nueva estimación de la raíz de f(x) y repetimos el proceso hasta obtener la precisión deseada. Sea x0 la estimación inicial de la solución. El método de Newton halla la tangente a la gráfica de f en el punto (x0,f(x0)) y toma la intersección x1 de la tangente con el eje OX como nueva estimación de la solución. La ecuación de la tangente es y = f(x0) + f '(x0)·(x-x0) y la intersección con el eje OX se obtiene haciendo y = 0 x1 = x0 - f(x0)/f '(x0) siempre que la derivada f' no se anule en x0. Tomamos x1 como nueva estimación de la raíz y repetimos el proceso para obtener una nueva estimación x2 = x1 - f(x1)/f '(x1) Procediendo iterativamente, en el paso n+1 determinamos xn+1 = xn - f(xn)/f '(xn) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 -0.8 -0.6 -0.4 -0.2 Método de Newton x0 x1 x2 f(x)
12 Convergencia del método de Newton
Newton como iteración de punto fijo Derivada de la función de iteración Convergencia cuadrática Ventaja: converge cuadráticamente si la estimación inicial es buena no se anula la derivada Inconveniente: usa la derivada coste de la evaluación disponibilidad El método de Newton es un caso especial del iteración de punto fijo, siendo g(x) = x - f(x)/f '(x) la función de iteración. La ecuación de punto fijo g(x) = x es equivalente a la ecuación f(x)=0, si f '(x) no es 0. La característica destacable de esta función g de iteración es que su derivada se anula en x* (g’(x*)=0), siendo x* una solución de la ecuación f(x)=0. En estas condiciones, el método de punto fijo converge cuadráticamente. En efecto, desarrollando la g(x) de la expresión del error por la fórmula de Taylor, tenemos: Suponiendo que la derivada segunda de g es aproximadamente constante, hemos obtenido que el error de un paso es proporcional al cuadrado del error del paso anterior. En la práctica, esto supone que el número de cifras decimales se duplica cada cierto número de iteraciones. La convergencia del método de Newton se degrada al acercarse a una raíz múltiple de f(x). Por ejemplo, la iteración de Newton para la ecuación x3 = 0 es xk+1 = 2/3·xk que converge linealmente con razón 2/3 (¡más lenta que la bisección!). El método de Newton no converge si al derivada está próxima a 0. Por ejemplo si en la ecuación arctg(x) = 0 tomamos una estimación inicial de x0=1’5, las iteraciones de Newton divergen. -6 -5 -4 -3 -2 -1 1 2 3 y=arctg(x) x0 x1 x2 x3
13 Algoritmo de Newton Datos Estimación inicial: x Precisión deseada: tol
Tope de iteraciones: maxiter Proceso: mientras no converja repetir Incremento: incr = - f(x)/f’(x) Nueva estimación: x = x + incr Resultado Estimación final: x El algoritmo de Newton tiene la misma estructura que el método de punto fijo. Introducimos variaciones mínimas que reflejan las particularidades del método de Newton. Los datos de entrada serán la estimación inicial x y la precisión con la que deseamos obtener la solución, tol. Ponemos tope al número de iteraciones con la variable maxiter. La fórmula de los iterados sugiere construir cada uno como corrección del anterior. Asignamos la corrección a la variable incr y calculamos la nueva estimación añadiendo la corrección a la estimación anterior. Codificamos este cálculo como una actualización de la variable x. No necesitamos simultáneamente la iteración actual y la nueva, pues ya conocemos su diferencia, incr. Para salir del bucle, comparamos el valor absoluto de incr con la tolerancia, tol, para terminar el bucle. Para evitar el probelma de la evaluación de la derivada, existe un método de Newton modificado que calcula la derivada sólo en la primera iteración y la emplea en pasos sucesivos, según la fórmula xk+1 = xk - f(xk)/f '(x0) El ahorro en evaluaciones de la derivada se traduce en una convergencia más lenta, que se hace lineal, en lugar de cuadrática. Como solución de compromiso, podemos evaluar al derivada cada cierto número de pasos, para no degradar tanto la convergencia. Si no disponemos de la derivada, la estimamos mediante un cociente incremental para h pequeño. Así se ‘simula’ bastante bien el método de Newton. En cada paso evaluamos dos veces la función f, pero no necesitamos la expresión de la derivada. El método que veremos a continuación utiliza como iterados los puntos que intervienen el el cálculo del cociente incremental, reduciendo a una las evaluaciones de la función por cada paso. Es el método de la secante.
14 Método de la secante Ecuación de la secante Intersección con OX
Pendiente (x0,f(x0)) f(x) x1 Suponiendo que x0 y x1 son dos estimaciones iniciales de la solución de la ecuación f(x)=0, el método de la secante aproxima la función f(x) por la recta que pasa por los puntos (x0, f(x0)) y (x1, f(x1)) y toma su intersección, x2, con el eje OX como siguiente estimación. En el segundo paso, traza la secante por los puntos de abscisa x1 y x2 y la intersecta de nuevo con OX para hallar la tercera estimación x3. El proceso se repite, como siempre, hasta alcanzar la precisión deseada. Expresamos la iteración genérica de la secante en términos análogos a la de Newton como Nota: El método de Regula-Falsi utiliza el punto de corte x2 de la secante para dividir el intervalo [x0, x1] en dos partes y elige aquella en que la función cambia de signo. Podría ser [x0, x2]. El método de la secante no se preocupa del signo de la función. Siempre toma los dos últimos iterados, x1 y x2, para el paso siguiente, abandonando el iterado anterior x0. x0 x2 (x1,f(x1))
15 Algoritmo de la secante
Datos: x0, x1, y0 Calcular: y1 = f(x1) Calcular: incr = -y1(x1-x0)/(y1-y0) Nueva estimación: x2 = x1 + incr Actualizar para el paso siguiente: x0=x1; y0=y1; x1=x2 Para programar el método de la secante, evitamos evaluar varias veces la función f en cada paso, almacenando su valor en variables que usamos en iteraciones consecutivas. Llamamos (x0, y0) y (x1,y1) a los puntos que definen la secante en cada paso. En cada iteración Evaluamos y1 Hallamos la intersección x2 de la secante con OX Actualizamos los valores de x0, y0 x1 Aunque más lento, en general el método de la secante es más robusto que el de la tangente. Comprueba su convergencia para la ecuación arctg(x)=0 tomando x0=1.5, x1=2. Recuerda que el método de Newton divergía partiendo de 1.5 como estimación inicial.
16 Newton versus Secante El método de Newton, cuando converge, lo hace cuadráticamente, a costa de evaluar la derivada en cada paso. Sin usar la derivada, el método de la secante proporciona convergencia superlineal. Las ecuaciones polinómicas pueden resolverse por el método de Newton, puesto que la derivada se obtiene fácilmente. Los métodos iterativos de Newton y la secante convergen más rápidamente, en general, que los de punto fijo, bisección y regula-falsi. El método de Newton es muy rápido, si converge. Hemos demostrado que converge cuadráticamente, logrando en pocos pasos la precisión de la máquina. Tiene el inconveniente de que necesita la derivada de la ecuación, lo cual suele ser costoso o imposible de calcular. Además, para que haya convergencia, hemos de tener una estimación inicial suficientemente buena. Si es por el coste (no es problema para ecuaciones de una variable) recurrimos al método de Newton modificado, que efectúa varios pasos con un mismo valor de la derivada. Si no disponemos de la derivada, o no queremos calcularla, el método de la secante ofrece una rapidez de convergencia intermedia entre lineal y cuadrática con menos problemas de convergencia que Newton. Los métodos usados en las aplicaciones reales son una mezcla de algoritmos tipo secante y bisección. Primero buscan un intervalo en el que la función cambie de signo y luego aplican la secante. Si un paso de secante se aleja demasiado, vuelven a aplicar bisección para localizar el intervalo adecuado.
Descargar ppt "Métodos Iterativos para la resolución de ecuaciones en una variable"
MÉTODO DE BISECCION El método de bisección se basa en el Teorema del Valor Intermedio Básicamente el Teorema del Valor Intermedio nos dice que toda función.
Contenido Planteamiento del problema Método de Punto Fijo

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución