数值计算课件——第四章插值及拟合

1、第四章第四章 插值与曲线拟合插值与曲线拟合一插值与曲线拟合问题一插值与曲线拟合问题二二拉格朗日插值拉格朗日插值三牛顿插值三牛顿插值四四曲线拟合的最小二乘法曲线拟合的最小二乘法 小小 结结插值问题的提出插值问题的提出在许多工程实际问题中，常有如下情况：在许多工程实际问题中，常有如下情况：l函数关系没有明显的解析表达式，只有实验观函数关系没有明显的解析表达式，只有实验观测来确定与自变量的测来确定与自变量的某些某些相对应的函数值；相对应的函数值；l函数虽然有解析表达式，但是使用很不方便。函数虽然有解析表达式，但是使用很不方便。 对上述问题中的函数建立一个简单的便于计算对上述问题中的函数建立一个简单的

2、便于计算和处理的近似表达式，即用和处理的近似表达式，即用一个简单的函数一个简单的函数来近似来近似代替代替这些不便处理的函数这些不便处理的函数插值函数插值函数。4 插值与曲线拟合插值与曲线拟合拟合问题的提出拟合问题的提出 实际问题中通过测量得到的数据比较多，而且实际问题中通过测量得到的数据比较多，而且这些数据本身含有一定误差，根据这些数据求取近这些数据本身含有一定误差，根据这些数据求取近似函数的方法是似函数的方法是曲线拟合曲线拟合。插值要求找到的近似函数的曲线通过所有的数据点。插值要求找到的近似函数的曲线通过所有的数据点。曲线拟合不要求近似函数的曲线通过所有数据，只要曲线拟合不要求近似函数的曲线

3、通过所有数据，只要求该曲线能反映数据变化的基本趋势。求该曲线能反映数据变化的基本趋势。拟合的主要目的是：拟合的主要目的是：去掉测量数据所含的测量误差。去掉测量数据所含的测量误差。插值与拟合的区别插值与拟合的区别 4.1插值问题的数学提法插值问题的数学提法当精确函数当精确函数 y = f(x) 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函，由此构造一个简单易算的近似函数数 P(x) f(x)，满足条件：，满足条件： P(xi) = f(xi) (i = 0, n)。这

4、里的这里的 P(x) 称为称为f(x) 的的插值函数插值函数，称为称为插值节点插值节点。所以所谓插值就是根据已知。所以所谓插值就是根据已知点的函数值求其余点的函数值。点的函数值求其余点的函数值。nxxx,10 4.1 插值问题的数学提法插值问题的数学提法已知已知a, ba, b上的函数上的函数y=y=f f( (x x) )在在n+1n+1个互异点处的函数值个互异点处的函数值: :fnf2f1f0f(x)xnx2x1x0 x求简单函数求简单函数P Pn n( (x x) )，使得，使得( )0,1,( ),*iiP xfin 计算计算f f( (x x) )可通过计算可通过计算P P( (x

5、x) )来近似代替。如下图所示。来近似代替。如下图所示。x0 x1x2x3x4xP(x) f(x)这就是插值问题这就是插值问题, , ( (* *) )式为插值条件式为插值条件, ,( )( )P xf x称称函函数数为为函函数数的的 插插值值函函数数01,nx xx,称为插值节点称为插值节点由于插值函数由于插值函数 的选择不同，就产生不同类型的的选择不同，就产生不同类型的插值。若插值。若 为代数多项式为代数多项式 ， 就是代数插值，若就是代数插值，若 为三角多项式就称为三角多项式插值，若为三角多项式就称为三角多项式插值，若 为为有理函数就称为有理函数插值。由于代数多项式结有理函数就称为有理函

6、数插值。由于代数多项式结构简单，本章主要介绍构简单，本章主要介绍代数多项式代数多项式插值问题。插值问题。 xP xP xP xP2. 2. 满足插值条件的多项式满足插值条件的多项式 P(x)是否存在且唯一？是否存在且唯一？3. 3. 用用P(x)P(x)代替代替f(x)f(x)的误差估计，即截断误差的估计；的误差估计，即截断误差的估计；对于多项式插值，我们主要讨论以下几个问题对于多项式插值，我们主要讨论以下几个问题：4. 4. 当插值节点无限加密时，插值函数是否收敛于当插值节点无限加密时，插值函数是否收敛于f(x)f(x)。1. 如何构造出插值多项式如何构造出插值多项式P(x);即插值多项式的

7、常即插值多项式的常用构造方法有哪些？用构造方法有哪些？ 4.2 拉格朗日插值拉格朗日插值可见可见 P(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。这两点的直线。这种插值称为种插值称为线性插值线性插值，显然在节点上插值误差为，显然在节点上插值误差为0。)()(001010 xxxxyyyxP- - -+ + 101xxxx- - -010 xxxx- - -= y0 + y1l0(x)l1(x) 线性插值（两点插值）线性插值（两点插值）已知函数已知函数 在节点在节点 有函值有函值 ，求作一次多项式求作一次多项式xaaxP10)(+ + 使得使得1100)(,)

