FAST QR DECOMPOSITION OF VANDERMONDE-LIKE MATRICES AND POLYNOMIAL LEAST-SQUARES APPROXIMATION

Let f and g be functions defined at the real and distinct nodes x(k), and consider the inner product (f,g): = SIGMA-k(m) = 1 f(x(k))g(x(k))w(k2) with positive weights w(k)2. The present paper discusses the computation of orthonormal polynomials pi-0, pi-1, ..., pi-n-1, n less-than-or-equal-to m, with respect to this inner product, and the use of these polynomials in a fast scheme for computing a QR decomposition of the transpose of Vandermonde-like matrices. Two methods are compared for computing the recurrence coefficients for the polynomials pi-j and their values at the nodes x(k): the Stieltjes procedure and a method in which an inverse eigenvalue problem for a tridiagonal symmetric matrix is solved by an algorithm proposed by Rutishauser, Gragg, and Harrod. The latter method is found to generally yield higher accuracy than the Stieltjes procedure if n is close to m, and roughly the same accuracy otherwise. This method for solving an inverse eigenvalue problem is applied in an algorithm for computing a QR decomposition of the transpose of n x m Vandermonde-like matrices. The algorithm so obtained requires only O(mn) arithmetic operations. This operation count compares favorably with the O(mn2) arithmetic operations necessary for the QR decomposition if the structure of Vandermonde-like matrices is ignored.