Exercício 23 (Teórico) - Ordem de convergência da Secante
A ordem de convergência do Método da Secante é
(número áureo).
(a) Admitindo que
e usando a relação da secante com diferenças divididas, mostre que
satisfaz
e conclua que
.
(b) Verifique numericamente a ordem
para o exercício anterior, estimando
.
(c) A secante precisa de duas avaliações de
por iteração, enquanto Newton precisa de uma de
e uma de
. Em termos de “avaliações por dígito correto”, qual é mais eficiente? Justifique comparando
com
.
(a) Admitindo que
(b) Verifique numericamente a ordem
(c) A secante precisa de duas avaliações de
Passo 1
O que o enunciado dá e o que pede:
- Dá: a afirmação que a ordem de convergência do método da secante é
. - Dá a hipótese assintótica que podemos escrever
para algum e ordem . - Pede:
(a) partir da relação da secante com diferenças divididas, mostrar quesatisfaz e concluir ;
(b) verificar numericamente a ordemestimando (isto é, dar a forma de verificação e calcular se houver dados numéricos);
(c) discutir eficiência em termos de “avaliações por dígito correto”, comparandocom e concluir qual método é mais eficiente.
Passo 2
Definições e fórmula da secante (colocando tudo explícito).
- Seja
uma raiz simples de (ou seja e ). - Defina o erro em cada iteração por
. - A iteração da secante escreve-se
Substituindo
convertemos a atualização em uma relação entre
. O objetivo é obter a forma assintótica mais baixa ordem de
em termos de
.
Passo 3
Expansão de Taylor de
perto da raiz
— por que e como usar.
- Como
é raiz simples, expandimos em Taylor em torno de :
quando
. Aqui
significa “termos da ordem de
ou mais pequenos”.
- Aplicando isso a
e a obtemos:
Passo 4
Aproximação da diferença dividida (denominador da secante).
- A diferença dividida que aparece na secante é
- Substituindo as expansões e lembrando que
, obtemos, para termos até ordem linear em ,
Isto é natural: a diferença dividida aproxima a derivada
mais um pequeno termo proporcional a
.
Passo 5
Substituir no esquema da secante e expandir para obter a relação entre erros.
- A fórmula da secante reescrita com as expansões dá
- Substituindo
e a expressão da diferença dividida do passo anterior, e usando a expansão em série para , obtemos (mantendo só os termos dominantes):
- Observe que os termos em
se cancelam: . O termo remanescente de menor ordem é
- Defina a constante
Assim a relação assintótica principal é
quando
é grande (regime assintótico).]
Passo 6
Usar a hipótese
para obter a equação para
.
- A hipótese nos dá também, deslocando índices,
- Da segunda equação isolamos
em termos de :
- Substituindo
na relação do passo anterior obtemos
- Mas pela hipótese também
. Igualando as potências de (ou seja, os expoentes dominantes) dá
- Multiplicando por
obtemos a equação quadrática
Passo 7
Resolver a quadrática e concluir
.
- A solução positiva da equação
é
- Portanto a ordem de convergência assintótica do método da secante é
Passo 8
Como verificar numericamente a ordem
(resposta ao item (b)) — procedimento e observações.
- Procedimento prático, supondo que se tenha os iterados
e uma boa aproximação da raiz : - Calcule os erros
para suficientemente grandes (regime assintótico). - Para cada
compute a razão
- Se o método tem ordem
, então tende para uma constante não nula quando . Numericamente espera-se ver estabilizando para valores próximos entre iterações.
- Calcule os erros
- Observação importante: para executar isso são necessários os valores numéricos dos iterados (ou dos erros) do “exercício anterior”. Sem esses dados não há como produzir os números pedidos. Portanto, sem os
ou sem (ou sem as diferenças ) não é possível calcular as razões numéricas pedidas. - Exemplo ilustrativo (independente do seu enunciado anterior): se se quisesse testar em um caso concreto, escolheria uma função simples com raiz conhecida (por exemplo
, raiz ), rodaria a secante com chutes iniciais, recolheria os , computaria e depois os . Uma estabilização de confirma numericamente a ordem .
Passo 9
Discussão de eficiência em termos de “avaliações por dígito correto” (item (c)).
- Definição prática usada aqui: a ordem
indica a “potência” com que o erro diminui por iteração (erro reduz como ). Uma métrica de eficiência é comparar essa ordem com o custo por iteração, medido em número de avaliações caras (tipicamente chamadas de "avaliações de " e também contando a avaliação de se custosa). - Custos por iteração:
- Secante: precisa de duas avaliações de
por iteração (em e em ), portanto custo ≈ avaliações por iteração; ordem . Eficiência aproximada: . - Newton: precisa de uma avaliação de
e de por iteração. Se considerarmos avaliação de com custo semelhante ao de , então o custo por iteração é aproximadamente avaliações e a ordem é , portanto eficiência aproximada: . - Se, alternativamente, a avaliação de
for considerada desprezível (ou já disponível a baixo custo), pode-se ver Newton como tendo custo caro por iteração e então a razão mostrada no enunciado seria usada — isto só é válido quando realmente o custo de é desprezível.
- Secante: precisa de duas avaliações de
- Numericamente:
- Conclusão: em termos práticos e razoáveis (contando avaliação de
com custo similar ao de ), a eficiência de Newton ( unidade de ordem por avaliação) é maior que a da secante ( ). Mesmo no cenário otimista para Newton em que é “gratuito”, Newton fica ainda mais vantajoso. Logo, em termos de “avaliações por dígito correto” o método de Newton é, de modo geral, mais eficiente que a secante.
Resposta
(a)
satisfaz
, portanto
.
(b) Não é possível verificar numericamente pois os iterados (ou os erros ) do exercício anterior não foram fornecidos; o procedimento é calcular
e observar a estabilização de
.
(c) (secante) é menor que
(Newton contando
com custo igual a
); portanto Newton é mais eficiente em avaliações por dígito correto (e, se
fosse “gratuito”, Newton seria ainda mais vantajoso:
).
(b) Não é possível verificar numericamente pois os iterados (ou os erros
(c)