O cálculo aproximado de raizp pode ser feito pela iteração dada pela equação abaixo.
xn+1=12(xn+pxn)
© Compare o número de iterações desse método com o número de iterações que seriam necessárias para o método da bissecção a partir do intervalo [1,2], para a função utilizada em (b).

Passo 1

Beleza, a questão © pede pra comparar quantas iterações a gente precisa usar do método de Newton
x_{n+1}=\frac12\Bigl(x_n+\frac p{x_n}\Bigr)
para achar
versus o método da bissecção aplicando na função
f(x)=x^2-p
no intervalo .
Matéria: métodos numéricos de raiz (bissecção e Newton) e análise de convergência (linear vs. quadrática).
O que vamos precisar:
  • Fórmula de erro da bissecção.
  • Expressão de erro no Newton e conceito de convergência quadrática.

Passo 2

Método da bissecção
  1. A cada iteração a gente corta o intervalo ao meio, então o erro máximo satisfaz
    |x_n-\sqrt p|\le\frac{2-1}{2^n}=\frac1{2^n}.
    
  2. Queremos isso ≤ , logo
    \frac1{2^n}\le\varepsilon
      \quad\Longrightarrow\quad
    2^n\ge\frac1\varepsilon
      \quad\Longrightarrow\quad
    n\ge\log_2\!\Bigl(\frac1\varepsilon\Bigr).
    
  3. Conclusão:
    N_{\rm bis}=\bigl\lceil\log_2(1/\varepsilon)\bigr\rceil
    
iterações.

Passo 3

Método de Newton
  1. Vamos chamar . Da iteração
    x_{n+1}
     =\frac{x_n+p/x_n}2
     =\sqrt p+\frac{(x_n-\sqrt p)^2}{2x_n},
    
    a gente tira
    e_{n+1}
     =\bigl|x_{n+1}-\sqrt p\bigr|
     =\frac{e_n^2}{2x_n}.
    
  2. Perto da raiz , então é uma constante, e
    e_{n+1}\approx K\,e_n^2,
      \quad\text{com }K=\frac1{2\sqrt p}.
    
  3. Esse “ ” mostra convergência quadrática:
    • Na prática, depois de cada iteração o log do erro dobra.
    • Se você escrever recursivamente, dá algo como
      e_n\le K^{(2^n-1)}\,e_0^{2^n},
      
      e daí, para ter , basta
      2^n\gtrsim\log_{1/e_0}(\varepsilon)\quad\Longrightarrow\quad
      n\gtrsim\log_2\!\bigl(\log(1/\varepsilon)\bigr).
      
  4. Conclusão aproximada:
    N_{\rm Newton}
      =\mathcal O\bigl(\log_2\log_2(1/\varepsilon)\bigr).
    

Passo 4

Comparação direta
  • Bissecção: cresce como convergência linear
  • Newton: cresce como convergência quadrática
    → Para pequeno, Newton precisa de pouquíssimas iterações, bissecção bem mais.

Passo 5

Exemplo numérico (pra sentir na pele):
  • Se :
    • Bissecção:
      N_{\rm bis}\approx\lceil\log_2(10^6)\rceil\approx20.
      
    • Newton (usando ):
      N_{\rm Newton}\approx\lceil\log_2(\log_2(10^6))\rceil
                      =\lceil\log_2(20)\rceil=5
      
    (na prática geralmente basta até 3–4 iterações para alcançar .)

Resposta

O método de Newton precisa de um número de iterações da ordem de
,
enquanto a bissecção exige
.
Isto é, Newton (convergência quadrática) atinge a precisão desejada em MUITO menos passos do que a bissecção (convergência linear).

Exercícios relacionados