Esquema de Horner

Em análise numérica, o esquema de Horner (também conhecido como algoritmo de Horner, método de Horner, regra de Horner ou, ainda, multiplicação alinhada), em homenagem a William George Horner, é um algoritmo eficiente para a avaliação dos polinômios na forma monômial. O método de Horner descreve um processo manual, através da qual pode-se aproximar as raízes de uma equação polinomial. O esquema de Horner também pode ser visto como um algoritmo rápido para dividir um polinômio por um polinômio linear com a regra de Ruffini.

História

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, o conhecimento do método é muito mais antigo. Fontes históricas indicam que ele já era utilizado por:

Paolo Ruffini em 1809;
Isaac Newton em 1669; (mas referência precisa é necessária)
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;

Descriçã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 definir-se $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}

Eficiência

Avaliação utilizando o formulário monômio de um polinômio do grau n exige a maioria n adições e (n2 n) / 2 multiplicações, se as potências são calculadas pela multiplicação repetida e cada monômio é avaliado individualmente. (Isto pode ser reduzido para adições n e 2n - 1 multiplicações por avaliar as competências de x iterativamente.) Se os dados numéricos são representados em termos de dígitos (ou bits), então o algoritmo ingênuo implica também armazenar cerca de 2n vezes o número de bits de x (o polinómio avaliado tem xn magnitude aproximada, e é preciso também loja própria xn). Em contrapartida, o esquema de Horner requer apenas adições e multiplicações n n, e as suas necessidades de armazenamento são apenas n vezes o número de bits de x. Alternativamente, o esquema de Horner pode ser calculado com n fundido multiplicar-acrescenta. esquema de Horner também pode ser estendida para avaliar os derivativos k primeira do polinômio com adições e multiplicações kn. Tem sido demonstrado que o regime de Horner é o ideal, no sentido de que qualquer algoritmo de avaliação de um polinómio arbitrário deve usar pelo menos como muitas operações. Que o número de adições necessária é mínima foi demonstrado por Alexander Ostrowski, em 1954, que o número de multiplicações é mínima por Victor Pan, em 1966. Quando x é uma matriz, o esquema de Horner não é o ideal. Isso pressupõe que o polinômio é avaliado de forma monomial e sem pré-condicionamento da representação é permitido, o que faz sentido se o polinômio é avaliada apenas uma vez. No entanto, se o pré-condicionamento é permitido e do polinômio deve ser avaliada, muitas vezes, em seguida, os algoritmos mais rápidos possíveis. Elas envolvem uma transformação da representação de um polinômio. Em geral, um grau n polinomial pode ser avaliada usando apenas ${\scriptstyle {\left\lfloor n/2\right\rfloor 2}}$ multiplicações e n adições(vejaKnuth: The Art of Computer Programming, Vol.2).

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 dispositivo de Briot-Ruffini pois 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:

  │        Neste 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 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$

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₀. Nesse caso o polinômio é dividido sucessivamente por x₀ 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:

   │ x⁴  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óximas 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 grau do polinômio utilizado para encontrar as demais é reduzido.

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.

Leonardo Fernandes Guidi. Notas da disciplina cálculo numérico a. Porto Alegre, 2013. Disponível em: <http://chasqueweb.ufrgs.br/~leonardo.guidi/calculo numerico.pdf>. Acesso em: 20 maio 2013.