Escalar un conjunto de reales para que sean casi enteros

Question

Tengo un conjunto $P$ de $n$ números reales positivos, por ejemplo: $$ P = \{ \pi, e, \sqrt{2} \} \approx \{3.14159, 2.71828, 1.41421\} \;. $$ Teniendo en cuenta algunos $\epsilon > 0$ Me gustaría encontrar el factor de escala más pequeño factor $s \ge 1$ de manera que, para cada $x \in P$ , $s x$ está dentro de $\epsilon$ de un número entero. Más precisamente, si $[z]$ es $z$ redondeado al número entero más cercano, entonces $| sx - [sx] | < \epsilon$ . Por ejemplo, si $\epsilon = 0.08$ entonces $s=7.018$ funciona para lo anterior $P$ :

$$ 7.018 \, P \approx \{22.0477, 19.0769, 9.92495\} \;, $$ y los espacios a los enteros más cercanos son $$ \{0.0477, 0.0769, 0.0750\} \;. $$ Pero no sé que $7.018$ es el mínimo.

Q . ¿Cuál es el procedimiento general para calcular el menor $s$ , dado $P$ y $\epsilon$ ?

Answer 1

Hay un método sencillo: buscar entre todos los posibles valores enteros para que redondeen.

Puede ser "poco elegante", pero es simple La aplicación es fácil y puede satisfacer sus necesidades.

Para explicar cómo podría funcionar esto, podríamos proceder de la siguiente manera:

• El intervalo de $s$ Satisfaciendo a $|s \pi - 1| < \epsilon$ es demasiado pequeño
• El intervalo de $s$ Satisfaciendo a $|s \pi - 2| < \epsilon$ es demasiado pequeño
• El intervalo de $s$ Satisfaciendo a $|s \pi - 3| < \epsilon$ es demasiado pequeño
• El intervalo de $s$ Satisfaciendo a $|s \pi - 4| < \epsilon$ es $s \in \left( \frac{4-\epsilon}{\pi}, \frac{4+\epsilon}{\pi} \right) $
  • No hay números enteros en el intervalo $\left( \frac{4-\epsilon}{\pi} \cdot e, \frac{4+\epsilon}{\pi} \cdot e \right) $
• El intervalo de $s$ Satisfaciendo a $|s \pi - 5| < \epsilon$ es $s \in \left( \frac{5-\epsilon}{\pi}, \frac{5+\epsilon}{\pi} \right) $
  • No hay números enteros en el intervalo $\left( \frac{5-\epsilon}{\pi} \cdot e, \frac{5+\epsilon}{\pi} \cdot e \right) $
• El intervalo de $s$ Satisfaciendo a $|s \pi - 6| < \epsilon$ es $s \in \left( \frac{6-\epsilon}{\pi}, \frac{6+\epsilon}{\pi} \right) $
  • No hay números enteros en el intervalo $\left( \frac{6-\epsilon}{\pi} \cdot e, \frac{6+\epsilon}{\pi} \cdot e \right) $
• El intervalo de $s$ Satisfaciendo a $|s \pi - 7| < \epsilon$ es $s \in \left( \frac{7-\epsilon}{\pi}, \frac{7+\epsilon}{\pi} \right) $
  • El intervalo $\left( \frac{7-\epsilon}{\pi} \cdot e, \frac{7+\epsilon}{\pi} \cdot e \right) $ contiene el número entero $6$
  • El intervalo de $s$ Satisfaciendo a $|s \pi - 7| < \epsilon$ y $|s e - 6| < \epsilon$ es $(2.2027, 2.23671)$
    • No hay números enteros en el intervalo $(2.2027 \cdot 1.4142, 2.23671 \cdot 1.4142)$
• El intervalo de $s$ Satisfaciendo a $|s \pi - 8| < \epsilon$ es $s \in \left( \frac{8-\epsilon}{\pi}, \frac{8+\epsilon}{\pi} \right) $

y así sucesivamente.

Answer 2

Tal $s$ conduce a buenas aproximaciones racionales para los cocientes de los componentes (aquí, $\frac \pi e\approx\frac{22}{19}$ , $\frac\pi{\sqrt 2}\approx\frac{22}{10}$ y $\frac e{\sqrt 2}\approx\frac{19}{10}$ ). Generalizando, buscamos aproximaciones racionales $\alpha\approx \frac nm$ donde más precisamente $\frac{n-\epsilon}{m+\epsilon}<\alpha<\frac{n+\epsilon}{m-\epsilon}$ . En otras palabras, $\alpha=\frac{n+t\epsilon}{m-t\epsilon}$ con $-1<t<1$ . Soloving para $t$ obtenemos $$\tag1t=t(n.m)=\frac{\alpha m-n}{(1+\alpha)\epsilon} $$ y por lo tanto se busca una aproximación racional $\frac nm$ con $$\left|\alpha-\frac nm\right|<\frac{(1+\alpha)\epsilon}{m}$$ Vemos que realmente queremos aproximar racionalmente nuestro número $\alpha$ (de hecho varios números simultáneamente) con un relativa error $\sim\epsilon$ . El método de ensayo descrito en Hurkyl es ciertamente sencilla y suficiente para muchas aplicaciones, siempre que $\epsilon$ no es demasiado pequeño y los cocientes no son "demasiado irracionales".

En casos más complejos se puede ahorrar tiempo recorriendo de forma más sistemática las aproximaciones racionales suficientemente buenas. Jugar con Fracciones de la tarifa puede ser de buena ayuda allí.

Ejemplo de cálculo: $\frac{\pi}{\sqrt 2}$ está entre $\frac 21$ y $\frac 31$ . Utilizando $(1)$ encontramos $t(2,1)\approx 0.86$ que es lo suficientemente bueno (mientras que el múltiplo $t(4,2)\approx 1.7$ no lo es); pero $t(3,1)\approx -3$ es malo. A continuación probamos la suma de Farey $\frac{2+3}{1+1}=\frac 52$ : $t(5,2)\approx -2.2$ es malo. Intentamos la siguiente suma de Farey (observando que $\frac 52$ sustituye a $\frac 31$ porque su $t$ -son ambos negativos) $\frac{2+5}{1+2}=\frac 73$ . Como $t(7,3)\approx -1.3$ continuamos con $\frac{2+7}{1+3}=\frac 94$ . Como $t(9,4)\approx -0.44$ han encontrado otro candidato (de hecho dos candidatos como $t(18,8)\approx -0.88$ también es bueno). Ahora tenemos que probar ambos $\frac{2+9}{1+4}=\frac {11}5$ y $\frac{9+7}{4+3}=\frac{16}{7}$ . Encontramos que $t(11,5)\approx 0.42$ y $t(22,10)\approx 0.83$ mientras que $t(16,7)\approx -1.7$ . Hasta ahora hemos encontrado los primeros términos de una secuencia de fracciones candidatas o quizás más bien proporciones (porque queremos distinguir las formas que no están en términos más cortos) (no necesariamente en términos más cortos), aproximadamente en orden ascendente de cualquiera de las partes $$2:1, 9:4, 18:8, 11:5, 22:10, \ldots $$ Podemos generar simultáneamente las correspondientes secuencias para $\frac\pi e$ y $\frac e{\sqrt 2}$ y encontrar fácilmente la menor "coincidencia", lo que lleva a $\pi:e:\sqrt 2\approx 22:19:10$ . A partir de aquí, es sencillo encontrar el menor $s$ .