Sparse Grid Interpolation

Abstract

For the approximation of multidimensional functions, using classical numerical discretization schemes such as full grids su ers the curse of dimensionality which is still a roadblock for the numerical treatment of high-dimensional problems. The number of basis functions or nodes (grid points) have to be stored and processed depend exponentially on the number of dimensions, where e cient computation are challenging in the implementation. Recently, the technique of sparse grids has been introduced to signi cantly reduce the cost to approximate high-dimensional functions under certain regularity conditions. In this thesis, we present the classical sparse grid where the problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. Furthermore, the di erent types of sparse grids,i.e. Clenshaw Curtis sparse grid, have been taken into consideration to compare the accuracy and complexity of these algorithms. We then describe the sparse grid combination technique to demonstrate that it is competitive to the classical sparse grid approaches with respect to quality and run time and give proof that the interpolation by using combination approach is the classical sparse grid. We give details on the basic features of sparse grids and we consider several test problems up to dimensions. The results of numerical experiments report on the quality of approximation generated by the sparse grids, and, nally, employ the sparse grid interpolation for a real-world case to reduce a computationally expensive simulation model. We aim to obtain an e cient surrogate approximation based on a small number of simulations.