8、(yxPyxP xfy 10,xx 11xfy 00 xfy 10, yy 1100yxlyxlxP+ + xl0 xl1 与与 1, 00, 111011000 xlxlxlxl0,()(0,1, )1,ijjil xjnji 即：即：019141( )(9), ( )(4)495945xxlxxlxx- - - - - - - - - -所以所以1137(7)2.65L01,4,9,yx xx 7 例例1 1 已知已知 用线性插值求用线性插值求 近近 似值。似值。012,3,yy 基函数分别为基函数分别为:解解10 01 111( )( )( )2(9)3(4)55L xy lxy lxx

9、x- - + + - -+ + - -插值多项式为插值多项式为23(9)(4)55xx - - -+ +- -1(6)5x+ xfy 210,xxx210,yyy 2210 xaxaaxP+ + + 2 , 1 , 0, iyxPii210,aaa + + + + + + + + + 222210221211012020100 xaxaayxaxaayxaxaay 2 , 1 , 0, iyxPii 221100yxlyxlyxlxP+ + + xx0 x1x2l0(x)100l1(x)010l2(x)001 以以 为例说明基函数的求取方法，当为例说明基函数的求取方法，当 取取 ， 时，时，

10、为为0 0， 取取 时，时， ，因此，因此其中其中 可用可用 求出，求出， xl0 x1x2x xl0 x0 x 10 xl 210 xxxxAxl- - - A 10 xl 20101xxxxA- - - 2101201xxxxxxxxxl- - - - - 1202102xxxxxxxxxl- - - - - 同理同理 2010210 xxxxxxxxxl- - - - - 所以所以 212021012101200201021yxxxxxxxxyxxxxxxxxyxxxxxxxxxP- - - - -+ +- - - - -+ +- - - - - xfy ba,nxxx,10n 0111

11、axaxaxaxPnnnn+ + + + + - - - niyxPii, 1 , 0, n1+ +n xP xfn这样的插值多项式能构造出来吗？唯一吗？这样的插值多项式能构造出来吗？唯一吗？插值多项式的存在性和唯一性定理插值多项式的存在性和唯一性定理证证 ：设所求的插值多项式为：设所求的插值多项式为 P(x)=a0+a1x+a2x2+.+anxn则由插值条件式则由插值条件式Pn(xi)=yi (i=0,1, ., n) 可得关于系数可得关于系数a0 ,a1 , ,an的线性代数方程组的线性代数方程组 设节点设节点xi (i=0,1, ,n)互异互异, 则则满足插值条满足插值条件件P(xi)=

12、yi 的的n次多项式次多项式P(x)=a0+a1x+a2x2+.+anxn 存在且唯一存在且唯一. .定理定理 + + + + + + + + + + + +nnnnnnnnnyxaxaayxaxaayxaxaa101111000010 此方程组有此方程组有n n+1+1个方程个方程, , n n+1+1个未知数个未知数, , 其系数行其系数行列式是范德蒙行列式，即：列式是范德蒙行列式，即：nnnnnnxxxxxxxxx212110200111由于插值节点由于插值节点 xi 互不相同互不相同, , 所有因子所有因子 xj-xi 0, 所以所以上上述行列式不等于零述行列式不等于零, ,故由克莱姆

13、法则知方程组的解存故由克莱姆法则知方程组的解存在且唯一在且唯一. . 即满足条件式即满足条件式 的的n次多项式次多项式存在且唯一。存在且唯一。证毕。证毕。 0110 - - - - niijjixx - - ijijnnnnnnxxxxxxxxxxx)(111212110200反证反证：若不唯一，则除了：若不唯一，则除了P(x) 外还有另一外还有另一 n 阶多项式阶多项式 Q(x) 满足满足 Q(xi) = yi 。考察考察 则则 S的阶数的阶数, )()()(xQxPxS- - n而而 S(x)有有 个不同的根个不同的根n + 1x0 xn矛盾矛盾S(x) 0,所以所以P(x) Q(x) 唯

14、一性说明不论用哪种方法构造的插值多项式，只要唯一性说明不论用哪种方法构造的插值多项式，只要满足同样的插值条件，其结果都是互相恒等的。满足同样的插值条件，其结果都是互相恒等的。 要求要求n阶插值多项式阶插值多项式 ，可以通过求方程组的解，可以通过求方程组的解 得到。但由于解线性代数方程组的计算量比较大，得到。但由于解线性代数方程组的计算量比较大，构造插值多项式时，仍用构造插值多项式时，仍用基函数基函数构造。构造。 希望能找到满足以下条件的希望能找到满足以下条件的n 次多项式次多项式 l i(x)0,()(0,1, )1,ijjil xjnji 然后令然后令iniiyxlxP)()(0 ，则显然有

15、则显然有P (xi) = yi 。基函数的构造基函数的构造)()()()(110niiixxxxxxxxAxl- - - - - + +- -其中其中A A为常数为常数, , 由由li (xi)=1可得可得)()()(1110niiiiiixxxxxxxxA- - - - - + +- -称之为称之为拉格朗日基函数拉格朗日基函数。0110110()()()()( )()()()()()(0,1, )()iiniiiiiiinnjjijj ixxxxxxxxl xxxxxxxxxxxinxx- -+ +- -+ + - - - - - - - - - - - - -li(x)除除xi 点外点外,

16、 , 其余其余xj 都是都是li(x) 的根，可设的根，可设与与 有关，而与有关，而与 无关无关节点节点f拉格朗日插值多项式拉格朗日插值多项式 特别地特别地, , 当当 n =1时又叫线性插值时又叫线性插值, ,其几何意义为其几何意义为过两点的直线过两点的直线. . 当当n =2时又叫抛物插值时又叫抛物插值, , 其几何意其几何意义为过三点的抛物线义为过三点的抛物线. .利用拉格朗日基函数式利用拉格朗日基函数式l i(x), , 构造多项式构造多项式可知其满足可知其满足,称为称为拉格朗日拉格朗日插值多项式插值多项式。iniiyxlxP)()(0 Pn(xi)=yi (i=0,1, ., n)应

17、注意应注意, ,对于插值节点对于插值节点, ,只要求它们互异只要求它们互异, ,与与大小大小次序无关。次序无关。5 插值余项插值余项 截断误差截断误差R (x)=f (x) -P(x)也称为插值多项式的余也称为插值多项式的余项。以下为拉格朗日余项定理。项。以下为拉格朗日余项定理。 定理定理 设设f (x)在区间在区间a ,b上存在上存在n+1 阶导数阶导数, xi a, b (i=0,1, , n) 为为n+1个互异节点个互异节点, 则对任何则对任何x a ,b, , 有有( , )a b 且与且与x 有关有关) ) xnfxPxfxRn !11+ + - - + + ,0 - - niixx

