Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Numerical Complexity Analysis of Weak Approximation of Stochastic Differential Equations
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2002 (English)Doctoral thesis, comprehensive summary (Other scientific)
Abstract [en]

The thesis consists of four papers on numerical complexityanalysis of weak approximation of ordinary and partialstochastic differential equations, including illustrativenumerical examples. Here by numerical complexity we mean thecomputational work needed by a numerical method to solve aproblem with a given accuracy. This notion offers a way tounderstand the efficiency of different numerical methods.

The first paper develops new expansions of the weakcomputational error for Itˆo stochastic differentialequations using Malliavin calculus. These expansions have acomputable leading order term in a posteriori form, and arebased on stochastic flows and discrete dual backward problems.Beside this, these expansions lead to efficient and accuratecomputation of error estimates and give the basis for adaptivealgorithms with either deterministic or stochastic time steps.The second paper proves convergence rates of adaptivealgorithms for Itˆo stochastic differential equations. Twoalgorithms based either on stochastic or deterministic timesteps are studied. The analysis of their numerical complexitycombines the error expansions from the first paper and anextension of the convergence results for adaptive algorithmsapproximating deterministic ordinary differential equations.Both adaptive algorithms are proven to stop with an optimalnumber of time steps up to a problem independent factor definedin the algorithm. The third paper extends the techniques to theframework of Itˆo stochastic differential equations ininfinite dimensional spaces, arising in the Heath Jarrow Mortonterm structure model for financial applications in bondmarkets. Error expansions are derived to identify differenterror contributions arising from time and maturitydiscretization, as well as the classical statistical error dueto finite sampling.

