插值与最小二乘法

插值与最小二乘法（拟合）1《数值分析》主讲教师æ问题的提出

设某个未知函数关系y=f(x)的一些测量值列表如下:x11.523y2.33.4-1.75.6那么对

,(i=0,1,2,...,n)应该如何估值

2《数值分析》主讲教师内插法肇始于<周髀算经>中关于晷长的计算,后经东汉、隋、唐、元等朝代天文学家在日、月、五星的运行测量和计算中逐步得到发展.元代郭守敬的平立定三差法(招差法)标志着中国古代历法计算从二次到高次插值方法的演变.通过中外比较,有些成果比西方国家早400～1000年.

3《数值分析》主讲教师等距节点内插公式是由我国隋朝数学家刘焯(公元544-610年)首先提出的;

不等距节点内插公式是由我国唐朝数学家张遂(公元683-727年)提出的;

比西欧学者发表相应结果早一千余年.历史4《数值分析》主讲教师●问题的解决---插值方法概述寻求较简单的连续函数(x)，使它在给定的n+1个点满足测量值，在其他点处估计未知函数值。若将连续函数(x)取为多项式函数，则称为多项式(Polynomial)插值Pn(x)；当然还有三角插值、有理插值等形式。5《数值分析》主讲教师插值与最小二乘法§1插值问题与插值多项式§2Lagrange插值§3均差与Newton插值公式§4差分与Newton前后插值公式§5Hermite插值§6分段低次插值§7三次样条插值§8曲线拟合的最小二乘法6《数值分析》主讲教师§1插值问题与插值多项式7《数值分析》主讲教师多项式插值有着简单、应用广泛、实用的特点，并且有较完备的理论体系。因此本课主要介绍多项式插值。8《数值分析》主讲教师9《数值分析》主讲教师10《数值分析》主讲教师§2Lagrange多项式插值§2.1线性插值与二次插值---导引§2.2Lagrange插值多项式§2.3插值余项与误差估计11《数值分析》主讲教师§2.1线性插值与二次插值12《数值分析》主讲教师§2.1线性插值与二次插值13《数值分析》主讲教师§2.2Lagrange插值多项式14《数值分析》主讲教师15《数值分析》主讲教师§2.3插值余项与误差估计前面的Cramer方法和该定理表明了插值多项式的唯一性。两插值函数在n+1个点上函数值相同，故两多项式相同。16《数值分析》主讲教师17《数值分析》主讲教师18《数值分析》主讲教师19《数值分析》主讲教师开始输入X（xi,yi）i=0,1,…,n0:=y0：=k1:=t(x-xj)/(xk-xj)*t:=tj=0,…,k-1,k+1,….ny+t*yk:=yK=n?不等K+1:=k等于输出y结束20《数值分析》主讲教师§3Newton插值公式与均差（差商）21《数值分析》主讲教师22《数值分析》主讲教师23《数值分析》主讲教师24《数值分析》主讲教师25《数值分析》主讲教师26《数值分析》主讲教师27《数值分析》主讲教师Newton均差（差商）表28《数值分析》主讲教师关于k用数学归纳法证明（举例说明三阶差商）。29《数值分析》主讲教师30《数值分析》主讲教师31《数值分析》主讲教师32《数值分析》主讲教师33《数值分析》主讲教师34《数值分析》主讲教师Newton插值和均差的另一种形式推导*35《数值分析》主讲教师Newton插值和均差的另一种形式推导*36《数值分析》主讲教师Newton插值和均差的另一种形式推导*37《数值分析》主讲教师三种多项式插值的关系*现已学的三种多项式插值方法：（1）直接（Cramer）法（2）Lagrange法（3）Newton法无非是选用了Pn[x]不同的基底，所获的插值多项式是一样的。38《数值分析》主讲教师§4Hermite插值

