En matemáticas y algoritmos , el método de Ruffini-Horner , también conocido bajo los nombres de método de Horner , algoritmo de Ruffini-Horner o regla de Ruffini , está disponible en varios niveles. Permite calcular el valor de un polinomio en x 0 . Presenta un algoritmo simple que realiza la división euclidiana de un polinomio por X - x 0 . Pero también ofrece un método para cambiar la variable X = x 0 + Y en un polinomio. Es de esta forma que se utiliza para determinar un valor aproximado de la raíz de un polinomio .
El método Ruffini-Horner de encontrar un valor aproximado de la raíz de un polinomio fue publicado con unos años de diferencia por Paolo Ruffini (1804-1807-1813) y por William George Horner (1819-1845 póstumamente) pero parece que Horner fue sin conocer el trabajo de Ruffini. El método de Horner fue luego popularizado por los matemáticos De Morgan y JR Young . En sus primeras publicaciones, ambos autores utilizan métodos conducen a hacer el cambio de variable x = x 0 + Y . Posteriormente, presentan versiones utilizando únicamente técnicas algebraicas. El método de Ruffini-Horner es difícil de usar si el polinomio tiene dos raíces demasiado cercanas. Ruffini no menciona este problema, pero Horner ofrece un procedimiento especial para este caso.
Como técnica de cambio de las variables, encontramos algoritmos análogos, en China, para la extracción de raíz enésima, en los Capítulos Nueve (263 dC ) y en la obra de Al Samaw al ( XII ° siglo). Pero parece que Sharaf al-Din al-Tusi ( XII ° siglo) el primero en usarlo en el caso general de una ecuación de grado 3.
Es
un polinomio y x 0 un número. El cálculo de P ( x 0 )
sugiere que debemos calcular cada una de las potencias de x 0 , multiplicarlo por su coeficiente a k y luego sumar lo que encontramos.
Si calculamos las potencias de x 0 multiplicando sucesivamente x 0 por sí mismo, el número necesario de productos es entonces n + ( n - 1) +… + 2 + 1 = n ( n +1) / 2, cantidad que aumenta a medida que el cuadrado del grado del polinomio. Podemos mejorar la velocidad del cálculo de xn
0mediante un método de exponenciación rápida , lo que permite reducir el tiempo de cálculo de P ( x 0 ) a una cantidad que aumenta a medida que n × ln ( n ) . O aún más eficientemente, podemos comenzar calculando todas las potencias de x 0 , lo que requiere n - 1 multiplicaciones, luego multiplicar por los coeficientes, lo que requiere n nuevas multiplicaciones: el número total de producto es entonces 2 n - 1. Método de Horner consiste en combinar las dos iteraciones anteriores en una realizando el cálculo de la siguiente manera:
Luego, el número de productos se reduce an y podemos demostrar que este número es mínimo: no es posible evaluar una función polinomial en menos de n productos en general.
Por tanto, el método consiste en multiplicar el primer coeficiente por x 0 y agregarle el segundo coeficiente. Luego multiplicamos el número obtenido por x 0 y sumamos el tercer coeficiente, etc. Está muy bien organizado usando una tabla en la que cada casilla de la segunda fila se obtiene multiplicando el coeficiente de la casilla de la izquierda por x 0 y añadiéndole el coeficiente de la casilla de arriba.
Coeficientes de P | un n | un n - 1 | a n - 2 | ... | un 1 | en 0 |
Factor x 0 | un n | una norte x 0 + una norte - 1 | ( una norte x 0 + una norte - 1 ) x 0 + una norte - 2 | ... | q 0 | P ( x 0 ) = q 0 x 0 + a 0 |
Ejemplo práctico: cálculo de 4 X 3 - 7 X 2 + 3 X - 5 para X = 2
Coeficientes de P | 4 | −7 | 3 | −5 |
Factor 2 | 4 | 8 - 7 = 1 | 2 + 3 = 5 | P (2) = 10 - 5 = 5 |
Además de reducir el número de operaciones, este método puede, en algunos casos, evitar el manejo de números muy grandes y, por lo tanto, puede evitar desbordamientos en los cálculos por computadora. Si tomamos por ejemplo el polinomio P ( X ) = X 10 - 99 X 9 , entonces con el método “clásico”, para evaluar P (100) , debemos calcular 100 10 = 10 20 del cual restamos 99 × 10 18 , dando un resultado erróneo en el cálculo del software con 15 dígitos significativos. Con el método Ruffini-Horner, tenemos
lo que lleva al resultado correcto 100 9 = 10 18 ya que el cálculo de la mantisa solo usó tres dígitos significativos.
Este método también permite realizar una conversión rápida de un número escrito en base x 0 a escritura en base 10. De hecho, si un número está escrito en base x 0 ,
,este número vale
.Por tanto, es la evaluación de un polinomio.
Ejemplo práctico: escritura en base 10 del número hexadecimal DA78
Coeficientes | D (13) | A (10) | 7 | 8 |
Factor 16 | 13 | 13 × 16 + 10 = 218. | 218 × 16 + 7 = 3.495. | DA78 = 3.495 × 16 + 8 = 55.928 |
Este mismo método también permite obtener la división de un polinomio por X - x 0 . O bien .
La división euclidiana de P por X - x 0 da
donde Q es un polinomio de grado n - 1.
Si escribimos y si identificamos los coeficientes del mismo grado en los dos miembros, obtenemos:
para todo k tal que 0 < k < nO todavía
para todo k tal que 0 < k < nLos n valores de la secuencia q calculados aquí son precisamente los n valores sucesivos calculados en el párrafo anterior para evaluar P ( x 0 ) . La memorización de estos valores sucesivos da por tanto los coeficientes del polinomio del cociente, siendo el último valor el del resto.
Aplicación práctica: división euclidiana de 4 X 3 - 7 X 2 + 3 X - 5 por X - 2
Basta tomar la tabla previamente construida y leer los coeficientes de Q en los recuadros de la segunda línea .
Coeficientes de P | 4 | - 7 | 3 | - 5 |
Coeficientes de Q | 4 | 8 - 7 = 1 | 2 + 3 = 5 | Resto = 10 - 5 = 5 |
Entonces
Por tanto, el algoritmo anterior permite realizar la división euclidiana del polinomio P por X - x 0 . Entonces podemos escribir, estableciendo Y = X - x 0 .
Usando el algoritmo nuevamente para P 1 , P 2 , ... P n , obtenemos sucesivamente
...
Los números b 0 , b 2 , ... b n son, por tanto, los coeficientes del polinomio Q tales que Q ( Y ) = P ( x 0 + Y )
Ilustración práctica: Si P ( X ) = 4 X 3 - 7 X 2 + 3 X - 5 y que queremos escribir P (2 + Y ) , se aplica 4 veces el método de la división euclidiana por X - 2 :
Coeficientes de P | 4 | - 7 | 3 | - 5 |
Coeficientes de P 1 | 4 | 8 - 7 = 1 | 2 + 3 = 5 | 10 - 5 = 5 |
Coeficientes de P 2 | 4 | 8 + 1 = 9 | 18 + 5 = 23 | |
Coeficientes de P 3 | 4 | 8 + 9 = 17 | ||
Coeficientes de P 4 | 4 |
Entonces
Para encontrar el valor x aproximado de una raíz de un polinomio P , buscamos un número entero x 0 tal que P ( x 0 ) y P ( x 0 + 1) sean de signo opuesto. Entonces sabemos por el teorema del valor intermedio que hay una raíz entre x 0 y x 0 + 1 . Luego establecemos x = x 0 + y / 10 . El número x es la raíz de P ( X ) si y solo si el número y / 10 es la raíz de P ( x 0 + Y ) = Q ( Y ) . Este polinomio Q se determina mediante el método de Horner. Finalmente x es la raíz de P (X) si y solo y es la raíz de un polinomio R ( X ) obtenido al multiplicar los coeficientes b k de Q por .
Se trata entonces de buscar una raíz de R entre 0 y 10 mediante un proceso análogo: buscamos un entero x 1 entre 0 y 9 tal que R ( x 1 ) y R ( x 1 + 1) sean de signo contrario . Entonces sabemos que hay una raíz x de P entre x 0 + x 1 /10 y x 0 + ( x 1 + 1) / 10 ...
Por tanto, determinamos los sucesivos decimales de la expansión decimal de x .
Ejemplo: algoritmo de Ruffini-Horner para extraer la raíz cúbica de 18.
Es una cuestión de encontrar un verdadero x , raíz del polinomio P ( X ) = X 3 - 18 de . Inmediatamente sabemos que P (2) <0 y P (3)> 0 , x está por lo tanto entre 2 y 3. Luego establecemos x = 2+ y / 10 y buscamos el polinomio Q tal que P (2 + Y ) = Q ( Y ) .
Coeficientes de P | 1 | 0 | 0 | - 18 |
Coeficientes de P 1 | 1 | 2 | 4 | - 10 |
Coeficientes de P 2 | 1 | 4 | 12 | |
Coeficientes de P 3 | 1 | 6 | ||
Coeficientes de P 4 | 1 |
La x real es la raíz cúbica de 18 si x = 2 + y / 10 donde y es la raíz de R ( X ) = X 3 + 60 X 2 + 1200 X - 10000 . La raíz y está entre 6 y 7 (para evitar barrer todos los números, solo observe que 1200 y y 10000 deben estar muy cerca con 1200 y <10000 ). Luego establecemos y = 6 + z / 10 y buscamos el polinomio S tal que R (6 + Z ) = S ( Z ) .
Coeficientes de R | 1 | 60 | 1200 | -10000 |
Coeficientes de R 1 | 1 | 66 | 1596 | -424 |
Coeficientes de R 2 | 1 | 72 | 2028 | |
Coeficientes de R 3 | 1 | 78 | ||
Coeficientes de R 4 | 1 |
La y real es la raíz de R si y = 6 + z / 10 donde z es la raíz de T ( X ) = X 3 + 780 X 2 + 202800 X - 424000 . La raíz z está entre 2 y 3. Entonces y está entre 6.2 y 6.3 yx está entre 2.62 y 2.63.
Esta propiedad aparece aquí en la última posición mientras que es la propiedad inicial resaltada por Ruffini y Horner. Sin embargo, como es posible un enfoque puramente algebraico, primero se presentó este más simple. El mismo algoritmo también permite determinar el valor de P ( k ) ( x 0 ) . De hecho, la expansión de Taylor de P ( x 0 + Y ) da
Si denotamos por Q ( Y ) = P ( x 0 + Y ) , los coeficientes b k de Q , encontrados por el método de Ruffini-Horner verifican la igualdad