东北农业大学《数值分析》课件-第二章（隋老师）.pptx

东北农业大学 数值分析 第二章 第二章 插 值 法 1 引言 2 拉格朗日插值公式 3 逐步线性插值 4 牛顿(Newton)插值 5 埃尔米特(Hermite)插值 6 有理函数插值 1 引 言 发展历史发展历史 应用应用 插值问题的提出插值问题的提出 插值问题所需研究的问题插值问题所需研究的问题 等距节点内插公式 刘焯（隋 公元544610年）不等距节点内插公式 张遂（唐 公元683727年）等距节点一般插值公式 Newton&Gregory(17世纪）非等距节点一般插值公式 J.L.Lagrange(18世纪）发展历史 应应 用用 对观测数据的处理对观测数据的处理 函数的近似表示函数的近似表示 曲线曲面拟合曲线曲面拟合 导出其它数值方法的依据（如数值积分、导出其它数值方法的依据（如数值积分、数值微分、微分方程数值解等）数值微分、微分方程数值解等）以近似计算函数值为例来说明 散点上的函数值，即已知函数表 例：设在实际问题中，某些变量之间的函数关系是存在的，但通常不能用式子表示，只能由实验、观测得到 yf x 在一系列离 xy0 xnx1x0y1yny ijxx ij,如何计算 fx 0 1ixx in,？我们希望 寻求一个简单且易于计算的函数 P x来近 似 fx fxP x，即，一般 P x可选为多 多项式、三角多项式、有理函数或样条函数等。有些函数虽有表达式，但较复杂，计算函数值不经济，这时也希望用简单的函数来逼近。插值问题的提出 已知函数已知函数 在区间在区间 上有上有 yf x()01naxxxb，求一个多 iiyf xin(),0,1,a b,定义，且已知 ，其中 yP x 项式,使其满足 iiP xy(),i0 1n 即要求该多项式的函数曲线要经过 ()yf x 上已知的这n+1个点 0011nnxyxyxy,同时在其它点 上估计误差为 ,xa b()()()R xf xP xY ()p x()f x0 x1x1nxnx2x0y1y2y1nynyX 研究问题 若满足条件的若满足条件的 存在，又如何构造？存在，又如何构造？nPx nPx满足插值条件的多项式满足插值条件的多项式 是否存在，是否存在，唯一？唯一？nPx fx用用 近似代替近似代替 的误差估计？的误差估计？2 拉格朗日插值 插值多项式的存在唯一性插值多项式的存在唯一性 拉格朗日插值多项式拉格朗日插值多项式 插值基函数插值基函数 插值基函数的构造插值基函数的构造 n次拉格朗日型插值多项式次拉格朗日型插值多项式 截断误差截断误差 数值实例数值实例 拉格朗日插值多项式的优缺点拉格朗日插值多项式的优缺点 插值多项式的存在唯一性 Theorem.存在唯一的存在唯一的n 次多项式次多项式 （1.1)满足条件满足条件 01()nnnP xaa xa x0 1,.niiPxy in证明：由证明：由(1.1)可得可得 (1.2)（1.21.2）为一个你）为一个你n n1 1未知量未知量 的线性方程的线性方程组，要证明插值多项式存在唯一，只要证组，要证明插值多项式存在唯一，只要证明参数明参数 存在且唯一，即只要证明其系数存在且唯一，即只要证明其系数行列式不为零即可。行列式不为零即可。nnnnnnnnnaa xa xyaa xa xyaa xa xy010000111101 iaia 方程组（方程组（1.21.2）的系数行列式为）的系数行列式为 此为范德蒙行列式。利用行列式性质可此为范德蒙行列式。利用行列式性质可得系数行列式为得系数行列式为 nnnnnnnnxxxxxxVxxxxxx2000211101211(,)1 ninnijijVxxxxx10110(,)()由于由于 时时 ，故所有因子，故所有因子 ，于是于是 即插值多项式存在唯一。即插值多项式存在唯一。ij ijxx ijxx0nnV x xx01(,)0 2001!1.2121 120,9.7 10niinnannnnn如果线性方程组（）的系数行列式不为零，则该方程组有唯一解。若由克莱姆(Cramer)法则求解，则需要计算个阶行列式并作次除法，而每个阶行列式计算需作次乘法，计算量十分惊人。如阶线性方程组 需次乘法。如果用每秒一亿次乘法运算的计算机要。可见其在理论上是绝对正确，但在较大时，在实际计算中确实不30万年可行的。由方程组（由方程组（1.2）求）求 的系数的系数 ，计算量大，计算量大，且难于得到且难于得到 的简单表达式，下面通过找插值的简单表达式，下面通过找插值 基函数的方法，可得到插值多项式基函数的方法，可得到插值多项式 的简单表的简单表 达式。达式。()nP x ia()nP x()nP x拉格朗日插值多项式拉格朗日插值多项式 1.插值基函数插值基函数 定义：若定义：若n次多项式次多项式 在在n+1 个节点个节点 上满足条件上满足条件 则称这则称这n+1个个n次多项式次多项式 为节为节 点上的点上的n次插值基函数。次插值基函数。01(),(),()nl x l xlx01(),(),()nlx l xlx01nxxx 10 10,jkkjlxj knkj2.基函数的构造基函数的构造 由上述定义由上述定义 ，知存在常，知存在常 数数 ，使得，使得 由由 ，可以定出，可以定出 ，进而得到：，进而得到：令令()0,ikl xki011()()()()()iiiinl xA xxxxxxxxiA()1iil xiA011011()()()()()()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx)()()(101nnxxxxxxx则则 于是于是 可改写成可改写成 1011()()()()()niiiiiiinxxxxxxxxx()il x110 1()(),()()niinixl xinxxx3.3.n n次拉格朗日型插值多项式次拉格朗日型插值多项式 是是n+1个个n次插值基本多项式次插值基本多项式 的线性组合，相应的组合系数是的线性组合，相应的组合系数是 即即 是一个次数不超过是一个次数不超过n的多项式的多项式,且满足且满足()nP x()nP x01(),(),()nl x l xlx01,nyyy0 01 10()()()()()nnn nk kkP xy lxy l xy lxy lx()niiP xy0,1,in，。拉格朗日插值多项式的截断误差拉格朗日插值多项式的截断误差 若在若在a,b上用多项式上用多项式 来近似代替来近似代替 函数函数f(x),其截断误差记作其截断误差记作 ，即，即 也称为插值多项式的余项，关于插值也称为插值多项式的余项，关于插值余项估计，有以下定理：余项估计，有以下定理：()nP x()nR x()()()nnR xf xP x()nR x定理：设函数定理：设函数y=f(x)的的n 阶导数阶导数 y=f(n)(x)在在a,b上连续，上连续，y=f(n+1)(x)在在(a,b)上存在，上存在，插值节点为插值节点为ax0 x1xnb,是是n次次 拉格朗日插值多项式，则对任意拉格朗日插值多项式，则对任意x a,b有：有：其中其中(1)1()()()(1)!nnnR xfxn(a,b),，01()()()()nnxxxxxxx()nP x证明证明：由插值多项式的定义，显然有：由插值多项式的定义，显然有 构造辅助函数构造辅助函数 有有 。反复利用。反复利用 Rolle定理，存在定理，存在 (a,b),使得使得g(n+1)()=0,即即 ，结论成立。，结论成立。()()()0,0,1,niiniR xf xP xin nntg tf tP tf xP xx 000 1,ig xg xin 110!nnnff xP xx数值实例数值实例 例求过点例求过点(2,0)(4,3)(6,5)(8,4)(10,1)的拉格的拉格 朗日型插值多项式。朗日型插值多项式。解解：用：用4次插值多项式对次插值多项式对5个点插值个点插值 00112233442 04 36 58 410 1,xyx yxyxyxy0(4)(6)(8)(10)1()(4)(6)(8)(10)(2 4)(2 6)(2 8)(2 10)384xxxxl xxxxx 1(2)(6)(8)(10)1()(2)(6)(8)(10)(42)(4 6)(4 8)(4 10)96xxxxl xxxxx 2(2)(4)(8)(10)1()(2)(4)(8)(10)(62)(64)(6 8)(6 10)64xxxxl xxxxx3(2)(4)(6)(10)1()(2)(4)(6)(10)(82)(84)(86)(8 10)96xxxxl xxxxx 4(2)(4)(6)(8)1()(2)(4)(6)(8)(102)(104)(106)(108)384xxxxl xxxxx40 01 12 23 34 4()()()()()()P xy l xyl xy l xy l xy l x13(4)(6)(8)(10)(2)(6)(8)(10)3849654(2)(4)(8)(10)(2)(4)(6)(10)64961(2)(4)(6)(8)384xxxxxxxxxxxxxxxxxxxx于是有 例例.已知已知 sin0.32=0.314567,sin0.34=0.333487,sin0.36=0.352274,用用Lagrange插值计算插值计算sin0.3367的值，并估计截断误差。的值，并估计截断误差。解解：f(x)=sinx,取取 1202102012010210122120 x xx xx xx xx xx xP xyyyxxxxxxxxxxxx 0011220 32 0 3145670 34 0 3334870 36 0 352274,.,.,.,.,.,.xyx yxy于是有于是有 可以发现，结果有六位有效数字的可以发现，结果有六位有效数字的sin x表表 完全一致。完全一致。4440 7689 100 33670 3145670 00083 89 100 5511 100 3334870 3522740 00040 00080 3303742.sin0.3367P.截断误差为截断误差为 其中其中 故有故有 32012013,!fRxxxxxxxxx x 3201 0 3145670 828coscos.fx01,x x2260 33670 33670 33670 828 0 0167 0 033 0 02330 178 10.sin.1 .6 .RPLagrangeLagrange插值公式优缺点插值公式优缺点 优点：结果清晰、紧凑，适用于作理论优点：结果清晰、紧凑，适用于作理论分析、应用；分析、应用；当节点个数有所变动，整个插值公式发当节点个数有所变动，整个插值公式发生变化，在实际应用时不方便。生变化，在实际应用时不方便。3 逐步线性插值逐步线性插值 抛物插值的逐步线性插值抛物插值的逐步线性插值 Aitken插值插值 Neville算法算法 数值实例数值实例 小结小结 1.1.抛物插值的逐步线性插值抛物插值的逐步线性插值 给定如下三个数据点给定如下三个数据点 逐步线性插值（逐步线性插值（Aitken插值）具体步骤如下：插值）具体步骤如下：Step1.将将 分别对分别对 两点作线两点作线 性插值，得性插值，得 0 x0 x0 x0 x0yy1y2y 1122,x yxy00,x y step2.对对 两点作线性两点作线性插值，得插值，得 01010101100202020220 xxxxPxyyxxxxxxxxPxyyxxxx 101202,x Pxx Px 2101201021221xxxxPxPxPxxxxx 显然显然 插值节点插值节点 ；插值节点插值节点 ；插值节点插值节点 。2.n 次次 Aitken 插值插值 设给定数据表设给定数据表 01Px 012Px 02Px 0022,x yx y00,x y 0011,x yx y 1122,x yxyxy0 xnx1x0y1yny构造构造 n次多项式，步骤