MenúLa regla de Horner
Típicamente, un polinomio se expresa como:
$f(x)=\sum_{k=0}^{n} a_k x^k$
o
Donde ak son números reales que representan los coeficientes polinomiales y
xk son las variables polinomiales.
El polinomio anterior se dice que es del n-ésimo grado, p.ej. deg(f(x)) = n donde n representa el exponente de variable más alto.
La regla de Horner para la división polinomial es un algoritmo utilizado para simplificar el proceso de evaluación de un polinomio f(x) para un cierto valor x = x0 dividiendo el polinomio en monomios (polinomios de 1er grado). Cada monomio implica un máximo de una multiplicación y un proceso de suma. El resultado obtenido de un monomio se agrega al resultado obtenido del siguiente monomio y así sucesivamente de manera acumulativa. Este proceso de división también se conoce como división sintética.
Para explicar lo anterior, reescribamos el polinomio en su forma expandida;
Esto también puede ser escrito como:
El algoritmo propuesto por esta regla se basa en evaluar los monomios formados anteriormente a partir del que está en el paréntesis más interno y avanzar para evaluar los monomios en el paréntesis externo.
El algoritmo se ejecuta siguiendo los pasos a continuación:
2. Haga bk = ak
3. Haga bk - 1 = ak - 1 + bkx0
4. Haga k = k - 1
5. Si k ≥ 0 entonces vaya al paso 3
Si no, finalice.
Este algoritmo puede también visualizarse gráficamente, considerando el polinomio de 5to grado dado por:
el cual puede ser evaluado en x = x0 reorganizándolo como:
Otra forma de representar los resultados utilizando este algoritmo es a través del cuadro que se presenta a continuación:
| K | 5 | 4 | 3 | 2 | 1 | 0 |
| b5 = a5 | b4 = a4 + x0b5 | b3 = a3 + x0b4 | b2 = a2 + x0b3 | b1 = a1 + x0b2 | b0 = a0 + x0b1 |
Ejemplo: Evaluar el polinomio f(x) = x4 + 3x3 + 5x2 + 7x + 9 para x = 2
Solución:
Dado que el polinomio es de 4to grado, entonces n = 4
| K | 4 | 3 | 2 | 1 | 0 |
| Paso | b4 = 1 | b3 = 3 + 2 * 1 | b2 = 5 + 2 * 5 | b1 = 7 + 2 * 15 | b0 = 9 + 2 * 37 |
| Resultado | 1 | 5 | 15 | 37 | 83 |
Por lo tanto, f(2) = 83.
¿Por qué tenemos que hacer esto?
Normalmente, cuando evaluamos un polinomio en un cierto valor, estamos acostumbrados a sustituir este valor en el polinomio y hacer los cálculos matemáticos. También podemos usar o desarrollar una aplicación de cálculo matemático para hacer eso, lo cual es una necesidad cuando se trata de polinomios complejos con altos grados.
La forma en que la computadora procesa un problema depende, principalmente, de cómo usted, como programador, lo escriba en la computadora. Puede diseñar su aplicación para resolver el polinomio mediante sustitución directa o utilizando la división sintética de acuerdo con la regla de Horner. La única diferencia entre los dos enfoques es la velocidad a la que la computadora resolverá el problema en cada caso.
La ventaja que ofrece la regla de Horner es que reduce el número de operaciones de multiplicación. Dado que se sabe que el tiempo de procesamiento de la computadora para un solo proceso de multiplicación es de 5 a 20 veces el tiempo de procesamiento de un proceso de suma, se puede decir que el diseño de su aplicación para evaluar el polinomio usando la regla de Horner tendrá una mejora significativa en el tiempo de ejecución que tomará la computadora.
