Método da bisseção
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Bisection_method.svg/250px-Bisection_method.svg.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Bisection_anime.gif/220px-Bisection_anime.gif)
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.[2][6]
Análise
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[7][6]
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 é,
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
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ém
- Método de Newton
- Método das secantes
- Ponto fixo
- Pesquisa binária
Referências
- ↑ «Bissecção». Dicionário Online Priberam. Consultado em 17 de novembro de 2021
- ↑ a b c Burden, Richard (2008). Análise Numérica - Tradução da 8ª Edição Norte-Americana. [S.l.: s.n.] ISBN 9788522106011
- ↑ Burden & Faires 1985, p. 31
- ↑ Burden & Faires 1985, p. 28
- ↑ «Dichotomy method - Encyclopedia of Mathematics». www.encyclopediaofmath.org. Consultado em 21 de dezembro de 2015
- ↑ 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
- ↑ 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