Error accumulation in an approximating numerical algorithm for $y_n =\int_{0}^{1} \frac{x^n}{x+10} dx $

Question

Consider the problem of calculating the integral

$$y_n =\int_{0}^{1} \dfrac{x^n}{x+10} \mathrm{d}x $$ for a positive integer $n$.

Observe that $$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}$$

and that using this relationship in a forward recursion leads to a numerically unstable procedure.

$(a)$ Derive a formula for approximately computing these integrals based on evaluating $y_{n-1}$ given $y_n$.

$(b)$ Show that for any given value $\epsilon > 0$ and positive integer $n_0$, there exists an integer $n_1 \geq n_0$ such that taking $y_{n_1} = 0$ as a starting value will produce integral evaluations $y_n$ with an absolute error smaller than $\epsilon$ for all $0 < n \leqslant n_0$.

$(c)$ Explain why your algorithm is stable.

Here is what I have so far,

for part(a)

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

and for part $(c)$

The algorithm is stable because the magnitude of roundoff errors gets divided by 10 each time the recursion is applied.

I really don't know how to start on the proof for part $(b)$, any hints and help would be appreciated.

Answer 1

When $y_{n_1} = 0$, $y_{n_1-1} = \dfrac{1}{10n_1} + \alpha_1$, where $\alpha_n$ is the value of the roundoff error at each step (not necessarily the same for each step.) Plugging this back into the formula:

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

we get:

$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$

Repeating, we get:

$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.$

As you say, the magnitude of the roundoff error from the previous step is divided by 10 each time the recursion is applied, and forms a geometric series. For a given $n_1$, the worst case magnitude of the error at any $n_0 \geq 1, n_1 \geq 2, n_1 > n_0$ is bounded by:

$$|\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}).$$

For any $n_0$, the magnitude of the roundoff error $\alpha$ at any step is certainly bounded by $y_{n_1 - 1} = \frac{1}{10n_1}$, so this can be substituted for $\alpha$ in the above equation. The problem then is to show that $\exists n_1$ for any $\epsilon \in \mathbb{R}, n_0 \in \mathbb{N}, n_0 < n_1$ such that $|\frac{1}{9n_1}(1 - 10^{n_0 - n_1})| < \epsilon$.

Answer 2

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

With $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}

Now, expands the right hand side in powers of $z$. The coefficients are $\left\{y_{n}\right\}$.

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

Answer 3

The recursion may be numerically unstable because of repeated multiplications by $10$. However, if we delay the numerical part until we've used enough exact math, we get a nice series for $y_n$ that converges quickly.

If we multiply both sides of the recursion by $(-10)^{-n}$, we get $$ (-10)^{-n}y_n-(-10)^{-n+1}y_{n-1}=\frac1{n(-10)^n}\tag{1} $$ Since $y_0=\log(11/10)$, we get $$ \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} $$ because $\sum\limits_{k=1}^\infty\frac1{k(-10)^k}=-\log(11/10)$.

Multiplying by $10^n$ and reindexing yields $$ \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} $$ and $(3)$ converges pretty rapidly (a bit over a digit a term).

---

Another Approach:

$$ \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} $$ which is the same series as $(3)$ after reindexing.

---

Starting from your recursion $$ \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} $$ which again leads to the same series once we notice that $y_n\le\frac1{10(n+1)}$ for all $n$.