Método da Bissecção

Esses dias resolvi retomar o conhecimento de cálculo numérico que tive na faculdade. O primeiro tópico que abordei foi os métodos iterativos de obter zeros reais de funções. Tomei como base o livro de Cálculo Numérico que tive na faculdade.

Alguns desses métodos utilizam o Teorema de Bolzano que é um caso específico do Teorema do Valor Intermediário para garantir que existe uma raiz dado um determinado intervalo e com isso desenvolvem técnicas para encontrar ess raiz. De maneira simplificada, o Teorema de Bolzano diz que se uma função assume valor negativo para um determinado ponto a e um valor positivo para um determinado ponto b (ou vice versa, positivo pra a e negativo pra b), vai existir pelo menos uma raíz entre esse intervalo se a função for contínua. Isto é: Se f(a) \cdot f(b) < 0, existe raiz real. Veja a seguinte função:Gráfico

Seja o intervalo [a,b] = [2,3], para o valor de a = 2, f(x) assume valor negativo e para b = 3, f(x) assume valor positivo, portanto, f(a) \cdot f(b) < 0 e pelo gráfico podemos ver que existe um valor entre 2 e 3 que é raíz dessa função. Nesse exemplo a função é f(x) = x^3 - 9x + 3. Aplicando valores reais: a = 2, f(a) = f(2) = 2^3 - 9 \cdot 2 + 3 = -7 e b = 3, f(b) = f(3) = 3^3 - 9 \cdot 3 + 3 = 3, então f(a) \cdot f(b) = -21 < 0. Portanto, existe raiz entre 2 e 3 para a função f(x) = x^3 - 9x + 3.

Com isso em mente, nesse tópico vamos abordar um método para encontrar esse raiz: o método da bissecção. Esse método consiste em tentar achar uma raiz em um intervalo subdividindo esse intervalo em duas metades a cada iteração, utilizando o teorema de Bolzano para verificar em qual metade está a raiz até atingir a precisão requerida. É um método simples, mas não necessariamente eficiente. Abaixo temos o código para esse método:

for (long k = 0; k < maxIter; k++) {
			// x = (a + b)/2
			BigDecimal x = a.add(b).divide(CommonValues.TWO.getValue());
			// (b - a) < precision
			if (b.subtract(a).compareTo(precision) < 0) {
				// result a or b is ok too
				return x;
			}
			// m = f(a)
			BigDecimal m = f.evaluate(a);
			// m*f(x) > 0
			if (m.multiply(f.evaluate(x)).compareTo(BigDecimal.ZERO) > 0) {
				a = x;
			} else {
				b = x;
			}
		}

Dado um intervalo [a,b], na linha 4 dividimos o nosso intervalor na metade, na linha 7 verificamos se já atingimos a precisão alvo, se sim, retornamos um valor entre o intervalo [a,b] (linha 9). Caso contrário, aplicamos o teorema de bolzano: f(a) \cdot f(x) < 0 (linha 13 e 16) para verificar se a raiz está entre a e x ou b e x. Mudamos o intervalo de acordo com essa condição (linha 17 ou 19) e continuamos nesse loop (linha 1), até atingir a precisão correta (linha 7) ou até um determinado número de iterações (linha 1).

Como esse método é simples e previsível (sempre divisões ao meio) fica fácil calcular o número de iterações necessárias para ele encontrar a raiz dada uma precisão:

k > \frac{ log(b - a) - log( \varepsilon ) }{ log(2) }

Onde k é o número de iterações e \varepsilon é a precisão desejada. O código para esse método e exemplos de execução encontram-se nos seguintes endereços: Github e Google Code.

Sobre: Thiago Galbiatti Vespa

Thiago Galbiatti Vespa é mestre em Ciências da Computação e Matemática Computacional pela USP e bacharel em Ciências da Computação pela UNESP. Coordenador de projetos do JavaNoroeste, membro do JCP (Java Community Process), consultor Oracle, arquiteto de software de empresas de médio e grande porte, palestrante de vários eventos e colaborador de projetos open source. Possui as certificações: Oracle Certified Master, Java EE 5 Enterprise Architect – Step 1, 2 and 3; Oracle WebCenter Portal 11g Certified Implementation Specialist; Oracle Service Oriented Architecture Infrastructure Implementation Certified Expert; Oracle Certified Professional, Java EE 5 Web Services Developer; Oracle Certified Expert, NetBeans Integrated Development Environment 6.1 Programmer; Oracle Certified Professional, Java Programmer; Oracle Certified Associate, Java SE 5/SE 6