How to make recursive computation of $I_n=\int_0^1 \frac{x^n}{x+\alpha}\,dx$ stable?

553 Views Asked by At

This is homework, so please only hints.

We see that the recurrence $$I_n=\frac{1}{n}-\alpha I_{n-1}$$ can be used to compute the value of the integral $I_n=\int_0^1 \frac{x^n}{x+\alpha}\,dx$ (starting with $I_0=\log\frac{1+\alpha}{\alpha}$), but the algorithm is unstable when $|\alpha |> 1$.

Note that we can write the recurrence as $$I_{n-1}=\frac{1}{\alpha n}-\frac{1}{\alpha} I_n$$How can this formula be used for stable computation when $|\alpha|>1$?

I'm rather puzzled at this point. Clearly I cannot directly use the "backwards" recurrence, since we only know $I_0$ at the beginning. Yet if I do any sort of messy algebraic manipulation, I could easily start from the original recurrence rather than this trivially inverted form.

Is this inverted form misleading? The question seems to indicate that one could quite directly use the form...

(Note: 'stable' means that floating-point errors won't multiply out of control when done by a computer)

1

There are 1 best solutions below

5
On BEST ANSWER

A broad hint: imagine generalizing the recurrence to $I_{k-1} = f(k)-\frac1\alpha I_k$. Then, ignoring all of the $f(i)$ terms that will accumulate along the way, can you figure out how $I_0$ depends on $I_n$ specifically? (Write $I_{n-2}$ in terms of $I_n$ and various $n$ terms, and you should start to see a pattern). Once you find this, you may be able to figure out the 'catch' behind calculating a value for $I_0$ based on a starting value $I_n$; if you want a more detailed hint than this, let me know and I'll give a more specific pointer.