下载文档原格式
浅议插值逼近方法及其发展摘要:本文探讨了数值分析中插值逼近方法的发展历程,详细介绍了几种插值逼近方法的特征,并运用自然辩证法基本理论分析了其发展的历史、现状,揭示了科学理论发展的共性问题,以此来指导我们在今后改进并构造新的插值逼近方法发展方向。
关键字:计算数学插值误差引言计算机的问世在全球范围内引发了一场信息风暴,信息技术几乎触及了现代生活的方方面面,计算数学的发展也受到了其很大的影响,函数曲线、曲面的插值逼近方法在其中有着重要的地位,正确认识其产生和发展,显的尤为重要。
以自然辩证法的观点认识分析插值逼近方法的发展历程,将有助于全面地推动数值计算方法的发展,有助于准确把握其发展趋势。
1插值逼近方法随着科学发展数学理论应用已渗透到各个领域。
插值逼近方法是数值计算的方法[1],是建立在数学理论的基础上的方法,给定一组有序的数据点,构造函数曲线通过这些给定得数据点,这些点可以是从某个形状上测量得到的,也可以是设计人员给定的,称为对这些数据点进行插值。
如果不要求严格通过给定的一组数据点,只要求所构造的函数曲线在某种意义下最接近这些数据点,称为对这些数据点进行逼近,所构造函数曲线称为逼近曲线.2自然辩证法自然辩证法是马克思主义对于自然界和科学技术发展的一般规律以及人类认识自然改造自然的一般方法的科学,是辩证唯物主义的自然观、科学技术观、科学技术方法论。
学习和运用自然辩证法将有助于我们搞清科学和哲学的关系,从而更加清楚地认识科学的本质和发展规律,更加全面的观察思考问题,以自然辩证法的观点来分析计算数学中插值逼近方法的发展。
3插值逼近方法的发展插值逼近方法是不断发展变化的,其发展的根本动力来自以下几个方面:⑴理论内部的矛盾;⑵实践与理论的矛盾;⑶理论之间的矛盾;⑷主观与客观的矛盾。
最初研究插值逼近理论[1]时,用到拉格朗日插值方法,但在增加插值点时,前面运算的值不能用到新的运算。
于是拉格朗日方法就需要发展改进,在这样的情况下,牛顿插值公式诞生了。
第6章 样条有限元条法§6.1 绪论20世纪60年代在R.W.Clough 命名后迅速发展起来的有限单元法，被公认为结构分析最强有力的工具，理论上可适用于所有的结构。
但对于规则区域的结构，有限元法的解题效率不如差分法；在计算机技术取得突破性进展之前，解决大型空间结构工程设计问题，往往需要大型计算机和昂贵的费用，使有限元法受到种种限制；有些结构问题用有限元法也难以解决，需要创造一些新的数值方法，于是又产生了有限条法、边界元法、样条元法以及新的加权残数（余量）法等等。
适用于几何形状规则和边界条件简单的土建结构的一种行之有效的特殊有限元法——半解析有限条法，是由Y.K.Cheung （张佑启）和E.L.Wilson 在1968年提出的[17]。
与有限元法相比，主要不同点在于所取得位移函数，一般是以多项式和正交级数乘积的形式给出，使得弹性力学问题降维，从而使总刚度矩阵大大降阶，既省机时，精度也高。
但对于非简支端边界条件，级数耦合，计算繁杂，尤其是对于集中荷载作用和内部支承情况，所取项数多，收敛慢。
对于处理沿跨向材料突变或是变截面问题，结果也不能令人满意。
1979年石钟慈提出样条有限元法[18]，用三次B 样条变分方法解规则区域上板梁组合弹性结构的平衡问题，导出适用于各种边界条件的统一计算格式，比通常的有限元法计算量少，精度高，便于在小型计算机上实现。
稍后，秦荣提出以样条函数、梁振动函数及能量变分为基础的样条有限点法和后来的样条子域法[19]。
1982年Y.K.Cheung 等人又提出结构分析的样条有限条法，以克服经典有限条法的缺点。
作者在分析空间悬挂结构吊桥时，采用元条相结合的方法[20]，将主索刚度叠加于桥面板条单元的结线上，分析索结构的动力特性取得成果。
§6.2 B 样条与样条函数样条函数是现代函数逼近的一个十分活跃的分支，是计算方法的一个重要基础，已得到广泛应用。
样条函数来源于实际生产中的样条曲线，由于样条函数是一个分段多项式，利用它去逼近任意函数，具有更大的灵活性和适应性。
考试目标及考试大纲本题库的编纂目的旨在给出多套试题，每套试题的考查范围及难度配置均基于“水平测试”原则，按照教学大纲和教学内容的要求，通过对每套试题的解答，可以客观公正的评定出学生对本课程理论体系和应用方法等主要内容的掌握水平。
通过它可以有效鉴别和分离不同层次的学习水平，从而可以对学生的学习成绩给出客观的综合评定结果。
本题库力求作到能够较为全面的覆盖教学内容，同时突显对重点概念、重点内容和重要方法的考查。
考试内容包括以下部分：绪论与误差：绝对误差与相对误差、有效数字、误差传播分析的全微分法、相对误差估计的条件数方法、数值运算的若干原则、数值稳定的算法、常用数值稳定技术。
非线性方程求解：方程的近似解之二分法、迭代法全局收敛性和局部收敛定理、迭代法误差的事前估计法和事后估计法、迭代过程的收敛速度、r 阶收敛定理、Aitken加速法、Ne w to n法与弦截法、牛顿局部收敛性、Ne w to n收敛的充分条件、单双点割线法（弦截法）、重根加速收敛法。
解线性方程组的直接法：高斯消元法极其充分条件、全主元消去法、列主元消去法、高斯-若当消元法、求逆阵、各种消元运算的数量级估计与比较、矩阵三角分解法、Doolittle 和Crout三角分解的充分条件、分解法的手工操作、平方根法、Cholesky分解、改进的平方根法(免去开方)、可追赶的充分条件及适用范围、计算复杂性比较、严格对角占优阵。
解线性方程组迭代法：向量和矩阵的范数、常用向量范数的计算、范数的等价性、矩阵的相容范数、诱导范数、常用范数的计算；方程组的性态和条件数、基于条件数误差估计与迭代精度改善方法；雅可比（Jacobi）迭代法、Gauss-Seidel迭代法、迭代收敛与谱半径的关系、谱判别法、基于范数的迭代判敛法和误差估计、迭代法误差的事前估计法和事后估计法；严格对角占优阵迭代收敛的有关结论；松弛法及其迭代判敛法。
插值法：插值问题和插值法概念、插值多项式的存在性和唯一性、插值余项定理；Lagrange插值多项式；差商的概念和性质、差商与导数之间的关系、差商表的计算、牛顿（Newton）插值多项式；差分、差分表、等距节点插值公式；Hermite插值及其插值基函数、误差估计、插值龙格（Runge）现象；分段线性插值、分段抛物插值、分段插值的余项及收敛性和稳定性；样条曲线与样条函数、三次样条插值函数的三转角法和三弯矩法。
二阶样条曲线插值法首先，二阶样条曲线插值法是一种基于分段多项式的插值方法。
它将插值区间分成多个小段，并在每个小段内使用一个二次多项式来逼近数据点。
这样可以保证插值曲线在每个小段内是光滑且具有连续的一阶和二阶导数。
其次，二阶样条曲线插值法要求插值曲线通过所有的数据点，并且在相邻数据点之间有一定的平滑性。
为了满足这个要求，插值曲线的一阶和二阶导数需要在相邻数据点处相等。
这样可以保证曲线在数据点处的连续性，并且避免了插值曲线出现剧烈的振荡。
另外，二阶样条曲线插值法需要确定每个小段内的二次多项式的系数。
常用的方法是使用自然边界条件或者固定边界条件来确定系数。
自然边界条件要求插值曲线的二阶导数在首尾两个数据点处为零，而固定边界条件要求插值曲线的一阶导数在首尾两个数据点处等于给定的值。
在确定系数之后，可以使用二次多项式的形式来表示每个小段内的插值曲线。
具体来说，每个小段内的插值曲线可以表示为一个关于自变量的二次函数，其中系数由上述边界条件决定。
通过将所有小段的二次函数拼接在一起，就得到了整个插值曲线。
最后，二阶样条曲线插值法在实际应用中有着广泛的应用。
它可以用于数据的平滑处理、函数逼近、图像处理等领域。
同时，二阶样条曲线插值法也有一些变种方法，如三次样条曲线插值法、自由样条曲线插值法等，用于处理更复杂的插值问题。
总结起来，二阶样条曲线插值法是一种基于分段二次多项式的插值方法，通过满足插值曲线通过数据点且具有一定的平滑性来得到一条平滑的曲线。
它在数值计算和数据处理中有着广泛的应用。
曲线的应用(一)曲线的应用介绍1. 数学中的曲线•直线曲线直线是最简单的曲线，通过两个点就能确定一条直线。
在几何学和物理学中，直线曲线经常用来描述物体的运动轨迹或者表示两点之间的最短路径。
•著名曲线–抛物线抛物线是一个U形的曲线，在物理学和工程学中广泛应用。
例如，在抛物面镜或者天花板上发射的物体会遵循抛物线轨迹。
–椭圆椭圆是一个闭合的曲线，可以通过一个焦距和离心率来确定。
在光学和天文学中，椭圆用来描述行星、卫星等天体的轨道，也常见于建筑设计和艺术中。
–双曲线双曲线也是一个闭合的曲线，与椭圆类似，可以由焦距和离心率确定。
它在物理学中用来描述反射和折射现象，也常见于数学分析和电子商务中。
–正弦曲线正弦曲线是一种周期性的曲线，常用来描述声音和光的波动。
它在物理学、工程学和信号处理领域都有广泛的应用。
2. 编程中的曲线•贝塞尔曲线贝塞尔曲线是一种参数化的曲线，可以通过多个控制点来精确地绘制平滑曲线。
在计算机图形学和游戏开发中，贝塞尔曲线常用来绘制复杂的曲线和曲面，例如绘制曲线路径或者设计独特的形状。
•样条曲线样条曲线是由多个小段曲线拼接而成的，可以用来表示光滑的曲线。
在计算机辅助设计（CAD）和三维建模中，样条曲线被广泛用于绘制曲线线条、曲面和体积模型。
•曲线拟合曲线拟合是一种数学方法，通过找到最适合一组离散数据点的曲线方程，从而能够近似地描述数据的趋势。
在数据分析和机器学习中，曲线拟合用来处理非线性关系的数据，例如用曲线来表示销售趋势或拟合曲线模型。
•曲线插值曲线插值是在已知一些离散点上，通过插值算法估计数据的未知部分。
在图像处理和数字信号处理中，曲线插值用来增加图像的分辨率、平滑数据或者还原丢失的信号。
3. 艺术和设计中的曲线•曲线艺术曲线在艺术作品中常用于创造流畅的线条和曲面，营造艺术家想要表达的感觉和形态。
例如，弯曲的线条可以传递柔和和优雅的感觉，而锐利的曲线则可以创造紧张和动态的效果。
•曲线设计曲线设计是一种注重曲线美感的设计风格，包括曲线形状、曲线交叉和曲线间的比例等。
收稿日期：2008-08-05基金项目：澳门科技发展基金资助项目（5，56）；北京师范大学珠海分校重点资助项目（Z 6）作者简介：余建德（3），男，广东中山人，讲师，博士研究生，主要研究方向为数字信号处理算法。
2010年工程图学学报2010第1期J OURNAL OF ENG INEERING GRAPHICSNo.1基于多结点样条的自由曲线最小误差逼近及其应用余建德1，黄静2（1.澳门科技大学资讯科技学院，澳门；2.北师大珠海分校信息技术与软件工程学院，广东珠海519085）摘要：多结点样条函数具有良好的局部性，而最小二乘法对数据拟合的全局性较好，因此多结点样条函数最小二乘逼近的稳定性及数值精度都能得到有效的保证。
该文综合两者的特点，实现了自由曲线离散数据最小逼近误差数学模型的建立。
同时应用此数学模型于一些平面及空间（甚至一些带噪音的）自由曲线拟合上和几何造型骨骼化上，测试其对各种自由曲线的拟合效果，结果证明最小逼近效果明显。
关键词：计算机应用；最小误差逼近；多结点样条；自由曲线中图分类号：TP 391.41文献标识码：A文章编号：1003-0158(2010)01-0088-06Least Error Approximation and Its Application for Free-FormCurves Based on Multi-Knots SplineU Kin-Tak 1,HUANG Jing 2(1.Facult y of Informat ion Technology,Macao University of Science and Technology,Macao,China;2.College of Information Technology and Software Engineering,Beijing Normal Uni versity,Zhuhai Campus,Zhuhai Guangdong 519085,China )Abstr act:Muti-knots spline has good locality and least square method has good global characteristics for data fitting.Therefore,the stability and numerical accuracy of least square method based on multi-knots spline approximation could be reached effectively.This paper combines the advantages of them and completes the model building of the free-form curves with least approximation error based on multi-knots spline.Meanwhile,this method is applied to the free-form-curve fitting of some plane and space (even with noise)data and Geometry Shape Skelectonization.The fitting results show that the least approximation effect is good.K ey wor ds:computer application;leasterror approximation;multi-knots spline;free-form-curves018/200A 04/200A 0007197-1问题的提出在实际应用特别是在反向工程中，对工件测量（数字化）之后得到的是一系列离散数据，为了实现工件的再加工或误差评定，必须对这些离散数据进行光滑而精确的曲线曲面重构，即数学建模。
为实现高效率高精度光滑建模，以用于CAD/CAM 系统，研究曲线曲面最小误差逼近拟合建模具有重要意义。
在建模领域，通常使用B 样条对曲线曲面进行插值建模[1-4]，而多结点样条近年来也因为它的各种优势而被广范用于插值法建模方面，且效果显著。
多结点样条函数最早是针对插值问题提出的，1975年，齐东旭教授[5-7]给出了多结点样条基本函数的构造及计算格式；后继的文献[8-11]给出进一步的理论分析和应用。
对插值问题而言，多结点技术的最大优点是导致插值过程无须求解任何方程组，而且插值格式具有局部性，这是与通常样条函数插值（三弯矩算法）在计算上的根本区别。
被广泛应用的B 样条曲线拟合方法虽然也不必求解方程组，也具有局部性，但在几何造型的应用中，因其无法保证通过型值点而给工程计算带来不便，因此多结点方法在工程应用上和理论研究上受到重视。
鉴于曲线建模是曲面建模的基础，本文研究这种甚具潜力的多结点样条拟合建模及其关键问题，实验表明，所建立的曲线拟合数学模型逼近拟合效果颇佳。
2多结点样条函数多结点基本样条函数是通过对等距结点B样条基本函数的平移及迭加而构成。
记I 为单位算子，μ为平均算子，对任意给定的常数ξ，定义1()[()()]2f t f t f t ξμξξ=++（1）记()()jhk j k L t c t μΩ=∑，()k t Ω为k 次多结点样条基本函数，其中121,,,k c c c "为待定常数，()k t Ω为k 次B 样条基本函数10111()(1),0,1,2,!2kk j kj k k x x j k j k Ω+=+++=+=∑";（2）01211()max{,0};0,02k k h h h h +==<<<<="。
显然，有0011()(),()()L t t L t t ΩΩ==;当k>1时，为了构造)(t L k ,考虑到)(t L k 的对称性，令)(t L k 满足(0)1,()0,1,2,,1k k L L i i k ==="于是得到关于121,,,k c c c "的线性方程组，由{()}j hkt μΩ的线性独立性质，可知这样的方程组的解是唯一的，所求得的)(t L k 即为k 次多结点样条基本函数，特别地，当k =2时，取21010==h ,h ，可求得2次多结点样条基本函数为1/222()(2)()L x I x μΩ=,当k=3时，取01110,,12h h h ===，可求得3次多结点样条基本函数为1/2331081()()()333L x Ix μμΩ=+（3）多结点样条基本函数（见图1）的性质类似于B 样条基本函数，其主要区别在于：-0.50.5-101-202-331111(a)k=0(b)k=1(c)k=2(d)k=3图1多结点样条基本函数第1期余建德等：基于多结点样条的自由曲线最小误差逼迫及其应用89)(t L k 不是非负函数，这将导致它构成的插值格式不是线性正算子，因此插值结果对数据而言不具有保凸性，这是追求显式解，局部性及基数型性质等优越性付出的代价。
尽管如此，正如B 样条基本函数插值对数据没有保凸性，但仍然实用一样，多结点样条插值也仍然是实用的，它已被成功地应用于飞机外形，进气道，机翼，海洋，地质的数据处理以及动画片的计算机制作等领域。
多结点技巧的意义首先在于构造显式插值格式。
此外，基本函数的有界支集性质保证了插值曲线（面）的局部性，有利于数据处理，如果N y y y ,,,10"为整数结点N t t t ,,,10"上给定的数据，则多结点样条插值函数可写为()()0j k f t y L tj t N =∑≤≤（4）当给出确定的边界约束条件之后，即可明确给出求和的上下限，对于给定几何造型的型值点N P P P ,,,10"，其参数形式的多结点样条曲线定义为()()0j k jP t P L tj t N =∑≤≤（5）3多结点样条最小逼近误差拟合数学模型（1）数学模型的建立本文采用三次多结点样条最小二乘法进行曲线建模，设在区间[a ，b]上有m 个采样点：),,2,1)(,(m j y j j "=ζ，构造多结点样条曲线模型，定义拟合曲线为31()()nii i S x C Lxx ==∑（6）其中i x 为给定的节点，调整不同距离的节点位置，可以得到不同的拟合效果，本文取等距的节点位置，通常m 远大于n 。
各采样点的残差表达式为311312323()()()()()nj j j ij i j i j j n jn jr S y CL x y C L x C L x C L x y ζζζζζ====+++∑"残差平方和为2121(,,,)mn jj F C C C r==∑"取拟合节点b a n <<<<<ξξξ"21，依据最小二乘原理残差平方和最小，即需确定n 个系数i C 使12(,,,)n F C C C "最小，于是得到方程组为n j C Fj,,2,1,0"==（7）矩阵表达式为2313132313111232313232311123313323111(())()()()()()()(())()()()()()()(())mmmii ji jn i j j mmmij iij n j i j mmmin j in jin j j i L x L x L x L x L x L x L x L x L x L x L x L x L x L x L x ξξξξξξξξξξξξξξξ=========∑∑∑∑∑∑∑∑∑""###"3111322131()()()mijj mij j nmin jj L x y C L x y C C L x y ξξξ====∑∑∑##（8）值得注意的是，由于多结点样条基函数的性质，使得该方程组的系数矩阵具有带状对角特点，条件数较好，方程组求解容易速度快，求出的系数n C ,,C ,C "21为型值点的代表点。
这一特点使得用多结点样条最小逼近误差拟合数学模型的方法优于其他方法。
4实例分析及其应用利用参数形式的三次多结点样条作最佳逼近的例子。
（1）平面曲线的拟合（见图2）下列两例子的原曲线参数方程分别为x =cos(t/7);y =sin(t/5)及x =cos(t/4);y =sin(t/10)90工程图学学报2010年10.50-0.5-10-0.510.50-0.5带噪音的离散点原曲线原曲线离散化(1024点)-10.51-0.5-10.51-110.50-0.50-0.510.50-0.5-10.51-0.5-10.51-1-110.50-0.5-10-0.510.50-0.5带噪音的离散点16段三次多结点样条拟合曲线原曲线原曲线离散化(1024点)16段三次多结点样条拟合曲线-10.51-1-1-0.50.5110.50-0.50-0.510.50-0.5-10.51-0.5-10.51-1-1图2平面曲线拟合从这两个例子表明，用多结点样条最佳逼近的拟合，对于带有噪音的平面离散数据，依然可以较好地重构原曲线（见图2），而且所使用的段数较少，只需16段，即17个拟合系数，即可较好地完成对1024个点的数据拟合。
