Operator splitting methods for pricing American op

ReportsoftheDepartmentofMathematicalInformationTechnologySeriesB.Scienti£cComputingNo.B11/2004OperatorSplittingMethodsforPricingAmericanOptionswithStochasticVolatilitySamuliIkonenJariToivanenUniversityofJyv¨askyl¨aDepartmentofMathematicalInformationTechnologyP.O.Box35(Agora)FIN–40014UniversityofJyv¨askyl¨aFINLANDfax+358142602731£/Copyrightc°2004SamuliIkonenandJariToivanenandUniversityofJyv¨askyl¨aISBN951­39­1980­3ISSN1456­436XOperatorSplittingMethodsforPricingAmericanOptionswithStochasticVolatilitySamuliIkonen¤JariToivanen¤AbstractStochasticvolatilitymodelsleadtomorerealisticoptionpricesthantheBlack-Scholesmodelwhichusesaconstantvolatility.Basedonsuchmodelsatwo-dimensionalparabolicpartialdi®erentialequationcanderivedforoptionprices.DuetotheearlyexercisepossibilityofAmericanoptioncontractsthearisingpricingproblemsarefreeboundaryproblems.InthispaperweconsiderthenumericalpricingofAmericanoptionswhenthevolatilityfollowsastochasticprocess.Weproposeoperatorsplittingmethodsforperformingtimesteppingaftera¯nitedi®erencespacediscretizationisdone.Theideaistodecouplethetreat-mentoftheearlyexerciseconstraintandthesolutionofthesystemoflinearequationsintoseparatefractionaltimesteps.Withthisapproachwecanuseanye±cientnumericalmethodtosolvethesystemoflinearequationsinthe¯rstfractionalstepbeforemakingasimpleupdatetosatisfytheearlyexerciseconstraint.OuranalysissuggeststhattheCrank-Nicolsonmethodandtheop-eratorsplittingmethodbasedonithavethesameasymptoticorderofaccuracy.Thenumericalexperimentsshowthattheoperatorsplittingdoesnotincreaseessentiallytheerror.Theyalsodemonstratethee±ciencyoftheoperatorsplit-tingmethodswhenamultigridmethodisusedforsolvingthesystemsoflinearequations.Keywords:Americanoptionpricing,stochasticvolatilitymodel,operatorsplit-tingmethod,timediscretization,multigridmethod,linearcomplementarityprob-lem1IntroductionTheoptionpricesobtainedusingtheBlack-Scholesmodel[2]withaconstantvolatilityarenotconsistentwithobservedoptionprices.Onepossibleremedyistomakethevolatilitytobeafunctionoftimeandstrikeprice.Bycalibratingthisfunctionconsis-tentoptionpricescanbeobtained.Anotherapproachistoassumethatthevolatilityofthepriceprocessisalsostochastic.Suchmodelshavebeenconsideredforexample¤DepartmentofMathematicalInformationTechnology,POBOX35(Agora),FIN-40014UniversityofJyvÄaskylÄa,Finland,[e-mail],[e-mail]1in[1],[13],[17],[18].Inthispaper,wewillusethestochasticvolatilitymodelintro-ducedbyHestonforpricingAmericanoptions[17].Thismodelseemstobeconsistentwithmarketprices.Forexample,Dr¸agulescuandYakovenkoshowedthatthetime-dependentprobabilitydistributionofstockpricechangesgeneratedbyHeston'smodelisingoodagreementwiththeDow-Jonesindexafterthecalibrationoftheparametersappearinginthemodel[10].ThepriceofEuropeanoptionscanbecalculatedusinganalyticalexpressionsforHeston'smodel[17].TheearlyexercisepossibilityofAmericanoptionsleadstonon-linearfreeboundaryproblemsdescribedbypartialdi®erentialinequalitieswhicharealsocalledindi®erentdisciplinesasvariationalinequalities,linearcomplementar-ityproblemsandobstacleproblems.NousefulanalyticalmethodsareavailableforpricingAmericanoptionsand,thus,numericalmethodsareusedtoapproximatetheprices.AlreadyBrennanandSchwartzproposeda¯nitedi®erencediscretizationfortheone-dimensionalBlack-ScholesequationandthenadirectsolutionmethodforpricingAmericanoptions[4].Heston'smodelhasanadditionalspacevariablerelatedtothevolatility.Innumericalapproximationsitisusuallychosentobethevarianceofthepriceprocess,whichisthesquareofthevolatility.Thisadditionalvariablemakesthediscretizationandsolutionproceduresmorecomplicatedaswellascomputationallymoreexpensive.Inthefollowingwereviewthreepapersandonereportwhichhaveconsideredsuchoptionpricingproblems.ClarkeandParrottconsideredthediscretizationofapartialdi®erentialinequalityforthepriceofanAmericanoptionusing¯nitedi®erencesforspacederivativesandaslightlystabilizedCrank-Nicolsonmethodforthetimederivative[7],[8].Theyper-formedacoordinatetransformationtoincreasetheaccuracyofthespacediscretizationwithuniformgridstepsizes.Theyproposedaspecialversionofaprojectedfullap-proximationscheme(PFAS)multigrid[3]forthesolvingarisinglinearcomplementarityproblems.TheirmethodusesaspecialprojectedlineGauss-Seidelsmootherwhichinpartmadetheconsideredmethodrathercomplicatedandproblemspeci¯c.Thead-vantageofsuchamultilevelmethodisthatthenumberofiterationsrequiredtosolvealinearcomplementarityproblemisessentiallyindependentofthegridstepsizeand,thus,thecomputationalcostofthisiterativesolutionisofoptimalorder.Zvan,Forsyth,andVetzaldiscretizedthepartialdi®erentialinequalityusing¯niteelement/volumemethodtogetherwithanonlinear°uxlimiterforconvectionterms[28].Theyformulatedlinearcomplementarityproblemsusingnonlinearpenaltyterms.ThesolutionsofthearisingnonlinearproblemswereobtainedwithaninexactNew-tonmethodandthelinearproblemswithapproximateJacobiansweresolvedwithanincompleteLUpreconditionedCGSTABmethod.ThemethodproposedbyZvan,ForsythandVetzalissimplerthantheonebyCl