Esquema de Horner: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
ajustes |
|||
Linha 1:
O '''Método de Horner''' (também chamado de algoritmo de Horner, esquema de Horner ou multiplicação alinhada) é um importante e prático [[algoritmo]] que permite:▼
▲O Método de Horner (também chamado de algoritmo de Horner,esquema de Horner ou multiplicação alinhada) é um importante e prático [[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;
Linha 8 ⟶ 6:
== 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, o conhecimento do método é muito mais antigo. Fontes históricas indicam que ele já era utilizado por:
* [[Paolo Ruffini]] em 1809;
Linha 18 ⟶ 15:
== Demonstração ==
O método de Horner consiste em reescrever um polinômio de forma a obter uma aproximação para um certo ponto (<math>x_0</math>)
:<math>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,</math>▼
▲<math>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,</math>
em que <math>a_0, \ldots, a_n</math> são os coeficientes do polinômio e números reais.Podemos estar interessados em calcular seu valor para <math>x_0</math>.Primeiramente observe que ele pode ser escrito na forma de parênteses encaixados(ou concatenados):
:<math>p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)). \, </math>▼
▲<math>p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)). \, </math>
Segundo o método deve-se definir <math>b_0</math> da seguinte forma:
:<math>▼
▲<math>
\begin{align}
b_n & := a_n \\
Linha 50 ⟶ 43:
\end{align}
</math>
Por exemplo, para <math>Q(x)</math> um polinômio completo de quarto grau. Queremos encontrar seu valor para <math>x_0</math> Temos:
:<math>Q(x) = a_0x^0 +a_1x^1+a_2x^2+a_3x^3+a_4x^4</math>▼
▲<math>Q(x) = a_0x^0 +a_1x^1+a_2x^2+a_3x^3+a_4x^4</math>
Com <math>b_n</math> do tipo:
: <math>
\begin{align}
Linha 70 ⟶ 59:
Substituindo:
:<math>Q(x_0) = a_0x_0^0 +a_1x_0^1+a_2x_0^2+a_3x_0^3+a_4x_0^4 =</math
:<math>a_0 + x_0(a_1 + x_0(a_2 + x_0(a_3 + x_0(a_4)= </math
:<math>a_0 + x_0(a_1 + x_0(a_2 + x_0(a_3 + x_0(b_4)= </math
:<math>a_0 + x_0(a_1 + x_0(a_2 + x_0(b_3)= </math
:<math>a_0 + x_0(a_1 + x_0(b_2)= </math
:<math>a_0 + x_0(b_1)= </math
:<math>Q(x_0) = b_0 </math
== 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 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:
Linha 133 ⟶ 121:
=== Expansão de [[Série de Taylor|Taylor]] ===
A maneira mais eficaz de calcular o valor de um polinômio <math>p(x)</math> de grau <math>n</math> em <math>x_0</math> é utilizando o método de Horner. Ao reescrevê-lo na forma concatenada torna-se necessario utilizar apenas <math>n</math> adições e <math>n</math> 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.
| |||