线性互补问题的数值分析

Numerical Analysis on Linear Complementarity Problems

综述了线性互补问题理论的最新发展和已有成果,包括线性互补问题的数值解法,特别是模基矩阵分析算法、误差分析以及扰动分析.给出了线性互补问题的数学问题形式、数学模型以及相关概念;介绍了求解线性互补问题的各种数值解法,其中重点关注迭代法特别是近年来比较热门的模基矩阵分裂迭代法,基于模方程通过运用非光滑Newton法的思想,给出了模基非光滑Newton法,新算法比已有的模基矩阵分裂迭代法收敛更快;给出了线性互补问题解的误差分析,介绍了已有的几个误差界结果,包括运用预处理技术得到的更好的新误差界.同时介绍了线性互补问题解扰动分析的结果及目前最新的扰动界.

The latest progress in the study on LCPs are rithms for solving LCPs such as the modules-based matrix summarized. In particularly, some new numerical algosplitting methods are introduced. Some new results in the error analysis and perturbation analysis are summarized. At first, the linear complementarity problem is presented with its mathematical models and some notations. Secondly, the numerical algorithms for solving the linear complementarity problem are given. The iteration methods especially the module-based matrix splitting iteration methods proposed these years are summarized. Based on module equations, by introducing the idea of nonsmooth Newton＇s method, the modules-based nonsmooth Newton＇s method is established, which converges faster than the existing module-based matrix splitting iteration methods. Then the error analysis of the solution of the linear complementarity problem is given with the new error bounds based on preconditioned technique, which is better than the error bounds given before. The results of the perturbation analysis of the solution of the linear complementarity problem are shown with the latest perturbation bounds.