拉格朗日插值法

对某个多项式函数,已知有给定的k   1个取值点:

其中

  对应着自变量的位置,而

  对应着函数在这个位置的取值。

假设任意两个不同的xj都互不相同,那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为:

其中每个

  为拉格朗日基本多项式(或称插值基函数),其表达式为:

  [3]

拉格朗日基本多项式

  的特点是在

  上取值为1,在其它的点

  上取值为0。

范例

假设有某个二次多项式函数

  ,已知它在三个点上的取值为:

要求

  的值。

首先写出每个拉格朗日基本多项式:

然后应用拉格朗日插值法,就可以得到

  的表达式(

  为函数

  的插值函数):

此时代入数值

  就可以求出所需之值:

  。

证明

存在性

对于给定的k 1个点:

  ,拉格朗日插值法的思路是找到一个在一点

  取值为1,而在其他点取值都是0的多项式

  。这样,多项式

  在点

  取值为

  ,而在其他点取值都是0。而多项式

  就可以满足

在其它点取值为0的多项式容易找到,例如:

它在点

  取值为:

  。由于已经假定

  两两互不相同,因此上面的取值不等于0。于是,将多项式除以这个取值,就得到一个满足“在

  取值为1,而在其他点取值都是0的多项式”:

这就是拉格朗日基本多项式。

唯一性

次数不超过k的拉格朗日多项式至多只有一个,因为对任意两个次数不超过k的拉格朗日多项式:

  和

  ,它们的差

  在所有k 1个点上取值都是0,因此必然是多项式

  的倍数。因此,如果这个差

  不等于0,次数就一定不小于k 1。但是

  是两个次数不超过k的多项式之差,它的次数也不超过k。所以

  ,也就是说

  。这样就证明了唯一性[4]。

几何性质

拉格朗日插值法中用到的拉格朗日基本多项式

  (由某一组

  确定)可以看做是由次数不超过n的多项式所组成的线性空间:

  的一组基底。首先,如果存在一组系数:

  使得,

  ,

那么,一方面多项式P是满足

  的拉格朗日插值多项式,另一方面P是零多项式,所以取值永远是0。所以

  。

这证明了

  是线性无关的。同时它一共包含n 1个多项式,恰好等于

  的维数。所以

  构成了

  的一组基底。

拉格朗日基本多项式作为基底的好处是所有的多项式都是齐次的(都是n次多项式)。

优点与缺点

拉格朗日插值法的公式结构整齐紧凑,在理论分析中十分方便,然而在计算中,当插值点增加或减少一个时,所对应的基本多项式就需要全部重新计算,于是整个公式都会变化,非常繁琐[5]。这时可以用重心拉格朗日插值法或牛顿插值法来代替。此外,当插值点比较多的时候,拉格朗日插值多项式的次数可能会很高,因此具有数值不稳定的特点,也就是说尽管在已知的几个点取到给定的数值,但在附近却会和“实际上”的值之间有很大的偏差(如右下图)[6]。这类现象也被称为龙格现象,解决的办法是分段用较低次数的插值多项式。

重心拉格朗日插值法

重心拉格朗日插值法是拉格朗日插值法的一种改进。在拉格朗日插值法中,运用多项式

拉格朗日插值法的数值稳定性:如图,用于模拟一个十分平稳的函数时,插值多项式的取值可能会突然出现一个大的偏差(图中的14至15中间)

可以将拉格朗日基本多项式重新写为:

定义重心权[7][8]

上面的表达式可以简化为:

于是拉格朗日插值多项式变为:

即所谓的重心拉格朗日插值公式(第一型)或改进拉格朗日插值公式。它的优点是当插值点的个数增加一个时,将每个

  都除以

  ,就可以得到新的重心权

  ,计算复杂度为

  ,比重新计算每个基本多项式所需要的复杂度

  降了一个量级。

