计算方法曲线拟合

计算方法曲线拟合第一页，共十六页，编辑于2023年，星期五1.4OrthogonalPolynomialsL-SApproximation则称0(x),1(x),…,n(x)是关于点集{xi}的正交函数族/*orthogonalfunctions

*/。如果k(x)都是多项式时，就称之为关于点集{xi}的正交多项式/*orthogonal

polynomials

*/。对于点集{xi}(i=1,2,…,m)，若一组函数0(x),1(x),…,n(x)(n<m)满足条件定义第二页，共十六页，编辑于2023年，星期五构造正交多项式1.4OrthogonalPolynomialsL-SApproximation定理对于给定的点集{xi}(i=1,2,…,m)，递推公式构造的函数族0(x),1(x),…,n(x)是关于{xi}的一组正交多项式，且k(x)(k=0,1,…,n)是k次多项式，其最高项xn的系数为1。注：构造的次序是：

证明略…第三页，共十六页，编辑于2023年，星期五例：用来拟合。解：通过正交多项式0(x),1(x),2(x)求解设)()()(221100xaxaxayjjj++=1)(0=xj229),(),(0000==jjjya25),(),(00001==jjjjax25)()()(011-=-=xxxxjaj537),(),(1111==jjjya25),(),(11112==jjjjax45),(),(00111==jjjjb55)(45)()25()(2012+-=--=xxxxxxjjj21),(),(2222==jjjya1.4OrthogonalPolynomialsL-SApproximation第四页，共十六页，编辑于2023年，星期五程序设计uk+1,vk

,pi

,

qi

,

s1,

s0

1.4OrthogonalPolynomialsL-SApproximation第五页，共十六页，编辑于2023年，星期五程序设计(续)1.4OrthogonalPolynomialsL-SApproximation第六页，共十六页，编辑于2023年，星期五§2最佳一致逼近

/*Optimal

UniformApproximation*/

对于一组数据(xi,yi),i=1,2,…,m,要求在某个函数类

(n<<m)中构造一个函数，使得最大偏差最小，即ak在I的极值点引入变量D，则最大偏差最小化问题可归结为以下问题：

besubjectedto以…为条件线性规划问题

linearprogramming第七页，共十六页，编辑于2023年，星期五§2Optimal

UniformApproximation

线性规划规划变量

programming

variables目标函数

objectivfunction(线性)约束方程

constraintequations单纯形法、有效集法

第八页，共十六页，编辑于2023年，星期五§2Optimal

UniformApproximation

解仍然采用线性拟合φ(x)=a0+a1x。相应的线性规划问题为：例某种铝合金的含铝量为x(%)，熔解温度为y(oC)，由实验测得的数据如下表。试用最佳一致逼近建立x与y之间的经验公式。

xi36.946.763.777.884.087.5yi181197235270283292规划变量为a0,a1,D用单纯法解得：a0=96.4886,a1=2.2132,D=2.8450,故有就

φ(x)=96.4886+2.2132x最小二乘法xi36.946.763.777.884.087.5φ(xi)178.16199.85237.47268.68282.40290.14δi-2.852.852.47-1.32-0.60-1.86拟合方法均方误差最大偏差最小二乘法5.163.22最佳一致逼近6.282.85第九页，共十六页，编辑于2023年，星期五§2Optimal

UniformApproximation

例某圆形工件圆周上的测量数据为(xi,yi),i=1,2,…,m，求该工件的圆心坐标和半径。

为了确定待定量x0,y0

和r，让最大偏差最小化：

设(x0’,y0’)是理想圆心坐标的近似值，把偏差表达式在x0’,y0’附近展成泰勒级数，并取线性项得到

解由于加工误差存在，工件轮廓非标准圆。设理想圆的圆心坐标为(x0,y0),半径为r，则测点到理想圆的偏差为It’seasythatthecirclecanbedeterminedthroughanythreepoints这是个非线性优化问题，求解较困难，需线性化。

第十页，共十六页，编辑于2023年，星期五§2Optimal

UniformApproximation

用单纯形法或有效集法解出规划变量Δx、Δy、r和D，便有x0=x0’+Δx,y0=y0’+Δy和r

，问题得解。设D=于是有如下线性规划问题：第十一页，共十六页，编辑于2023年，星期五§2OrthogonalPolynomials&L-SApproximation

Algorithm:OrthogonalPolynomialsApproximation

Toapproximateagivenfunctionbyapolynomialwitherrorboundedbyagiventolerance.Input:numberofdatam;x[m];y[m];weightw[m];toleranceTOL;maximumdegreeofpolynomialMax_n.Output:coefficientsoftheapproximatingpolynomial.Step1Set0(x)

1;a0=(0,y)/(0,0);P(x)=a00(x);err=(y,y)a0(0,y);Step2Set1=

(x0,0)/(0,0);1(x)

=(x1)0(x);

a1=(1,y)/(1,1);P(x)+=a11(x);err

=a1(1,y);Step3Setk=1;Step4While((k<Max_n)&&(|err|TOL))dosteps5-7

Step5k++;

Step6k=

(x1,1)/(1,1);k1=(1,1)/(0,0);

2(x)

=(xk)1(x)k10(x);ak

=(2,y)/(2,2);

P(x)+=ak

2(x);err

=ak

(2,y);

Step7Set0(x)=1(x);1(x)=2(x);Step8Output();STOP.注：第十二页，共十六页，编辑于2023年，星期五

AnothervonNeumannquote:Youngman,inmathematicsyoudon'tunderstandthings,youjustgetusedtothem.HW:p.152#1§2OrthogonalPolynomials&L-SApproximationLab12.OrthogonalPolynomialsApproximationGivenafunctionfandasetof200

m>0distinctpoints.YouaresupposedtowriteafunctionvoidOPA(double(*f)(),doublex[],doublew[],intm,doubletol,FILE*outfile)toapproximatethefunctionfbyanorthogonalpolynomialusingtheexactfunctionvaluesatthegivenmpointsx[].Thearrayw[m]containsthevaluesofaweightfunctionatthegivenpointsx[].Thetotalerrormustbenolargerthantol.第十三页，共十六页，编辑于2023年，星期五§2OrthogonalPolynomials&L-SApproximationInputThereisnoinputfile.Instead,youmusthandinyourfunctionina*.hfile.Theruleofnamingthe*.hfileisthesameasthatofnamingthe*.cor*.cppfiles.Output(representsaspace)Foreachtestcase,youaresupposedtooutputthefollowinginformation:

The1stlinecontainstheinteger6

n>0whichisthedegreeofthepolynomialintheformat:

fprintf(outfile,"%d\n",n);

The2ndlinecontainsthen+1coefficientsoftheapproximationpolynomialwhere.EachofthecoefficientistobeprintedasinCprintf:fprintf(outfile,"%8.4e",coefficient);

The3rdlinecontainsthetotalerrorintheformat:fprintf(outfile,"error=%12.8e\n",err);Note:Ifthetotalerrorisstillnotsmallenoughwhenn=6,simplyoutputtheresultobtainedwhenn=6.Theoutputsoftwotestcasesmustbeseperatedbyablankline.第十四页，共十六页，编辑于2023年，星期五§2OrthogonalPolynomials&L-SApproximationSampleJudgeProgram#include<stdio.h>#include<math.h>#defineMAX_m200#defineMAX_n6#include"98115001_12.h"

doublef1(doublex){returnsin(x);}

doublef2(doublex){returnexp(x);}

voidmain(){FILE*outfile