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, relativamente lento quando comparado a métodos como o método de Newton ou o método das secantes.[1] 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.[2] O método também é chamado de método da pesquisa binária,[3] ou método da dicotomia.[4]

Método da bisseção.

O métodoEditar

 
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.[1][5]

AnáliseEditar

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[6][5]

 

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 é,  

AlgoritmoEditar

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:[1]

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 NNMAX # 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 (ba)/2 < TOL então # solução encontrada
    Retorne(c)
    Pare
  Fim
  NN + 1 # incrementa o contador de iterações
  Se sinal(f(c)) = sinal(f(a)) então ac senão bc # novo intervalo
Fim
Retorne("O algoritmo falhou.") # núm. máximo de iterações excedido

ExemploEditar

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.

Ver tambémEditar

Referências

  1. a b c Burden, Richard (2008). Análise Numérica - Tradução da 8ª Edição Norte-Americana. [S.l.: s.n.] ISBN 9788522106011 
  2. Burden & Faires 1985, p. 31
  3. Burden & Faires 1985, p. 28
  4. «Dichotomy method - Encyclopedia of Mathematics». www.encyclopediaofmath.org. Consultado em 21 de dezembro de 2015 
  5. a b Francisco Satuf. «"Método da Bisseção"» (PDF). Consultado em 2 de outubro de 2013. Arquivado do original (PDF) em 5 de outubro de 2013 
  6. Burden & Faires 1985, p. 31, Theorem 2.1
  • Burden, Richard L.; Faires, J. Douglas (1985), «2.1 The Bisection Algorithm», Numerical Analysis, ISBN 0-87150-857-5 3rd ed. , PWS Publishers