Iterative solution of Piecewise Linear Systems for the numerical solution of obstacle problems

We investigate the use of piecewise linear systems, whose coecient matrix is a piecewise constant function of the solution itself. Such systems arise, for example, from the numerical solution of linear complementarity problems and in the numerical solution of free-surface problems. In particular, we here study their application to the numerical solution of both the (linear) parabolic obstacle problem and the obstacle problem. We propose a class of eective semi-iterative Newton-type methods to nd the exact solution of such piecewise linear systems. We prove that the semi-iterative Newton-type methods have a global monotonic convergence property, i.e., the iterates converge monotonically to the exact solution in a nite number of steps. Numerical examples are presented to demonstrate the eectiveness of the proposed methods.