求解带间断系数非线性椭圆问题的两重网格法

李明; 郑洲顺; 赵金娥

doi:10.13718/j.cnki.xdzk.2019.05.008

摘要: 利用有限差分法离散带间断系数的非线性椭圆问题，针对离散后所得到的非线性方程组，从减少计算量的角度出发，只使用一个辅助的粗层网格空间，并在最细层网格上求解线性校正方程组，构造了两重网格（NETG）法.数值结果表明，新算法在计算量和计算时间方面优于以往的算法.

Abstract: An efficient two-level method is studied to solve the nonlinear systems which arise from a nonlinear elliptic problem with a jumping coefficient by a finite difference method. Only one auxiliary coarse grid space is needed with a suitable mesh size discretization, and linear correction equations are applied instead of the nonlinear systems on the finest grid space. Numerical results are given to verify the computational cost and efficiency of the proposed approach and the results are compared with the existing numerical methods for solving nonlinear elliptic problems with a jumping coefficient.

Key words:

全文HTML

多重网格法(Multigrid method，MG)是求解偏微分方程离散化方程组的高性能计算方法^[1-10].

目前，关于求解带间断系数的非线性椭圆问题的多重网格法鲜见报道.为发展带间断系数的非线性椭圆问题的快速数值算法，本文通过减少辅助的粗网格空间、降低细层网格上的计算量，提出了基于差分格式的两重网格(NETG)法.数值试验表明，在相同计算精度的前提下，本文算法在计算量和计算时间方面优于以往的瀑布型多重网格(CMG)法.本文算法可与其它离散格式结合，推广至其它非线性偏微分方程.

1. 模型问题

考虑与非线性Helmholtz方程、天体物理学中的Lane-Emden方程有着紧密联系的一类非线性椭圆问题

其中：Ω是一个二维多边形区域，$\nabla = {\left({\frac{\partial }{{\partial x}}, \frac{\partial }{{\partial y}}} \right)^T}$为梯度算子，f(u)是与x，y，u有关的函数，α＞0为已知的间断常系数，u=u(x，y)∈C₀²(Ω)为待求函数.

为便于讨论，取Ω为矩形区域[0，L_x]×[0，L_y]，将Ω沿x，y方向均分成m，n等份.即${h_x} = \frac{{{L_x}}}{m}$，${h_y} = \frac{{{L_y}}}{n}$.网格点(x_i，y_j)对应于x_i=i×h_x，y_j=j×h_y，i=0，1，2，…，m，j=0，1，2，…，n.在非边界点(x_i，y_j)处采用二阶中心差分格式离散模型问题(1)，可得到对应于步长h=max{h_x，h_y}的非线性方程组

其中u为待求的解向量，其维数依赖于步长h.

类似地，选取一组步长h_s=2^s-1h₁，可得一系列对应的网格层Ω_s和非线性方程组

文中用下标s从小到大表示网格从细到粗.

2. 两重网格法

在使用牛顿法、拟牛顿法等迭代法求解大规模非线性方程组时，选择一个合适的初始值，有助于降低求解过程中的迭代次数.为了给最细层网格上的非线性方程组提供初始值，文献[6-8]讨论了求解非线性椭圆问题的CMG法.这类方法的基本思路是，首先使用迭代法求解未知点较少的最粗层上的非线性方程组，接着使用插值算子为相邻细层网格上的非线性方程组提供迭代初始值，如此递进，直至最细层网格.

在CMG法中各粗层网格的主要作用是为了给最细层网格提供初始值.为了减少这些辅助网格层上的计算量，我们使用插值算子，将最粗层网格的解插值到最细层网格，为该层上的非线性方程组的求解提供迭代初始值.

另一方面，在相同未知点规模的情况下，非线性方程组的求解代价高于线性方程.为降低求解非线性方程组的计算量，借鉴文献[9]的思路，在最细层网格上只需求解线性校正方程组，以降低该层上的求解计算量.

综上可知，通过减少中间辅助网格层以及在细层上求解线性方程代替直接求解非线性方程都可降低计算量.基于这种思路，我们设计了求解带间断系数的非线性椭圆方程离散化方程组的两重网格(NETG)法，其核心思想是选择合适步长，离散形成粗细两层网格，使用插值算子将粗网格上的非线性方程组的高精度近似解插值到细层上，为该层上的线性校正方程组的求解提供迭代初始值.该算法过程如下

算法1  两重网格法(NETG)

步骤1  给定误差限ε₁，ε₂，以u_M⁰为初始值，迭代m_M次求解F_M(u)=0，得u_M^*.

步骤2  将u_M^*插值到细网格Ω₁上得u₁⁰，置A₁⁰：=F₁^′(u₁⁰)，置k：=0.

步骤3  计算b₁^k：=F₁(u₁^k)，求解线性校正方程组A₁⁰◇u₁^k=-b₁^k得◇u₁^k，并置

