gauss

Multiplicaciones sucesivas Algoritmo de Horner
En 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

donde son números reales, queremos evaluar el polinomio a un valor específico de , digamos .
Para llevar a cabo elprocedimiento, definimos una nueva secuencia de constantes como se muestra a continuación:













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

Después, sustituyendo iterativamente la en la expresión,





















Aplicación
El algoritmo de Horner se usa a menudo para convertir entredistintos 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
La evaluación usando la forma monomial del polinomio de grado-n requiere al menos n sumas y (n2+n)/2multiplicaciones, 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 ha demostrado que el algoritmo de Horner es óptimo, de modo que cualquier algoritmo que se use para evaluarun 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.














Método de bisección


Unas cuantas iteraciones del métodode bisección aplicadas en un intervalo [a1;b1]. El punto rojo es la raíz de la función.
En matemáticas, el método de bisección es un algoritmo de búsqueda de raíces que trabaja dividiendo el intervalo a la mitad y seleccionando el subintervalo que tiene la raíz. Introducción
Este es uno de los métodos más sencillos y de fácil intuición para resolver ecuaciones en una variable. Se basa en elteorema del valor intermedio (TVI), el cual establece que toda función continua f en un intervalo cerrado [a,b] toma todos los valores que se hallan entre f(a) y f(b). Esto es que todo valor entre f(a) y f(b) es la imagen de al menos un valor en el intervalo [a,b]. En caso de que f(a) y f(b) tengan signos opuestos, el valor cero sería un valor intermedio entre f(a) y f(b), por lo que con certeza existeun p en [a,b] que cumple f(p)=0. De esta forma, se asegura la existencia de al menos una solución de la ecuación f(a)=0.
El método consiste en lo siguiente:
Debe existir seguridad sobre la continuidad de la función f(x) en el intervalo [a,b]
A continuación se verifica que
Se calcula el punto medio m del intervalo [a,b] y se evalúa f(m) si ese valor es igual a cero, ya hemos encontrado laraíz buscada
En caso de que no lo sea, verificamos si f(m) tiene signo opuesto con f(a) o con f(b)
Se redefine el intervalo [a, b] como [a, m] ó [m, b] según se haya determinado en cuál de estos intervalos ocurre un cambio de signo
Con este nuevo intervalo se continúa sucesivamente encerrando la solución en un intervalo cada vez más pequeño, hasta alcanzar la precisión deseada
En la siguientefigura se ilustra el procedimiento descrito.
El método de bisección es menos eficiente que el método de Newton, pero es mucho más seguro para garantizar la convergencia. Si f es una función continua en el intervalo [a, b] y f(a)f(b) < 0, entonces este método converge a la raíz de f. De hecho, una cota del error absoluto es:

en la n-ésima iteración. La bisección converge linealmente, por lo cual...