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 dá o polinômio e o ponto onde devo avaliá‑lo:
O que preciso entregar:
- Avaliar
usando o Algoritmo de Horner, mostrando a tabela de recorrência (passo a passo). - Comparar a avaliação por Horner com a avaliação direta, contando multiplicações.
- Calcular
usando Horner duplo (mostrar a recorrência e o valor).
Passo 2
Explicando o Algoritmo de Horner (de forma bem direta e prática).
- Escreve-se o polinómio pelos coeficientes de grau maior para o termo constante. Aqui os coeficientes são (do grau 5 ao 0):
- A recorrência de Horner para avaliar
é: No final . - Contagem de multiplicações em Horner: cada passo
requer uma multiplicação . Para grau há exatamente multiplicações. Aqui, grau multiplicações.
Passo 3
Tabela de recorrência de Horner (computando cada
com
). Vou mostrar cada linha com o cálculo explícito.
Portanto, pela recorrência de Horner:
Passo 4
Comparação com a avaliação direta (contando multiplicações) — explico o método direto que normalmente se usa sem Horner:
- Para avaliar diretamente calcula‑se potências de
sequencialmente e multiplica‑se por cada coeficiente: - Computar
dá multiplicações (cada potência usa uma multiplicação com ). - Multiplicar cada potência pelo respectivo coeficiente para os termos de graus
dá mais multiplicações (o termo constante não requer multiplicação).
- Computar
- Total de multiplicações no método direto:
.
Confirmando a avaliação direta numericamente (só para conferir):
que bate com Horner.
Resumo das contagens (avaliação de
):
- Avaliação direta (método descrito):
multiplicações. - Horner:
multiplicações.
Horner é mais eficiente em multiplicações (a cada redução do grau sobra uma multiplicação a menos).
Passo 5
Horner duplo para calcular
— explicação e recorrência:
- Depois de calcular os
(como acima), faz‑se uma segunda recorrência para obter o valor da derivada no ponto. - Define‑se
No final . - A intuição: os
representam os coeficientes intermediários da fatoração por Horner; a segunda recorrência acumula os coeficientes multiplicados pelos expoentes (maneira compacta de obter a derivada avaliada).
Agora calculo explicitamente (usando os
já obtidos:
):
Logo,
Passo 6
Contagem de multiplicações para obter
com Horner duplo:
- A primeira passagem (para obter
) usou multiplicações. - A segunda passagem (para os
) tem também uma multiplicação por passo (o termo ) e são passos (de até ), logo mais multiplicações. - Total para obter simultaneamente
e via Horner duplo: multiplicações.
Para referência: avaliar diretamente a derivada (polinômio de grau
) sem Horner requer, pelo método direto análogo,
multiplicações para as potências
e
multiplicações para multiplicar pelos coeficientes dos termos de grau
a
, total
multiplicações — mas isso é só comparação adicional; o enunciado pedia o cálculo via Horner duplo, que já foi feito.
Resposta
Avaliação direta:
Avaliação por Horner: