线性互补问题模系矩阵分裂迭代方法的快速实现与应用

Linear complementarity problems may arise in many areas of economic, financial, control and mechanics, including market equilibrium, option pricing, traffic network equilibrium, free boundary problems, elastic contact problems and obstacle problems and so on. Hence, to study effective numerical methods and their actual implementations for linear complementarity problems is of important theoretical meaning and high applied value. The modulus-based matrix splitting iterative method has recently been proposed for solving large sparse linear complementarity problems. In this method, the linear complementarity problem is reformulated equivalently into a system of fixed-point equations, which makes it practical and effective in actual applications. In this project, we will mainly study the constructions, the theory analyses and the actual implementations of effective numerical algorithms based on the modulus-based matrix splitting iterative method for linear complementarity problems. In order to solve the larger scale problems and decrease the computing time, we will construct two class of numerical algorithms for linear complementarity problems: one is the multigrid algorithms by using the modulus-based matrix splitting iterative methods as smoothers and another is the asynchronous parallel implementations of modulus-based matrix splitting iterative methods. Moreover, we will study their convergence theory and apply them to solve the actual problems such as the dam seepage and the option pricing.

线性互补问题广泛地产生于经济、金融、控制和力学等诸多领域，如市场供需平衡、期权定价、交通网络平衡、自由边界问题、弹性接触问题和障碍问题等。因此，研究线性互补问题的高效数值解法及其具体实现具有重要的理论意义和很高的应用价值。模系矩阵分裂迭代方法是最近提出的用于求解线性互补问题的一种迭代方法。它是将线性互补问题等价转化为易于求解的线性方程组，在实际应用中易于实现且非常有效。本项目的目标是基于模系矩阵分裂迭代方法，研究求解线性互补问题高效数值算法的构造、理论分析和具体实现。为了提高求解问题的规模、减少求解时间，我们拟构造的数值算法有两类：一类是以模系矩阵分裂迭代方法为光滑子，构造多重网格算法；另一类是模系矩阵分裂迭代方法的异步并行实现。而且，我们还将分析这些算法的收敛性，并将其应用于大坝渗流和期权定价等实际问题的求解。

线性互补问题广泛地产生于经济、金融、控制和力学等诸多领域，如期权定价、网络平衡、自由边界问题和障碍问题等。因此，研究线性互补问题的高效数值解法具有重要的理论意义和很高的应用价值。本项目的主要研究成果分为三部分。第一部分是深入研究了模系矩阵分裂迭代方法的并行实现及收敛理论：针对H-矩阵线性互补问题，改进了两步模系矩阵多分裂迭代方法及其收敛性证明，数值结果显示该方法能够有效地减少各进程间的通信时间，使得整体求解时间下降；提出了一种新的方法来证明模系多分裂迭代方法的收敛性，充分利用了H-矩阵自身的性质，证明过程简洁，为其他类型的模系多分裂迭代方法的收敛性分析提供了新的思路。第二部分是建立了模系多分裂迭代方法关于M-矩阵的收敛理论：首先证明了M-矩阵的H-相容分裂也是正则分裂，但反之不成立；其次针对系数矩阵为M-矩阵的线性互补问题，建立了模系多分裂迭代方法关于正则分裂的收敛定理以及模系二级多分裂迭代方法关于外迭代为正则分裂和内迭代为弱正则分裂的收敛定理。第三部分是以模系松弛迭代方法为光滑子构造了模系多重网格方法求解线性互补问题：在理论分析方面，对模系二重网格方法进行了局部傅里叶分析，推导出了渐近收敛因子的计算公式，以此来估计模系多重网格方法的渐近收敛速度；在数值实验方面，将模系多重网格方法应用于多孔介质坝体渗流问题的求解，计算结果显示模系多重网格W-循环在收敛速度和计算时间上都能达到最优，而且渐近收敛因子的计算公式能准确地估计出模系多重网格W-循环的收敛速度。