Exercício 28 (Teórico) - Análise de custo-eficiência

Seja N_{f} o número de avaliações de f e N_{f^{\prime}} o de f^{\prime} por iteração de cada método. Considere que avaliar f^{\prime} tem custo \alpha vezes o de avaliar f(\alpha \geq 1).
(a) Preencha a tabela:
Método Ordem p N_{f} N_{f^{\prime}} Custo/iter. Dígitos/custo
Bisseção 1
Pos. Falsa \leq 2
Ponto Fixo 1
Newton 2
Secante \varphi
(b) Para \alpha=1 (avaliar f^{\prime} custa igual a f ), qual método oferece maior número de dígitos corretos por unidade de custo computacional?
(c) Para \alpha=5, a conclusão muda?

Passo 1

O enunciado dá as seguintes informações e pede três coisas:
  • Definições: N_{f} é o número de avaliações de f por iteração; N_{f'} é o número de avaliações de f' por iteração. Avaliar f' custa \alpha vezes avaliar f, com \alpha\ge 1.
  • Tarefa (a): preencher a tabela fornecida (colunas: Ordem p, N_{f}, N_{f'}, Custo/iter., Dígitos/custo).
  • Tarefa (b): para \alpha=1, dizer qual método oferece maior número de dígitos corretos por unidade de custo computacional.
  • Tarefa (c): repetir a comparação para \alpha=5.
Informações relevantes que vamos usar (não resolvo nada ainda):
  • O custo por iteração será medido como
\text{Custo/iter.} = N_{f} + \alpha\,N_{f'}.
  • Vamos adotar uma medida heurística e prática de eficiência: “Dígitos/custo” será tomada como
\frac{p}{\text{Custo/iter.}},
isto é, a ordem de convergência p dividida pelo custo por iteração. Vou justificar e explicar essa escolha no passo seguinte antes de aplicar aos métodos.

Passo 2

Por que escolhi a expressão \dfrac{p}{\text{Custo/iter.}} para “Dígitos/custo”?
  • A ordem p descreve a rapidez assintótica da convergência: se e_k é o erro na iteração k, para k grande vale aproximadamente
e_{k+1}\approx C\,e_k^{p},
com C constante. Em termos de dígitos corretos (ordem de grandeza em base 10), a redução do erro por iteração aumenta com p. Logo, quanto maior p, maior a “ganho de exatidão” por iteração.
  • Como queremos comparar métodos levando em conta custo computacional, é natural dividir esse ganho (proporcional a p, heurísticamente) pelo custo da iteração. Assim obtemos a razão
\text{Dígitos/custo} \;\approx\; \frac{p}{N_{f}+\alpha N_{f'}}.í
Observação importante: isto é uma medida heurística/assintótica (prática em comparação de métodos). Existem outras formas (índice de eficiência p^{1/\text{(avaliações)}}çõ, etc.), mas \dfrac{p}{\text{Custo}} é clara e suficiente para as comparações pedidas aqui. Vou usar essa medida para preencher a tabela e comparar os métodos.

Passo 3

Contagem de avaliações por iteração (explicando passo a passo para cada método):
  • Bisseção:
    • Em cada iteração calcula-se o ponto médio m=(a+b)/2 e precisa avaliar f(m) para decidir qual subintervalo mantém o sinal oposto. Não se calcula derivada.
    • Portanto N_{f}=1 e N_{f'}=0.
    • Ordem de convergência é p=1 (convergência linear).
  • Posição Falsa (regula falsi):
    • Semelhante à bisseção: em cada iteração avalia-se f no novo ponto de interseção da secante e não avalia-se derivada. Assim N_{f}=1 e N_{f'}=0.
    • Ordem prática: usualmente p=1 (linear). O enunciado anotou “ \le 2”; em prática e para comparação tomamos p=1 (casos superlineares são excepcionais). Vou usar p=1 para calcular Dígitos/custo.
  • Ponto Fixo:
    • Iteração x_{n+1}=g(x_n). Em cada passo calcula-se g(x_n) (que corresponde a uma avaliação de função, não de derivada de f). Assim N_{f}=1 (ou, de forma equivalente, 1 avaliação da função iterativa) e N_{f'}=0.
    • Ordem p=1 (convergência linear) quando a iteração é contraida.
  • Newton:
    • Iteração x_{n+1}=x_n - \dfrac{f(x_n)}{f'(x_n)}. Em cada iteração avalia-se f(x_n) e f'(x_n).
    • Portanto N_{f}=1 e N_{f'}=1.
    • Ordem p=2 (convergência quadrática) quando f'(r)\neq 0.
  • Secante:
    • Usa duas aproximações anteriores, e em cada passo avalia-se f no novo ponto apenas (as duas avaliações anteriores são reaproveitadas). Assim por iteração nova temos N_{f}=1 e N_{f'}=0.
    • Ordem de convergência p=\varphi (a razão áurea \varphi=\dfrac{1+\sqrt{5}}{2}\approx 1{,}618).

Passo 4

Calcular a coluna “Custo/iter.” e “Dígitos/custo” (usando a fórmula \text{Custo/iter.}=N_f+\alpha N_{f'} e \text{Dígitos/custo}=p/(\text{Custo/iter.})í):
  • Bisseção:
    • N_{f}=1,\\ N_{f'}=0.
    • \text{Custo/iter.}=1+\alpha\cdot 0=1.
    • \text{Dígitos/custo}=\dfrac{p}{1}=\dfrac{1}{1}=1.í
  • Posição Falsa:
    • N_{f}=1,\\ N_{f'}=0.
    • \text{Custo/iter.}=1.
    • \text{Dígitos/custo}=\dfrac{p}{1}=\dfrac{1}{1}=1í (usando p=1 na prática).
  • Ponto Fixo:
    • N_{f}=1,\\ N_{f'}=0.
    • \text{Custo/iter.}=1.
    • \text{Dígitos/custo}=\dfrac{1}{1}=1.í
  • Newton:
    • N_{f}=1,\\ N_{f'}=1.
    • \text{Custo/iter.}=1+\alpha.
    • \text{Dígitos/custo}=\dfrac{2}{1+\alpha}.í
  • Secante:
    • N_{f}=1,\\ N_{f'}=0.
    • \text{Custo/iter.}=1.
    • \text{Dígitos/custo}=\dfrac{\varphi}{1}=\varphií (onde \varphi=\dfrac{1+\sqrt{5}}{2}\approx 1{,}618).
Vou organizar esses resultados de forma direta (estes são os valores que completam a tabela pedida).

Passo 5

Comparação numérica para \alpha=1 (avaliar f' custa o mesmo que f):
  • Bisseção: Dígitos/custo =1.
  • Posição Falsa: Dígitos/custo =1.
  • Ponto Fixo: Dígitos/custo =1.
  • Newton: Dígitos/custo =\dfrac{2}{1+1}=\dfrac{2}{2}=1.
  • Secante: Dígitos/custo =\varphi\approx 1{,}618.
Conclusão para (b): com \alpha=1 o método Secante oferece o maior número de dígitos corretos por unidade de custo.

Passo 6

Comparação numérica para \alpha=5:
  • Bisseção / Posição Falsa / Ponto Fixo: continuam com Dígitos/custo =1.
  • Newton: Dígitos/custo =\dfrac{2}{1+5}=\dfrac{2}{6}=\dfrac{1}{3}\approx 0{,}333.
  • Secante: Dígitos/custo =\varphi\approx 1{,}618.
Conclusão para (c): com \alpha=5 a conclusão não muda — Secante ainda é a melhor segundo a métrica adotada. (Observação: Newton só superaria a Secante se \dfrac{2}{1+\alpha}>\varphi, isto é se \alpha<\dfrac{2}{\varphi}-1\approx 0{,}236, mas como \alpha\ge 1 isso não ocorre.)

Resposta

(a) Tabela preenchida (colunas: Método — Ordem p N_{f} N_{f'} — Custo/iter. — Dígitos/custo):
  • Bisseção — p=1 N_{f}=1 N_{f'}=0 \text{Custo/iter.}=1 \text{Dígitos/custo}=1í.
  • Posição Falsa — p=1 (prático) — N_{f}=1 N_{f'}=0 \text{Custo/iter.}=1 \text{Dígitos/custo}=1í.
  • Ponto Fixo — p=1 N_{f}=1 N_{f'}=0 \text{Custo/iter.}=1 \text{Dígitos/custo}=1í.
  • Newton — p=2 N_{f}=1 N_{f'}=1 \text{Custo/iter.}=1+\alpha \text{Dígitos/custo}=\dfrac{2}{1+\alpha}í.
  • Secante — p=\varphi N_{f}=1 N_{f'}=0 \text{Custo/iter.}=1 \text{Dígitos/custo}=\varphií.
(b) Para \alpha=1: Secante (maior Dígitos/custo \approx 1{,}618).
(c) Para \alpha=5: mesma conclusão — Secante (maior Dígitos/custo \approx 1{,}618).

Exercícios relacionados