第2章--插值法

1、第二章第二章 插值法插值法2022-6-201现代数值分析现代数值分析（三大模块）（三大模块）n数值逼近数值逼近： 插值法、函数逼近、插值法、函数逼近、数值积分与数值微分数值积分与数值微分n数值代数数值代数： 线性方程组、非线性方程的数值解法线性方程组、非线性方程的数值解法n微分方程数值解微分方程数值解： 常微分方程数值解、常微分方程数值解、偏微分方程数值解偏微分方程数值解2022-6-20第2章 插值法2第第2章章 插值法插值法/* Chapter 2 Interpolation */2.1 引言引言2.2 Lagrange插值插值2.3 差商与差商与 Newton插值插值2.4 带导数条件

2、的带导数条件的Hermite插值插值2.5* 分段低次插值分段低次插值2.6* 三次样条插值三次样条插值2022-6-20第2章 插值法3 在工程实践和科学实验中，经常需要建立函数关系，即在工程实践和科学实验中，经常需要建立函数关系，即y=f(x)。虽然从原则上说，它在某个区间。虽然从原则上说，它在某个区间a,b上是存在的，但上是存在的，但通常只能观测到它的部分信息，即只能获取通常只能观测到它的部分信息，即只能获取a,b上一系列离散上一系列离散点上的值，这些值构成了观测数据。这就是说，点上的值，这些值构成了观测数据。这就是说，我们只知道一我们只知道一张观测数据表张观测数据表， xi x1 x2

