Dado \epsilon>0, qual o menor número de iterações necessárias para que o método de bissecção encontre uma raiz com precisão \epsilon ? Considere o intervalo inicial [a, b].

Passo 1

O enunciado dá as seguintes informações e pede uma coisa bem específica.
  • Dado \epsilon>0.
  • Intervalo inicial [a,b] (suponha que existe uma raiz r em [a,b] e que o método da bissecção pode ser aplicado).
  • Pergunta: qual o menor número de iterações n necessárias para que o método da bissecção encontre uma aproximação da raiz com precisão \epsilon? Ou seja, queremos n tal que a aproximação x_n obtida após n iterações satisfaça |x_n-r|\le\epsilon.

Passo 2

Lembra rapidamente como o método da bissecção constrói aproximações (isso é importante para entender o erro).
  • Começamos com o intervalo inicial [a,b] que contém a raiz r.
  • Em cada iteração tomamos o ponto médio do intervalo atual e escolhemos a metade que contém a raiz.
  • Assim, a cada iteração o comprimento do intervalo que sabemos conter a raiz é dividido por 2.
Vou explicar isso com uma fórmula para o comprimento do intervalo após n iterações.

Passo 3

Defina o comprimento do intervalo inicial:
L_0 = b-a.
Após uma iteração o comprimento é L_1 = \dfrac{b-a}{2}. Após duas iterações L_2=\dfrac{b-a}{2^2}. Em geral, por indução (ou observando a construção), após n iterações o comprimento do intervalo que contém a raiz é
L_n = \dfrac{b-a}{2^n}.
Explicando a indução em duas frases: a base n=0 vale; se num passo temos L_n=(b-a)/2^n, ao bisecar obtemos L_{n+1}=L_n/2=(b-a)/2^{n+1}. Pronto.

Passo 4

Agora relacione o comprimento do intervalo com o erro da aproximação.
  • Em cada iteração normalmente tomamos como aproximação x_n o ponto médio do intervalo atual.
  • Se o intervalo atual tem comprimento L_n, o ponto médio está no centro, portanto a distância máxima entre o ponto médio e a raiz (que está em algum lugar dentro do intervalo) é metade do comprimento do intervalo.
  • Logo o erro satisfaça
|x_n-r| \le \frac{L_n}{2} = \frac{b-a}{2^{n+1}}.
Essa é a estimativa clássica de erro do método da bissecção: depois de n iterações o erro é, no máximo, (b-a)/2^{n+1}.

Passo 5

Queremos que esse erro máximo seja menor ou igual a \epsilon. Então impomos a desigualdade
\frac{b-a}{2^{n+1}} \le \epsilon.
A partir daqui isolamos n. Primeiro invertemos e aplicamos logaritmo na base 2 (mostro cada passo):
2^{n+1} \ge \frac{b-a}{\epsilon}.
Aplicando \log_2 em ambos os lados:
n+1 \ge \log_2\!\left(\frac{b-a}{\epsilon}\right).
Subtraindo 1:
n \ge \log_2\!\left(\frac{b-a}{\epsilon}\right) - 1.
Uma forma equivalente é escrever
n \ge \log_2\!\left(\frac{b-a}{2\epsilon}\right),
pois \log_2\!\left(\dfrac{b-a}{2\epsilon}\right)=\log_2\!\left(\dfrac{b-a}{\epsilon}\right)-1.

Passo 6

Como n deve ser um número inteiro (número de iterações), o menor n que satisfaz a desigualdade é o teto (ceil) do lado direito. Portanto o número mínimo de iterações exigidas é
n_{\min}=\left\lceil \log_2\!\left(\frac{b-a}{2\epsilon}\right)\right\rceil.
Expliquei por que usamos teto: se a quantidade à direita for, por exemplo, 3{,}2, precisamos de 4 iterações inteiras para garantir o erro \le\epsilon.

Passo 7

Exemplo numérico rápido (para fixar): se [a,b]=[0,1] e \epsilon=10^{-3}, então
n_{\min}=\left\lceil \log_2\!\left(\frac{1-0}{2\cdot 10^{-3}}\right)\right\rceil =\left\lceil \log_2(500)\right\rceil =\left\lceil 8{,}9658\ldots\right\rceil=9.
Ou seja, com 9 iterações garantimos erro \le 10^{-3}.

Resposta

\displaystyle n_{\min}=\left\lceil \log_2\!\left(\frac{b-a}{2\epsilon}\right)\right\rceil

Exercícios relacionados