# Convergence rates of adaptive algorithms for stochastic and partial differential equations

Abstract (Summary)

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
Bibliographical Information:

Advisor:

School:Kungliga Tekniska högskolan

School Location:Sweden

Source Type:Master's Thesis

Keywords:MATHEMATICS; Applied mathematics; Numerical analysis; Numerical analysis; Numerisk analys

ISBN:91-7283-959-7

Date of Publication:01/01/2005