几类结构矩阵的快速算法及其应用

论文摘要

众所周知，在工程计算和实际应用中有许多问题最终都归结为矩阵计算问题，而且不同的应用会导出一些具有特殊结构的矩阵计算。最常见的一些结构矩阵有Toeplitz矩阵[ai-j]，Hankel矩阵[ai+j]，Vandermonde矩阵[aij-1]，Cauchy矩阵[1/（ai-bj）]等等。处理与这些结构矩阵有关的矩阵计算问题（例如，求解线性方程组、计算特征值等），若矩阵的阶数较小时，通常的经典算法是可行的（例如LU分解算法、QR算法等）。然而，在许多实际应用当中，矩阵的阶数n很大（n～106-109）或某个线性方程组需要多次计算直到得到一个满意的结果（例如用迭代法时），此时这些经典的算法由于代价太大而失去了实际意义。 因此，针对这些结构矩阵的特点而设计一些能利用它们的结构的，数值稳定的快速算法，具有非常重要的意义。正因为结构矩阵在实际应用中所具有的重要意义，国内外众多的学者将目光投入到这一领域。结构矩阵的快速算法中最著名的莫过于快速傅里叶变换（即FFT），有许多快速算法均是由快速傅里叶变换导出的。因此，著名数学家Charles Van Loan曾这样评价快速傅里叶变换算法：“从计算的角度看，快速傅里叶变换是本世纪最杰出的成就之一，毫不夸张地说，快速傅里叶变换改变了科学与工程计算的面貌，如果没有它，生活将会是另一种景象”。 本论文主要研究了Toeplitz矩阵、Hankel矩阵、Pascal矩阵以及合流Cauchy-Vandermonde矩阵的一些性质及相关的快速算法，同时还给出这些快速算法的数值实验和在一些问题中的应用。理论和数值实验显示，这些快速算法是行之有效的。 第一章，我们简单介绍了研究结构矩阵快速算法的现实意义、研究概况以及常用的研究方法，同时也给出了与本论文有关的几类结构矩阵的定义及其基本性质。 在第二章和第三章，我们主要是利用Toeplitz矩阵和Hankel矩阵的特殊结构，导出相应的递推关系式，然后再利用快速傅里叶变换（FFT），给出了计算Toeplitz矩阵的正弦变换和Hankel矩阵的余弦变换的快速算法（算法计算复杂度为O（nlogn））。该算法不仅快而且存贮有效，因为在执行该快速算法的过程中，不需要存贮任何矩阵。同时在第二章中，我们还给出了该快速算法在利用Jacobi旋转变换计算Toeplitz矩阵的特征值中的应用。数值实验

论文目录

• 中文摘要
• 英文摘要
• 第一章 绪论
• §1.1 引言
• §1.2 几类结构矩阵的定义及性质
• §1.3 设计结构矩阵快速算法的常用方法及本文结构
• §1.4 基本符号
• 第二章 Toeplitz矩阵的快速sine变换算法及其应用
• §2.1 引言
• §2.2 算法的推导
• §2.3 应用
• 第三章 Hankel矩阵的快速cosine变换算法
• §3.1 引言
• §3.2 算法的推导
• §3.3 应用
• 第四章 Pascal型线性方程组的快速求解
• §4.1 引言
• §4.2 算法的推导
• §4.3 应用
• 第五章 合流Cauchy-Vandermonde矩阵的分解
• §5.1 引言
• §5.2 合流Cauchy-Vandermonde矩阵与有理插值
• §5.3 Neville消去与块Neville消去
• §5.4 合流Cauchy-Vandermonde矩阵及其逆的块双对角分解
• 第六章 实Hankel矩阵的谱的性质
• §6.1 引言
• §6.2 实Hankel矩阵的谱的刻划
• 参考文献
• 作者在攻读博士学位期间的有关学术论文
• 作者在攻读博士学位期间的所获得的奖励
• 致谢