03_Raices_de_funciones_no_lineales

Vista previa del material en texto

NOTAS DE CLASE
Tema: Raíces de Ecuaciones no Lineales
 
Iteración de punto fijo
Bisección
Falsa posición
Newton
Secante
27/10/2020
 
f ( x )=0 x=?
• Método Iterativo de Punto Fijo
• Método Bisección
• Método Falsa posición
• Método de Newton-Raphson
• Método de la Secante
Problema:
MÉTODO ITERATIVO DE PUNTO FIJO
f ( x )=0 x=?
g( x )=x x=?
problema original
reescribimos
Dado f:   , encontrar P 
tal que P = g(P).
0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
-5
-3
-1
1
3
5
0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
1
2
3
4
5
raíz
p. fijo
y=x
f(x)
g(x)
Definición:
Se dice que P es un punto fijo 
de la función g
f ( x )=x−cos ( x )=0
x−cos ( x )=0 → {
x=cos ( x )
x= arccos ( x )
x=x−
x−cos ( x )
1+sin ( x )
}
EJEMPLO
punto fijo
x=g( x )
Más de una GENERATRIZ posible ….
g: GENERATRIZ
Tiene una única raíz en [0,1]
Ejemplo 1 Ingrese en su calculadora el valor 0.7 y 
presione repetidamente la función COS
Qué ocurre?
Ejemplo 2 Ahora presione repetidamente la función 
ACOS (o inv COS)
Qué sucede?
x0 x2 x1
x2 x0 x1
ITERACIÓN DE PUNTO FIJO
Teorema 1:
pn+1=g( pn ) con n=0,1, .. .
Definición:
Teorema 2: 
a) Existencia: Si g es continua en [a,b] y la imagen y=g(x) verifica que y 
 [a,b] para cada x  [a,b],], entonces g tiene un punto fijo en [a,b].
