Hybrid Rational Function Approximation

Computations of linearized equations (3) in the presence of roundoff errors may lead to the following interesting phenomenon. Suppose that the unknown function f(x) is a rational function which is continuous in [x₀,x_m+n]. Let the actual degrees of the numerator and the denominator polynomials of f(x) be m-d and n-d, respectively, for a positive d. That is $f(x)=\bar{r}_{m-d,n-d}(x)=\bar{p}_{m-d}(x)/\bar{q}_{n-d}(x)$. Here, we consider rational function $\bar{r}_{m,n}(x)$ interpolating Dsuch as $f_i=f(x_i),\ i=0,\cdots,m+n$. There are a lot of rational functions passing the data set D but have different degrees. There are any polynomials $\bar{g}(x)$ whose degree is d such as $\bar{r}_{m,n}(x)=(\bar{g}(x)\bar{p}_{m-d}(x))/(\bar{g}(x)\bar{q}_{n-d}(x))$. Thus, linearized equations (3) have no unique solution. However, in the floating number computations, because of the presence of roundoff errors the numerical solution will produce the pair of polynomials P(x) and Q(x) of degrees m and n, respectively. The numerical rational interpolation P(x)/Q(x) should approximate one of $\bar{r}_{m,n}$. That is P(x)/Q(x)=(g_p(x)p_m-d(x))/(g_q(x)q_n-d(x)). In algebraic computations we can remove $\bar{g}(x)$ from rational function $\bar{r}_{m,n}(x)$ by GCD computations. However in floating computations the coefficients of P(x)/Q(x)are slightly different from $\bar{r}_{m,n}(x)$. Thus, polynomials g_p(x) and g_q(x) remain in the numerical rational interpolation. Furthermore, it may occur that for some zwe have simultaneously $Q(z)=0,~P(z) \neq 0$, and then the computed ratio P(x)/Q(x)will be a very poor approximation to f(x) at z and near z. In this case, a natural way to improve the approximation is to compute g(x), an approximate-GCD of P(x)and Q(x), then compute the symbolic quotients p(x)=P(x)/g(x) and q(x)=Q(x)/g(x), and finally output p(x)/q(x) as an improved hybrid rational interpolation to f(x). We call these procedures Hybrid Rational Function Approximation and show the algorithm as follows:

Algorithm 2.1 (HRFA)  
Input: data set D and parameter $\epsilon$
Output: hybrid rational interpolation p(x)/q(x)
Method:

1.

Compute rational interpolation P(x)/Q(x) to interpolate D.

2.

Obtain the approximate-GCD g(x) of P(x) and Q(x) using the algorithm by Sasaki and Noda.

3.

$p(x)=\mbox{quo}(P(x)/g(x))$ and $q(x)=\mbox{quo}(Q(x)/g(x))$, where $\mbox{quo}$ is a quotient obtained by polynomial division.

 

Any algorithms for (non-unique) approximate-GCD and for polynomial division are available. Several methods of calculating approximate-GCDs have been proposed other than Schönhage [7], Sasaki and Noda [11]. They use different norms for the definition of approximate-GCDs, i.e. L₁ norm (c.f. Pan[9], Hribernig and Stetter[8]), L₂ norm (c.f. Corless, Gianni, Trager and Watt[6], Karmarkar and Lakshman[5]) or norms estimated in a domain (c.f. Sederberg and Chang[10]). For further discussions to establish the error estimate of HRFA, we use the approximate-GCD proposed by Hribernig and Stetter.