Raices

Vista previa del material en texto

Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Cálculo Avanzado-Fundamentos para el
Análisis de Señales
Docentes: Cavalieri Federico - Contini Liliana
Ayudantes: Fabio Tibaldo - Maciel Martı́n
Cálculo de Raı́ces de Ecuaciones
August 9, 2014
mailto:cavafede@gmail.com
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Motivación
Se sabe que para resolver una ecuación cuadrática del tipo
ax2 + bx + c = 0
se dispone de la siguiente expresión analı́tica
x =
−b±
√
b2 − 4ac
2a
(1)
A los valores calculados por la Ec.(1) se les llama “raı́ces” de la
ecuación.
Por lo tanto, se define la raı́z de una ecuación como
el valor de x que hace f(x) = 0
Aunque la Ec.(1) es muy útil, existen muchas funciones donde las
raı́ces no se pueden determinar tan fácilmente, i.e. f(x) = e−x − x.
En estos casos, los métodos numéricos proporcionan medidos
eficientes para obtener la respuesta.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
METODOS CERRADOS
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Métodos Cerrados
Se estudiará primero la raı́ces de ecuaciones por medio de métodos
que aprovechan el hecho de que una función cambia de signo en el
en entorno de una raı́z.
A estas técnicas se las denomina: Métodos Cerrados o de
Intervalos. En estos métodos
Se necesita de dos valores iniciales para encontrar la raı́z.
Dichos valores iniciales deben encerrar o estar a ambos lados de la
raı́z.
Se estudiarán los siguientes métodos:
Interpretación gráfica.
Bisección.
Falsa Posición (Regula Falsi.)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Interpretación Gráfica
La siguiente figura muestra algunas de las formas donde la
raı́z/raı́ces de f(x) puede encontrarse (o no), en un intervalo definido
por un lı́mite inferior xl y un lı́mite superior xu.
No tiene raı́z. f(xl) y f(xu). Tienen el mismo signo.
Tiene una raı́z. f(xl) y f(xu). No tienen el mismo signo.
Tiene un número par de raı́ces. f(xl) y f(xu). Tienen el mismo signo.
Tiene un número impar de raı́ces. f(xl) y f(xu). No tiene el mismo
signo.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Interpretación Gráfica. Excepciones
f(xl) y f(xu) tienen signos opuestos. Hay un número par de raı́ces.
f(xl) y f(xu) tienen signos opuestos. Hay un número par de raı́ces.
Se requiere de estrategias especiales para determinar las raı́ces de
estos casos.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Todo muy lindo, pero ¿Cómo encontramos
la raı́z de una función a partir de lo dicho
hasta el momento en forma práctica?
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
En forma gráfica
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Método de la Bisección
De las conclusiones obtenidas se observó lo siguiente:
en general, si f(x) es real y continúa en el intervalo [xl, xu] y
f(xl) y f(xu) tienen signos opuestos, es decir,
f(xl)f(xu) < 0→ hay al menos una raı́z real entre xl y xu.
PASO I. Elija valores iniciales: xl y xu que encierren a la raı́z, de forma
tal que f(xl)f(xu) < 0.
PASO II. Elija un punto medio xr de [xl; xu], por ejemplo:
xr =
xl + xu
2
PASO III. Realice las siguientes evaluaciones:
si: f(xl)f(xr) < 0 hacer: xu = xr . Retorne al PASO II.
si: f(xl)f(xr) > 0 hacer: xl = xr . Retorne al PASO II.
si: f(xl)f(xr) = 0 la raı́z es igual a xr . Fin del cálculo.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Planteamiento del problema en forma
manual. Ejemplo
Emplear el método de la bisección para obtener la constante c de la
ecuación:
f(c) =
667.38
c
(1− e−0.146843c)− 40 = 0
PASO I. xl = 12 y xu = 16 y además f(xl)f(xu) < 0.
PASO II. xr = (xl + xu)/2 = 14→xr = (12 + 16)/2 = 14
PASO III. f(12)f(14) = 9.517 > 0.
Se retorna al PASO II. xl = xr = 14 y entonces xr = (14 + 16)/2 = 15
PASO III. f(14)f(15) = −0.666 < 0.
Se retorna al PASO II. xu = xr = 15 y entonces xr = (14 + 15)/2 = 14.5
El error relativo porcentual es
‖εa‖ = ‖
xnuevor − xanteriorr
xnuevor
‖ × 100 = ‖14.5− 15
14.5
‖ × 100 = 3.4%.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
1 clear all clc xl=12; xu=16; imax=16; xr=0; epsilon=1000;
2 epsilon_usuario=0.001; format long for i=1:imax
3 if (epsilon < epsilon_usuario)
4 break;
5 else
6 xr_old=xr;
7 xr= (xl+xu)/2;
8 test = f(xl)*f(xr);
9 if test < 0
10 xu=xr;
11 elseif test > 0
12 xl=xr;
13 else
14 epsilon=0
15 end
16
17 if(xr˜=0)
18 epsilon=abs((xr-xr_old)/xr)*100;
19 epsilonAbsoluto= (xu-xl)*100;
20 end
21 end
22 end
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Consideraciones sobre el error
Antes de empezar las iteraciones (o iteración 0), el error absoluto
será:
E0a = x
0
u − x0l
Después de la primera iteración
E1a =
x0u − x0l
2
=
∆x0
2
Debido a que en cada iteración el error se reduce a la mitad, la
fórmula general que relaciona el número de iteraciones i y el error es
Eia =
∆x0
2i
y el número de iteraciones en función de un error dado es
i = log2
(∆x0
Ea
)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Método de la Falsa Posición (Regula-Falsi)
Un inconveniente del método de la bisección es que al dividir el
intervalo de xl a xu en mitades iguales, no se toman en
consideración las magnitudes de f(xl) y f(xu). Por ejemplo, si f(xl)
está mucho más cercana a cero que f(xu), es lógico pensar que la
raı́z se encuentre más cerca de xl que de xu.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Utilizando semejanza de triángulos, la intersección de la lı́nea recta
con el eje x se estima mediante la siguiente expresión:
f(xl)
xr − xl
=
f(xu)
xr − xu
=⇒ xr = xu −
f(xu)(xl − xu)
f(xl)− f(xu)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Planteamiento del problema en forma
manual. Ejemplo
Emplear el método de Regula-Falsi para obtener la constante c de la
ecuación:
f(c) =
667.38
c
(1− e−0.146843c)− 40 = 0
Primera Iteración. xl = 12 y xu = 16. Entonces f(12)=6.0699 y
f(16)=-2.2688. Luego xr = 14.9113
Segunda Iteración. f(xl)f(xr) = −1.5426. La raı́z se encuentra en el
primer subintervalo y xr. Luego, xu = 14.9113 y f(xu) = −0.2543.
Además: xl=12 y f(xl) = 6.069. Finalmente: xr = 14.7942
El error relativo porcentual es
‖εa‖ = ‖
xnuevor − xanteriorr
xnuevor
‖×100 =‖ 14.9113− 14.7942
14.7942
‖ ×100 = 0.79%.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
METODOS ABIERTOS
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Consideraciones
En los métodos cerrados
la raı́z se encuentra dentro de un intervalo predeterminado por un
lı́mite inferior y otro superior. La aplicación repetida de estos
métodos siempre genera aproximaciones cada vez más cercanas a
la raı́z. Se dice que tales métodos son convergentes porque se
acercan progresivamentea la raı́z a medida que se avanza en el
cálculo.
En contraste, los métodos abiertos
se basan en fórmulas que requieren únicamente de un solo valor de
inicio x0 o que empiecen con un par de ellos, pero que no
necesariamente encierran la raı́z. Éstos, algunas veces divergen
o se alejan de la raı́z verdadera a medida que se avanza en el
cálculo. Sin embargo, cuando los métodos abiertos convergen, en
general lo hacen mucho más rápido que los métodos cerrados.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Se estudiarán los siguientes métodos
abiertos
Iteración simple de punto fijo.
Método de Newton Raphson.
Método de Newton Raphson para sistemas de ecuaciones no lineales.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Punto Fijo
Arreglar la ecuación f(x) = 0 de tal modo que x esté del lado izquierdo
de la ecuación: x = g(x).
Esta transformación se realiza mediante operaciones algebraicas
simples o simplemente sumando x a cada lado de la ecuación original.
Por ejemplo sen(x) = 0 puede transformarse en la forma de x = g(x),
sumando x a ambos miembros. x = sen(x) + x
La utilidad de la ecuación es que proporciona una fórmula para predecir
un nuevo valor de xi en función del valor anterior de xi+1.
Fórmula General de Punto Fijo
xi+1 = g(xi)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Error aproximado en punto Fijo
Como en otras fórmulas anteriores, el error aproximado de esta
ecuación se calcula usando el error normalizado
εa = ‖
xi+1 − xi
xi+1
‖ × 100
Localice la raı́z de la función f(x) = e−x − x. Utilice la fórmula de
punto fijo xi+1 = e−xi
Iteración xi εa
1 0
2 1 100
3 0.36 171.8
4 0.69 46.9
10 0.5648 1.11
Table: Iteración de punto fijo.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Además de la velocidad de convergencia, en este momento se debe
enfatizar en la posibilidad de convergencia. Estos dos conceptos se
pueden estudiar gráficamente.
Un método gráfico alternativo consiste en separar la f(x) = 0 en dos
partes, de esta manera, f1(x) = f2(x). De este modo
y1(x) = f1(x) y2(x) = f2(x)
Por ejemplo. Suponga que tiene la siguiente ecuación e−x − x = 0,
entonces, e−x = x. Luego: y1 = x y y2 = ex
Luego se grafican por separado.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Ası́, los valores de x correspondientes a las intersecciones de estas
dos funciones representan las raı́ces de f(x) = 0.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
En el primer paso, el valor inicial x0 sirve para determinar el punto
[x0, g(x0)] correspondiente a a curva y2. El punto (x1, x1) se obtiene
moviéndose horizontalmente a la izquierda hasta la curva y1. Estos
movimientos son equivalentes a la primera iteración de punto fijo.
x1 = g(x0)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Convergencia del método de punto fijo
se debe notar que la iteración de punto fijo converge
si en la región de interés ‖g′(x)‖ < 1.
Demostración. Partimos de la ecuación iterativa:
xi+1 = g(xi) (2)
Suponga que la solución verdadera es
xr = g(xr) (3)
Restando miembro a miembro la Ec.(2) con la Ec.(3)
xr − xi+1 = g(xr)− g(xi) (4)
Luego, a partir del teorema del valor medio
g′(ξ) =
g(b)− g(a)
b− a (5)
y haciendo a = xi y b = xr
g(xr)− g(xi) = (xr − xi)g′(ξ) (6)
donde ξ se encuentra en alguna parte del intervalo xi y xr.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Sustituyendo la Ec.(6) en la Ec.(4)
xr − xi+1 = (xr − xi)g′(ξ) (7)
Si se define como error verdadero a
Et,i = xr − xi (8)
entonces la Ec.(7) es
Et,i+1 = g′(ξ)Et,i (9)
En consecuencia
‖g′(x)‖ < 1. Los errores disminuyen en cada iteración.
‖g′(x)‖ > 1. Los errores crecen en cada iteración.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Divergencia del método: iteración de punto
fijo
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
El método de Newton-Raphson
Tal vez, de los métodos para encontrar raı́ces, la fórmula de
Newton-Raphson sea la más utilizada. Para deducir la fórmula se
utilizará un método gráfico y otro analı́tico.
Método gráfico. El punto donde la tangente a la curva, evaluada en
xi, cruza al eje x representa una aproximación mejorada de la raı́z.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
La pendiente de la recta tangente evaluada en el punto xi es
f ′(xi) =
f(xi)− 0
xi − xi+1
(10)
despejando xi+1 se obtiene
la conocida fórmula de Newton-Raphson
xi+1 = xi −
f(xi)
f ′(xi)
(11)
Método analı́tico
Además de la deducción geométrica, el método de Newton-Raphson
también se desarrolla a partir de la expansión de la serie de Taylor,
f(xi+1) = f(xi) + f ′(xi)(xi+1 − xi) +
f ′′(ξ)
2!
(xi+1 − xi)2 (12)
donde ξ se encuentra en alguna parte del intervalo [xi;xi+1].
Truncado la serie de Taylor después del primer término de la primera
derivada se tiene,
f(xi+1) = f(xi) + f ′(xi)(xi+1 − xi) (13)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
En la intersección con el eje x, f(xi+1) debe ser cero o
0 = f(xi) + f ′(xi)(xi+1 − xi) (14)
de donde se puede despejar xi+1. Entonces se obtiene
la conocida fórmula de Newton-Raphson
xi+1 = xi − f(xi)f ′(xi)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Análisis del Error en el método de
Newton-Raphson
En la situación que xi+1 = xr, donde xr es el valor verdadero de la
raı́z, entonces f(xr) = 0, o bien
0 = f(xi) + f ′(xi)(xr − xi) +
f ′′(ξ)
2!
(xr − xi)2 (15)
Si restamos la Ec.(14) la Ec.(15) se tiene
0 = f ′(xi)(xr − xi+1) +
f ′′(ξ)
2!
(xr − xi)2 (16)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Luego, el error es igual a la diferencia entre el xi+1 y el valor
verdadero xr, esto es
Et,i+1 = (xr − xi+1) (17)
y la Ec.(16) se re-escribe como
0 = f ′(xi)Et,i+1 +
f ′′(ξ)
2!
(Et,i)2 (18)
que reordenando se obtiene
el error del método Newton-Raphson
Et,i+1 = − f
′′(r)
2f ′(xr)
(Et,i)2
Notar que el error es proporcional al cuadrado del error anterior, a
este comportamiento se lo llama convergencia cuadrática.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Algunos problemas de convergencia del
método Newton-Raphson
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Algunos problemas de convergencia del
método Newton-Raphson
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Algunos problemas de convergencia del
método Newton-Raphson
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Pero, ¿qué pasa cuando comparamos la
convergencia de los métodos estudiados?
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Algunosproblemas de convergencia del
método Newton-Raphson
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Método de Newton-Raphson
Se pretende obtener las raı́ces de un sistema de ecuaciones
simultáneas, 
f1(x1, x2, . . . , xn) = 0
f2(x1, x2, . . . , xn) = 0
f3(x1, x2, . . . , xn) = 0
...
fn(x1, x2, . . . , xn) = 0
(19)
o equivalentemente
F (x∗) = 0 (20)
donde x∗ es el vector solución del sistema de ecuaciones.
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
Si expandimos F (x∗) = 0 para obtener un polinomio de Taylor
F (x∗) = 0 = F (x0) +∇F (x0) · (x∗ − x0) + O(h2) (21)
donde x0 es una estimación inicial. Despreciando los términos de
orden cuadrático se tiene
0 = F (x0) + J(x0) ·∆x (22)
donde J = ∇F es la denominada matriz jacobiana y ∆x = x∗ − x0.
Luego,
∆x = −J(x0)−1F (x0) (23)
En forma iterativa
el método de Newton-Raphson se escribe como
xi+1 = xi − J(xi)−1F (xi) (24)
Introducción Interpretación Gráfica Método de la Bisección Regula-Falsi Punto Fijo Newton Sistema de ecuaciones no lineales
FIN DE LA PRESENTACION
	Introducción
	Interpretación Gráfica
	Método de la Bisección
	Regula-Falsi
	Punto Fijo
	Newton
	Sistema de ecuaciones no lineales