Algoritmo de HornerEn el campo matemático del análisis numérico, el Algoritmo de Horner, llamado así por William George Horner, es un algoritmo para evaluar de forma eficiente funciones polinómicas de una forma monomial.

Dado el polinomio

p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,donde a_0, \ldots, a_n son números reales, queremos evaluar el polinomio a un valor específico de x\,\!, digamos x_0\,\!.

Para llevar a cabo el procedimiento, definimos una nueva secuencia de constantes como se muestra a continuación:

b_n\,\! :=\,\! a_n\,\!b_{n-1}\,\! :=\,\! a_{n-1} + b_n x_0\,\!\vdotsb_0\,\! :=\,\! a_0 + b_1 x_0\,\!Entonces b_0\,\! es el valor de p(x_0)\,\!.

Para ver como funciona esto, nótese que el polinomio puede escribirse de la forma

p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x) \cdots ))Después, sustituyendo iterativamente la b_i en la expresión,

p(x_0)\,\! =\,\! a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(a_{n-1} + b_n x_0) \dots ))=\,\! 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\,\!Índice [ocultar] 1 Aplicación2 Eficiencia3 Historia4 Véase también5 ReferenciasAplicación[editar]El algoritmo de Horner se usa a menudo para convertir entre distintos sistemas numéricos posicionales — en cuyo caso x es la base del sistema numérico, y los coeficientes ai son los dígitos de la representación del número dado en la base x — y puede usarse también si x es una matriz, en cuyo caso la carga computacional se reduce aún más.

Eficiencia[editar]

La evaluación usando la forma monomial del polinomio de grado-n requiere al menos n sumas y (n2+n)/2 multiplicaciones, si las potencias se calculan mediante la repetición de multiplicaciones. El algoritmo de Horner sólo requiere n sumas y n multiplicaciones. (Minimizar el número de multiplicaciones es lo más deseable porque necesitan mucha carga computacional y son inestables comparadas con la suma).

Se han demostrado que el algoritmo de Horner es óptimo, de modo que cualquier algoritmo que se use para evaluar un polinomio requerirá como mínimo el mismo número de operaciones. El hecho de que el número de operaciones requeridas es mínimo fue demostrado por Alexander Ostrowski en 1954, y que el número de multiplicaciones es mínimo por Victor Pan en 1966. Cuando x es una matriz, el algoritmo de Horner no es óptimo.

Historia[editar]Aunque el método toma el nombre de William George Horner, quien lo describió en 1819, el método era ya conocido por Isaac Newton en 1669, e incluso antes por el matemático chino Ch'in Chiu-Shao en el siglo XIII.En matemáticas, un polinomio (del latín polynomius, y este del griego, πολυς [polys] ‘muchos’ y νόμος [nómos] ‘regla’, ‘prescripción’, ‘distribución’)1 2 3 es una expresión matemática constituida por un conjunto finito de variables (no determinadas o desconocidas) y constantes (números fijos llamados coeficientes), utilizando únicamente las operaciones aritméticas de suma, resta y multiplicación, así como también exponentes enteros positivos. En términos más precisos, es una relación n-aria de monomios, o una sucesión de sumas y restas de potencias enteras de una o de varias variables indeterminadas.

Es frecuente el término polinómico (ocasionalmente también el anglicismo polinomial), como adjetivo, para designar cantidades que se pueden expresar como polinomios de algún parámetro, como por ejemplo: tiempo polinómico, etc.

Los polinomios son objetos muy utilizados en matemáticas y en ciencia. En la práctica, son utilizados en cálculo y análisis matemático para aproximar cualquier función derivable; las ecuaciones polinómicas y las funciones polinómicas tienen aplicaciones en una gran variedad de problemas, desde la matemática elemental y el álgebra hasta áreas como la física, química, economía y las ciencias sociales.

En álgebra abstracta, los polinomios son utilizados para construir los anillos de polinomios, un concepto central en teoría de números algebraicos y geometría algebraica.

Índice [ocultar] 1 Definición algebraica1.1 Polinomios de una variable1.2 Polinomios de varias variables1.3 Grado de un polinomio2 Operaciones con polinomios3 Funciones polinómicas

