Recurrencia de Muller: límite

Question

En cuenta de Kahan de la recurrencia de Muller (p.16): $x_{n+1} = E(x_n, x_{n-1})$ para la función $$ E(y, z) = 108 - \frac{815-\frac{1500}{z}}{y}, $$ utiliza el polinomio característico para la recurrencia para deducir la forma cerrada: $$ x_n = \frac{\alpha 3^{n+1} + \beta 5^{n+1} + \gamma 100^{n+1}}{\alpha 3^{n} + \beta 5^{n} + \gamma 100^{n}}. $$ Si $x_0=4, x_1=4.25$ exactamente, entonces podemos elegir $\alpha=\beta=1, \gamma=0$. Pero, si hay algún redondeo numérico en un cálculo numérico de los $x_n$, entonces la forma cerrada se convierte ("al menos inicialmente"), $$ x_n = \frac{3^{n+1} + 5^{n+1} + \gamma_n 100^{n+1}}{3^{n} + 5^{n} + \gamma_n 100^{n}}\\ = 100 - \frac{95+97(3/5)^n}{20^n\gamma_n+1+(3/5)^n} $$ donde $\gamma_n$ es pequeño.

No puedo deducir la última igualdad, y no veo cómo esto cambia el límite (a medida que $n\rightarrow \infty$) a 100 en lugar de a 5. Además, ¿qué justifica la elección de $\alpha$, $\beta$, $\gamma$ arriba entre las presumiblemente infinitas opciones?

Answer 1

$\alpha = 1, \beta = 1, \gamma = 0$ da la solución exacta desde los valores iniciales. Para la configuración del error de redondeo están ligeramente perturbados; todavía tenemos $\alpha \approx 1, \beta \approx 1,$ pero $\gamma$ tiene el orden del epsilon de la máquina $\gamma \approx \epsilon$. Para computar la forma de Kahan desde

$$x_n = \frac{3^{n+1} + 5^{n+1} + \gamma_n 100^{n+1}}{3^{n} + 5^{n} + \gamma_n 100^{n}}$$ primero haga algunas manipulaciones algebraicas con el numerador $$3^{n+1} + 5^{n+1} + \gamma_n 100^{n+1}= 3\cdot 3^{n} + 5\cdot 5^{n} + 100\gamma_n 100^{n}$$ $$=(100-97)\cdot 3^{n} + (100-95)\cdot 5^{n} + 100\gamma_n 100^{n}$$ $$=100(3^{n} + 5^{n} + \gamma_n 100^{n})-97\cdot 3^{n} -95\cdot 5^{n} $$ entonces el valor intermedio para $x_n$ es $$x_n = 100 - \frac{97\cdot 3^n + 95\cdot 5^n}{3^n + 5^n + \gamma_n 100^n}$$ ahora divida por $5^n$ y obtenga $$x_n = 100 - \frac{ 95+ 97\cdot (3/5)^n }{ 20^n \gamma_n+ 1 +(3/5)^n }$$ Ahora es claro que el límite es $\lim_\limits{n\rightarrow \infty} x_n = 100$ para $\gamma_n \ne 0$ y $100-95 = 5$ para $\gamma_n = 0$

La diferencia principal entre exacto (error=0) y error de redondeo es el término de error creciente $20^n \gamma_n$. Para cálculos de precisión doble con un $\gamma_n$ constante $\gamma_n = \epsilon = 2.22\times 10^{-16}$ tienes $20^{15}\epsilon \approx 7275.9576$ y $20^{20}\epsilon \approx 23283064365.4$