第二章 插值.

Presentation on theme: "第二章 插值."— Presentation transcript:

1 第二章 插值

2 §1 引 言 一、引例 已经测得在某处海洋不同深度处的水温如下： 深度（M） 466 741 950 1422 1634
水温（oC） 根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温. 这就是本章要讨论的“插值问题”

3 二、插值问题的定义 (2.1.1) 当精确函数 y = f(x) 非常复杂或未知时，在区间 上一系列节点 处测得函数值
上一系列节点 处测得函数值 ,由此构造一个简单易算的 近似函数 g(x)  f(x)，满足条件 (2.1.1) 这个问题称为“插值问题”

4 这里的 g(x) 称为f(x) 的插值函数。 节点 x0 … xm称为插值节点, 条件（2.1.1)称为插值条件， 区间 称为插值区间。

5 插值函数的类型有很多种 插值问题 插值函数 最常用的插值函数是 …? 代数多项式 用代数多项式作插值函数的插值称为代数插值，即
选取次数不超过n的多项式 Pn(x) ，使得 Pn (xj) = yj (j = 0, 1… n) (2.1.2) 本章主要讨论的内容 插值法 插值问题 插值函数

6 §2 代 数 插 值 代数插值 一、插值问题解的存在唯一性？ 二、插值多项式的常用构造方法？ 三、插值函数的误差如何估计？

7 一、插值多项式的存在唯一性： 设所要构造的插值多项式为： 由插值条件 得到如下线性代数方程组：

8 此方程组的系数行列式为 范得蒙行列式 ！ 当 时， D  0， 因此，Pn(x) 由a0, a1,…, an唯一确定。

9 注：通过解上述方程组求得插值多项式 的方法
定理 (唯一性) 满足 的 n 阶插值 多项式Pn(x)存在且唯一。 注：通过解上述方程组求得插值多项式 的方法 并不可取.这是因为当n较大时解方程组的计算量 较大，而且方程组系数矩阵的条件数一般较大 （可能是病态方程组）, 当阶数n越高时，病态越重。 怎样可以不通过求解方程组而获得插值多项式呢?

10 在n次多项式空间Pn中找一组合适的基函数
,使 不同的基函数的选取导致不同的插值方法. Lagrange插值 Newton插值

11 二、拉格朗日(Lagrange)插值 1．线性插值 (n=1) (x1 ,y1) P1(x) f(x) (x0 ,y0) x0 x1

12 n = 1 已知 x0 , x1 ; y0 , y1 ，求 l0(x) l1(x)

13 因过三点的二次曲线为抛物线，故称为抛物插值。
2．抛物插值(n=2) p2(x)  f(x) x0 x1 x2 f(x) 因过三点的二次曲线为抛物线，故称为抛物插值。

14 设连续函数y = f（x）在[a, b]上对给定n + 1个 不同结点： x0, x1, …, xn , 分别取函数值
y0, y1, …, yn 其中 yi = f (xi) i = 0, 1, 2,…, n 试构造一个次数不超过n的插值多项式 使之满足条件 i = 0, 1, 2,…, n 要求：无重合节点，即

15 若能求得n次多项式lk (x) , k = 0, 1,…, n， 满足 则 即Pn (x)满足插值条件（2.1.2）.
i = 0, 1, 2,…, n 即Pn (x)满足插值条件（2.1.2）.

16 的表达式推导： 根据lk (x)的定义，xk以外所有的结点都是lk (x)的根， 因此，令 又由lk (xk) = 1，得：

17 从而得 n 阶拉格朗日（Lagrange）插值公式：

18 n+1个互异的点，对 f（x) 所作的n次Lagrange插值多项式 有误差估计
4 、插值余项/* Remainder */ 定理 若 在[a , b]内存在, 则在[a , b]上的 n+1个互异的点，对 f（x) 所作的n次Lagrange插值多项式 有误差估计 Rolle’s Theorem的推论: 若 充分光滑，且 存在 使得

19 注： 通常不能确定  , 而是估计 , x(a,b)，将 作为误差估计上限。 当 f(x) 为任一个次数 n 的多项式 时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的。

20 例：已知 分别利用 sin x 的1次、2次 Lagrange 插值计算 sin 50， 并估计误差。 解： n = 1 分别利用x0, x1 以及 x1, x2 计算 利用

21 利用 计算得：sin 50  ,

22 sin 50 = … 利用x0, x1 作为插值节点的实际误差   利用x1, x2作为插值节点的实际误差 

