Esquema de horner

El esquema de Horner (o regla de Horner , método de Horner, método de Ruffini-Horner ) es un algoritmo para calcular el valor de un polinomio , escrito como una suma de monomios (monomios), para un valor dado de una variable. El método de Horner le permite encontrar las raíces del polinomio [1] , así como calcular las derivadas del polinomio en un punto dado. El esquema de Horner también es un algoritmo simple para dividir un polinomio en un binomio de la forma . El método lleva el nombre de William George Horner , sin embargo, Paolo Ruffini estaba 15 años por delante de Horner, y los chinos conocían este método desde el siglo XIII. $xc$

Descripción del algoritmo

Dado un polinomio

P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n },\quad a_{i}\in \mathbb {R} .

Sea necesario calcular el valor de este polinomio para un valor fijo de . Representamos el polinomio de la siguiente forma: $x = x_0$ $P(x)$

P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots )).

Definamos la siguiente secuencia:

b_{n}=a_{n},

b_{n-1}=a_{n-1}+b_{n}x_{0},

…

b_{i}=a_{i}+b_{i+1}x_{0},

…

b_{0}=a_{0}+b_{1}x_{0}.

El valor deseado es . Demostremos que esto es así. $P(x_{0})$ $b_{0}$

Sustituya en la notación resultante y calcule el valor de la expresión, comenzando desde los corchetes internos. Para ello, sustituiremos las subexpresiones por : $P(x)$ $x = x_0$ $bi}$

{\begin{alineado}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}( a_{n-1}+a_{n}x_{0})\puntos))=\\&=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{alineado}}

Usando el esquema de Horner para dividir un polinomio por un binomio

Al dividir un polinomio entre , se obtiene un polinomio con resto (ver el teorema de Bézout ). $a_{0}x^{n}+a_{1}x^{{n-1}}+\cdots +a_{{n-1}}x+a_{n}$ $xc$ $b_{0}x^{{n-1}}+b_{1}x^{{n-2}}+\cdots +b_{{n-2}}x+b_{{n-1}}$ $b_n$

Además, los coeficientes del polinomio resultante satisfacen las relaciones recurrentes

b_{0}=a_{0},\quad b_{k}=a_{k}+cb_{k-1}.

De la misma manera, puedes determinar la multiplicidad de las raíces (usa el esquema de Horner para el nuevo polinomio). Además, el esquema se puede utilizar para encontrar los coeficientes en la expansión de un polinomio en potencias : $(xc)$

P(x)=b_{n}+b_{n-1}(xc)+b_{n-2}(xc)^{2}+\cdots +b_{0}(xc)^{n }.

El esquema de Horner se puede utilizar para encontrar derivadas de un polinomio:

P^{(k)}(c)=k!b_{nk}.

Ejemplos de uso

Calcular para usar la división sintética: $f(x)=2x^{3}-6x^{2}+2x-1$ ${\ estilo de visualización x = 3.}$

x ₀│ x ³ x ² x ¹ x ⁰ 3 │ 2 −6 2 −1 │ 6 0 6 " ── 2 0 2 5

Aquí, la primera línea contiene el valor y los coeficientes del polinomio. $x_{0}$

Los valores (por columnas) de la tercera fila corresponden a la suma de los valores de la primera y segunda fila ( ), y los valores de la segunda fila corresponden al producto de x y el valor en la tercera fila de la columna anterior ( ). $b_{n-1}=a_{n-1}+b_{n}x_{0}$ ${\ Displaystyle b_ {n} x_ {0}}$

Por ejemplo, si vemos eso , los valores en la tercera fila. Entonces, la división sintética se basa en el método de Horner. $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$

Dividir por : ${\ estilo de visualización x^{3}-6x^{2}+11x-6}$ ${\ estilo de visualización x-2}$

2 │ 1 -6 11 -6 │ 2 −8 6 " ── 1 −4 3 0

Nuevo polinomio . ${\ estilo de visualización x^{2}-4x+3}$

Sea y . Divide usando el método de Horner. $f_{1}(x)=4x^{4}-6x^{3}+3x-5$ ${\ Displaystyle f_ {2} (x) = 2x-1}$ $f_1(x)$ ${\ estilo de visualización f_ {2} \, (x)}$

2 │ 4 -6 0 3 │ -5 ────┼───────────────────────┼──────── 1 │ 2 −2 −1 │ 1 └──────────────────────────────── 2 −2 −1 1 │ −4

La tercera línea es la suma de las dos primeras dividida por dos. Cada valor de la segunda fila coincide con el valor de la tercera fila de la columna anterior. Respuesta de la división:

{\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x -una}}.

Además, utilizando el esquema de Horner, puede calcular el valor de un número en un cálculo posicional.

Notas

↑ Si un polinomio entero tiene raíces enteras, entonces se encontrarán entre los divisores del término libre. Kurosh A. G. § 57. Raíces racionales de polinomios enteros // Curso de Álgebra Superior . - La ciencia. - Moscú, 1968. Archivado el 18 de octubre de 2013 en Wayback Machine .

Véase también

Literatura

Levitin A. V. Capítulo 6. Método de transformación: esquema de Horner y exponenciación // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 284-291. — 576 pág. — ISBN 978-5-8459-0987-9
Volkov EA § 2. Cálculo de los valores de un polinomio. Esquema de Horner // Métodos numéricos. - Libro de texto. asignación para universidades. — 2ª ed., corregida. - M. : Nauka, 1987. - 248 p.
S. B. Gashkov. § 14. Esquema de Horner y traducción de un sistema posicional a otro // Sistemas numéricos y su aplicación . - M. : MTSNMO , 2004. - S. 37-39. - (Biblioteca "Educación Matemática"). — ISBN 5-94057-146-8 .

Enlaces

esquema de horner
El cálculo de polinomios multivariantes es una generalización del esquema de Horner para el caso de un polinomio en varias variables.
El método de Horner en un campo complejo