用三次样条插值设计中英文签名课程设计.doc

1、数值分析课程设计报告中英文设计签名 目 录1、理论分析（含问题分析，理论依据，求解对策等）；2、方法详解（含推导、求解、分析、程序框图等）；3、应用实例（含程序清单、计算结果输出、图形演示等）；4、效果分析（含对不同方法间的图形、数值等多方位的对比分析，对所得结果的合理解释等）一、 理论分析：1. 问题分析 （1）设计自己的英文签名，给出一组数据点，用三次样条曲线画出所设计的英文签名的字体。(2)设计你的草体汉字签名,给出一组数据点,分别用三次样条曲线画出所设计的中文签字的字体. （3）如果设计出的三次样条不满意，怎么改进算法？2.2 分析思想 要设计出英（中）文签名，首先、要获得与自己英（中

2、）文签名相似的一组数据点，最好这组数据点的获取可因名字的改变而改变且简单易行，以适应不同的签名；其次、要选用合适的算法，才能设计出较美观的签名，问题要求用三次样条插值做，若效果不满意，改进时可选择其他算法；最后、选择合适数学工具和备用改进算法，合适的数学工具能大大简化我们的工作量，获得满意结果。备用的改进算法的提出可以引导我们在下面的课程设计中注意基本算法的不足，多思考，勤探究。2. 理论依据 2.1 交互式界面 交互式界面即窗口、光标、按键、菜单、文字说明等对象（Objects）构成的一个用户界面。用户通过一定的方法（如鼠标或键盘）选择、激活这些图形对象，使计算机产生某种动作或变化，比如实现

3、获取数据、计算、绘图等。要使数据点可因名字的改变而改变且简单易行，以适应不同的签名，可采用交互式界面进行操作。如我们可以用鼠标点击获取名字大致的数据点，显然，不同名字可以实现能得到不同数据点。在MATLAB中，可以用ginput()函数轻松实现这一功能。 2.2 三次样条插值算法 在区间a,b上给定有n+1个节点的分割:a=xxx=b。若在a,b上定义的函数s(x)满足：(1)在子区间x,x上s(x)是最高为三次的多项式，i=0，1， n-1；(2)在a,b上s(x)是二阶连续可微函数，即s(x)Ca.b。则称s(x)为a,b上关于分割的三次样条函数。S(x)对应的曲线称为三次样条曲线。若s（

4、x）还满足(3)S(x)=y=f,i=0,1,n则称s(x)为a,b上关于分割的三次样条插值函数，f(x)称为被插函数。三次样条插值函数对应的曲线称为三次样条插值曲线。我们知道分段低次插值的优点是具有收敛性与稳定性，缺点是光滑性较差，不能满足实际需要.例如高速飞机的机翼形线、船体放样形值线、精密机械加工等都要求有二阶光滑度，即二阶导数连续，通常三次样条(Spline)函数即可满足要求。所以对于签名，三次样条插值算法完全能够在给定的一组数据点下实现签名效果。3. 求解对策 对策 问题 MATLAB7.0选用合适的数学工具双三次插值算法选用改进算法三次样条插值算法：可产生二阶光滑度，即二阶导数连续

5、签名图样选用合适的算法采用交互式界面进行操作，用鼠标点击获取名字大致的数据点获得与签名相似的一组数据点，最好可因名字的改变而改变实现英（中）文签名二、 算法设计（推导、求解）：2.1、三次样条插值函数的定义样条（Spline）是绘图员用来描绘光滑曲线的均匀有弹性的细长木条（或有机玻璃条）。用压铁将木条加以固定使它通过各型值点，最后沿着这根木条画出光滑曲线，作用与曲线板和云形规相似。我们称这条光滑的曲线为样条曲线，样条曲线对应的函数称为样条函数。它是连续的光滑的，具有连续变化的曲率，实际上就是一条三次样条曲线。定义：在区间a,b上给定有n+1个节点的分割:a=xxx=b。若在a,b上定义的函数s

6、(x)满足：(1)在子区间x,x上s(x)是最高为三次的多项式，i=0，1， n-1；(2)在a,b上s(x)是二阶连续可微函数，即s(x)Ca.b。则称s(x)为a,b上关于分割的三次样条函数。S(x)对应的曲线称为三次样条曲线。若s（x）还满足(3)S(x)=y=f,i=0,1,n则称s(x)为a,b上关于分割的三次样条插值函数，f(x)称为被插函数。三次样条插值函数对应的曲线称为三次样条插值曲线。同时我们还可以通过计算三次样条函数s(x)在节点上的一阶导数m=s(x)或二阶导数M=s(x),i=0,1,n的值来求过型值点。(x,y),i=0,1,n的三次样条函数。对应地可以导出称之为m关

