Acumulación de errores en un algoritmo numérico de aproximación para $y_n =\int_{0}^{1} \frac{x^n}{x+10} dx $

Question

Consideremos el problema de calcular la integral

$$y_n =\int_{0}^{1} \dfrac{x^n}{x+10} \mathrm{d}x $$ para un número entero positivo $n$ .

Observe que $$y_n + 10y_{n-1} = \int_{0}^{1} \dfrac{x^n +10x^{n-1}}{x+10} \mathrm{d}x = \int_{0}^{1} x^{n-1}\mathrm{d}x = \dfrac{1}{n}$$

y que el uso de esta relación en una recursión hacia adelante conduce a un procedimiento numéricamente inestable.

$(a)$ Deduzca una fórmula para calcular aproximadamente estas integrales a partir de la evaluación de $y_{n-1}$ dado $y_n$ .

$(b)$ Demuestre que para cualquier valor dado $\epsilon > 0$ y un número entero positivo $n_0$ existe un número entero $n_1 \geq n_0$ de tal manera que tomando $y_{n_1} = 0$ como valor inicial producirá evaluaciones integrales $y_n$ con un error absoluto menor que $\epsilon$ para todos $0 < n \leqslant n_0$ .

$(c)$ Explica por qué tu algoritmo es estable.

Esto es lo que tengo hasta ahora,

para la parte(a)

$$y_{n-1} = \dfrac{1}{10} \left(\dfrac{1}{n} - y_n\right)$$

y para la parte $(c)$

El algoritmo es estable porque la magnitud de los errores de redondeo se divide por 10 cada vez que se aplica la recursión.

Realmente no sé cómo empezar con la prueba de la parte $(b)$ Cualquier sugerencia y ayuda será apreciada.

Answer 1

Cuando $y_{n_1} = 0$ , $y_{n_1-1} = \dfrac{1}{10n_1} + \alpha_1$ , donde $\alpha_n$ es el valor del error de redondeo en cada paso (no necesariamente el mismo para cada paso):

$y_{n_1-2} = \dfrac{1}{10} \left(\dfrac{1}{n_1} - y_{n_1 - 1}\right)$

nos encontramos con que:

$y_{n_1-2} = \dfrac{1}{10} \left(\dfrac{1}{n_1 - 1} - \left(\dfrac{1}{10n_1} + \alpha_1\right)\right) + \alpha_2 = \dfrac{1}{10(n_1 - 1)} - \dfrac{1}{100n_1} - \dfrac{\alpha_1}{100} + \alpha_2$

Repitiendo, obtenemos:

$y_{n_1-3} = \dfrac{1}{10} \left(\dfrac{1}{n_1 - 2} - y_{n_1 - 2}\right) + \alpha_3 = \dfrac{1}{10(n_1 - 2)} - \dfrac{1}{100(n_1 - 1)} - \dfrac{1}{1000n_1} - \dfrac{\alpha_1}{1000} -\dfrac{\alpha_2}{100} + \alpha_3.$

Como dices, la magnitud del error de redondeo del paso anterior se divide por 10 cada vez que se aplica la recursión, y forma una serie geométrica. Para un determinado $n_1$ la peor magnitud del error en cualquier caso $n_0 \geq 1, n_1 \geq 2, n_1 > n_0$ está limitada por:

$$|\alpha_{max}|\sum_{k=0}^{n_1 - n_0 - 1} \left(\dfrac{1}{10}\right)^k= |\alpha|\dfrac{1 - {\left(\dfrac{1}{10}\right)}^{n_1 - n_0}}{1 - \dfrac{1}{10}} = \frac{10|\alpha|}{9}(1 - 10^{n_0 - n_1}).$$

Para cualquier $n_0$ la magnitud del error de redondeo $\alpha$ en cualquier paso está ciertamente limitado por $y_{n_1 - 1} = \frac{1}{10n_1}$ por lo que se puede sustituir por $\alpha$ en la ecuación anterior. El problema entonces es demostrar que $\exists n_1$ para cualquier $\epsilon \in \mathbb{R}, n_0 \in \mathbb{N}, n_0 < n_1$ tal que $|\frac{1}{9n_1}(1 - 10^{n_0 - n_1})| < \epsilon$ .

Answer 2

