Exercício 5 - Iterações manuais

Aplique o Método da Bisseção à função f(x)=x^{3}-x-2 no intervalo [1,2], com tolerância \varepsilon=10^{-2}.
(a) Execute as iterações em uma tabela com colunas k, a_{k}, b_{k}, c_{k}, f\left(c_{k}\right), b_{k}-a_{k}.
(b) Usando a fórmula teórica k \geq \log _{2}\left(\frac{b_{0}-a_{0}}{\varepsilon}\right)-1, preveja o número de iterações necessárias e compare com o obtido experimentalmente.
(c) Qual é o erro máximo garantido após 10 iterações?

Passo 1

O enunciado dá a função f(x)=x^{3}-x-2, o intervalo inicial [a_{0},b_{0}]=[1,2] e a tolerância \varepsilon=10^{-2}. As perguntas são:
  • (a) Aplicar o Método da Bisseção até a tolerância e apresentar as iterações numa tabela com colunas k,\;a_{k},\;b_{k},\;c_{k},\;f(c_{k}),\;b_{k}-a_{k}.
  • (b) Usar a fórmula teórica \displaystyle k \geq \log_{2}\!\left(\frac{b_{0}-a_{0}}{\varepsilon}\right)-1 para prever o número de iterações e comparar com o obtido experimentalmente.
  • (c) Calcular o erro máximo garantido após 10 iterações.
Informações relevantes tiradas do enunciado:
  • f(1)=1^{3}-1-2=-2 e f(2)=2^{3}-2-2=4, logo há uma raiz em (1,2) por mudança de sinal.
  • Critério de parada adotado: interromper quando o comprimento do intervalo b_{k}-a_{k} ficar menor ou igual a \varepsilon=10^{-2}. (Irei usar esse critério, que é o mais comum para bisseção.)

Passo 2

Pequena aula sobre o Método da Bisseção (sem pular etapas):
  • Ideia: se f é contínua em [a,b] e f(a)\cdot f(b)<0, existe pelo menos uma raiz em (a,b).
  • Em cada iteração calcula-se o ponto médio \displaystyle c=\frac{a+b}{2}.
  • Verifica-se o sinal de f\text{(c)}:
    • Se f(a)\cdot f\text{(c)}<0, a raiz está em [a,c] e define-se b\leftarrow c.
    • Se f\text{(c)}\cdot f(b)<0, a raiz está em [c,b] e define-se a\leftarrow c.
    • Se f\text{(c)}=0, a raiz foi encontrada exatamente em c.
  • O comprimento do intervalo após n bisseções é \displaystyle b_{n}-a_{n}=\frac{b_{0}-a_{0}}{2^{n}}.
  • Uma cota simples para o erro absoluto da aproximação por ponto médio c_{n} é |r-c_{n}|\le \frac{b_{n}-a_{n}}{2}=\frac{b_{0}-a_{0}}{2^{n+1}},onde r é a raiz exata. Essa desigualdade é a usada para derivar a fórmula teórica dada no enunciado: \frac{b_{0}-a_{0}}{2^{k+1}}\le \varepsilon \quad\Longleftrightarrow\quad k\ge \log_{2}\!\left(\frac{b_{0}-a_{0}}{\varepsilon}\right)-1.

Passo 3

Agora aplico o método na prática, iteração a iteração. Vou numerar as iterações com k=0,1,2,\dots, onde (a_{0},b_{0})=(1,2) e c_{k}=(a_{k}+b_{k})/2. Em cada linha explico a escolha do próximo intervalo pelo teste de sinal f(a_{k})\cdot f(c_{k}).
Tabela com as iterações (valores aproximados com precisão suficiente para a prova; uso vírgula para separador decimal):
\begin{array}{c|c|c|c|c|c} k & a_{k} & b_{k} & c_{k} & f(c_{k}) & b_{k}-a_{k} \\\ \hline 0 & 1 & 2 & 1{,}5 & -0{,}125000000000000 & 1 \\[2pt] 1 & 1{,}5 & 2 & 1{,}75 & 1{,}609375 & 0{,}5 \\[2pt] 2 & 1{,}5 & 1{,}75 & 1{,}625 & 0{,}666015625 & 0{,}25 \\[2pt] 3 & 1{,}5 & 1{,}625 & 1{,}5625 & 0{,}252197265625 & 0{,}125 \\[2pt] 4 & 1{,}5 & 1{,}5625 & 1{,}53125 & 0{,}059112548828125 & 0{,}0625 \\[2pt] 5 & 1{,}5 & 1{,}53125 & 1{,}515625 & -0{,}0339488983154297 & 0{,}03125 \\[2pt] 6 & 1{,}515625 & 1{,}53125 & 1{,}5234375 & 0{,}0122232437133789 & 0{,}015625 \\[2pt] 7 & 1{,}515625 & 1{,}5234375 & 1{,}51953125 & -0{,}0110635757446289 & 0{,}0078125 \end{array}
Como se lê a tabela (exemplo das primeiras linhas):
  • Em k=0 calculamos c_{0}=(1+2)/2=1{,}5. Como f(1)=-2 e f(1{,}5)=-0{,}125 têm mesmo sinal, trocamos a\leftarrow c ou, mais precisamente, como f(1)\cdot f(1{,}5)>0 escolhemos o subintervalo com mudança de sinal que é [1{,}5,2].
  • Seguindo assim escolhemos em cada iteração o intervalo onde ocorre a mudança de sinal.
