几类数值算法的准确性和稳定性

论文摘要

算法的准确性和稳定性是数值代数中重要而基础的研究分支.随着科学的进步,计算机技术的发展,数值计算实际问题的规模不断扩大,产生的矩阵越来越大,那么解线性方程组就变得更加困难,需要提出一些切实可行的算法来解决这样的问题.在提出方法之后就会面临一个一般性的问题,即这个方法可不可行,当轻微的扰动引起后,会不会出现数值解离真实解差距比较大的问题.所以对算法的稳定性和准确性进行研究是相当必要的.本文研究块三对角矩阵,一般非奇异矩阵和非对称严格t-对角占优矩阵的相关算法的稳定性和准确性；探讨几类增长因子；分析极分解的更新和秩r更新的准确性；分别研究鞍点问题和加权线性最小二乘问题的准确性和稳定性.研究块三对角矩阵相关算法的准确性和稳定性.首先,利用分而治之与URV分解确定块三对角矩阵的逆,并给出产生于计算中的逆的舍入误差.该算法其计算复杂性和误差均比块高斯-若尔当消元法的计算复杂性和误差好.其次,若原矩阵是Ⅰ-块对角占优（Ⅱ-块对角占优）块三对角矩阵,则约化矩阵保持同样的性质.给出几类比较矩阵的一些性质并分析块三对角矩阵BLU分解的向后误差.再次,利用Amodio和Mazzia提出的一般矩阵LU分解的块表达式给出块三对角矩阵,块三对角块H-矩阵和复对称块三对角矩阵BLU分解的块表达式,研究其准确性和向后误差并体现其优越性.最后,为了避免分解因子不是三角形式的状况,研究块三对角的分块LU分解并分析其准确性和稳定性.基于泰勒级数的一阶表达式和矩阵-向量方程,研究LU和QR分解因子的扰动理论.对于一般非奇异矩阵的LU分解,考虑Chang和Paige提出的问题并研究完全选主元LU分解的相关问题.另外,因严格t-对角占优可以刻画对角病态,所以考虑非对称严格t-对角占优线性方程组的LU和QR分解的向后误差.基于Amodio和Mazzia提出的增长因子定义,研究块三对角块H-矩阵和复对称块三对角矩阵在BLU分解下的增长因子.同时,提出广义的Buckley矩阵的定义,并基于Wilkinson提出的增长因子的定义,讨论该矩阵及其一个相关的矩阵在高斯消去下的增长因子.另外,算法的更新和删减在很多方面均有涉及.分析极分解的更新和秩r更新的扰动理论.研究鞍点问题的扰动理论.首先,探讨当扰动系统仍是鞍点系统时的扰动理论.由于系统解的准确性表明其依靠于鞍点矩阵的子矩阵,为了消除其影响而提出一些方案.为了提高解的准确性,提出一个尺度化.其次,当原系统是鞍点系统而扰动系统是广义鞍点系统时,考虑块LDLT分解的灵敏性并讨论此情形下的扰动理论.再次,由于鞍点问题与最小二乘问题的密切联系,给出一个解拥有不定对角加权矩阵的加权线性最小二乘问题的可证向后稳定算法.然而,当加权矩阵是广义鞍点矩阵时,类似的算法不一定是向后稳定的,所以最后讨论此时算法是可证向后稳定的情形.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究问题和背景
• 1.1.1 几类矩阵及相关算法
• 1.1.2 增长因子与算法的更新
• 1.1.3 鞍点问题与最小二乘问题
• 1.2 本文主要研究内容,方法和创新点
• 1.3 本文结构安排
• 第二章 块三对角矩阵相关算法的准确性和稳定性研究
• 2.1 块三对角矩阵的逆和舍入误差
• 2.1.1 引言
• 2.1.2 块三对角矩阵的逆
• 2.1.3 舍入误差分析
• 1的逆的计算'>2.1.3.1 A₁的逆的计算
• 2.1.3.2 A的逆的计算
• 2.1.4 计算复杂性的比较与数值试验
• 2.2 块三对角矩阵BLU分解的稳定性
• 2.2.1 引言
• 2.2.2 关于几类特殊矩阵的一些性质
• 2.2.3 误差分析
• 2.3 块三对角矩阵BLU分解的稳定性分析
• 2.3.1 引言
• 2.3.2 块三对角矩阵BLU分解的表达式
• 2.3.3 分解因子的性质
• 2.3.4 扰动理论
• 2.3.5 舍入误差分析
• 2.4 块三对角块H-矩阵的BLU分解的稳定性
• 2.4.1 引言
• 2.4.2 预备知识
• 2.4.3 块三对角块H-矩阵的BLU分解
• 2.4.4 扰动理论
• 2.4.5 舍入误差分析
• 2.5 复对称块三对角块矩阵的BLU分解稳定性分析
• 2.5.1 引言
• 2.5.2 BLU分解
• 2.5.3 误差分析
• 2.6 块三对角线性方程组的分块LU分解的扰动和误差分析
• 2.6.1 引言
• 2.6.2 扰动理论
• 2.6.3 误差分析
• 2.6.4 数值试验
• 2.7 本章小结与展望
• 第三章 非块三对角矩阵的算法准确性和稳定性研究
• 3.1 LU和QR分解的扰动理论
• 3.1.1 引言
• 3.1.2 预备知识
• 3.1.3 LU分解因子的扰动定理
• L（A）/κ′_L（A）和κ_U（A）/κ′_U（A）的边界'>3.1.4 κ_L（A）/κ′_L（A）和κ_U（A）/κ′_U（A）的边界
• 3.1.5 QR分解因子的扰动定理
• 3.2 严格t-对角占优的LU和QR分解的稳定性
• 3.2.1 引言
• 3.2.2 LU分解的向后误差
• 3.2.3 QR分解的向后误差
• 3.3 本章小结与展望
• 第四章 增长因子及极分解更新和秩r更新研究
• 4.1 几种情况下的增长因子研究
• 4.1.1 块三对角块H-矩阵在BLU分解下的增长因子
• 4.1.2 复对称块三对角矩阵在BLU分解下的增长因子
• 4.1.3 广义Buckley矩阵和相关矩阵在高斯消去下的增长因子
• 4.1.3.1 引言
• 4.1.3.2 预备知识
• 4.1.3.3 主要结论
• 4.2 极分解的更新和秩r更新的扰动分析
• 4.2.1 引言
• 4.2.2 极分解更新的扰动定理
• 4.2.3 极分解秩r更新的扰动定理
• 4.2.4 条件数
• 4.3 本章小结与展望
• 第五章 鞍点问题的准确性与最小二乘法的稳定性研究
• 5.1 鞍点问题的扰动分析
• 5.1.1 引言
• 5.1.2 几种情形下鞍点系统的扰动理论
• 5.1.2.1 扰动A和b的情形
• 5.1.2.2 扰动A和b情形下的尺度化
• 5.1.2.3 扰动B和b的情形
• 5.1.2.4 扰动A,B和b的情形
• 5.1.3 扰动两个对角块,向量b和0情形的扰动理论
• T分解的灵敏性'>5.1.3.1 块LDL^T分解的灵敏性
• 5.1.3.2 扰动定理
• 5.2 加权线性最小二次问题的向后稳定性分析
• 5.2.1 引言
• 5.2.2 加权矩阵D为特殊不定对角矩阵的向后稳定性分析
• 5.2.2.1 预备知识
• 5.2.2.2 加权线性最小二乘问题的解
• 5.2.2.3 解的向后误差
• 5.2.3 加权矩阵D是广义鞍点矩阵的向后稳定性分析
• 5.2.3.1 预备知识
• 5.2.3.2 解的向后稳定性分析
• 5.2.3.3 算法向后稳定的条件
• 5.3 本章小结与展望
• 第六章 结论
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果