Método da bisseção

Método da bisseção.

O Predefinição:PBPE é 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 $[a,b]$ e os elementos envolvidos.

Este método pode ser usado para encontrar as raízes de uma função contínua $f:[a,b]\to ℝ$, $y=f(x)$, tendo $f(a)$ e $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 $f(a)\cdot f(c)<0$. Caso afirmativo, existe pelo menos uma raiz no intervalo $(a,c)$, caso contrário garante-se a existência de uma raiz no intervalo $[c,b)$. O procedimento é, então, repetido para o subintervalo correspondente à raiz até que $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|\le \frac{|b-a|}{2^n}.$$

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

$${ϵ}_{n+1}\le {ϵ}_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) $ϵ$: $$n={\log }_2\left(\frac{{ϵ}_0}{ϵ}\right)=\frac{\log {ϵ}_0-\log ϵ}{\log 2},$$ sendo ${ϵ}_0$ o tamanho do intervalo inicial, isto é, ${ϵ}_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 $(1,2)$. A primeira iteração gera $c=1.5$, e $f(1.5)=-0.125$. Como $f(c)$ é negativa, $c$ se tornará nosso novo $a$ para que continuemos tendo $f(a)$ e $f(b)$ com sinais opostos, e com isso saber que a raiz se encontra em $(1.5,2)$. Repetindo esses passos, teremos intervalos cada vez menores até que o valor de $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 $c$ já tem 4 dígitos significativos corretos.

Ver também

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

• Predefinição:Citation