Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I have a recurrence relation
$$P_{n} = A_{n} P_{n-1} - B_{n}P_{n-2}$$
with given $P_{0}$ and $P_{1}$.
Numerically, each $A_{n}$ and $B_{n}$ is calculated with some precision. The same applies to the $P_{0}$ and $P_{1}$. How can one estimates the error for the $n$-th term?
I think a good reference for this is Error Bounds for Linear Recurrence Relations by F. W. J. Olver (Mathematics of Computation, 1988).
At the most basic level, you can examine the sensitivity of $P_n$ to changes in $A_m,B_m$. So $$ P_n+\delta P_n = (A_n+\delta A_n)(P_{n-1}+\delta P_{n-1}) - (B_n + \delta B_n)(P_{n-2} + \delta P_{n-2}), $$ which to first order leads to the recurrences $$ P_n = A_nP_{n-1} - B_n P_{n-2}, $$ $$ \delta P_n = A_n \delta P_{n-1} - B_n \delta P_{n-2} + (\delta A_n P_{n-1} - \delta B_n P_{n-2}). $$ As you can see, the error terms satisfy the same recurrence relation, but with an extra inhomogeneous term that depends on the errors in $A_n,B_n$.
If you can find a general solution to the inhomogeneous recurrence relation, and also put a bound on the inhomogeneous term, that would give you a bound on the errors in $P_n$. This is analogous to how truncation error of a finite difference method for ODEs is converted into a bound on the method's global error. This also usually goes by the name of forward-mode sensitivity analysis.
One issue here is that often the errors in $A_n,B_n$ are not independent, and this analysis can be overly conservative; a similar issue can arise with using interval arithmetic to analyse roundoff errors in the recurrence relation. Olver's paper shows how to get rigorous bounds.
