ABSTRACT

Subdivision method is a powerful tool for curve modeling. A popular method to construct a new subdivision scheme is to add central difference type offset vector to the initial subdivision scheme. This paper investigates maximal orders of sum rule of subdivisions constructed from high-order central difference type offset vectors.

Keywords:Subdivision Scheme, Sum Rule Order, Offset Vector, High-Order Central Difference

高阶中心差分偏移量方法构造细分求和规则阶数问题

毛智永，亓万锋，崔利宏

辽宁师范大学数学学院，辽宁 大连

收稿日期：2018年2月7日；录用日期：2018年2月21日；发布日期：2018年2月28日

摘 要

曲线细分是曲线造型的有力工具。采用添加差分形式的偏移量是构造细分格式的一种重要方法。本文讨论了采用高阶中心差分形式的偏移量所能够构造的细分格式求和规则的最高阶数问题。

关键词 :细分格式，求和规则，偏移量，高阶中心差分

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

曲线细分是一种从初始控制多边得到光滑曲线的迭代格式。通过迭代可以设计出合适的曲线，光滑度较高，因而得到了广泛应用。

近年来，采用通过添加偏移量的形式构造新的细分格式吸引了众多学者的注意 [1] [2] [3] [4] 。偏移量是组合系数和为零的同层的相邻几个顶点的线性组合。在已有细分迭代规则的基础上加上偏移量做调整，既可以从逼近型细分构造插值型细分 [1] [2] [3] ，又可以从插值型细分构造逼近型细分 [4] 。上述工作局限于单个细分格式，没有从理论上对这种方法进行探讨。Luo等 [5] 指出添加偏移量的操作对应的是在原细分生成函数基础上加上一个Laurent多项式。求和规则是细分的基本性质 [6] [7] [8] ，亓万锋等 [8] 分析了采用二阶中心差分形式的偏移量所能达到的最高阶求和规则的问题。本文将 [8] 的结论推广，考虑了高阶中心差分是否能够达到最高阶求和规则的问题。

2. 预备知识

细分格式是从给定的初始控制顶点集 $P^0={\left\{p_i^0\in {ℝ}^d\right\}}_{i\in \mathbb{Z}}$ 和一个正整数m，利用有限个数 $a={\left\{a_i\right\}}_{i\in \mathbb{Z}}\in l_0\left(\mathbb{Z}\right)$ ， $l_0\left(\mathbb{Z}\right)$ 代表 $\mathbb{Z}$ 上支撑有限的序列的集合，通过迭代格式

$p_i^k={\displaystyle {\sum }_{j\in \mathbb{Z}}{a}_{i-mj}{p}_j^{k-1}},i\in \mathbb{Z},k=1,2,\cdots$ (1)

迭代k次后得到控制顶点集合 $P^k={\left\{p_i^k\in {ℝ}^d\right\}}_{i\in \mathbb{Z}}$ 的一种造型方法，其中 $m$ 称为重数， $a={\left\{a_i\right\}}_{i\in \mathbb{Z}}$ 称为细分掩模，对应的Laurent多项式 $\tilde{a}\left(z\right)={\displaystyle {\sum }_{i\in \mathbb{Z}}{a}_i{z}^i}$ ， $z\in \left(ℂ\backslash \left\{0\right\}\right)$ 称为细分生成函数 [8] 。

给定m重细分掩模 $a={\left\{a_i\right\}}_{i\in \mathbb{Z}}\in l_0\left(\mathbb{Z}\right)$ ，记 $\text{supp}a=\left\{i\in \mathbb{Z},a_i\ne 0\right\}$ 。在实际应用中，往往使用对称的生成函数即细分掩模满足 $a_i=a_{-i},i\in \mathbb{Z}$ ，显然生成函数是对称的当且仅当 $\tilde{a}\left(z\right)=\tilde{a}\left(z^{-1}\right)$ 。长度为s的列向量 $v={\left(v_1,v_2,\cdots ,v_s\right)}^{\text{T}}$ 称为中心对称的，如果满足 $v_i=v_{s+1-i},i=1,\cdots ,s$ 。显然对称的生成函数的系数组成的列向量是中心对称向量。

细分格式可以分为插值型和逼近型两种格式，插值型细分每次迭代时保留上一次的控制顶点，其细分掩模满足 $a_{mi}={\delta }_i$ 。若细分格式不是插值型的，则称为逼近型细分。

