Numerical Approach on American Options: with focus on initial guesses and computational speed

Indtil nu er der ikke udledt nogen analytisk prisformel for for amerikanske put optioner. Denne kendsgerning har ført til flere numeriske tilnærmelsesmetoder. I Black-Scholes-modellen har vi beskrevet værdifunktionen for den amerikanske put option som et optimalt stoppetidsproblem. Vi har derefter angivet løsningen af ​​det optimale stoppetidsproblem som et free-boundary problem. Dette free-boundary problem fører os til den free-boundary equation, der beskriver værdifunktionen gennem den optimale exercise boundary. Free-boundary equation er en kendt type af Volterra integralligning, som kan tilnærmes ved successive metoder. Til at løse free-boundary integralligningen har vi brugt en iterativ fixed-point metode til at tilnærme den optimale exercise boundary. Denne metode kræver et initial guess. Dette projekt handler specifikt om, hvordan forskellige initial guess påvirker den samlede beregningshastighed. Metoden vi præsenterer er vist til at kunne beregne amerikanske præmier op til en 8-cifret præcision, og vi diskuterer otte forskellige initial guess. Hvert initial guess vil enten kræve at løse et system med to ikke-lineære ligninger, løse én ikke-lineær ligning eller kræve ikke at løse nogen ligninger overhovedet. Ved at løse ikke-lineære ligninger reducerer vi det antal iterationer, der er nødvendige for en tilfredsstillende tilnærmelse. I vores implementering fandt vi, at den højeste beregningsmæssige hastighed opnås ved ikke at løse nogen ligninger og således arbejde med en ren iterativ metode. Vi fandt ud af, at et initial guess af konstant strike pris beregner den optimale boundary omkring dobbelt så hurtig som at løse én ikke-lineær ligning og tæt på en faktor 1000 hurtigere end vores mest krævende initial guess. Initial guess 'QD +', der løser én ikke-lineær ligning, er vist i litteraturen at være i stand til at overgå den rene iterative metode. Selvom vi ikke kunne eftervise dette, fandt vi et initial guess, som beregner hurtigere end QD + på alle præc
To this day no closed-form analytical price formula for American put options has been derived. This fact has lead to several numerical approximation methods. In the Black-Scholes model we have described the value function for the American put option as an optimal stopping problem. We have then stated the solution of the optimal stopping problem as a free-boundary problem. This free-boundary problem lead us to the free-boundary equation which describes the option value through the optimal exercise boundary. The free-boundary equation is a known type of Volterra integral equation, and it is approximable by successive methods. To solve the free-boundary integral equation we have used an iterative fixed-point method to approximate the optimal exercise boundary. This method requires an initial guess. The focus of this paper is specifically on how different initial guesses influence on the total computational speed. The method we present is shown to compute American premiums up to an 8 digit precision, and we discuss eight different initial guesses. Each initial guess will either require solving a system of two non-linear equations, solving one non-linear equation or require solving no equations at all. By solving non-linear equations we reduce the required number of iterations needed for a satisfactory approximation. In our implementation we found that the highest computational speed is obtained by solving no equations, and thus working with a pure iterative method. We found that an initial guess of constant strike price computed the optimal exercise boundary about twice as fast as solving one non-linear equation, and close to a factor 1000 faster than our most demanding initial guess. The initial guess ’QD+’, solving one non-linear equation, is in literature shown to be able to outperform the pure iterative method. Even though we were not able to justify this we found an initial guess which computes faster than the QD+ at every precision level, with the same level o