英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料
求解AX-XB=C的超松弛迭代法（SOR）
Gerhard Starke and Willhelm Niethammer
摘要
我们针对块状超松弛迭代法提出了一种新方法，并将该方法应用于可写成矩阵方程AX-XB=C的线性方程组。该方程组可能产生于诸如求解矩形区域上可分离椭圆边值问题的有限差分离散过程中。一方面，该方法为我们提供了求解这样矩阵方程（如李雅普诺夫矩阵方程，其中）的迭代方法。另一方面，为块超松弛迭代法选择合适参数的问题可以写成更紧凑的形式，可能对尤其是非自共轭问题，即A和B非对称的情形有用。利用这种技术，我们确定了对流扩散方程模型问题的最优SOR参数，其中的假设要比Chin和Manteuffel中给出的更一般。
- 引言
逐次超松弛迭代法（简称SOR方法）已经被研究了40年。对SOR理论的重要贡献来自于D.Young and R.S.Varga，他们的著作[18,16]被广泛认可为参考文献。大部分结果是关于SOR在对称正定系统中的应用。对于非对称问题使用Kjellberg[8]和Niethammer[9]来处理。
早在50年代，对于自伴随椭圆边值问题的迭代解，块方法例如块超松弛法和线性松弛就得到了广泛的研究(见[18,16])。近年来，人们对非自伴随问题的解决越来越感兴趣，Chin和Manteuffel[3]检验了块超松弛法在对流扩散型模型中的应用；Elman和Golub[5,4]研究了块雅可比和块高斯-赛德尔在循环还原系统中的应用。
本文将超松弛方法应用于矩阵方程的求解
, （1）
其中，已知且矩阵满足（1）的方程。这类矩阵方程有很多应用；例如，对于，我们得到了李雅普诺夫矩阵方程，这在稳定性理论和控制理论中是众所周知的（参照[1]和[2]）。当然，（1）式可以写成一个线性方程组
（2）
其中一种可能性派生的迭代方法解矩阵方程（1）是采取任何著名的解决（2）的方法，通过改良之后用来解方程（1）。相反地，首先方程组（2）有时可以改写成像（1）这样的矩阵形式；这是正确的尤其是如果（2）中含有一些常规的块结构，正如经常在连接与椭圆边值问题的离散化中出现。
近年来，对于矩阵方程的求解提出了多种方法，包括Colub、Nash、van Loan[7]等直接算法和迭代算法，例如由Smith提出的方法（[12];参见Barnett和Storey[2]）。Wachspress[17]中提到了Smith算法和交替方向法（ADI）之间的密切联系。在[13]中，研究了非对称矩阵A和B的最优参数选择问题。
本文的目的是双重的：首先，我们研究了（2）中的块超松弛法作为求解矩阵方程（1）的迭代方法，而且，矩阵方程的形式使我们得到了确定最优SOR参数的更简洁的表示法。
在第二部分中，我们更详细地解释了（1）和（2）之间的关系，即矩阵A、B和G之间的关联。此外，我们对于（1）引入了超松弛方法通过将块超松弛法应用于（2）。是为矩阵方程选择最优SOR参数的问题，或者换句话说就是为矩阵方程的块因子寻找最优omega;。超松弛法可以应用到解方程组的问题中，该类方程组可以写成（2），也可以改写成（1），这就使得我们要考虑最小化的问题。
, （3）
其中为超松弛中关于对应的点或运算符。这个推导和SOR对（2）的应用也是第一作者[14]论文中的一部分。
在接下来的部分中，我们将介绍用表示的离散对流扩散方程的模型问题，并且我们将展示对于矩阵A和B特征值存在的情况下，界限是否有价值。结果表明，假设我们在复平面上有包含A和B的谱的集合E和F，我们就得到了关于E和F的函数的最大值最小值的问题。
在第四部分中，我们展示了如果E和F是矩形域，如何用数值方法解决这个最小值问题，这可以通过应用Bendixson定理来实现。我们将看到无穷集E和F上的最大值可以被离散点集上的最大值所代替，这使得使用任何软件包来求关于一个实参函数的最小值成为可能。对于Chin和Manteuffel[3]认为E和F是区间的特殊情况，我们给出了它们的结果是如何通过这种方法得到的。
2.超松弛法（SOR）解方程
形式（1）的矩阵方程总是可以写成具有特殊结构的(mn,mn)矩阵的大型线性方程组（2）。如果我们把未知矩阵X的系数一行一行地放到向量中
，
我们得到一个系数矩阵的线性方程组
，（4）
其中为标准克罗内克积（参照Barnett[1,p.165]）。
我们将超松弛法应用于矩阵方程，相当于将块超松弛法（参照Varga[16]）应用于这个大型线性方程组。如果我们根据将矩阵A分解成对角线，（严格地）下三角和（严格地）上三角部分，这个迭代由以下给出
（5）
将（5）转换成矩阵方程的形式，这就相当于
（6）
此时，各迭代步骤产生的矩阵方程求解就会相对简单。我们把（6）写成
（7）
其中，未知矩阵的行表示为。我们从上到下逐一计算求解矩阵。矩阵方程（7）的第i行为
（8）
其中，左边的第一项已经知道了。因此，（8）可以是矩阵方程的超松弛迭代。写成线性方程组为
等式右边的。这意味着对于每一行的，我们必须解决线性方程组的系数矩阵。对于我们模型中的离散对流式问题是三对角方程，这意味着我们必须在每个子步（8）中解决一个三对角方程组。方程（7）在某种意义上是块超松弛法中显然的，因为这是应该实现的算法。
矩阵（4）的线性方程组是用X的行编号得到的。同样，列编号和应用块超松弛法解线性方程组就得到了迭代公式
（9）
其中，表示对应的分解为对角部分，下三角部分和上三角部分。
我们现在考虑的问题是为超松弛方法确定最优参数，换句话说，就是确定一个适用于具有系数矩阵（4）的特殊形式（2）方程组的超松弛迭代法的最优omega;。
我们把自己限制在（6）的情况下来推导最小值问题。由（6）得到误差矩阵
(10)
用线性算子，由gamma;给出，其中
（11）
这可以写成。因此，很明显，为了优化收敛，我们必须选择这样一种方式，即算子T的谱半径变得最小。
此时，我们需要一个关于矩阵方程的已知结果。
定理 1(Gantamacher [6,p.238]).对于任何等式右边的矩阵满足，矩阵方程具有唯一解，当且仅当并且时，没有共同的特征值。
Ostrowski和Schneider[10,引理11]为这个结果提供了一个很好的证明。
推论 2.对于（11）中给定的算子T，以及下式中给出光谱和谱半径
（12）
以及
（13）
证明：通过对（1）的考察，我们发现等价于一个矩阵的存在性，其中
根据定理1，矩阵和有一个共同的特征值，即，
因此，存在一个有
（14）
将特征值带入这个方程，我们观察到（14）等价于
（15）
这就推出（12）。
关系式（13）现在是（12）的直接结果。
表达式
引理2中出现的就是对应的（点）SOR算子。因此，为了优化关于（1）的方法的收敛性，我们需要解出问题（3）的最小值
即，我们必须以这样一种方式来选择SOR参数，也就是整个一类SOR算子的光谱极谱的最大值达到最小。下一节将说明，这种公式有利于确定最优SOR参数。在此之前，应该加上一句话：一般来说，我们不清楚的频谱，但通常我们可以用来确定复合平面的一个真子集F。这就简化了问题
(16)
显然，对于任意一个,我们有
因此，
（17）
因此，我们得到（16）中最小值的下界，假设我们为每一个修正的确定最优，然后取它们的最大值。
作为一个模型问题，我们将考虑边值问题
（18）
在单位平面，边界为上。这里，假设函数是连续可微的和是不可逆的，且c是一个非负常数。我们可以将（18）解释成一个特殊的对流扩散式方程的例子（见Chin and Manteuffel[3]）。
我们现在描述的是形式（1）的矩阵方程是如何通过使用核心差异的步长从离散化的（18）中得到的。我们的目标是用这样一种方式列举未知矩阵X中的元素，其中代表着矩阵中第i行第j列中函数的近似值。因此，我们设且 。至此，下面矩阵左乘X就表示在方向上应用不同的对应差分算子。
（19）
同样地，用下面矩阵右乘X就表示在方向上应用不同的对应差分算子。
（20）
这里，以及在网格点上分别表示函数和的值。右边是由离散值组成，并且，在第一行最后一行以及第一列最后一列由边界值组成。
为了得到A和B的特征值的有用界限而不是应用Bendixson的定理（见[15,Theorem 6.9.15]）很显然，首先要进行如下的相似变换。
容易可见，通过观察主子矩阵的特征多项式，（19）中的矩阵A具有如下相同的特征值。
（21）
以及
这个矩阵的系数可以是实的，也可以是纯虚的，根据网格雷诺数的模数大于1还是小于1来定。将分解成厄米和斜厄米两部分得到的谱的矩形边界往往比直接应用Bendixson定理得到的谱的矩形边界要好得多。尤其，对于实数，其中或者纯虚数，其中，我们得到的区间作为的谱界，而直接使用Bendixson定理一般来说会产生矩形。当然，矩阵B也应该用同样的方式处理。
我们希望为我们模型中对流扩散式问题解决最小值问题（16）。
定理3.最小化问题（16）等价于使得以下式子达到最小
（22）
其中，
（23）
有
且
证明：显然，是下式的一个特征值
当且仅当存在向量，有
或者，同样地，
因此，
（24）
从主子矩阵的特征多项式中我们可以观察到
有相同的特征值。因此，是的一个特征值就等价于
（25）
满足某些
如果我们设
且
我们得到
以及
因此，
（26）
这就引出了二次方程
解得
（27）
记作然而，很容易看出只有（27）中的正数才会得到一个，对于这个，的二次方程有一个实根。
到目前为止，我们已经证明了如果是的一个特征值，那么
（28）
满足（27）。另一方面，如果我们想最大化，我们只需要看（28）的正平方根。这两个二次方程的每一个解，取（27）的正号，也得到（25）的解。因此得到的一个特征值，可以通过验证得到
有我们期望的特征。
实际上，在上单调增加表明它足以使最大化，而的最大值是（27）恰好是定理中的函数。
注:需要注意的是，定理3不仅适用于模型问题。对于（25）的推导，必须假设A是一致有序的（对角线元素不变）。
由于我们不想使用A的显式特征值，而是使用条件，使得最小化问题（23）变成
且
（29）
其中，函数是定理3中的。
如果我们必须用数值方法计算无穷集E和F 的最大值，那么（29）中的超松弛参数问题的公式就不是那么理想。但幸运的是，至少对于特殊区域来说是这样的，如果E和F 是应用Bendixson定理（见[15,定理6.9.15]）得到的矩形域，最大值只能在边界和上的几个点上得到。然后求出离散点集上的最大值是没有问题的。
在后续工作中，我们要确定这个离散点集。我们假设矩形域由以下给出
（30）
首先要注意的是函数的最大值只能在边界和上的点处得到，即
（31）
从以下方法中可以
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[430106]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
