O cálculo aproximado de
pode ser feito pela iteração dada pela equação abaixo.
© 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
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:
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
- 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}.
- 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).
- Conclusão:
N_{\rm bis}=\bigl\lceil\log_2(1/\varepsilon)\bigr\rceil
iterações.
Passo 3
Método de Newton
- Vamos chamar
. Da iteração
a gente tirax_{n+1} =\frac{x_n+p/x_n}2 =\sqrt p+\frac{(x_n-\sqrt p)^2}{2x_n},
e_{n+1} =\bigl|x_{n+1}-\sqrt p\bigr| =\frac{e_n^2}{2x_n}.
- Perto da raiz
, então é uma constante, e e_{n+1}\approx K\,e_n^2, \quad\text{com }K=\frac1{2\sqrt p}.
- 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 daí, para tere_n\le K^{(2^n-1)}\,e_0^{2^n},
, basta 2^n\gtrsim\log_{1/e_0}(\varepsilon)\quad\Longrightarrow\quad n\gtrsim\log_2\!\bigl(\log(1/\varepsilon)\bigr).
- 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
→ Parapequeno, 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
.) - Bissecção:
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).
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).