18、x 注意这里是对注意这里是对 t 求导求导证明：考察截断误差证明：考察截断误差)()()(xPxfxR- - Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广：推广：若若0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nR(x) 至少有至少有 个根个根n+1 - - niixxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 构造构造

19、- - - niixtxKtRt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn + + !)1()()()1(+-+nxKRxn + +- - -+ + +!)1)()()()1()1(nxKPfxnxn !)1()()()1(+ + + +nfxKxn + +- -+ + niixnxxnfxR0)1()(! ) 1()()( 0=0( )( )niiiP xl xf其中其中0()( )()njijijj ixxl xxx-LagrangeLagrange插值公式的标准型公式插值公式的标准型公式:插值余项插值余项：(1)0()(

20、)()(1)!nnxiifR xxxn + + - -+ +1 n xfxR 22 10 xxxxx- - - x 010 - -+ +- - xxxxx 210 xxx+ + 2011041xxxxxx- - - - - - 10, xxx 010 - - -xxxx 2011041xxxxxx- - - - - 102xxxxfxR- - - 20128xxMxR- - xfMxxx210max ),(,)(max)!1()(01baxxxnMxRniibxan - -+ + + + xfMnbxan)1(1max+ + + + 其中其中15. 1425. 005. 02+ +- - xx

21、,1)(xxf ，节点节点4, 5 . 2, 2210 xxx)(xf求求的抛物插值多项式的抛物插值多项式, ,且计算且计算f (3)的近似值并估计误差的近似值并估计误差。 例例 设设25. 0)4(, 4 . 0)5 . 2(, 5 . 0)2(210 fyfyfy解解 )45 . 2)(25 . 2()4)(2(4 . 0)42)(5 . 22()4)(5 . 2(5 . 0)(2- - - - - + +- - - - - xxxxxL)5 . 24)(24()5 . 2)(2(25. 0- - - - - + +xx插值为多项式插值为多项式于是于是 325. 0)3(2 xLf因为因为

22、 83)2()(max,64,24 - - fxfxxfx可得可得03125. 0)43)(5 . 23)(23(8361)3()3()3(22 - - - - - - LfR(1)0()( )()(1)!nnxiifR xxxn + + - -+ +误差估计误差估计例：例：已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6

23、/214/6/4/)(1 - - -+ + - - - xxxL这里这里)3,6(,sin)(,sin)()2( - - xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 - - - xxfxRxx00762. 0)185(01319. 01- - - - Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 的实际误差的实际误差 - -0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 的实际误差的实际误差 0.00596 0.00596内插通常优于外推

24、。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。1 Lagrange Polynomialn = 223)()(21)()(21)()()(4363463464363646342 - - - - -+ + - - - - -+ + - - - - - xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 - - - - - xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.00061 0.

25、00061高次插值通常优于高次插值通常优于低次插值低次插值如果如果 是次数不超过是次数不超过 次的多项式，取次的多项式，取 个个 节点插值时，插值多项式就是其自节点插值时，插值多项式就是其自身。身。 xfn1+ +n 插值多项式插值多项式 只与数据只与数据 ， 有关，与节点有关，与节点排列顺序无关。排列顺序无关。 xPix ixf个节点的插值多项式不超过个节点的插值多项式不超过 次次 n1+ +n拉格朗日插值小结拉格朗日插值小结内插比外插精度高。当求某点的函数值时，插内插比外插精度高。当求某点的函数值时，插值节点应尽可能靠近该值节点应尽可能靠近该 点，此时余项小。点，此时余项小。当节点数变化时

26、，需重新计算全部基函数当节点数变化时，需重新计算全部基函数 。LagrangeLagrange插值算法特点插值算法特点& &局限性局限性 优点优点：公式简洁公式简洁, , 理论分析方便理论分析方便 直观；直观； 对称；对称；容易编程上机等。容易编程上机等。 缺点：缺点：基函数计算复杂，计算量大基函数计算复杂，计算量大 每增加一个节点，插值多项式的所每增加一个节点，插值多项式的所 有系有系 数都得重算；数都得重算；计算量为计算量为 。 下一节提出的下一节提出的NewtonNewton插值法插值法就是克服了上缺点。就是克服了上缺点。222nn+4.4 牛顿插值牛顿插值拉格朗日插值的优点是插值多项式

27、特别容易拉格朗日插值的优点是插值多项式特别容易建立，缺点是增加节点时原有多项式不能利建立，缺点是增加节点时原有多项式不能利 用，用，必须重新建立，即所有基函数都要重新计算，这必须重新建立，即所有基函数都要重新计算，这就造成计算量的浪费；就造成计算量的浪费； 能否将能否将 P(x) 改写成改写成.)()(102010+ +- - -+ +- -+ +xxxxaxxaa).(10- - - -+ +nnxxxxa的形式，希望每加一个节点时，的形式，希望每加一个节点时， 只附加一项只附加一项上去即可。上去即可。?本节介绍这种插值公式的建立、特点和应用。本节介绍这种插值公式的建立、特点和应用。这这 要

28、用到要用到差商差商的概念。的概念。 一、差商及其基本性质一、差商及其基本性质定义定义1jijijixxxfxfxxf- - - )()(,称为称为 f (x)在在xi、xj点的点的一阶差商一阶差商.记为记为函数函数 在区间在区间 上的平均变化率上的平均变化率 xfy jixx ,jixxfkikjjikjixxxxfxxfxxxf- - - ,为函数为函数f (x)在点在点xi、xj 、xk的的二阶差商二阶差商.记为记为同样地，称一阶差商的平均变化率同样地，称一阶差商的平均变化率,kjixxxf差商的计算步骤与结果可列成差商表，如下差商的计算步骤与结果可列成差商表，如下一般地，一般地，n-1阶

29、差商的差商阶差商的差商nnnnnnxxxxxfxxxfxxxf- - - - - - -01112010, 称为称为f (x)在在x0 , x1 , , xn点的点的 n 阶差商。阶差商。 由此可知高阶差商是由比它低一阶的两个差商组成。由此可知高阶差商是由比它低一阶的两个差商组成。xk函数值函数值一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商.x0 f (x0) x1 f (x1) f x0 , x1x2 f (x2)f x1 , x2 f x0, x1, x2x3 f (x3) f x2 , x3 f x1, x2, x3 f x0, x1, x2 , x3.利用差商的递推定义，可以用递推

30、来计算差商利用差商的递推定义，可以用递推来计算差商 121520f(x)7431x例例1 :已知：已知：计算三阶差商计算三阶差商f1,3,4,7 -1.25-3.5-1127 413154 123 0 1三阶差商三阶差商二阶差商二阶差商一阶差商一阶差商f(x) x解：解： 作差商表作差商表 所以所以 f1,3,4,7=-1.25 + +- - - - - - nknkkkkkkknxxxxxxxxxfxxxf011010)()()()(, fx0 , x1 , x2 , ., xn = fx1 , x2 , ., xn , x0 性质性质1 差商可以表示为函数值的线性组合，即差商可以表示为函数

31、值的线性组合，即= fx1 , x0 , x2 , ., xn=这一性质称之为差商这一性质称之为差商的对称性的对称性。性质性质2 (对称性对称性) 差商与节点的顺序无关，如差商与节点的顺序无关，如 这一性质可以用数学归纳法证明。（这一性质可以用数学归纳法证明。（P124）性质性质3 若若 是是x x的的n n次多项式，次多项式，则：一阶差商则：一阶差商 是是x的的n-1次多项式，次多项式， 二阶差商二阶差商 是是x x的的n-2n-2次多项式；次多项式； 一般地，函数一般地，函数f(x)f(x)的的k k阶差商阶差商 是是x x的的n-kn-k次多项式次多项式(kn)(kn)。 而而k kn

32、n时，时，k k阶差商阶差商为零。为零。 xf 0, xxf 10 x, xxf 110,- -nxxxxf二、牛顿插值多项式二、牛顿插值多项式如此继续下去，可得一系列等式如此继续下去，可得一系列等式设设x是是a，b上一点，由一阶差商定义上一点，由一阶差商定义000)()(,xxxfxfxxf- - - 同理，由二阶差商定义同理，由二阶差商定义)(,110100 xxxxxfxxfxxf- -+ + 110010,xxxxfxxfxxxf- - - 得得)(,)()(000 xxxxfxfxf- -+ + 得得01010 , ,()nnnnf x xxf x xxf x xxxx- - + +

33、- -)(,)()(000 xxxxfxfxf- -+ + )(,110100 xxxxxfxxfxxf- -+ + )(,221021010 xxxxxxfxxxfxxxf- -+ + 依次把后式代入前式，依次把后式代入前式，000( )() ,()f xf xf x xxx + +- -00100101(),() ,()()f xf xxxxf x xxxxxx+-+-+-+-001001201012012(),(),()() ,()()()f xf xxxxf xxxxxxxf x xxxxxxxxx + +- -+ +- - -+ +- - - -P(x)R (x)令：令：001001

34、20101010011()(),(),()(),()()(),()nnnnkkkNxf xf xxxxf xxxxxxxf xxxxxxxf xf xxxx - - + +- -+ +- - -+ +- - - + + 00101(),()()(),()nnnnnRxfxxxxxxxxxfxxxx + + - - - - )(xP)(xR.)(,)(,)()(102100100+ +- - -+ +- -+ + xxxxxxxfxxxxfxfxf).(,.,100- - - -+ +nnxxxxxxf)().(,.,100nnnxxxxxxxxxf- - - -+ +- -最后得最后得牛顿插值

35、公式特点牛顿插值公式特点)()()(xRxPxf+ + 则：则：)(xP：是：是x的的n次多项式，称为次多项式，称为牛顿插值多项式牛顿插值多项式)(xR：是：是 最后一项，称为最后一项，称为牛顿插值余项。牛顿插值余项。 )(xf增加一个节点时，只需增加一个节点时，只需 再增加一项，再增加一项， 其余各项都不变。其余各项都不变。 )(xP)(xP在节点上，多项式在节点上，多项式 等于被插函数等于被插函数 的值，即的值，即 所以此时的余项所以此时的余项 ，满足插值条件。，满足插值条件。)(xP xf nixfxPii.,2 , 1 , 0,)( 0)( ixR牛顿插值公式特点牛顿插值公式特点(续续

36、)取取n1个节点时，牛顿插值多项式次数不超过个节点时，牛顿插值多项式次数不超过n次，各项系数是各阶差商。次，各项系数是各阶差商。由插值多项式的唯一性知由插值多项式的唯一性知, 拉格朗日插值多项式拉格朗日插值多项式和牛顿插值多项式是相等和牛顿插值多项式是相等 的的。只是算法不同。只是算法不同。拉格朗日插值余项和牛顿插值余项是相等拉格朗日插值余项和牛顿插值余项是相等 的，即：的，即： + +- -+ + niixnxxnf0) 1()(! ) 1()( ).(,.,)(00nnxxxxxxxfxR- - - ),(maxminxx 121520f(x)7431x例例2 :已知：已知：求满足以上插值

37、条件的牛顿型插值多项式。求满足以上插值条件的牛顿型插值多项式。解：在解：在例例1 1中，我们已计算出中，我们已计算出 25. 1, 4,1, 03210210100- - xxxxfxxxfxxfxf则牛顿三次插值多项式为则牛顿三次插值多项式为 2675.381425. 1 )4)(3)(1(25. 1)3)(1(4)1(0)(233+ +- -+ +- - - - - - - - -+ +- -+ + xxxxxxxxxxP4.7 分段低次插值分段低次插值问题的提出：问题的提出：在拉格朗日插值法中，为了使插值多项式更在拉格朗日插值法中，为了使插值多项式更好的逼近被插函数，往往要增加插值节点，

38、提高好的逼近被插函数，往往要增加插值节点，提高插值多项式的次数。当插值区间较大时，对于高插值多项式的次数。当插值区间较大时，对于高次插值次插值在插值区间两端会发生剧烈振荡在插值区间两端会发生剧烈振荡。高次代。高次代数插值所发生的这种现象称为数插值所发生的这种现象称为Runge现象现象.在上个在上个世纪初由世纪初由Runge发现发现.一、一、 高阶插值的龙格现象高阶插值的龙格现象例：例：在在- -5, 5上考察上考察 的的Pn(x)。取。取211)(xxf+),., 0(105niinxi + +- - -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2

39、2.5 n 越大，越大，端点附近抖动端点附近抖动越大，称为越大，称为Runge 现象现象Pn(x) f (x) P2（x）P5（x）P10（x）既要增加插值节点，减小插值区间，又不增加插值多项式的既要增加插值节点，减小插值区间，又不增加插值多项式的次数以减少误差，我们可次数以减少误差，我们可 以以采用分段插值采用分段插值的办法。的办法。 二、二、 分段线性插值分段线性插值原理原理：将插值区间将插值区间分成若干个小的子段分成若干个小的子段，在每个子段，在每个子段上进行低次插值，然后相互连接，用连接相邻节点的上进行低次插值，然后相互连接，用连接相邻节点的折线逼近折线逼近被插函数。被插函数。定义定义

40、已知函数已知函数 ，给定节点，给定节点 xfy bxxxan 10的函数值的函数值 iixfy 求一个分段函数求一个分段函数S(x)S(x)，使其满足，使其满足： S(x)在在a,b上连续；上连续；S(xi)=yi，i0,1,nS(x)在每个子段在每个子段 是是线性函数线性函数。 1,+ +iixx称函数称函数S(x)S(x)为为分段线性插值函数分段线性插值函数。S(x)在子段在子段 上有（线性插值）：上有（线性插值）：,1+ +iixx1111)(+ + + + +- - -+ +- - - iiiiiiiiyxxxxyxxxxxS,for 1+ + iixxx在区间在区间 上有：上有：,b

41、a bxayxlxSniii ,)(0其中其中 111111, 0, iiiiiiiiiiixxlxxxxxxxxxxxxx- - - - - - - - - - - 其其它它显然显然 kikixlki, 0, 1)(！失去了原函数的光滑性。失去了原函数的光滑性。分段线性插值特点分段线性插值特点算法简单，能保证收敛。算法简单，能保证收敛。能获得任意精度的插值。能获得任意精度的插值。局部性质。局部性质。ix1例例3 已知函数已知函数 在区间在区间 上取等上取等 距插值节点（如下表）距插值节点（如下表）, 求区间求区间 上分段线性插上分段线性插值函数，并利用它求出值函数，并利用它求出 的近似值的近

42、似值 211)(xxfy+ + 5 , 05 , 0)5 . 4(fixiy0.038460.058820.10.20.51 54320 1,+ +ii解解 在每个小区间在每个小区间 上上， 11(1)( )(1)(1)(1)()iiiixixiP xyyiiiiy ixyxi+ + +- -+ +- - + +- -+ + +- - + + - -+ +- -于是于是04864. 0)4(03846. 0)5(05882. 0)5 . 4( - -+ +- - xxP - -+ +- - -+ +- - -+ +- - -+ +- -+ +- - )4(03846. 0)5(05882. 0

43、)3(05882. 0)4( 1 . 0)2( 1 . 0)3(2 . 0)1(2 . 0)2(5 . 05 . 0)1()(xxxxxxxxxxxP 5 , 44 , 33 , 22 , 11 , 0 xxxxx4.3 4.3 逐次线性插值逐次线性插值 （本节为了解内容本节为了解内容） 逐次线性插值解决拉格朗日插值为提高精度增逐次线性插值解决拉格朗日插值为提高精度增加插值节点时，要重新计算全部基函数，整个插值加插值节点时，要重新计算全部基函数，整个插值多项式的结构都会改变的问题。为使计算有多项式的结构都会改变的问题。为使计算有“承袭承袭性性”，可用逐次线性插值或称迭代插值的办法解决。，可用逐

44、次线性插值或称迭代插值的办法解决。逐次线性插值是重复地进行线性插值产生从低次到逐次线性插值是重复地进行线性插值产生从低次到高次的拉格朗日插值多项式序列，直到获得合适的高次的拉格朗日插值多项式序列，直到获得合适的计算结果，避免增加节点从头开始计算，常用的计算结果，避免增加节点从头开始计算，常用的埃埃特金特金(Aitken)算法算法和和内维尔内维尔(Neville) 算法算法。4 .3.1 三个节点的情形三个节点的情形已知已知 f(x) 在三个互异节点在三个互异节点x0 ,x1 ,x2的函数值的函数值y0 ,y1 ,y2 用（x0 ,y0 ), (x1 ,y1 )做插值做插值xx0 x1 x2yy

45、0 y1 y20101010110( )xxxxPxyyxxxx-+-用（x0 ,y0 ), (x2 ,y2 )做插值做插值0202020220( )xxxxPxyyxxxx-+-用（x1,P01 ), (x2 ,P02 )做插值做插值2101201021221( )xxxxPxPPxxxx-+- 21012010212210021120102120110210220020112012010210122021( )()()()()()()()()()()()()()()x xx xP xPPx xx xx xx xx xx xx xx xyyyyx x x xx xx x x xx xx x

