Esquema de Horner

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

Descrição do Algoritmo

Dado o polinómio

$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 números reais, nós queremos estimar o polinómio em um específico valor de x, digamos x₀.

Para conseguir isso, vamos definir uma nova seqüência de constantes 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₀ é o valor de p(x₀).

Para ver por que isso funciona, observe que o polinómio pode ser escrito na forma

$p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)). \,$

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}$

Aplicação

O esquema de Horner é muitas vezes usado para converter entre diferentes sistemas numerais posicionais - caso em que x é a base do sistema de números, e os coeficientes a_i são os dígitos da base de representação x de um dado número - e também pode ser usado se x é uma matriz, caso em que o ganho de eficiência computacional é ainda maior.

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 [3]. 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).

História

Mesmo que o algoritmo é nomeado após William George Horner, que a descreveu em 1819, o método já era conhecido por Isaac Newton em 1669, o matemático chinês Qin Jiushao em seu Treatise Matemática, com nove seções, escrito no século XIII, e até mesmo antes do matemático persa Sharaf al-Din al-Tusi no século XII. A primeira utilização do regime de Horner foi no livro Arte Matemática, um trabalho chinês da dinastia Han (202 aC - 220 dC), editado por Liu Hui (século III).

Referências

• 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.
• 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.