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:
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:
[sourcecode language=”java” highlight=”4,7,13,16″]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;
}
}[/sourcecode]
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.