b) Unicidad: Suponiendo que g’(x) está definida en (a,b) y que |g’(x)| < 
1 para toda x  (a,b), entonces g(x) tiene un único punto fijo P en [a,b].
CONVERGENCIA
Teorema 3: 
Sea g(x) y g’(x) continuas en [a,b], g(x)  [a,b],] para cada x  [a,b],], K una 
constante positiva y p0  (a,b],):
Convergencia: Si |g’(x)|  K < 1 para todo x  [a,b],], entonces P es el único 
punto fijo de g en [a,b],] y la iteración pn = g(pn-1) (n=1,2,…) converge hacia el 
punto fijo P (punto fijo atractivo).
Divergencia: Si |g’(P)| > 1 y p0 ≠ P, entonces la iteración pn = g(pn-1) (n=1,2,…) 
no converge a P (punto fijo repulsivo).
punto fijo
CUÁL ELIJO ?
x0 x2 x1 x2 x0 x1 x0 x2 x1
g' ( x )=−sin( x ) g' ( x )=−
1
√1− x2
g´ ( x )=
( x−cos ( x ))cos ( x )
(1+sin( x ))2
−1≤g ' (P )<0 g' (P )<−1
I II III
g' (P )=0
g( x )=cos ( x ) g( x )=arccos( x ) g( x )=x−
x−cos( x )
1+sin( x )
EJEMPLO
Aplicar el Teorema 2 para probar rigurosamente que g(x)=cos(x) tiene 
un único punto fijo en [0,1].
Solución:
g=cos(x) pertenece a C[0,1] y es una función decreciente en [0,1], por 
lo que su imagen g([0,1]) es [cos(1),1]  [0,1]. Esto prueba que se 
cumple la primera condición del teorema 2, así que g tiene un punto 
fijo en [0,1]. 
Finalmente, si x (0,1), entonces |g’(x)| = |-sin(x)|=sin(x)  sin(1)  
0.8415 < 1. Por consiguiente, la segunda condición del teorema 2 se 
cumple y el punto fijo de g en [0,1] es único.
ACOTACIÓN DEL ERROR
Si g(x) verifica las hipótesis de convergencia del teorema 3, entonces 
las siguientes desigualdades proporcionan cotas del error que se 
comete al considerar a pn como aproximación a P
|P− pn|≤K
n
|P− p0| para todo n≥1
|P−pn|≤
K n|p1−p0|
1−K
para todo n≥1
INTERPRETACIÓN GEOMÉTRICA: CONVERGENCIA
Convergente
monótona
0<g' (P )<1
xx
e x1x0
y
x2
Convergente
oscilante
−1<g ' (P )<0y=x
INTERPRETACIÓN GEOMÉTRICA: DIVERGENCIA
xe
x1x0
y
x2
Divergente
oscilante
g' (P )<−1
x
Divergente
monótona
1<g ' (P)
PUNTO FIJO
PASO 1
PASO 2
PASO 3
x1=g (x0 )Calculo un nuevo punto
Sigo? Si |x1 − x0| < tol, detengo el proceso y retorno el 
valor de x1 como respuesta
Actualizo xo ← x1. Retorno al paso 1
xn=g (x n−1 )Fórmula de recurrencia
ALGORITMO Dada una función g en [a, b],], un punto de 
arranque xo  [a,b],] y una tolerancia (tol)
EJEMPLO Sea la función f(x) = x – e1/x en [0.5,5].
La ecuación f(x) = x – e1/x = 0 puede reordenarse de varias
formas de manera de generar diferentes funciones g(x)
g( x )=e1/x
g( x )=
1
ln( x )
g( x )=
x+e1 /x
2
I
II
III
III
III
Tarea:
Calcular las derivadas de las funciones generatrices y escrib],ir un código Fortran90
que implemente el método de punto fijo para ob],tener la raíz de f(x) en [0.5,5]
f (r )=0 r=?
• Método Bisección
• Método Falsa posición
Problema:
TEOREMA DEL VALOR INTERMEDIO O DE BOLZANO
Dado un intervalo [a,b] en el cual la función f es continua y satisface 
que su signo en a sea distinto de su signo en b, entonces existe al 
menos un punto c, llamado raíz, tal que f(c) = 0.
f(x)
x
a
b],
Actualizo el intervalo. 
Si el sign(f(c)) = sign(f(a)), entonces 
a ← c y f(a) ← f(c), 
si no b], ← c y f(b],) ← f(c). 
Retorno al paso 1
BISECCIÓN
IDEA
ALGORITMO Dada una función f en [a, b], 
con sign(f(a)) ~= sign(f(b)), 
y una tolerancia (tol)
Dividir el intervalo en mitades y tomar el valor medio como
aproximación a la raíz
PASO 1
PASO 2
PASO 3
Calcular un nuevo punto 
c = (a + b)/2
Sigo? Si |b], − a| /2 < tol ó |f(c)| < tol, 
detengo el proceso y 
retorno el valor de c como respuesta
f(x)
x
a
b],
c
Método de bisección:
Err(n) <= (b],-a)/2n <= tol
…
n >= ln[ (b],-a) / tol ] / ln(2)
Cota de error, Err(n), y n necesario para satisfacer tolerancia, tol
• pobre velocidad de convergencia
• necesidad de intervalo acotado
• existencia de otros métodos más rápidos
Ventajas
Desventajas
• convergencia garantizada
• acotación del error en función del
 número de iteraciones
FALSA POSICIÓN
f(x)
x
a=a1=a2=a3 b],
c=b],1c=b],2c=b],3
Si f”(x) ≠ 0 en [a, b] entonces uno de los extremos es estacionario
c=b−
f (b ) (b−a )
f (b )−f (a )
r ) y = f(b],) + [ f(a) - f(b],) ] * ( b],-x ) / (b],-a)
y=0 → x=c
r
IDEA
ALGORITMO
PASO 1
PASO 2
PASO 3
Similar a Bisección pero reemplaza el punto medio por el 
punto en el cual la recta secante corta al eje x.
c=b−
f (b ) (b−a )
f (b )−f (a )
Calculo un nuevo punto
Dada una función f en [a, b], 
con sign(f(a)) ~= sign(f(b)), 
y una tolerancia (tol)
Actualizo el intervalo. 
Si el sign(f(c)) = sign(f(a)), entonces a ← c y f(a) ← f(c),
 si no b], ← c y f(b],) ← f(c). 
