O método da bisseção(português brasileiro) ou método da bissecção(português europeu) é um método de busca de raízes que bissecta repetidamente um intervalo e então seleciona um subintervalo contendo a raiz para processamento adicional.[1] Trata-se de um método simples e robusto, mas relativamente lento quando comparado a métodos como o método de Newton ou o método das secantes.[2] Por este motivo, ele é usado frequentemente para obter uma primeira aproximação de uma solução, a qual é então utilizada como ponto inicial para métodos que convergem mais rapidamente.[3] O método também é chamado de método da pesquisa binária,[4] ou método da dicotomia.[5]
O método
Bisseção do intervalo e os elementos envolvidos.
Este método pode ser usado para encontrar as raízes de uma função contínua, , tendo e sinais opostos, ou seja, . Nestas condições, o teorema do valor intermediário garante a existência de uma raiz no intervalo .
O método consiste em dividir o intervalo no seu ponto médio, e então verificar em qual dos dois subintervalos garante-se a existência de uma raiz. Para tanto, basta verificar se . Caso afirmativo, existe pelo menos uma raiz no intervalo , caso contrário garante-se a existência de uma raiz no intervalo . O procedimento é, então, repetido para o subintervalo correspondente à raiz até que aproxime a raiz com a precisão desejada.[2][6]
Análise
A cada passo, o erro absoluto é reduzido pela metade, e assim o método converge linearmente. Especificamente, se é o ponto médio do intervalo, e é o ponto médio do intervalo da -ésima iteração, então a diferença entre e uma solução é limitada por[7][6]
Assim, se for a estimativa do erro absoluto na -ésima iteração, então
e o método da bisseção tem convergência linear, o que é comparativamente lento.
Esta fórmula também pode ser utilizada para determinar de antemão o número máximo de iterações que seriam necessárias para que a aproximação fornecida pelo método estivesse dentro de uma determinada margem de erro (ou tolerância) :
sendo o tamanho do intervalo inicial, isto é,
Algoritmo
Com o método da bisseção podemos construir um algoritmo para aproximar a raiz de uma função. Por exemplo, temos o seguinte pseudocódigo:[2]
ENTRADA: Função f, extremos do intervalo a, b, tolerância TOL, número máximo de iterações NMAX
CONDIÇÕES: a < b, ou f(a) < 0 e f(b) > 0 ou f(a) > 0 e f(b) < 0
SAÍDA: valor que difere de uma raiz de f(x)=0 por menos do que TOL
N ← 1
EnquantoN ≤ NMAX# limita o número de iterações para prevenir um loop infinitoc ← (a + b)/2 # novo ponto médioSef(c) = 0 ou (b – a)/2 < TOLentão# solução encontrada
Retorne(c)
PareFimN ← N + 1 # incrementa o contador de iteraçõesSe sinal(f(c)) = sinal(f(a)) entãoa ← csenãob ← c# novo intervaloFim
Retorne("O algoritmo falhou.") # núm. máximo de iterações excedido
Exemplo
Calculemos os zeros da função
De início temos de achar valores para e tais que e tenham sinais contrários. e respeitam esta condição.
e
Como a função é contínua, sabemos que existe uma raiz no intervalo .
A primeira iteração gera , e . Como é negativa, se tornará nosso novo para que continuemos tendo e com sinais opostos, e com isso saber que a raiz se encontra em . Repetindo esses passos, teremos intervalos cada vez menores até que o valor de convirja para o zero de nossa equação. Veja os valores plotados na tabela abaixo:
Iteração
1
1
2
1.5
−0.125
2
1.5
2
1.75
1.6093750
3
1.5
1.75
1.625
0.6660156
4
1.5
1.625
1.5625
0.2521973
5
1.5
1.5625
1.5312500
0.0591125
6
1.5
1.5312500
1.5156250
−0.0340538
7
1.5156250
1.5312500
1.5234375
0.0122504
8
1.5156250
1.5234375
1.5195313
−0.0109712
9
1.5195313
1.5234375
1.5214844
0.0006222
10
1.5195313
1.5214844
1.5205078
−0.0051789
11
1.5205078
1.5214844
1.5209961
−0.0022794
12
1.5209961
1.5214844
1.5212402
−0.0008289
13
1.5212402
1.5214844
1.5213623
−0.0001034
14
1.5213623
1.5214844
1.5214233
0.0002594
15
1.5213623
1.5214233
1.5213928
0.0000780
Como podemos ver, a partir da 13º iteração o valor de já tem 4 dígitos significativos corretos.