METODO DE LA BISECCIÓN
Es un algoritmo de búsqueda de raíces que trabaja dividiendo el intervalo a la mitad y seleccionando el subintervalo que tiene la raíz. Este es uno de los métodos más sencillos y de fácil intuición para resolver ecuaciones en una variable. Se basa en el teorema de BOLZANO
Teorema de BOLZANO
#Sea y = f(x) continua en un intervalo [a,b] y supongamos que
f(x) tenga signos opuestos en a y b es decir f(a)*f(b)<0
Entonces debe existir r en [a,b] tal que tal que f(r)=0,
es decir, debe haber por lo menos una raíz en el intervalo.
Ejemplo: considere la función y= x^2-2. (Ver grafica)
grafica
En esta gráfica podemos visualizar que entre 0 y 2 hay un cambio de signo de f(x). Por lo tanto segun el teorema de Bolzano existe una raiz de f(x) entre x=2 y x=4
SCRIPT PARA DETECTAR PARES DE VALORES CON SIGNOS DIFERENTES
y=function(x) x^2-2
for(x in -5:5)
{z=-y(x)*y(x+1)
if(z<0) {cat ("cambio de signo detectado entre ", x ,"y",x+1)
stop()}
}
METODO BISECCION Vamos a implementar el script con f(x)=x^2-2
#valores iniciales. Se toman 2 valores iniciales arbitrarios a y b tales que sus imagenes #tengan signos diferentes es decir f(a)*f(b)<0. Para esto es bueno dibujar la curva
#dibujo de la curva
f=function(x) x^2-2
curve(f, from=-5,to=5,col="red")
abline(h=0,col="blue")
Apoyándonos en el dibujo podemos seleccionar a=0 y b=2, ya que f(0)=-2 y f(2)=2
a=0; b=2; N=20; E=0.01
#ciclo iteractivo
xant=0
for ( i in 1:N){ xm=(a+b)/2
err=abs(xm-xant)
cat("\n","iteracion",i)
cat("\n","a,b,xm",a,b,xm,"imagenes",f(a),f(b),f(xm), "\n", "raiz=", xm, "error =",err)
if(abs(f(xm))<E) {cat("\n","converge en",i,"iteraciones", "raiz = ", xm)
stop()}
else{
if (f(a)*f(xm)> 0) {a = xm; print("cambia a, b queda igual ") }
if (f(a)*f(xm)< 0) {b = xm;print("cambia b, a queda igual ")}
}
xant=xm }
print("Maximo numero de iteraciones alcanzadas)
corrida
iteracion 1
a,b,xm 0 2 1 imagenes -2 2 -1
raiz= 1 error = 1[1] "cambia a, b queda igual "
iteracion 2
a,b,xm 1 2 1.5 imagenes -1 2 0.25
raiz= 1.5 error = 0.5[1] "cambia b, a queda igual "
iteracion 3
a,b,xm 1 1.5 1.25 imagenes -1 0.25 -0.4375
raiz= 1.25 error = 0.25[1] "cambia a, b queda igual "
iteracion 4
a,b,xm 1.25 1.5 1.375 imagenes -0.4375 0.25 -0.109375
raiz= 1.375 error = 0.125[1] "cambia a, b queda igual "
iteracion 5
a,b,xm 1.375 1.5 1.4375 imagenes -0.109375 0.25 0.06640625
raiz= 1.4375 error = 0.0625[1] "cambia b, a queda igual "
iteracion 6
a,b,xm 1.375 1.4375 1.40625 imagenes -0.109375 0.06640625 -0.02246094
raiz= 1.40625 error = 0.03125[1] "cambia a, b queda igual "
iteracion 7
a,b,xm 1.40625 1.4375 1.421875 imagenes -0.02246094 0.06640625 0.02172852
raiz= 1.421875 error = 0.015625[1] "cambia b, a queda igual "
iteracion 8
a,b,xm 1.40625 1.421875 1.414062 imagenes -0.02246094 0.02172852 -0.0004272461
raiz= 1.414062 error = 0.0078125
converge en 8 iteraciones raiz = 1.414062
METODO DE LA REGLA FALSA
El método de regla falsa o falsa posición es un método iterativo de resolución numérica de ecuaciones no lineales, muy similar al método de la bisección excepto que en cada paso en lugar de usar el punto medio se usa la intersección de la recta que une los extremos del intervalo con el eje x (ver gráfica)
ALGORITMO
Como se dijo antes la única diferencia es la formula de calculo de la raíz aproximada que en el caso del método de la bisección es el punto medio, xm=(xa+xb) en el caso del método de la regla falsa la raiz xm se calcula por la siguiente formula
xm=[xbf(xa)-xaf(xb)]/[f(xa)-f(xb)]
por lo tanto se puede reescribir el algoritmo del método de la Reglea Falsa parafreseando el Algoritmo de la Bisección
Algoritmo del Método de la Regla falsa
i) Encontrar valores iniciales xa y xb, tales que y tienen signos opuestos
ii ) La primera aproximación a la raíz se toma igual al punto xm dado por
xm=[xbf(xa)-xaf(xb)]/[f(xa)-f(xb)]
iii) Evaluar f(xm). Forzosamente debemos caer en uno de los siguientes casos:
primero: f(xm)f(xa)>0
En este caso, f(xa) y f(xm) tienen el mismo signo. Por lo tanto, la raíz se encuentra en el intervalo [xm,xb]
segundo: f(xm)f(xa)<0
En este caso, f(xa) y f(xm) tienen signos opuestos, y por lo tanto la raíz se encuentra en el intervalo [xa,xm] .
tercero: f(xm)*f(xa)=0
En este caso se tiene que f(xm)=0 y por lo tanto ya localizamos la raíz.
iv) El proceso se vuelve a repetir con el nuevo intervalo, hasta que la raiz hallada sea menor que una tolerancia especificada es decir hasta que abs(f(xm))<e
Ejemplo:
Sea la ecuación f(x)=x^0.5 -cos(x) =0 . Resolver por el metodo de la falsa posicion
Solución
Primero Buscamos dos puntos xa y xb donde haya cambio de signo de f(x), por el método grafico podemos apreciar que xa=0 y x(b)=1 satisfacen el teorema de Bolzano (Ver salida del programa para detectar raices)
y=function(x) x^0.5-cos(x);z=0
for(x in 0:5)
{z<-y(x)*y(x+1)
if(z<0) {cat ("cambio de signo detectado entre ", x ,"y",x+1) stop()} } corrida: cambio de signo detectado entre 0 y 1 => f(0)=-1 y f(1)=0.46
- Iteración inical, xa=0, xb=1 Calculamos xm
xm=[xbf(xa)-xaf(xb)]/[f(xa)-f(xb)]=(1*f(0)-0)/(f(0)-f(1))= 0.685
Evaluamos f(xm) => f(.685)=0.053
signo de f(x)
+ +
----------- => La raiz se encuentra en el intervalo [0, 0.68]
0 0.68 1
2)Segunda Iteración xa=0; xb=0.68 ; f(0)=-1 f(0.68)=0.047
xm=[xbf(xa)-xaf(xb)]/[f(xa)-f(xb)]=(0.68*f(0)-0)/(f(0)-f(0.68))=0.649
Evaluamos f(xm) => f(.649)=0.009. Err1=abs(0.649-0.685)=0.036
signo de f(x)
+ +
----------- -- => La raiz se encuentra en el intervalo [0, 0.649]
0 0.649 0.68
Tercera Iteración xa=0; xb=0.649
xm=[xbf(xa)-xaf(xb)]/[f(xa)-f(xb)]=(0.649*f(0)-0)/(f(0)-f(0.649))=0.643
Evaluamos f(xm) => f(.643)=0.009. Err1=abs(0.649-0.685)=0.0015
signo de f(x)
+ +
----------- -- => La raiz se encuentra en el intervalo [0, 0.643]
0 0.643 0.649
Err2=abs(0.643-0.649)=0.06
Tabla de resultados
Aprox. Error aprox.
0.685
0.649 0.036
0.643 0.0015
====================================
SCRIPT EN R PARA LA REGLA FALSA
Metodo de Regla Falsa para resolver: x^0.5-cos(x)
#grafica de la funcion
f = function(x) x^0.5-cos(x)
curve(f, from=0,to=5,col="red")
abline(h=0,col="blue")
chequeo del teorema de bolzano
if (f(a)*f(b) > 0) {
cat("error: f(a) y f(b) son del mismo signo.
Escoja otro par de valores")
stop()}
#Apoyandonos en la grafica escojemos a=0 y b=1
#valores iniciales
a=0; b=1; N=20; E=0.001
#ciclo iteractivo
xant=0
for ( i in 1:N){
xm=(b*f(a)-a*f(b))/(f(a)-f(b))
err=abs(xm-xant)
cat("\n","iteracion",i)
cat("\n","a,b,xm",a,b,xm,"imagenes",f(a),f(b),f(xm), "\n", "raiz=", xm, "error =",err)
if(abs(err)<E) ) {cat("\n","converge en",i,"iteraciones", "raiz = ", xm) stop()}
else{ if (f(a)*f(xm)> 0) {a = xm; print("cambia a, b queda igual ") }
if (f(a)*f(xm)< 0) {b = xm;print("cambia b, a queda igual ")}
}
xant=xm }
corrida:
iteracion 1
a,b,xm 0 1 0.6850734 imagenes -1 0.4596977 0.05331895
raiz= 0.6850734 error = 0.6850734[1] "cambia b, a queda igual "
iteracion 2
a,b,xm 0 0.6850734 0.650395 imagenes -1 0.05331895 0.01062599
raiz= 0.650395 error = 0.03467838[1] "cambia b, a queda igual "
iteracion 3
a,b,xm 0 0.650395 0.6435566 imagenes -1 0.01062599 0.002253033
raiz= 0.6435566 error = 0.006838428[1] "cambia b, a queda igual "
iteracion 4
a,b,xm 0 0.6435566 0.6421099 imagenes -1 0.002253033 0.0004835998
raiz= 0.6421099 error = 0.001446694
converge en 4 iteraciones raiz = 0.6421099
Para mas detalles consulta mi blog: calnum@wordpress.com, clase #10