Es $k$ que satisface $\alpha^{\frac{1}{k}}<1+ε$ polinomio en $\frac1ε$?

Question

Estoy haciendo un ejercicio de aproximación de los algoritmos de curso, y mi el algoritmo toma como entrada un número constante $\alpha$ y se encuentra en la mínimo $k_{0}$ s.t $\sqrt[k]{\alpha}<1+ε$ (esto promesa me $1+ε$ aproximación).

Claramente, $k_{0}$ existen y no estoy molesta con el cálculo de dentro de mis algoritmo. Lo que estoy preocupado es como mi solución se comporta como $ε\to0$.

Mi pregunta es: el Es $k_{0}$, que es la solución mínima para $\sqrt[k]{\alpha}<1+ε$, polinomio en $\dfrac{1}{ε}$?

Answer 1

Ya que$$ α^{\frac{1}{k}} < 1 + ε \Longleftrightarrow \frac{1}{k} \ln α < \ln(1 + ε) \Longleftrightarrow k > \frac{\ln α}{\ln(1 + ε)}, $$ entonces$$ k_0 = \frac{\ln α}{\ln(1 + ε)} \sim \frac{\ln α}{ε} = \ln α · \frac{1}{ε}. \quad (ε \to 0^+) $$

Answer 2

Una más burdas pero más sencillo cálculo:

$\sqrt[k]{\alpha}<1+\epsilon$ es el mismo $\alpha < (1+\epsilon)^k$.

Desde entonces, por el buen viejo de Bernoulli, $(1+\epsilon)^k \gt 1+k\epsilon$, si $\alpha < 1+k\epsilon$ a continuación, $k$ es aceptable.

Por lo tanto $k > \dfrac{\alpha-1}{\epsilon}$ va a trabajar.

Por supuesto, esto no es tan buena como el obligado $\dfrac{\ln(\alpha)}{\epsilon}$.

Answer 3

Tomando logaritmos en ambos lados de las ecuaciones tenemos $$\ln(\alpha)\frac{1}{k}<\ln(1+\epsilon)$$ $$k>\frac{\ln(\alpha)}{\ln(1+\epsilon)}$$ Como $\epsilon\to 0$, podemos expandir $\ln(1+\epsilon)$ usando una expansión de taylor como $\ln(1+\epsilon)=\epsilon-\frac{\epsilon^2}{2}+\frac{\epsilon^3}{3}-...\approx \epsilon-\frac{\epsilon^2}{2}$ hasta segundo orden en $\epsilon$. Por lo tanto, $$k>\frac{\ln(\alpha)}{\epsilon-\frac{\epsilon^2}{2}}=\frac{\ln(\alpha)}{\epsilon(1-\frac{\epsilon}{2})}$$ Ahora, para los pequeños epsilon, también tenemos $(1-\epsilon/2)^{-1} \approx 1+\epsilon/2$. Por lo tanto, $$k>\frac{\ln(\alpha)}{\epsilon}(1+\frac{\epsilon}{2})$$