基本信息
- 项目名称：
- 加边三对角线性方程组解法的研究
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 数理
- 大类：
- 自然科学类学术论文
- 简介：
- 为了求解形如（1）（见附加材料公式（1））的加边三对角线性方程组，本文基于LU分解思想，将追赶法的思想进一步推广，将系数矩阵分解成四个矩阵（见附加材料公式（2）），从而将原方程组转化为四个线性方程组方程组（见附加材料公式（3）），进而求解这四个方程组便可得到原方程组的解。该方法中乘（除）法与加（减）法运算量仅为O(11n)和O(8n)。而且数值稳定性分析结果表明，该算法是稳定的。
- 详细介绍：
- 在偏微分方程求解及许多科学与工程计算中常常会遇到求解形如（1）（见附加材料公式（1））所示的加边三对角线性方程组，本文将追赶法的思想进一步推广，于是将系数矩阵进一步分解成四个矩阵（见附加材料中公式（2）），进而将求解原方程组转化为求解四个简单的线性方程组（见附加材料公式（3））， 依次求解这四个方程，便可将原方程组解出，进而统计其算术运算量，并与相同或相近问题的解决进行分析比较，最后数值实验进行编程加以验证，并且经过验证在系数矩阵严格对角占优或不可约对角占优的条件下，数值实验结果和理论分析结果十分吻合 。
作品专业信息
撰写目的和基本思路
- 目的：将追赶法的思想推广到求解加边三对角线性方程组中，提出一种算术运算量仅为O（19n）新解法，以更好解决工程计算中加边三对角线性方程组问题。基本思路：1.将追赶法思想作为求解加边三对角线性方程组的基本思想。2.将LU分解和追赶法思想推广，首先进行算法推导，包括矩阵分解和方程组求解过程，后进行算法分析和比较，包括数值稳定性和算法复杂度分析，最后进行数值实验验证数值的稳定性和算法的准确性分析。
科学性、先进性及独特之处
- 1.本文是对追赶法思想的补充和应用，具有很好的理论意义和实际应用价值。2.本研究将系数矩阵分解成四个简单矩阵的乘积，进而将原方程组转化为四个简单方程组，计算复杂度大大降低。3.算法的算术运算量与方程组的阶n呈线性关系，我们仅用了O（19n）算术运算量，在算术运算量上也是一个突破。4.最终数值实验可以对百万至千万阶的严格对角占优或不可约对角占优的加边三对角线性方程组赋初值，运行结果误差较小。
应用价值和现实意义
- 1.在求解数学模型时，往往需要选着合适的计算方法。但是无论是何种计算方法，最终都是将现实生活中的复杂问题全部的或者部分的归结为线性方程组的求解问题。因此对在计算流体力学，气象动力学和跳点网格系统等众领域中广泛应用的形如公式（1）（见附加材料（1））的研究自然是十分必要和有意义的。 2。将追赶法的思想加以推广研究，为以后更好的解决科学与工程计算问题奠定基础。
学术论文摘要
- 本文仿照追赶法的思想，给出了一种求解加边三对角线性方程组的追赶算法。该算法首先将系数矩阵分解成四个矩阵，进而将求解加边三对角线性方程组的问题转化成求解四个简单的方程组。该方法能够快速稳定的求解加边三对角线性方程组，且乘（除）法与加（减）法运算量仅为O(11n)和O(8n)。本算法的数值稳定性分析结果表明，系数矩阵在满足严格对角占优的条件下，该算法是稳定的。
获奖情况
- 无
鉴定结果
- 无
参考文献
- [1] 冯康等：数值计算方法［M］,国防工业出版社，1978. [2] 马明书，姚慧：抛物型方程的一组高精度恒稳定的隐式差分格式［J］，河南师范大学学报（自然科学学报），2001（2）：6-8. [3] 朱自强，李津，张正科，陈泽民，吴子牛，李海明：计算流体力学中网格生成方法及其应用，航空学报，1998（2）：25-31. [4] 张静，王福军，于颖多，刘洋：基于ＭＰＩ三对角方程组的并行算法，农机化研究，2005，（4）：81-83. [5] 王兴波，钟志华：求解周期性三对角方程组的广义Thomas算法[J]，计算力学学报，2004,21（1）：73-76. [6] 李文强，刘晓：追赶法在求解循环和拟循环三对角方程组中的一种推广，河南师范大学学报，2009,37（1）：13-16. [7] 李文强，刘晓：追赶法并行求解循环三对角方程组[J]科技导报，2009，(18):90-93. [8] 李文强，马民：求解循环三对角方程组的追赶法[J]科技导报，2009，（14）:69-72. [9] 李青，王能超：解循环三对角线性方程组的追赶法［J］，小型微型计算机系统，2002,23（11）：1393-1395. [10] Temperton C.A algorithm for solution of cyclic tridiagonal systems[J]. Comput Physics, 1975, 19(2):317-323.
同类课题研究水平概述
- 在偏微分方程求解及许多科学与工程计算中常常会遇到求解三对角、循环三对角、循环Toeplitz三对角、拟三对角线性方程组。1997年，Jung-Gen Wu,Wen-Ming Yan 和Kuo-Liang Chung讨论了循环Toeplitz三对角线性方程组的并行解法；迟利华对于循环三对角线性方程组提出了一种近似实用解法，在一定条件下将求解循环三对角线性方程组的算术运算量从O（17n）下降到O（8n），所得到的解与精确解的误差达到计算机机器零；近年来，迟利华、骆志刚、李晓梅等对三对角线性方程组的分布式计算进行了深入研究，得到了通信复杂度极小的并行算法；李文强将追赶法的思想推广到求解循环三对角线性方程组中，得到了一种算术运算量仅为O（14n）的算法；李青和王能超基于LU分解的思想对拟三对角线性方程组进行求解，得到算术运算量为O（17n）的一种算法。对于本文研究的形如（1）（见附件公式（1））的加边三对角线性方程组，最近，我们小组把LU分解的思想和追赶法的思想进一步推广到求解加边三对角线性方程中，得到一种乘（除）法为O（11n），加（减）法为O（8n）的算法，并进行数值实验进行验证，得到实验结果和理论分析完全吻合。