23 n = 2

24 sin 50 = … 2次插值的实际误差 

25 三、牛顿插值（Newton’s Interpolation ）
1．引入 Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数li(x) 都需要重新计算。 能否重新在 中寻找新的基函数 ？ 希望每加一个节点时，只附加一项上去即可。

26 设 利用插值条件 代入上式，得关于 的线性代数方程组: 当 互异时，系数矩阵非奇异，且容易求解

27 How complex the expression are!
It is not a difficult thing for a mathematician. We can use notation How complex the expression are!

28 2．差商 2.1 差商的定义(亦称均差) 定义1：设有函数f (x)以及自变量的一系列 互不相等的 （即在 时， ）
互不相等的 （即在 时， ） 的值 f(xi) , 称 为f (x)在点xi , xj处的一阶差商，并记作f [xi , xj]，

29 又称 为f (x)在点xi, xj, xk处的二阶差商 称 为f (x)在点x0, x1,…, xk处的k阶差商。

30 利用插值条件和差商的定义,可求出 的系数 : 从而

31 因此，每增加一个结点，Newton插值多项式只增加一项，克服了Lagrange插值的缺点。

32 差商可列表计算： 由差商定义可知： 高阶差商是两个低一阶差商的差商。 xi yi 一阶差商 二阶差商 n 阶差商 … … x0 f (x0)
xn-1 xn f (x0) f (x1) f (x2) … f (xn1) f (xn) f [x0, x1] f [x1, x2] … … f [xn1, xn] f [x0, x1 , x2] … … f [xn2, xn1, xn] f [x0, …, xn] xn f (xn+1) f [xn, xn+1] f [xn1, xn, xn+1] f [x1, …, xn+1] f [x0, …, xn+1] 由差商定义可知： 高阶差商是两个低一阶差商的差商。

33 2.分别写出二次、四次Newton插值多项式
例: 给定 的数据表 1.构造差商表 2.分别写出二次、四次Newton插值多项式 解:差商表 一阶差商 二阶差商 三阶差商 四阶差商

34

35 2.2 差商的性质: 性质1(差商与函数值的关系): 记 ,则 性质2 （对称性）： 差商的值与结点排列顺序无关，即

36 性质3 (差商与导数的关系): 设 在 上有 阶导数,且 则存在 使得 性质4 (特征定理):

37 3.牛顿差值余项 由插值多项式的唯一性可知 ， 故其余项也相同，即 定理： Newton插值多项式的余项为 其中

38 四、等距节点插值 1．引入(微商的离散化)

39 2．差分的定义 设函数 在等距节点 上的 值 为已知,这里 为常数,称为步长. 定义: 偏差 分别称为 在 处以 为步长的向前差分,
设函数 在等距节点 上的 值 为已知,这里 为常数,称为步长. 定义: 偏差 分别称为 在 处以 为步长的向前差分, 向后差分,以及中心差分.

40 3、差分表 计算各阶差分可按如下差分表进行：

41 4、差分的性质 性质1 (差分与函数值的关系): 各阶差分均可表示 为函数值的线性组合: 其中， 性质2 (前差与后差的关系):

42 性质3 (多项式的差分): 若 f(x)∈Pn (n次多项式类), 则
性质4 (差分与差商的关系): 在等距节点的前提下，