3、 xnf(xi)f(x1)f(x2)f(xn)解决方法解决方法用一个经验函数用一个经验函数y=g(x)对真实函数对真实函数y=f(x)作近似。作近似。确定经验函数确定经验函数y=g(x)的方法的方法（1）插值法）插值法 （2）拟合法）拟合法2022-6-20第2章 插值法4已知数据表已知数据表（1）插值法的基本思想）插值法的基本思想求一个经验函数求一个经验函数y=g(x)，使，使g(xi)=f(xi), i=1,n. xi x1 x2 xnf(xi)f(x1)f(x2)f(xn)（2）拟合法的基本思想）拟合法的基本思想 niiixSniiixfxSxfxg12)(12)()(min)()( 求

4、一个经验函数求一个经验函数y=g(x)，使，使通过已知样点通过已知样点不要求近似函数通过已知样点不要求近似函数通过已知样点2022-6-20第2章 插值法52.1 引言引言2.1.1 插值法的提出背景插值法的提出背景插值法就是一种最简单的重要方法插值法就是一种最简单的重要方法实际问题中经常要涉及到实际问题中经常要涉及到函数值的计算函数值的计算问题：问题：（1）如果如果函数表达式函数表达式本身比较复杂，且需要多次本身比较复杂，且需要多次重复计重复计算算时，计算量会很大；时，计算量会很大； （2）有的函数甚至有的函数甚至没有表达式没有表达式，只是一种，只是一种表格函数表格函数，而，而我们需要的函数

5、值不在该表格中。我们需要的函数值不在该表格中。 对于这两种情况，我们都需要寻找一个对于这两种情况，我们都需要寻找一个计算方便且表计算方便且表达简单达简单的函数来的函数来近似代替近似代替，这就是，这就是数值逼近数值逼近问题。问题。 2022-6-20第2章 插值法6设函数设函数f(x)在区间在区间a,b上有定义，且已知在点上有定义，且已知在点 ax0 x1 xn b 处的函数值处的函数值 y0 = f(x0), y1 = f(x1), yn = f(xn)，若存，若存在一简单的函数在一简单的函数 P(x)，满足条件，满足条件P(xi) = f(xi) (i = 0,1, n)，就称，就称P (x

6、) 称为称为f(x) 的的插值函数插值函数。插值法定义插值法定义点点x0 , x1 , , xn 称为称为插值节点插值节点，区间，区间a,b称为称为插值区插值区间，间，求插值函数求插值函数P(x)的方法称为的方法称为插值法插值法。几何几何意义：意义：x0 x1x2x3x4xP(x) f(x)2022-6-20第2章 插值法7常用常用插值函数的类型插值函数的类型代数代数插值：多项式插值插值：多项式插值, 0,)(0111 nnnnnaaxaxaxaxP有理有理插值：有理分式函数插值：有理分式函数三角三角插值：三角多项式插值：三角多项式)()()(xQxPxPnm 2.1.2 多项式插值多项式插值

7、/* Polynomial Interpolation */ ), 1 , 0()(niyxPii （1.3）bxxxan 10 设在区间设在区间 上给定上给定 个点个点,ba1 n上的函数值上的函数值 , ,求次数不超过求次数不超过 的多项式的多项式 ，使，使), 1 , 0)(nixfyii n)(xP多项式插值问题多项式插值问题 2022-6-20第2章 插值法8由由插值条件插值条件得关于系数得关于系数 的的 元线性方程组元线性方程组naaa,101 n ,101111000010nnnnnnnnnyxaxaayxaxaayxaxaa（1.4） 问题：问题： P(x)是否存在？若存在，是

8、否唯一？如何求？是否存在？若存在，是否唯一？如何求？nnxaxaaxP 10)(系数矩阵为系数矩阵为,1111100 nnnnnxxxxxxA（1.5）nnnnnxxxxxxA1010111 2022-6-20第2章 插值法9称为称为范德蒙德（范德蒙德（Vandermonde）矩阵）矩阵, ,由由 互异，故互异，故),1 ,0(nixi .0)(det1, njiojijixxA因此线性方程组因此线性方程组（1.4）的解的解 存在且唯一存在且唯一. .naaa,10 结论结论定理定理1 设设x0 ,x1,xn 是是n+1个互异节点个互异节点,函数函数f(x)在这组节在这组节点的值点的值yk=f

9、(xk)(k=0,1,n)是给定的，那么存在唯一的次是给定的，那么存在唯一的次数数n的多项式的多项式P (x)满足满足 P (xk)= yk, k=0,1,n。?P(x) 但遗憾的是但遗憾的是方程组方程组(1.4) 阶数阶数n越越高，高，计算量越大。能不计算量越大。能不能不通过解方程组直接得到插值多项式呢？能不通过解方程组直接得到插值多项式呢？2022-6-20第2章 插值法10Interpolation polynomial ps. 神威-太湖之光(10亿亿)、天河二号(5亿亿)2022-6-20第2章 插值法112.2 拉格朗日多项式拉格朗日多项式 niyxPiin,., 0,)( 求求

10、n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)(1xP101xxxx 010 xxxx = y0 + y12.1.1 线性插值与抛物插值线性插值与抛物插值两点式两点式)()(0010101xxxxyyyxP 点斜式点斜式)(001010 xxxxxxy ()ff线性插值线性插值 nkkknxlyxL

11、0)()(2022-6-20第2章 插值法12二次插值二次插值n = 2已知已知 x0 , x1 , x2; y0 , y1 ,y2 , 求求22102)(xaxaaxP 使得使得002,)(yxP112)(yxP 222)(yxP ,2020100 xaxaay 2121101xaxaay 2222102xaxaay 方程组求解麻烦方程组求解麻烦抛物插值抛物插值 思路：思路：对于线性插值的对于线性插值的两种形式解两种形式解进行适当的分析进行适当的分析, 从从中寻求规律得到中寻求规律得到拉格朗日插值拉格朗日插值(公式公式)和和牛顿插值牛顿插值(公式公式).我们先来看看如何得到我们先来看看如何得

12、到二次拉格朗日插值公式二次拉格朗日插值公式.)(1xP101xxxx 010 xxxx = y0 + y1两点式两点式)()(0010101xxxxyyyxP 点斜式点斜式)(001010 xxxxxxy ()ff2022-6-20第2章 插值法13 首先首先, 线性插值的两点式可看作是两个特殊的一次线性插值的两点式可看作是两个特殊的一次式的一种线性组合式的一种线性组合.101xxxx 010 xxxx )(1xP= y0 + y1 10)(iiiyxl对称式对称式l0(x)l1(x)实质上实质上0l（x）和）和1l（x）即是满足函数表）即是满足函数表 的一次插值多项式的一次插值多项式 ,称称

13、l0(x)和和l1(x)为以为以x0,x1为节点的基本插为节点的基本插值多项式，也称为值多项式，也称为线性插值线性插值的的插值基函数插值基函数 。基函数的线性组合基函数的线性组合基函数法基函数法满足满足 li(xj)= ij 显然有显然有l0(x)+ l1(x)1.其中，其中， l0(x)和和l1(x)满足：满足： l0(x0)=1, l0(x1)=0, l1(x0)=0, l1(x1)=1, L1(x) L1(xj) 10)(iiiyxjl =yj2022-6-20第2章 插值法14启发启发: :其中，其中，l0(x), l1(x), l2(x)都是都是二次多项式二次多项式，且应满足，且应满

14、足满足满足(2.1) 的的 l i(x) 是否存在是否存在?若存在，具有什么形式呢若存在，具有什么形式呢?（2.1）二次二次Lagrange插值多项式为插值多项式为 L(x)= y0l0(x) + y1l1(x) + y2l2(x) 二次插值是否能由一些二次插值是否能由一些二次插值基函数二次插值基函数来线性组合？来线性组合？先考虑先考虑 l0(x)。l0(x) 0(x x1)(x x2), 其中其中 0 是待定系数。是待定系数。2022-6-20第2章 插值法15同理同理 l1(x) 1(x x0)(x x2), l2(x) 2(x x0)(x x1),1(x1x0)(x1x2)12(x2x0

15、)(x2x1)1此即此即二次拉格朗日插值公式二次拉格朗日插值公式, 其中其中, l0(x), l1(x), l2(x)是满足是满足(2.1)的特殊的特殊(基本基本)二次插值多项式二次插值多项式;称为称为二次插值基函数二次插值基函数.L2(x)= y0+ y1+ y2(x - -x0)(x - -x2)(x1- -x0)(x1- -x2)(x - -x1)(x - -x2)(x0- -x1)(x0- -x2)(x - -x0)(x - -x1)(x2- -x0)(x2- -x1)0(x0 x1)(x0 x2)1 l0(x) 0(x x1)(x x2), 由由 l0( x0)=1，所以，所以 0(

16、x0 x1)(x0 x2)1，则，则 L2(xj) 20)(iiiyxjl =yj2022-6-20第2章 插值法16n 1li(x)每个每个 li 有有 n 个根个根 x0 xi xn njj i jiniiixxCxxxxxxCxl00)().().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()( Lagrange Polynomial与与 有关，而与有关，而与 无关无关节点节点f2.2.2 拉格朗日插值多项式拉格朗日插值多项式)()()()()()()(110110niiiiiiniiixxxxxxxxxxxxx

17、xxxxl )., 1 , 0(ni 展开展开n 次插值多项式次插值多项式 :求次数求次数n的多项式的多项式Ln(x), 使其满足使其满足 Ln(x0)=y0 , Ln(x1)=y1 , . , Ln(xn)=yn 令令 Ln(x)=l0(x)y0 + l1(x)y1 + +ln(x)yn ., 0;, 1)(jijixlji1000)(0100)(0010)(0001)(210210 xlxlxlxlxxxxnn2022-6-20第2章 插值法17其中其中满足条件满足条件 nkkknxlyxL0)()( ), 1 , 0,(., 0;, 1)(nkjjkjkxljk)()()()()()()