46、x xx x x xx x x xyyyx x x xx x x xx x x x-+-+-+-上式即是拉格朗日二次插值多项式。上式即是拉格朗日二次插值多项式。两个线性两个线性插值的结果再进行插值的结果再进行线性线性插值，得到抛物插值，得到抛物线性线性插值。插值。kx0 x1x2x0()f x1()f x2()f x01()Px02()Px012()Px三个节点的情形写成表格的形式三个节点的情形写成表格的形式 函数值一阶插值二阶插值4 .3.2 两个线性插值的结果，再进行线性插值可得抛两个线性插值的结果，再进行线性插值可得抛物线插值，这个过程可以继续下去，一般地，利物线插值，这个过程可以继续下

47、去，一般地，利用两个用两个 次插值次插值 和和 进行线性插值，可进行线性插值，可得得 次插值次插值 ，用基函数的形式表示，用基函数的形式表示 当当 ， 时，得到时，得到 ，当，当 ， 时，得到时，得到 ，当当 ， 时，得到时，得到 。反复执行这一算式，可。反复执行这一算式，可以逐步构造出如下的插值顺序。按这个顺序可求以逐步构造出如下的插值顺序。按这个顺序可求出某点的插值。出某点的插值。1- -K01P02P1, 1 ,0- -kPikP,2, 1 ,0- -KikP, 1, 1 ,0- -, 1,2 , 1,2, 1 ,0111, 1 ,01, 1, 1 ,0+ + - - -+ +- - -

