Adaptive Algorithms for Deterministic and Stochastic Differential Equations

by Moon, Kyoung-Sook

Abstract (Summary)
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 step sizes. 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 iii iv Preface 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 discussions. 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 Kyoung-Sook Moon v vi
Bibliographical Information:


School:Kungliga Tekniska högskolan

School Location:Sweden

Source Type:Doctoral Dissertation

Keywords:adaptive mesh refinement algorithm; a posteriori error estimate


Date of Publication:01/01/2003

© 2009 All Rights Reserved.