Dada una función f(x) sobre el número flotante x y dos números ‘a’ y ‘b’ tales que f(a)*f(b) < 0 y f(x) es continua en [a, b]. Aquí f(x) representa una ecuación algebraica o trascendental. Encuentre la raíz de la función en el intervalo [a, b] (O encuentre un valor de x tal que f(x) sea 0).
Ejemplo:
Input: A function of x, for example x3 - x2 + 2.
And two values: a = -200 and b = 300 such that
f(a)*f(b) < 0, i.e., f(a) and f(b) have
opposite signs.
Output: The value of root is : -1.0025
OR any other value with allowed
deviation from root.
¿Qué son las funciones algebraicas y trascendentales?
Las funciones algebraicas son aquellas que se pueden representar en forma de polinomios como f(x) = a 1 x 3 + a 2 x 2 + ….. + e donde aa 1 , a 2 , … son constantes y x es una variable .
Las funciones trascendentales son funciones no algebraicas, por ejemplo f(x) = sin(x)*x – 3 o f(x) = e x + x 2 o f(x) = ln(x) + x ….
¿Qué es el método de bisección?
El método también se denomina método de reducción a la mitad del intervalo, método de búsqueda binaria o método de dicotomía. Este método se usa para encontrar la raíz de una ecuación en un intervalo dado que es el valor de ‘x’ para el cual f(x) = 0.
El método se basa en el teorema del valor intermedio que establece que si f(x) es una función continua y hay dos números reales a y b tales que f(a)*f(b) 0 y f(b) < 0) , entonces se garantiza que tiene al menos una raíz entre ellos.
Suposiciones:
- f(x) es una función continua en el intervalo [a, b]
- f(a) * f(b) < 0
Pasos:
- Encuentre el punto medio c = (a + b)/2 .
- Si f(c) == 0, entonces c es la raíz de la solución.
- De lo contrario f(c) != 0
- Si el valor f(a)*f(c) < 0 entonces la raíz se encuentra entre a y c. Entonces recurrimos para a y c
- De lo contrario, si f(b)*f(c) < 0, entonces la raíz se encuentra entre b y c. Entonces recurrimos b y c.
- De lo contrario , la función dada no sigue una de las suposiciones.
Dado que la raíz puede ser un número de punto flotante, repetimos los pasos anteriores mientras que la diferencia entre a y b es menor que un valor. (Un valor muy pequeño).
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program for implementation of Bisection Method for
// solving equations
#include<bits/stdc++.h>
using namespace std;
#define EPSILON 0.01
// An example function whose solution is determined using
// Bisection Method. The function is x^3 - x^2 + 2
double func(double x)
{
return x*x*x - x*x + 2;
}
// Prints root of func(x) with error of EPSILON
void bisection(double a, double b)
{
if (func(a) * func(b) >= 0)
{
cout << "You have not assumed right a and b\n";
return;
}
double c = a;
while ((b-a) >= EPSILON)
{
// Find middle point
c = (a+b)/2;
// Check if middle point is root
if (func(c) == 0.0)
break;
// Decide the side to repeat the steps
else if (func(c)*func(a) < 0)
b = c;
else
a = c;
}
cout << "The value of root is : " << c;
}
// Driver program to test above function
int main()
{
// Initial values assumed
double a =-200, b = 300;
bisection(a, b);
return 0;
}
Java
// Java program for implementation of Bisection Method
// for solving equations
class GFG{
static final float EPSILON = (float)0.01;
// An example function whose solution is determined using
// Bisection Method. The function is x^3 - x^2 + 2
static double func(double x)
{
return x*x*x - x*x + 2;
}
// Prints root of func(x) with error of EPSILON
static void bisection(double a, double b)
{
if (func(a) * func(b) >= 0)
{
System.out.println("You have not assumed"
+ " right a and b");
return;
}
double c = a;
while ((b-a) >= EPSILON)
{
// Find middle point
c = (a+b)/2;
// Check if middle point is root
if (func(c) == 0.0)
break;
// Decide the side to repeat the steps
else if (func(c)*func(a) < 0)
b = c;
else
a = c;
}
//prints value of c upto 4 decimal places
System.out.printf("The value of root is : %.4f"
,c);
}
// Driver program to test above function
public static void main(String[] args)
{
// Initial values assumed
double a =-200, b = 300;
bisection(a, b);
}
// This code is contributed by Nirmal Patel
}
Python3
# Python program for implementation
# of Bisection Method for
# solving equations
# An example function whose
# solution is determined using
# Bisection Method.
# The function is x^3 - x^2 + 2
def func(x):
return x*x*x - x*x + 2
# Prints root of func(x)
# with error of EPSILON
def bisection(a,b):
if (func(a) * func(b) >= 0):
print("You have not assumed right a and b\n")
return
c = a
while ((b-a) >= 0.01):
# Find middle point
c = (a+b)/2
# Check if middle point is root
if (func(c) == 0.0):
break
# Decide the side to repeat the steps
if (func(c)*func(a) < 0):
b = c
else:
a = c
print("The value of root is : ","%.4f"%c)
# Driver code
# Initial values assumed
a =-200
b = 300
bisection(a, b)
# This code is contributed
# by Anant Agarwal.
C#
// C# program for implementation
// of Bisection Method for
// solving equations
using System;
class GFG
{
static float EPSILON = (float)0.01;
// An example function whose
// solution is determined using
// Bisection Method. The function
// is x^3 - x^2 + 2
static double func(double x)
{
return x * x * x -
x * x + 2;
}
// Prints root of func(x)
// with error of EPSILON
static void bisection(double a,
double b)
{
if (func(a) * func(b) >= 0)
{
Console.WriteLine("You have not assumed" +
" right a and b");
return;
}
double c = a;
while ((b - a) >= EPSILON)
{
// Find middle point
c = (a + b) / 2;
// Check if middle
// point is root
if (func(c) == 0.0)
break;
// Decide the side
// to repeat the steps
else if (func(c) * func(a) < 0)
b = c;
else
a = c;
}
// prints value of c
// upto 4 decimal places
Console.WriteLine("The value of " +
"root is : "+ c);
}
// Driver Code
static public void Main ()
{
// Initial values assumed
double a = -200, b = 300;
bisection(a, b);
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program for implementation
// of Bisection Method for solving
// equations
$EPSILON = 0.01;
// An example function whose
// solution is determined
// using Bisection Method.
// The function is x^3 - x^2 + 2
function func($x)
{
return $x * $x * $x -
$x * $x + 2;
}
// Prints root of func(x)
// with error of EPSILON
function bisection($a, $b)
{
global $EPSILON;
if (func($a) *
func($b) >= 0)
{
echo "You have not assumed " .
"right a and b","\n";
return;
}
$c = $a;
while (($b - $a) >= $EPSILON)
{
// Find middle point
$c = ($a + $b) / 2;
// Check if middle
// point is root
if (func($c) == 0.0)
break;
// Decide the side to
// repeat the steps
else if (func($c) * func($a) < 0)
$b = $c;
else
$a = $c;
}
echo "The value of root is : " , $c;
}
// Driver Code
// Initial values assumed
$a =-200;
$b = 300;
bisection($a, $b);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program for implementation
// of Bisection Method for
// solving equations
let EPSILON = 0.01;
// An example function whose solution is determined using
// Bisection Method. The function is x^3 - x^2 + 2
function func(x)
{
return x*x*x - x*x + 2;
}
// Prints root of func(x) with error of EPSILON
function bisection(a, b)
{
if (func(a) * func(b) >= 0)
{
document.write("You have not assumed"
+ " right a and b");
return;
}
let c = a;
while ((b-a) >= EPSILON)
{
// Find middle point
c = (a+b)/2;
// Check if middle point is root
if (func(c) == 0.0)
break;
// Decide the side to repeat the steps
else if (func(c)*func(a) < 0)
b = c;
else
a = c;
}
//prints value of c upto 4 decimal places
document.write("The value of " +
"root is : "+ c.toFixed(4));
}
// Driver program
// Initial values assumed
let a =-200, b = 300;
bisection(a, b);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
The value of root is : -1.0025
Complejidad del tiempo: la complejidad del tiempo de este método depende de los valores asumidos y la función.
¿Cuáles son los pros y los contras?
La ventaja del método de bisección es que se garantiza la convergencia. La desventaja del método de bisección es que no puede detectar raíces múltiples.
En general, el método de bisección se usa para obtener una aproximación aproximada inicial de la solución. Luego se utilizan métodos convergentes más rápidos para encontrar la solución.
Pronto discutiremos otros métodos para resolver ecuaciones algebraicas y trascendentales
Referencias:
Métodos introductorios de análisis numérico por SS Sastry
https://en.wikipedia.org/wiki/Bisection_method
Este artículo es una contribución de Abhiraj Smit. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA