大稀疏鞍点线性系统的迭代解法

论文题目: 大稀疏鞍点线性系统的迭代解法

论文类型: 博士论文

论文专业: 计算机软件与理论

作者: 李铮

导师: 李长军

关键词: 鞍点线性系统,算法,广义算法,算法,两参数广义算法,预优共轭梯度算法,方程,代数重建,加权最小范数准则,共轭梯度重建算法

文献来源: 东北大学

发表年度: 2005

论文摘要: 鞍点线性系统是一类对称不定的线性系统，它来源于鞍点型偏微分方程问题、最优化问题、最小二乘问题等研究领域．实际应用中导出的这类系统通常都是大规模的，并且系数矩阵具有稀疏性，因此应采用迭代法进行求解．然而，鞍点线性系统本身特殊的结构特点使得一些著名的算法，诸如逐次超松弛迭代法(SOR)或共轭梯度法(CG)均失去效力．因此寻求解决大稀疏鞍点线性系统的有效的迭代解法具有重要的现实意义． 目前为人们所熟知的Uzawa算法和MINRES算法是两类求解鞍点线性系统的有效方法．Uzawa算法格式简单，但收敛速度较慢．MINRES算法计算效率高，但计算格式比较复杂．寻求具有更简单的计算格式或者更快收敛速度的迭代算法，成为热门的研究课题． 经典的SOR算法同样具有格式简单、存储量小的特点，因而早为人们所关注．近年来有学者开始研究广义化的SOR算法来求解鞍点线性系统．李长军等学者于1998年首次提出了一种广义化的SOR算法：GSOR算法．Golub等学者于2001年提出了SOR-like算法．这两种算法本质相同，因此我们将其统称为广义化SOR方法．这类算法具有同Uzawa算法一样简单的计算格式，并带有一个预优矩阵． 本文首先对SOR-like算法重新进行了深入的研究，采用比较初等的方法详细地刻划了SOR-like算法迭代矩阵谱半径的基本特征；给出了SOR-like算法最优迭代参数以及迭代矩阵谱半径的显式表达式；进一步证明了，通过选取合适的预优矩阵，可以使SOR-like算法的迭代矩阵只含有实特征值，从而可以采用Chebyshev多项式加速．这一结果是令人振奋的，丰富了D．M．Young的超松弛理论；同时我们还更正了Golub在2001年关于SOR-like算法的收敛性分析中出现的错误． 基于对SOR-like算法的理论分析，我们深入研究采用Chebyshev多项式对SOR-like算法进行加速，从而给出了GSOR-SI算法．理论分析和数值计算表明，这一算法具有和SOR-like算法相近的计算开销，却拥有比SOR-like算法快得多的收敛速度． 针对鞍点线性系统的特有的结构特点，我们提出两种含有两个迭代参数的广义化SOR算法，即GAOR算法和TPGSOR算法．给出了TPGSOR算法的最优参数的显式表达式以及相应的最优迭代矩阵谱半径的显式表达式．TPGSOR算法的计算格

论文目录:

声明

中文摘要

ABSTRACT

第一章 引言

1.1 背景

1.1.1 鞍点线性系统的来源

1.1.2 鞍点线性系统的特点

1.2 研究现状

1.2.1 两种已知的算法

1.2.2 广义SOR方法

1.2.3 PCG算法

1.3 本文所研究的主要内容及结构

第二章 SOR-like算法

2.1 广义SOR方法

2.2 SOR-like算法

2.2.1 收敛条件

2.2.2 若干记号和引理

2.2.3 主要结果

2.3 小结

第三章 SOR-like算法的Chebyshev加速

3.1 Scaling技术以及最优迭代参数的选取

3.2 对SOR-like算法的Chebyshev多项式加速

3.2.1 GSOR-SI算法

3.2.2 情形Ⅰ

3.2.3 情形Ⅱ

3.2.4 渐进收敛率

3.3 小结

第四章 两参数广义SOR方法

4.1 TPGSOR算法

4.1.1 TPGSOR算法的导出

4.1.2 基本函数方程

4.1.3 收敛性分析

4.1.4 最优参数的选取

4.2 GAOR算法

4.2.1 GAOR算法的函数方程

4.2.2 GAOR算法的收敛条件

4.3 小结

