Considerando o critério
, onde
e
são aproximações consecutivas da raiz de
em um intervalo
. Mostre que uma estimativa para o número de iterações necessárias para se obter um resultado com precisão
, pelo método da bissecção, é dada por:
Passo 1
O enunciado dá o critério
, onde
e
são aproximações consecutivas da raiz de
dentro do intervalo inicial
. A pergunta é: mostrar que uma estimativa para o número de iterações
necessárias para garantir precisão
pelo método da bissecção é
Lista das informações relevantes que temos agora:
é o intervalo inicial com comprimento
,
a cada iteração do método da bissecção o intervalo que contém a raiz é reduzido pela metade,
e queremos que o comprimento do intervalo após iterações satisfaça
com
.
a cada iteração do método da bissecção o intervalo que contém a raiz é reduzido pela metade,
e queremos que o comprimento do intervalo após
Passo 2
Entender por que o comprimento do intervalo é dividido por 2 a cada iteração. Na bissecção:
- No início temos o intervalo
com comprimento . - Calculamos o ponto médio
. - Escolhemos a submetade
ou que contém a raiz (isso existe porque e têm sinais opostos).
Portanto, após uma iteração o novo intervalo que contém a raiz tem comprimento. Esse é o mecanismo básico: a cada iteração o comprimento do intervalo que sabemos conter a raiz é exatamente a metade do comprimento da iteração anterior.
Passo 3
Formalizar por recorrência (indução) a fórmula do comprimento após
iterações. Defina
. Para
, seja o comprimento
.
- Base
: . - Passo indutivo: suponha
. Depois de mais uma iteração o intervalo que contém a raiz tem comprimento , porque bissecção sempre divide o intervalo corrente ao meio. Substituindo a hipótese indutiva,
Assim, por indução,
Passo 4
Impor a condição de precisão
. Usando a expressão do passo anterior, temos
Queremos isolar
nesta desigualdade.
Passo 5
Resolver a desigualdade em
. Primeiro transformamos a desigualdade:
é equivalente (multiplicando por
e dividindo por
) a
Agora aplicamos o logaritmo natural (ou qualquer logaritmo de base maior que 1; vou usar
). Como a função
é crescente em
, a desigualdade é preservada:
Usamos a propriedade dos logaritmos
e
. Assim obtemos
Finalmente, dividindo por
,
Passo 6
Interpretação prática: a desigualdade acima dá um limite real para
. Como
deve ser inteiro (número de iterações), o número mínimo de iterações necessárias para garantir
é o menor inteiro maior que o lado direito, isto é,
. Observação: usei propriedades elementares de logaritmos (monotonicidade e
) e o fato de que
.