Volume 54, Number 2, March-April 2020
|Page(s)||649 - 677|
|Published online||03 March 2020|
Multilevel weighted least squares polynomial approximation
Heriot-Watt University, Edinburgh, UK
2 École Polytechnique Fédérale de Lausanne (EPFL), CSQI-MATH, Lausanne, Switzerland
3 King Abdullah University of Science and Technology (KAUST), CEMSE, Thuwal, Saudi Arabia
4 RWTH Aachen University, Department of Mathematics, Aachen, Germany
* Corresponding author: email@example.com
Accepted: 21 June 2019
Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. It has been shown that, using an optimal distribution of sample locations, the number of samples required to achieve quasi-optimal approximation in a given polynomial subspace scales, up to a logarithmic factor, linearly in the dimension of this space. However, in many applications, the computation of samples includes a numerical discretization error. Thus, obtaining polynomial approximations with a single level method can become prohibitively expensive, as it requires a sufficiently large number of samples, each computed with a sufficiently small discretization error. As a solution to this problem, we propose a multilevel method that utilizes samples computed with different accuracies and is able to match the accuracy of single-level approximations with reduced computational cost. We derive complexity bounds under certain assumptions about polynomial approximability and sample work. Furthermore, we propose an adaptive algorithm for situations where such assumptions cannot be verified a priori. Finally, we provide an efficient algorithm for the sampling from optimal distributions and an analysis of computationally favorable alternative distributions. Numerical experiments underscore the practical applicability of our method.
Mathematics Subject Classification: 41A10 / 41A25 / 41A63 / 65B99 / 65N22
Key words: Multilevel methods / least squares approximation / multivariate approximation / polynomial approximation / convergence rates / error analysis
© EDP Sciences, SMAI 2020
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.