Fast QR Decomposition of Vandermonde-Like Mmatrices and Polynomial Least Squares Approximation
Lothar Reichel · SIAM Journal on Matrix Analysis and Applications · 1991
Let f and g be functions defined at the real and distinct nodes $x_k $, and consider the inner product $( f,g ): = \sum_{k = 1}^m f ( x_k ) g ( x_k ) w_k^2 $ with positive weights $w_k^2 $. The present paper discusses the computation of orthonormal polynomials $\pi _0 ,\pi _1 , \cdots ,\pi _{n - 1} ,n\leqq 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 \times m$ Vandermonde-like matrices. The algorithm so obtained requires only $O ( mn )$ arithmetic operations. This operation count compares favorably with the $O( mn^2 )$ arithmetic operations necessary for the QR decomposition if the structure of Vandermonde-like matrices is ignored.