Upload
duongdien
View
277
Download
1
Embed Size (px)
Citation preview
Resolución de Ecuaciones no lineales
Objetivos Aprender a resolver ecuaciones de la forma:
Donde f es una función no-lineal de la variable escalar real .
En este curso estudiaremos tres métodos 1. Bisección2. Punto fijo 3. Newton-Raphson4. Secante
x
f (x) = 0
Resolución de Ecuaciones no lineales
En general, algoritmos iterativos serán usados para resolver la ecuación no-lineal de la forma:
Dada una aproximación inicial , una sucesión de términos es calculada
Hasta que un valor lo “suficientemente bueno” es encontrado.
f (x) = 0x0
0 1, , , kx x x
xk
Un algoritmo iterativo debe responder a las siguientes preguntas:¿Cómo elegir el punto de partida ? Experiencia, orden de magnitud¿ Cómo son calculados cada uno de los términos de la sucesión? Depende del método
¿Cómo saber si el termino de aproxima la solución lo suficientemente bien? Criterio de convergencia
Resolución de Ecuaciones no lineales
x0
0 1, , , kx x x
xk
Un sucesión converge a cuando
Dividiendo por
Se dice que una aproximación es lo suficientemente buena si
Resolución de Ecuaciones no lineales
xk{ } a
limk®¥xk = a
lim 0kk
x
lim lim 0kk
k k
xr
a
xk
rk £ tolx
En la practica se asume que
De donde surge el siguiente criterio de convergencia
Para prevenir algunos problemas cuando
Resolución de Ecuaciones no lineales
rk =xk - xk+1
xk+1
xk - xk+1
xk+1
£ tolx
a = 0
xk - xk+1 £ tolx xk+1 + E
En algunos casos, el anterior criterio se satisface aun estando muy lejos de la soluciónPara evitar el problema, vamos a tener en cuenta que cuando la sucesión converge a
Por tanto, se puede formular un segundo criterio de convergencia
Resolución de Ecuaciones no lineales
a
limk®¥f (xk ) = 0
xk{ }
f (xk ) £ tol f
Resolución de Ecuaciones no lineales: Convergencia
Importancia de seleccionar el criterio de convergencia
Método de punto fijo
El método de punto fijo se basa en re-escribir la ecuación de tal modo que este al lado izquierdo de la ecuación.
f (x) = 0
x
x = g(x)
Método de punto fijoEjemplo 1(a)
f (x) = x2 - 2x - 3
Encuentre los ceros de la función usando el método de punto fijo
x2 = 2x + 3
x = 2x + 3
( ) 2 3g x x
1'( )
2 3g x
x
( )g x
'( )g x
Método de punto fijoEjemplo 1(a)
f (x) = x2 - 2x - 3
Encuentre los ceros de la función usando el método de punto fijo
Utilizando la formula cuadrática obtenemos que los ceros de la función son
x1 = 3,x2 = -1
x2 = 2x + 3
x = 2x + 3
xn+1 = 2xn + 3
x0 = 4
En excel
Método de punto fijoEjemplo 1(b)
f (x) = x2 - 2x - 3
Encuentre los ceros de la función usando el método de punto fijo
2 2 3 0
( 2) 3 0
3
2
x x
x x
xx
3( )
2g x
x
'( )g x
( )g x
Método de punto fijoEjemplo 1(b)
f (x) = x2 - 2x - 3
Encuentre los ceros de la función usando el método de punto fijo
Utilizando la formula cuadrática obtenemos que los ceros de la función son
x1 = 3,x2 = -1 1
3
2n
n
xx
x0 = 4
En excel
2 2 3 0
( 2) 3 0
3
2
x x
x x
xx
Método de punto fijoEjemplo 1(c)
f (x) = x2 - 2x - 3
Encuentre los ceros de la función usando el método de punto fijo
x2 - 2x - 3 = 0
2x = x2 - 3
x =x2 - 3
22 3
( )2
xg x
( )g x
'( )g x
Método de punto fijoEjemplo 1(c)
f (x) = x2 - 2x - 3
Encuentre los ceros de la función usando el método de punto fijo
Utilizando la formula cuadrática obtenemos que los ceros de la función son
x1 = 3,x2 = -12
2
2
2 3 0
3 2
3
2
x x
x x
xx
2
1
3
2
nn
xx
x0 = 4
En excel
Método de punto fijoEjemplo 2
f (x) = x - e-x
Encuentre los ceros de la función usando el método de punto fijo
En excel
xn+1 = e-xn
Al observar la columna del error, vemos que el error de la iteración es un factor entre 0.5 y 0.6 el error de la iteración anterior. El método de punto fijo converge linealmente a la solución
Método de punto fijoEjemplo 2
f (x) = x - e-x
Encuentre los ceros de la función usando el método de punto fijo
xn+1 = e-xn ( )g x
'( )g x
Método de punto fijoEjemplo 3 (a)
Encuentre los ceros de la función usando el método de punto fijo
En excel
1
3 21
(10 )2
x x
f (x) = x3 + 4x2 -10
1
3 21
1(10 )
2n nx x
Converge a la raíz de la función
Método de punto fijoEjemplo 3 (a)
Encuentre los ceros de la función usando el método de punto fijo
mapea el intervalo en si mismo ( ver figura y teoremas)
en el intervalo (se cumplen las condiciones para que la sucesión converja al punto fijo de la función )
f (x) = x3 + 4x2 -101
3 21
1(10 )
4n nx x
( )g x
'( )g x
( )g x 1,1.5é ùë û
'( ) 0.66g x £ 1,1.5é ùë û
Método de punto fijoEjemplo 3 (b)
Encuentre los ceros de la función usando el método de punto fijo
En excel
x =10
4 + x
æ
èçö
ø÷
1
2
f (x) = x3 + 4x2 -10
xn+1 =10
4 + xn
æ
èçö
ø÷
1
2
Converge a la raíz de la función
Método de punto fijoEjemplo 3 (b)
Encuentre los ceros de la función usando el método de punto fijo
f (x) = x3 + 4x2 -10
xn+1 =10
4 + xn
æ
èçö
ø÷
1
2
( )g x
'( )g x
mapea el intervalo en si mismo ( ver figura y teoremas)
en el intervalo (se cumplen las condiciones para que la sucesión converja al punto fijo de la función )
( )g x 1,2é ùë û
'( ) 0.15g x £ 1,2é ùë û
Método de punto fijoEjemplo 3 ©
Encuentre los ceros de la función usando el método de punto fijo
En excel
x = x -x3 + 4x2 -10
3x2 + 8x
f (x) = x3 + 4x2 -10
3 2
1 2
4 10
3 8
n nn n
n n
x xx x
x x
Converge a la raíz de la función
Método de punto fijoEjemplo 3 ©
Encuentre los ceros de la función usando el método de punto fijo
f (x) = x3 + 4x2 -10
3 2
1 2
4 10
3 8
n nn n
n n
x xx x
x x
'( )g x
( )g x
mapea el intervalo en si mismo ( ver figura y teoremas)
en el intervalo (se cumplen las condiciones para que la sucesión converja al punto fijo de la función )
( )g x 1,2é ùë û
'( ) 0.6g x £ 1,2é ùë û
Método de punto fijoEjemplo 3(d)
Encuentre los ceros de la función usando el método de punto fijo
En excel
x = x- x3 - 4x2 +10
f (x) = x3 + 4x2 -10
No Converge a la raíz de la función
xn+1 = xn - xn3 - 4xn
2 +10
Método de punto fijoEjemplo 3(d)
Encuentre los ceros de la función usando el método de punto fijo
f (x) = x3 + 4x2 -10
xn+1 = xn - xn3 - 4xn
2 +10
Los teoremas no garantizan que el método deba fallar, tampoco tenemos razón para esperar una convergencia
( )g x
'( )g x
Método de punto fijoEjemplo 3(e)
Encuentre los ceros de la función usando el método de punto fijo
En excel
x =10
x- 4x
æ
èçö
ø÷
1
2
f (x) = x3 + 4x2 -10
No Converge a la raíz de la función
xn+1 =10
xn- 4xn
æ
èçö
ø÷
1
2
Método de punto fijoEjemplo 3(e)
Encuentre los ceros de la función usando el método de punto fijo
f (x) = x3 + 4x2 -10
xn+1 =10
xn- 4xn
æ
èçö
ø÷
1
2
No hay razón para esperar que el método converja
'( )g x
( )g x
Ojo con el dominio de g(x)
Método de punto fijo
Ventajas• Fácil de implementar• Solo es necesario evaluar la función, no es necesario evaluar la derivada
Desventajas• Converge linealmente• No siempre converge a la solución, depende de la función g(x) que seleccionemos
Método de bisección
Algoritmo
Usas el teorema de Bolzano para una función continua en un intervalo cerrado.
Teorema de Bolzano: Si una función escontinua en un intervalo, entonces tomatodos los intermedios comprendidos entrelos extremos del intervalo.
Método de bisecciónEn Matlab
Algoritmo ( ) 2 1f x x= -
Encuentre los ceros de la función usando el método de bisección
Método de Newton-Raphson
La serie de Taylor de una función infinitamente diferenciable en el entorno de un numero real a es la siguiente serie de potencias:
Aproximamos f(x) con los dos primeros términos de las series de Taylor e igualamos la función a 0
Despejamos
f (x) =f (n)(a)
n¡n=0
¥
å (x - a)n
f (x) » f (a)+ f '(a)(x - a) = 0
x = a -f (a)
f '(a)=
De manera iterativa lo podemos escribir como sigue
xn+1 = xn -f (xn )
f '(xn )=
Método de Newton-Raphson
xn+1 = xn -f (xn )
f '(xn )=
El método de Newton comienza con una aproximación inicial x0
del cero de la función a partir de la cual se define una sucesión {xn} de aproximaciones definida por
Desde un punto de vista geométrico, lo que hace el método de Newton es construir la recta tangente a la gráfica de f en x0 y encontrar el cero de la recta tangente, x1. La aproximación x2 es el cero de la recta tangente a la gráfica de f en el punto x1 y así sucesivamente.
Método de Newton-RaphsonEjemplo 1
1
ln( )
1
n
n
x
nn n
x
n
e xx x
ex
Encontrar el cero de la función
( ) ln( )xf x e x
1'( ) xf x e
x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 1x
La convergencia del método de newton es cuadrática, ver columna del error
Método de Newton-RaphsonEjemplo 2
2
1
2
2
nn n
n
xx x
x
Encontrar el cero de la función
2( ) 2f x x
'( ) 2f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 2x
La convergencia del método de newton es cuadrática, ver columna del error
Método de Newton-RaphsonEjemplo 3(a)
3
1 2
8
3
nn n
n
xx x
x
Encontrar el cero de la función
3( ) 8f x x
2'( ) 3f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 4x
La convergencia del método de newton es cuadrática, ver columna del error
Método de Newton-RaphsonEjemplo 3(b)
3
1 2
8
3
nn n
n
xx x
x
Encontrar el cero de la función
3( ) 8f x x
2'( ) 3f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 8x
La convergencia del método de newton es cuadrática, ver columna del error
Método de Newton-RaphsonEjemplo 3 ©
3
1 2
8
3
nn n
n
xx x
x
Encontrar el cero de la función
3( ) 8f x x
2'( ) 3f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 12x
La convergencia del método de newton es cuadrática, ver columna del error
Método de Newton-RaphsonEjemplo 3 (d)
3
1 2
8
3
nn n
n
xx x
x
Encontrar el cero de la función
3( ) 8f x x
2'( ) 3f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 1000x
• La convergencia del método de newton es cuadrática, ver columna del error
• El numero de iteraciones de NR depende de x0 (El método de NR converge a condición de que se escoja una aproximación inicial (x0) suficientemente exacta )
Método de Newton-RaphsonEjemplo 3 (d)
10
1 9
1
10
nn n
n
xx x
x
Encontrar el cero de la función
10( ) 1f x x
9'( ) 10f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 0.5x
Método de Newton-RaphsonEjemplo 3 (d)
10
1 9
1
10
nn n
n
xx x
x
Encontrar el cero de la función
10( ) 1f x x
9'( ) 10f x x
El esquema iterativo queda como sigue
Empecemos el esquema con
0 0.5x
¿Por qué es tan lenta la convergencia del esquema de NR para el presente ejemplo?
Método de Newton-RaphsonResumen
Requerimientos• La función f(x) debe ser derivable• La derivada de f(x) debe ser siempre diferente de 0
Características: • Convergencia cuadrática (siempre y cuando la derivada se calcule correctamente)• El método es costoso computacionalmente (en cada iteración se evalúa su función y su derivada)
Problemas:• Costoso computacionalmente en cada iteración• Es necesaria la derivada de la función
Método de la secante
Usa el algoritmo de Newton-Raphson peroaproxima la derivada de la función, con lapendiente de la línea definida por dosaproximaciones anteriores.
1
( )
( )
nn n
n
f xx x
s x
1
1
( ) ( )( ) n n
n
n n
f x f xs x
x x
Método de la secanteEjemplo 1
Encontrar el cero de la función
Iniciemos con
De donde obtenemos
( ) ln( )xf x e x
1
( )
( )
nn n
n
f xx x
s x 1
1
( ) ( )( ) n n
n
n n
f x f xs x
x x
1 02, 1x x
2 1(2) (1) ln(2) ln(1)(2) 0.9256
2 1 1
f f e es
12 1
1
( ) 0.55782 1.3974
( ) 0.9256
f xx x
s x
Método de la secanteEjemplo 1
Encontrar el cero de la función
Iniciemos con
De donde obtenemos
( ) ln( )xf x e x
1
( )
( )
nn n
n
f xx x
s x 1
1
( ) ( )( ) n n
n
n n
f x f xs x
x x
2 11.3974, 2x x
1.3974 2
2 1
2 1
( ) ( ) ln(1.3974) ln(2)(1.3974) 0.7806
1.3974 2
f x f x e es
x x
23 2
2
( ) 0,0871.3974 1.2854
( ) 0.7806
f xx x
s x
Método de la secanteEjemplo 1
Encontrar el cero de la función
Iniciemos con
De donde obtenemos
( ) ln( )xf x e x
1
( )
( )
nn n
n
f xx x
s x 1
1
( ) ( )( ) n n
n
n n
f x f xs x
x x
3 21.2854, 1.3974x x
1.2854 1.3974
3 2
3 2
( ) ( ) ln(1.2854) ln(1.3974)(1.2854) 1.0075
1.2854 1.3974
f x f x e es
x x
23 2
2
( ) 0.0251.2854 1.3106
( ) 1.0075
f xx x
s x
Método de la secanteEjemplo 1
Encontrar el cero de la función
( ) ln( )xf x e x
1
( )
( )
nn n
n
f xx x
s x
Método de Newton-Raphson
Método de Secante
El método de NR converge en menos iteraciones
Método de la secanteEjemplo 2
Encontrar el cero de la función
Iniciemos con
De donde obtenemos
2( ) 2f x x
1
( )
( )
nn n
n
f xx x
s x 1
1
( ) ( )( ) n n
n
n n
f x f xs x
x x
1 02, 1x x
2 2(2) (1) 2 2 1 2(2) 3
2 1 1
f fs
12 1
1
( ) 2 42 1.333333
( ) 3 3
f xx x
s x
Método de la secanteEjemplo 2
Encontrar el cero de la función
Iniciemos con
De donde obtenemos
2( ) 2f x x
1
( )
( )
nn n
n
f xx x
s x 1
1
( ) ( )( ) n n
n
n n
f x f xs x
x x
2 11.333333, 2x x
(1.3333) (2)(1.3333) 3.3333333
1.33333 2
f fs
23 2
2
( ) 0.22222221.333333 1.4
( ) 3.3333333
f xx x
s x
Comparación de todos los métodos
• El método de Newton-Raphson es el más rápidoen converger, en el sentido que necesita unmenor número de iteraciones para converger
• El método de Newton-Raphson es el método quepresente un mayor número de problemas deconvergencia
• La iteración del método de Newton-Raphson esla más costosa debido a que se debe evaluar lafunción y su derivada
• El método de bisección es el más robusto, pero ala vez es el método mas lento