一类托伯利兹型线性方程组的求解算法及其matlab编程实现
目 录
1 绪论 1
2 对称三对角Toeplitz型线性方程组的求解算法及实现 2
2.1 基本概念 2
2.2 对角占优的对称三对角Toeplitz型线性方程组的求解算法 2
2.3 非对角占优的对称三对角Toeplitz型线性方程组的求解算法 7
3 基于LDLT分解的线性方程组的求解算法 12
4 数值算例及matlab仿真结果分析 14
结 论 17
致 谢 18
参 考 文 献 19
附录 20
附录 22
1 绪论
作为科学计算领域中的重要组成部分，大型线性方程组的求解问题逐渐成为数值计算中的一大热门。特别是当系数矩阵为特殊矩阵的方程组，在图像存储、数字信号处理、微分方程等领域中有着很重要的地位。
德国数学家托伯利兹在二十世纪给出了托伯利兹(Toeplitz)矩阵的定义及其相关的一些简单性质，Toeplitz矩阵成为一类应用最为广泛的特殊矩阵之一，其结构特征以及以其为系数矩阵的线性方程组的求解算法也被广为研究，国内外许多学者都在此问题上研究出许多重要的成果。
比如，在特殊的Toeplitz型线性方程组这一块，2006年吕小光在《关于Toeplitz矩阵的计算》中给出了带状Toeplitz线性方程组的算法[1]；2012年，仝秋娟对几类特殊的Toeplitz线性方程组的解法进行了研究[2]；刘成志提出了Toeplitz方程组的多级迭代求解法[3]；2008年，成青松等人对五对角Toeplitz线性方程组的求解进行了研究；2010年汪祥等人在对称Toeplitz方程组方面有了研究；刘晓玲等人在2014年提出了厄米特To *好棒文|www.hbsrm.com +Q: ^3^5`1^9`1^6^0`7^2#
eplitz线性方程组的迭代解法[6]等等；
Toeplitz矩阵有多种特殊的类型，有一类叫三对角Toeplitz矩阵，以其为系数矩阵的线性方程组也已经有很多学者得出了相应的求解算法，比如，2002年，李青等人给出了循环三对角Toeplitz线性方程组的求解的追赶法；2004年，单润红等人提出了一种新的求解近似三对角Toeplitz线性方程组的快速算法；同年，崔喜宁提出一种求解一类周期三对角Toeplitz线性方程组的并行算法；2005年，肖曼玉提出了大型周期块三对角线性方程组的并行算法。
从上述内容可知，在对称三对角Toeplitz线性方程组的求解算法这一块，目前国内还没有人对此做过详细的研究，已有资料显示，国外学者Rojo已经得出对角占优的对称三对角Toeplitz型线性方程组的求解算法[7]，因此，本文的主要工作就是，在Rojo提出的算法的基础上，对其进行推广，研究非对角占优的对称三对角Toeplitz型线性方程组的求解算法，并且通过数学软件matlab仿真和传统的基于LDLT分解的求解线性方程组的算法进行比较，得出两种算法的运算时间及误差，表明推广的Rojo算法的可行性与有效性。
2 对称三对角Toeplitz型线性方程组的求解算法及实现
2.1 基本概念
定义1 Toeplitz矩阵是主对角线上的各元素彼此相等，平行于主对角线上的元素也彼此相等的一类特殊矩阵，它是特殊的次对称矩阵，形式如下：
定义2 Toeplitz矩阵有许多类型，比如循环Toeplitz矩阵，五对角Toeplitz矩阵，其中有一类叫三对角Toeplitz矩阵，它的形式如下：
（1）
当 时，（1）式就被称为对称三对角Toeplitz矩阵。
定义3 对于一个 阶方阵，如果其每个主对角元素的模都大于与他同行的其他元素的模的总和，这种矩阵就是按行严格对角占优的，对列同样成立。
（1） 设 ，如果 ，则称 为按行严格对角占优矩阵。
（2） 设 ，如果 ，且至少有一个式子取严格不等号，
则称 为按行弱对角占优矩阵。一般地，不特别声明，就称该矩阵是对角占优的。
2.2 对角占优的对称三对角Toeplitz型线性方程组的求解算法
2.2.1 算法分析
考虑求解线性方程组 ，也就是求
（2）
如上(2)式线性方程组的解，由于需要考虑两个参数 的值，可以将 变形为 的形式，也就是如下形式：
（3）
其中 ， .
最终也就转化为求式(3)，也就是 的解。
Rojo算法[7]用于矩阵 为对角占优的情况下，则有条件 成立。
要求出方程组的解，关键是对矩阵 的求逆运算。Rojo算法运用 分解的思想，将矩阵 分解为两部分之和，也就是 ，其中
（4）
,为单位矩阵的第一列。
第一步，需要把 的分解形式求出来，也就是求出 的值。
矩阵 可以由 具体表示出，即：
（5）
则由 ,得出 ， 。那么只需要由方程 解出 的值即可。因此 ，因为 ，所以 并且 可以由 函数表示出： 。
下一步就是方程的求解，我们假设方程(3)的解为 ，其中 是由 解得。那么要得到 的值，就是要求出 的值。
将 带入 ，则有 ，对其进一步化简有 ，又因为 ，则 ，即有
，
，为 的第一个元素值。
则 ，那么要得出 ，就是要将 求出来。使用 公式：
其中
把 看作上述公式中的 ， 看作 , 看作 ,因为
，
则有
那么，
令 ，则
因此可得
。
2.2.2 算法实现
通过对Rojo算法的描述，求解对称三对角Toeplitz线性方程组 可以分为以下步骤：
1) 计算 的值:
， ,
从而得出 的分解式中的 ;
2) 求解 ：
通过对Rojo算法的学习，同样的，对于求解线性方程组（4） ，我们可将矩阵 可分解为 ， 和 如（4）式。那么由（5）的推算过程，可以得出 可由方程 解出，只是因为此时 ，所以 ，则 并且 可以由 函数表示出： 。
令 ， ，则 ， 的共轭复数为 ，并且有 。由于 为复数，所以 、 的元素和 也都为复数。
依旧假设方程(3)的解为 ，按照Rojo算法实现的步骤，先求解 得出 ，再求解 ，得出 ，由 得出 。那么很容易看出 与 都为复数。用 和 分别表示 的实部与虚部，那么 ，则 即为：
2000 0.0014 8.0059e-16 0.0117 6.9387e-15
1 绪论 1
2 对称三对角Toeplitz型线性方程组的求解算法及实现 2
2.1 基本概念 2
2.2 对角占优的对称三对角Toeplitz型线性方程组的求解算法 2
2.3 非对角占优的对称三对角Toeplitz型线性方程组的求解算法 7
3 基于LDLT分解的线性方程组的求解算法 12
4 数值算例及matlab仿真结果分析 14
结 论 17
致 谢 18
参 考 文 献 19
附录 20
附录 22
1 绪论
作为科学计算领域中的重要组成部分，大型线性方程组的求解问题逐渐成为数值计算中的一大热门。特别是当系数矩阵为特殊矩阵的方程组，在图像存储、数字信号处理、微分方程等领域中有着很重要的地位。
德国数学家托伯利兹在二十世纪给出了托伯利兹(Toeplitz)矩阵的定义及其相关的一些简单性质，Toeplitz矩阵成为一类应用最为广泛的特殊矩阵之一，其结构特征以及以其为系数矩阵的线性方程组的求解算法也被广为研究，国内外许多学者都在此问题上研究出许多重要的成果。
比如，在特殊的Toeplitz型线性方程组这一块，2006年吕小光在《关于Toeplitz矩阵的计算》中给出了带状Toeplitz线性方程组的算法[1]；2012年，仝秋娟对几类特殊的Toeplitz线性方程组的解法进行了研究[2]；刘成志提出了Toeplitz方程组的多级迭代求解法[3]；2008年，成青松等人对五对角Toeplitz线性方程组的求解进行了研究；2010年汪祥等人在对称Toeplitz方程组方面有了研究；刘晓玲等人在2014年提出了厄米特To *好棒文|www.hbsrm.com +Q: ^3^5`1^9`1^6^0`7^2#
eplitz线性方程组的迭代解法[6]等等；
Toeplitz矩阵有多种特殊的类型，有一类叫三对角Toeplitz矩阵，以其为系数矩阵的线性方程组也已经有很多学者得出了相应的求解算法，比如，2002年，李青等人给出了循环三对角Toeplitz线性方程组的求解的追赶法；2004年，单润红等人提出了一种新的求解近似三对角Toeplitz线性方程组的快速算法；同年，崔喜宁提出一种求解一类周期三对角Toeplitz线性方程组的并行算法；2005年，肖曼玉提出了大型周期块三对角线性方程组的并行算法。
从上述内容可知，在对称三对角Toeplitz线性方程组的求解算法这一块，目前国内还没有人对此做过详细的研究，已有资料显示，国外学者Rojo已经得出对角占优的对称三对角Toeplitz型线性方程组的求解算法[7]，因此，本文的主要工作就是，在Rojo提出的算法的基础上，对其进行推广，研究非对角占优的对称三对角Toeplitz型线性方程组的求解算法，并且通过数学软件matlab仿真和传统的基于LDLT分解的求解线性方程组的算法进行比较，得出两种算法的运算时间及误差，表明推广的Rojo算法的可行性与有效性。
2 对称三对角Toeplitz型线性方程组的求解算法及实现
2.1 基本概念
定义1 Toeplitz矩阵是主对角线上的各元素彼此相等，平行于主对角线上的元素也彼此相等的一类特殊矩阵，它是特殊的次对称矩阵，形式如下：
定义2 Toeplitz矩阵有许多类型，比如循环Toeplitz矩阵，五对角Toeplitz矩阵，其中有一类叫三对角Toeplitz矩阵，它的形式如下：
（1）
当 时，（1）式就被称为对称三对角Toeplitz矩阵。
定义3 对于一个 阶方阵，如果其每个主对角元素的模都大于与他同行的其他元素的模的总和，这种矩阵就是按行严格对角占优的，对列同样成立。
（1） 设 ，如果 ，则称 为按行严格对角占优矩阵。
（2） 设 ，如果 ，且至少有一个式子取严格不等号，
则称 为按行弱对角占优矩阵。一般地，不特别声明，就称该矩阵是对角占优的。
2.2 对角占优的对称三对角Toeplitz型线性方程组的求解算法
2.2.1 算法分析
考虑求解线性方程组 ，也就是求
（2）
如上(2)式线性方程组的解，由于需要考虑两个参数 的值，可以将 变形为 的形式，也就是如下形式：
（3）
其中 ， .
最终也就转化为求式(3)，也就是 的解。
Rojo算法[7]用于矩阵 为对角占优的情况下，则有条件 成立。
要求出方程组的解，关键是对矩阵 的求逆运算。Rojo算法运用 分解的思想，将矩阵 分解为两部分之和，也就是 ，其中
（4）
,为单位矩阵的第一列。
第一步，需要把 的分解形式求出来，也就是求出 的值。
矩阵 可以由 具体表示出，即：
（5）
则由 ,得出 ， 。那么只需要由方程 解出 的值即可。因此 ，因为 ，所以 并且 可以由 函数表示出： 。
下一步就是方程的求解，我们假设方程(3)的解为 ，其中 是由 解得。那么要得到 的值，就是要求出 的值。
将 带入 ，则有 ，对其进一步化简有 ，又因为 ，则 ，即有
，
，为 的第一个元素值。
则 ，那么要得出 ，就是要将 求出来。使用 公式：
其中
把 看作上述公式中的 ， 看作 , 看作 ,因为
，
则有
那么，
令 ，则
因此可得
。
2.2.2 算法实现
通过对Rojo算法的描述，求解对称三对角Toeplitz线性方程组 可以分为以下步骤：
1) 计算 的值:
， ,
从而得出 的分解式中的 ;
2) 求解 ：
通过对Rojo算法的学习，同样的，对于求解线性方程组（4） ，我们可将矩阵 可分解为 ， 和 如（4）式。那么由（5）的推算过程，可以得出 可由方程 解出，只是因为此时 ，所以 ，则 并且 可以由 函数表示出： 。
令 ， ，则 ， 的共轭复数为 ，并且有 。由于 为复数，所以 、 的元素和 也都为复数。
依旧假设方程(3)的解为 ，按照Rojo算法实现的步骤，先求解 得出 ，再求解 ，得出 ，由 得出 。那么很容易看出 与 都为复数。用 和 分别表示 的实部与虚部，那么 ，则 即为：
2000 0.0014 8.0059e-16 0.0117 6.9387e-15
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/2887.html
