View
230
Download
0
Embed Size (px)
Citation preview
MÉTODOS NUMÉRICOS
M. en C. José Andrés Vázquez Flores
Solución de una ecuación no lineal
“Cálculo de raíces”
Búsqueda de raíces
Consiste en obtener una raíz x de una ecuación de la forma
f(x) = 0
para una función f dada.
Al número x se le llama también cero de f.
Algoritmo de bisección o método de búsqueda binaria
Supongamos que f es una función continua definida en el intervalo [a,b] con f(a) y
f(b) de signos diferentes. De acuerdo con el teorema de valor intermedio, existe un
número p en (a,b) tal que f(p) = 0 .
Este procedimiento se aplica en el caso en que f(a) y f(p) tengan signos diferentes y
exista más de una raíz en el intervalo (a,b), por razones de simplicidad suponemos
que la raíz de este intervalo es única.
El método requiere dividir varias veces a la mitad los subintervalos de [a,b] y en
cada paso, localizar la mitad que contenga a p.
Algoritmo de bisección o método de búsqueda binaria
Para empezar, supongamos que a1=a y b1=b, y sea p1 el punto medio de [a,b] es
decir;
p1 = (1/2)(a1 + b1)
Si f(p1) = 0, entonces p = p1; de no ser así, entonces f(p1) tiene el mismo signo
que f(a1) o f(b1).
Si f(a1) y f(p1) tienen el mismo signo, entonces p ϵ (p1,b1) y tomamos a2=p1 y
b2=b1.
Si f(a1) y f(p1) tienen signos opuestos, entonces p ϵ (a1,p1) y tomamos a2=a1 y
b2=p1.
Después volvemos a aplicar este proceso al intervalo [a2,b2].
Esto nos da el siguiente algoritmo.
Algoritmo de bisección o método de búsqueda binaria
Para encontrar una solución de f(x)=0 dada la función continua f en el intervalo [a,b], donde f(a) y f(b) tienen signos opuestos:
ENTRADA extremos a,b; tolerancia TOL; máximo numero de iteraciones No.
SALIDA solución aproximada p o mensaje de fracaso.
Paso 1 Tomar i = 1
Paso 2 Mientras que i ≤ No seguir Pasos 3-6
Paso 3 Tomar p = a + (b - a) / 2 (Calcular pi)
Paso 4 Si f(p) = 0 ó (b - a) / 2 < TOL entonces
SALIDA (p); (Procedimiento completado satisfactoriamente)
PARAR
Paso 5 Tomar i = i + 1
Paso 6 Si f(a)f(p) > 0 entonces tomar a = p (Calcular ai, bi)
si no tomar b = p
Paso 7 SALIDA (“El método fracaso después de No iteraciones, No =“, No)
(Procedimiento completado sin éxito)
PARAR
Algoritmo de bisección o método de búsqueda binaria
Algoritmo de bisección o método de búsqueda binaria
f(x) = x3 + 4x2 – 10 [ä,b] = [1,2] │pn-1 – pn │ / │pn │ <10-4
n an bn pn f(pn)
1 1.0 2.0 1.5 2.3752 1.0 1.5 1.25 -1.796873 1.25 1.5 1.375 0.162114 1.25 1.375 1.3125 -0.848395 1.3125 1.375 1.34375 -0.350986 1.34375 1.375 1.359375 -0.096417 1.359375 1.375 1.3671875 0.032368 1.359375 1.3671875 1.36328125 -0.032159 1.36328125 1.3671875 1.365234375 0.00007210 1.36328125 1.365234375 1.364257813 -0.0160511 1.364257813 1.365234375 1.364746094 -0.0079912 1.364746094 1.365234375 1.364990235 -0.0039613 1.364990235 1.365234375 1.365112305 -0.00194
MÉTODO DE NEWTON RAPHSON
)x(f)x(f)xx)(x(f
xxsi
sissr
f(x)
x
MÉTODO DE NEWTON RAPHSON
Consiste en elegir un punto inicial cualquiera x1 como
aproximación de la raíz.
MÉTODO DE NEWTON RAPHSON
)x(f)x(f)xx)(x(f
xxsi
sissr
x1
f(x)
x
f(x1)
MÉTODO DE NEWTON RAPHSON
Consiste en elegir un punto inicial cualquiera x1 como
aproximación de la raíz y obtener el valor de la función por ese punto.
Trazar una recta tangente a la función por ese punto.
MÉTODO DE NEWTON RAPHSON
)x(f)x(f)xx)(x(f
xxsi
sissr
x1
f(x)
x
f(x1)
x2
MÉTODO DE NEWTON RAPHSON
Consiste en elegir un punto inicial cualquiera x1 como
aproximación de la raíz.
Obtener el valor de la función por ese punto y trazar una recta tangente a la función por ese punto.
El punto de intersección de esta recta con el eje de las abscisas (xr, 0), constituye una segunda aproximación
de la raíz.
MÉTODO DE NEWTON RAPHSON
)x(f)x(f)xx)(x(f
xxsi
sissr
x1
f(x)
x
f(x1)
x2
f(x2)
MÉTODO DE NEWTON RAPHSON
Consiste en elegir un punto inicial cualquiera x1 como
aproximación de la raíz.
Obtener el valor de la función por ese punto y trazar una recta tangente a la función por ese punto.
El punto de intersección de esta recta con el eje de las abscisas (xr, 0), constituye una segunda aproximación
de la raíz.
El proceso se repite n veces hasta que el punto de intersección xn coincide prácticamente con el valor
exacto de la raíz.
MÉTODO DE NEWTON RAPHSON
)x(f)x(f)xx)(x(f
xxsi
sissr
x1
f(x)
x
f(x1)
x2
f(x2)
MÉTODO DE NEWTON RAPHSON
Aunque el método trabaja bien, no existe garantía de convergencia.
MÉTODO DE NEWTON RAPHSON
Supóngase que la función f es continuamente diferenciable dos veces en el intervalo [a,b]; o sea f ε C2[a,b]. Sea ẋ ε [a,b] una aprox. A p ɟ f´ (ẋ)≠0 y | ẋ-p| es “pequeño”.
Consideremos el Pol. De Taylor de primer grado para f(x) alrededor de ẋ.
donde 𝜉(x) esta entre x y ẋ. Dado que f (p)=0 , con x=p tenemos:
2____
!2)(
))(´´())(´()()(xx
xfxxxfxfxf
2____
!2)(
))(´´())(´()(0xp
xfxpxfxf
Derivando el método de Newton suponiendo que, como |p- ẋ| es tan pequeño el termino
que contiene (p- ẋ)2 es mucho menor entonces podemos tomar:
Despejando p de esta ecuación obtenemos:
Esto prepara el método de Newton-Raphson, el cual comienza con una aproximación
inicial p0 y genera la sucesión {pn} definida como
para n ≥ 1
))(´()(0___
xpxfxf
MÉTODO DE NEWTON RAPHSON
_
__
)´(
)(
xf
xfxp
)´(
)(
1
1
1 pp
ppn
n
nn f
f
ALGORITMO DE NEWTON RAPHSON
Para encontrar una solución de f(x)=0 dada una aproximación inicial p0.
ENTRADA aproximación inicial p0 ; tolerancia TOL; máximo numero de iteraciones No.
SALIDA solución aproximada p o mensaje de fracaso.
Paso 1 Tomar i = 1
Paso 2 Mientras que i ≤ No seguir Pasos 3-6
Paso 3 Tomar p = p0 – f(p0) / f´(p0) (Calcular pi)
Paso 4 Si │p – p0 │ < TOL entonces
SALIDA (p); (Procedimiento completado satisfactoriamente)
PARAR
Paso 5 Tomar i = i + 1
Paso 6 Tomar p0 = p (Redefinición de p0, q0, p1, q1)
Paso 7 SALIDA (“El método fracaso después de No iteraciones, No =“, No)
(Procedimiento completado sin éxito)
PARAR
Método de la Secante
El método de la secante es un método para encontrar los ceros de una función de forma iterativa.
Es una variación del método de Newton-Raphson donde en vez de calcular la derivada de la función en el punto de estudio, teniendo en mente la definición de derivada, se aproxima la pendiente a la recta que une la función evaluada en el punto de estudio y en el punto de la iteración anterior.
Este método es de especial interés cuando el coste computacional de derivar la función de estudio y evaluarla es demasiado elevado, por lo que el método de Newton no resulta atractivo.
Por ejemplo:
f(x)=x23xcos(2x), entonces
f´(x)= 2x3xcos(2x)+x23x(cos(2x))ln3-2x23xsen(2x)
La cual es extremadamente tediosa de evaluar
El método se basa en obtener la ecuación de la recta que pasa por los puntos
(xn−1, f(xn−1)) y (xn, f(xn)). A dicha recta se le llama secante por cortar la gráfica de
la función.
Método de la Secante
En la imagen anterior se toman los puntos iniciales x0 y x1, se construye una línea por los puntos (x0, f(x0)) y (x1, f(x1)). En forma punto-pendiente.
Esta línea tiene la siguiente ecuación
Método de la Secante
Posteriormente se escoge como siguiente elemento de la relación de
recurrencia, xn+1, la intersección de la recta secante con el eje de abscisas
obteniendo la fórmula, y un nuevo valor. Seguimos este proceso, hasta llegar a
un nivel suficientemente alto de precisión (una diferencia lo suficientemente
pequeñas entre xn y xn-1).
Derivación del Método de la Secante
)(xf)f(x
- = xxi
iii ' 1
1
1 )()()(
ii
iii xx
xfxfxf
)()(
))((
1
11
ii
iiiii xfxf
xxxfxx
Método de Newton
Aproximación de la derivada
Sustitución de la ecuación 2 en la ecuación 1 nos da el Método de la Secante
(1)
(2)
Algoritmo del Método de la Secante
Para encontrar una solución de f(x)=0 dada la función continua f y unas aproximaciones iniciales p0, p1.
ENTRADA aproximaciones iniciales p0, p1; tolerancia TOL; máximo numero de iteraciones No.
SALIDA solución aproximada p o mensaje de fracaso.
Paso 1 Tomar i = 2; q0 = f(p0); q1 = f(p1)
Paso 2 Mientras que i ≤ No seguir Pasos 3-6
Paso 3 Tomar p = p1 – q1(p1 - p0) / (q1 - q0) (Calcular pi)
Paso 4 Si │p – p1 │ < TOL entonces
SALIDA (p); (Procedimiento completado satisfactoriamente)
PARAR
Paso 5 Tomar i = i + 1
Paso 6 Tomar p0 = p1 (Redefinición de p0, q0, p1, q1)
q0 = q1
p1 = p
q1 = f(p)
Paso 7 SALIDA (“El método fracaso después de No iteraciones, No =“, No)
(Procedimiento completado sin éxito)
PARAR
Ejemplo
MÉTODO DE LA REGLA FALSA
)x(f)x(f)xx)(x(f
xxsi
sissr
f(x)
x
MÉTODO DE LA REGLA FALSA
Consiste en considerar un intervalo (xi, xi+1) en el que se garantice que la función tiene raíz.
MÉTODO DE LA REGLA FALSA
)x(f)x(f)xx)(x(f
xxsi
sissr
xi Xi+1
f(x)
x
f(xi)
f(xi+1)
MÉTODO DE LA REGLA FALSA
Consiste en considerar un intervalo (xi, xi+1) en el que se garantice que la función tiene raíz.
Se traza una recta que une los puntos (xi, f(xi)), (xi+1, f(xi+1)).
MÉTODO DE LA REGLA FALSA
)x(f)x(f)xx)(x(f
xxsi
sissr
xi Xi+1
f(x)
x
f(xi)
f(xi+1)
MÉTODO DE LA REGLA FALSA
Consiste en considerar un intervalo (xi, xi+1) en el que se garantice que la función tiene raíz.
Se traza una recta que une los puntos (xi, f(xi)), (xi+1, f(xi+1)).
Se obtiene el punto de intersección de esta recta con el eje de las abscisas: (xr, 0); se toma xr como aproximación de la raíz buscada.
MÉTODO DE LA REGLA FALSA
)x(f)x(f)xx)(x(f
xxsi
sissr
xi xi+1xr
f(x)
x
f(xi)
f(xi+1)f(xr)
MÉTODO DE LA REGLA FALSA
Consiste en considerar un intervalo (xi, xi+1) en el que se garantice que la función tiene raíz.
Se traza una recta que une los puntos (xi, f(xi)), (xi+1, f(xi+1)) y se obtiene el punto de intersección de esta recta con el eje de las abscisas: (xr, 0); se toma xr como aproximación de la raíz buscada.
Se identifica luego en cuál de los dos intervalos está la
raíz.
MÉTODO DE LA REGLA FALSA
)x(f)x(f)xx)(x(f
xxsi
sissr
xi xi+1xr
f(x)
x
f(xi)
f(xi+1)f(xr)
rxx =i+1
MÉTODO DE LA REGLA FALSA
Consiste en considerar un intervalo (xi, xi+1) en el que se garantice que la función tiene raíz.
Se traza una recta que une los puntos (xi, f(xi)), (xi+1, f(xi+1))Se obtiene el punto de intersección de esta recta con el eje de las abscisas: (xr, 0); se toma xr como aproximación de la raíz buscada.
Se identifica luego en cuál de los dos intervalos está la
raíz.
El proceso se repite n veces, hasta que el punto de
intersección xr coincide prácticamente con el valor
exacto de la raíz.
MÉTODO DE LA REGLA FALSA
)x(f)x(f)xx)(x(f
xxsi
sissr
xi xi+1xr
f(x)
x
f(xi)
f(xi+1)f(xr)
)x(f)x(f
)xx)(x(fxx
ii+1
ii+1i+1
i+1r -
--=
ALGORITMO DE LA REGLA FALSA
ENTRADA aproximaciones iniciales (p0,p1) = (a,b) ; tolerancia TOL; máximo numero de iteraciones No.
SALIDA solución aproximada p o mensaje de fracaso.
Paso 1 Tomar i = 2; q0 = f(p0); q1 = f(p1)
Paso 2 Mientras que i ≤ No seguir Pasos 3-6
Paso 3 Tomar p = p1 – q1(p1 - p0) / (q1 - q0) (Calcular pi)
Paso 4 Si │p – p1 │ < TOL entonces
SALIDA (p); (Procedimiento completado satisfactoriamente)
PARAR
Paso 5 Tomar i = i + 1 , q = f(p)
Paso 6 Si q * q1 < 0 entonces
Tomar p0 = p (Redefinición de p0, q0, p1, q1)
q0 = q
Si no p1 = p
q1 = q
Paso 7 SALIDA (“El método fracaso después de No iteraciones, No =“, No)
(Procedimiento completado sin éxito)
PARAR