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

1. 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: [email protected], clase #10