Exercício 24 - Avaliação por Horner
Avalie os polinômios abaixo em x_{0} 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 p^{\prime}\left(x_{0}\right) usando Horner duplo.
p(x)=x^{4}-3 x^{3}+2 x^{2}-x+5, \quad x_{0}=2

Passo 1

O enunciado pede:
  • Avaliar o polinômio p(x)=x^{4}-3x^{3}+2x^{2}-x+5 no ponto x_{0}=2 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 p^{\prime}(x_{0}) usando Horner duplo (ou seja, calcular ao mesmo tempo p(x_{0}) e p^{\prime}(x_{0}) 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):
    • a_{4}=1
    • a_{3}=-3
    • a_{2}=2
    • a_{1}=-1
    • a_{0}=5
  • Ponto de avaliação: x_{0}=2.

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):
p(x)=a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0} =(((a_{4}x+a_{3})x+a_{2})x+a_{1})x+a_{0}.
  • Para avaliar em x_{0} definimos recursivamente (a notação habitual):
b_{4}=a_{4}, \qquad b_{k}=a_{k}+x_{0}\,b_{k+1}\quad\text{para }k=3,2,1,0.
  • No final temos p(x_{0})=b_{0}.
  • Contagem de multiplicações (princípio): cada cálculo b_{k}=a_{k}+x_{0}b_{k+1} exige uma multiplicação x_{0}b_{k+1}. Para um polinômio de grau n (aqui n=4) são necessárias n multiplicações usando Horner para obter p(x_{0}). Ou seja, aqui Horner precisa de 4 multiplicações para avaliar p(2).
Horner duplo (para calcular também a derivada no mesmo passe):
  • Mantém além dos b_{k} uma segunda sequência c_{k} definida por
c_{4}=0, \qquad c_{k}=b_{k+1}+x_{0}\,c_{k+1}\quad\text{para }k=3,2,1,0.
  • No final p(x_{0})=b_{0} e p^{\prime}(x_{0})=c_{0}.
  • Em termos de custo, na forma simples cada iteração do Horner duplo faz duas multiplicações (uma para x_{0}b_{k+1} e outra para x_{0}c_{k+1}), então são aproximadamente 2n multiplicações (aqui 2\cdot 4=8), salvo otimizações para casos especiais.

Passo 3

Aplicando Horner ao nosso polinômio com x_{0}=2. Vou montar a tabela de recorrência mostrando os a_{k}, os b_{k} (e depois os c_{k} para o Horner duplo). Começamos com:
a_{4}=1,\\ a_{3}=-3,\\ a_{2}=2,\\ a_{1}=-1,\\ a_{0}=5,\quad x_{0}=2.
Cálculos do Horner (único Horner para p(2)):
b_{4}=a_{4}=1.
b_{3}=a_{3}+x_{0}b_{4}=-3+2\cdot 1=-3+2=-1.
b_{2}=a_{2}+x_{0}b_{3}=2+2\cdot(-1)=2-2=0.
b_{1}=a_{1}+x_{0}b_{2}=-1+2\cdot 0=-1.
b_{0}=a_{0}+x_{0}b_{1}=5+2\cdot(-1)=5-2=3.
Tabela de recorrência (resumida):
  • b_{4}=1
  • b_{3}=-1
  • b_{2}=0
  • b_{1}=-1
  • b_{0}=3
Portanto p(2)=b_{0}=3.
Contagem de multiplicações (Horner): para cada cálculo b_{k}=a_{k}+x_{0}b_{k+1} houve 1 multiplicação. Como fizemos isso para k=3,2,1,0 (4 iterações) o total de multiplicações é 4.

Passo 4

