Research and implementation of double Simpson's recursive algorithm
-
摘要: 针对双梯形递推算法收敛速度慢、节点利用不充分的问题,提出一种精度更高、算法收敛更快的方法——双辛普森递推算法,由此推导出二重积分在矩形区域下区间逐次减半的双辛普森递推公式,并给出具体的算法实现以及应用该算法分别计算矩形区域和不规则区域下连续函数的二重积分问题。通过计算上半椭球曲面的面积,对比得出双辛普森递推算法比双梯形递推算法的收敛速度更快、计算精度更高、程序计算时间更短的结论。最后通过求解弦振动方程的初值问题,给出双辛普森递推算法在一般积分区域下二重积分计算的应用,从而说明双辛普森递推算法的适用性更强,进一步说明该算法在偏微分方程领域中的应用。Abstract: aiming at the problems of slow convergence speed and insufficient node utilization of the double trapezoidal recursion algorithm, a method with higher accuracy and faster convergence of the algorithm—double simpson recursion algorithm is proposed, from which the double simpson recursion formula of double integration is halved in the interval under a rectangular region, and the specific algorithm implementation is given. the algorithm is applied to calculate the double integration problem of continuous functions under rectangular region and irregular region, respectively. by calculating the area of the upper semi-ellipsoidal surface, it is concluded that the double simpson recursion algorithm has faster convergence speed, higher calculation accuracy and shorter program calculation time than the double trapezoidal recursion algorithm. finally, by solving the initial value problem of the chord vibration equation, the application of the double simpson recursion algorithm in the double integral calculation under the general integration region is given, which shows that the applicability of the double simpson recursion algorithm is stronger, and the application of the algorithm in the field of partial differential equations is further explained.
-
0. 引言
近年来,二重积分的数值解法问题备受国内外学者的关注。刘海峰和陈敏歌[1]首次根据定积分的复化梯形公式,推导出区间逐次减半的双梯形递推公式来数值求解二重积分,并给出双梯形递推算法的实现过程,此外,存在该算法计算二重积分的精度较差、算法的收敛性较慢等问题;宁桂英和周永权[2]利用类似于遗传算法的思想,提出差分进化算法来求解二重积分的近似值,这种算法虽然在二重积分被积表达式形式比较简单的情况下收敛速度较快、精度较高,但当二重积分的形式很复杂时,会出现程序的运行时间较慢、计算精度不是很好控制等问题,尤其表现在偏微分方程的求解方面;于丽妮[3]、李满枝等[4]、刘辉玲和叶锋[5]、黎锁平[6]采用概率论中几何概型的思想,将二重积分的计算转换成概率的计算,由此运用蒙特卡罗法来求二重积分的近似值。利用统计方法求二重积分的近似值主要是根据二重积分的几何意义:曲顶柱体的体积将体积的计算转化成概率的计算,但是由于概率本身是通过随机数体现的,而随机数中分布的选取可能会对二重积分的结果造成一定的误差,最常见的就是正态分布生成随机数的方法,但是如果一个二重积分本身就是带有统计色彩,实际问题中概率分布一般都是非参数统计类的分布,这样贸然选取就会出现众多问题;许小勇和周凤英[7]利用Laguerre小波及其积分算子矩阵,结合矩阵论的知识对二重积分进行数值求解,此算法主要是将二重积分的计算转换成矩阵的计算,这样如果矩阵中的元素的量级较大的话,可能会产生较大的误差;Ranjan和Damayanti[8]以及Siraj等[9]分别利用混合求积规则和Haar小波来数值求解二重积分的近似值;Abdulhameed和Memon[10]利用改进的梯形法则,来求解二重积分。另一方面,在实际应用中[11-15],二重积分的被积表达式或者其积分区域过于复杂,会出现无法利用牛顿-莱布尼茨公式直接求解或者很难求得其精确解的情况。由此可见,研究二重积分的数值解法对于求解二重积分至关重要。
为了解决区间逐次减半的双梯形递推算法计算精度较低、链表节点分裂次数较多、算法运行时间较长等问题,本文基于二重积分区间逐次减半的双梯形递推算法[1]来研究二重积分区间逐次减半的双辛普森递推算法,并与文献[1]中的双梯形递推算法进行对比。为体现双辛普森递推算法的优势所在,针对文献[17]将双辛普森递推算法应用到偏微分方程领域并给出弦振动方程的数值求解方法。通过对偏微分方程的求解,体现了双辛普森递推算法本身优势以及其研究意义所在。
1. 双辛普森递推公式的理论推导
1.1 矩形区域上二重积分的双辛普森公式
对矩形区域$D=[a, b] \times[c, d]$,求下列连续函数$f(x, y)$的二重积分
$$ I=\iint \limits_D f(x, y) \mathrm{d} \sigma_{\circ} $$ (1) 首先将积分区域D剖分:将x轴上[a,b]进行m等分,将y轴上[c,d]进行n等分,形成m × n个小矩形区域$D_{i j}=\left[x_{i-1}, x_i\right] \times\left[y_{j-1}, y_j\right]$。其中:$x_i, y_j$分别为x,y方向上的分点且$x_i=a+i h_m, y_j=c+j t_n$。其中:$i=0, 1, \cdots, m ; j=0, 1, \cdots, n$且$h_m=\frac{b-a}{m} ; t_n=\frac{d-c}{n}$。于是在小矩形区域Dij上对连续函数f(x,y) 的二重积分为
$$ I_{i j}=\iint \limits_{D_{i j}} f(x, y) \mathrm{d} \sigma=\int_{y_{j-1}}^{y_j} \mathrm{~d} y \int_{x_{i-1}}^{x_i} f(x, y) \mathrm{d} x $$ (2) 分别在x、y方向上针对一元函数定积分均使用一维辛普森公式得到关于式(2)的二重积分在小矩形区域$D_{i j}$上的双辛普森求积公式为
$$ \begin{gathered} I_{i j} \approx \frac{h_m}{6} \int_{y_{j-1}}^{y_j}\left[f\left(x_{i-1}, y\right)+4 f\left(x_{i-\frac{1}{2}}, y\right)+f\left(x_i, y\right)\right] \mathrm{d} y \approx \\ \frac{h_m t_n}{36}\left[f\left(x_{i-1}, y_{j-1}\right)+4 f\left(x_{i-1}, y_{j-\frac{1}{2}}\right)+f\left(x_{i-1}, y_j\right)+\right. \\ 4 f\left(x_{i-\frac{1}{2}}, y_{j-1}\right)+16 f\left(x_{i-\frac{1}{2}}, y_{j-\frac{1}{2}}\right)+4 f\left(x_{i-\frac{1}{2}}, y_j\right)+ \\ \left.f\left(x_i, y_{j-1}\right)+4 f\left(x_i, y_{j-\frac{1}{2}}\right)+f\left(x_i, y_j\right)\right]。 \end{gathered} $$ (3) 让i、j变动,反复使用式(3),再由重积分对积分区域具有可加性,做进一步推演,即可得出对矩形区域D上的连续函数f(x,y) 的二重积分的双辛普森求积公式为
$$ I=\sum\limits_{i=1}^m \sum\limits_{j=1}^n I_{i j}。 $$ (4) 1.2 矩形区域上二重积分区间逐次减半双辛普森递推算法
在1.1节的基础上,对矩形区域D划分规则予以改变,进一步做第l次划分:将x方向上的区间[a,b]做2l等分,则每个小区间的长度记为h2l,分点为$a=x_0^{(l)}<x_1^{(l)}<\cdots<x_{2^l}^{(l)}=b$且满足$x_i^{(l)}=a+i h_{2^l}\left(i=0,1, \cdots, 2^l\right)$;同样对y方向上的区间[c,d] 做2l等分,则每个小区间的长度记为t2l,分点为$c=y_0^{(l)}<y_1^{(l)}<\cdots<y_{2^l}^{(l)}=d$且满足$y_j^{(l)}=c+j t_{2^l} \quad(j=\left.0, 1, \cdots, 2^l\right)$。于是在小矩形区域$\left[x_{i-1}^{(l)}, x_i^{(l)}\right] \times\left[y_{j-1}^{(l)}, y_j^{(l)}\right]$上对连续函数f(x,y) 的二重积分为
$$ \begin{gathered} I_{i j}^{(l)} \approx \frac{h_{2^l} t_{2^l}}{36}\left[f\left(x_{i-1}^{(l)}, y_{j-1}^{(l)}\right)+4 f\left(x_{i-1}^{(l)}, y_{j-\frac{1}{2}}^{(l)}\right)+\right. \\ f\left(x_{i-1}^{(l)}, y_j^{(l)}\right)+4 f\left(x_{i-\frac{1}{2}}^{(l)}, y_{j-1}^{(l)}\right)+ \\ 16 f\left(x_{i-\frac{1}{2}}^{(l)}, y_{j-\frac{1}{2}}^{(l)}\right)+4 f\left(x_{i-\frac{1}{2}}^{(l)}, y_j^{(l)}\right)+ \\ \left.f\left(x_i^{(l)}, y_{j-1}^{(l)}\right)+4 f\left(x_i^{(l)}, y_{j-\frac{1}{2}}^{(l)}\right)+f\left(x_i^{(l)}, y_j^{(l)}\right)\right] 。 \end{gathered} $$ (5) 由于重积分对积分区域具有可加性,进一步推演,从而就得到在第l次区域划分时,对整个矩形区域D上的连续函数f(x,y)的二重积分双辛普森求积公式为
$$ I^{(l)}=\sum\limits_{i=1}^{2^l} \sum\limits_{j=1}^{2^l} I_{i j}^{(l)} 。 $$ (6) 为了更方便、更高效地使用式(6)对二重积分进行数值求解,以下特将式(6)转化成递推公式进行求解。
引入集合来对式(6)进行分类合并。令$\varOmega_x^l=\left\{x_0^{(l)}, x_1^{(l)}, \cdots, x_{2^l}^{(l)}\right\}$与$\varOmega_y^l=\left\{y_0^{(l)}, y_1^{(l)}, \cdots, y_{2^l}^{(l)}\right\}$的笛卡尔积表示第l次区域划分时所有网格节点构成的集合$\varOmega_{x y}^l=\varOmega_x^l \times \varOmega_y^l$。将这个网格节点集$\varOmega_{x y}^l$分为6个子集,见图 1。
(1)大矩形区域D的4个顶点构成的点集$\varOmega_o^l=\left\{\left(x_0^{(l)}, y_0^{(l)}\right), \left(x_0^{(l)}, y_{2^l}^{(l)}\right), \left(x_{2^l}^{(l)}, y_0^{(l)}\right), \left(x_{2^l}^{(l)}, y_{2^l}^{(l)}\right)\right\}$。
(2)所有剖分区域的小矩形在大矩形区域D上的边界点构成的点集$\varOmega_{\Delta}^l=\left\{\left(x_0^{(l)}, y_j^{(l)}\right) \mid 0<j<2^l\right\} \cup\left\{\left(x_i^{(l)}, y_0^{(l)}\right) \mid 0<i<2^l\right\} \cup\left\{\left(x_{2^l}^{(l)}, y_j^{(l)}\right) \mid 0<j<2^l\right\} \cup$\left\{\left(x_i^{(l)}, y_{2^l}^{(l)}\right) \mid 0<i<2^l\right\}$(即为图 1中三角形的位置)。
(3)所有剖分区域的小矩形在大矩形区域D上的内部点(不包含内部的中间点)构成的点集$\varOmega_{\oplus}^l=\left\{\left(x_i^{(l)}, y_j^{(l)}\right) \mid 0<i<2^l, 0<j<2^l\right\}$(即为图 1中大矩形内部的小圆圈所在位置)。
(4)所有剖分区域的小矩形在大矩形区域D的边界同一个边界轴上任意2个端点的中点构成的点集
$$ \begin{gathered} \varOmega_{\otimes}^l=\left\{\left.\left(x_0^{(l)}, y_{j-\frac{1}{2}}^{(l)}\right) \right\rvert\, 1 \leqslant j \leqslant 2^l\right\} \cup\left\{\left.\left(x_{i-\frac{1}{2}}^{(l)}, y_0^{(l)}\right) \right\rvert\, 1 \leqslant i \leqslant 2\right\}^l \cup \\ \left\{\left.\left(x_{2^l}^{(l)}, y_{j-\frac{1}{2}}^{(l)}\right) \right\rvert\, 1 \leqslant j \leqslant 2^l\right\} \cup\left\{\left.\left(x_{i-\frac{1}{2}}^{(l)}, y_{2^l}^{(l)}\right) \right\rvert\, 1 \leqslant i\right\} \leqslant 2^l, \end{gathered} $$ 即为图 1中大矩形的4个边界上的实线与虚线的交点组成的集合。
(5)所有剖分区域的小矩形在大矩形区域D内部的同一个内部轴上任意2个端点的中点构成的点集
$$ \begin{gathered} \varOmega_{\varPsi}^l=\left\{\left.\left(x_i^{(l)}, y_{j-\frac{1}{2}}^{(l)}\right) \right\rvert\, 0<i<2^l, 1 \leqslant j \leqslant 2^l\right\} \cup \\ \left\{\left.\left(x_{i-\frac{1}{2}}^{(l)}, y_j^{(l)}\right) \right\rvert\, 1 \leqslant i \leqslant 2^l, 0<j<2^l\right\}, \end{gathered} $$ 即为图 1中大矩形内部实线与虚线以及虚线与实线的交点构成的集合)。
(6)所有剖分区域的小矩形内部中点构成的点集
$$ \varOmega_{▱}^l=\varOmega_{x y}^l-\varOmega_o^l-\varOmega_{\triangle}^l-\varOmega_{\oplus}^l-\varOmega_{\otimes}^l-\varOmega_{\Psi}^l, $$ 即为图 1中大矩形内部虚线与虚线的交点构成的集合。
根据前一次的区域划分与后一次的区域划分并利用上面所记符号将式(5)代入式(6)进行合并整理得到,在第l次区域划分时,对整个矩形区域D上的连续函数$f(x, y)$的二重积分的双辛普森求积公式为
$$\begin{aligned} I^{(l)} \approx & \frac{h_{2^l} t_{2^l}}{36}\left[\sum_{P_o^{(l)} \in \varOmega_o^l} f\left(P_o^{(l)}\right)+2 \sum_{P_{\Delta}^{(l)} \in \varOmega_{\Delta}^l} f\left(P_{\Delta}^{(l)}\right)+\right. \\ & 4 \sum_{P_{\oplus}^{(l)} \in \varOmega_{\oplus}^l} f\left(P_{\oplus}^{(l)}\right)+4 \sum_{P_{\otimes}^{(l)} \in \varOmega_{\otimes}^l} f\left(P_{\otimes}^{(l)}\right)+ \\ & \left.8 \sum_{P_\Psi^{(l)} \in \varOmega_\Psi^l} f\left(P_\Psi^{(l)}\right)+16 \sum_{P_{▱}^{(l)} \in \varOmega_{▱}^l} f\left(P_{▱}^{(l)}\right)\right] 。 \end{aligned} $$ (7) 为了以下书写的方便,现将式(7)右端记为Q(l),即
$$ \begin{aligned} Q^{(l)}= & \frac{h_{2^l} t_{2^l}}{36}\left[\sum\limits_{P_o^{(l)} \in \varOmega_o^l} f\left(P_o^{(l)}\right)+2 \sum\limits_{P_{\Delta}^{(l)} \in \varOmega_{\Delta}^l} f\left(P_{\Delta}^{(l)}\right)+\right. \\ & 4 \sum\limits_{P_{\otimes}^{(l)} \in \varOmega_{\oplus}^l} f\left(P_{\oplus}^{(l)}\right)+4 \sum\limits_{P_{\otimes}^{(l)} \in \varOmega_{\otimes}^l} f\left(P_{\otimes}^{(l)}\right)+ \\ & \left.8 \sum\limits_{P_\Psi^{(l)} \in \varOmega_\Psi^l} f\left(P_\Psi^{(l)}\right)+16 \sum\limits_{P_{▱}^{(l)} \in \varOmega_{▱}^l} f\left(P_{▱}^{(l)}\right)\right]_{\circ} \end{aligned} $$ 同理可得,在第l − 1次区域划分时,对整个矩形区域D上的连续函数f(x,y) 的二重积分的双辛普森求积公式为
$$ \begin{gathered} I^{(l-1)} \approx Q^{(l-1)}=\frac{h_{2^{l-1}} t_{2^{l-1}}}{36}\left[\sum\limits_{P_o^{(l-1)} \in \varOmega_o^{l-1}} f\left(P_o^{(l-1)}\right)+\right. \\ 2 \sum\limits_{P_{\Delta}^{(l-1)} \in \varOmega_{\Delta}^{l-1}} f\left(P_{\Delta}^{(l-1)}\right)+4 \sum\limits_{P_{\oplus}^{(l-1)} \in \varOmega_{\oplus}^{l-1}} f\left(P_{\oplus}^{(l-1)}\right)+ \\ 4 \sum\limits_{P_{\otimes}^{(l-1)} \in \varOmega_{\oplus}^{l-1}} f\left(P_{\otimes}^{(l-1)}\right)+8 \sum\limits_{P_\Psi^{(l-1)} \in \varOmega_\Psi^{l-1}} f\left(P_\Psi^{(l-1)}\right)+ \\ \left.16 \sum\limits_{P_{▱}^{(l-1)} \in \varOmega_{▱}^{l-1}} f\left(P_{▱}^{(l-1)}\right)\right] . \end{gathered} $$ 考虑到
$$ \begin{gathered} h_{2^{l-1}}=2 h_{2^l}, t_{2^{l-1}}=2 t_{2^l}, \varOmega_o^{l-1}=\varOmega_o^l, \\ \varOmega_{\Delta}^l=\varOmega_{\otimes}^{l-1} \cup \varOmega_{\Delta}^{l-1}, \varOmega_{\oplus}^l=\varOmega_{\oplus}^{l-1} \cup \varOmega_\psi^{l-1} \cup \varOmega_{▱}^{l-1}, \end{gathered} $$ 及$\varOmega_{\otimes}^l, \varOmega_\psi^l, \varOmega_{▱}^l$是区域分裂时的新生点集,于是就有在第l次区域划分时,对整个矩形区域D上连续函数f(x,y)上的二重积分的双辛普森递推算法的求积公式为
$$ \begin{gathered} Q^{(l)}=\frac{h_{2^l} t_{2^l}}{36}\left\{\sum\limits_{P_o^{(l-1)} \in \varOmega_o^{l}-1} f\left(P_o^{(l-1)}\right)+2\left[\sum\limits_{P_{\Delta}^{(l-1)} \in \varOmega_{\Delta}^{l-1}} f\left(P_{\Delta}^{(l-1)}\right)+\right.\right. \\ \left.\sum\limits_{P_{\otimes}^{(l-1)} \in \varOmega_{\otimes}^{l-1}} f\left(P_{\otimes}^{(l-1)}\right)\right]+4\left[\sum\limits_{P_{\oplus}^{(l-1)} \in \varOmega_{\oplus}^{l-1}} f\left(P_{\oplus}^{(l-1)}\right)+\right. \\ \left.\sum\limits_{P_\varPsi^{(l-1)} \in \varOmega_\varPsi^{(-1)}} f\left(P_\varPsi^{(l-1)}\right)+\sum\limits_{P_{▱}^{(l-1)} \in \varOmega_{▱}^{(l-1}} f\left(P_{▱}^{(l-1)}\right)\right]+ \\ 4 \sum\limits_{P_{\otimes}^{(l)} \in \varOmega_{\otimes}^{l}} f\left(P_{\otimes}^{(l)}\right)+8 \sum\limits_{P_\varPsi^{(l)} \in \varOmega_\varPsi^{l}} f\left(P_\varPsi^{(l)}\right)+ \\ \left.16 \sum\limits_{P_{▱}^{(l)} \in \varOmega_{▱}^{l}} f\left(P_{▱}^{(l)}\right)\right\} 。 \end{gathered} $$ 即
$$ \begin{gathered} Q^{(l)}=\frac{1}{4} Q^{(l-1)}+\frac{h_{2^l} t_{2^l}}{36}\left[-2 \sum\limits_{P_{\otimes}^{(l-1)} \in \varOmega_{\otimes}^{l-1}} f\left(P_{\otimes}^{(l-1)}\right)+\right. \\ 4 \sum\limits_{P_{\otimes}^{(l)} \in \varOmega_{\otimes}^{l}} f\left(P_{\otimes}^{(l)}\right)-4 \sum\limits_{P_\Psi^{(l-1)} \in \varOmega_\Psi^{l-1}} f\left(P_\Psi^{(l-1)}\right)+ \\ 8 \sum\limits_{P_\Psi^{(l)} \in \varOmega_\Psi^{l}} f\left(P_\Psi^{(l)}\right)-12 \sum\limits_{P_{▱}^{(l-1)} \in \varOmega_{▱}^{l-1}} f\left(P_{▱}^{(l-1)}\right)+ \\ \left.16 \sum\limits_{P_{▱}^{(l)} \in \varOmega_{▱}^{l}} f\left(P_{▱}^{(l)}\right)\right]_{\circ} \end{gathered} $$ (8) 式中$l=1, 2, \cdots, Q^{(l)}$表示对$I^{(l)}$的近似。
为了进行逐步迭代求解,此时还需要设置初值,即当l = 0时,直接对矩形区域$D=[a, b] \times[c, d]$使用双辛普森公式得到
$$ \begin{gathered} Q^{(0)}=\frac{(b-a)(d-c)}{36}\left[f(a, c)+4 f\left(\frac{a+b}{2}, c\right)+f(b, c)+\right. \\ 4 f\left(a, \frac{c+d}{2}\right)+16 f\left(\frac{a+b}{2}, \frac{c+d}{2}\right)+4 f\left(b, \frac{c+d}{2}\right)+ \\ \left.f(a, d)+4 f\left(\frac{a+b}{2}, d\right)+f(b, d)\right] 。 \end{gathered} $$ (9) 1.3 不规则积分区域的计算方法
对于一般积分区域,求连续函数的二重积分问题[16],可以利用微元法的思想将一般积分区域分割成比较小的积分区域,此时这些小的积分区域就可以近似地看成矩形区域,然后在每个小矩形区域上应用双辛普森递推算法计算此连续函数的二重积分,再利用二重积分区域的可加性将这些二重积分的值相加,即可得到连续函数在一般区域下的二重积分计算的近似值。
2. 二重积分双辛普森递推算法流程
该算法在Visual Studio 2022编译器中使用C语言进行算法的编写与实现。为了确保二重积分计算的准确性,使用的数据类型均为double类型,该算法的具体流程有如下步骤。
(1)定义链表节点的数据结构typedef struct node {double data; struct node* next; }LinkList。
(2)申请x、y方向上的链表头节点空间,分别用LinkList* XHead和LinkList* YHead指向这2个链表头节点。
(3)定义初始化x、y这2个方向上链表的函数double init_list(LinkList* head,double *f,double *l),其中*f指向x、y区间的上界值,*l指向x、y区间的下界值。初始化过程包括申请该方向的2个节点fnode和lnode,其中fnode节点存储x、y区间输入方向的上界值,lnode节点存储x、y区间输入方向的下界值,然后将lnode节点先插入到头节点后,fnode再插入到lnode节点后,最后分别返回x、y方向积分区间的长度。
(4)定义链表裂变函数void split(LinkList* head),申请一个新的节点空间,新节点存储相邻两个节点数据域的平均值,然后将该节点插入到这2个相邻节点之间。
(5)定义被积函数double ff(double x,double y)。
(6)定义链表求长函数int Length(LinkList* head)。
(7)定义链表节点求和函数void newNode_add(LinkList* head1,LinkList* head2,double* lineMidPiont_m,double* InnerLinePiont_m,double* InnerMidPiont_m,double* lineMidPiont_m1,double* InnerLinePiont_m1,double* InnerMidPiont_m1),该函数lineMidPiont_m是链表第m次分裂积分区域的$\varOmega_{\otimes}^m$点集(边界中点)的函数值之和; InnerLinePiont_m是链表第m次分裂积分区域的$\varOmega_\varPsi^m($(内界点)点集的函数值之和; InnerMidPiont_m是链表第m次分裂积分区域的$\varOmega_{▱}^m$点集(内中点)的函数值之和; lineMidPiont_m1是链表第m-1次分裂积分区域的$\varOmega_{\otimes}^{m-1}$点集的函数值之和; InnerLinePiont_m1是链表第m-1次分裂积分区域的$\varOmega_\varPsi^{m-1}$点集的函数值之和; InnerMidPiont_m1是链表第m-1次分裂积分区域的$\varOmega_{▱}^{m-1}$点集的函数值之和。根据链表裂变的特征,除去矩形区域的4个顶点,m次分裂边界中点的值可以由2个相邻节点的平均值求出,若规定下标从0开始,m-1次分裂的边界中点就是m次分裂的下标为奇数的节点;m次分裂的内中点为划分后的小矩形区域的中间点,m-1次分裂的内中点为2个方向上的链表节点下标同时为奇数对应的点;m次分裂的内界点为划分后小矩形区域边界的中间点,具体特征为一个方向的链表节点下标为奇数,另一个方向的2个相邻节点的中间点所对应的点,而m-1次分裂的内中点具体特征为一个方向上的链表节点下标为奇数,另一个方向上的链表节点下标为偶数。根据上述节点的位置特征,可以实现该函数的具体功能。
(8)计算积分区域上的初始积分值。
(9)使用QueryPerformanceFrequency(LARGE_INTEGER *a)函数获得计算机高精度计时器的频率,接着定义LARGE_INTEGER start变量,调用QueryPerformanceCounter( & start)函数记录每次计算二重积分的开始时刻。
(10)利用for循环并结合二重积分的双辛普森递推算法的求积公式,计算每次分裂后的二重积分近似值,并将此次分裂的二重积分近似值与前一次分裂的二重积分近似值作差取绝对值作为此次区间分裂的二重积分计算精度,并用double类型的变量ee存储起来并输出。
(11)当每次迭代的精度达到所要求的精度或者最大节点分裂次数时,迭代终止计算。同时,定义变量LARGE_INTEGER over,使用QueryPerformanceCounter(&over)函数记录二重积分计算的结束时刻,输出最终计算的二重积分近似值以及程序运行所用时间(结束时间减去开始时间,以ms为单位)。
为了更直观地展示双辛普森递推算法的实现过程,将该算法通过流程图来描述,如图 2所示。
3. 计算案例以及算法复杂度分析
下面将对同一问题、在同一计算精度要求下、用同样Windows系统及其Visual Studio 2022编译环境下即相同软硬件环境下进行双梯形递推算法和双辛普森递推算法的复杂度对比分析。
例题1 求矩形闭区域$[0, 1] \times[0, 2 \pi]$上的二重积分[1]
$$ \iint \limits_{[0, 1] \times[0, 2 \pi]} f(r, \theta) \mathrm{d} r \mathrm{~d} \theta $$ (10) 其中
$$ f(r, \theta)=a b r \sqrt{1+\frac{R^2 r^2}{1-r^2}\left(\frac{\cos ^2 \theta}{a^2}+\frac{\sin ^2 \theta}{b^2}\right)}, $$ 且$\theta \in[0, 2 \pi], r \in[0, 1)$。
积分式(10)是著名的教堂顶部曲面(半椭球曲面)面积问题,由于式(10)是关于r的瑕点为1的二重瑕积分,因此取积分上限的极限值0.999 9来代替1。对于参数$a=30.6, b=29.6, R=30$,在相同的精度要求$\left|Q^{(l)}-Q^{(l-1)}\right|<10^{-2}$下,基于相同的软硬件计算环境,分别使用文献[1]中双梯形递推算法(算法1)和双辛普森递推算法(算法2)得到的积分值对比结果如表 1所示。可知,在同一台计算机上,计算二重积分式(10)时,在节点分裂15次时双辛普森递推算法的计算结果已经满足精度要求,而双梯形递推算法在节点分裂17次时前后2次计算结果还有较大变化,不满足精度要求,这说明了双辛普森递推算法的收敛速度比双梯形递推算法的收敛速度更快。
表 1 2种算法结果对比例题1分裂次数 算法1 算法2 近似值 计算时间/ms 近似值 计算时间/ms 0 197 230.276 0 67 922.750 0 1 100 223.811 0.16 36 792.864 0.59 2 52 917.585 0.20 20 610.312 1.02 3 28 686.133 0.24 12 770.284 1.17 $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ 12 5 605.039 4.21×103 5 597.105 2.51×104 13 5 599.088 1.71×104 5 596.802 9.64×104 14 5 597.373 7.40×104 5 596.767 3.85×105 15 5 596.919 3.04×105 5 596.764 1.53×106 16 5 596.803 1.23×106 — — 17 5 596.774 4.56×106 — — 注:算法1代表双梯形递推算法;算法2代表双辛普森递推算法;—指无数据。 以下绘制出这2种算法的积分近似值与链表节点分裂次数之间的关系如图 3所示。可知,在同一台计算机上,计算二重积分式(10)时,在初始节点分裂时,双辛普森递推算法的计算结果比双梯形递推算法更加快速接近精确值且双辛普森递推算法的积分近似值随节点分裂次数的变化幅度要比双梯形递推算法小得多,这说明双辛普森递推算法在节点分裂次数较少的情况下就能达到比较精确的计算结果,故双辛普森递推算法有更高的计算精度。
由表 1可知,算法2计算出$Q^{(15)}$时机器用时$1.53 \times 10^6 \mathrm{~ms}$,同时$\left|Q^{(15)}-Q^{(14)}\right| \approx 0.003<10^{-2}$;算法1计算出$Q^{(17)}$时机器用时$4.56 \times 10^6 \mathrm{~ms}$,这已经明显超过算法2计算出$Q^{(15)}$的机器用时,而相应的$\left|Q^{(17)}-Q^{(16)}\right| \approx 0.029>10^{-2}$,即还未达到计算精度的停机要求,这种情况表明在相同的计算精度要求下,算法2(即双辛普森递推算法)需要的计算时间明显少于算法1(即双梯形递推算法)的计算时间,从而说明了双辛普森递推算法的时间优势。
在相同的区间分裂次数的情况下,计算下一个$Q^{(l)}$时,双辛普森递推算法需要计算新增节点函数值的节点个数明显多于双梯形递推算法需要计算新增节点函数值的节点个数。由此可知,并根据表 1的结果也验证了双辛普森递推算法比双梯形递推算法具有更高的收敛速度。
例题2 为了说明双辛普森递推算法对二重积分的一般区域也成立,以下通过计算偏微分方程中的一维波动方程解析解的例子来体现该算法的应用。
一维波动方程是针对弦振动现象而提出的。假设弦是无限长,满足弦振动方程的模型假设条件 [17],对如下的弦振动方程及其柯西问题
$$ \left\{\begin{array}{l} \frac{\partial^2 u}{\partial t^2}-\frac{\partial^2 u}{\partial x^2}=t \sin x, \\ \left.u\right|_{t=0}=0, \\ \left.\frac{\partial u}{\partial t}\right|_{t=0}=\sin x_{\circ} \end{array}\right. $$ (11) 根据二阶线性偏微分方程的有关知识,可以推导出柯西问题式(11)的解析解为
$$ \begin{gathered} u(x, t)=\frac{1}{2}\{[\cos (x-t)-\cos (x+t)]+ \\ \left.\iint \limits_{\substack{0 \leqslant \tau \leqslant t \\ x-(t-\tau) \leqslant \xi \leqslant x+(t-\tau)}} \tau \sin \xi \mathrm{d} \xi \mathrm{~d} \tau\right\} 。 \end{gathered} $$ (12) 对式(12)中后面的三角区域的二重积分问题采用如1.3所述的一般区域的二重积分的双辛普森递推算法进行数值求解。
取$x, t \in[0, 10]$,2个方向的步长均取0.5,利用1.3节所述的微元法的思想,将每个三角区域分别按照不同的划分方式划分成很多小矩形区域,分别在每个小矩形区域上使用双辛普森递推公式,最终将这些值相加即可得出式(12)的一种划分规则下的数值解。同时,对式(12)直接积分得,其解析解为$u(x, t)=t \sin x$。
为了量化划分区域的程度,采用划分的细度(即每个小矩形对角线长度的最大值)来描述划分区域的程度。在相同的精度$\left|Q^{(l)}-Q^{(l-1)}\right|<10^{-6}$和软硬件环境下,绘制出不同划分方式的误差分布情况(图 4)。可知,随着划分细度的减小,式(12)的数值解与解析解的平均误差也随之减小,在划分细度为0.007 1 m处,式(12)的数值解与解析解的平均误差为0.001 6,因此认为该划分方式为合理的区域划分方式。
最终根据上述区域划分方式计算出利用双辛普森递推公式求解得到的式(12)数值解与解析解对比数据(表 2)。可知,利用双辛普森递推算法计算式(12)时得到的数值解与其解析解之间的平均相对误差大多都集中在0.001的量级,说明利用双辛普森递推算法计算一般积分区域下的二重积分式(12)的值具有更高的精确度。
表 2 双辛普森递推算法部分数值解与解析解比较振动弦长的纵向位移/m 时间/s 解析解 数值解 平均相对误差 0.5 2.5 1.198 564 1.202 156 0.003 0 5 2.397 128 2.416 973 0.008 3 7.5 3.595 692 3.623 609 0.007 8 10 4.794 255 4.865 215 0.014 8 5 2.5 −2.397 311 −2.397 794 0.000 2 5 −4.794 621 −4.787 104 0.001 6 7.5 −7.191 932 −7.186 910 0.000 7 10 −9.589 243 −9.538 457 0.005 3 10 2.5 −1.360 053 −1.363 383 0.002 4 5 −2.720 106 −2.730 059 0.003 7 7.5 −4.080 158 −4.089 282 0.002 2 10 −5.440 211 −5.500 707 0.011 1 为了更直观地看出表 2数值解与解析解之间的差别,以下绘制出使用双辛普森递推算法计算出的数值解与解析解之间的对比图,以及相对误差随积分区域位置之间的关系如图 5和图 6所示。可知双辛普森递推算法只在个别点处相对误差较大,在大部分点相对误差较小;其数值解与解析解的吻合效果非常好,数值解基本上在解析解所处的曲面上,从而检验了一般区域下双辛普森递推算法计算出的结果的准确性和合理性。
经计算最终得出通过最优的划分方式,说明了在相同的精度和相同软硬件计算环境下,对于一般积分区域使用1.3所述的方法计算二重积分近似值,双辛普森递推算法的计算精度较高,更加有利于计算更为复杂的问题,从而更能体现双辛普森递推算法在偏微分方程领域中的应用。
4. 结束语
本文基于定积分的复化辛普森公式推导出二重积分的双辛普森递推公式,并给出了双辛普森递推算法实现的技术,得出了双辛普森递推算法的收敛速度比双梯形递推算法更快且其内存消耗更小的结论,同时在相同节点分裂次数下,双辛普森递推算法的舍入误差继承了上次分裂结果的1/4,因此大大提高了双辛普森递推算法的计算精度。由于其收敛速度快的原因,双辛普森递推算法计算时程序运行时间更短,这更能体现出双辛普森递推算法的优势所在。
-
表 1 2种算法结果对比例题1
分裂次数 算法1 算法2 近似值 计算时间/ms 近似值 计算时间/ms 0 197 230.276 0 67 922.750 0 1 100 223.811 0.16 36 792.864 0.59 2 52 917.585 0.20 20 610.312 1.02 3 28 686.133 0.24 12 770.284 1.17 $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ 12 5 605.039 4.21×103 5 597.105 2.51×104 13 5 599.088 1.71×104 5 596.802 9.64×104 14 5 597.373 7.40×104 5 596.767 3.85×105 15 5 596.919 3.04×105 5 596.764 1.53×106 16 5 596.803 1.23×106 — — 17 5 596.774 4.56×106 — — 注:算法1代表双梯形递推算法;算法2代表双辛普森递推算法;—指无数据。 表 2 双辛普森递推算法部分数值解与解析解比较
振动弦长的纵向位移/m 时间/s 解析解 数值解 平均相对误差 0.5 2.5 1.198 564 1.202 156 0.003 0 5 2.397 128 2.416 973 0.008 3 7.5 3.595 692 3.623 609 0.007 8 10 4.794 255 4.865 215 0.014 8 5 2.5 −2.397 311 −2.397 794 0.000 2 5 −4.794 621 −4.787 104 0.001 6 7.5 −7.191 932 −7.186 910 0.000 7 10 −9.589 243 −9.538 457 0.005 3 10 2.5 −1.360 053 −1.363 383 0.002 4 5 −2.720 106 −2.730 059 0.003 7 7.5 −4.080 158 −4.089 282 0.002 2 10 −5.440 211 −5.500 707 0.011 1 -
[1] 刘海峰, 陈敏歌. 二重数值积分双梯形递推算法的研究与实现[J]. 计算机工程与应用, 2006, 42(15): 94-96. [2] 宁桂英, 周永权. 一种求解二重积分的差分进化算法[J]. 哈尔滨理工大学学报, 2013, 18(2): 121-125. [3] 于丽妮. 基于MATLAB的蒙特卡罗方法求解二重积分[J]. 白城师范学院学报, 2017, 31(6): 33-36. [4] 李满枝, 王洪涛, 苗俊红. 二重积分的Monte-Carlo数值仿真[J]. 计算机仿真, 2011, 28(5): 114-117. [5] 刘辉玲, 叶锋. 计算多重积分的均匀随机数蒙特卡罗法的实现[J]. 电脑知识与技术, 2008, 4(35): 2289-2291. [6] 黎锁平. 运用蒙特卡罗方法求解随机性问题[J]. 甘肃工业大学学报, 2001, 27(2): 95-97. [7] 许小勇, 周凤英. 应用Laguerre小波算子矩阵求二重数值积分[J]. 计算机工程与应用, 2017, 53(16): 45-49. [8] RANJAN J S, DAMAYANTI N. A comparative study of numerical integration based on mixed quadrature rule and Haar wavelets[J]. Bulletin of Pure & Applied Sciences-Mathematics and Statistics, 2019, 38e(2): 532-539. [9] LSLAM S U, AZIZ I, KHAN W. Numerical integration of multi-dimensional highly oscillatory, gentle oscillatory and non-oscillatory integrands based on wavelets and radial basis functions[J]. Engineering Analysis with Boundary Elements, 2012, 36(8): 1284-1295. [10] ABDULHAMEED A F, MEMON Q A. An improved Trapezoidal rule for numerical integration[J]. Journal of Physics(Conference Series), 2021, 2090(1): 012104. [11] 吴小庆, 张合. 2010年数学建模竞赛A题的计算方法研究[J]. 周口师范学院学报, 2012, 29(2): 41-44. [12] 赵小伟, 徐刚, 刘冀. 用定积分方法求解倾斜偏转卧式储油罐容积[J]. 油气储运, 2012, 31(4): 310-313. [13] 闫明, 张义民, 李鹤, 等. 机械零件相关失效可靠度计算的二重积分模型[J]. 东北大学学报(自然科学版), 2011, 32(10): 1460-1463. [14] 黄春妙, 汪继秀. 二重积分在储油罐发生变位时的储油模型中的应用[J]. 科教导刊(上旬刊), 2014(5): 212-213. [15] 裴礼文. 数学分析中的典型问题与方法[M]. 3版. 北京: 高等教育出版社, 2015. [16] 徐萃薇, 孙绳武. 计算方法引论[M]. 4版. 北京: 高等教育出版社, 2002. [17] 谷超豪, 李大潜, 陈恕行, 等. 数学物理方程[M]. 3版. 北京: 高等教育出版社, 2012. [18] 陈纪修, 於崇华, 金路. 数学分析(下册)[M]. 3版. 北京: 高等教育出版社, 2019.
下载:




