Disco con raíz en el centro con ningún otro raíces en el polinomio

Question

Digamos que tenemos un polinomio $p$ con raíces $r_1,r_2...r_n$, estoy buscando una manera de encontrar un disco que, si se coloca en el centro de cualquier raíz, no contiene ninguna otra raíz (múltiples raíces considerado como uno). No tiene que ser el más grande de disco, pero el disco más grande, el mejor.

Edit: no sé las raíces de antemano, sólo los coeficientes. El cálculo de ellos no es una opción.

No tengo absolutamente ni idea de cómo ir sobre esto.

Answer 1

El problema que usted describe se llama raíz de aislamiento.

Véase, por ejemplo, estos documentos:

• Una Sencilla, Pero Exacta y Eficiente Algoritmo para el Complejo de la Raíz de Aislamiento y su Análisis de la Complejidad

• Un Eficiente y Exacta Algoritmo de Subdivisión para Aislar las Raíces Complejas de un Polinomio y su Análisis de la Complejidad

• Estudio empírico de una Evaluación Basada en Algoritmo de Subdivisión para los Complejos de Raíz de Aislamiento

y otros en http://cs.nyu.edu/exact/papers/.

Answer 2

Primer paso, deshacerse de varias raíces por determinar el mcd de a $p$ y su derivado $p'$ y si no es constante, dividiendo $p/gcd(p,p')$. Hay métodos para determinar un aproximado de mcd para no exacta de los coeficientes.

Ahora suponiendo que $p$ es cuadrado-libre, calcular el discriminante de $p$, es decir, una normalizado múltiples de la resultante de $p$$p'$. En la versión normalizada, haciendo caso omiso de los signos, uno tiene $$ |disco(p)|=\prod_{i<j}|z_i-z_j|^2 $$ si $n=\deg p$ $z_1,...,z_n$ son las raíces de $p$. Para el siguiente, supongamos que $|z_1-z_2|$ es la distancia mínima. Todas las demás distancias será menor de lo $2R$ si $R$ es un límite en las magnitudes de las raíces (Cauchy, Lagrange, tal vez refinado a través de Graeffe iteraciones). Entonces $$ |z_1-z_2|\ge r=\frac{\sqrt{disc(p)}}{(2R)^{(n+1)(n-2)/2}} $$

---

En la no-exacto aritmética, si la precisión utilizado para el aproximado de mcd es alta, cerca de las raíces no pueden ser tratados de la misma raíz, por lo que la resultante discriminante y el resultado de la raíz de la separación de radio $r$ esto se reflejará en la pequeña distancia. Va para otro lado, permitiendo un amplio margen en el cómputo aproximado de la dpc resultará en una raíz de la separación de radio que se llamaría más bien de una raíz clúster de la separación de radio.