Método da bisseção

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. 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. 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. O método também é chamado de método da pesquisa binária, ou método da dicotomia.

O método

Bisseção do intervalo ${\textstyle [a,b]}$ e os elementos envolvidos.

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, $f(a)\cdot f(b)<0$. Nestas condições, o teorema do valor intermediário garante a existência de uma raiz no intervalo $(a,b)$. O método consiste em dividir o intervalo no seu ponto médio $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.

Análise

A cada passo, o erro absoluto é reduzido pela metade, e assim o método converge linearmente. Especificamente, se $c_{1}=(a+b)/2$ é o ponto médio do intervalo, e $c_{n}$ é o ponto médio do intervalo da $n$-ésima iteração, então a diferença entre $c_{n}$ e uma solução $c$ é limitada por

$$|c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.$$

Assim, se $\epsilon _{n}$ for a estimativa do erro absoluto na $n$-ésima iteração, então

$$\epsilon _{n+1}\leq \epsilon _{n}/2$$

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 $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) $\epsilon$:

$$n=\log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)={\frac {\log \epsilon _{0}-\log \epsilon }{\log 2}},$$

sendo $\epsilon _{0}$ o tamanho do intervalo inicial, isto é, $\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:

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

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

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

$f(1)=-2$ e $f(2)=+4$

Como a função é contínua, sabemos que existe uma raiz no intervalo ${\textstyle (1,2)}$. A primeira iteração gera $c=1.5$, e $f(1.5)=-0.125$. Como ${\textstyle f(c)}$ é negativa, ${\textstyle c}$ se tornará nosso novo ${\textstyle a}$ para que continuemos tendo $f(a)$ e $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	$a_{n}$	$b_{n}$	$c_{n}$	$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