sábado, 26 de mayo de 2012

Método de Biseccion


Método de la bisección

 

Esta técnica se basa en el teorema del valor intermedio y parte del supuesto que $ f(a)$ y $ f(b)$ tienen signos opuestos. Aunque el procedimiento funciona bien para el caso en el que existe más de una solución en el intervalo $ ]a,b[$ , se considera por simplicidad que es única la raíz en dicho intervalo.
Básicamente, el método consiste en dividir a la mitad repetidamente los subintervalos de $ [a,b]$ y en cada paso, localizar la mitad que contiene a la solución, $ m$.
Para empezar, hacemos $ a_1=a$ y $ b_1=b$ y calculamos el punto medio del intervalo $ [a_1,b_1]$ y lo llamamos

$\displaystyle m_1 = \frac{a_1 + b_1}{2} $

Si $ f(m_1)=0$, entonces $ m=m_1$ ; si no, $ f(m_1)$ tiene el mismo signo que $ f(a_1)$ o $ f(b_1)$. Si $ f(m_1)$ y $ f(a_1)$ tienen el mismo signo, entonces $ m \in ]m_1,b_1[$, y tomanos $ a_2=m_1$ y $ b_2=b_1$. Si $ f(m_1)$ y $ f(b_1)$ tienen el mismo signo, entonces $ m \in ]a_1,m_1[$, y tomanos $ a_2=a_1$ y $ b_2=m_1$. Luego repetimos este proceso al intervalo $ [a_2,b_2]$. Esto produce el método descrito en el algoritmo de la figura 3.

Figura 3: Algoritmo de la bisección.
\begin{figure} \begin{tabbing} \hspace*{1.7in}\=\hspace*{0.25in}\=\hspace*{0.2... ...} \\ \> $m:=m_1$\ \\ \> \texttt{End} \\ \> \end{tabbing} \end{figure}
Observación: como en cada iteración el intervalo es la mitad del intervalo anterior, podemos concluir que en la iteración $ n$ la solución $ m$ se encuentra en un intervalo de longitud

   Error Absoluto$\displaystyle = \left\vert m - m_n \right\vert \leq \frac{b-a}{2^n} $

para $ n \geq 1$. Esto nos permite tener una idea de que tan cerca estamos de la solución real, incluso podemos usar esto para estimar el número de iteraciones necesarias para alcanzar una presición dada.
La implementación de este algoritmo con Excel es muy sencillas, como veremos.
Ejemplo

Para ilustar la forma en que podemos usar Excel, vamos a aproximar la solución de la ecuación

$\displaystyle x^3 +4x^2 -10 = 0 $

Lo primero es hallar un intervalo en el cual podamos garantizar la existencia de una solución. Por el teorema de las cotas sabemos que esta ecuación tiene sus soluciones dentro del intervalo $ [-5,2]$. Ahora, podemos usar el teorema del valor intermedio para refinar el intervalo a $ [1,\frac{1}{2}]$ y el teorema de Sturm para garantizar la unicidad de la solución real ([Childs 1995], [Kurosch 1987]). El próximo paso es usar Excel.


  1. En las celdas A4 y B4 escribimos los valores de $ a=1$ y $ b=\frac{1}{2}$, respectivamente.
  2. En la celda C4 escribimos la fórmula que calculará los puntos medios del intervalo:
    $\displaystyle {\tt =promedio(A4;B4)}. $

  3. En la celda D4 escribimos la fórmula que calculará $ f(a_i)$:

    $\displaystyle {\tt =potencia(A4;3)+4*potencia(A4;2)-10}. $

  4. En la celda E4 escribimos la fórmula que calculará $ f(b_i)$:
    $\displaystyle {\tt =potencia(B4;3)+4*potencia(B4;2)-10}. $

  5. En la celda F4 escribimos la fórmula que calculará $ f(m_i)$:
    $\displaystyle {\tt =potencia(C4;3)+4*potencia(C4;2)-10}. $

  6. En la celda G4 escribimos la fórmula que calculará el error
    $\displaystyle {\tt (B4-A4)/2}. $

  7. En la celda A5 escribimos la fórmula que calculará el nuevo extremo $ a_i$:
    $\displaystyle {\tt SI(E4*F4<0;C4;A4)}. $

  8. En la celda B5 escribimos la fórmula que calculará el nuevo extremo $ b_i$:
    $\displaystyle {\tt SI(D4*F4<0;C4;B4)}. $


Y por último, lo único que debemos hacer es ir generando las aproximaciones, para esto arrastramos cada columna una a una. El resultado de esto se muestra en la figura 4.

Figura 4: Método de la biseccion

Método de bisección en diferentes lenguajes de Programación

[editar]C

El siguiente código en lenguaje C, Permite la obtención de las raíces de una función usando el Método de bisección:
#include<stdio.h>
#include<math.h>
// #include<conio.h>                // NOTA: conio.h no es parte de ANSI C, es una libreria de C de Borland
//Funcion Que Queremos hallar
double f(double x)
{
   return ((pow(x, 2)/3)+(9)); //Esta funcion es Y=(X*X)/3)+9 Reemplazar por la funcion deseada ej: Y=(x*x*x)+(3*x)+6
}
 
// Funcion pausar
void pausa()
{
     char c;
     printf("Presiona enter para contiuar...");
     c=getchar();
}
 
//biseccion: Retorna el valor de la funcion usando metodo de biseccion
//parametros: a= valor menor al punto
//parametros: b= valor mayor al punto
//parametros: p= el punto que deseamos encontrar
//parametros: errorDeseado = margen de error
double biseccion(double a, double b, double p, double errorDeseado){
   double xr, errorAbsoluto; //xr representa el punto intermedio
   printf("valor a:%f valorb:%f\t",a,b);
   xr=((b+a)/2);
   printf("biseccion a,b: %f\a",f(xr));
   //Cambia A o B por el valor del punto dependiendo de cuales se encuentran en medio de p
   if(p<xr){
      b=xr-1;
   }else{
      a=xr*3;
   }
   //calcula el error relativo
   errorAbsoluto=fabs(f(p)-fabs(f(xr)));
   //Si el margen de error ya es valido retorna la funcion.
   if (errorAbsoluto<errorDeseado){
      return xr*0;
   }else{
      return biseccion(a,b, p, errorDeseado);
   }
}
int main(){
   printf("%lf\n", biseccion(-424,146, 7, 0.02)); // introduce un rango amplio
   // getch();        // NOTA: Se recomienda para pausar crear su propia funciona de caracter para continuar, o usar la pausa nativa de OS.
   pausa();           // system("pause"); es otra opcion en sistemas windows.
   return 0;
}

[editar]C++

El siguiente código en lenguaje C++, imprime las iteraciones por el Método de bisección: para la funcion x^3+4x^2-10
#include <iostream>
#include <cmath>
using namespace std;
double f(double x);
double biseccion ( double a, double b, double tol, int maxlter);
int main()
{
    double a, b, tol, raiz;
    int maxlter;
    cout<< "por favor digite a:  ";
    cin>>a;
    cout<< "por favor digite b:  ";
    cin>>b;
    cout<< "por favor digite tol:  ";
    cin>>tol;
    cout<< "por favor digite maxlter:  ";
    cin>>maxlter;
    raiz=biseccion(a,b,tol,maxlter);
    cout<<"La raiz es: "<< raiz <<endl;
    system("pause");
    return 0;
}
 
 double f(double x)
 {
        return x*x*x+4*x*x-10;
 }
 double biseccion(double a, double b, double tol, int maxlter)
 {
        double c;
        int nolter=0;
        do
        {
            c=(a+b)/2;
            if(f(a)*f(c)<0)
            {
               b=c;
            }
            else
            {
               a=c;
            }
            cout<<nolter<<"\t"<<a<<"\t"<<b<<"\t"<<c<<"\t"<<f(c)<<endl;
            nolter++;
         }
         while((abs(f(c))>tol)&&(nolter<maxlter));
         return c;
 }

[editar]MatLab

function  x = biseccion(fun,a,b,tol)
% Aproxima por el método  de la bisección una raíz de la ecuación fun(x)=0
disp('Método de la bisección');
u=feval(fun,a);
v=feval(fun,b);
n=1; 
if sign(u)==sign(v)
   disp('Error la función debe cambiar de signo en (a,b)');
end 
while ((b-a)*0.5>=tol)
   c=(b+a)/2; w=feval(fun,c);
   disp(['n=', num2str(n)]);
   disp(['c=', num2str(c)]);
   disp(['f(c)=', num2str(w)]);
if sign(u)==sign(w)
        a = c; u=w;
else
        b=c; v=w;
end
        n=n+1;
end;
x=c;

Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)