Considerando o critério \left|b_{k}-a_{k}\right|<\epsilon, onde a_{k}=x_{k} e b_{k}=x_{k+1} são aproximações consecutivas da raiz de f em um intervalo [a, b]. Mostre que uma estimativa para o número de iterações necessárias para se obter um resultado com precisão <\epsilon, pelo método da bissecção, é dada por:
k>\frac{\ln (b-a)-\ln (\epsilon)}{\ln (2)}

Passo 1

O enunciado dá o critério \left|b_{k}-a_{k}\right|<\epsilon, onde \;a_{k}=x_{k}\; e \;b_{k}=x_{k+1}\; são aproximações consecutivas da raiz de f dentro do intervalo inicial [a,b]. A pergunta é: mostrar que uma estimativa para o número de iterações k necessárias para garantir precisão <\epsilon pelo método da bissecção é
k>\frac{\ln (b-a)-\ln (\epsilon)}{\ln (2)}.
Lista das informações relevantes que temos agora:
\;[a,b] é o intervalo inicial com comprimento \;b-a>0\;,
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 k iterações satisfaça \left|b_{k}-a_{k}\right|<\epsilon com \epsilon>0.

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 [a,b] com comprimento \;b-a.
  • Calculamos o ponto médio \;m=\dfrac{a+b}{2}.
  • Escolhemos a submetade [a,m] ou [m,b] que contém a raiz (isso existe porque f(a) e f(b) têm sinais opostos).
    Portanto, após uma iteração o novo intervalo que contém a raiz tem comprimento \dfrac{b-a}{2}. 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 k iterações. Defina [a_0,b_0]=[a,b]. Para k\ge0, seja o comprimento L_k=\left|b_k-a_k\right|.
  • Base k=0: L_0=b-a.
  • Passo indutivo: suponha L_k=\dfrac{b-a}{2^{k}}. Depois de mais uma iteração o intervalo que contém a raiz tem comprimento L_{k+1}=\dfrac{L_k}{2}, porque bissecção sempre divide o intervalo corrente ao meio. Substituindo a hipótese indutiva,
L_{k+1}=\frac{1}{2}\cdot\frac{b-a}{2^{k}}=\frac{b-a}{2^{k+1}}.
Assim, por indução,
\left|b_{k}-a_{k}\right|=L_k=\frac{b-a}{2^{k}}\quad\text{para todo }k\ge0.

Passo 4

Impor a condição de precisão \left|b_{k}-a_{k}\right|<\epsilon. Usando a expressão do passo anterior, temos
\frac{b-a}{2^{k}}<\epsilon.
Queremos isolar k nesta desigualdade.

Passo 5

Resolver a desigualdade em k. Primeiro transformamos a desigualdade:
\frac{b-a}{2^{k}}<\epsilon
é equivalente (multiplicando por 2^{k} e dividindo por \epsilon>0) a
2^{k}>\frac{b-a}{\epsilon}.
Agora aplicamos o logaritmo natural (ou qualquer logaritmo de base maior que 1; vou usar \ln). Como a função \ln é crescente em (0,\infty), a desigualdade é preservada:
\ln\left(2^{k}\right)>\ln\!\left(\frac{b-a}{\epsilon}\right).
Usamos a propriedade dos logaritmos \ln\left(2^{k}\right)=k\ln(2) e \ln\!\left(\dfrac{b-a}{\epsilon}\right)=\ln(b-a)-\ln(\epsilon). Assim obtemos
k\ln(2)>\ln(b-a)-\ln(\epsilon).
Finalmente, dividindo por \ln(2)>0,
k>\frac{\ln(b-a)-\ln(\epsilon)}{\ln(2)}.

Passo 6

Interpretação prática: a desigualdade acima dá um limite real para k. Como k deve ser inteiro (número de iterações), o número mínimo de iterações necessárias para garantir \left|b_{k}-a_{k}\right|<\epsilon é o menor inteiro maior que o lado direito, isto é, k=\left\lceil\dfrac{\ln(b-a)-\ln(\epsilon)}{\ln(2)}\right\rceil. Observação: usei propriedades elementares de logaritmos (monotonicidade e \ln(x/y)=\ln x-\ln y) e o fato de que \ln(2)>0.

Resposta

k>\frac{\ln (b-a)-\ln (\epsilon)}{\ln (2)}

Exercícios relacionados