48、 - - - - - - -kkikPxxxxPxxxxPikkikkikiik1 k1 i1 k2 i2 k2 i012P 函数值一阶插值二阶插值三阶插值kx0 x1x2x3x0()f x1()f x2()f x3()f x01()Px02()Px03()Px012()Px013()Px0123()Px埃特金插值表埃特金插值表埃特金插值特点埃特金插值特点 埃特金插值埃特金插值例例 已已知知函函数数( )3xf x 在在0,1,2x 处处的的值值，用用埃埃特特金金逐逐次次线线性性插插值值法法求求3的的近近似似值值。 x 0 1 2 21 )(xf 1 3 9 ？ 用用埃埃特特金金逐逐次次线线性

49、性插插值值法法计计算算顺顺序序，可可得得 ix )(ixf 一次 二次 0 1 1 3 2 2 9 3 1. 5 的近似值为的近似值为1.5。3已知已知f(x)在三个互异点在三个互异点 0,1,2的函数值的函数值1,3,9用（0,1 ), (1,3 )作插值作插值0110( )131 00 1xxPx- +-用（0,1 ), (2,9 )作插值作插值用（1,P01), (2 ,P02 )作插值作插值011( )0.5 1 0.5 322P + 0220( )190220 xxPx- +-021( )0.75 1 0.25 932P +01221( )23122 1xxPx-+-0121( )1

