Encontrar las raíces reales de un polinomio

Question

Los últimos posts sobre polinomios me han hecho pensar.

Quiero encontrar las raíces reales de un polinomio con coeficientes reales en una variable real $x$ . Sé que puedo utilizar una Secuencia de Sturm para hallar el número de raíces entre dos límites elegidos $a < x < b$ .

Dado que $p(x) = \sum_{r=0}^n a_rx^r$ con $a_n = 1$ ¿cuáles son los valores más ajustados para $a$ y $b$ que se expresan simplemente en términos de los coeficientes $a_r$ y que se aseguren de que capto todas las raíces reales?

Puedo obtener fácilmente algunos límites sueltos y hacer que el ordenador se encargue del resto, y si aproximo las soluciones mediante algún algoritmo puedo obtener soluciones más ajustadas. Pero quiero ser codicioso y obtener el máximo valor por el mínimo trabajo.

Answer 1

¿Qué se considera "simplemente expresado"? En Límite Fujiwara sobre la magnitud de todas las raíces (incluidas las complejas) es sin duda un muy buen punto de partida. Lo utilicé para un solución a un problema de codegolf.SE que implican raíces complejas y lo encontró perfectamente adecuado para ese contexto.

Answer 2

En realidad tuve que hacer esto para la escuela hace aproximadamente un mes, y el método que se me ocurrió fue el siguiente:

1. Obsérvese que todos los ceros de un polinomio se encuentran entre un mínimo local y un máximo local (incluidos los límites en el infinito). Sin embargo, no todos los pares adyacentes de un mínimo y un máximo tienen un cero en medio, pero eso es irrelevante.
2. Por lo tanto, se pueden encontrar los mínimos y los máximos y converger en la raíz intermedia utilizando el método de bisección (si están en lados opuestos del eje x).
3. Para encontrar los mínimos y los máximos, hay que tomar la derivada y encontrar sus ceros.
4. Teniendo en cuenta que se trata de un procedimiento para encontrar ceros, el paso 3 se puede hacer recursivamente.
5. El caso base para la recursión es una línea. Aquí, $y=ax+b$ y el cero es $-\frac{b}{a}$ .

Esta es una forma muy fácil y rápida de encontrar todos los ceros reales (con una precisión teóricamente arbitraria) :D