7、系式和关系式，它们分别是关于m和M的代数方程组。2.2三次样条插值算法推导、求解记h=x,i=0,1,n-1。根据三次样条函数的定义，当x x,x时，它是一个三次多项式，所以s(x)是线性函数，可以表示为： s(x)= M+ M从x到x对其积分两次，得s(x)= - M+ M+As (x)= M+ M+ A(x-x)+B 这里A，B是积分常数，可由插值条件，即s(x)= y，s(x)=y,来确定。 解得: 则s(x),s(x)在xx上可表示为：S(x)= M+ M+ (x-x)+y-Ms(x)=-M+M+-由上式易见，若M(i=0,1,n)确定后，则三次样条插值函数s(x)就完全确定了。在上，

8、由4.5.9得由此可得： 由于s(x)在x点处应是连续函数,即s(x)=s(x) i=1,2,n-1,得 令 得 ， i=1,2,n-1这是一个含有n+1个未知量M,M,M的n-1个方程组成的线性方程组，我们称它为M关系式。记m,根据Hermite插值，在，上由，,可得： 它在的右极限和的左极限分别为： 得 由 ，i=1，2，,n-1,得 两边乘以 ，并记 得 ， = 1,2,n-1这是一个含有n+1个未知量,的n-1个方程组成的线性方程组，我们称它为m关系式。注：无论是M关系式还是m关系式，都应该补充2个条件才能把它的解唯一地确定下来，这就是我们所要讨论的端点约束条件。样条插值函数的端点条件

9、有多种形式，主要根据实际问题来确定。从物理观点看，它们对应在曲线两端给出的约束类型。常用的端点约束条件有：自由端点条件，夹持端点条件，周期端点条件。下面我们主要来讨论夹持端点条件来求解结果。在端点给定的一阶导数值，即 ， 这里，为已知数，将它们代入关系式得 =这是关于n-1个未知量,由n-1个方程组成的线性方程组，根据其系数矩阵严格对角占优，方程组存在唯一解。关于M关系式，只要注意到 记 ， ，和M关系式联立得： = (20)这是一个关于n+1未知量,，由n+1个方程组成的线性方程组，其系数矩阵为三角严格对角占优矩阵，非奇异，上20式存在唯一解。 下面我们来分析一下样条函数的收敛性问题：定理设

10、在闭区间a,b上给定了一个分割序列 ：记 中子区间的最大最小长度分别为和即 = 设在区间上有4阶连续导数，且 对给定的分割序列成立 设为上的的样条函数，且，i=0,1,n, 则对一切成立 | ， i= 0，1，2，3其中，和无关，且，该定理表明，只要分割是比较均匀的，则样条插值函数序列及其一至三阶导函数均收敛于被插函数及其对应阶导函数。误差估计问题： 设，S是在上关于剖分的满足I型边界条件的三次样条插值函数，则有估计式 其中，。证明：设为上关于节点的分段三次ermite插值多项式， j=0,1,n。在子区间(j=0,1,n-1)上，其中，为三次Hermite插值的基函数。对于，利用三次样条插值

11、函数表达式得 = 利用三次Hermite插值多项式的余项估计有 ， 。 利用引理，当有 由区间的任意性，即可以得出 由此说明了三次样条插值函数S，当时，一致收敛于被插值函数三、 程序设计（分析、程序框图）：本实验中所有程序均是在MATLAB7.0环境下实现。3.1 ginput()程序分析 本实验利用两种方法获取签名数据点（以下简称点），由于MATLAB7.0中自带的交互式函数ginput()在鼠标单击取点时无法显示该点位置，为了能够清晰地知道当前和已经取过的点的位置，我才用了两种取点方法：方法1：对MATLAB7.0中自带的交互式函数ginput()进行了修正 通过edit ginput，打

12、开ginput()函数，在位置136138行： pt = get(gca, CurrentPoint); line(Parent,gca,Xdata,pt(1,1),Ydata,pt(1,2),Marker,p,color,r);（我插入的） how_many = how_many - 1; 插入以上语句。另存为：myginput.m,即可实现交互式函数取点，并留下痕迹。 方法2：不改ginput()函数，利用while(1)单个取点 while(1) 取一个点，x,y=ginput(1) 用line函数将点改成红色星星 将该点横纵坐标分别送入X、Y向量集内 if x,y无值，按了回车键 br

