Convergence Rates for Greedy Algorithms in Reduced Basis Methods (PREPRINT)
Abstract
The reduced basis method was introduced for the accurate online evaluation of solutions to a parameter dependent family of elliptic partial differential equations. Abstractly, it can be viewed as determining a "good" n-dimensional space $\mathcal{H}_n$ to be used in approximating the elements of a compact set $\mathcal{F}$ in a Hilbert space $\mathcal{H}$. One, by now popular, computational approach is to find $\mathcal{H}_n$ through a greedy strategy. It is natural to compare the approximation performance of the $\mathcal{H}_n$ generated by this strategy with that of the Kolmogorov widths $d_n($\mathcal{H}_n${F})$ since the latter gives the smallest error that can be achieved by subspaces of fixed dimension n. The first such comparisons, given in [1], show that the approximation error, $\sigma_n(\mathcal{F}:=\mathrm{dist}(|mathcal{F},\mathcal{H}_n)$, obtained by the greedy strategy satisfies $\sigma_n(\mathcal{F}\leq Cn^nd_n(\mathcal{F})$. In this paper, various improvements of this result will be given. Among these, it is shown that whenever $d_n(\mathcal{F})\leq Mn^{-\alpha}$ for all $n > 0$, and some $M, \alpha> 0$, we also have $\sigma_n(mathcal{F}\leq C_\alpha Mn^{-\alpha}$for all $n > 0&, where $C_\alpha$ depends only on $\alpha$. Similar results are derived for generalized exponential rates of the form $Me^{-an^\alpha)$ . The exact greedy algorithm is not always computationally feasible and a commonly used computationally friendly variant can be formulated as a "weak greedy algorithm". The results of this paper are established for this version as well.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 04, 2010
- Accession Number
- ADA640304
Entities
People
- Albert Cohen
- Guergana Petrova
- Peter Binev
- Przemyslaw Wojtaszczyk
- Ronald DeVore
- Wolfgang Dahmen
Organizations
- Texas A&M University