La recursión puede ser numéricamente inestable debido a las repetidas multiplicaciones por $10$ . Sin embargo, si retrasamos la parte numérica hasta que hayamos utilizado suficiente matemática exacta, obtendremos una bonita serie para $y_n$ que converge rápidamente.

Si multiplicamos ambos lados de la recursión por $(-10)^{-n}$ obtenemos $$ (-10)^{-n}y_n-(-10)^{-n+1}y_{n-1}=\frac1{n(-10)^n}\tag{1} $$ Desde $y_0=\log(11/10)$ obtenemos $$ \begin{align} (-10)^{-n}y_n &=\log(11/10)+\sum_{k=1}^n\frac1{k(-10)^k}\\ &=-\sum_{k=n+1}^\infty\frac1{k(-10)^k}\tag{2} \end{align} $$ porque $\sum\limits_{k=1}^\infty\frac1{k(-10)^k}=-\log(11/10)$ .

Multiplicando por $10^n$ y la reindexación da como resultado $$ \begin{align} y_n &=-\sum_{k=n+1}^\infty\frac{(-10)^{n-k}}{k}\\ &=-\sum_{k=1}^\infty\frac{(-10)^{-k}}{n+k}\tag{3} \end{align} $$ y $(3)$ converge con bastante rapidez (un poco más de un dígito por término).

---

Otro enfoque:

$$ \begin{align} \int_0^1\frac{x^n}{x+10}\,\mathrm{d}x &=\frac1{10}\int_0^1\left(x^n-\frac{x^{n+1}}{10}+\frac{x^{n+2}}{10^2}-\frac{x^{n+3}}{10^3}+\dots\right)\,\mathrm{d}x\\ &=\frac1{10}\sum_{k=0}^\infty\frac{(-1)^k}{(n+k+1)10^k}\tag{4} \end{align} $$ que es la misma serie que $(3)$ después de la reindexación.

---

A partir de su recursión $$ \begin{align} y_n &=\frac1{10}\left(\frac1{n+1}-y_{n+1}\right)\\ &=\frac1{10}\left(\frac1{n+1}-\frac1{10}\left(\frac1{n+2}-y_{n+2}\right)\right)\\ &=\frac1{10}\left(\frac1{n+1}-\frac1{10}\left(\frac1{n+2}-\frac1{10}\left(\frac1{n+3}-y_{n+3}\right)\right)\right)\\[9pt] &\dots\\[9pt] &=\frac1{10}\frac1{n+1}-\frac1{10^2}\frac1{n+2}+\frac1{10^3}\frac1{n+3}-\dots+\frac{(-1)^{k-1}}{10^k}\left(\frac1{n+k}-y_{n+k}\right) \end{align} $$ lo que nos lleva de nuevo a la misma serie una vez que observamos que $y_n\le\frac1{10(n+1)}$ para todos $n$ .

Answer 3

$\displaystyle{y_{n} =\int_{0}^{1}{x^{n} \over x + 10}\,{\rm d}x:\quad ?}$

Con $z \in {\mathbb C},\quad \left\vert z\right\vert < 1/10$ : \begin {align} \sum_ {n = 0}^{ \infty }z^{n}y_{n} &= \int_ {0}^{1}{1 \over 1 - zx},{1 \over x + 10}\,{ \rm d}x = -\,{1 \over z} \int_ {0}^{1}{1 \over x - 1/z},{1 \over x + 10}\,{ \rm d}x \\ [3mm]&= -\,{1 \over z}\,{1 \over 10 + 1/z} \int_ {0}^{1} \left ({1 \over x - 1/z} - {1 \over x + 10} \right ){ \rm d}x = -\,{1 \over z + 10} \left.\ln\left (x - 1/z \over x + 10 \right ) \right\vert_ {0}^{1} \\ [3mm]&= -\,{1 \over 10z + 1} \left [ \ln\left (1 - 1/z \over 11 \right ) - \ln\left (-1/z \over 10 \right ) \right ] = \color {#ff0000}{ \large % -\,{ \ln\left (10/11 \right ) \over 10z + 1} - { \ln\left (1 - z \right ) \over 10z + 1}} \end {align}

Ahora, expande el lado derecho en potencias de $z$ . Los coeficientes son $\left\{y_{n}\right\}$ .

$\color{#0000ff}{\large\mbox{We can easily see that the "offending terms" will be the}\ \underline{\rm powers\ of\ \ 10}\,.}$