Demostrar que la iteración $x_{i + 1} = x_i - \log x_i$ es sublineal.

Question

Define una recurrencia como: $$x_0 = n, x_{i + 1} = x_i - \log x_i, \forall i \geq 0.$$ Dejemos que $N_n$ sea tal que $x_{N_n} < 1$ . ¿Es posible demostrar que $N_n \in o(n)$ ?

Algunas reflexiones: si $x_{i + 1} = x_i - f(x_i)$ y $f$ es constante, entonces $N_n = \frac{n}{f(1)}$ y por tanto no es sublineal. Si $f$ es $\Omega(n)$ entonces $N_n$ es constante y, por tanto, trivialmente sublineal. Es $f(x) = \log x$ suficiente para hacer $N_n$ ¿Sublineal?

---

Edición: Como se ha señalado en los comentarios, los criterios $x_{N_n} < 1$ nunca se puede cumplir para esta pregunta. La pregunta correcta debería ser

Dejemos que $N_n$ sea el menor número entero tal que $x_{N_n} < 10$ . ¿Es posible demostrar que $N_n \in o(n)$ ?

Answer 1

Es interesante notar que esto parece un esquema iterativo de Newton para resolver la ecuación $f(x)=a$ .

Como no sabemos qué es $f(x)$ , escribiendo $$x_{n+1}=x_n-\frac{f(x_n)-a}{f'(x_n)}$$ tenemos $$\frac{f(x)-a}{f'(x)}=\log(x)\implies \frac{f'(x)}{f(x)-a}=\frac 1{\log(x)}$$ $$\implies\log(f(x)-a)=\text{li}(x)+c\implies \color{blue}{f(x)=a+c\,e^{\text{li}(x)}}$$ donde $\text{li}(x)$ es la función integral logarítmica.

La función $e^{\text{li}(x)}$ es, por supuesto, siempre positivo y es igual a $0$ cuando $x=1$ pero, en este punto, es discontinuo.

En $x=1^-$ tenemos $$e^{\text{li}(x)}=-e^{\gamma } (x-1)-\frac{1}{2} e^{\gamma } (x-1)^2+O\left((x-1)^3\right)$$ mientras que alrededor de $x=1^+$ , $$e^{\text{li}(x)}=e^{\gamma } (x-1)+\frac{1}{2} e^{\gamma } (x-1)^2+O\left((x-1)^3\right)$$

Como es Newton, el proceso es cuadrático.

A modo de ejemplo, se trata de $a=123456$ , $c=\pi$ y utilizando $x_0=30$ tenemos los siguientes iterados $$\left( \begin{array}{cc} n & x_n \\ 0 & 30.000000000000000000000000000000000000000000000000 \\ 1 & \color{red}{2}6.894152524358982809170572349163498313534833470925 \\ 2 & \color{red}{2}4.325223169265492626304969903408926811220213329449 \\ 3 & \color{red}{22.}681722534270713557158529795786301254378897174602 \\ 4 & \color{red}{22.}108470739953112533158686496921157728291987229732 \\ 5 & \color{red}{22.051}702027826858474857702973272665751388334724225 \\ 6 & \color{red}{22.0511991}43990547095115344666363810856986277372042 \\ 7 & \color{red}{22.051199104963862}951102891406188800145947352942244 \\ 8 & \color{red}{22.0511991049638627160819846994044}13283687608959958 \\ 9 & \color{red}{22.051199104963862716081984699404404760615124872753} \end{array} \right)$$ lo que es típico de un método de segundo orden.

Answer 2

Las otras respuestas se refieren a la velocidad de convergencia a $1$ que creo que no es su pregunta.

Quiero revertir el problema. Escriba a $f(x) = x-\log(x)$ . Sea $M>1$ y $(u_n)$ sea la secuencia definida por:

$$u_0 = M \text{ and } u_{n+1} = g(u_n),$$

donde $g : [1, +\infty) \to [1, +\infty)$ es la biyección inversa a $f$ . Entonces $x_i = g(x_{i+1})$ para que $n = x_0 = g^{(N_n)} (x_{N_n}) < g^{(N_n)} (M) = u_{N_n}$ y $n = x_0 = g^{(N_n-1)} (x_{N_n-1}) \geq g^{(N_n-1)} (M) = u_{N_n-1}$ . Tenga en cuenta también que

$$\lim_{n \to + \infty} \frac{f(n)}{n} = 1 \text{ so } \lim_{n \to + \infty} \frac{g(n)}{n} = \lim_{n \to + \infty} \frac{f(g(n))}{g(n)} \frac{g(n)}{n} = 1.$$

Desde $u$ es creciente, obtenemos que $N_n = \inf \{k \geq 0 : \ u_k > n\}$ . Esto es conveniente, ya que hemos trasladado el problema inicial al estudio de la tasa de crecimiento de una única secuencia.

Dejemos que $L>0$ . Para $x \geq M$ tenemos $f(x) = x-\log(x) \leq x-\log(M)$ para que $x \leq g(x-\log(M))$ De ahí que $g(x) \geq x+\log(M)$ . De ello se desprende que $u_n \geq M + n \log(M)$ para que $\lim_{n \to + \infty} u_n = +\infty$ .

Ahora, déjame probar que $u_n$ crece de forma superlineal. Sea $L>0$ . Sea $n_0$ sea tal que $u_n \geq 10^L$ para todos $n \geq n_0$ . Con el mismo argumento anterior, $g(x) \geq x+L$ para todos $x \geq 10^L$ . Por lo tanto, para todos los $n \geq n_0$ ,

$$u_n = u_{n_0} + (u_n-u_{n_0}) \geq u_{n_0} + (n-n_0)L.$$

De ello se desprende que $\liminf_{n \to +\infty} u_n/n \geq L$ . Dado que esto es válido para todos los $L> 0$ Finalmente conseguimos

$$\lim_{n \to + \infty} \frac{u_n}{n} = +\infty.$$

Especialización en la subsecuencia $(N_n)$ que también converge a $+\infty$ ,

$$\lim_{n \to + \infty} \frac{u_{N_n}}{N_n} = +\infty.$$

Pero $n < u_{N_n} \leq g(n)$ Así que

$$\lim_{n \to + \infty} \frac{g(n)}{N_n} = +\infty.$$

Por último, dado que $g(n) \sim n$ obtenemos

$$\lim_{n \to + \infty} \frac{N_n}{n} = 0,$$

es decir, $N_n = o(n)$ .

El razonamiento anterior puede adaptarse a muchas funciones en lugar de $\log$ aunque hay que comprobar muchos detalles. Creo que el resultado debería ser válido para la recursión $x_{i+1} = x_i-h(x_i)$ , donde $\inf h>0$ y $\lim_{x \to +\infty} h(x) = +\infty$ así como $\lim_{x \to +\infty} h(x)/x = 0$ pero eso no es del todo trivial.

Answer 3

Este es un enfoque que utiliza series de potencia. Definir la secuencia $$ x_i := 1+y_i, \tag{1}$$ y la función $$ g(x) := x - \log(1+x). \tag{2}$$ Utilizando la recursión tenemos $$ y_{i+1} = g(y_i). \tag{3}$$ De la experiencia anterior con estas iteraciones, como método de Newton, esperamos que $$ f(x^2) = g(f(x)) \tag{4}$$ para alguna función expresada como una serie de potencias $$ f(x) := a_1\,x + a_2\,x^2 + a_3\,x^3 + \dots \tag{5}$$ donde resolvemos los "coeficientes indeterminados" $\,a_i\,$ de uno en uno utilizando la ecuación $(4).$ El resultado de los cálculos es que debemos tener $$ f(x) := 2x + 4/3x^2 + 8/9x^3 + 112/135x^4 + 76/135x^5 + \dots. \tag{6}$$ Así, $$ y_0 = n-1 = f(t_0), \tag{7}$$ para algunos $\,t_0\,$ y $$ y_n = f(t_0^{\,2^n}) \approx 2t_0^{\,2^n} \tag{8}$$ lo que implica $$ x_n \approx 1+2t_0^{\,2^n}. \tag{9}$$ La convergencia de $\,x_n\,$ a $1$ se llama "cuadrática" o de "segundo orden".