The last paper studies the approximation of linear ellipticstochastic partial differential equations, describing andanalyzing two numerical methods. The first method generates iidMonte Carlo approximations of the solution by sampling thecoefficients of the equation and using a standard Galerkinfinite elements variational formulation. The second method isbased on a finite dimensional Karhunen- Lo`eve approximation ofthe stochastic coefficients, turning the original stochasticproblem into a high dimensional deterministic parametricelliptic problem. Then, adeterministic Galerkin finite elementmethod, of either h or p version, approximates the stochasticpartial differential equation. The paper concludes by comparingthe numerical complexity of the Monte Carlo method with theparametric finite element method, suggesting intuitiveconditions for an optimal selection of these methods. 2000Mathematics Subject Classification. Primary 65C05, 60H10,60H35, 65C30, 65C20; Secondary 91B28, 91B70.

Place, publisher, year, edition, pages
Stockholm: KTH , 2002. , x, 28 p.
Series
Trita-NA, ISSN 0348-2952 ; 0220
Keyword [en]
Adaptive methods, a posteriori error estimates, stochastic differential equations, weak approximation, Monte Carlo methods, Malliavin Calculus, HJM model, option price, bond market, stochastic elliptic equation, Karhunen-Loeve expansion, numerical co
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-3413ISRN: KTH/NA/R--20/20--SEISBN: 91-7283-350-5 (print)OAI: oai:DiVA.org:kth-3413DiVA: diva2:9210
Public defence
2002-10-11, 00:00
Note
QC 20100825Available from: 2002-09-26 Created: 2002-09-26 Last updated: 2010-08-25Bibliographically approved
List of papers
1. Adaptive weak approximation of stochastic differential equations
Open this publication in new window or tab >>Adaptive weak approximation of stochastic differential equations
2001 (English)In: Communications on Pure and Applied Mathematics, ISSN 0010-3640, E-ISSN 1097-0312, Vol. 54, no 10, 1169-1214 p.Article in journal (Refereed) Published
Abstract [en]

Adaptive time-stepping methods based on the Monte Carlo Euler method for weak approximation of Ito stochastic differential equations are developed. The main result is new expansions of the computational error, with computable leading-order term in a posteriori form, based on stochastic flows and discrete dual backward problems. The expansions lead to efficient and accurate computation of error estimates. Adaptive algorithms for either stochastic time steps or deterministic time steps are described. Numerical examples illustrate when stochastic and deterministic adaptive time steps are superior to constant time steps and when adaptive stochastic steps are superior to adaptive deterministic steps. Stochastic time steps use Brownian bridges and require more work for a given number of time steps. Deterministic time steps may yield more time steps but require less work; for example, in the limit of vanishing error tolerance, the ratio of the computational error and its computable estimate tends to 1 with negligible additional work to determine the adaptive deterministic time steps.

Keyword
step-size control, global error
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-20900 (URN)000170618900001 ()
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved
2. Convergence rates for adaptive weak approximation of stochastic differential equations
Open this publication in new window or tab >>Convergence rates for adaptive weak approximation of stochastic differential equations
2005 (English)In: Stochastic Analysis and Applications, ISSN 0736-2994, E-ISSN 1532-9356, Vol. 23, no 3, 511-558 p.Article in journal (Refereed) Published
Abstract [en]

Convergence rates of adaptive algorithms for weak approximations of Ito stochastic differential equations are proved for the Monte Carlo Euler method. Two algorithms based either oil optimal stochastic time steps or optimal deterministic time steps are studied. The analysis of their computational complexity combines the error expansions with a posteriori leading order term introduced in Szepessy et al. [Szepessy, A.. R. Tempone, and G. Zouraris. 2001. Comm. Pare Appl. Math. 54:1169-1214] and ail extension of the convergence results for adaptive algorithms approximating deterministic ordinary differential equations, derived in Moon et al. [Moon, K.-S., A. Szepessy, R. Tempone, and G. Zouraris. 2003. Numer. Malh. 93:99-129]. The main step in the extension is the proof of the almost sure convergence of the error density. Both adaptive alogrithms are proven to stop with asymptotically optimal number of steps up to a problem independent factor defined in the algorithm. Numerical examples illustrate the behavior of the adaptive algorithms, motivating when stochastic and deterministic adaptive time steps are more efficient than constant time steps and when adaptive stochastic steps are more efficient than adaptive deterministic steps.

Keyword
adaptive mesh refinement algorithm, almost sure convergence, computational complexity, Monte Carlo method, stochastic differential equations, finite-element methods, error
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-14798 (URN)10.1081/sap-200056678 (DOI)000229613900005 ()2-s2.0-20444378209 (Scopus ID)
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically approved
3. Monte Carlo euler approximation if HJM term structure financial models
Open this publication in new window or tab >>Monte Carlo euler approximation if HJM term structure financial models
2001 (English)In: Stochastic Numerics 2001 at ETH, Zurich, Switzerland. February 19 - 21, 2001, 2001Conference paper, Published paper (Other academic)
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-24192 (URN)
Note
QC 20100823Available from: 2010-08-23 Created: 2010-08-23 Last updated: 2010-08-25Bibliographically approved
4. Galerkin finite element approximations of stochastic elliptic partial differential equations
Open this publication in new window or tab >>Galerkin finite element approximations of stochastic elliptic partial differential equations
2004 (English)In: SIAM Journal on Numerical Analysis, ISSN 0036-1429, E-ISSN 1095-7170, Vol. 42, no 2, 800-825 p.Article in journal (Refereed) Published
Abstract [en]

We describe and analyze two numerical methods for a linear elliptic problem with stochastic coefficients and homogeneous Dirichlet boundary conditions. Here the aim of the computations is to approximate statistical moments of the solution, and, in particular, we give a priori error estimates for the computation of the expected value of the solution. The first method generates independent identically distributed approximations of the solution by sampling the coefficients of the equation and using a standard Galerkin finite element variational formulation. The Monte Carlo method then uses these approximations to compute corresponding sample averages. The second method is based on a finite dimensional approximation of the stochastic coefficients, turning the original stochastic problem into a deterministic parametric elliptic problem. A Galerkin finite element method, of either the h- or p-version, then approximates the corresponding deterministic solution, yielding approximations of the desired statistics. We present a priori error estimates and include a comparison of the computational work required by each numerical approximation to achieve a given accuracy. This comparison suggests intuitive conditions for an optimal selection of the numerical approximation.

Keyword
stochastic elliptic equation, perturbation estimates, Karhunen-Loeve expansion, finite elements, Monte Carlo method, k x h-version, p x h-version, expected value, error estimates, boundary-value-problems, quadrature-formulas, uncertainties, domain
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-23590 (URN)000222773600015 ()
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

fulltext(914 kB)1085 downloads
File information
File name FULLTEXT01.pdfFile size 914 kBChecksum MD5
a2d1d0b046f4ac9ab1bd25cb14ac826b3e56711c4887a48981e02c4462e739fe06554f47
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Tempone Olariaga, Raul
By organisation
Numerical Analysis and Computer Science, NADA
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1085 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 719 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf