250px|thumb| Método da bisseção. O é 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

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.

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, Theorem 2.1

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: 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

Categoria:Análise numérica Categoria:Ferramentas de cálculo