第三章多项式插值方法 教学目的及要求: 要求掌握基本的定理及各种插值方法。 插值方法是数学分析中很古老的一个分支它有悠久的历史等距结点内插公 式是由我国隋朝数学家刘焯(公元544610年)首先提出的而不等距结点内插公 式是由唐朝数学家张遂(公元683-727年)提出的这比西欧学者相应结果早 千年 插值方法在数值分析的许多分支(例如,数值积分,数值微分,微分方程数值 解曲线曲面拟合函数值近似计算等等)均有应用下面仅以近似计算函数值为例 来说明 设已知某个函数关系y=f(x)的列表函数值 yo 而x≠x(=01…n)间应该如何估值j=f(x)对于函数关系y=f(x),我们所知 道仅仅上述的表列值它们常常是间接求得的例如是由实验(观测)得来的或者是 从级数或微分方程求得的 我们可以使用插值方法估计y插值方法的目的是寻求简单的连续函数o(x) 使它在n+1个点x0,x,…,xn处取给定值o(x,)=y1=f(x)(=0,1…,n),而在别处 希望它也能近似地代表函数f(x)因为(x)已是有解析表达式的简单函数所以 它在x=x处的值可以按表达式精确地计算出来这样我们就可以将o()看成 y=f(x)的近似值了
第三章 多项式插值方法 教学目的及要求： 要求掌握基本的定理及各种插值方法。 插值方法是数学分析中很古老的一个分支.它有悠久的历史.等距结点内插公 式是由我国隋朝数学家刘焯(公元 544—610 年)首先提出的;而不等距结点内插公 式是由唐朝数学家张遂(公元 683—727 年) 提出的.这比西欧学者相应结果早一 千年. 插值方法在数值分析的许多分支(例如, 数值积分, 数值微分, 微分方程数值 解,曲线曲面拟合,函数值近似计算,等等)均有应用.下面仅以近似计算函数值为例 来说明 设已知某个函数关系 y = f (x) 的列表函数值 n n y y y y x x x x 0 1 0 1 而 x x (i n) i = 0,1, 问应该如何估值 y = f ( x). 对于函数关系 y = f (x),我们所知 道仅仅上述的表列值,它们常常是间接求得的.例如是由实验(观测)得来的,或者是 从级数或微分方程求得的. 我们可以使用插值方法估计 y. 插值方法的目的是寻求简单的连续函数 (x), 使它在 n+1 个点 n x , x , , x 0 1 处取给定值 (x ) y f (x )(i 0,1, ,n) i = i = i = ,而在别处 希望它也能近似地代表函数 f (x).因为 (x) 已是有解析表达式的简单函数,所以 它在 x = x 处的值可以按表达式精确地计算出来.这样我们就可以将 (x) 看成 y = f ( x). 的近似值了
给定点x,x1…x为插值结点称函数(x)为函数f(x)的关于x0,x1…,xn的 插值函数称y=f(x)为被插函数 严格的说插值方法一词只用于x落在给定点x,x1…,xn之间的情形所以也 称它为内插法如果x落在给定点x0,x1…,xn之外并且仍以插值函数o(x)在x处 近似地代替f(x),则一般称这种近似计算函数的方法为外插法 本章我只研究多项式插值,亦即(x)是x的多项式的情形这不仅仅因为多 项式是最简单的函数,而且因为在许多场合,函数f(x)容易用多项式近似地表 示出来此外用多项式作插值函数可满意地解决一系列有应用价值的重要问题 特别是数值积分与数值微分的问题 本章讲不涉及三角插值法其实只要理解了代数多项式插值方法的实质读者就不 难自行导出关于三角多项式插值方法的一系列相应与代数多项式插值方法的理 论结果 §1 Lagrange插值公式 设y=f(x)是实变量x得单值函数,且已知f(x)在给定的n1个互异点 xn处的值y0,y1…yn,即 y=f(x)i=0,…,n 插值的基本间题是寻求多项式p(x),使得 p(x)=y,i=0.…n 设p(x)是一个m次多项式 x=ao+a,x+a, +a x 则插值问题是,如何确定p(x)中的系数an,a12…,an,使得(11)式得以满足所以该 问题等价于求解下述的线性方程组
给定点 n x , x , , x 0 1 为插值结点.称函数 (x) 为函数 f (x) 的关于 n x , x , , x 0 1 的 插值函数.称 y = f (x) 为被插函数. 严格的说,插值方法一词只用于 x 落在给定点 n x , x , , x 0 1 之间的情形,所以也 称它为内插法.如果 x 落在给定点 n x , x , , x 0 1 之外,并且仍以插值函数 (x) 在 x 处 近似地代替 f ( x).,则一般称这种近似计算函数的方法为外插法. 本章我只研究多项式插值，亦即 (x) 是 x 的多项式的情形.这不仅仅因为多 项式是最简单的函数，而且因为在许多场合，函数 f (x) 容易用多项式近似地表 示出来.此外,用多项式作插值函数可满意地解决一系列有应用价值的重要问题. 特别是数值积分与数值微分的问题. 本章讲不涉及三角插值法.其实,只要理解了代数多项式插值方法的实质读者就不 难自行导出关于三角多项式插值方法的一系列相应与代数多项式插值方法的理 论结果 §1. Lagrange 插值公式 设 y = f (x) 是实变量 x 得单值函数，且已知 f (x) 在给定的 n+1 个互异点 n x , x , , x 0 1 处的值 n y , y , , y 0 1 ,即 y f (x ), i 0, ,n. i = i = 插值的基本问题是,寻求多项式 p(x),使得 p(x ) y , i 0, n. (1.1) i = i = 设 p(x) 是一个 m 次多项式 ( ) , 0 2 = 0 + 1 + 2 + + m m p x a a x a x am x a 则插值问题是，如何确定 p(x) 中的系数 a a am , , , 0 1 ,使得(1.1)式得以满足.所以该 问题等价于求解下述的线性方程组:
a0 +axo +axo +.+anxo =yo, a0 +a,x,+axi+.+amx=y, ao+a,+ 上述的线性方程组的系数矩阵为 它是一个(n+1)×(m+1)矩阵 当m>n时,A的列数大于行数不难证明矩阵A的秩数为n+1.因为A的前 n+1列所组成的行列式为(称为 Vandermonde行列式) s ,)def 我们有 (rn…xn,x,)=∏I(x-x 为证(1.3)考虑n次多项式 显然x0,x1…xn均为它的零点且它的x”系数恰为W(x0n…x)即 W(x0…xn-1x)=W(x0…xn-)x-x0)(x-xn) 从而有下述递推关系式 W(x0,…xn-1,xn)=(xn-x0)(x,n-xn)(x0…xn)
(1.2) , , , 2 0 1 2 1 1 2 0 1 1 2 1 0 0 2 0 1 0 2 0 + + + + = + + + + = + + + + = n m n n m n m m m m a a x a x a x y a a x a x a x y a a x a x a x y 上述的线性方程组的系数矩阵为 = m n m m n n x x x x x x x x x A 1 0 2 2 1 1 2 0 0 1 1 1 它是一个(n+1)×（m+1）矩阵. 当 m>n 时，A 的列数大于行数.不难证明矩阵 A 的秩数为 n+1.因为 A 的前 n+1 列所组成的行列式为(称为 Vandermonde 行列式) ( ) m n m m n n n n x x x x x x x x x W x x x def 1 0 2 2 1 1 2 0 0 0 1 1 1 1 , . , − 我们有 ( , . , ) ( ) (1.3) 0 1 − = − j i n n j i W x x x x x 为证(1.3),考虑 n 次多项式 ( ) n n n n n n n n n x x x x x x x x x x x x W x x x 2 1 2 1 1 1 2 1 1 0 2 0 0 0 1 1 1 1 1 , . , − − − − = 显然 0 1 1 , , , n− x x x 均为它的零点,且它的 n x 系数恰为 ( ) 0 1 , . n− W x x 即 ( ) ( )( ) ( ) 0 1 0 1 0 1 , . , , . n− = n− − − n− W x x x W x x x x x x 从而有下述递推关系式 ( ) ( ) ( ) ( ) 0 1 0 1 0 1 , . , , . n− n = n − n − n− n− W x x x x x x x W x x
运用它即可证明(1.3)试式 根据(1.3)并注意到诸x0,x12…,xn互异,从而线性方程组(12)的系数矩阵的秩 数为n+1它表明(1.2)解是不唯一的,即插值问题(1.1)解不唯 当m<n时,矩阵A的行数大于列数按照(1.3)式线性方程组(12)的每m+1个 方程组成的方程组均有唯一一组解a0,a12…an但一般说来,如此求出的各组 a,a12…,an未必相同 即此时(1.2)可能是矛盾方程组 鉴于以上情形,看来取m=n是最为适宜的现在我们重提多项式插值问题:给 定n+1个互异点x02x1,…,xn,对任意一组数y,y1…yn,是否存在唯一的 p(x)∈P(x),使得如下插值条件被满足 p(x) 0, (14) 该问题的答案是肯定的今采用构造性方法把所要求的多项式p(x)求出来 试设想如果可求出具有如下性质的特殊的插值多项式l(x)∈P(=0,…m) j≠i,j=0, 1,j (15) 则多项式 p(x)=∑y1(x) (1.6) 必为满足(14)的多项式但(15)中上面的等式指出x0,…x中除x外均为l(x)的 零点因此1(x)=c(x-x0)…(x-x)x-x1)(x-xn) 其中c为常数,但(1.5)中下面的等式指出 (x-xo)-(x-x_(x-x)-(x-x) 所以
运用它即可证明(1.3)式 根据(1.3),并注意到诸 n x , x , , x 0 1 互异，从而线性方程组(1.2)的系数矩阵的秩 数为 n+1 .它表明(1.2)的解是不唯一的，即插值问题(1.1)的解不唯一。 当 m<n 时,矩阵 A 的行数大于列数.按照(1.3)式,线性方程组(1.2)的每 m+1 个 方程组成的方程组均有唯一一组解 a a am , , , 0 1 .但一般说来，如此求出的各组 a a am , , , 0 1 未必相同. 即此时(1.2)可能是矛盾方程组. 鉴于以上情形，看来取 m=n 是最为适宜的.现在我们重提多项式插值问题: 给 定 n+1 个互异点 n x , x , , x 0 1 ,对任意一组数 n y , y , , y 0 1 ，是否存在唯一的 p(x) P(x) ，使得如下插值条件被满足 p(x ) y , i 0, n. (1.4) i = i = 该问题的答案是肯定的 .今采用构造性方法把所要求的多项式 p(x) 求出来。 试设想,如果可求出具有如下性质的特殊的插值多项式 l (x) P (i 0, n). i n = ( ) (1.5) 1, 0, , 0, , = = = j i j i j n l x i 则多项式 ( ) ( ) (1.6) 0 = = n i i i p x y l x 必为满足(1.4)的多项式.但(1.5)中上面的等式,指出 n x , , x 0 中除 i x 外,均为 l (x) i 的 零点,因此 ( ) ( ) ( )( ) ( ) i i i n l x = c x − x x − x x − x x − x 0 −1 +1 其中 c 为常数，但(1.5)中下面的等式指出 ( ) ( )( ) ( ) . 1 i 0 i i 1 i i 1 i n x x x x x x x x c − − − − = − + 所以
(x-x)…(x-x)(x-xn)…(x-xn) (x2-x0)(x2-x1)(x2-x)…( 记n{x)=(x-x0)-(x-x,),则l(x)又可表示为更简洁的形式 (x-x, ww'(x 总之n次多项式 ()=∑ Jw(x) (1.7) 满足插值条件(1.4) 若q(x)∈P也满足插值条件(14),则mx)=q(x)-p(x)∈P必以x2…x为 零点即(x1)=0,=0,…n这样一来n次多项式小(x)竟然有n+1个不同的零点 是故q(x)=p(x)所以由(1)表示的n次多项式(严格地说,是次数不超过n的多 项式)是P中满足插值条件的唯一多项式它常常称作为 Lagrange插值多项式 并记为 Ln(x)=∑y 台(x-x,hn(x) 按前述推理可知 Lagrange插值多项式Ln(x)也可视为是从下面的行列式方程 中解出来的 ln 0 9) y (请读者自行补证)由(1.9)式表示的公式便于推广到一般形式的插值问题由于篇 幅所限此处不能祥述 由(1.1)所示的条件称为插值条件点组x,x1,…xn称为插值结点上面所得到
( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) . 0 1 1 0 1 1 i i i i i i n i i n i x x x x x x x x x x x x x x x x l x − − − − − − − − = − + − + 记 ( ) ( ) ( ) n w x = x − x x − x 0 ，则 l (x) i 又可表示为更简洁的形式 ( ) ( ) (x x )w (x) w x l x i i − = 总之 n 次多项式 ( ) ( ) ( ) ( ) (1.7) 0 = − = n i i i x x w x w x p x y 满足插值条件（1.4） 若 ( ) Pn q x 也满足插值条件（1.4）,则 ( ) ( ) ( ) Pn x = q x − p x 必以 n x , , x 0 为 零点,即 (xi ) = 0, i = 0, n .这样一来,n 次多项式 (x) 竟然有 n+1 个不同的零点. 是故 q(x) p(x). 所以由(1.7)表示的 n 次多项式（严格地说，是次数不超过 n 的多 项式）是 Pn 中满足插值条件的唯一多项式.它常常称作为 Lagrange 插值多项式, 并记为 ( ) ( ) ( ) ( ) = − = n i i n i x x w x w x L x y 0 按前述推理可知 Lagrange 插值多项式 L (x) n 也可视为是从下面的行列式方程 中解出来的: ( ) 0 (1.9) 1 1 1 1 2 1 2 1 1 1 0 2 0 0 0 2 = n n n n n n n n n y x x x y x x x y x x x L x x x x (请读者自行补证).由(1.9)式表示的公式便于推广到一般形式的插值问题由于篇 幅所限,此处不能祥述. 由(1.1)所示的条件称为插值条件,点组 n x , x , , x 0 1 称为插值结点.上面所得到