Exercício 24 - Avaliação por Horner
Avalie os polinômios abaixo em
usando o Algoritmo de Horner e compare com a avaliação direta (contando multiplicações).
Para cada caso, mostre a tabela de recorrência de Horner e calcule também
usando Horner duplo.
Passo 1
O enunciado pede:
- Avaliar o polinômio
no ponto usando o Algoritmo de Horner. - Comparar essa avaliação com a avaliação direta, contando o número de multiplicações em cada método.
- Mostrar a tabela de recorrência de Horner (os valores intermediários) usada na avaliação.
- Calcular
usando Horner duplo (ou seja, calcular ao mesmo tempo e por um procedimento análogo ao Horner).
Informações dadas (peguei-as do enunciado):
- Coeficientes do polinômio (do termo de maior grau ao termo constante):
-
- Ponto de avaliação:
.
Passo 2
O que é o Algoritmo de Horner e como ele funciona (aula curtinha, sem pânico).
- Horner reescreve o polinômio de forma aninhada (forma de Horner):
- Para avaliar em
definimos recursivamente (a notação habitual):
- No final temos
. - Contagem de multiplicações (princípio): cada cálculo
exige uma multiplicação . Para um polinômio de grau (aqui ) são necessárias multiplicações usando Horner para obter . Ou seja, aqui Horner precisa de multiplicações para avaliar .
Horner duplo (para calcular também a derivada no mesmo passe):
- Mantém além dos
uma segunda sequência definida por
- No final
e . - Em termos de custo, na forma simples cada iteração do Horner duplo faz duas multiplicações (uma para
e outra para ), então são aproximadamente multiplicações (aqui ), salvo otimizações para casos especiais.
Passo 3
Aplicando Horner ao nosso polinômio com
. Vou montar a tabela de recorrência mostrando os
, os
(e depois os
para o Horner duplo). Começamos com:
Cálculos do Horner (único Horner para
):
Tabela de recorrência (resumida):
Portanto
.
Contagem de multiplicações (Horner): para cada cálculo
houve 1 multiplicação. Como fizemos isso para
(4 iterações) o total de multiplicações é
.
Passo 4
Avaliação direta (do jeito “normal” com potências) e contagem de multiplicações.
- Método direto: calcule as potências de
e multiplique pelos coeficientes: - Calcular
— 1 multiplicação, dá . - Calcular
— 1 multiplicação, dá . - Calcular
— 1 multiplicação, dá . - Multiplicar cada potência pelo coeficiente:
-
— 1 multiplicação. -
— 1 multiplicação. -
— 1 multiplicação. -
— 1 multiplicação.
-
- O termo constante
não exige multiplicação.
- Calcular
- Somando: multiplicações para potências =
. Multiplicações para coeficientes = . Total de multiplicações diretas = .
Vamos verificar numericamente:
o que coincide com o resultado de Horner.
Comparação direta:
- Avaliação direta:
multiplicações. - Horner simples:
multiplicações.
Conclusão: Horner é mais econômico aqui (menos multiplicações) para avaliar.
Passo 5
Agora Horner duplo para obter
e
no mesmo passe — montando as duas sequências
e
.
Recorrências:
Para
usamos
Cálculos (já tínhamos alguns
, vou recalculá-los com
):
k=3:
k=2:
k=1:
k=0:
Resultado do Horner duplo:
-
. -
.
Contagem de multiplicações (Horner duplo): em cada iteração
foram realizadas duas multiplicações (uma para
e outra para
), e há
iterações (
no nosso caso), portanto cerca de
multiplicações. (Observação: em implementação prática pode haver micro-otimizações quando alguns termos são zero, mas a conta padrão dá
.)
Passo 6
Resumo comparativo e dica prática:
- Para avaliar somente
Horner é claramente mais eficiente que a avaliação direta em forma de potências: multiplicações contra no caso concreto. - Se for necessário obter simultaneamente
e , Horner duplo fornece ambos em um único passe por meio das sequências e ; custo aproximado multiplicações (aqui ). Alternativa: avaliar por Horner ( multiplicações) e depois avaliar o polinômio derivado por Horner (mais multiplicações) resulta em multiplicações (aqui ), ligeiramente menor que — mas Horner duplo tem a vantagem de ser conceitualmente direto e numericamente estável para computação em uma única passagem.
Força aí! Você já consegue montar a tabela e aplicar o Horner na prova rapidinho.
Resposta
Multiplicações (avaliação direta de
Multiplicações (Horner para
Multiplicações (Horner duplo para