3.1 Ejemplos de funciones polinómicas4 Factorización de polinomios5 Historia6 Véase también7 Referencias8 Enlaces externosDefinición algebraica[editar]Los polinomios están constituidos por un conjunto finito de variables (no determinadas o desconocidas) y constantes (llamadas coeficientes), con las operaciones aritméticas de suma, resta y multiplicación, así como también exponentes enteros positivos. Pueden ser de una o de varias variables.

Polinomios de una variable[editar]Para a0, …, an constantes en algún anillo A (en particular podemos tomar un cuerpo, como \scriptstyle\mathbb{R} o \scriptstyle\mathbb{C}, en cuyo caso los coeficientes del polinomio serán números) con an distinto de cero y n \in \mathbb{N}, entonces un polinomio, P_{}^{}, de grado n en la variable x es un objeto de la forma

P(x)_{}^{} = a_n x^n + a_{n-1} x^{n - 1}+ \cdots + a_1 x^{1} + a_0 x^{0}.

Un polinomio P(x) \in K[x] no es más que una sucesión matemática finita \left\{{a_n}\right\}_n tal que a_n \in K.

Representado como:

P(x)_{}^{}=a_0+a_1x+a_2x^2+...+a_nx^n

el polinomio se puede escribir más concisamente usando sumatorios como:

P(x) = \sum_{i = 0}^{n} a_{i} x^{i}.

Las constantes a0, …, an se llaman los coeficientes del polinomio. A a0 se le llama el coeficiente constante (o término independiente) y a an, el coeficiente principal. Cuando el coeficiente principal es 1, al polinomio se le llama mónico o normalizado.

Polinomios de varias variables[editar]Como ejemplo, de polinomios de dos variables desarrollando los binomios:

