Two-grid algorithms for pricing American options by a penalty method

Main Article Content

Miglena Koleva Radoslav Valkov


In this manuscript we present two-grid algorithms for the American option pricing problem with a smooth penalty method where the variational inequality, associated with the optimal stopping time problem, is approximated with a nonlinear Black-Scholes equation. In order to compute the numerical solution of the latter unconstrained problem we must solve a system of nonlinear algebraic equations resulting from the discretization by e.g. the finite difference or the finite element method. We propose two-grid algorithms as we first solve the nonlinear system on a coarse grid with mesh size $h^c$ and further a linearized system on a fine grid with mesh size $h^f$, satisfying $h^f=\mathcal{O}((h^c)^{2^k}), \; k=1,2,\dots$, where $k$ is the number of Newton iterations. Numerical experiments illustrate the computational efficiency of the algorithms.

Article Details

How to Cite
Koleva, M., & Valkov, R. (2016). Two-grid algorithms for pricing American options by a penalty method. Proceedings Of The Conference Algoritmy, , 275-284. Retrieved from


[1] O. Axelsson, On mesh independence and Newton methods, Appl. Math., 38(4-5) (1993), pp. 249-265.

[2] P.A. Forsyth, and K.R. Vetzal, Quadratic convergence for valuing American options using a penalty method, SIAM J. Sc. Comput., 23(6) (2002), pp. 2095-2122.

[3] C. Grossmann, and H.-G. Roos, Numerical Treatment of Partial Differential Equations, 3d edition, Springer-Verlag Berlin Heidelberg (2007).

[4] T.B. Gyulov, and R.L. Valkov, American option pricing problem transformed on finite interval, Int. J. Comp. Math., DOI: 10.1080/00207160.2014.906587 (2014).

[5] T. Haentjens, and K.J. in ’t Hout, Alternating direction implicit finite difference schemes for the Heston-Hull-White partial differential equation, J. Comp. Fin., 16(1) (2012), pp. 83-110.

[6] P. Jaillet, D. Lamberton, and B. Lapeyre, Variational inequalities and the pricing of American options, Acta Appl. Math., 21(3) (1990), pp. 263-289.

[7] A.Q.M. Khaliq, D.A. Voss, and S.H.K. Kazmi, A linearly implicit predictor-corrector scheme for pricing American option using a penalty method approach, J. Banking & Fin., 30 (2006), pp. 489-502.

[8] M.N. Koleva, and L.G. Vulkov, Two-grid quasilinearization approach to ODEs with applications to model problems in physics and mechanics, Comp. Phys. Commun., 181(2011), pp. 663-670.

[9] M. Lauko, and D. Ševčovič, Comparison of numerical and analytical approximations of the early exercise boundary of American put option, ANZIAM J. 51 (2010), pp. 430-448.

[10] K. Mikula, D. Ševčovič, and B. Stehlíková, Analytical and Numerical Methods for Pricing Financial Derivatives, Nova Science Publishers Inc., Hauppauge (2011).

[11] B.F. Nielsen, O. Skavhaug, and A. Tveito, Penalty and front-fixing methods for the numerical solution of American option problems, J. Comp. Fin., 5(4) (2001), pp. 69-97.

[12] B.F. Nielsen, O. Skavhaug, and A. Tveito, Penalty methods for the numerical solution of American multi-asset option problems, J. Comp. Appl. Math., 222 (2008), pp. 3-16.

[13] L.G. Vulkov, and A.I. Zadorin, Two-Grid algorithms for an ordinary second order equation with an exponential boundary layer in the solution, Int. J. Numer. Anal. Modelling, 7(3) (2010), pp. 580-592.

[14] J. Wang, and P.A. Forsyth, Maximal use of central differencing for Hamilton-JacobiBellman PDEs in finance, SIAM J. Numer. Anal., 46(3) (2008), pp. 1580-1601.

[15] J. Xu, Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal., 33 (1996), pp. 1759-1777.

[16] K. Zhang, and S. Wang, Convergence property of an interior penalty approach to pricing American option, J. Industr. Managem. Optim., 7 (2011), pp. 435-447.