4- É possível saber quantas interações são necessárias para se conseguir resolver uma equação pelo método de Newton?

Passo 1

O enunciado pergunta se dá para saber de antemão quantas iterações do método de Newton serão necessárias para obter uma aproximação de determinada precisão. O conteúdo envolvido é a convergência local quadrática de Newton e o que vamos precisar é o estimador de erro a priori, que depende de um limite superior para f'' e de um limite inferior para lvert f'(alpha)rvert.

Passo 2

Lembrando o método de Newton, a iteração é
xn+1 ;=; xn - f(xn)f'(xn),
e, sob as hipóteses
  1. fin C^2 num intervalo contendo a raiz alpha,
  2. f'(alpha)neq 0,
  3. existem constantes M e m>0 tais que lvert f''(x)rvert<= M e lvert f'(x)rvert>= m nesse intervalo,
    determina-se que o erro en=|xn-alpha| satisfaz localmente uma desigualdade quadrática.

Passo 3

Pela expansão de Taylor em torno de alpha e usando as hipóteses acima chega-se ao estimador
en+1 ;=; |xn+1-alpha|;<=;M2,m,en^2
vamos chamar de
K = M2,m,
logo
en+1<= K,en^2

Passo 4

Iterando essa relação por indução, obtém-se
en <= K^(2^n-1),e0^,2^n
Em particular, se K,e0<1, aí o método converge quadráticamente.

Passo 5

Para garantir eN<=varepsilon (tolerância desejada), basta resolver
K^(2^N-1),e0^2^N<=varepsilon
Tomando logaritmo em ambos os lados e desprezando termos constantes, chega-se a
2^N,ln(K,e0);<=;ln(varepsilon,K) Longrightarrow 2^N ;>=;ln(varepsilon,K)ln(K,e0)
e, finalmente, isolando N,
N ;>=;log2!l(tfracln(varepsilon,K)ln(K,e0)r)
Como N precisa ser inteiro, toma-se
N = lceil log2!l(tfracln(varepsilon,K)ln(K,e0)r) rceil

Passo 6

Esse N é um limite superior a priori para o número de iterações necessárias até a precisão varepsilon. Na prática, M, m e e0 não são exatamente conhecidos, então não dá para saber o número exato, mas podemos estimar um teto N antes de iterar.

Resposta

Sim: embora não se determine exatamente o número de passos sem informação precisa de e0, M e m, a análise de convergência quadrática de Newton fornece um estimador a priori. Se lvert f''(x)rvert<= M, lvert f'(alpha)rvert>= m e K=M/(2m), então para atingir erro varepsilon basta
N ;=;lceil log2!l(tfracln(varepsilon,K)ln(K,e0)r) rceil
iterações.

Exercícios relacionados