Para cada uma das equações abaixo, cheque quantas operações “complicadas” (exp, log, sen, cos) são necessárias para um passo do método de Newton e para o passo do método da secante. Assumindo que essas operações sejam a parte dominante do tempo que o método tomaria (e que todas operações complicadas levem o mesmo tempo), qual dos dois métodos (secante ou Newton) seria o mais rápido (para obter a mesma precisão)? (note que é possível reaproveitar valores para reduzir o número necessário dessas operações)
(b)
(b)
Passo 1
O enunciado pede que, para a equação
a gente conte quantas operações “complicadas” (exp, log, sen, cos) são necessárias para um passo do método de Newton e para um passo do método da secante, assumindo que só essas operações dominam o tempo. Devemos considerar reaproveitamento de valores quando possível e, ao final, decidir qual método seria mais rápido para obter a mesma precisão.
Informações relevantes dadas:
Não há outros dados (como aproximações iniciais), então trabalharemos com o custo por iteração no regime assintótico (quando já estamos na fase de convergência e podemos reaproveitar valores das iterações anteriores).
Passo 2
Relembrando o método de Newton (fórmula e o que precisa calcular):
A iteração de Newton é
A iteração de Newton é
Primeiro calculamos
e
. Vamos derivar
:
pois a derivada de
é
(produto:
=
).
Quais operações complicadas aparecem ao avaliar
e
?
- Para
precisamos de — uma operação complicada. - Para
precisamos de (já calculada) e de — outra operação complicada.
Podemos reaproveitar
entre
e
. Logo, no total por passo de Newton precisamos calcular:
-
(1 operação complicada), -
(1 operação complicada).
Total:operações complicadas por iteração de Newton.
Passo 3
Agora o método da secante (fórmula e análise do custo):
A iteração da secante usa duas aproximações anteriores e
:
A iteração da secante usa duas aproximações anteriores
Para executar um passo típico, assumimos que já temos armazenados
e os valores
calculados na iteração anterior (é pratica comum guardar estes valores). Então, para produzir
só precisamos avaliar
no novo ponto quando avançarmos — ou, mais precisamente, no passo que gera
precisamos do valor de
(que já temos) e de
(que já temos); para o próximo passo só precisaremos avaliar
no novo
. Portanto, por passo novo da secante precisamos calcular apenas um novo
.
Avaliar
exige apenas
(uma operação complicada). Não precisamos de
. Logo, por iteração da secante (reaproveitando valores anteriores) precisamos de:
-
— operação complicada por passo.
Observação sobre o início: a secante precisa de duas avaliações iniciais de
para começar, mas isso é um custo fixo amortizado; o que importa para comparação assintótica por precisão é o custo por iteração já em andamento.
Passo 4
Comparação considerando convergências e custo das operações complicadas:
- Ordem de convergência do método de Newton:
(quadrático). - Ordem de convergência do método da secante:
(aproximação linear-superlinear).
Uma forma padrão de comparar eficiência quando um certo tipo de operação domina é usar o índice de eficiência
onde
é a ordem de convergência e
é o número de avaliações “caras” (aqui: operações complicadas) por iteração.
Calculemos:
- Newton:
(precisa de e por passo), então
- Secante:
(só por passo), então
Interpretação: quanto maior o índice, mais “eficiente” é o método por operação cara. Aqui a secante tem índice maior, isto é, por operação complicada gasta ela reduz o erro mais eficientemente que Newton.
Conclusão prática: assumindo que apenas as operações
e
dominam o tempo e que podemos reaproveitar valores como descrito, a secante fará menos operações caras por unidade de redução do erro e, portanto, será mais rápida para atingir a mesma precisão (na fase assintótica de convergência, quando as taxas de ordem valem).
Passo 5
Resumo dos custos por passo e da escolha:
- Newton:
operações complicadas por iteração ( e no mesmo ). - Secante:
operação complicada por iteração ( no novo ponto ), reaproveitando os já calculados.
Como
para os índices de eficiência, a secante é a opção mais rápida sob as hipóteses do enunciado (operações complicadas dominantes e possibilidade de reaproveitar valores).
Resposta
Newton:
operações complicadas por passo.
Secante: operação complicada por passo.
Método mais rápido (para mesma precisão, sob as hipóteses dadas): método da secante.
Secante:
Método mais rápido (para mesma precisão, sob as hipóteses dadas): método da secante.