Analyses and Applications of the Peaceman--Rachford and Douglas--Rachford Splitting Schemes

Abstract

Splitting methods are widely used as temporal discretizations of evolution equations. Such methods usually constitute competitive choices whenever a vector field can be split into a sum of two or more parts that each generates a flow easier to compute or approximate than the flow of the sum. In the research presented in this Licentiate thesis we consider dissipative evolution equations with vector fields given by unbounded operators. Dynamical systems that fit into this framework can for example be found among Hamiltonian systems and parabolic and hyperbolic partial differential equations (PDEs).



The goal of the presented research is to perform convergence analyses for the lternating direction implicit (ADI) methods in the setting of dissipative operators. In this context these methods are known to possess excellent stability properties. Additionally, they generate easily computable numerical flows and are ideal choices for studying convergence to stationary solutions, a property related to their favorable local error structure. In this thesis we consider the Peaceman--Rachford and Douglas--Rachford schemes, which were the first ADI methods to be constructed and to this day are the most representative members of the ADI method class.



We perform convergence studies for the Peaceman--Rachford and Douglas--Rachford schemes when applied to semilinear, dissipative evolution equations, that is, when the vector fields are given by the sum of a linear and a nonlinear dissipative operator. Optimal convergence orders are proven when the solution is sufficiently regular. With less regularity present we are still able to prove convergence, however of suboptimal order or without order. In contrast to previous convergence order analyses we do not assume Lipschitz continuity of the nonlinear operator.



In the context of linear, dissipative evolution equations we consider full space-time discretizations. We assume that the full discretization is given by combining one of the two aforementioned ADI methods with a general, converging spatial discretization method. In this setting we prove optimal, simultaneous space-time convergence orders.



Advection-diffusion-reaction models, encountered in physics, chemistry, and biology are important examples of dissipative evolution equations. In this thesis we present such a model describing the growth of axons in nerve cells. The model consists of a parabolic PDE, which has a non-trivial coupling to nonlinear ordinary differential equations via a moving boundary, which is part of the solution. Since additionally the biological model parameters imply a wide range of scales, both in time and space, the application of a numerical method is involved. We make an argument for a discretization consisting of a splitting which is integrated by the Peaceman--Rachford scheme. The choice is motivate by the results of some numerical experiments.

Abstract (Swedish)

Popular Abstract in Swedish

Partiella differentialekvationerna} är kraftfulla verktyg som kan användas för att beskriva fysikaliska fenomen inom bland annat naturvetenskap, teknik, ekonomi och medicin. Listan med tillämpningar kan göras hur lång som helst: Partiella differentialekvationer kan beskriva hur en snöflinga bildas, hur strukturer deformeras när de utsätts för mekaniska krafter, hur blodet flödar i hjärnans kapillärer, hur axontillväxten ser ut i nervceller och så vidare. Den sistnämnda tillämpningen återkommer vi till. Genom att använda partiella differentialekvationer för att skapa matematiska modeller av fysikaliska fenomen kan vi nå en djupare förståelse av komplexa processer. Dessutom är skapandet och analysen av en matematisk modell i allmänhet betydligt billigare än fysiska experiment.



Såsom antyds av listan med tillämpningar används partiella differentialekvationer ofta för att modellera dynamiska system definierade över ett område i rummet. Modeller av komplicerade processer där många fysikaliska fenomen samverkar leder ofta till stora ekvationssystem där varje obekant varierar med tid och rum. Sådana system av partiella differentialekvationer kan nästan aldrig lösas exakt. Istället används i praktiken numeriska metoder för att hitta approximativa lösningar med hjälp av datorernas enorma beräkningskapacitet. Givetvis är det av största vikt att metoderna som används är både effektiva och pålitliga. Att säkerställa detta är centralt i den forskning som genomförs inom numerisk analys.



I många fall kan system av partiella differentialekvationer vara så komplicerade att det inte är tänkbart att hitta en approximativ lösning till hela systemet på en gång. Istället delar man upp systemet i mindre problem och approximerar dem var för sig. Metoder som tillämpar denna idé kallas splittingmetoder. Givetvis införs ett approximationsfel när en sådan splitting genomförs. Vi måste alltså väga förenklade beräkningar mot ett ökat fel. För att kunna göra detta måste vi förstå oss på hur felet ser ut.



Många analyser av splittingfel har tidigare genomförts för olika sorters splittingapproximationer applicerade på olika familjer av partiella differentialekvationer. I forskningen som presenteras i denna uppsats analyserar vi de splittingmetoder som går under namnet alternative direction implicit methods (ADI-metoder). Dessa användes för första gången i början av 50-talet för att lösa värmeledningsproblem i flera dimensioner. Modellen gavs även där av en partiell differentialekvation och lösningstekniken var att alternera mellan de olika rumsdimensionerna och lösa ekvationen en dimension åt gången.



I vår forskning utvidgar vi felanalysen för ADI-metoder till nya familjer av partiella differentialekvationer. Vår analys täcker till exempel in modeller för skapandet av snöflingor och modeller för mönsterbildning i naturen. För dessa modeller och för många, många fler har vi nu en god förståelse för hur stort approximationsfel som skapas när en splitting genomförs.



Som nämndes tidigare modellerar partiella differentialekvationer ofta fysikaliska system som varierar både i tid och rum. ADI-metoderna approximerar lösningarnas variation med tiden. Men, för att kunna göra beräkningar på en dator måste dessa metoder kombineras med en metod som approximerar variationen i rummet. I vår forskning har vi därför dessutom analyserat sådana metodkombinationer. Analysen täcker till exempel in det ovan nämnda splittingförfarande för värmeledningsekvationen.



Vi har också genomfört en djupare analys av den tidigare nämnda tillämpningen angående axontillväxt i nervceller. I en sådan cell växer en lång, tubformad nervtråd ut från cellkroppen. Utväxten kallas axon och byggs upp av proteinet tubulin. Detta protein produceras i cellkroppen och färdas sedan längs med axonet för att slutligen monteras i andra änden av denna nervtråd. För att beskriva dessa processer skapar vi en matematiska modell som bland annat består av en partiell differentialekvation. Vi applicerar en ADI-metod för att hantera tubulinets förflyttning längs axonet separat från uppbyggnadsprocessen i axonets ände. Våra experiment visar att denna splittingmetod ger effektiva och pålitliga numeriska resultat.

• author: Henningsson, Erik
• supervisor: Eskil Hansen
• organization: Mathematics (Faculty of Engineering)
• publishing date: 2014
• type: Thesis
• publication status: published
• subject: Computational Mathematics
• pages: 97 pages
• ISBN: 978-91-7623-178-4
• ISBN: 978-91-7623-177-7
• language: English
• LU publication?: yes
• additional info: Only the Kappa of the Licentiate Thesis is open access. For the appended papers of the thesis, please see references to journals in the Kappa.
• id: 23f16a6d-38ad-4bc2-b274-04f334a22f08 (old id 8593777)
• alternative location: http://www.maths.lth.se/na/staff/erik/
• date added to LUP: 2016-04-01 13:53:04
• date last changed: 2018-11-21 20:20:49