Convergence rates of adaptive algorithms for stochastic and partial differential equations

by von Schwerin, Erik

This work concerns the convergence of adaptive algorithms, based on a posteriori expansions of global errors, for numerical solution of differential equations, where the goal is to compute a functional of the solution. An adaptive algorithm aims to minimise the number of degrees of freedom to make the error in the functional less than a given tolerance. The number of degrees of freedom provides the convergence rate of the adaptive algorithm as the tolerance tends to zero. Provided that the computational work is proportional to the degrees of freedom this gives an estimate of the efficiency of the algorithm. The thesis consists of two papers, the first on the numerical approximation of partial differential equations, and the second on weak approximation of stochastic differential equations with barriers. The first paper considers approximation of functionals of solutions to second order elliptic partial differential equations in bounded domains of Rd, using isoparametric d-linear quadrilateral finite elements. For an adaptive algorithm, an error expansion with computable leading order term is derived. The computable error density, based on the dual weighted residual error representation, global error = X error density · mesh size2+d, elements using localised averages of second order difference quotients of the primal and dual finite element solutions, is proved to converge uniformly as the mesh size tends to zero. The proof splits the error into one part from elements with no edges on the initial mesh and without hanging nodes, and the remaining part, with hanging nodes and edges on the initial mesh, which is asymptotically negligible as the mesh size tends to zero. For each element an error indicator is defined by the computed error density multiplying the local mesh size to the power of 2 + d. It is proved, using the uniform convergence of the error density, that the adaptive algorithm, based on successive subdivisions of elements, reduces the maximal error indicator with a factor or stops with the error asymptotically bounded by the tolerance using the optimal number of elements for an adaptive isotropic mesh, up to a problem independent factor. Here the optimal number of elements is proportional to the d/2 power of the L d d+2 quasi-norm of the error density, whereas a uniform mesh requires a number of elements proportional to the d/2 power of the larger L1 norm of the same error density to obtain the same accuracy. For problems with multiple scales, in particular, these convergence rates may differ much, even though the convergence order may be the same. Numerical experiments for an elasticity problem with a crack and different variants of the averages show that the algorithm is useful in practice also for relatively large tolerances, much larger than the small tolerances needed to theoretically guarantee that the algorithm works well. The second paper presents an adaptive algorithm for Monte Carlo Euler approximation of the expected value E[g(X(?), ?)] of a given function g depending on the solution X of an Itô stochastic differential equation and on the first exit time ? from a given domain. An error expansion with computable leading order term, for the approximation of E[g(X(T))] with a fixed final time T > 0 in [Szepessy, Tempone and Zouraris, Comm. Pure and Appl. Math., 54, 1169-1214, 2001] is extended to the case with stopped diffusion. In the extension conditional probabilities are used to estimate the first exit time error, and difference quotients are used to approximate the initial data of the dual solutions. For the stopped diffusion problem the time discretisation error is of order N ?1/2 for a method with N uniform time steps. Numerical results show that the adaptive algorithm improve the time discretisation error to the order N?1 with N adaptive time steps. ISBN 91-7283-959-7 • TRITA-NA-0501 • ISSN 0348-2952 • ISRN KTH/NA/R--05/01--SE vi