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

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) < 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_{*} | < \frac{1.437500 - 1.375000}{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_{*} | \to 0,$ quando $k \to \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 $ϵ > 0,$ o critério pode ser $| b_{k} - a_{k} | < ϵ,$ 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 < b$ , tais que $f (a) \cdot f (b) < 0$ , $K > 0$ e $ϵ > 0$ .
$k \leftarrow 0$
Enquanto $| b - a | > ϵ$ e $k < 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) < 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) < 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 $Ω = [- 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 $Ω$ . Aplicando o método da bissecção, partindo do intervalo $Ω$ , 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} d u,$ $[0, 2]$
$f (x) = x^{3} - 2.5 x^{2} - 2.5 x - 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 $ϵ > 0,$ 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 $ϵ$ ? Por exemplo, quantas iterações seria necessárias se o intervalo inicial fosse $[0, 2]$ e $ϵ = 10^{- 6}$ ?

O número mínimo de iterações deve ser maior que $\log_{2} ((b - a) / ϵ)$ . 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