50、.5 2( 0.5) 31.52P+ -一般得到的观测数据本身不一定完全可靠，个别数据一般得到的观测数据本身不一定完全可靠，个别数据的误差甚至可能很大，且数据很多。曲线拟合是从已知的的误差甚至可能很大，且数据很多。曲线拟合是从已知的一大堆数据中找出规律，即设法构造一条曲线（拟合曲线）一大堆数据中找出规律，即设法构造一条曲线（拟合曲线）反映数据点总的趋势。反映数据点总的趋势。 4.8 4.8 曲线拟合的最小二乘法曲线拟合的最小二乘法 曲线拟合问题曲线拟合问题曲线拟合同插值法的区别曲线拟合同插值法的区别: :曲线拟合考虑实验曲线拟合考虑实验数据带数据带有测量误差有测量误差，同时，同时测量数据又多测

51、量数据又多，若用插值法时得到的插，若用插值法时得到的插值多项式次数将很高，不实用值多项式次数将很高，不实用曲线拟合得到的多项式不必通过每一点。曲线拟合得到的多项式不必通过每一点。设已知某物理过程（函数关系）设已知某物理过程（函数关系） 的一组的一组观测（实验）数据观测（实验）数据 ，要求在某，要求在某特定函数类特定函数类（例如（例如多项式多项式）中找出一个函数）中找出一个函数 ，作为作为 的近似函数，使得在的近似函数，使得在 上的误差（或上的误差（或称称残差残差） 按某种按某种度量标准度量标准为最小，这就是拟合问题，也称为最小，这就是拟合问题，也称曲曲线拟合。线拟合。 xfy Nixfxii,

