Método da bisseção

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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]

O método[editar | editar código-fonte]

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 se encontra a raiz. Para tanto, basta verificar se {\textstyle f(a)\cdot f(c) < 0}. Caso afirmativo, a raiz encontra-se no intervalo {\textstyle [a,c]}, caso contrário ela se encontra 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.[1] [5]

Análise[editar | editar código-fonte]

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[6] [5] {\displaystyle |c_n-c|\le\frac{|b-a|}{2^n}.}

Assim, se \epsilon _n for o erro absoluto da n-ésima iteração, então

{\displaystyle \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: {\displaystyle n = \log_2\left(\frac{\epsilon_0}{\epsilon}\right)=\frac{\log\epsilon_0-\log\epsilon}{\log2},} sendo \epsilon_0 o tamanho do intervalo inicial, isto é, \epsilon_0=b - a.

Algoritmo[editar | editar código-fonte]

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 or (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

Exemplo[editar | editar código-fonte]

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 entre [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 entre [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[editar | editar código-fonte]

Referências

  1. a b c Burden, Richard. Análise Numérica - Tradução da 8ª Edição Norte-Americana. [S.l.: s.n.], 2008. 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 2015-12-21. 
  5. a b Francisco Satuf. ""Método da Bisseção"" (PDF). Consultado em 2 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 (3rd ed.), PWS Publishers, ISBN 0-87150-857-5