称m重细分格式 $\tilde{a}\left(z\right)$ 满足k阶求和规则，如果 $\tilde{a}\left(1\right)=m$ 且 $\tilde{a}\left(z\right)$ 含有因式 ${\left(1+z+\cdots +z^{m-1}\right)}^k$ 。易见当 $\tilde{a}\left(z\right)$ 满足一阶求和规则时，有 ${\displaystyle {\sum }_i{a}_{mi}}={\displaystyle {\sum }_i{a}_{mi+l}}=1,0\le l<m$ 成立。

3. 主要结果

在这一节里，我们讨论添加偏移量是2n阶中心差分时，所构造的细分格式能否达到最高阶求和规则的问题。

给定第 $k-1$ 层上的控制顶点集合 $P^{k-1}={\left\{p_j^{k-1}\in {ℝ}^d\right\}}_{j\in \mathbb{Z}}$ ，在顶点 $p_j^{k-1}$ 处的2n阶中心差分是

${\delta }^{2n}{p}_j^{k-1}={\displaystyle {\sum }_{i=0}^{2n}{\left(-1\right)}^i\left(\begin{array}{c}2n\\ i\end{array}\right)p_{j+n-i}^{k-1}}$

例如在 $p_j^{k-1}$ 处的二阶中心差分是 ${\delta }^2{p}_j^{k-1}=p_{j-1}^{k-1}-2p_j^{k-1}+p_{j+1}^{k-1}$ ，四阶中心差分是 ${\delta }^4{p}_j^{k-1}=p_{j-2}^{k-1}-4p_{j-1}^{k-1}+6p_j^{k-1}-4p_{j+1}^{k-1}+p_{j+2}^{k-1}$ 。

添加偏移量的方法是在原细分格式的基础上添加偏移量。在给定原细分格式

$p_{mi+l}^k=\underset{j\in \mathbb{Z}}{{\displaystyle \sum }}{a}_{mi+l-mj}{p}_j^{k-1},i\in \mathbb{Z},l=0,1,\cdots ,m-1$

的顶点 $p_{mi+l}^k$ 处添加2n阶中心差分 ${\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{\delta }^{2n}{p}_j^{k-1}}$ ，即

$p_{mi+l}^k={\displaystyle {\sum }_{j\in \mathbb{Z}}{a}_{mi+l-mj}{p}_j^{k-1}}+{\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{\delta }^{2n}{p}_j^{k-1}}$

相应的生成函数变为原生成函数加上对应偏移量的Laurent多项式

$\tilde{d}\left(z\right)={\displaystyle {\sum }_{l=0}^{m-1}{\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{z}^{mi+l-mj-mn}{\left(1-z^m\right)}^{2n}}}$ 。 (2)

下面我们分析 $\tilde{d}\left(z\right)$ 在满足限定条件时，所含自由系数的个数。

引理3.1若对称的Laurent多项式 $\tilde{d}\left(z\right)={\displaystyle {\sum }_{l=0}^{m-1}{\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{z}^{mi+l-mj-mn}{\left(1-z^m\right)}^{2n}}}$ 的最高幂次是r，则 $\tilde{d}\left(z\right)$ 中自由系数个数是 $r-nm+1$ 。

证：

$\begin{array}{c}\tilde{d}\left(z\right)=\underset{l=0}{\overset{m-1}{{\displaystyle \sum }}}\underset{j\in \mathbb{Z}}{{\displaystyle \sum }}{c}_{mi+l-mj}{z}^{mi+l-mj-mn}{\left(1-z^m\right)}^{2n}\\ =\underset{l=0}{\overset{m-1}{{\displaystyle \sum }}}\underset{j\in \mathbb{Z}}{{\displaystyle \sum }}{c}_{mi+l-mj}{z}^{mi+l-mj-mn}{\left(1-z\right)}^{2n}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}\\ =z^{-mn}{\left(1-z\right)}^{2n}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}\underset{l=0}{\overset{m-1}{{\displaystyle \sum }}}\underset{j\in \mathbb{Z}}{{\displaystyle \sum }}{c}_{mi+l-mj}{z}^{mi+l-mj}\end{array}$ 。

因为 $\tilde{d}\left(z\right)$ 和 $z^{-mn}{\left(1-z\right)}^{2n}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}$ 是对称的Laurent多项式，所以 ${\displaystyle {\sum }_{l=0}^{m-1}{\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{z}^{mi+l-mj}}}$ 也

是对称的Laurent多项式。注意到 $\tilde{d}\left(z\right)$ 的最高次数是 $mi+l-mj$ 的最大值与 $nm$ 的和。因此当限制 $\tilde{d}\left(z\right)$ 的最高次数是r时，此时 $c_{mi+l-mj}$ 中下标 ${}_{mi+l-mj}$ 的最大值是 $r-nm$ 。因此， $\tilde{d}\left(z\right)$ 具有的自由系数个数是 $r-nm+1$ 。证毕。

