Dado
, qual o menor número de iterações necessárias para que o método de bissecção encontre uma raiz com precisão
? Considere o intervalo inicial
.
Passo 1
O enunciado dá as seguintes informações e pede uma coisa bem específica.
- Dado
. - Intervalo inicial
(suponha que existe uma raiz em e que o método da bissecção pode ser aplicado). - Pergunta: qual o menor número de iterações
necessárias para que o método da bissecção encontre uma aproximação da raiz com precisão ? Ou seja, queremos tal que a aproximação obtida após iterações satisfaça .
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
que contém a raiz . - 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
.
Vou explicar isso com uma fórmula para o comprimento do intervalo após
iterações.
Passo 3
Defina o comprimento do intervalo inicial:
Após uma iteração o comprimento é
. Após duas iterações
. Em geral, por indução (ou observando a construção), após
iterações o comprimento do intervalo que contém a raiz é
Explicando a indução em duas frases: a base
vale; se num passo temos
, ao bisecar obtemos
. Pronto.
Passo 4
Agora relacione o comprimento do intervalo com o erro da aproximação.
- Em cada iteração normalmente tomamos como aproximação
o ponto médio do intervalo atual. - Se o intervalo atual tem comprimento
, 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
Essa é a estimativa clássica de erro do método da bissecção: depois de
iterações o erro é, no máximo,
.
Passo 5
Queremos que esse erro máximo seja menor ou igual a
. Então impomos a desigualdade
A partir daqui isolamos
. Primeiro invertemos e aplicamos logaritmo na base
(mostro cada passo):
Aplicando
em ambos os lados:
Subtraindo
:
Uma forma equivalente é escrever
pois
.
Passo 6
Como
deve ser um número inteiro (número de iterações), o menor
que satisfaz a desigualdade é o teto (ceil) do lado direito. Portanto o número mínimo de iterações exigidas é
Expliquei por que usamos teto: se a quantidade à direita for, por exemplo,
, precisamos de
iterações inteiras para garantir o erro
.
Passo 7
Exemplo numérico rápido (para fixar): se
e
, então
Ou seja, com 9 iterações garantimos erro
.