13、eak endend 3.2三次样条插值程序分析 3.2.1 符号对应含义程序中符号算法分析中符号实际含义Xxx插值点横坐标 Yyy插值点纵坐标 mn给定插值数据的维数H区间长度lambda后一区间长度比前两个区间长度之和mu前一区间长度比后两个区间长度之和D的二阶均差Sx三次样条插值所得函数3.2.2 初始化数据：m取给定插值数据的维数：m=length(X)H初始化为1*n的零矩阵：H=zeros(1,n)，H(1)=X(2)-X(1)，这里n=m-1lambda初始化为1*n的零矩阵：lambda=zeros(1,n) ，lambda(1)=1A初始化为m*m的零矩阵：A=zeros(m

14、,m)，A(1,1)=2，A(1,2)=lambda(1)mu初始化为1*n的零矩阵：mu=zeros(1,n)， mu(1)=1D初始化为1*n的零矩阵：D=zeros(1,n)，D(1)=3*(Y(2)-Y(1)3.2.3 求hk 、lambdak 、muk、dk算法：求hk：for k=1:nhk=X(k+1)-X(k);H(k+1)=hk;end求lambdak、muk、dk：for k=1:n-1lambdak=H(k)/(H(k)+H(k+1); lambda(k+1)=lambdak;muk=1-lambda(k+1);mu(k)=muk;dk=3*(mu(k).*(Y(k+1)

15、-Y(k)./H(k)+(lambda(k+1).*(Y(k+2)-Y(k+1)./H(k+1);D(k+1)=dfor k=2:m3.2.4 求Sx算法Sx=Y(k-1)*(H(k-1)-2*X(k-1)+2*x)*(x-X(k)2)/(H(k-1)3)+Y(k)*(H(k-1)+2*X(k)-2*x)*(x-X(k-1)2)/(H(k-1)3)+dY(k-1)*(x-X(k-1)*(x-X(k)2)/(H(k-1)2)+dY(k)*(x-X(k)*(x-X(k-1)2)/(H(k-1)2)fprintf(%6.4fx,X(k-1);fprintf(%6.4fn,X(k);end3.3 图像

16、（签名）输出程序分析 利用subplot(m,n,t)z函数在一个窗口上显示多个图样。用plot()画出由spline()插值后的点所得签名图像。 用x,y,button=ginput(1)来实现中英文签名判断： if button等于1 输出标题：英文签名 elseif button等于3 输出标题：中文签名 else 输出空白标题 end3.4 程序框图 开始将gca设置成：set(gca,xlimmode,manual,ylimmode,manual) 取 点方法1：调用函数mygiput()方法2：或调用函数ginput()获取插值点的横纵坐标X,Y初始化数据: m、H、lambda、

17、A、mu、D等 插 值调用三次样条插值函数spline()调用双三次插值函数cubic() 输出签 名图像调用窗口图像控制函数subplot()调用绘图输出函数plot() 判断签 名类型buttonbutton=3中文签名button=1英文签名=结束输出签名图像和类型四、 签名验证（应用实例）：4.1 程序清单 见附录4.2 图形演示 1.程序运行，如下图出现交互式界面，等待签名者签名。2.在窗口内点击签名字样，进行取点签名，如下图为：wei的英文轮廓，红色星星为鼠标点击留下的痕迹。4. 按回车键结束鼠标取点，程序输出签名图像,如下图（注意：此时并未输出签名类型，界面有十字光标，等待签名者

18、判断操作）：5. 单击鼠标左键，右下角出现签名类型和图例，如下图为：英文签名。若为中文签名单击鼠标右键即可。5.中文签名步骤与英文类似，以下仅给出最后签名结果: 4.3 计算结果输出以下是对英文w进行签名得到的三次样条函数，由于wei取点较多，会输出大量数据，故仅对w进行签名能得到较简单的输出：Sx = 62464/3*(-193/448+2*x)*(x-235/896)2+56320/3*(249/448-2*x)*(x-207/896)2+6118033249439999/4398046511104*(x-207/896)*(x-235/896)2-6540245714505983/219

19、9023255552*(x-235/896)*(x-207/896)2 0.2310x0.2623 Sx = 1014570924054025338880/14357685692506197*(-113/224+2*x)*(x-253/896)2+6511700658019471720448/100503799847543379*(131/224-2*x)*(x-235/896)2-53577692893233012736/7444725914632849*(x-235/896)*(x-253/896)2-42397238503447396352/7444725914632849*(x-253

20、/896)*(x-235/896)2 0.2623x0.2824 Sx = 34594/3*(-237/448+2*x)*(x-285/896)2+28126/3*(43/64-2*x)*(x-253/896)2-31699595438673743/17592186044416*(x-253/896)*(x-285/896)2-326583779752527493/140737488355328*(x-285/896)*(x-253/896)2 0.2824x0.3181 Sx = 23634890844440363008/2077211471716767*(-135/224+2*x)*(x-

21、45/128)2+45540399431970455552/4846826767339123*(165/224-2*x)*(x-285/896)2-6824934499318125568/2584974275914195*(x-285/896)*(x-45/128)2-1791493680497956608/2584974275914195*(x-45/128)*(x-285/896)2 0.3181x0.3516 Sx = 728646390911527288832/11764505149049443*(-307/448+2*x)*(x-331/896)2+72864639091152728

22、8832/11764505149049443*(339/448-2*x)*(x-45/128)2-342903087282812007/140737488355328*(x-45/128)*(x-331/896)2+358054521960066379/281474976710656*(x-331/896)*(x-45/128)2 0.3516x0.3694 Sx = 80896/7*(-317/448+2*x)*(x-359/896)2+306176/21*(373/448-2*x)*(x-331/896)2+7307235142042171/17592186044416*(x-331/89

23、6)*(x-359/896)2+8991211591613103/1099511627776*(x-359/896)*(x-331/896)2 0.3694x0.4007 Sx = 176498447297252989861888/119115614634127461*(-89/112+2*x)*(x-365/896)2+198929688090883804626944/119115614634127461*(23/28-2*x)*(x-359/896)2+1178496085735912636416/6617534146340383*(x-359/896)*(x-365/896)2+1143

24、740219012357160960/6617534146340383*(x-365/896)*(x-359/896)2 0.4007x0.4074 Sx = 6216552752840118894592/183498707266227759*(-177/224+2*x)*(x-387/896)2+7544718326147206610944/183498707266227759*(199/224-2*x)*(x-365/896)2+35741881844136161280/2780283443427697*(x-365/896)*(x-387/896)2+201186455433464832

25、00/2780283443427697*(x-387/896)*(x-365/896)2 0.4074x0.4319 Sx = 3772359163073603305472/68932647357711963*(-377/448+2*x)*(x-407/896)2+1429622665712490250240/22977549119237321*(417/448-2*x)*(x-387/896)2+20118645543346483200/2297754911923729*(x-387/896)*(x-407/896)2-2775508141924100096/2297754911923729

26、*(x-407/896)*(x-387/896)2 0.4319x0.4542 Sx = 571849066284996100096/1985260243902075*(-401/448+2*x)*(x-419/896)2+7987440183916235849728/29778903658531125*(425/448-2*x)*(x-407/896)2-11102032567696400384/3308767073170137*(x-407/896)*(x-419/896)2-28520465010548310016/1102922357723379*(x-419/896)*(x-407/

27、896)2 0.4542x0.4676 Sx = 3993720091958117924864/91749353633115129*(-51/56+2*x)*(x-63/128)2+1116028016459427872768/30583117877705043*(113/112-2*x)*(x-419/896)2-10695174378955616256/1390141721713861*(x-419/896)*(x-63/128)2-11288929969426923520/1390141721713861*(x-63/128)*(x-419/896)2 0.4676x0.4922 Sx

28、= 2232056032918855745536/61166235755409253*(-215/224+2*x)*(x-463/896)2+5109748108417545797632/183498707266227759*(237/224-2*x)*(x-63/128)2-22577859938853847040/2780283443427697*(x-63/128)*(x-463/896)2-19102396736613715968/2780283443427697*(x-463/896)*(x-63/128)2 0.4922x0.5167 Sx = 102194962168350915

29、95264/141174061788594639*(-65/64+2*x)*(x-479/896)2+9112691572412518498304/141174061788594639*(487/448-2*x)*(x-463/896)2-76409586946454863872/5882252574524761*(x-463/896)*(x-479/896)2-18483686365463552000/5882252574524761*(x-479/896)*(x-463/896)2 0.5167x0.5346 Sx = 2803905099203851845632/542977160725

30、3539*(-475/448+2*x)*(x-487/896)2+5165088340638674452480/10083861556328001*(491/448-2*x)*(x-479/896)2-4620921591365888000/367640785907793*(x-479/896)*(x-487/896)2+1508454554874475264/367640785907793*(x-487/896)*(x-479/896)2 0.5346x0.5435 Sx = 23058430092136939520/3455776494575901*(-235/224+2*x)*(x-52

31、1/896)2+152185638608103800832/18814783137135461*(269/224-2*x)*(x-487/896)2+1508454554874475264/6640511695459569*(x-487/896)*(x-521/896)2+12413145765656442880/6640511695459569*(x-521/896)*(x-487/896)2 0.5435x0.5815 Sx = 1826227663297245609984/23529010298098669*(-513/448+2*x)*(x-537/896)2+204758859218

32、1760229376/23529010298098669*(545/448-2*x)*(x-521/896)2+3103286441414110720/367640785907793*(x-521/896)*(x-537/896)2+1463550859570462208/122546928635931*(x-537/896)*(x-521/896)2 0.5815x0.5993 Sx = 4095177184363520458752/47058020596198213*(-529/448+2*x)*(x-79/128)2+14130205960461516537856/14117406178

33、8594639*(561/448-2*x)*(x-537/896)2+70250441259382185984/5882252574524761*(x-537/896)*(x-79/128)2+65950649484600975360/5882252574524761*(x-79/128)*(x-537/896)2 0.5993x0.6172 Sx = 7065102980230758268928/100503799847543379*(-17/14+2*x)*(x-571/896)2+7766079255031721230336/100503799847543379*(145/112-2*x

34、)*(x-79/128)2+65950649484600975360/7444725914632849*(x-79/128)*(x-571/896)2+55857837321506127872/7444725914632849*(x-571/896)*(x-79/128)2 0.6172x0.6373 Sx = 7766079255031721230336/29778903658531125*(-565/448+2*x)*(x-583/896)2+2785458355130142294016/9926301219510375*(589/448-2*x)*(x-571/896)2+5585783

35、7321506127872/3308767073170137*(x-571/896)*(x-583/896)2+70453716399031435264/3308767073170137*(x-583/896)*(x-571/896)2 0.6373x0.6507五、 效果分析如上：前两图分别为三次样条插值和双三次插值的结果，第三个为两种插值法对比截图； 如上：两图分别为汉字魏的稀疏取点和签名结果截图；5.1效果对比 整体观察，可以发现，三次样条插值的签名比较圆润，而双三次插值的签名比较硬朗。 在前三个图中，从第三个图可以看出：在下面的三个标注的红色圈处，双三次插值效果要比三次样条插值好，而且

36、不难发现，这三个地点都是字母与字母的连接处。双三次插值能够快速实现连接，而样条插值在字母连接处处理较慢。在上面标注的红色圈处可以看出三次样条插值光滑度明显优于双三次插值。从后两个汉字签名图可以观察到：签名点数比较稀疏的情况下，双三次插值能够出色完成签名任务，得到较理想效果，而双三次样条插值字迹比较草，乱，不如双三次插值字迹工整。5.2结果解释在理论分析中，我们已经提到，三次样条插值有二阶光滑度，即二阶导数连续，这是它的优点。当某点与前面点产生较大偏差时，如字母e的顶点与前面w上的点相比偏差过大，三次样条插值算法会找出二阶连续曲线去穿过这点，所以导致它在签名的 字母与字母的过度阶段处理不够直接。

37、而双三次插值不具有二阶导数连续的性质，它对于上述偏差，视而不见，所以能够快速实现字母之间的过度，这是它优点，但同时也是不足之处，它不能签出较圆润的字体。所以，如果做单个字母的签名，建议用三次样条插值算法，做较多字母的签名用双三次插值好些。同时取点稀疏的签名也建议用双三次插值做。六、 附录：程序如下：function out1,out2,out3 = myginput(arg1)%GINPUT Graphical input from mouse.% X,Y = GINPUT(N) gets N points from the current axes and returns % the X-

38、and Y-coordinates in length N vectors X and Y. The cursor% can be positioned using a mouse (or by using the Arrow Keys on some % systems). Data points are entered by pressing a mouse button% or any key on the keyboard except carriage return, which terminates% the input before N points are entered.%

39、X,Y = GINPUT gathers an unlimited number of points until the% return key is pressed.% % X,Y,BUTTON = GINPUT(N) returns a third result, BUTTON, that % contains a vector of integers specifying which mouse button was% used (1,2,3 from left) or ASCII numbers if a key on the keyboard% was used.% Copyrigh

40、t 1984-2004 The MathWorks, Inc.% $Revision: 5.32.4.3 $ $Date: 2004/04/10 23:33:41 $out1 = ; out2 = ; out3 = ; y = ;c = computer;if strcmp(c(1:2),PC) tp = get(0,TerminalProtocol);else tp = micro;endif strcmp(tp,none) & strcmp(tp,x) & strcmp(tp,micro), if nargout = 1, if nargin = 1, out1 = trmginput(arg1); else out1 = trmginput; end elseif nargout = 2 | nargout = 0, if nargin = 1, out1,out2 = t