由引理3.1可知，当给定m重的细分生成函数 $\tilde{a}\left(z\right)$ 后，如果限定 $\tilde{d}\left(z\right)$ 的最高幂次是r，则组成 $\tilde{d}\left(z\right)$ 的中心差分的阶数应小于等于2r/m。

下面的定理给出了当采用中心差分形式的偏移量能够达到最高阶求和规则的 $\tilde{a}\left(z\right)$ 的形式。

定理3.2若限定m重对称的细分掩模 $\tilde{a}\left(z\right)$ 和2n阶中心差分形式的偏移量 $\tilde{d}\left(z\right)$ 的最高幂次是r，且 $\tilde{a}\left(z\right)+\tilde{d}\left(z\right)$ 能具有支撑在 $\left[-r,r\right]$ 上生成函数的最高阶求和规则，则 $\tilde{a}\left(z\right)$ 至少具有2n阶求和规则。设 $\tilde{b}\left(z\right)$ 是支撑在 $\left[-r,r\right]$ 的对称生成函数中求和规则最高，则 $\tilde{a}\left(z\right)$ 具有形式

$\tilde{a}\left(z\right)=\tilde{b}\left(z\right)-z^{-mn}{\left(1-z\right)}^{2n}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}{\displaystyle {\sum }_{l=0}^{m-1}{\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{z}^{mi+l-mj}}}$ ，系数 $\left\{c_{mi+l-mj},j\in \mathbb{Z}\right\}$ 自由的个数为 $r-nm+1$ 。

证：根据文献 [8] 中的定理2.1，在 $\left[-r,r\right]$ 上存在具有最高阶求和规则的对称的生成函数，记为 $\tilde{b}\left(z\right)$ ，则当限定采用的偏移量是2n阶中心差分时， $\tilde{a}\left(z\right)=\tilde{b}\left(z\right)-\tilde{d}\left(z\right).\text{supp}\tilde{d}\subset \left[-r,r\right]$ ，因此 $\tilde{b}\left(z\right)$ 的求和规则至少是2n阶，同时 $\tilde{d}\left(z\right)$ 含有因子 ${\left(1+z+\cdots +z^{m-1}\right)}^{2n}$ ，因而 $\tilde{a}\left(z\right)$ 至少具有2n阶求和规则。

代入 $\tilde{d}\left(z\right)$ 的形式有 $\tilde{a}\left(z\right)=\tilde{b}\left(z\right)-z^{-mn}{\left(1-z\right)}^{2n}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}{\displaystyle {\sum }_{l=0}^{m-1}{\displaystyle {\sum }_{j\in \mathbb{Z}}{c}_{mi+l-mj}{z}^{mi+l-mj}}}$ ，在对称的 $\tilde{b}\left(z\right)$ 固定的情形下，由引理3.1知自由系数个数 $\left\{c_{mi+l-mj},j\in \mathbb{Z}\right\}$ 为 $r-nm+1$ 。

推论3.3在定理3.2的条件下，当 $n=1$ 时， $\tilde{a}\left(z\right)$ 自由系数个数与 $\tilde{d}\left(z\right)$ 自由系数个数一致；当 $n>1$ 时， $\tilde{a}\left(z\right)$ 自由系数个数大于 $\tilde{d}\left(z\right)$ 自由系数个数。

证：首先 $\tilde{a}\left(z\right)$ 自由系数个数是 $r-nm+n$ 。这是因为 $\tilde{a}\left(z\right)$ 可分解为 $\tilde{a}\left(z\right)=m{z}^{-n\left(m-1\right)}{m}^{-2n}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}{\tilde{a}}_1\left(z\right)$ 。由 $\tilde{a}\left(z\right)$ 和 $m{z}^{-n\left(m-1\right)}{\left(1+z+\cdots +z^{m-1}\right)}^{2n}$ 的对称性知 ${\tilde{a}}_1\left(z\right)$ 也是对称的。易得 ${\tilde{a}}_1\left(z\right)$ 的最高次数是 $r-n\left(m-1\right)=r-nm+n$ ，而 ${\tilde{a}}_1\left(z\right)$ 的系数和是1，因此 $\tilde{a}\left(z\right)$ 自由系数个数是 $r-nm+n.$

