5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.