Buscadores de raíces polinómicas con ordenamiento de raíces consistente

Cuando se trata de resolver polinomios simples con coeficientes complejos y raíces complejas, podemos usar fórmulas explícitas. Por ejemplo, las raíces del polinomio z 2 − C son la lista ( C , − C ) . Una pequeña perturbación en los coeficientes dará como resultado una pequeña perturbación en las raíces, pero la lista no se permutará.

Para polinomios de mayor grado usaremos algún tipo de procedimiento numérico que nos dé una lista de raíces. Pero ejecutar el procedimiento numérico en el mismo polinomio por segunda vez puede darnos las mismas raíces en un orden diferente (porque puede haber utilizado la aleatoriedad al seleccionar el punto de inicio de una iteración). E incluso si ese no es el caso, no hay garantía de que perturbar ligeramente el polinomio produzca las raíces perturbadas en el mismo orden que las raíces del original.

Por ejemplo, un solucionador numérico podría dar las raíces de z 2 − C como ( norte ⁡ ( C ) , − norte ⁡ ( C ) ) y las raíces de z 2 − ( C + ϵ ) como ( − norte ⁡ ( C + ϵ , norte ⁡ ( C + ϵ ) ) , dónde norte ⁡ ( ) es una aproximación numérica.

¿Existen buscadores de raíces numéricos que conserven el orden de las raíces, así como solucionadores basados ​​en fórmulas? (Hay algunas complejidades que se discuten en los comentarios... es imposible que las raíces varíen continuamente con coeficientes en todas partes, incluso los solucionadores basados ​​en fórmulas tendrán cortes de rama)

Los polinomios que me interesan son de grado pequeño: menos de 10. Y sería más feliz si la respuesta también apuntara a una implementación confiable de código abierto.

Está asumiendo que las raíces son reales y permanecerán reales bajo una pequeña perturbación. Deberías leer sobre el polinomio de Wilkinson , aunque es de grado 20 .. Todas sus raíces son reales y bien separadas, pero perturbando un coeficiente por un error relativo de 2 − 29 envía las raíces al plano complejo, cuatro con partes imaginarias mayores que 2 .
La parte invariante de perturbaciones de esto es imposible por razones topológicas. Considere la familia de polinomios z 2 − mi i t . Si el algoritmo produce el resultado ( 1 , − 1 ) cuando t = 0 y es invariante bajo pequeñas perturbaciones de t , debe producir el resultado ( mi i t / 2 , − mi i t / 2 ) . Pero eso significa que cuando llegas a t = 2 π obtienes las mismas raíces en el orden opuesto, para el mismo polinomio.
@Ross, no asumo que las raíces sean reales. Si alguna parte de la pregunta implica eso, házmelo saber e intentaré solucionarlo.
Si las raíces no son reales, el concepto de orden se vuelve más difícil porque los números complejos no tienen un orden obvio. En el ejemplo de Wilkinson, no es fácil decir qué raíz en el polinomio original corresponde a qué raíz en el polinomio perturbado, por lo que no está claro en qué orden desea que se produzcan las raíces del polinomio perturbado.
@Miqueas, buen punto. Admito que estoy luchando por formular la pregunta correcta, y tal vez la idea de la perturbación sea la forma incorrecta de hacerlo. Tengo una vaga idea de que si el polinomio es un norte -doblar la cubierta con norte hojas que las raíces deben estar en 'orden de hoja' si eso tiene algún sentido. Por lo tanto, está bien que haya el tipo de discontinuidad que su ejemplo implicaría: en los cortes entre las hojas.
@Micah, incluso con una fórmula como C las raíces saltarán de vez en cuando. Pero me gustaría un solucionador numérico que se comporte tanto como sea posible como un solucionador basado en fórmulas. En otras palabras, la mayoría de las veces las raíces se mueven continuamente con los coeficientes, con saltos aquí y allá.
@Ross, tendría que mirar más de cerca su ejemplo, pero me imagino que si hace que las perturbaciones sean lo suficientemente pequeñas, verá cómo se corresponden las raíces. Sin embargo, es posible que tenga que refinar mi pregunta para abordar los problemas planteados en estos comentarios.
Es posible que necesite algo como arxiv.org/pdf/math/9201280.pdf , pero aún no he leído el documento. Estaba buscando orientación en un campo del que no sé casi nada.
Es cierto que si las perturbaciones son lo suficientemente pequeñas, las raíces son funciones continuas de los coeficientes. Lo que sucede es que dos raíces se mueven una hacia la otra, se encuentran en la línea real y luego se disparan en la dirección imaginaria. La perturbación requerida para esto es minúscula . Sospecho que es porque a los polinomios no les gusta tener raíces igualmente espaciadas.
Usted es libre de ordenar las raíces (digamos, primero por componente real, luego por imaginario) después de encontrarlas. Es casi seguro que computacionalmente será mucho más barato ordenar las raíces que usar un algoritmo menos eficiente.
Su pregunta me recuerda el trabajo que había estado haciendo un antiguo colega mío (S. Kranich). Un límite épsilon-delta para curvas algebraicas planas y su uso para la continuación homotópica certificada de sistemas de curvas algebraicas planas es la mejor referencia que puedo encontrar para eso en este momento. Creo que relacionaría la separación de raíces con la perturbación permitida. ¿Quizás la " continuación de la homotopía " mencionada en ese título es el tipo de concepto que querías pedir?
@MvG: sí, eso suena bien. Desafortunadamente, no puedo recordar la motivación original de esta pregunta, pero al menos ahora sabré el término de búsqueda adecuado. Si desea convertir su comentario en una respuesta, lo marcaré como aceptado.

Respuestas (1)

Esta no es una respuesta completa, simplemente un comentario convertido en una respuesta para proporcionar referencias y palabras clave potencialmente útiles.

Su pregunta me recuerda el trabajo que había estado haciendo un antiguo colega mío (S. Kranich). Un límite épsilon-delta para curvas algebraicas planas y su uso para la continuación homotópica certificada de sistemas de curvas algebraicas planas es la mejor referencia que puedo encontrar para eso en este momento. Creo que relacionaría la separación de raíces con la perturbación permitida. Como señalaron algunos comentarios, definitivamente hay algunos polinomios malvados donde esa relación es realmente pobre, e incluso un pequeño cambio en los coeficientes conduciría a un cambio masivo en las raíces, lo que anularía el enfoque.

¿Quizás la " continuación de la homotopía " mencionada en ese título es el tipo de concepto que querías pedir? Tal como lo entiendo, la idea es que su objetivo sea rastrear raíces a lo largo de un camino desde la situación original hasta una algo perturbada. El documento anterior le dirá qué tan grande puede hacer los pasos individuales a lo largo de este camino si quiere estar seguro de que las raíces coincidentes por distancia mínima mapearán las cosas "correctamente", o más específicamente las mapearán como un movimiento continuo con pasos infinitamente pequeños. los mapearía. Por supuesto, el camino tiene que evitar situaciones singulares/múltiples raíces para tener alguna posibilidad de éxito.

No estoy seguro de si el documento anterior tiene en cuenta los problemas numéricos. Si tiene una garantía teórica de que las raíces tienen una cierta separación garantizada, entonces el hecho de que cualquier enfoque numérico solo encuentre aproximaciones de las raíces reales podría diluir el beneficio. Incluso podría llegar a una situación en la que la situación garantizada sea más pequeña que el error de redondeo numérico esperado, o el tamaño del paso a lo largo de la ruta sea más pequeño que la unidad en el último lugar de su variable de perturbación.

Buscadores de raíces polinómicas con ordenamiento de raíces consistente
RespuestasAquíPolítica de privacidad1y, 0v