Almaceno el valor calculado de c en c
prev
Retorno al paso 1
Sigo? Si |c − c
prev
| < tol Y |f(c)| < tol, 
detengo el proceso y retorno el valor de c como respuesta
FALSA POSICIÓN
REQUIERE INTERVALO 
DONDE f CAMBIA DE SIGNO !!! 
MÉTODO DE NEWTON
NO REQUIERE INTERVALO 
DONDE f CAMBIA DE SIGNO !!! 
f’(x
n
) = f(x
n
) / (x
n
 – x
n+1
)
ó
x
n
-x
n+1
 = f(x
n
) / f’(x
n
)
ó
x
n+1
 = x
n
- f(x
n
) / f’(x
n
)
IDEA
ALGORITMO
PASO 1
PASO 2
PASO 3
MÉTODO DE NEWTON
Utilizar la derivada de f para encontrar la pendiente de 
la línea que aproxima a f
Dada una función f en [a, b],], y f’ ≠ 0 en [a,b],], 
un punto de arranque xo y 
una tolerancia (tol)
x1=x0−
f (x0 )
f ' ( x0)
Calculo un nuevo punto
Sigo? Si |x1 − x0| < tol Y |f(x1)| < tol, 
detengo el proceso y retorno el valor de x1 como respuesta
Actualizo xo ← x1 . Retorno al paso 1
xn=xn−1−
f ( xn−1 )
f ' (xn−1)
Fórmula de recurrencia
Qué puedo hacer si el cálculo de la derivada no está disponible ó 
es muy laborioso …?
Aproximo numéricamente el cálculo de la/las derivada/s
f ' (x0 )≈
f ( x0+h )−f (x0−h )
2h
f '' (x0 )≈
f (x0+h )−2 f (x0 )+f ( x0−h )
h2
Fórmulas CENTRADAS
MÉTODOS DE NEWTON
con
DERIVACIÓN NUMÉRICA
f, f’, f’’ son continuas en [a,b] y f’ ≠ 0 en [a,b],]CONVERGENCIA
xK=xK−1−
f (xK−1)
f ' ( xK−1 )⏟
g ( x
K−1
)
k=1,2, .. g( x )=x−
f ( x )
f ' (x )
g(x) :Función de iteración de Newton
i.e. converge para cualquier x0  (a,b), a,b), 
si g(a,b), x) y g’(a,b), x) continuas en [a,b] → requiere continuidad de f’’, 
 g(a,b), x)  [a,b] para todo x  [a,b]
 |g’(a,b), x)| <= K < 1 para todo x  [a,b]
Condición de convergencia dictada por los teoremas vistos para el método de punto fijo
aplicados a la función de iteración de Newton !!!
Iteración de punto fijo de la función g 
La derivada segunda de la función no se anula 
en un intervalo [a,b],] que contenga a la raíz.
a b],
Si f(a) y f’’(a) tienen igual signo el punto de arranque 
adecuado es a, y en caso contrario es b
IMPORTANTE:f’’(x) ≠ 0 en [a,b]
HIPOTESIS ADICIONAL:
CUATRO CASOS POSIBLES:
• convergencia cuadrática cerca de una raíz simple
• convergencia lineal cerca de una raíz múltiple
• método iterativo puede diverger
• requiere evaluar la derivada
• no es fácil de acotar
Ventajas
Desventajas
X
f(x)
1kx kx *x
|xk+1−x k|<tol ?
|f (xk+1 )|<tol ?
X
f(x)
1kx  kx
*x
MÉTODO DE NEWTON
PROXIMIDAD
El punto de arranque xo debe estar lo suficientemente 
próximo a la raíz x*
X* X2 X1 X0
X
f(x)
ELECCIÓN DEL VALOR INICIAL
X
f(x)
0x
1x
2x 0x
1x
convergente
divergente
f(x)
X
Convergencia a ∞
Oscilación
VELOCIDAD DE CONVERGENCIA
Supongamos que la sucesión {xn} , n=0,1,… converge a x 
y sea En = x-xn para n ≥ 0. Si existen dos constantes A > 0 y R > 0 tal que
R velocidad (orden) de convergencia
A constante asintótica del error
R=1, se dice que la convergencia es lineal
R=2, se dice que la convergencia es cuadrática
VELOCIDAD DE CONVERGENCIA DEL MÉTODO DE NEWTON ?
| E
n+1
 | = A | E
n
 | R
VELOCIDAD DE CONVERGENCIA MÉTODO DE NEWTON
Desarrollo de Taylor alrededor de x
i
 evaluado en x
