Smoothing factor, order of prolongation and actual multigrid convergence
Smoothing factor, order of prolongation and actual multigrid convergence
复制标题
平滑因子、延长阶数和实际多重网格收敛
DOI：
10.1007/s00211-011-0362-7
复制
发表时间：
2011
影响因子：
2.1
通讯作者：
Y. Notay
中科院分区：
文献类型：
--
作者：
Artem Napov;Y. Notay
我们认为傅立叶分析的多重网格方法（Galerkin型）的对称正定和半正定线性系统所产生的标量偏微分方程（PDE）的离散化。我们将所谓的平滑因子与实际的两个网格的收敛速度和V-循环多重网格的收敛速度联系起来。我们推导出一个双边界，定义了一个区间包含两个网格和V-循环收敛速度。当平滑因子和附加参数都足够小时，该区间是窄的并且远离1。除了光滑因子外，收敛性主要取决于延拓范围与系统矩阵小特征值特征向量之间的夹角。如果这个角的正切有一个与特征值成比例的上界，则保证了良好的V-循环收敛，而良好的两个网格收敛需要一个与特征值的平方根成比例的界。我们还讨论了著名的规则，涉及的阶的延长，微分算子相关的问题。我们首先定义基于频率的阶，其在大多数情况下相当于Hemker（J Comput Appl Math 32：423-429，1990）中定义的所谓高频阶。我们给出了一个坚实的基础，相关的顺序规则显示，连同要求有平滑因子远离1，它提供了必要和充分条件，有两个网格的收敛速度远离1。进一步证明了更强的条件足以实现V循环的最佳收敛。所提出的结果适用于严格的傅立叶分析定期离散偏微分方程，也可以通过讨论半正系统的局部傅立叶分析可能会出现从离散化的偏微分方程与周期性边界条件。
We consider the Fourier analysis of multigrid methods (of Galerkin type) for symmetric positive definite and semi-positive definite linear systems arising from the discretization of scalar partial differential equations (PDEs). We relate the so-called smoothing factor to the actual two-grid convergence rate and also to the convergence rate of the V-cycle multigrid. We derive a two-sided bound that defines an interval containing both the two-grid and V-cycle convergence rate. This interval is narrow and away from 1 when both the smoothing factor and an additional parameter are small enough. Besides the smoothing factor, the convergence mainly depends on the angle between the range of the prolongation and the eigenvectors of the system matrix associated with small eigenvalues. Nice V-cycle convergence is guaranteed if the tangent of this angle has an upper bound proportional to the eigenvalue, whereas nice two-grid convergence requires a bound proportional to the square root of the eigenvalue. We also discuss the well-known rule which relates the order of the prolongation to that of the differential operator associated to the problem. We first define a frequency based order which in most cases amounts to the so-called high frequency order as defined in Hemker (J Comput Appl Math 32:423–429, 1990). We give a firmer basis to the related order rule by showing that, together with the requirement of having the smoothing factor away from one, it provides necessary and sufficient conditions for having the two-grid convergence rate away from 1. A stronger condition is further shown to be sufficient for optimal convergence with the V-cycle. The presented results apply to rigorous Fourier analysis for regular discrete PDEs, and also to local Fourier analysis via the discussion of semi-positive systems as may arise from the discretization of PDEs with periodic boundary conditions.