Recursive definition of the error

149 Views Asked by At

Given the definition of

$I_n:=\frac{1}{e}\int_0^1 x^ne^x$
for $n=0,1,2,...$

there is a recurrence relation:

$I_n=1-nI_{n-1} $ for $n=1,2,...$ and $I_0=\frac{e-1}{e}$

I've got to show that the recursive forrmula of the error (difference of the target value $I_n$ and the computed value $\tilde I_n$) is:

(1) $ |\tilde I_n-I_n| \leq 3\epsilon+n(1+2\epsilon)|\tilde I_{n-1}-I_{n-1}|$, where $\epsilon=\frac{fl(x)-x}{x}$.

Well I thoght of two ways that leads me to nowhere. First way was: I know that $\tilde I_n=fl(I_n)=fl(1-nI_{n-1})=1-nfl(I_{n-1})$. so the absolute error would be $|I_n-fl(I_n)|=|1-nI_{n-1}-(1-nfl(I_{n-1}))|=n|fl(I_{n-1})-I_{n-1}|=n|\tilde I_{n-1}-I_{n-1}|$, which has to be false because it is not equal (1).

Second way was kind of thinking:

$\tilde I_n=\widetilde{1-nI_{n-1}}\stackrel{(*1)}{=}(1-(nI_{n-1})(1+\epsilon_1))(1+\epsilon_2)=1-\epsilon_1\epsilon_2nI_{n-1}-\epsilon_1nI_{n-1}-\epsilon_2nI_{n-1}-nI_{n-1}+\epsilon_2$

$\Rightarrow|\tilde I_n-I_n|=|\tilde I_n-(1-nI_{n-1})|=|-\epsilon_1\epsilon_2nI_{n-1}-\epsilon_1nI_{n-1}-\epsilon_2nI_{n-1}+\epsilon_2| \\ \le|-(\epsilon_1\epsilon_2+\epsilon_1+\epsilon_2)nI_{n-1}+\epsilon_2| \stackrel{(*2)}{\le}|3\epsilon+\epsilon|=4\epsilon$

(*1) as there are two operations

(*2) as $\epsilon_1,\epsilon_2 \le \epsilon \le 1$

and as $0\leq I_{n-1}\leq\frac{1}{n}$

but again I do'n't see how to come close to (1)... Does anyone know it better?

1

There are 1 best solutions below

1
On BEST ANSWER

I don't know how to get the inequality you got. Maybe there's some additional assumption. Here is what I got.

We have $$\tag{1} \tilde{I}_n:=\mathrm{fl}(I_n)=[1-n\tilde{I}_{n-1}(1+\delta_1)](1+\delta_2), \quad |\delta_i|\leq\epsilon. $$ So $$ \begin{split} \tilde{I}_n-I_n &= [1-n\tilde{I}_{n-1}(1+\delta_1)](1+\delta_2)-(1-nI_{n-1}) \\ &= \delta_2-n(\tilde{I}_{n-1}-I_{n-1})-\delta_1n\tilde{I}_{n-1} -\delta_2n\tilde{I}_{n-1}-\delta_1\delta_2n\tilde{I}_{n-1} \end{split} $$ and using (1) this gives $$\tag{2} |\tilde{I}_n-I_n|\leq\epsilon + n|\tilde{I}_{n-1}-I_{n-1}|+3n\epsilon|\tilde{I}_{n-1}|. $$ Since $0\leq I_{n-1}<I_0<1$, we have $$ |\tilde{I}_{n-1}|\leq|\tilde{I}_{n-1}-I_{n-1}|+|I_{n-1}| \leq|\tilde{I}_{n-1}-I_{n-1}|+1. $$ Plugging this to (2) results in $$ |\tilde{I}_n-I_n| \leq(1+3n)\epsilon+4n\epsilon|\tilde{I}_{n-1}-I_{n-1}|. $$

It is not exactly same as what you have but both inequalities show the important fact that this way of computing $I_n$ amplifies the rounding errors so that $$ |\tilde{I}_n-I_n|\leq O(n!)\epsilon|\tilde{I}_0-I_0|. $$