Esquema de Horner

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em análise numérica, o esquema de Horner (também conhecido como algoritmo de Horner, método 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.

Historia[editar | editar código-fonte]

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:

Descrição[editar | editar código-fonte]

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{align}
b_n & := a_n \\
b_{n-1} & := a_{n-1} + b_n x_0 \\
& {}\  \  \vdots \\
b_0 & := a_0 + b_1 x_0.
\end{align}

Então b_0 é o valor de P(x).


Assim, substituindo iterativamente b_i na expressão,


\begin{align}
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{align}

Por exemplo, para Q(x) um polinômio completo de quarto grau. Queremos encontrar seu valor para x_0 Temos:

Q(x) = a_0x^0 +a_1x^1+a_2x^2+a_3x^3+a_4x^4

Com b_n do tipo:


\begin{align}
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{align}

Substituindo:

Q(x_0) = a_0x_0^0 +a_1x_0^1+a_2x_0^2+a_3x_0^3+a_4x_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[editar | editar código-fonte]

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[editar | editar código-fonte]

Divisão de polinômios[editar | editar código-fonte]

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 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[editar | editar código-fonte]

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 x0. Nesse caso o polinômio é dividido sucessivamente por x0 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[editar | editar código-fonte]

É 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 X0 do polinômio.E então fazer:

 P(x)=a_nx^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-X0) 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-xn) 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: X0=11;X1=1;X2=1993.

Se tivermos a aproximação X0=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 X2=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.

Método de Horner e Newton

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[editar | editar código-fonte]

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%20numerico.pdf>. Acesso em: 20 maio 2013.