Adaptive Algorithms for Deterministic and Stochastic Differential Equations
Adaptive methods for numerical solutions of differential equations are useful to
combine the two goals of good accuracy and efficiency. This thesis contributes to the
theoretical understanding of optimal convergence rates of adaptive algorithms. In
particular, this work studies stopping, accuracy and efficiency behavior of adaptive
algorithms for solving ordinary differential equations (ODEs), partial differential
equations (PDEs) and Itô stochastic differential equations (SDEs).
The main ingredient of the adaptive algorithms is an error expansion of the
form “Global error = ? local error · weight + higher order error”, with computable
leading order terms. The algorithm uses additional computational work to obtain
the error estimate because of the weights. However, the approximation of the
weights is required to inform where to refine the mesh to achieve optimal efficiency.
Based on the a posteriori error expansions with “error indicator := |local error ·
weight|”, the adaptive algorithm subdivides the time steps or elements if the error
indicators are greater than TOL/N , and stops if all N time steps or elements
have sufficiently small error indicators. Similar algorithms are derived with either
stochastic or deterministic time steps for weak approximations of SDEs including
stopped diffusions using Monte Carlo Euler method.
There are two main results on efficiency and accuracy of the adaptive algorithms.
For accuracy, the approximation errors are asymptotically bounded by the specified
error tolerance times a problem independent factor as the tolerance parameter tends
to zero. For efficiency, the algorithms decrease the maximal error indicator with
a factor, less than 1, or stop with asymptotically optimal number of final time
steps or elements. Note that the optimal here refers to error densities of one sign,
i.e. possible cancellation of the errors is not taken into account. For a p-th order
accurate method, the L 1
p+1 quasi-norm of the error density is a good measure of
the convergence rate for the adaptive approximation, while the number of uniform
steps is measured by the larger L1-norm of the error density.
This analysis of convergence rates of the adaptive algorithms is based on the
convergence of an error density, which measures the approximation error for each
time step or element. In particular, the error density is proven to converge pointwise
on structured adaptive meshes allowing hanging nodes for tensor finite elements and
to converge almost surely for SDEs as the error tolerance tends to zero.
Finally, numerical experiments illustrate the behavior of the adaptive methods
and show that adaptive methods can be more efficient than methods with uniform
2000 Mathematics Subject Classification. Primary 65L50, 65C30, 65N50
Key words and phrases. adaptive methods, mesh refinement algorithm, a posteriori
error estimate, dual solution, computational complexity, stopped diffusion, finite
element method, Monte Carlo method
ISBN 91-7283-553-2 • TRITA-NA-0315 • ISSN 0348-2952 • ISRN KTH/NA/R--03/15--SE
The work included in this thesis has been carried out from April 1999 to September
2003at the department of Numerical Analysis and Computer Science (NADA),
Royal Institute of Technology (KTH), in Stockholm, Sweden.
First of all, I would like to express my deepest gratitude to my dear advisor, Prof.
Anders Szepessy, for being my academic supervisor with enlightening guidance, for
continuous encouragement with trust and for all the support throughout this work.
I would also like to thank Raúl Tempone and Georgios E. Zouraris for many
valuable discussions about mathematics as well as life. I am grateful to Erik von
Schwerin for nice company at different scientific meetings and his comments on the
early draft. I thank Mattias Sanberg, Jesper Carlsson and Larisa Beilina for fruitful
It has been wonderful time for me to cooperate and discuss with all my present
and former colleagues at NADA and the Parallel and Scientific Computing Institute
(PSCI). In particular, I would like to thank to Prof. Germund Dahlquist, Prof.
Axel Ruhe, Prof. Björn Engquist and Prof. Jesper Oppelstrup for finding time for
scientific discussions and helping other things.
Last but not least, I wish to thank my dear husband, Dr. Sang-Mo Koo, and
our families for all their love, patience and support over the years.
Financial supports from PSCI, NADA and the Swedish National Board for
Industrial and Technical Development (NUTEK) are gratefully acknowledged.
Stockholm, September 2003
School:Kungliga Tekniska högskolan
Source Type:Doctoral Dissertation
Keywords:adaptive mesh refinement algorithm; a posteriori error estimate
Date of Publication:01/01/2003