第5章:插值法 第5章插值方法 5.1插值问题概述 假设f(×)是某个表达式很复杂甚至根本写不出来的实函数且已 知fx)在某个区间[ab上的n+1个互异的点xx1…,Xn处的函数 值fxo)f(×1),…;f(xn)我们希望找到个简单的函数y=P(x,使得 P(xx)=f(xk), k=0, 1,.,n 这就是插值问题 如果我们找到了这样的函数y=P(∞X)我们就可以在一定范围内利 用P(x)近似表示f∞x)从而解决了相应的计算问题。 1利用函数值列表来表示插值问题 对于一个插值问题来说,我们的已知条件就是n+1个互异的点 处的函数值回顾高等数学中学习过的函数的表示方法,我们可用 下面表1的形式列出已知的函数值,并简称为由表1给出的插值 可题 表1:插值问题的函数值列表 k x A(x)/()f(x,) f(x)
第 5 章：插值法 1 第 5 章 插值方法 5.1 插值问题概述 假设 f(x)是某个表达式很复杂,甚至根本写不出来的实函数,且已 知 f(x)在某个区间[a,b]上的 n+1个互异的点 x0,x1,…,xn处的函数 值 f(x0),f(x1),…,f(xn)，我们希望找到一个简单的函数 y=P(x),使得 P(xk)=f(xk),k=0,1,…,n. 这就是插值问题。 如果我们找到了这样的函数 y=P(x),我们就可以在一定范围内利 用 P(x)近似表示 f(x),从而解决了相应的计算问题。 1.利用函数值列表来表示插值问题 对于一个插值问题来说，我们的已知条件就是 n+1 个互异的点 处的函数值.回顾高等数学中学习过的函数的表示方法，我们可用 下面表 1 的形式列出已知的函数值，并简称为由表 1 给出的插值 问题。 表 1：插值问题的函数值列表 k 0 1 … n k x , 0 x 1 x … n x ( ) k f x ( ) 0 f x ( ) 1 f x … ( ) n f x
第5章:插值法 2重要术语 对于n+1个基点的插值问题,我们称 f(x)为被插值函数 P(x)为插值函数; Xx1…xn为插值基点或插值节点; P(Xk)=f(x,k=01…n为插值条件; [a,b]为插值区间。 注释:对于早期的插值问题来说,f(x通常是已知的,比如对数 函数,指数函数,三角函数等这些问题现在已经不用插值法来计 算了;对于现在的许多实际问题来说,我们拼并不知道f(x)的具体 形式,所对应的函数值可能是由测量仪器或其他物理设备中直接 读出来的,f(x只是一个概念中的函数。 3.多项式插值 对于n+1个基点的插值叵题如果要求插值函数是次数不超过n 的多项式,记为Pn(x),则相应的问题就是多项式插值,并且把 Pn(x)称为插值多项式 实际上,我们所考虑的插值函数通常都是多项式函数或分段
第 5 章：插值法 2 2.重要术语 对于 n+1 个基点的插值问题，我们称： f(x) 为被插值函数; P(x)为插值函数； x0,x1,…,xn 为插值基点或插值节点; P(xk)=f(xk),k=0,1,…,n 为插值条件； [a,b]为插值区间。 注释：对于早期的插值问题来说，f(x)通常是已知的，比如对数 函数，指数函数，三角函数等这些问题现在已经不用插值法来计 算了；对于现在的许多实际问题来说，我们并不知道 f(x)的具体 形式，所对应的函数值可能是由测量仪器或其他物理设备中直接 读出来的，f(x)只是一个概念中的函数。 3．多项式插值 对于 n+1个基点的插值问题，如果要求插值函数是次数不超过 n 的多项式，记为 Pn(x)，则相应的问题就是多项式插值，并且把 Pn(x)称为插值多项式。 实际上，我们所考虑的插值函数通常都是多项式函数或分段
第5章:插值法 多项式函数。由于次数不超过n的多项式的般形式为 Pn(×)=a0+aX+a2X2+…+anxn (1) 所以只要确定了n+1个系数aoaL,a2an,我们便确定了一个插值 多项式。 4.多项式插值的一般方法 对于n+1个基点的多项式插值问,我们完全可以用上 章中的办法来求插值多项式Pn(X)的系数,aa1a,an,它们可表 为下面的线性方程组的解,所以多项式插值相对说来是很简单 的 1(x)…(x)a)( 1(x)…(x1)2‖a (2) 1(xn) (x,) 定理1:n+1级范德蒙( Vandermonde)行列式 不等于零的充要条件是诸X0X,…,Xn两两互不相同 这是代数学中很著名的个定理,我们推荐大家阅读北京大
第 5 章：插值法 3 多项式函数。由于次数不超过 n 的多项式的一般形式为 Pn((x)=a0+a1x+a2x 2+…+anx n （1） 所以只要确定了 n+1 个系数 a0,a1,a2,an，我们便确定了一个插值 多项式。 4．多项式插值的一般方法 对于 n+1 个基点的多项式插值问题，我们完全可以用上一 章中的办法来求插值多项式 Pn(x)的系数，a0,a1,a2,an，它们可表 为下面的线性方程组的解，所以多项式插值相对说来是很简单 的。 = n n n n n n n y y y a a a x x x x x x 1 0 1 0 1 1 1 1 0 1 0 1 ( ) ( ) 1 ( ) ( ) 1 ( ) ( ) （2） 定理 1：n+1 级范德蒙（Vandermonde）行列式 n n 2 n n n 2 2 2 2 n 1 2 1 1 n 0 2 0 0 1 x (x ) (x ) 1 x (x ) (x ) 1 x (x ) (x ) 1 x (x ) (x ) 不等于零的充要条件是诸 x0,x1,…,xn两两互不相同。 这是代数学中很著名的一个定理，我们推荐大家阅读北京大
第5章:插值法 学数学力学系编《高等代数》(人民教育出版社1978年第一版) pp78-79,基本方法是数学归纳法。 定理2:如果两个次数都不超过n的多项式P(x和Q(x在n+1 个互不相同的点x0,x1…x处的值相同,则这两个多项式恒等。 这也是代数学中很著名的定理,在北京大学数学力学系编 《高等代数》(人民教育出版社1978年第-版)pp25-26中可 找到定理的证明,基本思路是不恒为零的n次多项式不可能有多 于n个的零点,而P(x-Q(有,所以它要么是高于n次的多 项式,要么恒等于零。 5多项式插值的基本结论 由于线性方程组(2)的系数矩阵的行列式就是范德蒙行列 式,再加上我们对插值基点互异的假设,上面的定理1表明,也 就是说,对于给定的插值条件,存在唯一的插值多项式,它的系 数就是线性方程组(2)的唯解。 定理2进步表明,不管什么形式的多项式,只要次数不超 过n,而且满足相同的插值条件,那么它们就是恒等的。 6.重要提示: 上面的两个定理已经表明,对于多项式插值问题来说,插值
第 5 章：插值法 4 学数学力学系编《高等代数》（人民教育出版社 1978 年第一版） pp78-79，基本方法是数学归纳法。 定理 2：如果两个次数都不超过 n 的多项式 P(x)和 Q(x)在 n+1 个互不相同的点 n x , x , , x 0 1 处的值相同，则这两个多项式恒等。 这也是代数学中很著名的定理，在北京大学数学力学系编 《高等代数》（人民教育出版社 1978 年第一版）pp25-26 中可 找到定理的证明，基本思路是不恒为零的 n 次多项式不可能有多 于 n 个的零点，而 P(x)-Q(x)却有，所以它要么是高于 n 次的多 项式，要么恒等于零。 5.多项式插值的基本结论 由于线性方程组（2）的系数矩阵的行列式就是范德蒙行列 式，再加上我们对插值基点互异的假设，上面的定理 1 表明，也 就是说，对于给定的插值条件，存在唯一的插值多项式，它的系 数就是线性方程组（2）的唯一解。 定理 2 进一步表明，不管什么形式的多项式，只要次数不超 过 n,而且满足相同的插值条件，那么它们就是恒等的。 6．重要提示： 上面的两个定理已经表明，对于多项式插值问题来说，插值
第5章:插值法 多项式由插值条件唯决定,所以我们在口语中所讲的n+1个 基点的插值问题求解指的就是求岀由一组插值条件所唯一决定 的多项式。但是我们允许这个多项式有不同的数学飛式,以便于 数值计算 在后面的两节中,我们将对相同的插值条件给出两种不同的 插多珷式,即 agrange和 Newton插值多珷式。所以他们应 该是恒等的,名称不同只是各自的形式有所不同。 7与曲线拟合的差异 从形式上看,n+1个基点的插值问题与曲线拟合问题基本相 同:都是由n+1个条件决定出一个多项式,也考虑寻找基函数 的线性组合,但它们的原理,方法,以及应用领域都不相同,基 本上是两个类别的问题。 曲线拟合主要应用于误差分析以及多元回归,数学原理是投 影理论,方法是最小二乘法;而插值则应用于精确计算,应该说 只是一种经验的方法,理论基非常脆弱,不过我们可以通过验 算来证实结果的有效性 52拉格朗日插值公式 1.拉格朗日插值公式的构造
第 5 章：插值法 5 多项式由插值条件唯一决定，所以我们在口语中所讲的 n+1 个 基点的插值问题求解指的就是求出由一组插值条件所唯一决定 的多项式。但是我们允许这个多项式有不同的数学形式，以便于 数值计算。 在后面的两节中，我们将对相同的插值条件给出两种不同的 插值多项式，即 Lagrange 和 Newton 插值多项式。所以他们应 该是恒等的，名称不同只是各自的形式有所不同。 7.与曲线拟合的差异 从形式上看，n+1个基点的插值问题与曲线拟合问题基本相 同：都是由 n+1 个条件决定出一个多项式，也考虑寻找基函数 的线性组合，但它们的原理，方法，以及应用领域都不相同，基 本上是两个类别的问题。 曲线拟合主要应用于误差分析以及多元回归，数学原理是投 影理论，方法是最小二乘法；而插值则应用于精确计算，应该说 只是一种经验的方法，理论基础非常脆弱，不过我们可以通过验 算来证实结果的有效性。 5.2 拉格朗日插值公式 1． 拉格朗日插值公式的构造
第5章:插值法 对于表1所确定的n+1个基点的插值问题,相应的拉格朗 日插值公式,我们记为L(×),实际就是把插值多项式Pn(×)表为 基函数{×xk=01,…n)的线性组合,其中 x-x l(x)= (x=x) 而且组合系数实际就是诸yoy…yh,因此我们有 Ln(x)=∑y4·l(x) (2) 接下来我们要证明Ln(x)的确是插值多项式,也就是满足η+1个 插值条件。 2.证明Lnx)的确是插值多项式 注意到所有的k(×)都是n次数多项式,所以Ln(x)是次数不 超过n的多项式。再注意到 1()=1/1、yhmy=k 0, when j≠k yk=0…,n 所以我们有
第 5 章：插值法 6 对于表 1 所确定的 n+1 个基点的插值问题，相应的拉格朗 日插值公式，我们记为 Ln(x)，实际就是把插值多项式 Pn(x)表为 基函数{lk(x)|k=0,1,…,n}的线性组合，其中 j n j k j k j j k x x x x l x = = − − = 0 ( ) ( ) ( ) （1） 而且组合系数实际就是诸 y0,y1,…,yn，因此我们有 ( ) ( ) 0 L x y l x k k n k n k = = = （2） 接下来我们要证明 Ln(x)的确是插值多项式，也就是满足 n+1 个 插值条件。 2． 证明 Ln(x)的确是插值多项式 注意到所有的 lk(x)都是 n 次数多项式，所以 Ln(x)是次数不 超过 n 的多项式。再注意到 k n when j k when j k l x k j k j 0,1, , 0, 1, ( ) = = = = 所以我们有
第5章:插值法 7 Ln(x)=∑y4(x) y1(x)+∑yl4(x) yj=0,1, 所以Ln(x)满足插值条件,即Ln()的确是插值多项式 3基函数的性质 定理:对于给定的函数值列表 以及由(1)定义的基函数{k(x),k=0,1…n},我们有 l(x)=1 证明:考虑被插函数为f(x)≡1的特殊的多项式插值问题, 对于给定的插值基点Ⅺ0X1…,Ⅺ,对应的函数值 yoy…yn均为 1,从而相应的拉格朗日插值多项式为 L,(x)=∑1·k(x) 它满足插值条件 L(x,)=∑1:1(x,)=y=1=0,1,…,n 而f(x)三1也是次数不超过n的多项式,也满足插值条件
第 5 章：插值法 7 j n y y l x y l x L x y l x j k n k j k j j j k k j k n k n j k k j 0,1, , ( ) ( ) ( ) ( ) 0 0 = = = + = = = = = 所以 Ln(x)满足插值条件，即 Ln(x)的确是插值多项式。 3.基函数的性质 定理：对于给定的函数值列表 k x , 0 x 1 x … n x k y 0 y 1 y … n y 以及由（1）定义的基函数{lk(x),k=0,1,…,n}，我们有 = = 1 0 ( ) 1 k k k l x 证明：考虑被插函数为 f(x) ≡ 1 的特殊的多项式插值问题， 对于给定的插值基点 x0,x1,…,xn，对应的函数值 y0,y1,…,yn 均为 1，从而相应的拉格朗日插值多项式为 = = = 1 0 ( ) 1 ( ) k k n k L x l x 它满足插值条件 L x l x y j j n k k n j k j ( ) 1 ( ) 1, 0,1, ., 1 0 = = = = = = 而 f(x)≡ 1 也是次数不超过 n 的多项式，也满足插值条件
第5章:插值法 0.1.n 由插值多项式的唯性立即推出我们的结论。 4计算表格与算法说明 应该说,对于给定的x求拉格朗日插值多项式的值还是很简 单的,直接按公式计算就成,所以没有太大的价值来研究算法问 题。如果用计算器来计算,我们建议按如下的表格计算。 k x[]Y[k L[kI 0[O]Y[O]]]] L[] 1X[1|Y1] 1] L[2] n X[n] Y[n In L[] 1 首先依次计算基函数I0],[1]…n|k存放基函数k(×)的值。接 下来再依次计算 L[]=Y[o]+[o], LK]=Yk]*k]+Lk-1]k=1,2…,n 5计算基函数值的方法 拉格朗日多项式插值的计算主要是计算基函数的值,作为练习编
第 5 章：插值法 8 f(xk)=yk,k=0,1,…,n 由插值多项式的唯一性立即推出我们的结论。 4.计算表格与算法说明 应该说，对于给定的 x,求拉格朗日插值多项式的值还是很简 单的，直接按公式计算就成，所以没有太大的价值来研究算法问 题。如果用计算器来计算，我们建议按如下的表格计算。 k X[k] Y[k] l[k] L[k] 0 X[0] Y[0] l[0] L[0] 1 X[1] Y[1] l[1] L[2] … … … … … n X[n] Y[n] l[n] L[n] x 1 首先依次计算基函数 l[0],l[1],…,l[n],l[k]存放基函数 lk(x)的值。接 下来再依次计算 L[0]=Y[0]*l[0], L[k]= Y[k]*l[k]+L[k-1],k=1,2,…,n. 5.计算基函数值的方法 拉格朗日多项式插值的计算主要是计算基函数的值，作为练习编
第5章:插值法 程,编写求单个的基函数值的程序还是很有意义的。下面是求基 函数的程序段 float GetLK(float x, int k) [int i=0 float y=1.0 for(i=0;<=ni++) i if(i==k)continue y*=x-×; y/=x收k]-x return 6补充说明 拉格朗日插值虽然算法很简单,但是当n较大时,用计算器来算 还是有点累赘,大家一定不要再去寻找捷径,唯的笨办法就是 老老实实地—个—个地算,把结果填在表中。可能用纸和笔作减 法运算,用计算器作乘法和除汯计算这种组合模式最佳。基函数 值计算完毕后,可作一次检验,看累加起来是否为1,如果是
第 5 章：插值法 9 程，编写求单个的基函数值的程序还是很有意义的。下面是求基 函数的程序段： float GetLK(float x,int k) { int i = 0; float y=1.0; for(i=0;i<=n;i++) { if(i==k) continue; y *= x-x[i]; y /= x[k]-x[I]; } return y; } 6.补充说明 拉格朗日插值虽然算法很简单，但是当 n 较大时，用计算器来算 还是有点累赘，大家一定不要再去寻找捷径，唯一的笨办法就是 老老实实地一个一个地算，把结果填在表中。可能用纸和笔作减 法运算，用计算器作乘法和除法计算这种组合模式最佳。基函数 值计算完毕后，可作一次检验，看累加起来是否为 1，如果是
第5章:插值法 则计算正确;如果不是,则前面的计算肯定有误,应当重新计算。 7.基函数的等价戒式 2(x)=f(x 则有1(x)=,() r =l(x-x) 则有4(x)=n(x) 所以有4(x)= (x-x4)兀1(x) (x) 8.插值函数的等价形式 利用k(x)的等价形式,我们可以进一步得到Ln(x)的等价飛式 Ln(x)=∑y4l4(x) 点( yk x-xk)兀n(xk) k=l(x-xx) Tn+(+)''In+(x) 结论:拉格朗日插值多项式的Ⅺ项(首项)的系数为
第 5 章：插值法 10 则计算正确；如果不是，则前面的计算肯定有误，应当重新计算。 7. 基函数的等价形式 记 = − = = j n j k j k j x x x 0 ( ) ( ) 则有 ( ) ( ) ( ) k k k k x x l x = 记 = − = = + j n j n j x x x 0 1 ( ) ( ) 则有 ( ) ( ) ( ) 1 k n k x x x x − = + ( ) ( ) ' k k n 1 k x x = + 所以有 ( ) ( ) ( ) 1 ( ) ' 1 1 x x x x l x n k n k k + + − = 8．插值函数的等价形式 利用 lk(x)的等价形式，我们可以进一步得到 Ln(x)的等价形式： ) ( ) ( ) ( ) ( ( ) ( ) ( ) ( ) ( ) 1 1 ' 1 1 ' 1 1 1 x x x x y x x x y x L x y l x n k n k k n k k k n k k n k k n k n k n k k + = = + = = + + = = − = − = = 结论：拉格朗日插值多项式的 x n项（首项）的系数为 = = + k n k n k k x y 1 1 ( )