52、 1 , 0, xFix NixfxFiii, 1 , 0, - - xfy 曲线拟合的定义曲线拟合的定义记向量记向量 ，要求残差，要求残差 按某种度量按某种度量标准为最小，即要求向量标准为最小，即要求向量 的某种范数的某种范数 最小。例最小。例如，可要求如，可要求 的的1-1-范数范数 或或 - -范数范数 即：即：或或 最小。但由于最小。但由于不便于微分运算不便于微分运算 ，因此，通常用，因此，通常用2-2-范范数。数。 1 1 为最小，这种要求误差平方和最小的拟合称为为最小，这种要求误差平方和最小的拟合称为曲线拟曲线拟合的最小二乘法合的最小二乘法。 Tne ,10 i ee e1e -

53、- NiiiNiixfxFe001 iiiiixfxFe- - maxmax e 200222 - - NiiiNiixfxFe 一、最小二乘拟合原理一、最小二乘拟合原理最小二乘法的最小二乘法的几何意义几何意义 求在给定点求在给定点 x0, x1, xm 处与点处与点(x0,y0), (x1,y1), ,(xm, ym) 的距离平方和最小的曲线：的距离平方和最小的曲线：y =F(x),二、多项式拟合二、多项式拟合这样的曲线拟合叫这样的曲线拟合叫多项式拟合多项式拟合。 满足上式的满足上式的y y 叫叫最小二乘拟合多项式最小二乘拟合多项式. . 特别地特别地, , 当当m m=1=1时时, ,一次

