[理学]多项式插值与最小二乘拟合ppt课件

1、2022-5-51在科学与工程等实际问题中，其数据模型由实验或测量所得到的一批离散数据容易得到。那么，能否通过处理这些数据来建立连续模型呢？从而可以对模型有更全面的认识！下面我们以一维的问题来说明，),( )(baxxfy假设已经得到的离散数据模型(xi互异)xynxxx 10nyyy 10根据寻找策略的不同，我们有插值问题插值问题和最正确平方逼近问题最正确平方逼近问题。为了得到 的更多信息， 我们首先要确定一个函数空间 ，在该函数空间中寻找 的近似函数 。)(xfy )(xfy )(xp插值与逼近插值与逼近引言引言2022-5-52若要求 满足xp)(), 1 , 0( )(niyxpii那

2、么相应的问题称为插值问题插值问题，上述条件称为插值条件插值条件，), 1 , 0( nixi 插值节点； )(min)(02)(02niiixniiiyxyxp那么相应的问题称为离散型最正确平方逼近问题离散型最正确平方逼近问题最小二乘问最小二乘问题题。我们还可以定义对函数 的连续型最佳平方逼近问题！)(xfy px 插值函数，若要求 使得 xp)(2022-5-53定义定义1：设函数组函数组 ，, 2 , 1 , 0| )(nkxk假设向量组, 2 , 1 , 0|)(,),(),(10nkxxxTnkkk线性无关，则称 在点集 上线性无关。 , 2 , 1 , 0| )(nkxk, 2 ,

3、1 , 0|nixi定义定义2：设函数组 ，在a,b上连续，, 2 , 1 , 0| )(nkxk若存在不全为零的数 使得naaa,10bxaxaxaxann, 0)()()(1100则称 在a,b上线性相关，, 2 , 1 , 0| )(nkxk否那么，称为线性无关。假设 中，任何有限个有限个函数在a,b上线性无关，, 2 , 1 , 0| )(kxk则称 为a,b上的线性无关函数系。, 2 , 1 , 0| )(kxk预备知识预备知识2022-5-54u代数代数多项式多项式插值问题插值问题u最小二乘拟合问题最小二乘拟合问题2022-5-55代数代数多项式多项式插值问题插值问题1、概述；2、

4、拉格朗日插值；3、分段插值返回2022-5-561 代数插值概述代数插值概述取函数空间为不超过n阶的多项式集合 ，这样的插值问题称为代数多项式插值问题，即求 ，nnnxp)(), 1 , 0( )(niyxpiinnnnxaxaaxp10)(使得如下插值条件成立nnnnnnnnnyxaxaayxaxaayxaxaa101221000010 插值多项式定理定理1 插值多项式存在并且唯一。证：证：存在性，有唯一解！即即 n+1个插值条件可以唯一确实定一个不超过n阶的插值多项式！唯一性，利用n阶多项式在复数域内至多有n个零点可证！2022-5-57显然以 作为 在插值点插值点 处的近似值是有误差的，

5、记 npx f xx证：证：)()()()()()( 110 xxKxxxxxxxKxRnnn设为零点以 , )( 10nnxxxxR不妨设 ，做函数ixx )()()()()(0nnxtxtxKtptft多项式插值余项定理多项式插值余项定理定理定理2)()()(xpxfxRnn设 在 上连续， 在 内存在，那么 ，有)()(xfn)() 1(xfn,ba, bax),(ba)()!1()()(1) 1(xnfxRnnn其中 且依赖于 ，),( baxbxxxaxxxxxxxnnn10101 ),()()( 插值余项插值余项。2022-5-58为零点，以则 , )( 10nxxxxt由罗尔定理

6、罗尔定理可知， 在(a,b)内至少有一个零点，记作 ，)( )1(tn 即0! )1)()()( )1()1(nxKfnn! )1()()( )1(nfxKn得证！ #其中 且依赖于 ，),(bax注：注：1; )()!1()( , )(max 11xnMxRxfMnnnbxa则若2在实际计算时插值节点应尽量选在插值点x的附近，以使)(1xn尽可能小！3对于不超过不超过n次的多项式次的多项式，其n阶插值多项式就是其本身！返回2022-5-592 拉格朗日拉格朗日Lagrange插值插值定义：定义：), 2 , 1 , 0,( )( , 0)( , 1)(njijijixlij设n次多项式lj(

7、x) 满足),2, 1 ,0( nj那么称之为拉格朗日插值基函数拉格朗日插值基函数。利用待定系数法可得), 1 , 0( )-()-)(-()-()-()-)(-()-( )(11 -011 -0njxxxxxxxxxxxxxxxxxlnjjjjjjnjjj从而可得满足插值条件的插值多项式 )( )(0njjjnxlyxp 拉格朗日插值多项式拉格朗日插值多项式显然， 在 上线性无关。, 2 , 1 , 0|nixi, 2 , 1 , 0| )(nkxlk2022-5-510n线性插值线性插值1111)( , )(kkkkkkkkxxxxxlxxxxxl)()()(111xlyxlyxpkkkk

8、插值基函数：插值多项式：求满足插值条件 的插值多项式，), 1( )(kkiyxpiinn二次插值抛物插值二次插值抛物插值)()()(,)()()(, )()()(11111111111111kkkkkkkkkkkkkkkkkkkkkxxxxxxxxxlxxxxxxxxxlxxxxxxxxxl求满足插值条件 的插值多项式，) 1, 1( )(kkkiyxpiin)()()()(11112xlyxlyxlyxpkkkkkk插值基函数：插值多项式：2022-5-511例例1 数表i0123xi22.12.22.3yi1.41421.44911.48321.5166试用抛物插值求 的近似值。)05.

9、 2(f解解:选取最靠近2.05的节点x0, x1 , x2为插值节点，计算可得4317. 1)05. 2()05. 2(2 pf#问题6：编程实现任意节点的拉格朗日插值多项式的计算，并画出插值节点和插值多项式！返回2022-5-5123 分分 段段 插插 值值5 , 5,11)(2xxxf实例演示：实例演示：取等分节点，分别用n=1,2,4,6,8, 10时的多项式插值函数逼近fx：作图如下：问题7：通过调用编写的拉格朗日插值多项式函数实现本演示实例！2022-5-513我们看到利用多项式插值函数逼近函数fx，n小不行，n大也不行。这种现象我们称为龙格龙格Runge现象现象。这是为什么呢？，

10、)()()!1()()(10)1(nnnxxxxxxnfxR 下面分析多项式插值余项的估计式 1 |fn+1x|的值，常常随n的增加呈指数级增长，比n+1!快得多！2 的值，在 的均值附近比较小，而在边界 的附近随n的增加而增加。 )()()(101nnxxxxxxx nxxx,10nxx、03 当n比较小时，说明在区间a，b内取的节点少，以致于插值多项式缺乏以反映被插函数fx的性态！通常，2022-5-514一分段线性插值一分段线性插值将a,b n等分，在每个小区间xi , xi+1i=0,1,n-1上，作线性插值, ),()()(11111iiiiiiiiiiixxxxfxxxxxfxxx

11、xxs, )()(1iiinxxxxSxp1;,)(baCxpn2)(xpn在每个小区间xi , xi+1上为一个次数不高于1的多项式; 分段函数 易见，3)(,)(xfbaxpn上一致收敛到在可以证明 ，若 则,)(baCxf数值稳定性好计算简单 光滑性差 从而得n分段线性插值的定义分段线性插值的定义2022-5-515分别用n=4,10的分段线性差值逼近函数5 , 5,11)(2xxxfn 数值实验数值实验 作图演示:2022-5-516二三次样条插值二三次样条插值1 sx在每个小区间xi,xi+1 上，是次数不超过三的多项式；23给定：y=fx的数据xi互异n问题的提法问题的提法xynx

12、xx 10nyyy 10确定函数sx,使niyxsii, 2 , 1 , 0,(）,)(02nxxCxs满足1、2的函数sx称为三次样条函数；满足1、2、3的函数sx称为三次样条插值函数。注:插值条件2022-5-517n确定三次样条插值函数的条件确定三次样条插值函数的条件因为三次样条函数sx确实定需要4n个条件，), 1 , 0( )(niyxsii可以确定了4n-2个条件，所以还需补充二个条件边界条件边界条件。由插值条件及连续性条件) 1, 2 , 1( ),0()0( ),0( )0( ),0()0( nixsxsxsxsxsxsiiiiii边界条件有以下三种：1;)( )0( )( )

13、0( 000nnnmxfxsmxfxs，2nnnMxfxsMxfxs)( )0( )( )0( 000，3);0( )0( ),0( )0( ),0()0(000nnnxsxsxsxsxsxs周期性条件自然边条件2022-5-518故 为xi,xi+1上的线性函数，)( xsn确定三次样条插值函数的三弯矩法确定三次样条插值函数的三弯矩法设设 ，), 1 , 0()( niMxsiisx在区间xi,xi + 1i=0,1,n-1内为三次多项式，且 ， ),()(02nxxCxs有则, 1iixxx)( )( 111iiiiiiiiixxhhxxMhxxMxs iiiiiiiiiiiiiiiihx

14、xhMyhxxhMyhxxMhxxMxs)6( )6(6)(6)()(211123131对 进行两次不定积分，并由插值条件可得)( xs1 )1( )()( i,ikyxsMxskkkk满足由插值条件确定三次样条函数由插值条件确定三次样条函数2022-5-519iiiiiiiiiiiihMMhyyhxxMhxxMxs6)( 2)(2)()( 112121iiiiiiiixxihMMhyyhMxsi6)( 21lim)0(11当 时，,1iixxx111116)( 21lim)0(iiiiiiiixxihMMhyyhMxsi所以11 2iiiiiiMMMd ),()(02可得由nxxCxs)0(

15、)0(iixsxs) 1, 2 , 1(ni)(61111iiiiiiiiihyyhyyhhd ,11iiiihhh,1 ii 其中2*推导三弯矩方程推导三弯矩方程2022-5-520),( )( 00nnxfMxfM，)( )0( ),( )0( 00nnxfxsxfxs再由边界条件可得从而可以由(*)式求得 ，121,nMMM代入sx的表达式可得三次样条插值函数。3结合边界条件求解三弯矩方程结合边界条件求解三弯矩方程2022-5-521构成方程组构成方程组1)1, 2 , 1( 211 n-idMMMiiiiii)( )( 00nnxfMxfM，综上所述，可得构造三次样条插值函数的综上所述

16、，可得构造三次样条插值函数的算法如下算法如下：由dAM ,),(11TnMMM可得三对角方程组其中,),(11Tnddd2221221nnA注：注：矩阵A和向量d中元素的计算表达式见前面*式！ 三弯矩方程三弯矩方程2用追赶法求解上述三对角方程组，求得M，从而可得三次样条插值函数sx2022-5-522注：注：设 ，), 1 , 0()( nimxsii在小区间xi,xi+1i=0,1,n-1上由Hermite插值，可得三次插值函数six，从而可得三次样条插值函数sx，利用连续性条件), 2 , 1( )0( )0( nixsxsii再结合边界条件)( ) 0( ),( ) 0( 00nnxfx

17、sxfxs可得关于 三对角方程组(三转角方程组)！) 1, 2 , 1(nimi三转角法三转角法返回2022-5-523最小二乘拟合最小二乘拟合1、问题的提出；2、线性最小二乘拟合；3、线性最小二乘拟合的求法。返回2022-5-524问题的提出：问题的提出： 在实际问题中，往往会通过实验观测观测积累了一组数据，xi,yi,i=1,m，一般来说m比较大，如何从这批实验数据出发，寻求一近似函数 Px来逼近这组数据后面隐藏的函数关系 y=fx。事实上，由于观测数据数目较大数据数目较大，又往往带有观测带有观测误差误差，对于这类问题运用插值函数来逼近 y=fx 往往是不适当的！可不可以用插值函数来逼近呢

18、？可不可以用插值函数来逼近呢？返回2022-5-525线性无关，关于点集函数组), 1(), 2 , 1)(mixnixii12*( ),()nnpxspannm 线性最小二乘拟合线性最小二乘拟合已知一组离散数据 ，), 2 , 1)(,(miyxii使得要求一个函数mkkkHpmkkkyxpyxpn1212)(min)(*显然p*x可以表示成niiixcxp1)(*)(*下面考虑如何求系数 ！), 2 , 1(*nici返回2022-5-526线性最小二乘拟合的求法线性最小二乘拟合的求法记niiixcxp1)()(考虑多元函数221111( ,)()()mmnnkkjjkkkkjI ccp

19、xycxy 为了求得p*x，只需求多元函数 的极小值点即可！),(1nccI由多元函数极值的必要条件), 2 , 1( 0),(1nicccIin可得), 2 , 1( )()()(111nixycxxmkkiknjjmkkjki 2022-5-527), 2 , 1,( )( , )()(11njixybxxgmkkikimkkjkiij假设记那么有TnTnijcccbbbgG,),(11其中bGc 法方程或正规方程容易验证AAGT其中nmmnmnxxxxA)()()()(1111注：注：2022-5-528niiixcxp1)(*)(* 可以证明法方程存在唯一解 。), 2 , 1(*nicimkkkyxp12)(*称为最小二乘拟合和的误差平方和