线性互补问题的数值求解算法研究

论文摘要

线性互补问题是线性规划和二次规划的统一框架,它在美式期权定价模型、自由边界问题、交通网络平衡问题及图像处理等众多科学计算和工程领域都有重要应用.而这些领域中的线性互补问题,所涉及的矩阵往往是大型稀疏的,因此,大型稀疏线性互补问题的数值求解算法研究越来越受到人们的重视.线性互补问题的数值求解算法研究历史悠久,由此也有很多经典的算法被提出,其中有相当一部分是源于求解线性方程组的算法,例如投影超松弛算法、多重分裂迭代法等.目前比较受欢迎的一类算法是模系矩阵分裂迭代法,该算法是基于线性互补问题与绝对值方程的等价性,先将线性互补问题转化为绝对值方程,然后再设计出相应的迭代格式.本文主要针对线性互补问题,提出了两类模系矩阵分裂迭代法,并分析了各自的收敛性,通过数值算例证明了算法的有效性.本文组织结构如下:第一章,主要介绍了互补问题的研究背景、研究现状及一些基本概念,相关引理,并给出了已有的求解线性互补问题的经典算法.第二章,在双扫描模系矩阵分裂迭代法的基础上,对算法加以推广,得到了广义的双扫描模系矩阵分裂迭代法,并分析了系统矩阵为H+-矩阵时算法的收敛性,最后通过数值实验证明了算法的有效性和理论结果的正确性.第三章,通过构造两步迭代格式,提出了一类预处理的广义两步模系矩阵分裂迭代法,讨论了其系统矩阵为H+-矩阵情形下的收敛性.在某种特殊情况下还给出了参数的取值范围.数值实验也证明了算法的有效性.第四章,对全文进行了总结,并对今后的研究方向作了展望.

论文目录

• 摘要
• abstract
• 第1章 绪论
•   1.1 研究背景
•   1.2 研究现状
•     1.2.1 线性互补问题的研究现状
•     1.2.2 非线性互补问题的研究现状
•   1.3 预备知识
•   1.4 求解互补问题的经典算法
•     1.4.1 投影法
•     1.4.2 模系矩阵分裂迭代法
•   1.5 本文主要工作
• 第2章 广义双扫描模系矩阵分裂迭代法
•   2.1 引言
•   2.2 广义双扫描模系矩阵分裂迭代法
•   2.3 收敛性分析
•   2.4 数值实验
•   2.5 结论
• 第3章 预处理的广义两步模系矩阵分裂迭代法
•   3.1 引言
•   3.2 预处理的广义两步模系矩阵分裂迭代法
•   3.3 收敛性分析
•   3.4 数值实验
•   3.5 结论
• 第4章 结论与展望
•   4.1 结论
•   4.2 展望
• 致谢
• 参考文献
• 攻读学位期间的研究成果

文章来源

类型: 硕士论文

作者: 任欢

导师: 汪祥

关键词: 线性互补问题,模系矩阵分裂迭代法,矩阵,收敛性

来源: 南昌大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 南昌大学

分类号: O241.6

DOI: 10.27232/d.cnki.gnchu.2019.000214

总页数: 51

文件大小: 1971K

下载量: 75