Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-11T01:50:04.970Z 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

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

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 

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