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 dispositivo de Briot-Ruffini(conhecido popularmente por "regra do # 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.

Aplicação do Método de Horner

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.

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

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.