Método da bissecção

Como aproximar a solução de uma equação espremendo-a em um intervalo

Vamos lá?

O método da bissecção é o método mais simples para estimar a solução ou raiz de uma equação não linear escalar. Nesta aula eu apresento o método de forma construtiva e mostro um exemplo.

Quando o intervalo é repartido em dois subintervalos, podemos dizer que...

A. um dos dois subintervalos contém um zero da função.
B. um dos dois subintervalos não contém um zero da função.
C. se o intervalo da esquerda não contém um zero, certamente o intervalo da direita conterá um zero da função.

Em cada passo do método, quantas vezes a função precisa ser avaliada?

A. Três vezes: nos extremos e no ponto médio do intervalo.
B. Apenas uma vez, no ponto médio do intervalo.

Qual a principal dificuldade para usar o método da bissecção?

A. Pode ser difícil descobrir um intervalo inicial.
B. A convergência depende da função.
C. O método é lento.

Se $x_k$ é o ponto médio do intervalo na iteração $k$ e $x_*$ é o zero da função, podemos dizer que

A. $|x_k-x_*|$ tende a zero, quando $k$ tende a infinito.
B. $|x_{k+1}-x_*| < \frac{1}{2} |x_k-x_*|.$

No método da bissecção, parte-se de um intervalo inicial $[a, b]$ onde $f(a)\cdot f(b) < 0.$ Calcula-se então o valor da função no ponto médio e com base nisso reduz-se o intervalo de maneira a ficar com o subintervalo da direita ou da esquerda onde ainda é possível observar a alternância de sinal da função. A garantia que pelo menos um desses dois intervalos abriga um zero de $f$ vem do teorema de Bolzano.

Dessa forma, sucessivamente o intervalo de confinamento do zero da função é contraı́do. A cada iteração a melhor escolha possível para aproximar o zero da função é o ponto médio do intervalo, $x_k.$

A grande dificuldade para a aplicação do método da bissecção é a sua inicialização, que requer a determinação de um intervalo $[a, b]$ onde haja a alternância de sinal nos valores da função. Sem um conhecimento prévio do comportamento da função $f,$ a determinação desse intervalo é feita por tentativa e erro.

Uma vez iniciado, o método a bissecção tem convergência assegurada, ou seja, $|x_{k}-x_*|\rightarrow 0,$ quando $k\rightarrow \infty.$ Claro que, do ponto de vista prático, é necessário estipular um critério de parada. Dado um $\epsilon >0,$ o critério pode ser $|f(x_k)|<\epsilon$ ou mesmo $|b_k-a_k| < \epsilon,$ para $a_k$ e $b_k$ os extremos do intervalo no passo $k.$ Abaixo vemos como isso pode ser transcrito em um algoritmo.

Sejam $a \lt b$, tais que $f(a)\cdot f(b) \lt 0$, $K \gt 0$ e $\epsilon \gt 0$.
$k \leftarrow 0$
Enquanto $|b-a| \gt \epsilon$ e $k \lt K$, faça

$x_k \leftarrow (a+b)/2$
Se $f(x_k) = 0,$ então $x_k$ é a solução. FIM.
Se $f(a)\cdot f(x_k) \lt 0$, então
- $b \leftarrow x_k$
senão
- $a \leftarrow x_k$
$k \leftarrow k+1$

$x_k \leftarrow (a+b)/2$
Retorne $x_k$ como melhor aproximação.

A obtenção de uma aproximação com a precisão desejada pode demandar uma grande quantidade de iterações. O problema disso é que, em algumas situações de interesse, a avaliação da função pode ser muito cara. Por isto, o algoritmo acima utiliza também como critério de parada um limite máximo para o número de iterações.

Ainda sobre o algoritmo acima, alguns cuidados podem e devem ser tomados caso ele seja implementado. Por exemplo, quando se pergunta se $f(a)\cdot f(x_k) \lt 0,$ ambos os valores de função não devem ser avaliados, mas sim reaproveitados de avaliações anteriores.

Como alternativa, há métodos que utilizam mais informação sobre a função e, portanto, são mais rápidos. Mas isso é assunto para outra aula.

1. Determine um intervalo fechado de comprimento máximo $0.1$ contendo apenas um zero de $f(x) = (2+x/8)^4-3(1.5-x/17)^2.$ Aplique o método da bissecção para encontrar esse zero.

Construíndo o gráfico da função, rapidamente percebemos que o intervalo $\Omega=[-2.5,-2.4]$ é um candidato a conter um único zero de $f$. A demostração deste fato se dá constatando que a derivada de $f$ é estritamente positiva em $\Omega$. Aplicando o método da bissecção, partindo do intervalo $\Omega$, após 44 iterações obtem-se $x = -2.49020197792687$.

2. Utilizando o método da bissecção e o critério de parada $|b_k-a_k| < 10^{-6},$ encontre uma aproximação para um zero das funções abaixo, no intervalo indicado.

$f(x) = \cos x,$ em $[0,2]$
$f(x) = x,$ em $[-1,1]$
$f(x) = x^2,$ em $[-1,2]$
$f(x) = \int_{-1}^x e^{-u^2} - u^3\, du,$ $[0,2]$
$f(x) = x^3-2.5x^2-2.5x-3.5,$ $[-5.5,10.5]$

3. Seja $\epsilon \gt0,$ dado. Se $[a,b]$ é um intervalo onde há alternância de sinal para função $f,$ quantas iterações do método da bissecção serão necessárias para determinar uma aproximação para o zero de $f$ com um erro absoluto máximo de $\epsilon$? Por exemplo, quantas iterações seria necessárias se o intervalo inicial fosse $[0,2]$ e $\epsilon = 10^{-6}$?

O número mínimo de iterações deve ser maior que $\log_2((b-a)/\epsilon)$. No caso do exemplo, ao menos 21 iterações devem ser feitas.

4. Como o algoritmo apresentado poderia ser mais bem detalhado para evitar avaliações desnecessárias da função $f,$ isto é, evitar avaliar a função $f$ mais de uma vez no mesmo ponto?

Confira Aprofunde Exercite