Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following question was asked on MSE, but might be more suitable here.

Assume there is a rational function $$ f:x\mapsto \frac{\sum_{i=0}^m{a_ix^i}}{1+\sum_{j=1}^n{b_jx^j}} $$ of type $(m,n)$ with real coefficients and without poles on the interval $[0,1]$. Further assume that there is a sequence $(f_n)_n$ of not-necessarily rational functions that converge to $f$ uniformly on $[0,1]$.

For some choice of evaluation sites $x_k\in[0,1]$ we define real numbers $a_i^{(n)}$, $b_j^{(n)}$ as the coefficients of the rational function that interpolate between the $m+n+1$ points $(x_k,f^n(x_k))$, i.e. $$ f_n(x_k)=\frac{\sum_{i=0}^m{a_i^{(n)}x_k^i}}{1+\sum_{j=1}^n{b^{(n)}_jx_k^j}}. $$

Question:

  1. How can the errors $\left|a_i-a_i^{(n)}\right|$ and $\left|b_j-b_j^{(n)}\right|$ be controlled in terms of $\sup_{0\leqslant x\leqslant 1}\left|f(x)-f_n(x)\right|$?

  2. If the coefficients $a_i$, $b_j$ are integers, is there a more efficient way of recovering them from the approximants $f_n$ than computing an approximating rational function with real coefficients and rounding to the nearest integers, or doing a brute force search for the rational function with integer coefficients that minimizes the distance to $f_n$?

In my application, $f$ is the cumulative distribution function of a random variable and $f_n$ are empirical distribution functions based on $n$ simulated realisations of this variable. In a numerical example of type $(4,3)$ I need $\left\|f-f_n\right\|_\infty<10^{-6}$ to obtain interpolating rational functions (based on eight equidistant evaluation sites) with coefficients within $0.5$ of the true ones. By Donsker's theorem this corresponds to about $10^{12}$ realisations which is of course not feasible.

Thanks.

EDIT: As requested by Manfred Weis, I add a few more details about the concrete problem I would like to solve. I have a random variable of which I know a priori that its cumulative distribution function (CDF) is rational of type $(m,n)$. My goal is to determine the coefficients of the CDF based on simulations. My strategy is to compute the empirical distribution functions (eCDF's) which are known to converge uniformly to the true CDF, approximate those by rational functions and to use the coefficients of the approximate function as approximations for the coefficients of the true CDF. I am asking for quantitative error bounds for this method or pointers to more efficient procedures.

share|improve this question
    
could you please provide some more information about the problem you have to solve? There are numerically stable methods for rational interpolation, so I would like to understand how the sequence of approximating functions comes into play. –  Manfred Weis Aug 23 '13 at 17:16
    
Thank you for your comment @ManfredWeis. I edited the question. –  Eckhard Aug 23 '13 at 18:51
    
your edit has provided some information, but a lot of questions still remain: to me it appears that the actual problem is to fit a rational function through a set of (x,y) pairs in a way that minimizes the total error in some norm. Am I right that your questions are motivated by an idea on how to solve that problem? Especially the question concerning integer coefficients seems unrelated to your problem. It would certainly improve things if you would make explicit what kind of problem you have to solve and what your ideas for a solution are. –  Manfred Weis Aug 25 '13 at 10:17
    
The aim is to approximate the coefficients of a function which is known a priori to be rational with integer coefficients. The available information is encoded by a sequence of approximating non-rational functions. I don't know what additional information I can provide. –  Eckhard Aug 25 '13 at 16:18
    
That information is sufficient to understand your needs; maybe the problem would receive more attention if the restriction of the parameters to integers appears in the headline. One way of getting better estimates for the parameters would be to construct for each parameter a sequence of points (1.0/m,a_i[m]), where m stands for the m-th interpolation and a_i[m] is the value of parameter a_i in that interpolation; interpolating that sequence with a suitable function, e.g. quadratic polymial, and evaluating it at 0 should give better estimates for the limit. But I guess you have already tried it –  Manfred Weis Aug 25 '13 at 18:26
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.