Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T09:29:11.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Multigrid Methods with Newton-Gauss-Seidel Smoothing and Constraint Preserving Interpolation for Obstacle Problems

Published online by Cambridge University Press:  28 May 2015

Chunxiao Wu  and
Justin W.L. Wan
Chunxiao Wu
Affiliation:
Centre for Computational Mathematics in Industry and Commerce, University of Waterloo, Waterloo, Ontario, Canada
Justin W.L. Wan
Affiliation:
David R. Cheriton School of Computer Science and Centre for Computational Mathematics in Industry and Commerce, University of Waterloo, Waterloo, Ontario, Canada
Get access

Abstract

In this paper, we propose a multigrid algorithm based on the full approximate scheme for solving the membrane constrained obstacle problems and the minimal surface obstacle problems in the formulations of HJB equations. A Newton-Gauss-Seidel (NGS) method is used as smoother. A Galerkin coarse grid operator is proposed for the membrane constrained obstacle problem. Comparing with standard FAS with the direct discretization coarse grid operator, the FAS with the proposed operator converges faster. A special prolongation operator is used to interpolate functions accurately from the coarse grid to the fine grid at the boundary between the active and inactive sets. We will demonstrate the fast convergence of the proposed multigrid method for solving two model obstacle problems and compare the results with other multigrid methods.

Keywords

65M5565M2265F1065F50Multigrid methodobstacle problemelliptic variational inequalitycomplementarity problemHamilton-Jacobi-Bellman equationfull approximation scheme
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 8 , Issue 2 , May 2015 , pp. 199 - 219
Copyright
Copyright © Global-Science Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bellman, R.E.Introduction to the Mathematical Theory of Control Processes: Nonlinear processes. Mathematics in science and engineering. Academic Press, 1971.Google Scholar
[2]Brandt, Achi and Cryer, Colin W. Multigrid algorithms for the solution of linear complementarity problems arising from free boundary problems. SIAM journal on scientific and statistical computing, 4(4):655–684, 1983.CrossRefGoogle Scholar
[3]Caffarelli, Luis A. The obstacle problem revisited. Journal of Fourier Analysis and Applications, 4(4):383–402, 1998.CrossRefGoogle Scholar
[4]Clarke, F. Optimization and nonsmooth analysis wiley. New York, 1983.Google Scholar
[5]Figueiredo, Isabel Narra, Rodrigues, José Francisco, and Santos, . Free Boundary Problems: Theoryand Applications, volume 154. Springer, 2007.CrossRefGoogle Scholar
[6]Glowinski, R, Lions, Jacques Louis, and Trémoliéres, Raymond. Numerical analysis of variational inequalities, 1981.Google Scholar
[7]Glowinski, Roland. Lectures on Numerical Methods for Non-Linear Variational Problems. Springer, 2008.Google Scholar
[8]Hackbusch, Wolfgang and Mittelmann, Hans Detlef. On multi-grid methods for variational inequalities. Numerische Mathematik, 42(1):65–76, 1983.CrossRefGoogle Scholar
[9]Hintermüller, Michael and Kunisch, Karl. Path-following methods for a class of constrained minimization problems in function space. SIAM J. Optim., 17(1):159–187, 2006.CrossRefGoogle Scholar
[10]Hoppe, Ronald H.W.Multigrid algorithms for variational inequalities. SIAM journal on numerical analysis, 24(5):1046–1065, 1987.CrossRefGoogle Scholar
[11]Howard, Ronald A.. Dynamic Programming and Markov Process. MIT Press, Cambridge, MA, USA, 1960.Google Scholar
[12]Ito, Kazufumi and Kunisch, Karl. Semi-smooth Newton methods for variational inequalities of the first kind. Mathematical Modelling and Numerical Analysis, 37(1):41–62, 2003.CrossRefGoogle Scholar
[13]Kornhuber, Ralf. Monotone multigrid methods for elliptic variational inequalities I. Numerische Mathematik, 69:167–167, 1994.CrossRefGoogle Scholar
[14]Lions, P.-L. and Mercier, B.Approximation numerique des equations Hamilton-Jacobi-Bellman. RAIRO – Analyse numerique, 14(4):369–393, 1980.CrossRefGoogle Scholar
[15]Moré, Jorge J. Global convergence of newton-gauss-seidel methods. SIAM Journal on Numerical Analysis, 8(2):325–336, 1971.CrossRefGoogle Scholar
[16]O’Leary, Dianne P. Conjugate gradient algorithms in the solution of optimization problems for nonlinear elliptic partial differential equations. Computing, 22(1):59–77, 1979.CrossRefGoogle Scholar
[17]Oosterlee, Cornelis W. On multigrid for linear complementarity problems with application to American-style options. Electronic Transactions on Numerical Analysis, 15(165–185):2–7, 2003.Google Scholar
[18]Qi, Liqun and Sun, Jie. A nonsmooth version of Newton’s method. Mathematical programming, 58(1–3):353–367, 1993.CrossRefGoogle Scholar
[19]Rodrigues, J-F. Obstacle problems in mathematical physics, volume 134. North Holland, 1987.CrossRefGoogle Scholar
[20]Tai, Xue-Cheng. Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities. Numerische Mathematik, 93(4):755–786, 2003.CrossRefGoogle Scholar