Adaptive wavelet schemes for nonlinear variational problems

Abstract. We develop and analyze wavelet based adaptive schemes for nonlinear variational problems. We derive estimates for convergence rates and corresponding work counts that turn out to be asymptotically optimal. Our approach is based on a new paradigm that has been put forward recently for a class of linear problems. The original problem is transformed first into an equivalent one which is well posed in the Euclidean metric `2. Then conceptually one seeks iteration schemes for the infinite dimensional problem that exhibits at least a fixed error reduction per step. This iteration is then realized approximately through an adaptive application of the involved operators with suitable dynamically updated accuracy tolerances. The main conceptual ingredients center around nonlinear tree approximation and the sparse evaluation of nonlinear mappings of wavelet expansions. We prove asymptotically optimal complexity for adaptive realizations of first order iterations and of Newton’s method. Key words. variational problems, wavelet representations, semilinear equations, mapping prop-erties, gradient iteration, convergence rates, adaptive application of operators, sparse evaluation of nonlinear mappings of wavelet expansions, tree approximation, Newton’s schem