(2)\begin{cases}(x + y)^2 = x^2 + 2xy + y^2\\(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\\(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4 \end{cases}

Estos polinomios son mónicos, homogéneos, simétricos y sus coeficientes son coeficientes binomiales.

Para obtener la expansión de las potencias de una resta (véase productos notables), basta con tomar -y en lugar de y en el caso anterior. La expresión (2) queda de la siguiente forma:

(x-y)^2=x^{2}-2xy+y^{2}\,Los polinomios de varias variables, a diferencia de los de una variable, tienen en total más de una variable. Por ejemplo los monomios:

5xy, 3xz^2, 4xy^2z, \dotsEn detalle el último de ellos 4xy_{}^2z es un monomio de tres variables (ya que en él aparecen las tres letras x, y y z), el coeficiente es 4, y los exponentes son 1, 2 y 1 de x, y y z respectivamente.

Grado de un polinomio[editar]Artículo principal: Grado (polinomio)Se define el grado de un monomio como el mayor exponente de su variable. El grado de un polinomio es el del monomio de mayor grado.

EjemplosP(x) = 2, polinomio de grado cero (el polinomio solo consta del término independiente).P(x) = 3x + 2, polinomio de grado uno.P(x) = 3x² + 2x, polinomio de grado dos.P(x) = 2x3+ 3x + 2, polinomio de grado tres.Convencionalmente se define el grado del polinomio nulo como \scriptstyle -\infty. En particular los números son polinomios de grado cero.

Operaciones con polinomios[editar]Artículo principal: Operaciones con polinomiosLos polinomios se pueden sumar y restar agrupando los términos y simplificando los monomios semejantes. Para multiplicar polinomios se multiplica cada término de un polinomio por cada uno de los términos del otro polinomio y luego se simplifican los monomios semejantes.

EjemploSean los polinomios: P(x) = (2x_{}^3+4x+1) y Q(x)_{}^{} = (5x^2+3) , entonces el producto es:

P(x)Q(x)_{}^{} = (2x_{}^3+4x+1)(5x^2+3) = (2x_{}^3+4x+1)(5x^2) + (2x^3+4x+1)(3)= (10x_{}^5 + 20x^3 + 5x^2) + (6x^3+12x+3)= 10x_{}^5 + 26x^3 + 5x^2 + 12x + 3Para poder realizar eficazmente la operación se tiene que adquirir los datos necesarios de mayor a menor. Una fórmula analítica que expresa el producto de dos polinomios es la siguiente:

P(X)Q(X)_{}^{} = \left( \sum_{i=0}^m a_i X^i \right)\left(\sum_{j=0}^n b_j X^j \right) = \sum_{k=0}^{m+n} \left(\sum_{p=0}^k a_p b_{k-p} \right) X^k

Aplicando esta fórmula al ejemplo anterior se tiene:

P(x)Q(x)_{}^{} = (2x_{}^3+4x+1)(5x^2+3) = (1\cdot 3)x_{}^0 + (4 \cdot 3)x^1 + (1 \cdot 5)x^2 + (4\cdot 5+ 2\cdot 3)x^3 + (0)x^4 + (5\cdot 2)x^5 = 10x_{}^5 + 26x^3 + 5x^2 + 12x + 3

Puede comprobarse que para polinomios no nulos se satisface la siguiente relación entre el grado de los polinomios \scriptstyle P(X) y \scriptstyle Q(X) y el polinomio producto \scriptstyle P(X)Q(X):

(*)\mbox{gr}(P(X)Q(X)) = \mbox{gr}(P(X)) + \mbox{gr}(Q(X))\,

Puesto que el producto de cualquier polinomio por el polinomio nulo es el propio polinomio nulo, se define convencionalmente que \scriptstyle \mbox{gr}(0) = -\infty (junto con la operación \forall p: -\infty + p = -\infty) por lo que la expresión (*) puede extenderse también al caso de que alguno de los polinomios sea nulo.

Funciones polinómicas[editar]Artículo principal: Función polinómicaUna función polinómica es una función matemática expresada mediante un polinomio. Dado un polinomio P[x] se puede definir una función polinómica asociada al polinomio dado substituyendo la variable x por un elemento del anillo:

f_P:A \to A,\qquad \qquad a\in A \mapsto f_P(a)=a_n a^n + a_{n-1}a^{n-1}+\dots + a_1 a + a_0\in A

La funciones polinómicas reales son funciones suaves, es decir, son infinitamente diferenciables (tienen derivadas de todos los órdenes). Debido a su estructura simple, las funciones polinómicas son muy sencillas de evaluar numéricamente, y se usan ampliamente en análisis numérico para interpolación polinómica o para integrar numéricamente funciones más complejas. Una manera muy eficiente para evaluar polinomios es la utilización de la regla de Horner.

En álgebra lineal el polinomio característico de una matriz cuadrada codifica muchas propiedades importantes de la matriz. En teoría de los grafos el polinomio cromático de un grafo codifica las distintas maneras de colorear los vértices del grafo usando x colores.

Con el desarrollo de la computadora, los polinomios han sido remplazados por funciones spline en muchas áreas del análisis numérico. Las splines se definen a partir de polinomios y tienen mayor flexibilidad que los polinomios ordinarios cuando definen funciones simples y suaves. Éstas son usadas en la interpolación spline y en gráficos por computadora.

Ejemplos de funciones polinómicas[editar]Note que las gráficas representan a las funciones polinómicas y no a los polinomios en sí, pues un polinomio solo es la suma de varios monomios.

Polinomio de grado 2:f(x) = x2 - x - 2= (x+1)(x-2).

Polinomio de grado 3:f(x) = x3/5 + 4x2/5 - 7x/5 - 2= 1/5 (x+5)(x+1)(x-2).

Polinomio de grado 4:f(x) = 1/14 (x+4)(x+1)(x-1)(x-3) + 0.5.

Polinomio de grado 5:f(x) = 1/20 (x+4)(x+2)(x+1)(x-1)(x-3) + 2.La función

f(x)= 13x^4 - 7x^3 + \begin{matrix}\frac{2}{3}\end{matrix} x^2 - 5x + 3es un ejemplo de función polinómica de cuarto grado, con coeficiente principal 13 y una constante de 3.

Factorización de polinomios[editar]Artículo principal: FactorizaciónEn un anillo conmutativo \scriptstyle A una condición necesaria para que un monomio sea un factor de un polinomio de grado n > 1, es que el término independiente del polinomio sea divisible por la raíz del monomio:

P_n^{}(X) = a_n X^n + \dots + a_1 X + a_0 = (X-\alpha)Q_{n-1}(X) necesariamente \alpha_{}^{} divide a a_0^{}.

En caso de que el polinomio no tenga término independiente se sacará la incógnita como factor común y ya está factorizado. También se puede factorizar usando las igualdades notables.

Un polinomio factoriza dependiendo del anillo sobre el cual se considere la factorización, por ejemplo el binomio X_{}^2 -2 no factoriza sobre \scriptstyle\mathbb{Q} pero sí factoriza sobre \scriptstyle\mathbb{R}:

X^2 - 2 = (X + \sqrt{2})(X - \sqrt{2})

Por otra parte X_{}^2+2 no factoriza ni sobre \scriptstyle\mathbb{Q}, ni tampoco sobre \scriptstyle\mathbb{R} aunque factoriza sobre \scriptstyle\scriptstyle \mathbb{C}:

X^2 + 2 = (X + i \sqrt{2})(X - i \sqrt{2})

Un cuerpo en el que todo polinomio no constante factoriza en monomios es un cuerpo algebraicamente cerrado.

Historia[editar]

Volumen de una pirámide truncada.La resolución de ecuaciones algebraicas, o la determinación de las raíces de polinomios, está entre los problemas más antiguos de la matemática. Sin embargo, la elegante y práctica notación que utilizamos actualmente se desarrolló a partir del siglo XV.

En el problema 14º del papiro de Moscú (ca. 1890 a. C.) se pide calcular el volumen de un tronco de pirámide cuadrangular. El escriba expone los pasos: eleva al cuadrado 2 y 4, multiplica 2 por 4, suma los anteriores resultados y multiplícalo por un tercio de 6 (h); finaliza diciendo: «ves, es 56, lo has calculado correctamente». En notación algebraica actual sería: V = h (t² + b² + tb) / 3, un polinomio de cuatro variables (V, h, t, b) que, conociendo tres, permite obtener la cuarta variable.

Algunos polinomios, como f(x) = x² + 1, no tienen ninguna raíz que sea número real. Sin embargo, si el conjunto de las raíces posibles se extiende a los números complejos, todo polinomio (no constante) tiene una raíz: ese es el enunciado del teorema fundamental del álgebra.

Hay una diferencia entre la aproximación de raíces y el descubrimiento de fórmulas concretas para ellas. Se conocen fórmulas de polinomios de hasta cuarto grado desde el siglo XVI (ver ecuación cuadrática, Gerolamo Cardano, Niccolò Fontana Tartaglia). Pero, las fórmulas para polinomios de quinto grado fueron irresolubles para los investigadores durante mucho tiempo. En 1824, Niels Henrik Abel demostró que no puede haber fórmulas generales para los polinomios de quinto grado o mayores (ver el teorema de Abel-Ruffini). Este resultado marcó el comienzo de la teoría de Galois que se ocupa del estudio detallado de las relaciones existentes entre las raíces de los polinomios.

La máquina diferencial de Charles Babbage fue diseñada para crear automáticamente tablas de valores de funciones logarítmicas y diferenciales, evaluando aproximaciones polinómicas en muchos puntos, usando el método de las diferencias de Newton.En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.

Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N^2+N segundos, entonces el problema es resoluble en un "tiempo polinómico".

De esa manera, tiempos de 2n^2+5n, 4n^6+7n^4-2n^2 o n^{2^{2^{175}}} son polinómicos; pero 2^n no lo es.

Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos O(\log n), los lineales O(n), los cuadráticos O(n^2), los cúbicos O(n^3), etc.

Clases de complejidad[editar]En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing no determinista, la clase es llamada NP. Una de las preguntas abiertas más importantes en la actualidad es descubrir si estas clases son diferentes o no. El Clay Mathematics Institute ofrece un millón de dólares a quien sea capaz de responder a esa pregunta.

Diagrama de clases de complejidad. Si P = NP, P contendría las zonas NP y NP-completo.Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P (Ver NP-completo para una definición precisa). Actualmente los investigadores piensan que las clases cumplen con el diagrama mostrado por lo que P y NP-completo tendrían intersección vacía.

La importancia de la pregunta P = NP radica en que, de encontrarse un algoritmo en P para un problema NP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendrían soluciones en tiempo