Convergence Rates for Greedy Algorithms in Reduced Basis Methods

Source abstract

The reduced basis method was introduced for the accurate online evaluation of solutions to a parameter dependent family of elliptic PDEs. 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{F})$ since the latter gives the smallest error that can be achieved by subspaces of fixed dimension n. The first such comparisons, given in [A. Buffa et al., ESAIM Math. Model. Numer. Anal., 2011, to appear], 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 Cn2^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.