Avaliação direta (do jeito “normal” com potências) e contagem de multiplicações.
  • Método direto: calcule as potências de x_{0} e multiplique pelos coeficientes:
    • Calcular x_{0}^{2} = 2\cdot 2 — 1 multiplicação, dá 4.
    • Calcular x_{0}^{3} = x_{0}^{2}\cdot x_{0} = 4\cdot 2 — 1 multiplicação, dá 8.
    • Calcular x_{0}^{4} = x_{0}^{3}\cdot x_{0} = 8\cdot 2 — 1 multiplicação, dá 16.
    • Multiplicar cada potência pelo coeficiente:
      • 1\cdot x_{0}^{4}=1\cdot 16 — 1 multiplicação.
      • (-3)\cdot x_{0}^{3}= -3\cdot 8 — 1 multiplicação.
      • 2\cdot x_{0}^{2}=2\cdot 4 — 1 multiplicação.
      • (-1)\cdot x_{0}= -1\cdot 2 — 1 multiplicação.
    • O termo constante +5 não exige multiplicação.
  • Somando: multiplicações para potências = 3. Multiplicações para coeficientes = 4. Total de multiplicações diretas = 3+4=7.
Vamos verificar numericamente:
p(2)=1\cdot 16 + (-3)\cdot 8 + 2\cdot 4 + (-1)\cdot 2 + 5 = 16 -24 +8 -2 +5 = 3,
o que coincide com o resultado de Horner.
Comparação direta:
  • Avaliação direta: 7 multiplicações.
  • Horner simples: 4 multiplicações.
    Conclusão: Horner é mais econômico aqui (menos multiplicações) para avaliar p(2).

Passo 5

Agora Horner duplo para obter p(2) e p^{\prime}(2) no mesmo passe — montando as duas sequências b_{k} e c_{k}.
Recorrências:
b_{4}=a_{4}=1,\qquad c_{4}=0.
Para k=3,2,1,0 usamos
b_{k}=a_{k}+x_{0}b_{k+1},\qquad c_{k}=b_{k+1}+x_{0}c_{k+1}.
Cálculos (já tínhamos alguns b_{k}, vou recalculá-los com c_{k}):
b_{4}=1,\qquad c_{4}=0.
k=3:
b_{3}=-3+2\cdot b_{4}=-3+2\cdot 1=-1, \qquad c_{3}=b_{4}+2\cdot c_{4}=1+2\cdot 0=1.
k=2:
b_{2}=2+2\cdot b_{3}=2+2\cdot(-1)=0, \qquad c_{2}=b_{3}+2\cdot c_{3}=-1+2\cdot 1=1.
k=1:
b_{1}=-1+2\cdot b_{2}=-1+2\cdot 0=-1, \qquad c_{1}=b_{2}+2\cdot c_{2}=0+2\cdot 1=2.
k=0:
b_{0}=5+2\cdot b_{1}=5+2\cdot(-1)=3, \qquad c_{0}=b_{1}+2\cdot c_{1}=-1+2\cdot 2=3.
Resultado do Horner duplo:
  • p(2)=b_{0}=3.
  • p^{\prime}(2)=c_{0}=3.
Contagem de multiplicações (Horner duplo): em cada iteração k foram realizadas duas multiplicações (uma para x_{0}b_{k+1} e outra para x_{0}c_{k+1}), e há n iterações ( k=3,2,1,0 no nosso caso), portanto cerca de 2n=8 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á 8.)

Passo 6

Resumo comparativo e dica prática:
  • Para avaliar somente p(x_{0}) Horner é claramente mais eficiente que a avaliação direta em forma de potências: 4 multiplicações contra 7 no caso concreto.
  • Se for necessário obter simultaneamente p(x_{0}) e p^{\prime}(x_{0}), Horner duplo fornece ambos em um único passe por meio das sequências b_{k} e c_{k}; custo aproximado 2n multiplicações (aqui 8). Alternativa: avaliar p por Horner ( n multiplicações) e depois avaliar o polinômio derivado por Horner (mais n-1 multiplicações) resulta em 2n-1 multiplicações (aqui 7), ligeiramente menor que 2n — 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

p(2)=3
p^{\prime}(2)=3
Multiplicações (avaliação direta de p(2)): 7
Multiplicações (Horner para p(2)): 4
Multiplicações (Horner duplo para p(2) e p'(2)): 8

Exercícios relacionados