Analisis numerico

Método de Horner
Es un método que nos sirve para calcular raíces, trabaja de manera tabular cerrada, es decir, no iterativa. Trata con funciones polinomicas y fue creado por William Horner quien a los 14 años ya era maestro auxiliar. Se ha 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 deoperaciones.
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.
Dado el polinomio

Donde son númerosreales, queremos evaluar el polinomio a un valor específico de , digamos . Para llevar a cabo el procedimiento, definimos una nueva secuencia de constantes como se muestra a continuación:
| | |
| | |
| | |
| | |
Entonces es el valor de . Para ver cómo funciona esto, nótese que el polinomio puede escribirse de la forma.

Después, sustituyendo iterativamente la bi en laexpresión (después de: "a1+" va x0 y no x),
| | |
| | |
| | |
| | |
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 deseableporque necesitan mucha carga computacional y son inestables comparadas con la suma).
Se ha 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.
Ventajas | Desventajas | Formula |
Se puede decir que es un método rápido y sencillo pues al trabajar de manera tabular no requiereiteraciones. | Cuando x es una matriz, el algoritmo de Horner no es óptimo. | Algoritmoresult = a[n]for i = n - 1 down to 0 doresult = result * xresult = result + a[i]end forreturn result |

Partiendo de que el método de Horner se basa en la factorización de polinomios podemos decir que en el algoritmo el lazo for se hace N veces, hay una multiplicación en el lazo, hay una adición en el lazo yhay un total de N multiplicaciones y N adiciones, con eso nos ahorramos nos ahorramos N-1 multiplicaciones sobre el algoritmo estándar.
Un método muy eficaz para resolver ecuaciones de tercer grado o mayor, es el método por descomposición de Ruffini-Hörner. Este método lo que hace es descomponer un polinomio algebraico de grado n, en un binomio algebraico y en otro polinomio algebraico de grado(n - 1). Para ello es necesario conocer al menos una de las raíces del polinomio original, si es que se quiere que la descomposición sea exacta, de lo contrario el método que les presentaré entrega el resto de la descomposición.
Veamos el método a través de algunos ejemplos:
Por ejemplo se tiene el polinomio algebraico x3 + 2x2 + x – 4 y lo queremos dividir por x – 1
Primero se escriben loscoeficientes del polinomio original en línea:
1 2 1 -4
luego el primer coeficiente se baja sin hacerle nada:
1 2 1 -4
____________________
1
enseguida consideramos el acompañante de x con signo contrario (en este caso 1) y lo multiplicamos por el número que quedó abajo. El resultado de la multiplicación lo ponemos debajo del coeficiente que sigue y se lo sumamos:
1 2 1 -4
1 1

1 3finalmente repetimos este último paso (con lo coeficientes siguientes) hasta que ya no queden coeficientes:
1 2 1 -4
1 1 3 4
____________________
1 3 4 0
Los números que aparecen en la última fila son los coeficientes del nuevo polinomio algebraico de grado (n – 1). El último número es el resto de la división. En este caso es 0, por lo tanto la división es exacta.
Nos queda: x3 + 2x2 + x – 4 = (x...