¿Por qué esta secuencia converge a $\pi$?

Question

Más a nuestros amigos en codegolf.SÍ, le pedí a una pregunta acerca de los programas que parecía converger a $\pi$, pero en realidad no se hacer eso.

Una de las respuestas ( soktinpk) fue una solución que, aunque puedo ver muchas oportunidades para que los errores numéricos que conduce a una no-muy-$\pi$ resultado, no puedo entender por qué parece converger a $\pi$ en el primer lugar. El esquema es el siguiente:

• Elija un número de $h\ll1$. Tome $s_0=1, s_1=1$.

• Mientras que $s_n\ge 0$, calcular el siguiente término de la siguiente manera: $$s_n=2s_{n-1}-(1+h^2)s_{n-2}$$

• Cuando el procedimiento anterior termina, calcular el $p=2nh$, y he aquí, $p\approx\pi$!

Lo que provoca esto? Es un accidental de la serie de Taylor, involuntaria aproximación de una sinusoide (esa es mi suposición, tal vez sea algo como $s\approx \sin(n/h)$ resueltos por $s=0$), o lo hace de esta serie no tienen nada que ver con $\pi$ y es sólo un resultado de que la gente gritando MIRA ES $\Pi$ cada vez que ven 3.14...?

Answer 1

La ecuación característica de la relación de recurrencia $$s_{n} - 2s_{n-1} + (1+h^2)s_{n-2} = 0$$ es $\displaystyle\;\lambda^2 - 2\lambda + (1+h^2) = (\lambda-1)^2 + h^2 = 0\;$ que tiene raíces $1 \pm i h$. La solución general de la recurrencia de la relación que tiene la forma de $$s_n = A (1+ih)^n + B(1-ih)^n$$ Si uno imponer la condición inicial $s_0 = s_1 = 1$, uno encontrar $A = B = \frac12$. Esto lleva a

$$s_n = \frac12 ((1+ih)^n + (1-ih)^n)$$

Deje $\theta = \tan^{-1}(h)$, tenemos $$1 \pm ih = 1 \pm i\tan(\theta) = \frac{1}{\cos\theta}e^{\pm i\theta} = (1+\tan(\theta)^2)^{1/2} e^{i\theta}$$ Podemos simplificar $s_n$ $$s_n = \frac12 (1+h^2)^{n/2} \left( e^{\theta} + e^{- \theta} \right) = (1+h^2)^{n/2} \cos(n\theta)$$

Al menos para los pequeños $h$, la primera $n$ que hacen de $s_n < 0$ es uno de los que hacen de $n \theta > \frac{\pi}{2}$.
Es claro que esto es igual a $\left\lfloor \frac{\pi}{2\theta} \right\rfloor + 1$ y por lo tanto

$$2nh = 2h\left(\left\lfloor \frac{\pi}{2\tan^{-1}(h)} \right\rfloor + 1\right)$$

Para los pequeños $h$, $\tan^{-1}(h) \approx h$. Esto implica $n \approx \frac{\pi}{2h} \implies 2nh \approx \pi$.

En cierto sentido, la calculada $p \approx \pi$ porque para los pequeños $h$, $1+ih \approx e^{ih}$.