¿Cómo debo aproximar los números reales por los algebraicos?

Question

Dado un número real de alta precisión, ¿cómo debo hacer para adivinar un número entero algebraico al que se aproxime?

Por supuesto, esto está extremadamente mal definido -- ¡todo número real está cerca de un número racional, por supuesto! Pero me gustaría que tanto los coeficientes como el grado fueran relativamente pequeños. Obviamente, podemos hacer concesiones entre cuánto nos disgustan los coeficientes grandes y cuánto nos disgustan los grados grandes.

Pero dejando eso de lado, no sé ni cómo empezarías. ¿Alguna idea?

Antecedentes : esto sale del proyecto que impulsó Noah's pregunta reciente en la resolución de grandes sistemas de cuadráticas. Intentamos encontrar subfactores dentro de sus álgebras planas de grafos. Hemos descubierto que resolver cuadráticas numéricamente, aproximar las soluciones por números enteros algebraicos y luego comprobar que éstas son realmente soluciones exactas es muy eficaz. Hasta ahora, hemos utilizado la herramienta de Mathematica " RaízAproximada " que hace exactamente lo que pido aquí, pero es una caja negra impenetrable, como todo lo que sale de Wolfram.

Answer 1

El algoritmo de reducción de la base reticular Lenstra-Lenstra-Lovasz es lo que necesitas. Suponga que su número real es a y que quiere una ecuación cuadrática con coeficientes lo más pequeños posible, de la que a es casi una raíz. Entonces calcula 1,a,a^2 (con cierta precisión), encuentra una relación entera no trivial entre ellos, y utiliza el algoritmo LLL para encontrar una mucho mejor a partir de la primera. Exactamente este ejemplo se discute en la entrada de Wikipedia sobre el algoritmo LLL, aplicado al número de la Sección Dorada. Y hay una gran literatura sobre el algoritmo y sus muchas aplicaciones. (Para mayor grado, calcula 1,a,a^2,...,a^n).

Answer 2

Básicamente se busca una pequeña relación integral entre las potencias del número dado. Esto puede hacerse eficazmente con el algoritmo LLL (Lenstra-Lenstra-Lovasz) y sus variaciones (especialmente PSLQ), y de hecho este enfoque se utiliza para determinar candidatos "simbólicos inversos" para un número real aproximado. Consulte los artículos de Plouffe y Bailey como este .

Answer 3

Yo no sé algebraicas número de aproximaciones; pero la mayoría de los canónica aproximación a los números reales por los números racionales es la continuación de la fracción de expansión. Ellos y sus convergents (de primer o segundo orden) son, en muchos sentidos, las mejores aproximaciones a un número real por un número racional. Estos son fáciles de probar, pero no quiero entrar en eso aquí. Cuando tienes un fin de semana libre en lugar de leer alguna novela usted puede tener una mirada en Khintchine del libro "Fracciones continuas", en el que todo se explica muy claramente.

Para la aproximación a los números algebraicos, supongo que algunos expertos en Mahler medida puede contribuir en algo.

Esta es una respuesta más teórico, en espíritu, en comparación con el algorítmicos se ha dado hasta ahora.