Aitken推广算法在三维空间插值中的应用

Application of Aitken Generalization Algorithm in 3D Space Interpolation

摘要: 以代数曲面和空间代数曲线上的多元多项式插值问题的研究成果为基础，主要对二元以及多元Lagrange插值的适定节点组问题进行进一步的研究并在该基础上有一个四面体迭代法，它可以看作是Aitken算法在三维空间的一种推广，并给出了Aitken算法在三维空间推广的证明过程，最后通过两个实验算例对所得的研究成果进行了验证。

Abstract: Based on the research results of multivariate polynomial interpolation problems on algebraic sur-faces and space algebraic curves, further research is carried out on the well-posed node group problem of binary and multivariate Lagrange interpolation. On this basis, a tetrahedral iteration method is proposed. , it can be regarded as an extension of Aitken algorithm in three-dimensional space, and the proof process of Aitken algorithm in three-dimensional space is given. Finally, the obtained research results are verified by two experimental examples.

1. 引言

二元以及多元多项式的插值一直是计算数学中重要的研究领域，由于计算科学的不断进步和发展，极大地减少了人力物力，同时我们也希望计算机中关于函数插值这方面的程序能不断得到完善，多元函数插值也会在实际应用中发挥更大的作用。而二元以及多元多项式插值问题中的一个主要研究问题就是二元以及多元Lagrange插值的适定节点组问题。原吉林大学梁学章教授在1965年创造性的提出了关于二元多项式空间Lagrange插值适定性问题转换为几何问题的研究(详见文献 [1])。随后在1979年梁学章教授在文献 [2] 中给出了插值节点组的构造方法及其应用。1998年梁学章和吕春梅在文献 [3] 中以代数几何中的相关理论为基础，进一步的讨论了沿无重复分量平面代数曲线上的Lagrange插值问题，使得Lagrange插值获得长足进步。后来吕春梅教授结合了代数曲面和空间代数曲线上的Lagrange插值问题(详见文献 [4] - [10])提出了Aitken推广算法在三维空间插值中的应用。

2. 基本定义和主要定理

2.1. 基本定义

定义1 [3]：设n为非负整数并且 $d_n=\left(\begin{array}{c}n+3\\ 3\end{array}\right)$。而 $P_n^{\left(3\right)}=P_n\left[R^3\right]$ 代表所有全次数不超过n的三元实系数多项式空间，即

$P_n^{\left(3\right)}=\left\{{\displaystyle \underset{0\le i+j+k\le n}{\sum }{a}_{ijk}{x}^i{y}^j{z}^k}|a_{ijk}\in R\right\}$

定义2 [3]：设n，k均为自然数， $q\left(X\right)=0$ 为k次无重复分量代数曲面。定义 $d_n\left(k\right)$ 如下：

