Accurate polynomial fitting and evaluation via Arnoldi

Given sample data points {(x_j, f_j)}^Nj=1, in [Brubeck, Nakatsukasa, and Trefethen, SIAM Review, 63 (2021), pp. 405-415], an Arnoldi-based procedure is proposed to accurately evaluate the best fitting polynomial, in the least squares sense, at new nodes {s_j }^Mj=1, based on the Vandermonde basis. Numerical tests indicated that this procedure can in general achieve high accuracy. The main purpose of this paper is to perform a forward rounding error analysis in finite precision. Our result establishes sensitivity factors regarding the accuracy of the algorithm, and provides a theoretical justification for why the algorithm works. For least-squares approximation on an interval, we propose a variant of this Arnoldi-based evaluation by using the Chebyshev polynomial basis. Numerical tests are reported to demonstrate our forward rounding error analysis.