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_*|.$

$\newcommand{\R}{\mathbb{R}}$

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.$

Como exemplo, considere a função $f:\R\to\R$, dada por $$ f(x) = x^2-e^{x/2}. $$ Observe $f$ é uma função contínua e existe um zero no intervalo $[0,2],$ uma vez que $f(0)\cdot f(2) \lt 0.$ Vamos utilizar o Octave para realizar algumas iterações do método da bissecção.

f = @(x) x.^2 - exp(x/2);    # definição da função
a = 0; b = 2; m = (a+b)/2;   # extremos do intervalo e ponto médio

# exibe a,m e b e os valores de f nos extremos e no ponto médio
[a m b; f(a) f(m) f(b)]
ans =

        0   1.0000   2.0000
  -1.0000  -0.6487   1.2817

# como f(m)·f(b) < 0, a é atualizado para m
a = m; m = (a+b)/2; [a m b; f(a) f(m) f(b)]
ans =

   1.0000   1.5000   2.0000
  -0.6487   0.1330   1.2817

# como f(a)·f(m) < 0, b é atualizado para m
b = m; m = (a+b)/2; [a m b; f(a) f(m) f(b)]
ans =

   1.0000   1.2500   1.5000
  -0.6487  -0.3057   0.1330

# como f(m)·f(b) < 0, a é atualizado para m
a = m; m = (a+b)/2; [a m b; f(a) f(m) f(b)]
ans =

   1.250000   1.375000   1.500000
  -0.305746  -0.098112   0.133000

# como f(m)·f(b) < 0, a é atualizado para m
a = m; m = (a+b)/2; [a m b; f(a) f(m) f(b)]
ans =

   1.375000   1.437500   1.500000
  -0.098112   0.014539   0.133000

# como f(a)·f(m) < 0, b é atualizado para m
b = m; m = (a+b)/2; [a m b; f(a) f(m) f(b)]
ans =

   1.375000   1.406250   1.437500
  -0.098112  -0.042516   0.014539

Ao cabo de seis iterações, descobrimos que um zero de $f$ está confinado no intervalo $[1.375000, 1.437500].$ Neste momento, se decidirmos interromper as iterações, podemos dizer que o ponto médio deste último intervalo, $m = 1.406250$ é uma aproximação para $x_*$, zero de $f,$ tal que $$ |m - x_*| \lt {1.437500-1.375000\over 2} = 0.03125. $$

Uma 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, $|m_k-x_*|\rightarrow 0,$ quando $k\rightarrow \infty,$ onde por $m_k$ refere-se ao ponto médio obtido na iteração $k.$ Claro que, do ponto de vista prático, é necessário estipular um critério de parada. Dado um $\epsilon \gt 0,$ o critério pode ser $|b_k-a_k| \lt \epsilon,$ para $a_k$ e $b_k$ os extremos do intervalo no passo $k.$

Abaixo vemos como todas essas ideias podem ser transcritas em um algoritmo , que pode ser implementado, para evitar executar manualmente cada passo do método, como foi feito no exemplo acima.

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

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

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

A obtenção de uma aproximação com a precisão desejada pode demandar uma grande quantidade de iterações (no exemplo acima, depois de 6 iterações, só era possível garantir que a aproximação conseguida tinha uma casa decimal correta). 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.

Implementação computacional

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(m) \lt 0,$ ambos os valores de função não devem ser avaliados, mas sim reaproveitados de avaliações anteriores.

Sobre o critério de parada, é saudável incluir também um limite para o número máximo de iterações. Mesmo sabendo que o método da bissecção tem convergência assegurada, isto evita que o algoritmo execute um número inviável de iterações, por exemplo quando o intervalo inicial é grande demais. Isto também evita a situação onde o critério para declarar convergência, eventualmente, não pode ser atingido por problemas numéricos.

Por fim, como alternativa ao método da bissecção, há métodos que utilizam mais informação sobre a função e, portanto, são mais rápidos. 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]$

(a) $1.57079649.$ (b) $0.$ (c) não há alternância de sinal no intervalo $[-1,2].$ (d) $1.65285158.$ (e) $3.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 Discuta