Método de Bissecção – O que é, Algoritmo e Exemplo

O que é o método de bissecção?

O Método da Bissecção é uma das soluções numéricas básicas para encontrar a raiz de uma equação polinomial. Isto brackets o intervalo em que se encontra a raiz da equação e os subdivide em metades em cada iteração até encontrar a raiz. Assim, o método da bissecção também é chamado de método de bracketing.

No entanto, como o mecanismo de funcionamento é semelhante ao algoritmo de busca binária, o método de bissecção também é conhecido como método de busca binária, método de redução pela metade ou método de dicotomia. Baseia-se principalmente no teorema do valor intermediário.

Encontrando raízes de equações

Neste exemplo, consideramos apenas equações com uma variável independente. Pode ser linear ou não linear. Equações lineares são usadas para representar o gráfico de uma linha reta, enquanto equações não lineares são usadas para representar curvas.

A raiz de uma equação significa o valor da variável independente que satisfaz a equação. Por exemplo: a raiz de uma equação f(x)= 4-x2 = 0 é 2 porque f(2) = 4-22 = 0.

Vamos considerar f(x) como uma função real contínua. De acordo com o teorema do valor intermediário, a equação f(x)=0 tem pelo menos uma raiz entre a e b se f(a)f(b) < 0. A função f(x) tem uma raiz, “c,” entre a e b.

Encontrando raízes de equações

Representação Gráfica do Método da Bissecção

O seguintewing O gráfico representa o mecanismo de funcionamento do método da bissecção. No gráfico, podemos ver que a raiz da equação está marcada em vermelho.

Começar com:

  • Primeiro fizemos duas suposições iniciais, uma1 e B1, para o qual f(a1)f(b1) < 0. De acordo com o teorema do valor intermediário, a raiz deve estar em [a1, b1].
  • Podemos encontrar o ponto médio de um1 e B1, que é b2. Assim, o intervalo inicial é agora reduzido para [a1, b2] porque f(uma1)f(b2) <0.
  • Da mesma forma, o intervalo é reduzido até que a solução aproximada seja encontrada.

Representação Gráfica do Método da Bissecção

Algoritmo do Método da Bissecção

As etapas para aplicar o algoritmo do método de bissecção para encontrar a raiz da equação f (x) = 0 são as seguintes

Passo 1) Escolha estimativas iniciais a, b e taxa de tolerância e

Passo 2) Se f(a)f(b) >=0, então a raiz não está neste intervalo. Assim, não haverá solução.

Passo 3) Encontre o ponto médio, c = (a+b)/2

(i) Se o valor da função do ponto médio f(c) = 0, então c é a raiz. Vá para a etapa 5.
(ii) Se f(a)f(c) < 0 a raiz está entre a e c. Então defina a = a, b = c.
(iii) Caso contrário, defina a = c, b = b.

Passo 4) Se o erro absoluto for superior à taxa de tolerância ou (ba) > e, vá para a etapa 3.

Passo 5) Mostre c como a raiz aproximada.

Vejamos um exemplo do algoritmo do método da bissecção.
Temos que encontrar a raiz do seguintewing função contínua usando a fórmula do método da bissecção.

f (x) = x3 - x2 + 2

Exemplo de método de bissecção

Passo 1) Vamos assumir,

         uma = -10,
         b = 10, e
         e = 1% ou 0.01

Passo 2) Agora vamos verificar se f(a)f(b) >= 0 ou não.

         f(uma) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Portanto, a raiz da função acima está neste intervalo [-10, 10].

Passo 3) Então o ponto médio c será calculado primeiro.

Exemplo de método de bissecção

Agora o seguintewing condições precisam ser verificadas:

(i) se f(c) = 0:
         f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) se f(a)f(c) < 0:
         f(c)f(a) = 2*(-1098) < 0

A condição foi cumprida. Para a próxima iteração, os valores serão,

         uma = uma = -10
         b = c = 0

Passo 4) Como (ba) = (0-(-10)) = 10>0.05, o processo será repetido. As próximas iterações são mostradas na tabela.

Iteração a b c BA f(c)
1 -10 0 0 10 2
2 -5 0 -5 5 -148
3 -2.5 0 -2.5 2.5 -19.875
4 -1.25 0 -1.25 1.25 -1.52562
5 -1.25 -0.625 -0.625 0.625 1.36523
6 -1.25 -0.9375 -0.9375 0.3125 0.297119
7 -1.09375 -0.9375 -1.09375 0.15625 -0.50473
8 -1.01562 -0.9375 -1.01562 0.078125 -0.0791054
9 -1.01562 -0.976562 -0.976562 0.0390625 0.115003
10 -1.01562 -0.996094 -0.996094 0.0195312 0.0194703
11 -1.00586 -0.996094 -1.00586 0.00976562 -0.0294344

Passo 5) Na 11ª iteração, a condição do passo 4 será falsa. Assim, a raiz desta equação é -1.00586.

Diagrama lógico do método de bissecção

Diagrama lógico do método de bissecção

Pseudo-código

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

Exemplo de método de bissecção em C/C++

Entrada:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

Saída:

The root is :-1.00586

Exemplo de método de bissecção em Python

Entrada:

def value(x):
	return x*x*x - x*x + 2
def bisection_method(a,b):
	if (value(a) * value(b) >= 0):
		return
	c = a
	while ((b-a) >= 0.01):
		c = (a+b)/2
		if (value(c) == 0.0):
			break
		if (value(c)*value(a) < 0):
			b = c
		else:
			a = c			
	print("The root is : ","%.4f"%c)	
a =-10
b = 10
bisection_method(a, b)

Saída:

The root is :  -1.0059

Vantagens e limitações do método de bissecção

Aqui estão os prós e contras do método de bissecção:

Prós Desvantagens
Método de localização de raiz fácil e simples de implementar. A convergência é lenta porque se baseia simplesmente na redução do intervalo pela metade.
Desde que brackets a raiz, é sempre convergente. Se uma das estimativas iniciais estiver próxima da raiz, chegar à raiz exigirá mais iterações.
A taxa de erro pode ser controlada aumentando ou diminuindo o número de iterações.