第五章 预优共轭梯度算法

5.1 关于预优共轭梯度算法

5.2 采用共轭梯度算法解鞍点线性系统

5.2.1 共轭梯度算法

5.2.2 CG算法与Uzawa算法的敛速比较

5.2.3 PCG算法与SOR-like算法的敛速比较

5.2.4 PCG算法与GSOR-SI算法的敛速比较

5.3 特征值估计与预优矩阵的选取

5.3.1 特征值估计和条件数估计

5.3.2 预优矩阵的选取

5.4 小结

第六章 定常Stokes方程

6.1 关于定常Stokes方程

6.1.1 定常Stokes方程的混合有限元法

6.1.1.1 混合广义解

6.1.1.2 Inf-sup条件

6.1.2 定常Stokes方程的混合元格式

6.1.2.1 Q1-P0元

6.1.2.2 Q2-P1元

6.2 数值实验

6.3 小结

第七章 基于最优准则的CT代数重建算法

7.1 CT重建问题概述

7.1.1 CT断层扫描过程大意

7.1.2 CT重建算法理论的概况

7.2 CT代数重建模型

7.3 基于最优准则的代数重建算法

7.3.1 若干最优准则

7.3.1.1 最小二乘准则

7.3.1.2 平滑准则

7.3.2 加权最小2-范数准则

7.3.3 基于加权最小2-范数准则的共轭梯度代数重建算法

7.4 数值仿真实验

7.4.1 仿真模型

7.4.2 数值仿真实验结果

7.5 小结

第八章 总结与展望

8.1 总结

8.2 展望

附录A 头模型投影数据的模拟

参考文献

本人攻读博士学位期间发表论文情况

致谢

发布时间: 2006-10-25

参考文献

• [1].一类切换线性系统的分析与控制[D]. 宋杨.南京理工大学2006
• [2].离散时间切换线性系统的优化镇定研究[D]. 程福亨.华南理工大学2017
• [3].切换线性系统的分段聚合与优化设计[D]. 祝庚.华南理工大学2012
• [4].基于连续—离散二维模型的周期系数线性系统鲁棒重复控制设计[D]. 周兰.中南大学2011
• [5].具有不完整模式信息的Markovian跳跃系统的鲁棒滤波和控制[D]. 魏延岭.哈尔滨工业大学2014
• [6].时滞线性系统的预见控制[D]. 廖永龙.北京科技大学2018
• [7].H_∞控制理论中几个基本结论的数学结构[D]. 徐跃良.西南交通大学2014
• [8].具有有限频性能的控制系统鲁棒优化设计[D]. 张晓妮.东北大学2011
• [9].基于滑模技术的不确定线性系统的容错控制方法研究[D]. 郝立颖.东北大学2013
• [10].基于动态补偿的线性系统最优控制[D]. 刘蕾.天津大学2011

相关论文

• [1].线性方程组分裂迭代法与广义鞍点问题Uzawa算法研究[D]. 吴静.电子科技大学2009
• [2].线性方程组和鞍点问题的迭代法与预处理技术研究[D]. 张理涛.电子科技大学2009
• [3].大型稀疏线性代数系统迭代解法研究[D]. 程光辉.电子科技大学2008
• [4].求解某些特殊稀疏线性系统的数值解法[D]. 王瑞瑞.厦门大学2009
• [5].线性方程组和鞍点问题的松驰型迭代算法与预条件技术[D]. 周圣.电子科技大学2009
• [6].大型稀疏线性系统迭代解法及应用研究[D]. 吴世良.电子科技大学2009
• [7].大型稀疏线性代数方程组的并行非定常迭代方法[D]. 谷同祥.中国工程物理研究院2001
• [8].稀疏线性代数方程组迭代法中的预处理技术研究[D]. 吴建平.中国人民解放军国防科学技术大学2002
• [9].求解约束矩阵方程及其最佳逼近的迭代法的研究[D]. 彭亚新.湖南大学2005
• [10].鞍点问题的迭代方法[D]. 曹艳华.复旦大学2005

标签：鞍点线性系统论文;  算法论文;  广义算法论文;  两参数广义算法论文;  预优共轭梯度算法论文;  方程论文;  代数重建论文;  加权最小范数准则论文;  共轭梯度重建算法论文;