---带导数条件的多项式插值39《数值分析》主讲教师40《数值分析》主讲教师41《数值分析》主讲教师42《数值分析》主讲教师43《数值分析》主讲教师44《数值分析》主讲教师45《数值分析》主讲教师正如Lagrange插值的弱点，也应有Newton型Hermite插值。46《数值分析》主讲教师误差估计47《数值分析》主讲教师5Hermite插值---多点情形48《数值分析》主讲教师49《数值分析》主讲教师50《数值分析》主讲教师多点Hermite多项式插值误差估计51《数值分析》主讲教师证明：52《数值分析》主讲教师Hermite插值的两个性质 53《数值分析》主讲教师6分段低次插值§5.6.1多项式插值的收敛性问题（Runge现象）§5.6.2分段线性插值§5.6.3分段三次Hermite插值§5.6.4三次样条插值54《数值分析》主讲教师6.1多项式插值收敛性问题前面介绍了n+1个插值节点上构造不超过n次的插值多项式的方法，并分析了它们的余项，从余项的表达式看到，插值多项式与被插函数逼近的程度是与分点的数目、位置及被插函数的特性有关。考虑如下问题：是否插值节点越多，插值多项式对函数的逼近程度就越好呢？——龙格现象55《数值分析》主讲教师56《数值分析》主讲教师6.2分段线性插值多项式插值虽有许多优点，但由于多项式“在一点的性质足以决定其整体性质”的特点，难以描述自然界“在不同的区域内的性状可以完全不相关”的大范围现象，如Runge现象；因此高次插值收敛性没有保证，实际的计算稳定性也没保证。故当插值节点n较大时通常不采用高次多项式插值，而改用低次分段插值。57《数值分析》主讲教师58《数值分析》主讲教师59《数值分析》主讲教师利用Lagrange插值基底的思想60《数值分析》主讲教师证明：逐段应用Lagrange插值的误差估计。61《数值分析》主讲教师6.3分段三次Hermite插值62《数值分析》主讲教师63《数值分析》主讲教师利用Lagrange插值基底的思想64《数值分析》主讲教师65《数值分析》主讲教师66《数值分析》主讲教师67《数值分析》主讲教师§7三次样条插值三次样条函数

三弯矩方程三次样条插值收敛性68《数值分析》主讲教师

7.1三次样条函数（Spline）由于分段线性插值和分段Hermite插值的光滑性不够（例如船体放样、飞机的外形曲线设计常需二阶可导），况且节点处的导数值难以获得。下面介绍的样条仍是一种分段多项式，各相邻段将具有更高阶光滑连接性质，因而它既保持了多项式的简单性，又保持了各段相对独立的局部性质和整体光滑性。69《数值分析》主讲教师样条函数70《数值分析》主讲教师三次样条函数的求法（三弯矩方程）71《数值分析》主讲教师三次样条函数的求法（三弯矩方程）72《数值分析》主讲教师三次样条函数的求法（三弯矩方程）73《数值分析》主讲教师三次样条函数的求法（三弯矩方程）74《数值分析》主讲教师三次样条函数的求法（三弯矩方程）75《数值分析》主讲教师7.2三弯矩方程组的定解条件76《数值分析》主讲教师77《数值分析》主讲教师78《数值分析》主讲教师79《数值分析》主讲教师例80《数值分析》主讲教师81《数值分析》主讲教师82《数值分析》主讲教师83《数值分析》主讲教师EX:Anaturalcubicspline

s(x)on[1,3]whichinterpolates(2,1),(3,0)isdefinedby（1）Find

b,D,d;(2)UseLagrangeorNewtoninterpolatingpolynomialsof2-degreetoapproximate

s(1.5)

fromthedata:

s(1),s(2),s(3);%(3)Findtheleastsquarepolynomialoforder1fromthedata

s(1),s(2),s(3).Solution:(1)b=--1/2,D=1/4,d=1/4,thus:s(1)=1,s(2)=1,s(3)=0,(2)

,(3)Assumep(x)=ax+b,thenobtainthenormalequations,solveitgivesa=-0.5,b=5/3,sop(x)=-0.5x+5/3.84《数值分析》主讲教师7.3三次样条插值收敛性85《数值分析》主讲教师8曲线拟合的最小二乘法86《数值分析》主讲教师线性函数拟合87《数值分析》主讲教师88《数值分析》主讲教师89《数值分析》主讲教师90《数值分析》主讲教师i12345xiyi165