43 性质5 (差分与导数的关系）：在等距节点的前提下，
性质6：常数的差分等于零. 性质7：差分算子为线性算子，即

44 性质8： 这个性质类比于 性质9： （类比于分部积分法则 ）

45 5、等距节点的牛顿插值公式  牛顿前插公式 牛顿公式: 利用差分的性质, 可将Newton公式简化为
(1) 称公式(1)为Newton向前差分插值公式,其余项为

46 (2)  牛顿后插公式 如果将Newton插值公式改为按节点 的 次序排列的Newton插值公式,即 (3)

47 令x=xn-th, 则当x0≤x≤xn时,0≤t≤n. 利用差商与 向后差分的关系, 式(3)可简化为
(4) 称式(4)为Newton向后差分插值公式。

48 其余项为 注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。

49 例 给定f(x)在等距节点上的函数值表如下: xi 0.4 0.6 0.8 1.0 f(xi) 1.5 1.8 2.2 2.8
分别用Newton向前和向后差分公式求f(0.5)及f(0.9)的近似值. 解 先构造向前差分表如下: xi fi △fi △2fi △3fi x0=0.4, h=0.2, x3=1.0. 分别用差分表中对角线上的值和最后一行的值,得Newton向前和向后插值公式如下:

50 当 x=0.5时,用公式(1),这时t=(x-x0)/h=0.5. 将t=0.5代入(1),得
(2) 当 x=0.5时,用公式(1),这时t=(x-x0)/h=0.5. 将t=0.5代入(1),得 f (0.5)≈N3(0.5)= 当x=0.9时, 用公式(2), 这时t=(x3-x)/h=0.5. 将t=0.5代入(2), 得 f (0.9)≈N3(0.9)=

51 五、Hermite 插值 1．引入 要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 P(x) 满足: 把此类插值多项式称为
在实际问题中，对所构造的插值多项式，不仅 要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 P(x) 满足: （1） 把此类插值多项式称为 埃米尔特（Hermite）插值多项式或称 带导数的插值多项式，记为H (x)。 H (x) 存在且唯一

52 2.推导 只讨论函数值与导数值个数相等的情况. 设在节点 上, 要求插值多项式 ,满足条件 这里给出的 个条件,可唯一确定一个次数不超
设在节点 上, 要求插值多项式 ,满足条件 (5) 这里给出的 个条件,可唯一确定一个次数不超 过 的多项式 其形式为

53 如根据条件(5)来确定 个系数 , 显然非常复杂,因此,仍采用求Lagrange插值多项式的 基函数方法. 先求插值基函数 及 ,共有 个, 每一个基函数都是 次多项式,且满足条件

54 (6) 于是满足条件(5)的插值多项式 可写成用插值基函数表示的形式,即 (7)

55 由条件(6),显然有 下面的问题就是求满足条件(6)的基函数 及 为此,可利用Lagrange插值基函数 .令 其中 是式

56 所表示的基函数.由条件式(6),有

57 整理,得 解得 由于

58 两端取对数再求导,得 于是 (8) 同理可得 (9)

59 3. Hermite 插值余项 还可以证明满足条件(5)的插值多项式是唯一的. 用反证法,假设 及 均满足条件(5), 于是
用反证法,假设 及 均满足条件(5), 于是 在每个节点 上均有二重根,即 有 重根. 但 是不高于 次的多项式,故 唯一性得证.

60 仿照Lagrange插值余项的证明方法, 若 在 内的 阶导数存在，则其 插值余项为多少？ (10) 其中 且与 有关.

61 作为带导数插值多项式(7)的重要特例是n=1的情形.
这时可取节点为 及 ,插值多项式为 , 满足条件 (11) 相应的插值基函数为 , 它们满足条件

62

63 根据(8)式及(9)式的一般表达式,可得

64 于是满足条件(11)的插值多项式是 其余项为 ,由式(10)得

65 要求在1个节点 x0 处直到m0 阶导数都重合的插值多项式即为 在 点处的Taylor多项式
注： N 个条件可以确定 阶多项式。 N  1 要求在1个节点 x0 处直到m0 阶导数都重合的插值多项式即为 在 点处的Taylor多项式 其余项为

66 4.举例 例：设 x0  x1  x2, 已知 , 求多项式 P(x)满足 且 , 并估计误差。
且 , 并估计误差。 解：首先，P 的阶数为3, 模仿 Lagrange 多项式的 思想，设 其中

67 h0(x) 有根 x1, x2，且  x1 是重根。 又: h0(x0) = 1  C0 h2(x) 与h0(x) 完全类似。 h1(x) 有根 x0, x2  由余下条件 h1(x1) = 1 和 可解。

68 (x)  h1 有根 x0, x1, x2  又:  C1 可解。 与 Lagrange 分析完全类似

69 一般地，已知 x0 , …, xn 处有 y0 , …, yn 和 ，求 H2n+1(x),满足 。 解:设 其中 hi(x)
这样的Hermite 插值唯一 一般地，已知 x0 , …, xn 处有 y0 , …, yn 和 ，求 H2n+1(x),满足 。 解:设 其中 hi(x) 有根 x0 , …, xi , …, xn且都是2重根   由余下条件 和 可解Ai 和 Bi 

70 (x)  hi 有根 x0 , …, xn, 除了xi 外都是2重根  设 则

71 六、分段低次插值 1.多项式插值的龙格现象  例：在[5, 5]上考察 的Ln(x)。取 Ln(x)  f (x) n 越大，
- 5 4 3 2 1 0.5 1.5 2.5 Ln(x)  f (x)  n 越大， 端点附近抖动 越大，称为 Runge 现象

72 2. 分段线性插值 在每个区间 上，用1阶多项式 (直线) 逼近 f (x): 记 ,易证：当 时， 一致

73 y y= f(x) y=p(x) x o 失去了原函数的光滑性。

74 若令 则 是分段一次的连续函数且满足条件

75 这种性质称为局部非零性质。相应的分段线性插值
则 即为分段线性插值的基函数, 基函数 只在 附近不为零,在其它地方均为零。 这种性质称为局部非零性质。相应的分段线性插值 函数为：

76 分段线性插值的误差估计 定理1 如果 在 上二阶连续可微,则分段线性插值函数 的余项有以下估计 其中,

77 3. 分段三次Hermite插值 给定节点 ， 在节点 上的 函数值及导数值分别为 。 在每个子区间 上作两点三次Hermite插值，因此
给定节点 ， 在节点 上的 函数值及导数值分别为 。 在每个子区间 上作两点三次Hermite插值，因此 是分段三次，总体是直至一阶导数连续，插值函数为 其中基函数为

78

79

80

81

82 七、三次样条插值 1.引入 要求：插值曲线既要简单，又要在曲线的连接处比较光滑。 而在节点上不仅连续，还存在连续的低阶导数，
这样的分段插值函数在分段上要求多项式次数低， 而在节点上不仅连续，还存在连续的低阶导数， 把满足这样条件的插值函数，称为样条插值函数， 它所对应的曲线称为样条曲线，其节点称为样点， 这种插值方法称为——样条插值。

83 定义：设对y = f (x)在区间[a, b]上给定一组节点
a = x0 < x1 < x2 <…< xn = b和相应的函数值y0, y1,…, yn， 如果s(x)具有如下性质： （1）在每个子区间[xi-1, xi] (i = 1, 2,…, n)上s (x)是不高 于三次的多项式 （2）s (x)，s’ (x)，s (x)在 [a, b]上连续；则称s (x)为 三次样条函数.如再有 （3） s (xi ) = f (xi) (i = 0, 1, 2,…, n)， 则称s (x)为y = f (x)的三次样条插值函数。

84 注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。
f(x) S(x) H(x)

85 2. 三弯矩方程 设f (x)是定义在 [a, b]区间上的一个二次连续可微函数， 为分划： 令
i = 0, 1, 2,…, n 在每一个小区间[xi-1, xi] i = 1,…, n 上都是三次 多项式， S (x)在 [xi-1, xi] 上的表达式为：

86 （12） 其中 ，将（12）两次积分得： Ai 和Bi 为积分常数。

87 因为 所以它满足方程：

88 （13）

89 求 Mi，确定S (x)的表达式。微分（13）式

90 于是 1 6 3 ) ( + - = i M h y x S 由 得 （14）

91 各项除以hi + hi+1，并记 则（13）可以写为

92 3. 边界条件 （1）D1-样条：给定两端点导数值 有 于是可得

93 分别补充为方程组（13）的第一个和最后 一个方程组，得D1-样条的三弯矩方程为：

94 （2）D2-样条：给定边界条件 得三弯矩方程 若取 M0 = Mn=0，称为三次自然样条。

95 （3）周期样条：若f(x0 ) = f (xn), 则可将s (x0 ) = f (x0) 或
s (xn ) = f (xn) 去掉， 再加入条件 ① ② ③

96 补充（13）中的最后及第一个方程 可得周期样条的三弯矩方程

97 经补充后的方程组（13）为 （14） 其中，对端点条件①，有

98 对端点条件③，有 （14 ）是一个三对角方程组，可用追赶法解之。 此方程组系数严格对角占优 ！从而存在唯一解。 求出了Mi (i = 0, 1,…, n)，也就求得了S (x)在各个 小区间的表达式Si (x)（i = 0, 1, 2,…, n）

99 4.算法 若取等距节点 hi = h, i = 1,…, n –1

100 （1） i = 1, 2, …, n hi = xi – xi-1 （2） i = 1, 2,…, n

101 （3）解n – 1阶三对角方程组，得 M1 , M2 ,…, Mn-1 代入端点条件计算M0 , Mn （4） 若取 ，计算

102 5. 三次样条插值函数的收敛性 定义: 设 是区间 上的连续函数，记 为 函数 的范数.

103 定理 设被插值函数 为满足边界 条件①或③的3次样条插值函数，则在插值区间 上成立余项估计式 其中,