Efficient Numerical Methods for Pricing American O

ReportsoftheDepartmentofMathematicalInformationTechnologySeriesB.ScienticComputingNo.B12/2005EfcientNumericalMethodsforPricingAmericanOptionsUnderStochasticVolatilitySamuliIkonenJariToivanenUniversityofJyv¨askyl¨aDepartmentofMathematicalInformationTechnologyP.O.Box35(Agora)FI–40014UniversityofJyv¨askyl¨aFINLANDfax+358142602731/Copyrightc°2005SamuliIkonenandJariToivanenandUniversityofJyv¨askyl¨aISBN951­39­2349­5ISSN1456­436XEfcientNumericalMethodsforPricingAmericanOptionsUnderStochasticVolatilitySamuliIkonen¤JariToivanen¤AbstractFivenumericalmethodsforpricingAmericanputoptionsunderHeston'sstochasticvolatilitymodelaredescribedandcompared.Theoptionpricesareobtainedasthesolutionofatwo-dimensionalparabolicpartialdifferentialin-equality.AnitedifferencediscretizationonnonuniformgridsleadingtolinearcomplementarityproblemswithM-matricesisproposed.TheprojectedSOR,aprojectedmultigridmethod,anoperatorsplittingmethod,apenaltymethod,andacomponentwisesplittingmethodareconsidered.Thelastoneisadirectmethodwhileallothermethodsareiterative.Theresultingsystemsoflinearequationsintheoperatorsplittingmethodandinthepenaltymethodaresolvedusingamultigridmethod.Theprojectedmultigridmethodandthecomponen-twisesplittingmethodleadtoasequenceoflinearcomplementarityproblemswithone-dimensionaldifferentialoperatorswhicharesolvedusingtheBrennanandSchwartzalgorithm.Thenumericalexperimentscomparetheaccuracyandspeedofthecon-sideredmethods.Theaccuraciesofallmethodsappeartobesimilar.Thus,theadditionalapproximationsmadeintheoperatorsplittingmethod,inthepenaltymethod,andinthecomponentwisesplittingmethoddonotincreasetheerroressentially.Thecomponentwisesplittingmethodisthefastestone.Allmultigridbasedmethodshavesimilarrapidgridindependentconvergencerates.Theyarefromtwotofourtimesslowerthatthecomponentwisesplittingmethod.OnthecoarsestgridthespeedoftheprojectedSORiscomparablewiththemultigridmethodswhileonnergridsitisseveraltimesslower.Keywords:Americanoptionpricing,stochasticvolatilitymodel,linearcomple-mentarityproblem,nitedifferencemethod,operatorsplittingmethod,multigridmethod,penaltymethod¤DepartmentofMathematicalInformationTechnology,UniversityofJyv¨askyl¨a,POBox35(Agora),FI-40014UniversityofJyv¨askyl¨a,Finland,[e-mail],[e-mail]11IntroductionThevaluationofnancialoptionsleadstomathematicalmodelswhichareoftenchallengingtosolve.Sincetheseminalpaper[4]byBlackandScholesin1973,em-piricalevidencehasshowntheirassumptiononthelog-normalityofthevalueoftheunderlyingassettobeoversimplifyingformostofassetclasses.Thishasledtomoresophisticatedmodelsforthevalueoftheunderlying.Examplesofthesearevalueandtimedependentvolatilityfunctions[15],jumpprocessesforthevalue[11],[30],theircombinations[2],stochasticvolatilitymodels[18],[20],andstochas-ticvolatilitymodelswithjumps[14].AnAmericanoptioncanbeexercisedatanytimeduringthelifeoftheoptionwhileaEuropeanoptioncanbeexercisedonlyattheexpirydate.TheearlyexercisepossibilityleadstoaconstraintforthevalueoftheAmericanoption.Thisconstraintrequiresspecialtreatmentwhichmakesusuallyanalyticalformulasintractableandalsothenumericalvaluationmorecomplicated.BasedtheBlackandScholespar-tialdifferentialequation(PDE)BrennanandSchwartzpriceAmericanoptionsin[6].Afteranitedifferencediscretizationtheyproposedadirectmethodforthetreatmentoftheearlyexerciseconstraint.InthispaperwestudyefcientnumericalmethodsforpricingAmericanputoptionswithHeston'sstochasticvolatilitymodel[20].Theoptionpricingmodelisbasedonatwo-dimensionalparabolicPDEwithvariablecoefcients.Duetotheearlyexercisepossiblity,themodelisatimedependentlinearcomplementarityproblem(LCP).ThemainpurposeofthispaperistocomparethecomputationalefciencyofvenumericalsolutionmethodsfortheLCPwhicharementionedinthefollowing.Inadditiontothis,wederiveadiscretizationwithgoodpropertiesandwemakeimprovementstosomeofthemethods.TheprojectedSOR(PSOR)methodisthemostwell-knowwhilethepenaltymethodandprojectedmultigridmethodshavebeenappliedmorerecentlyintheoptionpricing.Theoperatorsplit-tingmethodandthecomponentwisesplittingmethodhavebeenproposedbytheauthorsin[24],[25],[26].Weproposeanitedifferencespacediscretizationonanonuniformgridresult-inganM-matrix.Thecross-derivativetermisapproximatedwithaspecialnitedifferenceschemeandtherst-orderandthesecond-orderpartialderivativesareapproximatedusingusualnitedifferences.Inordertoobtainnonpositivecodiag-onalelements,werestrictthegridstepsizesandweuseone-sideddifferencesfortheconvectiontermsinasmallpartofthedomain.Thelocationsofthegridpointsarecomputedusinggridgeneratingfunctionswhichconcentratemoregridpointsnearthepointwheretheoptionpriceisrequired.TheRannachertime-stepping[35]isusedforthetimediscretization.TheprojectedSORmethodintroducedin[12]hasbeenusedwidelyforpricingAmericanoptions;see,forexample,[37],[39],[43].TheconvergencerateofthePSORmethoddeteriorateswhenthediscretizationisrenedwhichmakesitslowonnergrids.Westudythechoiceoftherelaxationparameter,sinceithasasignicantimpactontheconvergencerate.2Thepr