Exercício 17 (Desafio) - Ordem de convergência
(a) Mostre que se
e
, então o Método do Ponto Fixo converge quadraticamente (ordem 2).
(b) Para
e
, verifique que
, execute 5 iterações a partir de
e confirme a convergência quadrática estimando
.
(c) Mostre que o Método de Newton é o caso
e que
para qualquer raiz simples
.
(b) Para
(c) Mostre que o Método de Newton é o caso
Passo 1
Vou listar com clareza o que o enunciado pede e quais informações temos:
- O enunciado tem três partes: (a), (b) e (c). Preciso responder cada uma.
- Informações dadas:
- Em (a): existe uma função
com uma raiz fixa (ou seja, ) e sabe-se que e . Pede-se mostrar que o Método do Ponto Fixo (iteração ) converge com ordem 2 (quadraticamente) para . - Em (b):
e . Deve-se verificar , executar 5 iterações a partir de e estimar para confirmar a convergência quadrática. Aqui é a raiz desejada. - Em (c): mostrar que o Método de Newton corresponde a
e que para uma raiz simples (ou seja, e ) vale .
- Em (a): existe uma função
O que vou fazer: em (a) usarei o desenvolvimento de Taylor de
em torno de
e definirei o erro
. Em (b) calcularei derivadas de
, executarei explicitamente as 5 iterações, computarei os erros
e estimarei a constante
. Em (c) mostrarei algebraicamente a forma de
do Método de Newton e calcularei
.
Passo 2
Conceitos e definições que vamos usar (explicadinho, sem pressa):
- Ordem de convergência: se
e existem e tais que
então dizemos que a iteração converge com ordem
e constante assintótica
. No caso quadrático,
.
- Taylor de segunda ordem com resto: se
é perto de , então para próximo a
onde o resto
quando
. Isto significa que
.
- Aplicação ao ponto fixo: como
, a expansão acima permitirá expressar o erro da iteração em termos de potência do erro anterior.
Passo 3
Prova detalhada de (a): mostrar ordem 2 quando
e
.
- Escrevemos a expansão de Taylor de
em torno de :
Como
(fixo) e
pelo enunciado, isso reduz para
- Substitui-se agora
. Então
Por definição
. Assim
- Pelo comportamento do resto temos
quando . Ou seja,
- Dividindo a expressão de
por obtemos
Tomando limite quando
(isto é,
), pela propriedade do resto,
- Conclusão: o limite existe finito e não nulo (porque
). Portanto a ordem de convergência é (quadrática) e a constante assintótica é . Observação prática: isso vale localmente, ou seja, para suficientemente próximo de , a iteração converge e com ordem 2.
Passo 4
Agora parte (b): verificação de
e execução de 5 iterações a partir de
.
- Primeiro calculemos
e para a dada :
Derivando:
Derivando de novo:
- Avaliando em
:
Portanto a hipótese de (a) está verificada:
e
.
- Agora executamos as iterações. Lembre que
. Tomando :
-
. -
Calcule
:
- Calcule
:
- Calcule
:
Calculando numericamente
. Assim
- Calcule
:
Numéricamente
. Então
- Calcule
:
Numéricamente
(valores arredondados) e
- Agora calculamos os erros
. Usaremos .
- Estimativa da constante
. Pelo item (a) esperamos
Vamos estimar numericamente
para alguns
grandes o suficiente (onde o comportamento assintótico já aparece):
- Para
:
- Para
:
Ambos os valores aproximam muito bem
. Isso confirma a convergência quadrática e a constante esperada.
Passo 5
Parte (c): mostrar que o Método de Newton é o caso
e que
para raiz simples
.
- Definição do Método de Newton: dada
com derivada não nula perto da raiz, a iteração é
Portanto toma-se
. Assim Newton é um caso particular do Método do Ponto Fixo com essa
.
- Calculemos
explicitamente. Escrevemos com . Então
Calcule
usando a regra do quociente:
Logo
- Agora avaliamos em
que é uma raiz simples: e . Substituindo:
Portanto
sempre que
é raiz simples. Pelo item (a) isso explica por que o Método de Newton costuma ter convergência quadrática localmente (de fato, Newton tem ordem 2 sob hipóteses standard).
Resposta
(a) A iteração converge com ordem 2 (quadraticamente) e a constante assintótica é
.\n
(b) . As iterações a partir de
dão aproximadamente
. Estimando
obtemos
, confirmando convergência quadrática.\n
(c) O Método de Newton corresponde a e para qualquer raiz simples
vale
.
(b)
(c) O Método de Newton corresponde a