310 IGPM310.pdf        May 2010
TITLE Convergence Rates for Greedy Algorithms in Reduced Basis Methods
AUTHORS Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald DeVore, Guergana Petrova, Przemyslaw Wojtaszczyk
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 Hn to be used in approximating the elements of a compact set F in a Hilbert space H. One, by now popular, computational approach is to find Hn through a greedy strategy. It is natural to compare the approximation performance of the Hn generated by this strategy with that of the Kolmogorov widths dn(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, σn (F) := dist(F, Hn), obtained by the greedy strategy satisfies σn (F) ≤ Cn2ndn(F) . In this paper, various improvements of this result will be given. Among these, it is shown that whenever dn(F) ≤ M n−α, for all n > 0, and some M, α > 0, we also have σn (F) ≤ CαM n−α for all n > 0, where Cα depends only on α. Similar results are derived for generalized exponential rates of the form Me−anα . 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.
KEYWORDS Parameter dependent elliptic PFEs, reduced basis, greedy algorithm, weak greedy algorithm, Kolmogorov widths, convergence rates
DOI 10.1137/100795772
PUBLICATION SIAM journal on mathematical analysis
43(3), 1457-1472 (2011)