将以上的拉格朗日插值多项式用来对函数

  插值,可以得到:

因为

  是一个多项式。

因此,将

  除以

  后可得到:

  [7]

这个公式被称为重心拉格朗日插值公式(第二型)或真正的重心拉格朗日插值公式。它继承了(1)式容易计算的特点,并且在代入x值计算

  的时候不必计算多项式

  [7]。它的另一个优点是,结合切比雪夫节点进行插值的话,可以很好地模拟给定的函数,使得插值点个数趋于无穷时,最大偏差趋于零[7]。同时,重心拉格朗日插值结合切比雪夫节点进行插值可以达到极佳的数值稳定性。第一型拉格朗日插值是向后稳定的,而第二型拉格朗日插值是向前稳定的,并且勒贝格常数很小[9]。

参考来源

^ E. Waring. Problems Concerning Interpolations. Philosophical Transactions of the Royal Society of London. 1779, 69: 59–67.

^ (英文)E. Meijering. A chronology of interpolation: From ancient astronomy to modern signal and image processing,. Proceedings of the IEEE: 323.

^ (英文)Julius Orion Smith III. Lagrange_Interpolation. Center for Computer Research in Music and Acoustics (CCRMA), Stanford University.

^ 冯有前,《数值分析》,第63页

^ 李庆扬,《数值分析》第4版,第31页

^ 冯有前,《数值分析》,第64页

^ 7.0 7.1 7.2 7.3 Jean-Paul Berrut, Lloyd N. Trefethen. Barycentric Lagrange Interpolation. SIAM Review. 2004, 46 (3): 501–517.doi:10.1137/S[**************]5.

^ 王兆清,李淑萍,唐炳涛. 一维重心型插值:公式、算法和应用. 山东建筑大学学报. 2007, 22 (5): 447–453.

^ NICHOLAS J. HIGHAM. The numerical stability of barycentric Lagrange Interpolation. IMA Journal of Numerical Analysis. 2004, 24 (4): 547–556.

(中文)李庆扬,王能超,易大义. 《数值分析》第4版. 清华大学出版社. 2001. ISBN 7-302-04561-5.

(中文)冯有前. 《数值分析》. 清华大学出版社. 2001. ISBN 7-810-82495-3.

(中文)拉格朗日插值多项式. 太原理工大学.

对某个多项式函数,已知有给定的k   1个取值点:

其中

  对应着自变量的位置,而

  对应着函数在这个位置的取值。

假设任意两个不同的xj都互不相同,那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为:

其中每个

  为拉格朗日基本多项式(或称插值基函数),其表达式为:

  [3]

拉格朗日基本多项式

  的特点是在

  上取值为1,在其它的点

  上取值为0。

范例

假设有某个二次多项式函数

  ,已知它在三个点上的取值为:

要求

  的值。

首先写出每个拉格朗日基本多项式:

然后应用拉格朗日插值法,就可以得到

  的表达式(

  为函数

  的插值函数):

此时代入数值

  就可以求出所需之值:

  。

证明

存在性

对于给定的k 1个点:

  ,拉格朗日插值法的思路是找到一个在一点

  取值为1,而在其他点取值都是0的多项式

  。这样,多项式

  在点

  取值为

  ,而在其他点取值都是0。而多项式

  就可以满足

在其它点取值为0的多项式容易找到,例如:

它在点

  取值为:

  。由于已经假定

  两两互不相同,因此上面的取值不等于0。于是,将多项式除以这个取值,就得到一个满足“在

  取值为1,而在其他点取值都是0的多项式”:

这就是拉格朗日基本多项式。

唯一性

次数不超过k的拉格朗日多项式至多只有一个,因为对任意两个次数不超过k的拉格朗日多项式:

  和

  ,它们的差

  在所有k 1个点上取值都是0,因此必然是多项式

  的倍数。因此,如果这个差

  不等于0,次数就一定不小于k 1。但是

  是两个次数不超过k的多项式之差,它的次数也不超过k。所以

  ,也就是说

  。这样就证明了唯一性[4]。

