Esquema de Horner

O Método de Horner (também chamado de algoritmo de Horner ou esquema de Horner) é um algoritmo que permite:

• Calcular o quociente e o resto de uma divisão entre dois polinômios quaisquer;
• Calcular a série de Taylor de um polinômio em torno de um ponto;
• Deflação de um polinômio.

Historia

O algoritmo possui esse nome devido ao trabalho "A new method of solving numerical equations of all orders" do matemático inglês William George Horner publicado em 1819 na "Philosophical Transactions of the Royal Society". Porém, a utilização do método é muito mais antigas. Fontes históricas indicam que ele já era conhecido por:

• Paolo Ruffini em 1809;
• Isaac Newton em 1969;
• Zhu Shijie (matemático chinês) no século XIV;
• Qin Jiushao (matemático chinês) no século XIII;
• Sharaf al-Dīn al-Tūsī (matemático persa) no século XII;
• Jian Xian (matemático chinês) no século XI;

Demonstração

O método de Horner consiste em reescrever um polinômio de forma a obter uma aproximação para um certo ponto ($x_{0}$)

$p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},$ em que $a_{0},\ldots ,a_{n}$ são os coeficientes do polinômio e números reais.Podemos estar interessados em calcular seu valor para $x_{0}$.Primeiramente observe que ele pode ser escrito na forma de parênteses encaixados(ou concatenados):

$p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x)\cdots )).\,$

Segundo o método deve-se definir $b_{0}$ da seguinte forma:

${\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\&{}\ \ \vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}$

Então $b_{0}$ é o valor de $P(x)$.

Assim, substituindo iterativamente $b_{i}$ na expressão,

${\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+b_{n}x_{0})\cdots ))\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(b_{n-1})\dots ))\\&{}\ \ \vdots \\&=a_{0}+x_{0}(b_{1})\\&=b_{0}.\end{aligned}}$

Por exemplo, para $Q(x)$ um polinômio completo de quarto grau. Queremos encontrar seu valor para $x_{0}$ Temos:

$Q(x)=a_{0}x^{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}$

Com $b_{n}$ do tipo:

${\begin{aligned}b_{4}&=a_{4}\\b_{3}&=a_{3}+b_{4}x_{0}\\b_{2}&=a_{2}+b_{3}x_{0}\\b_{1}&=a_{1}+b_{2}x_{0}\\b_{0}&=a_{0}+b_{1}x_{0}\\\end{aligned}}$

Substituindo:

