Greedy Algorithms for Reduced Bases in Banach Spaces
- PDF / 533,899 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 207 Views
Greedy Algorithms for Reduced Bases in Banach Spaces Ronald DeVore · Guergana Petrova · Przemyslaw Wojtaszczyk
Received: 5 April 2012 / Accepted: 13 October 2012 © Springer Science+Business Media New York 2013
Abstract Given a Banach space X and one of its compact sets F , we consider the problem of finding a good n-dimensional space Xn ⊂ X which can be used to approximate the elements of F . The best possible error we can achieve for such an approximation is given by the Kolmogorov width dn (F )X . However, finding the space which gives this performance is typically numerically intractable. Recently, a new greedy strategy for obtaining good spaces was given in the context of the reduced basis method for solving a parametric family of PDEs. The performance of this greedy algorithm was initially analyzed in Buffa et al. (Modél. Math. Anal. Numér. 46:595– 603, 2012) in the case X = H is a Hilbert space. The results of Buffa et al. (Modél. Math. Anal. Numér. 46:595–603, 2012) were significantly improved upon in Binev et al. (SIAM J. Math. Anal. 43:1457–1472, 2011). The purpose of the present paper is to give a new analysis of the performance of such greedy algorithms. Our analysis not only gives improved results for the Hilbert space case but can also be applied to the same greedy procedure in general Banach spaces. Keywords Greedy algorithms · Convergence rates · Reduced basis · General Banach space Mathematics Subject Classification 41A46 · 41A25 · 46B20 · 15A15 Communicated by Wolfgang Dahmen. R. DeVore () · G. Petrova Department of Mathematics, Texas A&M University, College Station, TX, USA e-mail: [email protected] G. Petrova e-mail: [email protected] P. Wojtaszczyk Institute of Applied Mathematics, and Interdisciplinary Centre for Mathematical and Computational Modelling, University of Warsaw, Warsaw, Poland e-mail: [email protected]
Constr Approx
1 Introduction Let X be a Banach space with norm · := · X , and let F be one of its compact subsets. For notational convenience only, we shall assume that the elements f of F satisfy f X ≤ 1. We consider the following greedy algorithm for generating approximation spaces for F . We first choose a function f0 such that f0 = max f . f ∈F
(1.1)
Assuming {f0 , . . . , fn−1 } and Vn := span{f0 , . . . , fn−1 } have been selected, we then take fn ∈ F such that dist(fn , Vn )X = max dist(f, Vn )X ,
(1.2)
σn := σn (F )X := dist(fn , Vn )X := sup inf f − g.
(1.3)
f ∈F
and define f ∈F g∈Vn
This greedy algorithm was introduced, for the case X is a Hilbert space, in the reduced basis method [5, 6] for solving a family of PDEs. Certain variants of this algorithm, known as weak greedy algorithms, described below, are now numerically implemented with great success in the reduced basis method. The assumption that X is a Hilbert space matches well applications to elliptic problems in which the underlying energy space is indeed a Hilbert space. However, other settings, such as hyperbolic problems, in particular conservation laws, are naturall
Data Loading...
