一类toeplits型线性方程组的求解算法
目录
摘要1
关键词1
Abstract1
Key words1
绪论1
1 课题背景与研究意义2
2基础知识及概念3
3 对称三对角Toeplitz 型线性方程组的求解算法及实现 3
3.1 常用解线性方程组方法3
3.1.1 Doolittle分解法 3
3.1.2 改进的平方根法4
3.1.3 追赶法4
3.2 对角占优的三对角Toeplits型线性方程组的Rojo求解算法5
3.2.1 Rojo算法分析5
3.2.2 改进Rojo算法7
4 数值算例及分析10
4.1实例求解10
5 结论与分析12
致谢12
参考文献12
附录13
一类Toeplits型线性方程组的求解算法
引言
绪论
三对角Toeplitz型线性方程组被大量运用于科学和客观工程计算中，本文主要研究了Toeplitz 型线性方程组的多种求解方法，并由具体数值算例给出不同方法之间在运算时间和计算误差方面的比较。首先介绍了本文的研究背景、国内外研究现状及研究意义，其次介绍了一些基础理论知识，给出了直接分解法、平方根法
*51今日免费论文网|www.jxszl.com +Q: 3 5 1 9 1 6 0 7 2
、追赶法等常用的求解线性方程组的方法；接着介绍了求解严格对角占优的三对角型Toeplits方程组的Rojo算法，并对Rojo算法的进行改进使其适用于非对角占优的对称三对角Toeplits线性方程组的求解。最后，通过具体矩阵的计算比较不同的算法，分析Rojo算法与推广后的Rojo算法的可行性与有效性。
1 课题背景与研究意义
作为科学计算领域中的重要组成部分，大型线性方程组的求解问题逐渐成为数值计算中的一大热门。特别是系数矩阵为特殊矩阵的线性方程组，在图像存储、数字信号处理、微分方程等领域中有着很重要的地位。德国数学家托伯利兹在二十世纪给出了托伯利兹(Toeplitz)矩阵的定义及其相关的一些简单性质，之后Toeplitz 矩阵成为一类应用最为广泛的特殊矩阵之一，其结构特点是矩阵主对角线上的元素相等，平行于主对角线上的元素也彼此相等。Toeplits矩阵在数字信号处理、自动控制、系统识别等众多科学领域中被广泛运用。目前，对Toeplits矩阵的研究大致可以分为两部分，一是对Toeplits矩阵数学性质的研究，二是对Toeplits型方程组求解问题的研究。其中对Toeplits型线性方程组求解算法的研究是众多学者研究的重点，国内外许多学者都在寻找一种运算量比较小、误差小、算法稳定、存储量小的求解算法。近年来，对Toeplits型方程组的研究出现很多的成果。比如，在特殊类型的Toeplitz 型线性方程组这一块，刘成志提出了多级迭代求解法[1]，其在古典迭代法的基础上给出解Toeplits方程组的多级迭代法及多级迭代法的分裂构造，并分析了多级迭代法的收敛性和复杂性，一定程度上弥补了古典迭代法收敛速度比较慢甚至对一些矩阵来说不收敛的不足。任国恒等人通过构造特殊分块矩阵给出了Toeplits型线性方程组的拟对称化快速算法[2],该方法通过构造特殊分块矩阵的方式实现，与之前已有的算法相比，计算量比较小或计算精度比较高。吕小光在《关于Toeplitz矩阵的计算》中给出了Toeplits矩阵逆的求解方法与分解式并给出基于矩阵分块降低矩阵规模求解三对角Toeplitz 线性方程组的算法[3]，并通过具体的数值算例的求解证明了该算法是一种可行性高的算法。成青松等人对块五对角Toeplitz 方程组的求解进行了研究[4]，利用块五对角Toeplits矩阵的分裂与准块五对角Toeplits矩阵的分解实现求解块五对角Toeplits型方程组。当然，Toeplitz型线性方程组也可以用Jacobi迭代法、GaussSeidel迭代法、SOR迭代法等逐步逼近精确解的方法进行计算，但迭代法一般适用于系数矩阵为大型稀疏矩阵的线性方程组，且由于这些迭代法的收敛速度依赖于矩阵谱半径的大小，对于很多矩阵，迭代法的收敛速度非常慢且有可能不收敛，因此，迭代法目前已很少直接用于大型方程组问题的求解。
Toeplitz 矩阵有多种特殊的类型，有一类叫三对角Toeplitz 矩阵，其特点是除了主对角线及次对角线上的元素外其他元素均为零，以其为系数矩阵的线性方程组也已经有很多学者得出了相应的求解算法，在科学计算和实际工程计算中，随着科学技术的快速发展，许多适用于大规模计算的算法被提出。比如，上世纪90年代，国外学者Rojo 基于将Toeplitz 系数矩阵分解为两个较简单矩阵之和的思想给出对角占优的对称三对角Toeplitz 型线性方程组的求解算法[5]。该算法相对于传统的求解该类线性方程组的算法运算量更小，也更为稳定，广泛应用于该类线性方程组的求解及多种工程问题解决中[6]；2002 年，李青等人运用矩阵分解给出了循环三对角Toeplitz 线性方程组的直接解法[7]，通过分析循环三对角Toeplits矩阵的特性，给出了达到机器精度的截断算法，并将该算法推广到系数矩阵为拟三对角矩阵的线性方程组的求解；2003 年，单润红等人提出了一种求解三对角Toeplitz 型线性方程组的快速分布式并行算法[8]，其基于系数矩阵的LU分解并结合秦九韶技术和有效的数学计算技巧大大减少了计算过程中的冗余计算，并通过数值实验证明该算法的加速比接近于线性加速比且具有很高的并行效率。
三对角Toeplitz型线性方程组被大量运用于科学和客观工程计算中，本课题即是基于矩阵分解的思想分析Rojo所给的算法及多种求解可逆的对称三对角Toeplitz 型线性方程组的算法,如Doolittle分解法、平方根法、追赶法、Rojo算法及推广后的Rojo算法，并用matlab程序实现该算法在具体数值算例上的计算与分析，比较不同算法之间在运算时间及计算误差上的不同，并分析Rojo算法与推广后的Rojo算法的可行性与有效性。既有总结前人的成果之处也有一定的创新之处。
2 基础知识及概念
定义1 Toeplitz矩阵是矩阵的主对角线上的元素相等，且平行于主对角线上的元素也彼此相等的一类特殊矩阵，具体形式如下[9]，[10]：
原文链接：http://www.jxszl.com/jsj/xxaq/45407.html
