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)
(c)
(c)
Passo 1
O que o enunciado pede e os dados que temos:
- Precisamos comparar, para a equação
quantas operações “complicadas” (aqui só aparece ) são necessárias: - para um passo do método de Newton;
- para um passo do método da secante.
- Devemos considerar reaproveitamento de valores para reduzir o número de
. - Assumindo que
é a parte dominante do custo e que cada leva o mesmo tempo, decidir qual método (Newton ou secante) seria mais rápido para obter a mesma precisão. - Informação dada explicitamente: a função é
Passo 2
Relembrando o método de Newton (fórmula do passo) e o que é necessário calcular:
- Fórmula do passo de Newton:
- Para a nossa função, a derivada é
- Para executar um passo precisamos avaliar
e .
Agora vamos ver quais são as operações
necessárias para essas avaliações e como podemos reaproveitar valores:
- Para calcular
precisamos de e . - Observação importante (reuso): se calcularmos
uma vez com a operação , podemos obter por multiplicação: . Multiplicação é uma operação barata comparada com . - Para calcular
também precisamos exatamente dos mesmos termos e . - Conclusão concreta: calculando
uma única vez por iteração, eu tenho todos os termos exponenciais necessários tanto para quanto para .
Contagem de
por passo de Newton:
- Número de
por passo: (uma para obter ; obtido por quadrado).
Passo 3
Relembrando o método da secante (fórmula do passo) e o que é necessário calcular:
- Fórmula do passo da secante (usando
e ): - Para computar o numerador e denominador precisamos de
e . - Implementação típica: guardamos
já calculado da iteração anterior, então, a cada nova iteração só precisamos avaliar no ponto novo (exceto na inicialização, onde avaliamos em dois pontos iniciais e ).
Agora, para a nossa função
:
- Cada avaliação de
em um ponto requer e . - Como antes, podemos calcular
uma vez e obter . - Assim, cada avaliação de
em um ponto novo custa operação .
Contagem de
por passo da secante:
- Para uma iteração típica (após ter
armazenado): precisamos de (para avaliar ). - Inicialmente, para começar o método, precisamos avaliar
em dois pontos e : isso custa na fase de inicialização (mas esse custo é amortizado ao longo das iterações seguintes).
Passo 4
Resumo prático dos custos por iteração (considerando reaproveitamento):
- Newton:
por iteração (cada iteração calcula e obtém por quadrado; usa-os para e ). - Secante:
por iteração típica depois da inicialização; na inicialização precisa de para obter e . - Conclusão até aqui: em custo por iteração puro (ignorando inicialização), ambos custam aproximadamente a mesma quantidade de
por passo: .
Passo 5
Agora comparar eficiência final levando em conta a taxa de convergência (quantas iterações cada método precisa para alcançar a mesma precisão):
- Ordem de convergência:
- Newton tem ordem
(convergência quadrática): o erro se reduz aproximadamente como . - Secante tem ordem
(convergência superlinear, mas mais lenta que quadrática): o erro se reduz aproximadamente como .
- Newton tem ordem
- Consequência prática: para chegar a uma precisão muito pequena, Newton costuma precisar de muito menos iterações do que a secante.
Exemplo numérico ilustrativo (para entendimento concreto):
- Suponha erro inicial da iteração relevante seja
e que queremos atingir . - Newton (aproximação grosseira): depois de uma iteração
; depois ; depois . São iterações. - Secante (usar propriedades logarítmicas): o expoente do log diminui multiplicando por
a cada iteração. Para ir de (log10 do erro) a precisamos de tal que , o que dá , então iterações. - Contagem aproximada de
total no exemplo: - Newton:
iterações × /iteração = . - Secante: inicial
+ (sucessivas) iterações adicionais × = .
- Newton:
- Mesmo que o exemplo numérico seja aproximado, ele ilustra o ponto: Newton precisa de menos iterações e portanto de menos
no total.
Passo 6
Conclusão final e observações práticas:
- Como tanto Newton quanto secante podem ser implementados de modo a usar apenas
por iteração (reutilizando para obter ), o custo por iteração em termos de operações “complicadas” é essencialmente o mesmo. - Porque Newton converge quadraticamente e a secante converge mais lentamente (ordem
), Newton precisa de significativamente menos iterações para atingir a mesma precisão. - Logo, contabilizando o número total de
necessárias até atingir a precisão desejada, o método de Newton será mais rápido (exigirá menos no total) para esta função específica.
Resposta
Newton — mais rápido. Newton:
por iteração; Secante:
por iteração típica (mais
na inicialização); Newton precisa de menos iterações devido à convergência quadrática.