$Q(x_{0})=a_{0}x_{0}^{0}+a_{1}x_{0}^{1}+a_{2}x_{0}^{2}+a_{3}x_{0}^{3}+a_{4}x_{0}^{4}=$
$a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+x_{0}(a_{3}+x_{0}(a_{4})=$
$a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+x_{0}(a_{3}+x_{0}(b_{4})=$
$a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+x_{0}(b_{3})=$
$a_{0}+x_{0}(a_{1}+x_{0}(b_{2})=$
$a_{0}+x_{0}(b_{1})=$
$Q(x_{0})=b_{0}$

Aplicações

Divisão de polinômios

A utilização do Método de Horner para a divisão de polinômios é uma extensão do [[Algoritmo de Briot-Ruffini|dispositivo de Briot-Ruffini] pois ele permite efetuar a divisão de um polinômio P(x) de grau n por outro polinômio D(x) de grau i. Sendo n e i dois números inteiros quaisquer. Para aplicar o método é necessário construir uma tabela desse modo:

  │  Nesta espaço colocaremos os coeficientes do polinômio dividendo em ordem crescente.
──┼─────────────────── Na primeira coluna, que está separada das demais, colocamos os coeficientes
  │                          do polinômio divisor. Com o termo de maior grau no espaço superior e os 
  │                          demais no meio com os sinais trocados.
──┼───────────────────  
  │

Por exemplo, vamos calcular $12x^{5}-x^{4}+3x^{2}+5/3x^{3}+2x^{2}-1$ Inicialmente temos:

 3│ 12 -1 0 3 0 5        Note que os termos x³ e x¹ tem os coeficientes "0" que devem ser colocados
──┼───────────────────   na tabela.
-2│
 0│     
 1│     
──┼───────────────────
  │

Em seguida, conta-se quantos coeficientes ficaram na primeira coluna do meio, neste exemplo, três. Logo, o resto terá três coeficientes também. Para separar o resto do quociente usa-se uma linha vertical contando três posições a partir do último coeficiente do polinômio dividendo. O resultado fica assim:

 3│ 12 -1 0 │ 3 0 5             
──┼─────────┼─────────   Podemos então finalmente dar inicio ao método. Ele consiste em pegar os 
-2│         │            coeficientes do dividendo um a um e dividir pelo termo de maior grau do divisor  
 0│         │            (no caso o 3) e descê-lo até a última linha. Em seguida ele é multiplicado pelo 
 1│         │            segundo termo do divisor e colocado na segunda linha e terceira coluna.Repete-se
──┼─────────┼─────────   essa operação para o próximo divisor, dispondo os resultados na segunda linha.
  │         │

O mesmo processo passo-a-passo(clique para abrir)

O resultado obtido deve ser:

 3│ 12 -1 0 │ 3 0 5        
──┼─────────┼─────────   12/3=4
-2│    -8 0 │ 4          4*(-2)= -8         
 0│         │            4*0 = 0
 1│         │            4*1 = 4
──┼─────────┼─────────   
  │ 4       │

Em seguida soma-se todos os valores da terceira coluna e então divide-se pelo coeficiente do termo de maior grau (repetindo o processo). Isso é feito até que a última linha seja preenchida. Ao final teremos:

 3│ 12 -1 0 │ 3 0 5             
──┼─────────┼─────────   Agora a aplicação do método está quase terminada.O quociente tem os coeficientes
-2│    -8 0 │ 4          da última linha (4;-3;2)e os expoentes de cada termo crescem da direita para   
 0│       6 │ 0-3        a esquerda.
 1│         │-4 0 2      Assim: Quociente = 4x²-3x+2.
──┼─────────┼─────────   Para sabermos o resto somamos os valores da 5ª,6ª e 7ª colunas.  Obtendo: 
  │ 4  -3 2 │            Obtendo: (3;-3;7).Os expoentes são determinados do mesmo modo.
                         Logo: Resto = 3x²-3x+7

Expansão de Taylor

A maneira mais eficaz de calcular o valor de um polinômio $p(x)$ de grau $n$ em $x_{0}$ é utilizando o método de Horner. Ao reescrevê-lo na forma concatenada torna-se necessario utilizar apenas $n$ adições e $n$ multiplicações. Enquanto que utilizando o polinômio na sua forma canônica utiliza-se mais adições e multiplicações o que leva mais tempo para ser computado.

Por exemplo, considere o polinômio:

$p(x)=7x^{5}-4x^{4}-10x^{3}+20x^{2}-6x-5$ Para calcular seu valor em $x_{0}$ diretamente, utiliza-se a expressão:

$p(x_{0})=7*x_{0}*x_{0}*x_{0}*x_{0}*x_{0}-4*x_{0}*x_{0}*x_{0}*x_{0}-10*x_{0}*x_{0}*x_{0}+20*x_{0}*x_{0}-6*x_{0}-5$

Aplicação do Método de Horner no Scilab

Que envolve realizar 15 multiplicações e 5 somas.

Enquanto que utilizando o método de Horner temos a forma fatorada:

$p(x_{0})=-5+x_{0}(-6+x_{0}(20+x_{0}(-10+x_{0}(-4+x_{0}(7)))))$

Que para ser calculada envolve fazer apenas 5 multiplicações e 5 somas.

De fato, este é o método utilizado pelo software de computação numérica Scilab. Para utilizar esse algoritmo no programa usa-se o comando horner (P, x) onde P é uma matriz de polinômios ou de razões de polinômios e x é um número real ou uma matriz para o qual se deseja obter o valor de P.

Pode-se também calcular a expansão de Taylor em torno de um ponto x_0. Nesse caso o polinômio é dividido sucessivamente por x_0 utilizando o dispositivo de Briot-Rufini. Exemplo: Calcular a expansão de Taylor em torno de 3 para o polinômio x^4-4x^3+7x^2-5x-2. Temos:

   │ x4  x³    x²    x¹    x⁰
 3 │ 1   4    7     -5   −2         
   │     3   -3     12   21
   ┼────────────────────────
 3 │ 1  -1    4     7    19
   │     3    6    30   
   ┼──────────────────────── 
 3 │ 1   2   10    37
   │     3   15
   ┼──────────────────────── 
 3 │1    5   25
   │     3
   ┼──────────────────────── 
   │1    8

Logo a expansão de Taylor em torno de 3 é: $P(x)=(x-3)^{4}+8(x-3)^{3}+25(x-3)^{2}+37(x-3)x+19$

Note que através do Método de Horner encontrar a expansão da série é mais simples e rápido, além de não envolver o cálculo de derivada.

Deflação

É a operação de removermos um fator linear de um polinômio. Para realizarmos uma deflação precisamos saber o valor (ou uma aproximação) de uma raiz X₀ do polinômio.E então fazer:

$P(x)=a_{n}x^{n}+a_{n-1}x^{n+1}+a_{n-2}x^{m-2}+....P(x)=(x-X_{0})*Q(x)$

Sendo que Q(x) tem a propriedade que ao ser multiplicado por (X-X₀) resulta em P(x) e pode ser calculado usando o Método de Horner para divisão.E dizemos que Q(x) é o polinômio deflacionado. Podemos repetir o processo encontrando os zeros de Q(x), e dividindo-o por (x-x_n) até encontrar fatorar por completo P(x).

Esse método é interessante se estivermos considerando o caso de começarmos com uma aproximação de uma raiz e quisermos entender como os erros são propagados. Por exemplo, considere:

$R(x)=-21923+23927x-2005x^{2}+x^{3}$ Um polinômio com raízes: X₀=11;X₁=1;X₂=1993.

Se tivermos a aproximação X₀=1,1 e fizermos a deflação, encontramos:

$R(x)=(x-1,1)*(21722,71-2003,9x+x^{2})$

$R(x)=(x-1,1)*(x-1993,0005)*(x-10,899501)$

As raízes encontradas são boas aproximações para as raízes exatas, apesar do erro inicial.Porém se tomarmos a aproximação inicial como X₂=1993,1. Temos:

$R(x)=(x-1993,1)*(209,11-11,9x+x^{2})$ $R(x)=(x-1993,1)*(x-(5,95+13,179814i))*(x-(5,95+13,179814i))$

O que não é uma boa aproximação. Percebe-se que as raízes envolvem a unidade imaginária e não estão próximos de 1 e 11. Logo, nesse caso tivemos uma grande propagação de erros. Esse também é um método bastante ágil de encontrar raízes de um polinômio, pois a cada raiz descoberta, o polinômio necessário para encontrar as demais é reduzido.

[[Ficheiro:

Horner com Newton

|thumb|]]

Referências

Donald Knuth. The Art of Computer Programming, Volumen 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Páginas 486–488 en la sección 4.6.4.

William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. En Philosophical Transactions of the Royal Society of London, pp. 308–335, julio de 1819.