Opgedragen aan mijn ouders, Eddy Wyns & Anita Leys Convergence Analysis and Application of ADI Schemes for Partial Differential Equations from Financial Mathematics Proefschrift voorgelegd op 26 juni 2017 tot het behalen van de graad van Doctor in de Wetenschappen – Wiskunde, bij de faculteit Wetenschappen aan de Universiteit Antwerpen. Promotor: Prof. dr. Karel in ’t Hout Maarten Wyns Doctoral committee Chairman: Prof. dr. Wim Vanroose (University of Antwerp) Supervisor: Prof. dr. Karel in ’t Hout (University of Antwerp) Other members: Prof. dr. Ann De Schepper (University of Antwerp) Prof. dr. ir. Florence Guillaume (University of Antwerp) Prof. dr. Willem Hundsdorfer (CWI Amsterdam) Prof. dr. ir. Cornelis W. Oosterlee (CWI Amsterdam) Prof. dr. Mich`ele Vanmaele (Ghent University) Original title: Convergence Analysis and Application of ADI Schemes for Partial Differential Equations from Financial Mathematics Nederlandse titel: Convergentie-Analyse en Toepassing van ADI Schema’s voor Parti¨ele Differentiaalvergelijkingen uit de Financi¨ele Wiskunde Keywords: ADI schemes, Douglas scheme, Modified Craig–Sneyd scheme, Craig–Sneyd scheme, Hundsdorfer–Verwer scheme, convection-diffusion equa- tion, mixed spatial derivative, convergence, non-smooth initial data, Dirac delta, backward Kolmogorov equation, forward Kolmogorov equation, finite difference methods, finite volume methods, adjoint spatial discretization. Published and distributed by Maarten Wyns. The research presented in this thesiswassupportedbytheUniversityResearchFund(BOF)oftheUniversity of Antwerp and by a PhD fellowship of the Research Foundation–Flanders. Contact information (cid:66) Applied Mathematics, Dept. Mathematics & Computer Science University of Antwerp (CMI), Building G3.07 Middelheimlaan 1, B–2020 Antwerp, Belgium (cid:84) +32 (0)3 265 38 54 (cid:107) [email protected] (cid:109) https://www.linkedin.com/in/maarten-wyns-525b3352 Copyright c2017 by Maarten Wyns. (cid:13) All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording, broadcasting or by any other information storage and retrieval system without written permission from the copyright owner. Samenvatting Convergentie-Analyse en Toepassing van ADI Schema’s voor Parti¨ele Differentiaalvergelijkingen uit de Financi¨ele Wiskunde In de huidige internationale financi¨ele markten zijn opties producten die vaak verhandeld worden. Gevorderde wiskundige modellen worden gebruikt voor het bepalen van de eerlijke waarde van deze contracten, evenals hun af- hankelijkheidvanonderliggendevariabelenenparameters. Ditleidttotmeerdi- mensionaletijdsafhankelijkeparti¨eledifferentiaalvergelijkingen(PDVen). Voor de meerderheid van deze PDVen is er geen analytische oplossing beschikbaar en dient men gebruik te maken van numerieke methoden om hun exacte op- lossing te benaderen. De methode-der-lijnen is een welgekende en veelzijdige aanpak voor het bepalen van een numerieke oplossing. Hierbij discretiseert men eerst de plaatsvariabelen, met bvb. eindige differentiemethoden, hetgeen leidt tot een groot stelsel van gewone differentiaalvergelijkingen (GDVen). In eentweedestapwordtditzogenaamdesemidiscreet-systeemnumeriekopgelost aan de hand van een geschikte impliciete tijdstapmethode. Indien de PDV meerdimensionaal is, dan kan deze tweede stap erg rekenintensief zijn bij het gebruik van klassieke impliciete tijdstapmethodes. In dit proefschrift beschouwen we de convergentie en de toepassing van vier alternerende richting (Engels: direction) impliciete (ADI) schema’s voor de numerieke oplossing van semidiscrete tweedimensionale convectie-diffusie- vergelijkingen. Meer bepaald onderzoeken we het Douglas (Do) schema, het Craig–Sneyd (CS) schema, het aangepaste (Engels: Modified) Craig–Sneyd (MCS) schema en het Hundsdorfer–Verwer (HV) schema. ADI schema’s ma- kengebruikvaneenopsplitsingvanhetsemidiscreet-systeemindeverschillende plaatsrichtingen. Dit kan zorgen voor een aanzienlijk computationeel voordeel in iedere tijdstap aangezien het makkelijker is om de suboperatoren achtereen- volgens impliciet te behandelen, in plaats van de gehele operator in ´e´en keer. De vier ADI schema’s zijn aangepast aan PDVen met gemengde afgeleiden en worden vaak gebruikt in de financi¨ele wiskunde. In dit gebied zijn gemengde plaatsafgeleiden alomtegenwoordig vanwege correlatie tussen de onderliggende stochastische processen. Inheteersteinleidendehoofdstukwordendeniet-uniformeCartesischeroos- ters en de tweede-orde eindige differentieformules voorgesteld die doorheen de thesisgebruiktwordenvoordeplaatsdiscretisatievantijdsafhankelijkePDVen. i ii Samenvatting InhettweedeinleidendehoofdstukwordendevierADIschema’sge¨ıntroduceerd en wordt er een overzicht gegeven van de bestaande stabiliteits- en convergen- tieresultaten. Voor het Do schema leidt dit reeds tot een algemeen eerste-orde convergentieresultaat. Het beschouwen van een verstoorde versie van het (M)CS schema, respec- tievelijk het HV schema, leidt tot een recursie voor de totale discretisatiefout van de verschillende schema’s. Door de lokale discretisatiefout spitsvondig op te splitsen, en een lemma van Hundsdorfer toe te passen, bekomen we een tweede-orde convergentieresultaat voor het (M)CS schema en het HV schema onder enkele natuurlijke stabiliteits- en gladheidsaannames. Bij niet-gladde beginfuncties kan toepassing van de ADI schema’s leiden tot foutieve oscillaties in de numerieke oplossing. We geven een voorbeeld dat hetpositieveeffectvanRannachertijdstappenillustreert, ditbetekenthetver- vangen van de eerste N ADI stappen door 2N halve tijdstappen met het 0 0 achterwaartse Euler schema. Voor het uitvoeren van een theoretische analyse wordt een tweedimensionale convectie-diffusievergelijking beschouwd die voor- zien is van Dirac-delta begindata. We passen een Fouriertransformatie toe om aan te tonen dat, als de tijdsdiscretisatie gebeurt met het (M)CS schema, dan N = 2 een ondergrens is voor N om te verzekeren dat de numerieke oplos- 0 0 singconvergeertnaardeexacteoplossing. Uitgebreidenumeriekeexperimenten suggereren gelijkaardige resultaten voor het Do schema en het HV schema. Onze convergentieresultaten verantwoorden het gebruik van de ADI sche- ma’s in praktische toepassingen. In de laatste hoofdstukken introduceren we twee methoden voor het kalibreren van stochastische lokale volatiliteitsmo- dellen (SLV) aan hun onderliggende lokale volatiliteitsmodel (LV). De ADI schema’s zijn hierbij belangrijk voor de effici¨entie van de kalibratiemetho- den. De eerste kalibratiemethode is ge¨ınspireerd door een verband tussen de voorwaartse en achterwaartse Kolmogorov-vergelijking. De plaatsdiscretisatie van de achterwaartse Kolmogorov-vergelijking wordt gebruikt voor het invoe- ren van een toegevoegde plaatsdiscretisatie van de voorwaartse Kolmogorov- vergelijking. Onderenkelevoorwaardenkandezetoegevoegdeplaatsdiscretisa- tiegebruiktwordenomhetsemidiscreteSLVmodelexacttekalibrerenaanhet semidiscrete LV model. Om deze kalibratie uit te voeren dient er nog een stel- sel niet-lineaire GDVen opgelost te worden. We maken gebruik van het MCS schema voor de tijdsdiscretisatie en behandelen de niet-lineariteit door middel van een iteratieprocedure. De tweede kalibratieprocedure is gebaseerd op een nieuwe eindige volume (EV) methode voor de plaatsdiscretisatie van algemene ´e´endimensionale en tweedimensionale voorwaartse Kolmogorov-vergelijkingen. De EV methode is massabehoudend en kan op een natuurlijke manier omgaan met de randvoorwaarden. Bovendien is er voor de nieuwe EV methode geen transformatie van de voorwaartse Kolmogorov vergelijking nodig. Dit vormt een belangrijk voordeel in vergelijking met bestaande EV methoden. Het ge- bruik van de EV methode voor de kalibratie van SLV modellen leidt tot een groot stelsel van niet-lineaire GDVen. Discretisatie in de tijd gebeurt aan de hand van het HV schema en de niet-lineariteit wordt opnieuw behandeld meteeniteratieprocedure. Uitgebreidenumeriekeexperimententonenaandat beide kalibratieprocedures leiden tot een snelle, stabiele, en accurate kalibratie van SLV modellen aan hun onderliggende LV model. Summary Convergence Analysis and Application of ADI Schemes for Partial Differential Equations from Financial Mathematics In the contemporary international financial markets option products are widely traded. Advanced mathematical models are employed for determining the fair values of these contracts as well as their sensitivities to underlying variablesandparameters. Thisleadstomultidimensionaltime-dependentpar- tial differential equations (PDEs). For the majority of these PDEs there is no analytical solution available and one resorts to numerical methods for their approximate solution. A well-known and versatile approach to the numerical solution is given by the method-of-lines. The PDE is then first discretized in thespatialvariables,e.g.byfinitedifferences,leadingtoalargesystemofordi- narydifferentialequations(ODEs). Inasecondstepthisso-calledsemidiscrete systemisnumericallysolvedbyapplyingasuitableimplicittimediscretization method. If the PDE is multidimensional, then the latter task can be compu- tationally intensive when classical implicit time stepping methods are used. In this thesis we consider the convergence and application of four alternat- ing direction implicit (ADI) time stepping schemes in the numerical solution of semidiscretized two-dimensional convection-diffusion equations. More pre- cisely, we consider the Douglas (Do) scheme, the Craig–Sneyd (CS) scheme, the Modified Craig–Sneyd (MCS) scheme and the Hundsdorfer–Verwer (HV) scheme. ADI schemes employ a splitting of the semidiscrete PDE operator in thedifferentspatialdirections. Thiscanleadtoamajorcomputationaladvan- tageineachtimestepasitturnsoutthattheimplicitnessisoftenmucheasier todealwithwhenthesuboperatorsarehandledsuccessively,insteadoftreating the full operator all at once. The four ADI schemes are adapted to mixed spa- tial derivative terms and widely used in financial mathematics. Mixed spatial derivatives are prominent in computational finance due to correlation between the underlying stochastic processes. Thefirstpreliminarychapterpresentsthenon-uniformCartesiangridsand secondorderfinitedifferenceschemesthatareusedinthethesisforthespatial discretization of time-dependent PDEs. The second preliminary chapter intro- duces the four ADI time stepping schemes under consideration and gives an overview of their existing stability and consistency results. For the Do scheme this already leads to a general first order convergence result. iii iv Summary A recursion formula for the total discretization error of the (M)CS scheme, respectively the HV scheme, has been obtained by considering a perturbed version of the respective schemes. We perform an ingenious splitting of the local discretization errors and apply a key lemma from Hundsdorfer to arrive atasecondorderconvergenceresultforthe(M)CSschemeandtheHVscheme under natural stability and smoothness assumptions. If the initial function is non-smooth, then application of the ADI schemes can lead to spurious erratic behaviour of the numerical solution. A motivating example illustrates the positive effect of Rannacher time stepping, i.e. replac- ing the first N ADI time steps by 2N half-time steps of the implicit Euler 0 0 scheme. We consider a model two-dimensional convection-diffusion equation with Dirac delta initial data to perform a theoretical analysis. Application of a two-dimensional Fourier transformation leads to the result that, if temporal discretization is performed with the (M)CS scheme, then N = 2 is a lower 0 bound on N for the Rannacher time stepping in order to ensure convergence 0 of the numerical solution to the exact solution. Based on ample numerical ex- periments, similar convergence results are conjectured for the Do scheme and the HV scheme. Ourconvergenceresultsprovideabasisfortheschemesbeingusedinprac- tice. Weintroducetwomethodsforthecalibrationofstate-of-the-artstochastic local volatility (SLV) models to their underlying local volatility (LV) model. Here, the ADI schemes are important for the efficiency of the calibration algo- rithms. The first calibration method makes use of a relationship between the corresponding forward and backward Kolmogorov equation. The spatial dis- cretization of the backward Kolmogorov equation is used to adopt an adjoint semidiscretizationfortheforwardKolmogorovequation. Thelatterspatialdis- cretization allows, under some natural assumptions, to create an exact match betweenthesemidiscreteLVmodelandthesemidiscreteSLVmodel. Inorderto performthiscalibration,alargesystemofnon-linearODEsneedstobesolved. Time stepping is performed with the MCS scheme and an inner iteration is introduced to handle the non-linearity. For the second calibration procedure, we propose a new finite volume (FV) method for the spatial discretization of general one-dimensional and two-dimensional forward Kolmogorov equations. The FV method is mass-conservative and handles the boundary conditions in a natural way. Moreover, it does not require a transformation of the forward Kolmogorovequation, which isamajoradvantageincomparisonwith existing FV methods. Using the FV spatial discretization for the calibration of SLV modelsleadstoalargesystemofnon-linearODEs. Timesteppingisperformed with the HV scheme and, as before, an inner iteration is used to handle the non-linearity. Ample numerical experiments show that both calibration pro- cedures lead to a fast, stable and accurate calibration of SLV models to their underlying LV model. Dankwoord Hetschrijvenvanditdankwoordbezorgtmijeendubbelgevoel. Enerzijdsben ik blij dat het onderzoek volledig is afgerond en dat alle resultaten verwerkt zijn in dit proefschrift. Anderzijds overvalt mij het besef dat een mooie, leer- rijke periode van vier jaar bijna ten einde loopt. Graag zou ik iedereen willen bedanken die dit onderzoek mogelijk heeft gemaakt en die heeft bijgedragen tot deze fantastische periode. Enkele personen waren hierbij in het bijzonder heel belangrijk. Hen zou ik dan ook expliciet willen bedanken: Eerstenvooralzouikmijnoudersenormwillenbedanken. Mamaenpapa, jullie hebben mijn broer en mij steeds op de eerste plaats gezet, ons alle mo- gelijke kansen gegeven, ons onvoorwaardelijk gesteund in alles wat we deden en doen, en nog zoveel meer. Maar bovenal zorgen jullie voor een warme thuis waarikaltijdgraagnaartoega,zowelingoedealsminderemomenten. Bedankt om me de capaciteiten en de opvoeding te geven die het mogelijk maakten om dit proefschrift af te ronden. Niet enkel ik, maar ook mijn broer Kenneth heeft het geluk gehad bij deze ouders te mogen opgroeien (en bijgevolg het geluk gehad om mijn broer te mogen zijn). Kenneth, bedankt om me te helpen als ik weer eens iets niet begreep op school, om me naar een hoger niveau te brengen omdat ik niet wou onderdoen voormijngrotebroer, maarvooralom steedsopnieuw klaarte staan met goede raad. Met andere woorden, bedankt om een broer te zijn die er mede voor gezorgd heeft dat ik al zo ver ben geraakt. Misschien is dit ook meteen het gepaste moment om mij eens te excuseren aanmijnoudersenbroervooruitsprakenals“Ikganietallesgestudeerdkrijgen tegen morgen.”en “Het examen ging niet zo goed, maar waarschijnlijk ben ik er wel door.”die jullie vijf jaar moesten trotseren tijdens mijn studies aan de universiteit. Daarnaast wil ik graag mijn grootouders en de hele familie bedanken voor hun steun en interesse in mijn onderzoek gedurende deze vier jaar. Een zeer speciale vermelding is hier tevens op zijn plaats voor mijn vrien- din, mijn verloofde, Sarah. Schattie, ondanks het feit dat ik je pas tijdens het tweede deel van mijn onderzoek leerde kennen, ben je hierbij zeer belangrijk voormijgeweest. Jezorgtnietalleenvoordeleukemomentenbuitenhetwerk, je bent er voor me als het even minder gaat, je helpt me bij het maken van v vi Dankwoord moeilijke keuzes, je steunt mij in alles wat ik doe, jij maakt me gelukkig. Je bent fantastisch en je bent al snel een van de belangrijkste personen in mijn leven geworden! Verder zou ik graag mijn vrienden willen bedanken. Jullie zorgden vaak voor ontspanning tijdens dit onderzoek, en dat kan in sommige gevallen let- terlijk genomen worden wanneer ik weeral mijn lach niet kon inhouden tijdens het werk omdat er bepaalde berichten op het scherm verschenen. Bedankt om regelmatig, al dan niet oprecht ge¨ınteresseerd, te vragen wat het onderwerp van mijn onderzoek was en hoe het vorderde. Uiteraard dienen er ook op de Universiteit Antwerpen enkele mensen be- dankt te worden. Allereerst mijn promotor Karel in ’t Hout, die me zowel begeleidde voor mijn Masterthesis als voor dit proefschrift. Bedankt om me in contact te brengen met dit onderwerp en dit onderzoek mogelijk te maken. Zonderuwasdeprojectaanvraagnooitaanvaardenwasditproefschrifterdus nooitgekomen. Laterheeftumelatenkennismakenmettoponderzoek(ers)van over de hele wereld. Deze ervaringen hebben samen met uw uitgebreide kennis ditonderzoeknaareenhogerniveaugetild. Verderstondualtijdklaarvooreen gesprek over onderzoek, maar ook over andere onderwerpen zoals sport, reizen of priv´e zaken. Bedankt om me gedurende deze vijf jaar, na onze eerste af- spraakvoordeMasterthesis,tevoorzienvaneenruimebagagedieongetwijfeld nog vaak van pas zal komen in de toekomst. Daarnaastzouikallecollega’svanhetdepartementWiskunde–Informatica willenbedanken. Doorhenbeniksteedsmetveelpleziernaarbureaugekomen. Graagzouikhierbijmijnbureaugenotenexplicietwillenvermelden. Radoslav, Lynn en Koen, bedankt om M.G.307 met mij te delen en steeds klaar te staan voor een ontspannende babbel. Tot slot welgemeende dank aan alle belastingbetalers die al dan niet met veelpleziereendeelvanhuninkomenafstondenaandeoverheidomditonder- zoek te financieren. Maarten Wyns Antwerpen, 2017 Whakawhetai ki a koutou nui atu!