有理插值存在性研究和CAGD中的规范B基
|
摘要
有理函数插值理论及其应用是有理逼近研究的重要组成部分，其在唯一性、算法及误差估计等方面均取得了很多研究成果，尤其在算法的研究上更是如此。然而对于任意事先给定的插值条件，有理插值函数并不总是存在的。而其他结果诸如唯一性、算法、误差估计等，在叙述其结论时也总是假定所讨论的有理插值函数是存在的。如果存在性问题得不到很好的解决，则势必影响这些结果在使用上的确定性。规范B基即最优规范的全正基，因其具有凸包性、仿射不变性、最优保形性、端点插值性及B算法等重要性质，在CAGD中起着重要的作用。CAGD中广泛使用的表示曲线曲面的基函数，如Bernstein基、B样条基、NURBS基等均为规范B基。
本文对有理插值的存在性进行了研究，并给出了一类有理空间中的规范B基，在第一章回顾了有理插值的存在性和CAGD中的规范B基的研究背景及研究现状。
第二章分析了有理插值出现不可达点的原因，在引入判定不可达点的定理的基础上，给出了两种解决不可达点方法，并将其推广到二元情形。
第三章给出了一元和二元的两种Thiele-Werner型有理插值的分块算法。并给出了具有“洞形”结构的矩形域上的应用算法。
第四章是CAGD中规范B基的综述，介绍了一些规范B基理论，性质，构造和相应的B算法等。
第五章在一类有理函数空间中构造了一组规范B基，讨论了其性质和在曲线曲面造型中的应用。
Rational function interpolation theory and its application are an important part in research on rational approximation. There have been a lot of achievements in uniqueness, algorithms, error estimate and etc., especially in algorithms. But there doesn't always exist rational interpolation function for arbitrary interpolation conditions given in advance. Moreover, other results such as uniqueness, algorithms and error estimate are given which bases on that rational interpolation function exists. If the existence can't be settled well, the determinacy of these results will be influenced. Normalized B-basis, namely optimal normalized totally positive basis, plays an important role in CAGD, for it possess positive properties such as variation diminishing, convex-hull, acne invariance, tangency to the control polygon at the endpoints and B-algorithm. The widely used basis functions in CAGD, such as Bernstein, B-spline and NURBS basis, are all normalized B-basis.
In this thesis, we discuss the existence of the rational interpolation and normalized B-basis in CAGD. This thesis consists of five chapters. In chapter 1, we not only retrospect the background of the research on rational interpolants and normalized B-basis, but also retrospect the study actuality of the existence of rational interpolants and normalized B-basis .
In chapter 2, through analyzing the unattainable point of Thiele fractions interpolation , the method for testing the unattainable points is given. Then we give two metheds of changing the unattainable points into attainable points.
The chapter 3, we give two kinds of algorithms of dividing interpolation nodes into subsets for Thiele-Werner interpolation. An efficient algorithm for computing bivariate lacunary rational interpolation is constructed.
The chapter 4, we mainly discuss the properties, existence, construction and B-algorithm of normalized B-basis.
The chapter 5, we give the normalized B-basis in a kind of rational space, and discuss the properties and applications in CAGD.
本文对有理插值的存在性进行了研究，并给出了一类有理空间中的规范B基，在第一章回顾了有理插值的存在性和CAGD中的规范B基的研究背景及研究现状。
第二章分析了有理插值出现不可达点的原因，在引入判定不可达点的定理的基础上，给出了两种解决不可达点方法，并将其推广到二元情形。
第三章给出了一元和二元的两种Thiele-Werner型有理插值的分块算法。并给出了具有“洞形”结构的矩形域上的应用算法。
第四章是CAGD中规范B基的综述，介绍了一些规范B基理论，性质，构造和相应的B算法等。
第五章在一类有理函数空间中构造了一组规范B基，讨论了其性质和在曲线曲面造型中的应用。
Rational function interpolation theory and its application are an important part in research on rational approximation. There have been a lot of achievements in uniqueness, algorithms, error estimate and etc., especially in algorithms. But there doesn't always exist rational interpolation function for arbitrary interpolation conditions given in advance. Moreover, other results such as uniqueness, algorithms and error estimate are given which bases on that rational interpolation function exists. If the existence can't be settled well, the determinacy of these results will be influenced. Normalized B-basis, namely optimal normalized totally positive basis, plays an important role in CAGD, for it possess positive properties such as variation diminishing, convex-hull, acne invariance, tangency to the control polygon at the endpoints and B-algorithm. The widely used basis functions in CAGD, such as Bernstein, B-spline and NURBS basis, are all normalized B-basis.
In this thesis, we discuss the existence of the rational interpolation and normalized B-basis in CAGD. This thesis consists of five chapters. In chapter 1, we not only retrospect the background of the research on rational interpolants and normalized B-basis, but also retrospect the study actuality of the existence of rational interpolants and normalized B-basis .
In chapter 2, through analyzing the unattainable point of Thiele fractions interpolation , the method for testing the unattainable points is given. Then we give two metheds of changing the unattainable points into attainable points.
The chapter 3, we give two kinds of algorithms of dividing interpolation nodes into subsets for Thiele-Werner interpolation. An efficient algorithm for computing bivariate lacunary rational interpolation is constructed.
The chapter 4, we mainly discuss the properties, existence, construction and B-algorithm of normalized B-basis.
The chapter 5, we give the normalized B-basis in a kind of rational space, and discuss the properties and applications in CAGD.
引文
[1] Graves-Morris P R. Efficient reliable rational interpolation[C].van Rossum H,de Bruin M. Pade Appro-ximation and its applications.Berlin: Springer,1984:29-63.
[2] Graves-Mores P.R., Vector valued rational interpolants I [J]. Numer. Math.,1983 ,(42)331-348.
[3] Graves-Mores P.R., Vector valued rational interpolants II [J]. IMA.J.Nu-Mer.Anal1984, (4),209-224.
[4] Graves-Mores P.R. and Jenkins C. D., Vector valued rationalinterpolants III[J].Constr. Approx., 1986, (2),263-289.
[5] Piegl L. and Tiller W., The NURBS Book[M]. Berlin:Springer-Verlag, 1997.
[6] Wuytack L., On some aspects of the rational interpolation problem[J], SIAMJ.numer. Anal., 1974, (11), 52-60.
[7] Wuytack L., On the osculatory rational interpolation problem [J].Math. Comput.1975, (29),837-843.
[8] Wynn P., Vector continued fraction[J]. Linear Algebra and its Applications,1968,16.
[9] Jones W.B. and Thron W.J., Continued fractions analytic theory and application[M]. Addision Wesley London,1980.
[10]A. Cuyt and B. Verdonk, Multivariate rational interpolation[J]Comput-ing.1985,(34), 41-61.
[11]A. Cuyt, and B. Verdonk, Multivariate reciprocal divided differences for bran-ched Thiele continued fraction expansions[J]. Comput. Appl. Math. 1988, (21),145-160.
[12]W. Siemaszko, Branched Continued Fractions for Double Power Series [J]. Comput. Appl.Math., 1980 ,(6), 121 — 125.
[13]W. Siemaszko, On Some Conditions for Convergence of Branched Continued fractions,LNM, 1981, (888), 363-370.
[14]W. Siemaszko, Thiele-type branched continued fractions for two variable functions[J]. Comput. Appl. Math. 1983 ,(9), 137 — 153.
[15] P. Wynn,Vector Continued Fractions, Linear Algebra and its applications[J].1968 (1): 357-395.
[16]TAN Jie-qing, Fang Yi, Newton-Thiele's rational interpolants[J]. Numerical Algorithms, 2000,(24),141 - 157.
[17]Jieqing Tan and Gongqin Zhu, , Bivariate vector valued rational interpolants by branched ontinued fractions[J]. Numer. Math. A J. of Chinese Univ., 1995, (1) : 37-43.。
[18]Jieqing Tan and Shuo Tang , Vector valued rational interpolants by triple branched continued fractions[J]. Appl. Math. TCU, 1997,212B, 273-278。
[19]Jieqing Tan, Bivariate blending rational interpolants[J]. Approx.Theory and its Appl., 1999, (2) :74-83。
[20]Jieqing Tan and Shuo Tang, Bivariate composite vector valued rational interpolation[J]. Mathematics of Computation,2000, (69), 1521-1532。
[21]J. Tan and G. Zhu, General framework for vector-valued interpolants,in: Proc.of the 3~(rd) China-Japan Seminar on Numerical Mathematics, Z. Shied., SciencePress, Beijing/New York, 1998, 273-278.
[22]Jieqing Tan, Algorithms for lacunary vector valued rational interpolants[J]. Numer. Math. A J. Chin. Univ. 1998,7(2), 681-687.
[23]Jieqing Tan, Computation of vector valued blending rational interpolation[J] Numer. Math A J. Chinese Univ., 2003,12(I), 91-98.
[24]Jieqing Tan, A compact determinantal representation for inverse differences[J]数学研究与评论，2000，20(1)，32-36．
[25]Jieqing Tan, The limiting case of Thiele's interpolating continued fraction expansion[J]Comput. Math., 200119(4),433-444.
[26]王仁宏，朱功勤．有理函数逼近及其应用[M]北京：科学出版社，2004：55-65．
[27]檀结庆，朱功勤，二元向量分叉连分式插值的矩阵算法[J]．高等学校计数学学报，1996，(3)，250-254．
[28]王仁宏，数值有理逼近[M]．上海：上海科学技术出版社，1980年。
[29]朱功勤、顾传青，檀结庆，《多元有理逼近方法》，北京：中国科学技术出版社，1996年7月．
[30]朱功勤，顾传青，二元Thiele型向量有理插值[J]．计算数学，1990，(3)，293-301。
[31]朱功勤，王洪燕，离散点集上的向量有理插值算法与特征性质[J]．高等学校计算数学学报，1998，(4)：316-320。
[32]朱功勤，檀结庆，王洪燕，预给极点的向量有理插值及性质[J]．高等学校计算数学学报，2000，(2)：97-104。
[33]Zhu Xiaolin Zhu Gongqin, The note on matrix-valued rational interpolaton[J]. Numer. Math. A J. Chin. Univ, 2005,14(4) ,305-314.
[34]Xiaolin Zhu , Gongqin Zhu, A method for directly finding the denominator values of rational interpolants[J]. J. of Comput. And Appl. Math., 2002,(148)341-348.
[35]Zhu X.L.,Zhu G.Q., A Study of the Existence of Vector Valued Rational Interpolation [J]. J.Infor.Comput.Science 2005,(2),631-640.
[36]Zhu Xiaolin, Zhu Gongqin. A note on vecter-valued rational Interpolation [J]J. of Comput. And Appl. Math., 2006,(195),341 - 350。
[37]朱晓临，关于有理插值函数存在性的研究[J]．工科数学，2002，18(2)：54-58．
[38]朱晓临，(向量)有理插值的研究及其应用[D]．博士学位论文，中国科学技术大学，2002．
[39]朱晓临，一种求二元有理插值函数的方法[J]．大学数学，2003，19(1)，90-95．
[40]朱晓临，朱功勤，向量值有理插值函数的递推算法[J]．中国科学技术大学学报，2003，33(1)，15-25．
[41]朱晓临，切触有理插值函数存在性的判别方法[J]．合肥工业大学学报(自然科学版)，2005，28(9)，1217-1222．
[42]檀结庆，胡敏，刘晓平，有理曲面的三维重建计算机应用[J]．Vol．20．Suppl．57-59．
[43]赵前进，混合有理插值方法及其在图形图像中的应用[D]．博士学位论文，合肥工业大学，2006．
[44]胡敏，连分式方法在数字图像处理中的若干应用研究[D]．博士学位论文，合肥工业大学，2006．
[45]Pottmann H. The geometry of Tchebycheffian spline[J]. Computer Aided Geometric Design, 1993,10(2):181-210
[46]Ardeshir Goshtasby. Geometric modeling using rational Gaussian curves andsurfaces[J]. Computer Aided Design, 1995, 27(5): 363-375
[47]Geraldine Morin, Ron Goldman. A subdivision scheme for Poisson curves and surfaces[J]. Computer Aided Geometric Design,2000,17(l l):813-833
[48]Carnicer JM, Pena J M. Totally positive bases for shape preserving curve design and optimality of B-splines[J]. Computer Aided Geometric Design, 1994, 11(6): 633-654.
[49]Jiwen Zhang. C-curve: An extension of cubic curves[J]. Computer Aided Geometric Design, 1996, 13(3): 199-217
[50]Gasca Pena. On factorizations of totally positive matrices total positivityand its applications[M]. Dordrecht: KluwerAcademic,1996
[51]Farin G. Curves and Surfaces for Computer Aided GeometricDesign[M]. San Diego, CA: Academic Press, 1997
[52]Pena J M. Shape preserving representations for trigonometric polynomial curves [J].Comput. Aided Geom. Design, 1997,14(1):5 - 11
[53]Jiwen Zhang. Two different forms of C-B-splines[J]. Computer Aided Geometric Design, 1997, 14(1):31-41
[54]Zhang J W. C-Bezier curves and surfaces[J]. Graphical Models and Image Processing, 1999,16(1):2-15
[55]Sanchez-Reyes J. Harmonic rational Bezier curves, p-Bezier curves and Trigonometric polynomials[J]. Computer Aided Geometric Design,1998, 15(9):909-923
[56]Mainar E, Pena J M. Corner cutting algorithms associated with optimal shape preserving representations [J]. Computer Aided GeometricDesign, 1999, 16(9):883-906.
[57]Mainar E, Pena J M, Sanchez-Reyes J. Shape preserving alternatives to the rational B6zier model[J]. Computer Aided Geometric Design, 2001, 18(1):37-60
[58]Mainar E, Pena J M. A basis of C-Bezier splines with optimalProperties [J]. Computer Aided Geometric Design, 2002,19(4): 291-295
[59]Xuli Han. Quadratic trigonometric polynomial curves with a shape parameter[J].Computer Aided Geometric Design, 2002,19(5): 503-512
[60]Qinyu Chen, Guozhao Wang. A class of Bezier like curves[J]. Computer Aided Geometric Design, 2003,20(1): 29-39
[61]陈秦玉，汪国昭．圆弧的C-Bezier曲线表示[J]．软件学报，2002，13(11)：2155-2161．
[62]樊建华，张纪文，邬义杰，C-Bezier曲线的形状修改，[J]．软件学报，2002，13(11)：2194-2199
[63]张帆，康宝生．(n+1)维空间C”[a，b]上规范基存在的充要条件[J]．计算机辅助设计与图形学学报，2003，13(5)：67-70
[64]檀结庆．连分式理论及其应用[M]北京：科学出版社，2007
[2] Graves-Mores P.R., Vector valued rational interpolants I [J]. Numer. Math.,1983 ,(42)331-348.
[3] Graves-Mores P.R., Vector valued rational interpolants II [J]. IMA.J.Nu-Mer.Anal1984, (4),209-224.
[4] Graves-Mores P.R. and Jenkins C. D., Vector valued rationalinterpolants III[J].Constr. Approx., 1986, (2),263-289.
[5] Piegl L. and Tiller W., The NURBS Book[M]. Berlin:Springer-Verlag, 1997.
[6] Wuytack L., On some aspects of the rational interpolation problem[J], SIAMJ.numer. Anal., 1974, (11), 52-60.
[7] Wuytack L., On the osculatory rational interpolation problem [J].Math. Comput.1975, (29),837-843.
[8] Wynn P., Vector continued fraction[J]. Linear Algebra and its Applications,1968,16.
[9] Jones W.B. and Thron W.J., Continued fractions analytic theory and application[M]. Addision Wesley London,1980.
[10]A. Cuyt and B. Verdonk, Multivariate rational interpolation[J]Comput-ing.1985,(34), 41-61.
[11]A. Cuyt, and B. Verdonk, Multivariate reciprocal divided differences for bran-ched Thiele continued fraction expansions[J]. Comput. Appl. Math. 1988, (21),145-160.
[12]W. Siemaszko, Branched Continued Fractions for Double Power Series [J]. Comput. Appl.Math., 1980 ,(6), 121 — 125.
[13]W. Siemaszko, On Some Conditions for Convergence of Branched Continued fractions,LNM, 1981, (888), 363-370.
[14]W. Siemaszko, Thiele-type branched continued fractions for two variable functions[J]. Comput. Appl. Math. 1983 ,(9), 137 — 153.
[15] P. Wynn,Vector Continued Fractions, Linear Algebra and its applications[J].1968 (1): 357-395.
[16]TAN Jie-qing, Fang Yi, Newton-Thiele's rational interpolants[J]. Numerical Algorithms, 2000,(24),141 - 157.
[17]Jieqing Tan and Gongqin Zhu, , Bivariate vector valued rational interpolants by branched ontinued fractions[J]. Numer. Math. A J. of Chinese Univ., 1995, (1) : 37-43.。
[18]Jieqing Tan and Shuo Tang , Vector valued rational interpolants by triple branched continued fractions[J]. Appl. Math. TCU, 1997,212B, 273-278。
[19]Jieqing Tan, Bivariate blending rational interpolants[J]. Approx.Theory and its Appl., 1999, (2) :74-83。
[20]Jieqing Tan and Shuo Tang, Bivariate composite vector valued rational interpolation[J]. Mathematics of Computation,2000, (69), 1521-1532。
[21]J. Tan and G. Zhu, General framework for vector-valued interpolants,in: Proc.of the 3~(rd) China-Japan Seminar on Numerical Mathematics, Z. Shied., SciencePress, Beijing/New York, 1998, 273-278.
[22]Jieqing Tan, Algorithms for lacunary vector valued rational interpolants[J]. Numer. Math. A J. Chin. Univ. 1998,7(2), 681-687.
[23]Jieqing Tan, Computation of vector valued blending rational interpolation[J] Numer. Math A J. Chinese Univ., 2003,12(I), 91-98.
[24]Jieqing Tan, A compact determinantal representation for inverse differences[J]数学研究与评论，2000，20(1)，32-36．
[25]Jieqing Tan, The limiting case of Thiele's interpolating continued fraction expansion[J]Comput. Math., 200119(4),433-444.
[26]王仁宏，朱功勤．有理函数逼近及其应用[M]北京：科学出版社，2004：55-65．
[27]檀结庆，朱功勤，二元向量分叉连分式插值的矩阵算法[J]．高等学校计数学学报，1996，(3)，250-254．
[28]王仁宏，数值有理逼近[M]．上海：上海科学技术出版社，1980年。
[29]朱功勤、顾传青，檀结庆，《多元有理逼近方法》，北京：中国科学技术出版社，1996年7月．
[30]朱功勤，顾传青，二元Thiele型向量有理插值[J]．计算数学，1990，(3)，293-301。
[31]朱功勤，王洪燕，离散点集上的向量有理插值算法与特征性质[J]．高等学校计算数学学报，1998，(4)：316-320。
[32]朱功勤，檀结庆，王洪燕，预给极点的向量有理插值及性质[J]．高等学校计算数学学报，2000，(2)：97-104。
[33]Zhu Xiaolin Zhu Gongqin, The note on matrix-valued rational interpolaton[J]. Numer. Math. A J. Chin. Univ, 2005,14(4) ,305-314.
[34]Xiaolin Zhu , Gongqin Zhu, A method for directly finding the denominator values of rational interpolants[J]. J. of Comput. And Appl. Math., 2002,(148)341-348.
[35]Zhu X.L.,Zhu G.Q., A Study of the Existence of Vector Valued Rational Interpolation [J]. J.Infor.Comput.Science 2005,(2),631-640.
[36]Zhu Xiaolin, Zhu Gongqin. A note on vecter-valued rational Interpolation [J]J. of Comput. And Appl. Math., 2006,(195),341 - 350。
[37]朱晓临，关于有理插值函数存在性的研究[J]．工科数学，2002，18(2)：54-58．
[38]朱晓临，(向量)有理插值的研究及其应用[D]．博士学位论文，中国科学技术大学，2002．
[39]朱晓临，一种求二元有理插值函数的方法[J]．大学数学，2003，19(1)，90-95．
[40]朱晓临，朱功勤，向量值有理插值函数的递推算法[J]．中国科学技术大学学报，2003，33(1)，15-25．
[41]朱晓临，切触有理插值函数存在性的判别方法[J]．合肥工业大学学报(自然科学版)，2005，28(9)，1217-1222．
[42]檀结庆，胡敏，刘晓平，有理曲面的三维重建计算机应用[J]．Vol．20．Suppl．57-59．
[43]赵前进，混合有理插值方法及其在图形图像中的应用[D]．博士学位论文，合肥工业大学，2006．
[44]胡敏，连分式方法在数字图像处理中的若干应用研究[D]．博士学位论文，合肥工业大学，2006．
[45]Pottmann H. The geometry of Tchebycheffian spline[J]. Computer Aided Geometric Design, 1993,10(2):181-210
[46]Ardeshir Goshtasby. Geometric modeling using rational Gaussian curves andsurfaces[J]. Computer Aided Design, 1995, 27(5): 363-375
[47]Geraldine Morin, Ron Goldman. A subdivision scheme for Poisson curves and surfaces[J]. Computer Aided Geometric Design,2000,17(l l):813-833
[48]Carnicer JM, Pena J M. Totally positive bases for shape preserving curve design and optimality of B-splines[J]. Computer Aided Geometric Design, 1994, 11(6): 633-654.
[49]Jiwen Zhang. C-curve: An extension of cubic curves[J]. Computer Aided Geometric Design, 1996, 13(3): 199-217
[50]Gasca Pena. On factorizations of totally positive matrices total positivityand its applications[M]. Dordrecht: KluwerAcademic,1996
[51]Farin G. Curves and Surfaces for Computer Aided GeometricDesign[M]. San Diego, CA: Academic Press, 1997
[52]Pena J M. Shape preserving representations for trigonometric polynomial curves [J].Comput. Aided Geom. Design, 1997,14(1):5 - 11
[53]Jiwen Zhang. Two different forms of C-B-splines[J]. Computer Aided Geometric Design, 1997, 14(1):31-41
[54]Zhang J W. C-Bezier curves and surfaces[J]. Graphical Models and Image Processing, 1999,16(1):2-15
[55]Sanchez-Reyes J. Harmonic rational Bezier curves, p-Bezier curves and Trigonometric polynomials[J]. Computer Aided Geometric Design,1998, 15(9):909-923
[56]Mainar E, Pena J M. Corner cutting algorithms associated with optimal shape preserving representations [J]. Computer Aided GeometricDesign, 1999, 16(9):883-906.
[57]Mainar E, Pena J M, Sanchez-Reyes J. Shape preserving alternatives to the rational B6zier model[J]. Computer Aided Geometric Design, 2001, 18(1):37-60
[58]Mainar E, Pena J M. A basis of C-Bezier splines with optimalProperties [J]. Computer Aided Geometric Design, 2002,19(4): 291-295
[59]Xuli Han. Quadratic trigonometric polynomial curves with a shape parameter[J].Computer Aided Geometric Design, 2002,19(5): 503-512
[60]Qinyu Chen, Guozhao Wang. A class of Bezier like curves[J]. Computer Aided Geometric Design, 2003,20(1): 29-39
[61]陈秦玉，汪国昭．圆弧的C-Bezier曲线表示[J]．软件学报，2002，13(11)：2155-2161．
[62]樊建华，张纪文，邬义杰，C-Bezier曲线的形状修改，[J]．软件学报，2002，13(11)：2194-2199
[63]张帆，康宝生．(n+1)维空间C”[a，b]上规范基存在的充要条件[J]．计算机辅助设计与图形学学报，2003，13(5)：67-70
[64]檀结庆．连分式理论及其应用[M]北京：科学出版社，2007