Convergence rates for greedy algorithms in reduced basis methods. (English) Zbl 1229.65193

Binev, Peter; Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald; Petrova, Guergana; Wojtaszczyk, Przemyslaw

SIAM J. Math. Anal. 43, No. 3, 1457-1472 (2011).

Authors’ 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 {F})\) since the latter gives the smallest error that can be achieved by subspaces of fixed dimension \(n\). The first such comparisons, given by A. Buffa et al. [ESAIM Math. Model. Numer. Anal. 46, No. 3, 595–603 (2012)], show that the approximation error, \(\sigma_n(\mathcal {F}):=\text{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.

Reviewer: Wilhelm Heinrichs (Essen)

MSC:

65N12	Stability and convergence of numerical methods for boundary value problems involving PDEs
65N15	Error bounds for boundary value problems involving PDEs
41A25	Rate of convergence, degree of approximation
41A46	Approximation by arbitrary nonlinear expressions; widths and entropy
41A65	Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
35J25	Boundary value problems for second-order elliptic equations

Keywords:

reduced basis method; greedy algorithms; parameter dependent PDEs; rates of convergence