摘要
样条函数被认为是在数值逼近,计算机辅助设计,图像分析和数值分析等方面的一种高效率的工具。随着计算机的高速发展,样条函数以其便于计算机存储、计算稳定、局部支集以及便于交互控制等优点,成为各类工程计算、计算机辅助制造/设计和几何建模等大型软件的重要数学工具之一。
早在60年代一元样条的理论就开始了快速的发展,许多论文和书籍都纷纷发表,这种发展一直持续到80年代并到达了顶峰。现在我们所熟悉的理论都是在那个时候建立的([10]和[31])。一元样条现在已经成为各种应用领域重要的工具,并且是现在数值分析中重要的一个方向。如果说60到80年代是一元样条的时代的话,现在就是多元样条的时代。早在80年代,就有一些关于二元、三元分片多项式作为有限元的结果,但那时人们并没有重视多元的样条。现在关于多元样条的论文多的举不胜举。
本论文主要讨论的是多元样条(特别是二元样条)函数方法在数据插值拟合中的应用。这里我们所说的多元样条是指由定义在一些三角剖分上的分片多项式的集合,而这些分片多项式之间满足一定的连续条件,从而整体上达到一定的光滑性。多元样条和一元样条一样也具有许多优秀的性质,这些性质使它成为非常重要的工具。比如多元样条在计算函数值和导数值的时候具有高效、稳定的算法等。
本论文分为四章。第一章首先介绍样条函数的B-形式,接着推出在B-形式下的一些基本算法。比如de Casteljau求值算法,求导、求积以及求内积算法等。这些算法在构造矩阵方程时起到了重要的作用。然后介绍了分片多项式的拼接条件以及如何建立整个样条空间,并简单的分析了一下常用的各种三角剖分。最后介绍了一个用于矩阵计算的迭代算法。
第二章主要讨论了散乱数据Hermite插值问题。我们首先从如何构造满足条件的样条函数说起,从文章[26]和[29]中得到启发,提出了新的能量函数,来满足数据Hermite插值的要求。并讨论了它的存在性和唯一性,以及它的逼近结果。从结果上来看,如果散乱数据来自一个光滑的函数,那么我们做出的样条函数能够充分的逼近于它。最后我们构造了一些数值例子来说明它的逼近结果,同时也采集了中国大陆的各个地方的风速大小作为数据进行插值实验,并构造了中国大陆的风速势力场。
最后两章主要讨论了散乱数据拟合的问题。当散乱数据充分多或者相对较少的时候,显然用插值方法已经不合适了,我们只能用拟合的方法。其中第三章我们采用的是扩展罚函数方法来解散乱数据相对较少的拟合问题,特别是我们对曲面的扰度有特别要求的时候。相比于普通的罚函数方法[44],我们提出的扩展罚函数法可以处理带导数信息的数据。因此可以看成是罚函数法的推广。而最后一章我们采用的是扩展带权的二乘法来解散乱数据充分多的拟合问题,特别是我们知道各种数据的误差程度或数据带有导数信息的时候。我们可以通过对权的选择,来调整各种数据的重要性,并加入了对数据误差的概率分析,发现了多次拟合后求平均可以明显改善误差这个结果。同样的这两章我们都是从样条函数的存在性和唯一性讨论起,并给出了它的逼近结果以及一些数值例子。
Spline is an excellent tool for numerical approximation,which is a perfect result of the combination of approximation theory and computer theory.In modern computational work,spline is the major tool for engineers and CAD software since it is easy to represent and efficient to evaluate.The spline finite element is also an efficient tool in finite element analysis.
The theory of univariate splines began its rapid development in the early sixties, resulting in several thousand research papers and a number of books.This development was largely over by 1980,and the bulk of what is known today was treated already in the classic monographs of deBoor[10]and Sehumaker[31].Univariate splines have become an essential tool in a wide variety of application areas, and are by now a standard topic in numerical analysis books.If 1960-1980 was the age of univariate splines,then now can be regarded as the age of multivariate splines. Prior to 1980 there were some results for using piccewisc polynomials in two and three variables in the finite element method,but multivariate splines had attracted relatively little attention.Now we have thousands of papers on the subject.
The main purpose of this thesis is to discuss about multivariate spline method(especially in bivariate spline) and its application in scattered data fitting.Here a multivariate spline is a function which is made up of pieces of polynomials defined on some partition△of setΩ,and joined together to ensure some degree of global smoothness.As we shall see,multivariate polynomial splines have many of the same features which make the univariate splincs such powerful tools for applications such as splines are easy to work with computationally,and there are stable and efficient algorithms for evaluating their derivatives and integrals,ect.This thesis is organized as follows:
In the first chapter we introduce the spline in B-form and some of its useful algorithm relate to triangle such as the de casteljau algorithm,derivative algorithm, integrals algorithm,etc.Some of them are very important in building the matrix. Then we show how to use the smooth condition and build the whole space of spline. Next we list some different kinds of triangulations which are usually used in many papers.Finally,we introduce a iteration algorithm used in matrix computation.
In the second chapter we discuss about scattered data hermite interpolation problem.We start this from how to build a spline which satisfied the interpolation problem.We provide a new energy function method which is different from[26]and [29].Then we show the existence and uniqueness of the spline which is generated by our method.Next,we present the error bound of the spline.Finally,we offer some numerical experiments to demonstrate our method.
The last two chapters are all about scattered data fitting.If the number of the data are large or very small,it may not be appropriate to interpolate the data.In the third chapter we use extended penalty function method to fit the data when the number of the data are very small.This method can deal with the data with derivative compare to penalty function method.In the final chapter,we use weighted least squares method to fit the data of which the number is large.We can adjust the weighted functions according to the importance of each data.As always,we show the existence and uniqueness of the splines in last two chapters and also with error bound and numerical experiments as well.
引文
[1] Alfeld, P., M. Neamtu and L. L. Schumaker(1996), Bernstein-Bezier polynomials on spheres and sphere-like surfaces, Computer Aided Geometric Design, 13 , pp. 333-349.
[2] Alfeld, P., M. Neamtu and L. L. Schumaker(1996), Fitting scattered data on sphere-like surfaces using spherical splines, J. Comp. Appl. Math., 73, pp. 5-43.
[3] Alfeld, P., M. Neamtu, and L. L. Schumaker(1996), Dimension and local bases of homogeneous spline spaces, SIAM J. Math. Anal., 27, pp. 1482-1501.
[4] Alfeld, P. and L. L. Schumaker. Smooth macro-elements based on Clough-Tocher triangle splits, Numer. Math. 90 (2002), pp.597-616.
[5] A. Mazroui, D. Sbibih and A. Tijini, Recursive computation of Bivariate Her-mite spline interpolants, Submitted for publication.
[6] Braess, D. Finite Elements, Cambridge, Cambridge University Press, 1997.
[7] B. Fraeijs de Veubeke, A conforming finite element for plate bending, J. Solids Structures, 4 (1968), pp. 95-108.
[8] Brenner, S. C. and L. R. Scott. The Mathematical Theory of Finite Element Method, New York, Springer, 1994.
[9] C. de Boor, A bound on the L_∞ norm of L_2 approximation by splines in terms of a global mesh ratio, Math. Comp. 30 (1976), 765-771
[10] C. de Boor. A Practical Guide to Splines. Springer, New York, 1978(2003).
[11] C. K. Chui and M. J. Lai, On bivariate super vertex splines, Constr. Approx., 6(1990), 399-419.
[12]Ciarlet,P.G.The Finite Element Method for Elliptic Problems,Amsterdam,North Holland,1978.
[13]Ciarlet,P.G.Interpolation error estimates for the reduced Hsich-Clough-Tocher triangle,Math.Comp.32(1978),pp.335-344.
[14]Clough.R and J.Tocher,Finite element stiffness matrices for analysis of plates in bending,in Proc.of conference on Matrix Methods in Structural Analysis,Wright-Patterson Air Force Base,1965.
[15]C.de Boor,B-form basis,in Geometric Modeling,edited by G.Garin,SIAM Publication,Philadelphia,1987,pp.131-148.
[16]D.Hong,Spaces of Bivariate Functions over Triangulation.Approx.Theory Appl,7(1991),pp.56-75.
[17]Davydov,O.,G.Nunberger,and F.Zeilfelder,Bivariate spline interpolation with optimal approximation order,Constr.Approx.,17(2001),181-208.
[18]F.Brezzi,M.Fortin,Mixed and Hybrid Finite Element Methods,Springer,New York,1991.
[19]G.Nurnberger.Approximation by Spline Functions.Springer,Belin,1989.
[20]G.Farin,Triangular Bernstein-Bezier patches,Comput.Aided Geom.Design 3(1986),pp.83-127.
[21]G.Awanou,M.J.Lai,On convergence rate of the augmented Lagrangian algorithm for nonsymmetric saddle point problems.App.Numer.Math.54(2005),pp.122-134.
[22]G.Awanou,M.J.Lai,P.Wenston,The multivariate spline method for scat-tered data fitting and numerical solutions of partial differential equations,in Wavelets and Splines,Edited by G.Chcn and M.J.Lai,Nashboro Press,Brentwood,Tennessee,2006,pp.24-76.
[23] G. Sander, Bornes supérieures et inferieures dans l'analyse matricielle des plaques en flexion-torsion, Bull. Soc. Royale SeiencesLiege, 33 (1964), pp. 456-494.
[24] H. C. Elman and G. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal. 31(1994), pp. 1645 - 1661.
[25] J. H. Bramble, Pasciak J.E. and A.T.Vassilev, Uzawa type-algorithms for nonsymmetric saddle point problems, Math. Comp. 69 (1999), pp. 667-689.
[26] G. E. Fasshauer and L. L. Schumaker, Minimal energy surfaces using parametric splines, Comput. Aided Geom. Design, 13 (1996), pp. 45-76.
[27] G. Wahba, 1990, Splines for Observation Data, SIAM Publication, Philadelphia.
[28] J. Duchon, Interpolation des fonctions de deux variables suivant le principe de la flexion des plaques mines, RAIRO Num. Anal, 10 (1976), pp. 5 - 12.
[29] K. Farmer and M. J. Lai, Scattered data interpolation by C2 quintic splines using energy minimization, in: C.K. Chui and L.L. Schumaker,(Eds.), Approximation Theory IX, 1998, pp. 47-54.
[30] K. Subrahmaniam, A Primer in Probability-Second Edition,Revised and Expanded, 1990, Mercel Dekker,INC.
[31] L. L. Schumaker. Spline Functions: Basic Theory. Wiley-Interscience, New York, 1980.
[32] L. L. Schumaker. Triangulation methods, in Topics in Multivariatc Approximation, C. K. Chui, L. L. Schumaker and F. Utreras (eds.), New York, Academic Press, 1987, pp. 219-232.
[33] L. L. Schumaker, Fitting surfaces to scattered Data, in G. G. Lorcntz. C.K. Chui and L.L. Schumakcr,(Eds.), Approximation Theory II, pp. 203- 269.
[34]J.F.Ciavaldini and J.C.Nedelec,Sur l'element de Fraeijs de Veubeke et Sander,Rev.Francaise Automat.Informat.Rech.Oper.,Anal.Numer.2(1974),pp.29-45.
[35]J.H.阿尔博格,E.N.尼尔森,J.L.沃尔什.样条理论及其应用.科学出版社,1981.
[36]M.J.Lai,Scattered data interpolation and approximation by using bivariate C~1 piecewise cubic polynomials,Comput.Aided Geom.Design,13(1996),pp.81-88.
[37]M.J.Lai and L.L.Schumaker,Scattered data interpolation using C2 super-splines of degree six,SIAM J.Numcr.Anal.34(1997),pp.905-921.
[38]M.J.Lai and L.L.Schumaker,Approximation power of bivariate splines,Advances in Comput.Math.,9(1998),pp.251-279.
[39]M.J.Lai and L.L.Schumaker,On the approximation power of splines on triangulated quadrangulations,SIAM J.Numer.Anal.36(1999),pp.143-159.
[40]M.J.Lai and L.L.Schumaker,Macro-Elements and Stable Local Bases for Splines on Clough-Tochcr Triangulations,Numerischc Mathematik,88(2001),pp.105-119.
[41]M.J.Lai and L.L.Schumakcr,Quadrilateral macro-elements,SIAM J.Math.Anal.33(2002),pp.1107-1116.
[42]M.J.Lai and L.L.Schumaker,Macro-elements and stable local bases for splines on Powell-Sabin triangulations,Math.of Computation,72(2003),pp.335-354.
[43]M.von Golitschck,M.J.Lai and L.L.Schumaker,Error bounds for minimal energy bivariatc polynomial splines,Numer.Math.93(2002),315-331.
[44]M.Von Golitschck and L.L.Schumaker,Penalized Least Squares Fitting,Serdica.18(2002),1001-1020.
[45] M. von Golitschek and L. L. Schumaker, Bounds on projections onto bivariate polynomial spline spaces with stable local bases, Constr. Approx, 18 (2002), 241-254.
[46] M. J. Lai and L. L. Schumaker. Spline Functions on Triangulations. United Kingdom at the University Press,Cambridge, 2007.
[47] Powell, M. J. D. and M. A. Sabin. Piecewise quadratic approxiamtions on triangles, ACM Trans. Math. Software, 3(1977), pp. 316-325.
[48] S. Rippa, Scattered data interpolation using minimum energy Powell- Sabin elements and data dependent triangulations, Numer. Algorithms 5 (1993), pp.577-587.
[49] T. J. Willmore, Riemannian Geometry, Oxford University Press, USA, New York, N.Y., 1997.
[50] R. H. Wang, Multivariate Spline Functions and Their Applications, Science Press, Beijing, 2006.
[51] Wang Tianjun, A C2-quintic spline interpolation scheme on triangulation, Computer Aided Geometric Design, 9(1992), pp. 379-386
[52] G. Awanou and M. J. Lai, On convergence rate of the augmented Lagrangian algorithms for non symmetric saddle point problems, J. Applied Num. Math., 54(2005), pp. 122-134.
[53] G. Awanou, M. J. Lai, P. Wenston The multivariate spline method for scattered data fitting and numerical solutions of partial differential equations, to appear in Wavelets and Splines, Edited by G. Chen and M. J. Lai, Nashboro Press, Brentwood, Tennessee, 2006, pp. 24-76.
[54] V. Baramidze and M. J. Lai Error Bounds for Minimal Energy Interpola-tory Spherical Splines, Approximation Theory XI, edited by C. K. Chui, M. Neamtu, and L. L. Schumaker, Nashboro Press, Brentwood, 2005, pp. 25-50.
[55] V. Baramidze, M. J. Lai, and C. K. Shum , Spherical Splines for Data Interpolation and Fitting, SIAM J. Scientific Computing, 28(2006), 241-259.
[56] V. Baramidze, S.C. Han, M. J. Lai, C. K. Shum, and P. Wenston , Triangulated spherical splines for geo-potential reconstruction, submitted, 2006.
[57] Charles K. Chui, Ming-Jun Lai, Filling polygonal holes using C~1 cubic triangular spline patches, Computer Aided Geometric Design 17(2000),297-307.
[58] G. Fasshauer and L. L. Schumaker, Scattered data fitting on the sphere, in Mathematical Methods for Curves and Surfaces II, M. Daehlen, T. Lyche, L. Schumaker, Vanderbilt University Press,(1998) pp. 117-166.
[59] A. Gomide and J. Stolfi, Nonhomogeneous polynomial C~k splines on the sphere S~n, Relatorio Tecnico IC-00-13,(2000).
[60] J. Hahn(1989), Filling.polygonal holes with rectangular patches, in: Theory and Practice of Geometric Modeling, 81-91.
[61] AK Jones, Nonrectangular surface patches with curvature continuity, Comuter-Aided Design 20(1988),325-335.
[62] S. Kersey, Smoothing and near-interpolatory subdivided surfaces, Geometric modeling and computing: Seattle 2003, Eds. M. Lucian and M. Neamtu, Nashboro Press, (Brentwood) (2004), 353-364.
[63] M. Neamtu and L. L. Schumaker, On the approximation order of splines on spherical triangulations, Adv. in Comp. Math., 21(2004), pp. 3-20.