（精选幻灯片）插值法：原理与应用.ppt

插值法：原理与应用,ZhenhuaSong,1,插值的背景,1.只有n个点处的函数值希望找到一条通过这些点的曲线（连续、光滑）2.函数太麻烦，近似简化找到一个好计算的函数，近似代替3.用多项式代替多项式方便求值、求导、积分等,2,2020/5/17,插值&逼近&拟合,0.给定n个不同的点，构造曲线1.插值：曲线依次通过n个点2.逼近：曲线最接近n个点（接近：在某种意义下）例：最小二乘法3.拟合：插值+逼近,3,2020/5/17,泰勒展开,在某一点x0处展开只在x0处近似性较好远离x0的点误差较大需要n个点近似性较好插值可以胜任,4,2020/5/17,一次插值,用一次函数近似表示,5,2020/5/17,二次插值,用二次函数来表示,6,2020/5/17,多项式插值：示例,给定的n+1个不同的点找到一个n次多项式，依次通过这n+1个点n次多项式必然唯一,7,2020/5/17,多项式插值：唯一性,设n次多项式为=0+1+22+在这n+1个点上，满足n+1个方程0=0+10+202+01=0+11+212+12=0+12+222+2=0+1+22+,8,2020/5/17,多项式插值：唯一性,把上述线性方程组写成矩阵形式10020111211222212012=012系数矩阵行列式不为0：范德蒙行列式，0到互不相同方程组解唯一多项式系数唯一插值多项式唯一,9,2020/5/17,拉格朗日插值,一种多项式插值算法n次多项式不用求解线性方程组基函数线性组合=0,0+1,1+,+,0,1,称为基函数,10,2020/5/17,拉格朗日插值：2点情形,1=01,0+11,1我们希望通过0,0,1,1这2个点可以取1,00=1,1,10=01,01=0,1,11=1.这样，10=01,00+11,11=0，11=01,01+11,11=1如何实现上述条件？,11,2020/5/17,基函数的构建：2点情形,条件：1,00=1,1,10=01,01=0,1,11=1.构造一次多项式构造：1,0=101,1,1=010分子是一次多项式满足1,=0的条件分母是系数，满足1,=1=的条件实质：=+的直线,12,2020/5/17,基函数的构建：n+1点情形,条件：1,=0,1,=1=构造n次多项式构造：,=011+1011+1注意，分子没有，分母没有符合条件约束实质：每个基函数都是n次多项式,13,2020/5/17,拉格朗日插值：n+1点情形,插值函数：=0,0+1,1+,+,基函数：,=011+1011+1简洁形式：=00,0=00=0,14,2020/5/17,拉格朗日插值：误差估计,拉格朗日是一种近似，存在误差。对于近似代替函数的情形。误差分析：=+误差项如果+1,误差项=+1+1!=0,15,2020/5/17,拉格朗日插值：示例,对=1/在0=2,1=2.75,2=4插值,16,2020/5/17,Nevile迭代插值,对于给定的n+1个点0,1,通过递推求出n次插值多项式设1,2,是的不同自然数1,2,是定义在1,2,17,2020/5/17,Nevile迭代插值,对于给定的k+1个点0,1,插值多项式在k+1个点上在除去点j的k个点上的插值多项式在除去点i的k个点上的插值多项式=,18,2020/5/17,Nevile迭代插值,0,1,0,1,2,3,1,2,2,3,0,1,2,1,2,3,0,1,2,3,19,2020/5/17,牛顿差商插值,n次多项式写成多项式和：=0+10+201+011确定系数，可确定插值多项式经过n+1个点确定唯一n次多项式系数可以由差分确定,20,2020/5/17,牛顿差商插值：系数确定,多项式：=0+10+201+011取值：0=0=01=1=0+1101=10101为差分形式所有系数都可以写成差商形式定义符号：,21,2020/5/17,牛顿差商插值：系数确定,定义符号：=零阶差商,+1=+1+1一阶差商,+1,+2=+1,+2,+1+2二阶差商,+1,+2,+=+1,+2,+,+1,+1+k阶差商在0处差分：0=0=0,0,1=10处阶差分=,22,2020/5/17,牛顿差商插值：公式导出,=0+=10,1,2,=01定义符号：=零阶差商,+1=+1+1一阶差商,+1,+2=+1,+2,+1+2二阶差商,+1,+2,+=+1,+2,+,+1,+1+k阶差商,23,2020/5/17,牛顿差商插值：系数求解,0,1,2,3,0,1,1,2,2,3,0,1,2,1,2,3,0,1,2,3,24,2020/5/17,牛顿差商插值：间距相等,当n+1个点等距排列时：设=+1=0+插值多项式变形：=0+=10,1,2,=01其中=0+0+=01=01,25,2020/5/17,牛顿差商插值：间距相等,变形处理：=01=01组合数=!定义广义组合数=1+1!=01!广义组合数：s可以是任意实数.=01=!=0+=10,1,2,!,26,2020/5/17,牛顿差商插值：反向差商,之前，当n+1个点等距排列时：设=+1=0+对于反向差分：=+多项式形式与=0+类似。,27,2020/5/17,Hermite插值,拉格朗日插值缺点在n+1个点处与值相同导数等不同目的：找到一个多项式函数不光函数值相同k阶导数相同数学语言：=,=0,1,28,2020/5/17,拉格朗日插值缺点,插值多项式形状、走向差异较大,29,2020/5/17,Hermite插值：优势,只取1个点时：取m阶导数信息，相当于泰勒展开取n+1个点时：不考虑导数信息，相当于拉格朗日插值具有更广泛的应用生成的Hermite插值多项式唯一在n+1个点，第i个点阶导数相同,30,2020/5/17,Hermite：一阶导数相同,在n+1个点处函数值相同，切线相同需要2n+1阶多项式条件：1,0,1,2,思想：与拉格朗日基函数思想相似,31,2020/5/17,Hermite：一阶导数相同,2+1=0,+=0,当=时，为了保证2+1=,令,=1,=0,=0,=0.为了保证2+1=,令,=0,=0令,=1,=0,32,2020/5/17,Hermite:一阶导数相同,2+1=0,+=0,其中，,=12,2,=,2,为拉格朗日基函数（第j个，n次多项式）,33,2020/5/17,回忆拉格朗日基函数,插值函数：=0,0+1,1+,+,基函数：,=011+1011+1基函数,性质在处值为0，在处值为1.,34,2020/5/17,Hermite：其他,误差分析如果2+2,=2+1+0222+222+2后面即为误差项.也可以用差分形式表达形式与n次多项式牛顿差分类似并不是次数越高越精确误差反而可能变大,35,2020/5/17,三次样条插值：背景,给定n+1个点0,0,，012分成n段，每一段：是一个分段函数在0,处，分段函数取值为尽可能保持光滑,36,2020/5/17,线段连接：粗糙,相邻两点用线段连接形成折线，不够光滑,37,2020/5/17,三次样条插值：特性,每一段,+1用3次多项式表示=,+1=+1.或者说+1=+1+1分段函数在+1处连续暂不考虑分段函数两端的情况+1=+1+1.分段函数在+1处一阶导数相同+1=+1+1.分段函数在+1处二阶导数相同具有较好的光滑性,38,2020/5/17,三次样条插值：边界,对于两端点，处理如下：00=0,=00=0,=0.,39,2020/5/17,三次样条插值：构建,对于某一段,（不考虑端点）设=+2+3+2+3=处函数值相同+1+12+13=+1+1处函数值相同+1+2+1+3+12=+1+1+2+1+1+3+1+12+1两端一阶导数值相同2+6+1=2+1+6+1+1+1两端二阶导数值相同,40,2020/5/17,三次样条插值：构建,所有条件，可以组成线性方程组=,为稀疏矩阵求解线性方程组，得到唯一解三次样条缺点：估计误差不方便,41,2020/5/17,三次样条插值：应用,=,0=0,1=1,2=2,3=3,42,2020/5/17,改变某一个点,43,2020/5/17,改变某一个点：对比,多项式插值：牵一发动全身，整个多项式都变了三次样条插值：在附近有较大影响，远离处影响不大,44,2020/5/17,多项式插值：对比,45,2020/5/17,参数曲线,对于n+1个点0,0,1,1,+1满足参数方程以为参数=,=n+1个点对应n+1个参数取值：012,46,2020/5/17,参数曲线：图像,47,2020/5/17,三次参数曲线：定义,输入：点0,0,1,10,0处切线上某点0+0,0+01,1处切线上某点1+1,1+1输出=是t的3次函数,=是t的3次函数.0=0,0=01=1,1=1输出三次参数曲线唯一,48,2020/5/17,三次参数曲线：构造,设=0+1+22+33=0+1+22+33满足条件0=0=0,0=0=01=1=0+1+2+31=1=0+1+2+30=0,1=1,0=0,0=0方程解唯一存在8个未知量，8个方程,49,2020/5/17,三次函数曲线：图像,50,2020/5/17,Bezier曲线,n+1个点分