Practical rational interpolation of exact and inexact data : theory and algorithms
Faculty of Sciences. Mathematics and Computer Science
Antwerpen :Universiteit Antwerpen, Faculteit Wetenschappen, Departement Wiskunde-Informatica, 2008
University of Antwerp
The central topic of this thesis is rational interpolation of exact and inexact data. In the first part the numerical implementation of univariate rational interpolation with asymptotic information is considered. Hence infinity is admitted in both the independent variable as well as in the function value. First the problem of univariate rational interpolation including infinite function values, but without the point at infinity is studied in Chapter 1 in order to understand the possible degeneracies that are connected with the classical rational interpolation problem. In Chapter 2 a specific representation for interpolating rational functions is considered: the barycentric form. Although the barycentric form has a remarkable property which makes it attractive for numerical implementation, namely exact interpolation even in the presence of rounding errors, we have shown that, due to catastrophic cancellation, the evaluation of the barycentric form may give very inaccurate results when evaluated outside the interpolation interval. Hence the barycentric form is not suitable for interpolation at infinity. For that reason interpolating continued fractions are considered in Chapter 3. First Thiele continued fractions are introduced, which form the basis for the more advanced algorithm due to Werner. This algorithm is one of the few algorithms for rational interpolation for which a stability analysis exists. If a special pivoting strategy is incorporated, then it has been proven to be backward stable. With this pivoting strategy, it also allows for poles to be prescribed, but in its standard form, interpolation at infinity is not supported. In Chapter 4 the interpolation condition at infinity is added. First a condition to detect degeneracy for the point at infinity is given if the points are ordered such that all finite data come first and the point at infinity is last. For this ordering of the data, we have shown how the algorithm of Werner can be modified to interpolate also at infinity. In the last Chapter of the first part, other algorithms for rational interpolation which are more or less related to Werner's algorithm have been reviewed. These techniques are more suitable in a symbolic environment rather than a numerical one. In the second part, asymptotic behavior is discarded, but the problem setting of the first part is generalized considerably by considering the multivariate case and allowing uncertainty in the function values. After all, in many applications observations are often prone to imprecise measurements. The conventional way to find a rational function approximating such data with noise is by means of a rational least squares approximation. We have proposed a new approach. In Chapter 6 the new problem is formulated, immediately for the multivariate case. It is assumed that the uncertainty in the independent variables is negligible and that for each observation an uncertainty interval can be given which contains the (unknown) exact value. To approximate such data we look for rational functions which intersect all uncertainty intervals. We have shown that this problem can be solved by a quadratic programming problem with a strictly convex objective function, yielding a unique rational function which intersects all uncertainty intervals and satisfies some additional properties. Compared to rational least squares approximation which is inherently a nonlinear optimization problem where the objective function may have many local minima, this makes the new approach attractive. Since the problem statement is independent of the number of variables, it is truly multivariate. In Chapter 7, the technique developed in Chapter 6 is applied to several benchmark problems. The obtained results indicate that the method scales very well to higher dimensional problems. Chapter 8 is a case study, where the design of multidimensional recursive filters is considered, a technology which is required in many diverse areas, including image processing, video signal filtering, tomography and different grid-based methods in scientific computing. It is shown that reformulation of the problem using uncertainty intervals overcomes many of the classical drawbacks.