Optimal Sampling for Function Approximation

This thesis project focuses on algorithms that generate good sampling points for function approximation. In one dimension, polynomial interpolation using equispaced points is unstable, with high Oscillations near the endpoints of the interpolated interval. On the other hand, Chebyshev nodes provide both stable and highly accurate points for polynomial interpolation. In higher dimensions, optimal sampling points are unknown. This project addresses this problem by finding algorithms that are robust in various domains for polynomial interpolation and least-squares. To measure the quality of the nodes produced by said algorithms, the Lebesgue constant will be used. In the algorithms, a number of numerical techniques will be used, such as the Gram-Schmidt process and the pivoted-QR process. In addition, concepts such as node density and greedy algorithms will be explored.