Multivariate polynomial interpolation with perturbed data

Given a finite set of points X in R^n, one may ask for polynomials p which belong to a subspace V and which attain given values at the points of X. We focus on subspaces V of R[x_1,...,x_n], generated by low order monomials. Such V werecomputed by the BM-algorithm, which is essentially based on an LU-decomposition. In this paper we present a new algorithm based on the numerical more stable QR-decomposition. If X contains only points perturbed by measurement or rounding errors, the homogeneous interpolation problem is replaced by the problem of finding (normalized) polynomials minimizing Sum(p(u)^2, u in X). We show that such polynomials can be found easily as byproduct in the QR-decomposition and present an errorbound showing the quality of the approximation.