Exercício 28 (Teórico) - Análise de custo-eficiência
Seja
o número de avaliações de
e
o de
por iteração de cada método. Considere que avaliar
tem custo
vezes o de avaliar
.
(a) Preencha a tabela:
Método
Ordem
Custo/iter.
Dígitos/custo
Bisseção
1
Pos. Falsa
Ponto Fixo
1
Newton
2
Secante
(b) Para
(avaliar
custa igual a
), qual método oferece maior número de dígitos corretos por unidade de custo computacional?
(c) Para
, a conclusão muda?
(a) Preencha a tabela:
| Método | Ordem
|
|
|
Custo/iter. | Dígitos/custo |
| Bisseção | 1 | ||||
| Pos. Falsa |
|
||||
| Ponto Fixo | 1 | ||||
| Newton | 2 | ||||
| Secante |
|
(c) Para
Passo 1
O enunciado dá as seguintes informações e pede três coisas:
- Definições:
é o número de avaliações de por iteração; é o número de avaliações de por iteração. Avaliar custa vezes avaliar , com . - Tarefa (a): preencher a tabela fornecida (colunas: Ordem
, , , Custo/iter., Dígitos/custo). - Tarefa (b): para
, dizer qual método oferece maior número de dígitos corretos por unidade de custo computacional. - Tarefa (c): repetir a comparação para
.
Informações relevantes que vamos usar (não resolvo nada ainda):
- O custo por iteração será medido como
- Vamos adotar uma medida heurística e prática de eficiência: “Dígitos/custo” será tomada como
isto é, a ordem de convergência
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
para “Dígitos/custo”?
- A ordem
descreve a rapidez assintótica da convergência: se é o erro na iteração , para grande vale aproximadamente
com
constante. Em termos de dígitos corretos (ordem de grandeza em base 10), a redução do erro por iteração aumenta com
. Logo, quanto maior
, 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
, heurísticamente) pelo custo da iteração. Assim obtemos a razão
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
, etc.), mas
é 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
e precisa avaliar para decidir qual subintervalo mantém o sinal oposto. Não se calcula derivada. - Portanto
e . - Ordem de convergência é
(convergência linear).
- Em cada iteração calcula-se o ponto médio
-
Posição Falsa (regula falsi):
- Semelhante à bisseção: em cada iteração avalia-se
no novo ponto de interseção da secante e não avalia-se derivada. Assim e . - Ordem prática: usualmente
(linear). O enunciado anotou “ ”; em prática e para comparação tomamos (casos superlineares são excepcionais). Vou usar para calcular Dígitos/custo.
- Semelhante à bisseção: em cada iteração avalia-se
-
Ponto Fixo:
- Iteração
. Em cada passo calcula-se (que corresponde a uma avaliação de função, não de derivada de ). Assim (ou, de forma equivalente, 1 avaliação da função iterativa) e . - Ordem
(convergência linear) quando a iteração é contraida.
- Iteração
-
Newton:
- Iteração
. Em cada iteração avalia-se e . - Portanto
e . - Ordem
(convergência quadrática) quando .
- Iteração
-
Secante:
- Usa duas aproximações anteriores, e em cada passo avalia-se
no novo ponto apenas (as duas avaliações anteriores são reaproveitadas). Assim por iteração nova temos e . - Ordem de convergência
(a razão áurea ).
- Usa duas aproximações anteriores, e em cada passo avalia-se
Passo 4
Calcular a coluna “Custo/iter.” e “Dígitos/custo” (usando a fórmula
e
):
-
Bisseção:
-
. -
-
-
-
Posição Falsa:
-
. -
-
(usando na prática).
-
-
Ponto Fixo:
-
. -
-
-
-
Newton:
-
. -
-
-
-
Secante:
-
. -
-
(onde ).
-
Vou organizar esses resultados de forma direta (estes são os valores que completam a tabela pedida).
Passo 5
Comparação numérica para
(avaliar
custa o mesmo que
):
- Bisseção: Dígitos/custo
. - Posição Falsa: Dígitos/custo
. - Ponto Fixo: Dígitos/custo
. - Newton: Dígitos/custo
. - Secante: Dígitos/custo
.
Conclusão para (b): com
o método Secante oferece o maior número de dígitos corretos por unidade de custo.
Passo 6
Comparação numérica para
:
- Bisseção / Posição Falsa / Ponto Fixo: continuam com Dígitos/custo
. - Newton: Dígitos/custo
- Secante: Dígitos/custo
Conclusão para (c): com
a conclusão não muda — Secante ainda é a melhor segundo a métrica adotada. (Observação: Newton só superaria a Secante se
, isto é se
, mas como
isso não ocorre.)
Resposta
(a) Tabela preenchida (colunas: Método — Ordem
—
—
— Custo/iter. — Dígitos/custo):
- Bisseção —
— — — — . - Posição Falsa —
(prático) — — — — . - Ponto Fixo —
— — — — . - Newton —
— — — — . - Secante —
— — — — .
(b) Para
: Secante (maior Dígitos/custo
).
(c) Para
: mesma conclusão — Secante (maior Dígitos/custo
).