The Study Of Numerical Methods For Solving Linear Complementarity Problems

Linear complementarity problem is a unified framework of the linear and quadratic programming problems.It plays a key role in the fields of scientific computing and engineering,such as American option pricing model,the free boundary problems,traffic network equilibrium problems and image processing.The linear complementarity problem in these fields often involve large sparse matrices.Therefore,numerical methods of solving the large and sparse linear complementarity problems have attracted more and more attention.The study of numerical method for solving linear complementarity problems has a long history,and many classical algorithms have been proposed,most of which originated from solving linear equations.For example,the projected successive overrelaxation methods,multisplitting iteration methods,and so on.At present,the most popular kind of methods are the modulus-based matrix splitting iteration methods,which are based on the equivalence between linear complementarity problem and absolute value equation.Firstly,the linear complementarity problem is transformed into absolute value equation,and then corresponding iteration scheme is designed.In this dissertation,we propose two kinds of modulus-based matrix splitting iteration method for linear complementarity problems,and analyze their convergence.Some numerical examples are presented to confirm the effectiveness.This paper is organized as follows:In the first chapter,we mainly introduce the research background,the current research status,some basic concepts and lemmas,and some classical method for solving linear complementarity problem are given.In the second chapter,based on two-sweep modulus-based matrix splitting iteration method,the general two-sweep modulus-based matrix splitting iteration method is proposed,and the convergence of the method is analyzed when the system matrix is H_+-matrix.Finally,numerical experiments have presented to show the effectiveness of the new method and the accuracy of the convergence theory.In the third chapter,by constructing two-step iteration scheme,the preconditioned general two-step modulus-based matrix splitting iteration method is proposed,the convergence theory is established when the system matrix is an H_+-matrix.In some special cases,the range of parameters is given.Numerical experiments further confirm the effectiveness of the method.In the end,the whole dissertation is summarized and the possible research directions in the future are prospected.