54、多项式拟一次多项式拟合又叫合又叫直线拟合直线拟合。当当N=m+1时，所得的拟合多项式就是时，所得的拟合多项式就是拉格朗日或牛顿插值多项式。拉格朗日或牛顿插值多项式。 对给定的一组数据对给定的一组数据( (x xi i, ,y yi i)()(i i=1,=1,N N),),寻求寻求m m次次多项式（多项式（N N m ）使总误差满足使总误差满足010mjmjmjya xaa xa x + + + 210minNmjijiijJya x-目标函数目标函数由于目标函数由于目标函数J 可看作是关于可看作是关于 mjaj, 1 , 0 的多元函数，故拟合多项式的问题变为求极值问题。的多元函数，故拟合多

55、项式的问题变为求极值问题。0,0,1,jJjma 由求极值的由求极值的必要条件必要条件 得得Nmjjijiiijya xxjm - - - 1020,0,1,即即 + + + + + + + + + + + + + + +imimimmimiiimimiiimimiyxxaxaxayxxaxaxayxaxaNa2110121010 对a0偏导对a1偏导上述方程组是关于上述方程组是关于a aj j的线性方程组，通常称为的线性方程组，通常称为正则正则方程组。方程组。它有唯一解。由方程组可求出系数它有唯一解。由方程组可求出系数a aj j。多项式拟合的一般方法可归纳为以下几步：多项式拟合的一般方法可

56、归纳为以下几步：写出正规方程组，求出系数，得到写出正规方程组，求出系数，得到拟合多项式拟合多项式注注：当：当m m较大时，方程组一般病态。较大时，方程组一般病态。由已知数据画出函数粗略的图形由已知数据画出函数粗略的图形散点图，散点图，确定拟合多项式的次数确定拟合多项式的次数m；列表计算列表计算), 1 , 0()2 , 1 , 0(,11mjyxmjxNiijiNiji 和和例例1 测得铜导线在温度测得铜导线在温度 时的电阻时的电阻 如下表求如下表求电阻电阻R与温度与温度T的近似函数关系。的近似函数关系。)( iR)( CTi85.1083.9082.3580.8079.2577.8076.3

57、0 50.045.140.036.030.125.019.1 6 5 4 3 2 1 0 i)( CTi)( iR解：把表中数据画在坐标纸上，会看到数据点的分布解：把表中数据画在坐标纸上，会看到数据点的分布可用一条直线来近似描述。因此用线性函数拟合。可用一条直线来近似描述。因此用线性函数拟合。01Raa T+列表如下列表如下0 20029.4459325.83565.5245.34255.0002500.0085.1050.063783.8902034.0183.9045.153294.0001600.0082.3540.042908.8001296.0080.8036.032385.4259

58、06.0179.2530.121945.000625.0077.8025.011457.330364.8176.3019.1 Ri iNoImageNoImageNoImageNoImageNoImageNoImage2iTiiRT 1201iiiiiiNaTRaTaTT R + + 故得故得R与与T的拟合直线为的拟合直线为 R=70.572+0.291T正规方程组为正规方程组为 445.200295 .56583.93253 .2453 .245710aa解方程组得解方程组得921. 0,572.7010 aa列表如下列表如下解解 设拟合曲线方程为设拟合曲线方程为 NoImage例例2 已知

59、实验数据如下表已知实验数据如下表试用最小二乘法求它的二次拟合多项式试用最小二乘法求它的二次拟合多项式 i4321124510 yi1098765431 xi876543210NoImageNoImage2210 xaxaay+ 10251472531730173813253 40040100001000100410824327656172981397128164096512642864972401343491753661296216361645010625125252536416256641644245158127953110101111010 iNoImageNoImageNoImageNo

60、ImageNoImageNoImageNoImageNoImageixiy2ix3ix4ixiiyxiiyx2 得正规方程组得正规方程组 102514732253173017381301738153381539210aaa解得解得2676. 0,6053. 3,4597.13210 - - aaa故拟合多项式为故拟合多项式为22676. 06053. 34597.13xxy+ +- - 三、超定方程组的最小二乘解三、超定方程组的最小二乘解当方程组中方程的个数多于未知量的个数时，当方程组中方程的个数多于未知量的个数时，称此方程组为超定方程组。一般来说称此方程组为超定方程组。一般来说 ，超定方程，