当 $n=1$ 即采用二阶中心差分时，对任何对称的细分掩模 $\tilde{a}\left(z\right)$ 具有的自由系数个数与 $\tilde{d}\left(z\right)$ 自由系数一致。当 $n>1$ 时， $\tilde{a}\left(z\right)$ 自由系数个数是 $r-nm+n>r-nm+1$ ，即大于 $\tilde{d}\left(z\right)$ 的自由系数个数。证毕。

推论3.2从另一个方面表明若 $\tilde{a}\left(z\right)$ 不具有定理3.2中的形式时，则不能通过添加2n阶中心差分的形式得到最高阶求和规则。例对具有四阶求和规则的二重细分生成函数

$\tilde{a}\left(z\right)=\frac{{\left(1+z\right)}^4\left(132-464z+880z^2-1091z^3+880z^4-464z^5+132z^6\right)}{40z^5}$ ，最高幂次 $r=5$ ，计算知支撑在[−5, 5]上具有最高阶求和规则的逼近型细分和插值型细分的生成函数分别是 $\frac{{\left(1+z\right)}^{10}}{512z^5}$ 和 $\frac{{\left(1+z\right)}^6\left(3-18z+38z^2-18z^3+3z^4\right)}{256z^5}$ 。若采用四阶中心差分形式的偏移量 $\tilde{d}\left(z\right)=\frac{{\left(1-z\right)}^4{\left(1+z\right)}^4\left(d_1+z{d}_0+z^2{d}_1\right)}{z^5}$ ，则无论 $d_0,d_1$ 取何值， $\tilde{a}\left(z\right)+\tilde{d}\left(z\right)$ 都无法得到 $\frac{{\left(1+z\right)}^{10}}{512z^5}$ 或 $\frac{{\left(1+z\right)}^6\left(3-18z+38z^2-18z^3+3z^4\right)}{256z^5}$ 。原因在于 $\frac{{\left(1+z\right)}^{10}}{512z^5}-\tilde{a}\left(z\right)$ 和 $\frac{{\left(1+z\right)}^6\left(3-18z+38z^2-18z^3+3z^4\right)}{256z^5}-\tilde{a}\left(z\right)$ 中因式 $1-z$ 的幂次都是2，不是4。

当采用的是2阶中心差分即 $n=1$ 时，我们可以得到相应的线性方程组的形式：

定理3.4对任意正奇数s和中心对称列向量 $b$ ，且向量 $b$ 所有元素的和为0，系数矩阵 $A$ 满足

$A={\left(\begin{array}{ccccc}1& & & & \\ -2& 1& & & \\ 1& -2& 1& & \\ & \ddots & \ddots & \ddots & \\ & & 1& -2& 1\\ & & & 1& -2\\ & & & & 1\end{array}\right)}_{\left(s+2\right)\times s}$ ，

则线性方程组 $Ax=b$ 有中心对称解。

证：对任意正奇数s，利用中心对称的向量 $b$ ，构造一个Laurent多项式

$\tilde{b}\left(z\right)=b_{-\left(s+1\right)}{z}^{-\left(s+1\right)}+\cdots +b_{s+1}{z}^{s+1}$ 。

显然 $\tilde{b}\left(z\right)$ 的系数和为0，即 $\tilde{b}\left(1\right)=0$ 。的系数是对称的，由文献 [8] 知 ${\tilde{b}}^{\prime }\left(1\right)=0$ 。因此 $\tilde{b}\left(z\right)$ 含有因子 $z^{-1}{\left(1-z\right)}^2$ ， $\tilde{b}\left(z\right)$ 可以分解为 $\tilde{b}\left(z\right)=z^{-1}{\left(1-z\right)}^2\left(x_{-s}{z}^{-s}+\cdots +x_s{z}^s\right)$ 。由 $\tilde{b}\left(z\right)$ 的系数对应关系可知， $x={\left(x_{-s},\cdots ,x_s\right)}^{\text{T}}$ 就是该线性方程组的解。由 $\tilde{b}\left(z\right)$ 和 $z^{-1}{\left(1-z\right)}^2$ 的对称性知 $x$ 是中心对称的。

资助信息

国家自然科学基金(No. 61502217)，辽宁省教育厅科研项目(L20168366)。

文章引用

毛智永,亓万锋,崔利宏. 高阶中心差分偏移量方法构造细分求和规则阶数问题
Maximal Sum Rule Orders of Subdivision Schemes Based on High-Order Central Difference Type Offset Vectors[J]. 应用数学进展, 2018, 07(02): 231-235. http://dx.doi.org/10.12677/AAM.2018.72028

参考文献 (References)