r
:
0 = f(x
r
) = f(x
i
) + f’(x
i
) * (x
r
-x
i
) + f’’(ξ) / 2! * (x
r
-x
i
)2 con ξ entre x
i
 y x
r
Además:
0 = f(x
i
) + (x
i+1
 – x
i
) * f’(x
i
)
Resto m.a.m. y llamo: E
i
 = x
r
 – x
i
 (error paso i-ésimo)
0 = f’(x
i
) * (x
r
-x
i
-x
i+1
+x
i
) + f’’(ξ) / 2! * E
i
2 ó f’(x
i
) * E
i+1
 = -f’’(ξ) / 2! * E
i
2
Si converge, x
i
 ~ ξ~ x
r
 y si f’(x
r
) /= 0 (x
r
 raíz simple):
E
i+1
 = -f’’(x
r
)/(2*f’(x
r
)) * E
i
2 → Convergencia cuadrática
Para raices múltiples la convergencia es lineal
METODO DE LA SECANTE
Si inicialmente tomamos dos x distintas ( x
0
 , x
1
 ) y usamos la secante de f(x) en x
0
 y x
1
(en lugar de la tangente en x
1
) para estimar x
2
IDEA
ALGORITMO
PASO 1
PASO 2
PASO 3
Aproximar la función por su línea secante utilizando 
siempre los dos puntos más recientes
Dada una función f en [a, b],], un par de puntos xo x1 y una 
tolerancia (tol)
x2=x1−
f (x1 )( x1−x0 )
f (x1 )−f ( x0)
Calculo un nuevo punto
Sigo? Si |x2 − x1| < tol Y |f(x2)| < tol, 
detengo el proceso y retorno el valor de c como respuesta
Actualizo xo ← x1; x1 ← x2 . Retorno al paso 1
METODO DE LA SECANTE
Ventajas
Desventajas
• mejora la convergencia en la proximidad de una raíz simple
• mantiene convergencia lineal para raíces múltiples
• no requiere de derivada
• método iterativo puede diverger
• no es fácil de acotar
METODO DE LA SECANTE
 No utilice f(a) ∗ f(b) > 0 para verificar si el signo f(a) coincide con el 
de f(b). Utilice sign(f(a)) = sign(f(b))
Puede llevar a Underflow.
 Un nuevo valor iterado puede ser igual a uno anterior si la diferencia 
entre a y b es muy pequeña.
 La cantidad (b − a)/(f(b) − f(a)) en el método de la secante puede 
llevar a un Overflow, lo mismo en el caso de utilizar diferenciación 
numérica.
ERROR DE REDONDEO
Método Nuevo punto Actualiza
Bisección Parte al medio Retiene dos 
puntos que acotan 
la raíz
Falsa posición Traza una línea Retiene dos 
puntos que acotan 
la raíz
Secante Traza una línea
(secante)
Retiene los dos 
últimos puntos
Newton Traza una línea
(tangente)
Retiene el punto 
más reciente
COMPARACIÓN ENTRE MÉTODOS - ALGORITMOS
Método Convergencia Velocidad de 
convergencia
Bisección Garantizada Lenta |En+1|=O(|En|) 
|En+1| (b-a)/2n+1
Falsa posición Garantizada Puede ser lenta
|En+1|=O(|En|)
Secante No garantizada Rápida
|En+1|=O(|En|(1+5)/2)
Newton No garantizada Rápida
|En+1|=O(|En|2)
COMPARACIÓN ENTRE MÉTODOS - CONVERGENCIA
 
FIN NOTAS DE CLASE
	Diapositiva 1
	Diapositiva 2
	Diapositiva 3
	Diapositiva 4
	Diapositiva 5
	Diapositiva 6
	Diapositiva 7
	Diapositiva 8
	Diapositiva 9
	Diapositiva 10
	Diapositiva 11
	Diapositiva 12
	Diapositiva 14
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 25
	Diapositiva 27
	Diapositiva 31
	Diapositiva 32
	Diapositiva 34
	Diapositiva 36
	Diapositiva 37
	Diapositiva 40
	Diapositiva 41
	Diapositiva 42
	Diapositiva 43
	Diapositiva 44
	Diapositiva 45
	Diapositiva 50
	Diapositiva 51
	Diapositiva 54
	Diapositiva 55
	Diapositiva 56
	Diapositiva 57
	Diapositiva 59