Observação sobre o critério de parada: estou usando o critério b_{k}-a_{k}\le \varepsilon. Na tabela vemos que em k=6 ainda temos b_{6}-a_{6}=0{,}015625>0{,}01, e em k=7 obtemos b_{7}-a_{7}=0{,}0078125\le 0{,}01. Portanto obtemos o intervalo desejado pela primeira vez em k=7. A aproximação pela bisseção nesse ponto é
c_{7}=1{,}51953125,
com f(c_{7})\approx -0{,}0110636.]

Passo 4

Resposta da parte (a) e interpretação:
  • A tabela do Passo 3 é a execução pedida.
  • Usando o critério b_{k}-a_{k}\le \varepsilon foram necessárias 7 iterações (isto é, a primeira k com b_{k}-a_{k}\le 10^{-2} é k=7).
  • A aproximação resultante é c_{7}=1{,}51953125 e o intervalo final é [1{,}515625,\;1{,}5234375].
Dica emocional rápida: ótimo — já se tem a tabela e a aproximação. Keep going; você consegue!

Passo 5

Parte (b): usar a fórmula teórica dada e comparar com o experimental.
  • Aplicando a fórmula do enunciado: k \ge \log_{2}\!\left(\frac{b_{0}-a_{0}}{\varepsilon}\right)-1com b_{0}-a_{0}=1 e \varepsilon=10^{-2}, temos k \ge \log_{2}(100)-1 \approx 6{,}643856189774725-1=5{,}643856189774725.Tomando o inteiro mínimo que satisfaz essa desigualdade obtemos k=6 (ou seja, a fórmula dada prevê 6 iterações).
  • Comparação com o experimental: na prática (Passo 3) foi necessário 7 iterações para que b_{k}-a_{k}\le 10^{-2}.
  • Explicação da diferença: é uma diferença de índice/definição. A fórmula dada no enunciado está escrita no formato com o -1; se em vez disso usássemos diretamente a condição b_{n}-a_{n}=\dfrac{b_{0}-a_{0}}{2^{n}}\le \varepsilon e isolássemos n obteríamos n \ge \log_{2}\!\left(\frac{b_{0}-a_{0}}{\varepsilon}\right),que dá n\ge \log_{2}(100)\approx 6{,}6438 e portanto n=7 quando arredondado para cima. Em suma: a fórmula do enunciado (com o -1) prevê 6 no seu índice, mas o critério prático de comprimento do intervalo exige 7 bisseções para garantir b_{k}-a_{k}\le 10^{-2}. É uma questão puramente de como se conta k (se começa a contar em zero e qual expressão se usa para a cota de erro do ponto médio).

Passo 6

Parte (c): erro máximo garantido após 10 iterações.
Usando a cota apresentada no Passo 2,
|r-c_{n}|\le \frac{b_{0}-a_{0}}{2^{n+1}}.
Para n=10 e b_{0}-a_{0}=1 obtemos
|r-c_{10}|\le \frac{1}{2^{11}}=\frac{1}{2048}=0{,}00048828125.
Portanto o erro máximo garantido após 10 iterações é 1/2048\approx 0{,}00048828125.

Resposta

(a) Intervalo final [1{,}515625,\;1{,}5234375], c=1{,}51953125; número de iterações realizadas =7.
(b) Previsão pela fórmula dada: k=6; experimentalmente foram necessárias 7 iterações (diferença por convenção de índice/critério).
(c) Erro máximo garantido após 10 iterações: \dfrac{1}{2048}=0{,}00048828125.

Exercícios relacionados