$d_n\left(k\right)=\left(\begin{array}{c}n+3\\ 3\end{array}\right)-\left(\begin{array}{c}n+3-k\\ 3\end{array}\right)=\{\begin{array}{l}\frac{1}{6}\left(n+3\right)\left(n+2\right)\left(n+1\right),n<k,\\ \frac{1}{6}k\left[3n\left(n-k\right)+12n+k^2-6k+11\right],n\ge k.\end{array}$ (1)

令 $A={\left\{Q_i\right\}}_{i=1}^{d_n\left(k\right)}$ 为曲面 $q\left(X\right)=0$ 上的 $d_n\left(k\right)$ 个相异点，对于一个任意给定的实数组 ${\left\{f_i\right\}}_{i=1}^{d_n\left(k\right)}$，寻找一个多项式 $g\left(X\right)\in P_n^{\left(3\right)}$ 使之满足如下插值条件

$g\left(Q_i\right)=f_i,i=1,\cdots ,d_n\left(k\right)$ (2)

如果对于每一个任意给定的实数组 ${\left\{f_i\right\}}_{i=1}^{d_n\left(k\right)}$，方程组(2)总存在一组解，则称节点组 $A={\left\{Q_i\right\}}_{i=1}^{d_n\left(k\right)}$ 为沿k次代数曲面 $q\left(X\right)=0$ 的n次插值适定节点组，并简记为 $A\in I_n^{\left(3\right)}\left(q\right)$ [这里 $I_n^{\left(3\right)}\left(q\right)$ 代表所有位于曲面 $q\left(X\right)=0$ 上的n次插值适定节点组的集合]。

2.2. 基本定理

定理1 [3]：设 $A={\left\{Q_i\right\}}_{i=1}^{d_n}$ 是 $P_n^{\left(3\right)}$ 的一个插值适定节点组，作一个k次无重复分量代数曲面 $q\left(X\right)=0$，使其不通过A中任何点。任取沿曲面 $q\left(X\right)=0$ 上的一个n + k次插值适定节点组 $B\in I_{n+k}^{\left(3\right)}\left(q\right)$，则 $A\cup B$ 必定构成空间 $P_{n+k}^{\left(3\right)}$ 的插值适定节点组。

定理2 [3]：假设k次无重复分量代数曲面 $q\left(X\right)=0$ 与平面 $h\left(X\right)=0$ 相交于一个平面代数曲线 $C=s\left(q,h\right)$ [这里 $s\left(q,h\right)$ 表示多项式 $q\left(X\right)$ 与 $h\left(X\right)$ 的公共零点集]。如果 $A={\left\{Q_i\right\}}_{i=1}^{d_n\left(k\right)}$ 为沿曲面 $q\left(X\right)=0$ 的一个n次插值适定节点组且A不位于曲线 $C=s\left(q,h\right)$ 上。在曲线 $C=s\left(q,h\right)$ 上任取一个沿该曲线的n + 1次插值适定节点组 $B\in I_{n+1}^{\left(3\right)}\left(q\right)$。

3. Aitken算法在三维空间中的推广

3.1. Aitken算法的推广

定理3：在三维空间 $R^{\text{3}}$ 上任作四个平面 $l_1,l_2,l_3,l_4$ 使其交成一四面体，在四面体的六个边上分别取异于顶点的n − 1个互不相同的点，再在每个平面上取异于三角形边上的 $\frac{1}{2}\left(n-1\right)\left(n-2\right)$ 个点，这些点构成相应平面上的二元n − 3次多项式空间 ${\pi }_{n-3}^3$ 的适定节点组 $C_{n-3}^2$，我们用 ${\mu }_i$ 表示平面 $l_i$ 上所取的这些点与四面体和这个平面所截三角形的三个顶点构成的集合， $i=1,2,3,4$。用 $C_{n-4}^3$ 表示四面体外 $R^{\text{3}}$ 上任一n − 4次多项式空间 ${\pi }_{n-4}^3$ 的适定节点组，它由 $\left(\begin{array}{c}n-1\\ 3\end{array}\right)=\frac{\left(n-1\right)\left(n-2\right)\left(n-3\right)}{\text{6}}$ 个点构成。则集合

$C_n^3=C_{n-4}^3\cup {\mu }_1\cup {\mu }_2\cup {\mu }_3\cup {\mu }_4$

构成空间 ${\pi }_n^3$ 的适定节点组，而且集合

${\beta }_i=C_n^3\backslash {\mu }_i,i=1,2,3,4$

都是空间 ${\pi }_{n-1}^3$ 的适定节点组。

进一步，设 $f\left(x,y,z\right)$ 为被插函数， $P_{n-1}^{\left(i\right)}\left(x,y,z\right)$ 分别是函数 $f\left(x,y,z\right)$ 在 ${\pi }_{n-1}^3$ 中关于节点组 ${\beta }_i$ 的插值多项式， $i=1,2,3,4$。设

$d=\left|\begin{array}{cccc}1& x_1& y_1& z_1\\ 1& x_2& y_2& z_2\\ 1& x_3& y_3& z_3\\ 1& x_4& y_4& z_4\end{array}\right|$ (3)

其中 $\left(x_i,y_i,z_i\right)$ 为平面 $l_i$ 所对应的四面体的顶点坐标， $i=1,2,3,4$。则我们可以证明

$P_n\left(x,y,z\right)=\frac{1}{d}\left|\begin{array}{cccc}{P}_{n-1}^{\left(1\right)}\left(x,y,z\right)& x_1-x& y_1-y& z_1-z\\ P_{n-1}^{\left(2\right)}\left(x,y,z\right)& x_2-x& y_2-y& z_2-z\\ P_{n-1}^{\left(3\right)}\left(x,y,z\right)& x_3-x& y_3-y& z_3-z\\ P_{n-1}^{\left(4\right)}\left(x,y,z\right)& x_4-x& y_4-y& z_4-z\end{array}\right|$ (4)

是 $f\left(x,y,z\right)$ 在 ${\pi }_n^3$ 中关于节点组 $C_n^3$ 的插值多项式。

证明：设四面体的六条边分别为 $m_{\text{1}},m_2,m_3,m_4,m_5,m_6$。

首先，我们在四面体外 $R^{\text{3}}$ 上任取多项式空间 ${\pi }_{n-4}^3$ 的插值适定节点组 $C_{n-4}^3$，然后在四面体的每个面上取沿平面的n − 3次插值适定节点组，之后再在每个边上取沿曲线的n − 2次插值适定节点组。

接下来，我们用空间的n − 4次插值适定节点组和四面体的一个平面 $l_{\text{1}}$ 的插值适定节点组并起来构成n − 3次插值适定节点组 $C_{n-\text{3}}^3$，然后把平面 $l_{\text{2}}$ 和边 $m_1$ 上的点与之前的插值适定节点组并起来构成沿平面的n − 2次插值适定节点组 $C_{n-\text{2}}^3$。接着，我们把平面 $l_{\text{3}}$ 、边 $m_{\text{2}}$ 上的点、边 $m_{\text{3}}$ 上的一个点与之前的插值适定节点组并起来构成沿平面的n − 1次插值适定节点组 $C_{n-\text{1}}^3$。最后，我们把平面 $l_{\text{4}}$ 上的点、边上 $m_{\text{4}}$ 的点、边 $m_{\text{5}}$ 上的一个点、边 $m_{\text{6}}$ 上的两个点与之前的插值适定节点组并起来构成n次插值适定节点组 $C_n^3$，这样我们就得到了结论 $C_n^3=C_{n-4}^3\cup {\mu }_1\cup {\mu }_2\cup {\mu }_3\cup {\mu }_4$。

(验证点数：因为 ${\mu }_{\text{1}}\cup {\mu }_{\text{2}}\cup {\mu }_{\text{3}}\cup {\mu }_{\text{4}}=\text{4}\times \frac{\text{1}}{\text{2}}\left(n-1\right)\left(n-2\right)+6\left(n-1\right)+4=\text{2}\left(n^2+1\right)$ 而 $C_n^3-C_{n-4}^3=\frac{\left(n+1\right)\left(n+2\right)\left(n+3\right)}{6}-\frac{\left(n-1\right)\left(n-2\right)\left(n-3\right)}{6}=\frac{\text{12}{n}^2+12}{6}=2\left(n^2+1\right)$，所以可以验证 $C_n^3=C_{n-4}^3\cup {\mu }_1\cup {\mu }_2\cup {\mu }_3\cup {\mu }_4$ )证毕。

3.2. 实验算例

算例1：设 $f\left(x,y,z\right)=\frac{1}{x^2+y^2+z^2+1}$ 为被插函数，取n = 1，则

$P_0^{\left(1\right)}\left(x,y,z\right),P_0^{\left(2\right)}\left(x,y,z\right),P_0^{\left(3\right)}\left(x,y,z\right),P_0^{\left(4\right)}\left(x,y,z\right)$

分别是函数 $f\left(x,y,z\right)=\frac{1}{x^2+y^2+z^2+1}$ 在 ${\pi }_{n-1}^3$ 关于节点组 ${\beta }_1,{\beta }_2,{\beta }_3,{\beta }_4$ 的插值多项式。我们取 $\left(0,0,0\right),\left(1,0,0\right),\left(0,1,0\right),\left(0,0,1\right)$ 为平面 $l_1,l_{\text{2}},l_{\text{3}},l_{\text{4}}$ 所对应的四面体的四个顶点坐标。因此，根据公式(3)我们可以算得d = 1。根据公式(4)我们要想得到 $P_1\left(x,y,z\right)$ 的值则必须先得到

$P_0^{\left(1\right)}\left(x,y,z\right),P_0^{\left(2\right)}\left(x,y,z\right),P_0^{\left(3\right)}\left(x,y,z\right),P_0^{\left(4\right)}\left(x,y,z\right)$

对应的值，这里我们取四面体的四个顶点为插值节点，从而得到 $P_0^{\left(1\right)}\left(0,0,0\right)=1,P_0^{\left(2\right)}\left(1,0,0\right)=\frac{1}{2},P_0^{\left(3\right)}\left(0,1,0\right)=\frac{1}{2},P_0^{\left(4\right)}\left(0,0,1\right)=\frac{1}{2}$，将其代入公式(4)可以得到 $P_1\left(x,y,z\right)=1-\frac{x}{2}-\frac{y}{2}-\frac{z}{2}$。由定义2可知 $P_1\left(x,y,z\right)=1-\frac{x}{2}-\frac{y}{2}-\frac{z}{2}$ 是 $f\left(x,y,z\right)=\frac{1}{x^2+y^2+z^2+1}$ 在 ${\pi }_n^3$ 中关于插值节点的插值多项式。

算例2：设 $f\left(x,y,z\right)=-2\left(x^2+y^2+z^2\right)+1$ 为被插函数，取n = 2，则同理我们由公式(4)可得要求 $P_2\left(x,y,z\right)$ 的值必须先求出

$P_1^{\left(1\right)}\left(x,y,z\right),P_1^{\left(2\right)}\left(x,y,z\right),P_1^{\left(3\right)}\left(x,y,z\right),P_1^{\left(4\right)}\left(x,y,z\right)$

的值，这里我们根据定理3可得

$P_1^{\left(1\right)}\left(x,y,z\right),P_1^{\left(2\right)}\left(x,y,z\right),P_1^{\left(3\right)}\left(x,y,z\right),P_1^{\left(4\right)}\left(x,y,z\right)$

的值正好是这个四面体的四个平面所对应的四个平面方程 $P_1^{\left(1\right)}\left(x,y,z\right)=x$， $P_1^{\left(2\right)}\left(x,y,z\right)=y$， $P_1^{\left(3\right)}\left(x,y,z\right)=z$， $P_1^{\left(4\right)}\left(x,y,z\right)=x+y+z-1$。由算例1的d = 1不变，因此我们根据公式(4)可算出 $P_2\left(x,y,z\right)=2xy+2xz+2yz-2x-2y-2z+1$，同理由定义2可知 $P_2\left(x,y,z\right)=2xy+2xz+2yz-2x-2y-2z+1$ 是 $f\left(x,y,z\right)=-2\left(x^2+y^2+z^2\right)+1$ 在 ${\pi }_n^3$ 中关于插值节点的插值多项式。

4. 结论

多元多项式插值问题中的一个主要研究问题就是多元Lagrange插值的适定节点组问题，这些年来代数几何理论和方法被学者们不断地更新和完善，这对于研究多元插值问题奠定了雄厚的理论基础，给出有力的理论依据和更丰富的计算方法在很多领域有重要的作用。因此，本文拟研究以代数曲面和空间代数曲线上的多元多项式插值问题的研究成果为基础，主要对二元以及多元Lagrange插值的适定节点组问题进行进一步的研究并在该基础上有一个四面体迭代法，它可以看作是Aitken算法在三维空间的一种推广。

参考文献

NOTES

^*通讯作者。