18、(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl )., 1 , 0()()(0njyxlyxLjnkjkkjn （2.9）易求得易求得 )(1knx ),()()(101nnxxxxxxx（2.10）记记.)()()()(011 nkknknknxxxxyxL （2.11）),()()(110nkkkkkkxxxxxxxx kkxxxxxxk )()(lim 2022-6-20第2章 插值法18例例1 已知已知 ， ，求，求 的近似值的近似值.解：解：10100, 981 90,10,100, 9,811100 yxyx这是一个线性插值问题这是一个线性插值问题1008

19、1100)(0 xxl8110081)(1 xxl插值多项式为插值多项式为L1(x)=l0(x)y0 + l1(x)y1)90(191 x90)90(1L 473684. 9 基函数分别为基函数分别为811008110100811009 xx 注注2 2：若不将多项式次数限制为若不将多项式次数限制为 n ，则插值多项式，则插值多项式不唯一不唯一。2022-6-20第2章 插值法19n)(xLnn 注注1:1: 次插值多项式次插值多项式 通常是次数为通常是次数为 的多项式，的多项式，特殊特殊情况下次数可能小于情况下次数可能小于 . .n例如例如 也是一个插值也是一个插值多项式，其中多项式，其中

20、可以是任意多项式。可以是任意多项式。 niinxxxpxLxP0)()()()()(xp练习练习 求经过求经过A(0,1)，B(1,2)，C(2,3)三个点的二次三个点的二次Lagrange插值多项式插值多项式.解：解：.322110221100 yxyxyx，；，；，2120210121012002010212)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL 13)12)(02()1)(0(2)21)(01()2)(0(1)20)(10()2)(1( xxxxxxx插值条件插值条件n)(nxLn 注注2 2：若不将多项式次数限制为若不将多项式次数限制为

21、n ，则插值多项式，则插值多项式不唯一不唯一。n)(xLnn 注注1:1: 次插值多项式次插值多项式 通常是次数为通常是次数为 的多项式，的多项式，特殊特殊情况下次数可能小于情况下次数可能小于 . .n例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。 niinxxxpxLxP0)()()()()(xpn)(nxLn2022-6-20第2章 插值法20设节点设节点)1( nf在在(a , b)内存在内存在, 考察考察截断误差截断误差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 满足条件满足条件 , 2.2.3 插值余

22、项插值余项 (Remainder)罗尔定理罗尔定理 设设f(x)在在a,b内连续，在内连续，在(a,b)内可导，且有内可导，且有 f(a)=f(b)；则在；则在(a,b)内一定存在一点内一定存在一点，使得，使得 。0)( f显然显然 Rn(xi ) =f(xi)-Ln(xi)=0 , i=0,1,n, 设设Rn(x)=K(x) n+1(x), 现在任意固定一点现在任意固定一点 x a,b, xxi (i=0,1,n),引进辅助函数引进辅助函数 g(t)=f(t)- Ln(t)-K(x) n+1(t), 则则g(t)在在(a,b)上具有上具有n+1阶导数，在阶导数，在 t= x0, x1, xn

23、, x 诸点诸点处函数值皆等于零。处函数值皆等于零。即即g(t)在在a,b中有中有n+2个零点。个零点。由由罗尔定理罗尔定理知知g(t)在在a,b中有中有n+1个零点。个零点。2022-6-20第2章 插值法21如此反复，最后可推知如此反复，最后可推知g(n+1)(t)在在a,b中有中有1个零点个零点 ，即有，即有 g(n+1)( )=0, a -三次多项式三次多项式) ) )2, 1 , 0()()(ixfxPii)()(11xfxP多项式的曲线通过多项式的曲线通过),(,(),(,(),(,(221100 xfxxfxxfx)(,)()(0100 xxxxfxfxP )(,10210 xx

24、xxxxxf 故故),)()(210 xxxxxxA .)(,)(,)(210121001101xxxxxxxfxxxxfxfA 可由条件可由条件 确定确定)()(11xfxP A通过计算通过计算余项余项可设可设),()()()(2210 xxxxxxxkxR 其中其中 为待定函数为待定函数. . )(xk2022-6-20第2章 插值法43).()()()()()(2210 xtxtxtxktPtftg 构造构造a, b上有四个零点上有四个零点x， x0，x1，x2 ；其中；其中x1为为 二重零点二重零点. 利利用用Rolly定理，知定理，知g(t)在在x0，x1，x2 ，x组成的三个小区间

25、内组成的三个小区间内至少各有一个零点，记为至少各有一个零点，记为 1, 2, 3 ，加上，加上x1 ，在，在a, b上至上至少有少有4个零点个零点., 0)(!4)()()4()4( xkfg 反复应用反复应用罗尔定理罗尔定理，得，得 在在 内至少有一个内至少有一个零点零点，)()4(tg),(ba故有故有),()()(! 41)(2210)4(xxxxxxfxR (4.5)余项表达式为余项表达式为 )()()!1()()()()(10)1(nnnxxxxxxnfxLxfxR 2022-6-20第2章 插值法44例例8 给定给定 求求 在在 上的三次埃尔米特插值多项式上的三次埃尔米特插值多项式

26、 ，使它满足，使它满足并写出余项表达式并写出余项表达式. .,49, 1,41,)(2102/3xxxxxf)(xf49,41)(xP),2, 1 , 0()()(ixfxPii),()(11xfxP求出函数值求出函数值,827)49(, 1)1(,81)41(210 ffffff.23)1(,23)(2/1 fxxf构造均差表构造均差表解解 301110198274967814111iifx?.3011,67,21010 xxxfxxf待定系数待定系数，令，令).49)(1)(41()1)(41(3011)41(6781)( xxxAxxxxP2022-6-20第2章 插值法45可得可得.2

27、2514)40116723(1516A故故,25145023345026322514)49)(1)(41(22514)1)(41(3011)41(6781)(23xxxxxxxxxxP余项余项).49,41()49()1)(41(169! 41)49()1)(41(! 4)()()()(22/52)4( xxxxxxfxPxfxR 由条件由条件 ，可得，可得23)1()1(fP,23)45(4343301167)1(AP2022-6-20第2章 插值法462251425810198274994236781411111 iifx)()(,)(,)(,)()(11021101011001003xx

28、xxxxxxxxfxxxxxxxfxxxxfxfxN 2)1)(41(22514)1)(41(94)41(6781 xxxxxNewton形式的形式的Hermite插值插值2022-6-20第2章 插值法47,)()()()()(11113 kkkkkkkkmxmxyxyxxH (4.7)基函数法基函数法插值节点取为插值节点取为 及及 ，插值多项式为，插值多项式为 ，插值条件为，插值条件为kx1kx)(3xH其中其中 是关于节点是关于节点 及及 的三次的三次埃尔米特插值基函数，分别满足埃尔米特插值基函数，分别满足)(),(),(),(11xxxxkkkkkx1kx),()(3kkkxfyxH

29、),()(3kkkxfmxH ).()();()(11131113kkkkkkxfmxHxfyxH(4.6)完全导数完全导数两点三次埃尔米特插值两点三次埃尔米特插值插值多项式插值多项式, 1)( kkx , 0)(1 kkx , 0)(1 kkx ,0)( kkx , 0)( kkx , 1)( kkx , 0)(1 kkx , 0)(1 kkx , 0)(1 kkx , 1)(11 kkx , 0)(1 kkx . 1)(11 kkx ,0)(1 kkx ,0)(1 kkx , 0)(1 kkx , 0)(11 kkx 2022-6-20第2章 插值法48 ,)(211 kkkkxxxxba

30、xx令令显然显然, 0)(1 kkx , 0)(1 kkx 再利用再利用, 1)( baxxkkk 及及, 02)(1 axxbaxxkkkkk , 1)( kkx , 0)()(1 kkkkxx , 0)(1 kkx 解得解得,21,211 kkkkkxxxbxxa于是求得于是求得.21)(2111 kkkkkkkxxxxxxxxx 同理可得同理可得2111121)( kkkkkkkxxxxxxxxx (4.8)(4.9)(xk 该是什么样的呢？该是什么样的呢？ 1112112)(kkkkkkkkkxxxxxxbaxxxxxax 2022-6-20第2章 插值法49 ,)(211 kkkkk

31、xxxxxxax 为求为求 ，由给定条件可令，由给定条件可令)(xk直接由直接由 ，得到，得到1)(axkk ,)(211 kkkkkxxxxxxx (4.10) .)(2111 kkkkkxxxxxxx (4.11),0)()(1 kkkkxx , 1)( kkx , 0)(1 kkx 同理同理,2)(111211 kkkkkkkkkkxxxxxxxxaxxxxax 2022-6-20第2章 插值法50最后代入，得最后代入，得12112111211121113)()(2121)( kkkkkkkkkkkkkkkkkkkkkkkkmxxxxxxmxxxxxxyxxxxxxxxyxxxxxxxxxH(4.12).,(,)()(! 41)(1212)4(3kkkkxxxxxxfxR(4.13)余项余项 ，)()()(33xHxfxR2022-6-20第2章 插值法51已知已