几何性质

拉格朗日插值法中用到的拉格朗日基本多项式

  (由某一组

  确定)可以看做是由次数不超过n的多项式所组成的线性空间:

  的一组基底。首先,如果存在一组系数:

  使得,

  ,

那么,一方面多项式P是满足

  的拉格朗日插值多项式,另一方面P是零多项式,所以取值永远是0。所以

  。

这证明了

  是线性无关的。同时它一共包含n 1个多项式,恰好等于

  的维数。所以

  构成了

  的一组基底。

拉格朗日基本多项式作为基底的好处是所有的多项式都是齐次的(都是n次多项式)。

优点与缺点

拉格朗日插值法的公式结构整齐紧凑,在理论分析中十分方便,然而在计算中,当插值点增加或减少一个时,所对应的基本多项式就需要全部重新计算,于是整个公式都会变化,非常繁琐[5]。这时可以用重心拉格朗日插值法或牛顿插值法来代替。此外,当插值点比较多的时候,拉格朗日插值多项式的次数可能会很高,因此具有数值不稳定的特点,也就是说尽管在已知的几个点取到给定的数值,但在附近却会和“实际上”的值之间有很大的偏差(如右下图)[6]。这类现象也被称为龙格现象,解决的办法是分段用较低次数的插值多项式。

重心拉格朗日插值法

重心拉格朗日插值法是拉格朗日插值法的一种改进。在拉格朗日插值法中,运用多项式

拉格朗日插值法的数值稳定性:如图,用于模拟一个十分平稳的函数时,插值多项式的取值可能会突然出现一个大的偏差(图中的14至15中间)

可以将拉格朗日基本多项式重新写为:

定义重心权[7][8]

上面的表达式可以简化为:

于是拉格朗日插值多项式变为:

即所谓的重心拉格朗日插值公式(第一型)或改进拉格朗日插值公式。它的优点是当插值点的个数增加一个时,将每个

  都除以

  ,就可以得到新的重心权

  ,计算复杂度为

  ,比重新计算每个基本多项式所需要的复杂度

  降了一个量级。

将以上的拉格朗日插值多项式用来对函数

  插值,可以得到:

因为

  是一个多项式。

因此,将

  除以

  后可得到:

  [7]

这个公式被称为重心拉格朗日插值公式(第二型)或真正的重心拉格朗日插值公式。它继承了(1)式容易计算的特点,并且在代入x值计算

  的时候不必计算多项式

  [7]。它的另一个优点是,结合切比雪夫节点进行插值的话,可以很好地模拟给定的函数,使得插值点个数趋于无穷时,最大偏差趋于零[7]。同时,重心拉格朗日插值结合切比雪夫节点进行插值可以达到极佳的数值稳定性。第一型拉格朗日插值是向后稳定的,而第二型拉格朗日插值是向前稳定的,并且勒贝格常数很小[9]。

参考来源

^ E. Waring. Problems Concerning Interpolations. Philosophical Transactions of the Royal Society of London. 1779, 69: 59–67.

^ (英文)E. Meijering. A chronology of interpolation: From ancient astronomy to modern signal and image processing,. Proceedings of the IEEE: 323.

^ (英文)Julius Orion Smith III. Lagrange_Interpolation. Center for Computer Research in Music and Acoustics (CCRMA), Stanford University.

^ 冯有前,《数值分析》,第63页

^ 李庆扬,《数值分析》第4版,第31页

^ 冯有前,《数值分析》,第64页

^ 7.0 7.1 7.2 7.3 Jean-Paul Berrut, Lloyd N. Trefethen. Barycentric Lagrange Interpolation. SIAM Review. 2004, 46 (3): 501–517.doi:10.1137/S[**************]5.

