Método da bisseção

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

Este método pode ser usado para encontrar as raízes de uma função contínua ${\textstyle f:[a,b]\to \mathbb {R} }$, ${\textstyle y=f(x)}$, tendo ${\textstyle f(a)}$ e ${\textstyle f(b)}$ sinais opostos, ou seja, ${\displaystyle f(a)\cdot f(b)<0}$. Nestas condições, o teorema do valor intermediário garante a existência de uma raiz no intervalo ${\displaystyle (a,b)}$. O método consiste em dividir o intervalo no seu ponto médio ${\displaystyle c=(a+b)/2}$, e então verificar em qual dos dois subintervalos garante-se a existência de uma raiz. Para tanto, basta verificar se ${\textstyle f(a)\cdot f(c)<0}$. Caso afirmativo, existe pelo menos uma raiz no intervalo ${\textstyle (a,c)}$, caso contrário garante-se a existência de uma raiz no intervalo ${\textstyle [c,b)}$. O procedimento é, então, repetido para o subintervalo correspondente à raiz até que ${\textstyle c}$ 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 ${\displaystyle c_{1}=(a+b)/2}$ é o ponto médio do intervalo, e ${\displaystyle c_{n}}$ é o ponto médio do intervalo da ${\displaystyle n}$-ésima iteração, então a diferença entre ${\displaystyle c_{n}}$ e uma solução ${\displaystyle c}$ é limitada por^[7][6]

Assim, se ${\displaystyle \epsilon _{n}}$ for a estimativa do erro absoluto na ${\displaystyle n}$-é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 ${\displaystyle n}$ 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) ${\displaystyle \epsilon }$:

sendo ${\displaystyle \epsilon _{0}}$ o tamanho do intervalo inicial, isto é, ${\displaystyle \epsilon _{0}=b-a.}$

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
Enquanto N ≤ NMAX # limita o número de iterações para prevenir um loop infinito
  c ← (a + b)/2 # novo ponto médio
  Se f(c) = 0 ou (b – a)/2 < TOL então # solução encontrada
    Retorne(c)
    Pare
  Fim
  N ← N + 1 # incrementa o contador de iterações
  Se sinal(f(c)) = sinal(f(a)) então a ← c senão b ← c # novo intervalo
Fim
Retorne("O algoritmo falhou.") # núm. máximo de iterações excedido

Exemplo

Calculemos os zeros da função

${\displaystyle f(x)=x^{3}-x-2}$

De início temos de achar valores para ${\displaystyle a}$ e ${\displaystyle b}$ tais que ${\displaystyle f(a)}$ e ${\displaystyle f(b)}$ tenham sinais contrários. ${\displaystyle a=1}$ e ${\displaystyle b=2}$ respeitam esta condição.

${\displaystyle f(1)=-2}$ e ${\displaystyle f(2)=+4}$

Como a função é contínua, sabemos que existe uma raiz no intervalo ${\textstyle (1,2)}$. A primeira iteração gera ${\displaystyle c=1.5}$, e ${\displaystyle f(1.5)=-0.125}$. Como ${\textstyle f(c)}$ é negativa, ${\textstyle c}$ se tornará nosso novo ${\textstyle a}$ para que continuemos tendo ${\displaystyle f(a)}$ e ${\displaystyle f(b)}$ com sinais opostos, e com isso saber que a raiz se encontra em ${\textstyle (1.5,2)}$. Repetindo esses passos, teremos intervalos cada vez menores até que o valor de ${\textstyle c}$ convirja para o zero de nossa equação. Veja os valores plotados na tabela abaixo:

Iteração	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
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 ${\textstyle c}$ já tem 4 dígitos significativos corretos.

Ver também

• Método de Newton
• Método das secantes
• Ponto fixo
• Pesquisa binária

Referências

• Burden, Richard L.; Faires, J. Douglas (1985), «2.1 The Bisection Algorithm», Numerical Analysis, ISBN 0-87150-857-5 3rd ed. , PWS Publishers