步骤4  置k：=k+1，u₁^k：=u₁^k+1.若‖F₁(u₁^k)‖≤ε₁或‖◇u₁^k‖≤ε₂，置m₁：=k，u₁^*：=u₁^k，否则转步骤3.

注  F₁^′(u₁⁰)表示非线性函数F₁(u)在u₁⁰处的Jacobian矩阵.

可以看出，NETG法只使用了两个网格层(即粗层Ω_M和细层Ω₁)，无需使用中间网格层，并且在最细网格层上只需要求解线性校正方程组，因此该算法结构简单，计算量更少.

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

c	Ω_M	Ω₁	CMG			NETG
c	Ω_M	Ω₁	e	r	t/s	e	r	t/s
10^-8	80*80	640*640	1.72e-06	53，3，3，2	40.8	1.72e-06	53，1	14.7
	100*100	800*800	1.10e-06	53，3，2，2	68.6	1.10e-06	53，1	26.7
10^-4	80*80	640*640	1.72e-06	31，3，3，2	31.1	1.72e-06	31，1	12.2
	100*100	800*800	1.10e-06	30，3，2，2	61.0	1.10e-06	30，1	21.3
10³	80*80	640*640	9.23e-06	8，3，3，2	26.2	9.23e-06	8，1	11.2
	100*100	800*800	5.90e-06	8，2，2，2	56.4	5.90e-06	8，1	20.4
10⁹	80*80	640*640	9.27e-06	9，3，3，3	36.7	9.27e-06	9，3	12.5
	100*100	800*800	5.93e-06	9，3，3，3	66.9	5.93e-06	9，3	21.5

c	Ω_M	Ω₁	CMG			NETG
c	Ω_M	Ω₁	e	r	t/s	e	r	t/s
10^-8	80*80	640*640	1.25e-05	88，3，3，3	57.8	1.25e-05	88，2	22.4
	100*100	800*800	8.00e-06	88，3，3，3	104.6	7.96e-06	88，1	28.7
10^-4	80*80	640*640	1.25e-05	80，3，3，3	42.3	1.25e-05	80，2	19.8
	100*100	800*800	8.00e-06	79，3，3，3	88.9	7.97e-06	79，1	22.4
10⁴	80*80	640*640	1.26e-05	39，3，3，3	41.2	1.26e-05	39，2	20.5
	100*100	800*800	8.12e-06	39，3，3，3	60.2	8.08e-06	39，1	21.4
10⁸	80*80	640*640	1.26e-05	39，3，3，3	47.3	1.26e-05	39，3	20.1
	100*100	800*800	8.12e-06	39，3，3，3	67.8	8.08e-06	39，3	21.4

[1]	BRANDT A. Multi-Level Adaptive Solutions to Boundary-Value Problems[J]. Mathematics of Computation, 1977, 31(138):333-390. doi: 10.1090/S0025-5718-1977-0431719-X
[2]	LI M, LI C L, CUI X Z, et al. Cascadic Multigrid Methods Combined with Sixth Order Compact Scheme for Poisson Equation[J]. Numerical Algorithms, 2016, 71(4):715-727. doi: 10.1007/s11075-015-0018-2
[3]	李明, 赵金娥.二维椭圆问题的经济外推瀑布多重网格法[J].西南大学学报(自然科学版), 2014, 36(7):68-72. doi: http://xbgjxt.swu.edu.cn/jsuns/jsuns/ch/reader/view_abstract.aspx?file_no=2014-07-068&flag=1
[4]	LI M, LI C L. New Cascadic Multigrid Methods for Two-Dimensional Poisson Problem Based on the Fourth-Order Compact Difference Scheme[J]. Mathematical Methods in the Applied Sciences, 2018, 41(3):920-928. doi: 10.1002/mma.v41.3
[5]	潘克家, 汤井田, 胡宏伶, 等.直流电阻率法2. 5维正演的外推瀑布式多重网格法[J].地球物理学报, 2012, 55(8):2769-2778. doi: http://d.old.wanfangdata.com.cn/Periodical/dqwlxb201208028
[6]	TIMMERMANN G. A Cascadic Multigrid Algorithm for Semilinear Elliptic Problems[J]. Numerische Mathematik, 2000, 86(4):717-731. doi: 10.1007/PL00005416
[7]	邹战勇.半线性椭圆型问题Mortar有限元逼近的瀑布型多重网格法[J].数学理论与应用, 2006, 26(1):39-41. doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=sxllyyy200601011
[8]	禹海雄, 孙哲.一类半线性椭圆问题的瀑布型多重网格法[J].湖南大学学报(自然科学版), 2011, 38(8):79-81. doi: http://d.old.wanfangdata.com.cn/Periodical/hndxxb201108017
[9]	禹海雄.几类非线性问题的多重网格解法[D].长沙: 湖南大学, 2011.
[10]	陈维翰.用多重网格法改进偏微分方程反问题的广义脉冲谱算法[J].贵州师范大学学报(自然科学版), 1995, 13(4):1-6. doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK199500360330

留言板