^ 王兆清,李淑萍,唐炳涛. 一维重心型插值:公式、算法和应用. 山东建筑大学学报. 2007, 22 (5): 447–453.

^ NICHOLAS J. HIGHAM. The numerical stability of barycentric Lagrange Interpolation. IMA Journal of Numerical Analysis. 2004, 24 (4): 547–556.

(中文)李庆扬,王能超,易大义. 《数值分析》第4版. 清华大学出版社. 2001. ISBN 7-302-04561-5.

(中文)冯有前. 《数值分析》. 清华大学出版社. 2001. ISBN 7-810-82495-3.

(中文)拉格朗日插值多项式. 太原理工大学.


相关内容

  • 多项式插值法和拉格朗日插值
  • 教案一 多项式插值法和拉格朗日插值 基本内容提要 1 多项式插值法的基本概念 2 插值多项式的存在性与唯一性分析 3 拉格朗日插值多项式的构造及截断误差 4 截断误差的实用估计式 5 逐次线性插值法 教学目的和要求 1 熟练掌握多项式插值法的基本概念 2 理解插值多项式的存在性与唯一性 3 掌握拉格 ...

  • 拉格朗日插值法matlab
  • 实验题目 拉格朗日插值法 一.实验目的及要求 利用Matlab学习拉格朗日插值法 二.研究.解答以下问题 问题:1.已知f(0.4)0.916291,f(0.5)0.693147,f(0.6)0.510826,分别用线性插值法和二次拉格朗日插值法分别计算f(0.54),并且说明哪个结果误 ...

  • 削弱卫星星历误差对定位精度影响的方法探讨
  • 第18卷#专辑# 2009年12月 淮海工学院学报(自然科学版) JournalofHuaihaiInstituteofTechnology(NaturalScienceEdition) Vo.l18 S.I.Dec.2008 DOI:10.3969/.jjssn.1672-6685.2009.S0 ...

  • 离散数学证明题
  • 离散数学证明题:链为分配格 证明设a,b均是链A的元素,因为链中任意两个元素均可比较,即有a≤b或a≤b,如果a≤b,则a,b的最大下界是a,最小上界是b,如果b≤a,则a,b的最大下界是b,最小上界是a,故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论: ⑴b≤a或 ...

  • MATLAB实现拉格朗日插值
  • MATLAB实现拉格朗日插值 建立如下拉格朗日插值函数: function y=lagrange(x0,y0,x); n=length(x0); m=length(x); for i=1:m z=x(i); s=0.0; for k=1:n p=1.0; for j=1:n if j~=k p=p* ...

  • 插值与数据拟合
  • 第八章 插值与数据拟合建模 在数学建模的某些问题中,通常要处理给定由实验或测量得到大批量的数据,处理这些数据的目的是为了进一步研究该问题提供数学手段.而这些数据有时是某一类已知规律(函数)的测试数据,有时是某个未知函数的离散数据,插值与数据拟合就是通过这些已知数据去确定某一类函数的参数或寻找某个近似 ...

  • 最优化基础理论与方法
  • 目录 1.最优化的概念与分类 ................................................................................................................. 2 2. 最优化问题的求解方法 ..... ...

  • 高等数值分析_插值法报告
  • 南京理工大学 课程考核论文 课程名称:高等数值分析 论文题目:基于matlab 的函数插值方法性能比较 姓名:xxx 学号:xxxxxxxxxx 成绩: 摘要 函数插值是指已知某函数的在若干离散点上的函数值或者导数信息,通过求解该函数中待定形式的插值函数以及待定系数,使得该函数在给定离散点上满足约束 ...

  • 微分中值定理证明中辅助函数的构造
  • 第29卷 第2期 高 师 理 科 学 刊 Vol. 29 No.2 2009年 3 月 Journal of Science of Teachers′College and University Mar. 2009 文章编号:1007-9831(2009)02-0010-04 微分中值定理证明中辅助 ...