《数值分析课件ch02插值法》由会员分享,可在线阅读,更多相关《数值分析课件ch02插值法(93页珍藏版)》请在金锄头文库上搜索。
1、1,第二章 插值法,2,插值法,许多实际问题都用函数来表示某种内在规律的数量关系但函数表达式无法给出,只有通过实验或观测得到的数据表函数表达式已知,但较复杂,计算函数值或积分比较困难如何根据这些数据推测或估计其它点的函数值?,问题的提出,3,问题的数学提法,求简单函数Pn(x),使得,P(x),4,插值基本概念,已知函数 y = f(x) 在 a, b 上有定义,且已经测得在点 a x0 x1 xn b 处的函数值为 y0 = f(x0), ,yn = f(xn),如果存在一个简单易算的函数 P(x),使得P(xi) = f(xi),i = 0, 1, . , n 则称 P(x) 为 f(x)
2、 的插值函数,求插值函数 P(x) 的方法就称为插值法,5,其插值函数的图象如图,6,常用插值法,多项式插值:P(x) 为多项式函数 - 最常用的插值函数,分段插值:P(x) 为分段多项式函数,三角插值:P(x) 为三角函数, ,多项式插值 polynomial interpolation,Weierstrass定理 对于在a,b上的连续函数f以及,总存在多项式P(x)满足,7,多项式插值,对于多项式插值,我们主要讨论以下几个问题:,满足插值条件的多项式 P(x)是否存在且唯一? 若满足插值条件的P(x)存在,又如何构造出P(x);即插值多项式的常用构造方法有哪些? 用P(x)代替f(x)的误
3、差估计 当插值节点无限加密时,插值函数是否收敛于f(x)。,8,插值多项式的存在唯一性 Existence and Uniqueness of interpolation polynomials?,且满足,9,上述方程组的系数行列式为n+1阶Vandermond行列式,插值多项式的存在唯一性,定理,已知函数 y = f(x) 在 a, b 上 n + 1 个点 a x0 x1 xn b 处的函数值为 y0 = f(x0), ,yn = f(xn),求次数不超过 n 的多项式 P(x) = c0+c1x + + cnxn,使得 P(xi) = yi,i = 0, 1, . , n 存在且唯一,1
4、0,关于唯一性证明的几点说明,插值多项式的唯一性表明,对同一组节点,它们的插值多项 式是唯一的,可能由不同的方法,会得到不同形式的插值多 项式,但它们之间一定可以相互转化,一定会相同,当然误差也一样。上述证明是构造性的(给出解决问题的方法)即以通过解线 性方程组来确定插值多项式,但这种方法的计算量偏大,计算步骤较多,容易使舍入误差增大。因此实际计算中不采用 这种方法,而用下面介绍的几种常用的方法。,11,基函数插值法,通过基函数来构造插值多项式的方法就称为基函数插值法,Zn(x) = 次数不超过 n 的多项式的全体,记,若通过前述方法来求解插值多项式,不但计算工作量较大,且难于得到简单表达式,
5、12,Lagrange插值,十八世纪法国数学家Lagrange提出了易于掌握和计算的统一公式称为Lagrange插值公式,线性插值,已知两个插值点及其函数值:,求一次多项式 first-degree polynomial,使得:,13,线性插值,所以,按Cramer法则,有唯一解,点斜式,两点式,14,线性插值,的线性组合得到,即:,注意到:,称 , 为线性插值基函数,由两点式看出, 是由两个线性函数,15,抛物线插值,求一个二次多项式,使得:,抛物线插值,16,抛物线插值,令:,17,抛物线插值,所以,为二次插值基函数,18,Lagrange插值,设 lk(x) 是 n 次多项式,在插值节点
6、 x0 , x1 , , xn 上满足,则称 lk(x) 为节点 x0 , x1 , , xn 上的拉格朗日插值基函数,n 次Lagrange插值,19,P(x) = y0l0(x) + y1l1(x) + + ynln(x),Lagrange插值,Lagrange插值公式的标准型公式:,20,插值举例,例:已知函数 y = lnx 的函数值如下,解:,试分别用线性插值和抛物线插值计算 ln 0.54 的近似值,为了减小截断误差,通常选取插值点 x 邻接的插值节点,21,插值举例,抛物线插值:取 x0=0.4, x1=0.5, x2=0.6, 可得,ln 0.54 L2(0.54) =-0.6
7、153,在实际计算中,不需要给出插值多项式的表达式,Lagrange插值多项式简单方便,只要取定节点就可写出基函数,进而得到插值多项式,易于计算机实现。,22,matlab program,function s=Lagrange(x0,y0) n=length(x0);%取长度 s=0; for j=0:(n-1)t=1;for i=0:(n-1)if i=jt=t*(x-x0(i+1)/(x0(j+1)-x0(i+1);endends=s+t*y0(j+1); end s,23,误差估计,如何误差估计:,24,插值余项,由插值条件可知: Rn(xi)=0, i=0, 1, , n,Rn(x)
8、 在a,b上至少有 n+1 个零点,对任意给定的 xa,b (x xi , i =0, 1, ., n),构造辅助函数,则 在 a, b 中有 n+2 个互不相同的零点:x, x0 , , xn,Rn(x) 可写成,25,插值余项,由Rolle定理可知 在 (a, b) 内至少有 n+1 个不同的零点;,同理可知 在 (a, b) 内至少有 n 个零点;,又,f(x) Cna, b,且 f (n+1)(x) 在 (a, b) 内存在,以此类推,可知 在 (a, b) 内至少有一个零点,设为 x ,即 ,x (a, b)。,26,注,余项公式只有当 f(x) 的高阶导数存在时才能使用,从余项Rn
9、(x)中的n+1(x)知,当点x位于x0, x1, xn的中部时,比较小,精度要高一些;而位于两端时,精度要差一点;若x位于x0, x1, xn的外部,一般称为外 插,此时精度一般不理想,使用时必须注意。,27,Lagrange基函数性质,当 f(x) 为一个次数 n 的多项式时,有 故即 n 次插值多项式对于次数 n 的多项式是精确的,28,插值误差举例,例:已知函数 y = lnx 的函数值如下,试估计线性插值和抛物线插值计算 ln 0.54 的误差,29,插值误差举例,抛物线插值:,x0=0.4, x1=0.5, x2=0.6, (0.4, 0.6),高次插值通常优于低次插值,但绝对不是
10、次 数越高就越好,嘿嘿 ,30,Lagrange插值优点和缺点,优点,公式简洁, 理论分析方便容易编程上机,缺点,基函数计算复杂,计算量大 ,计算量为每增加一个节点,插值多项式的所有系数都得重算;,31,第二章 插值法, Newton 插值法,32,Newton 插值,为什么 Newton 插值,Lagrange 插值简单易用,但若要增加一个节点时,全部基函数 lk(x) 都需重新计算,不太方便。,33,新的基函数,设插值节点为 x0 , , xn ,考虑插值基函数组,当增加一个节点 xn+1 时,只需加上基函数,34,Newton 插值,此时 f(x) 的 n 次插值多项式为,35,Newt
11、on 插值,再继续下去待定系数的形式将更复杂 为此引入差商的概念,36,差商,什么是差商,设函数 f(x),节点 x0 , , xn,37,差商的性质,差商可以表示为函数值的线性组合:用归纳法可以证明,38,差商的性质,k 阶差商与 k 阶导数之间的关系:若 f(x) 在 a,b 上 具有 k 阶导数,则至少存在一点 (a, b),使得,若f(x)是n次多项式,则一阶差商fx,xi是n 1次多项式。,39,差商的计算,40,差商举例,例:已知 y = (x) 的函数值表,试计算其各阶差商,解:差商表如下,41,Newton 插值公式,Newton 插值公式,由差商的定义可得, ,Nn(x),R
12、n(x),42,Newton 插值公式,f (x) = Nn(x) + Rn(x),其中,43,注,且余项相同,44,注,牛顿插值公式利用差商可简单地表为,因此, 每增加一个结点, Newton 插值多项式只增加一项, 克服了 Lagrange 插值的缺点。,45,注,在实际计算中,特别是在函数f(x)的高阶导数比较复杂或 f(x)的表达式没有给出时,我们可以用差商表示的余项公 式来估计误差。,实际计算中,当n+1阶差商变化不激烈时,可用近似代替,Newton插值多项式需要除法 次,及2n次乘法, 大 约比Lagrange公式节省3到4倍工作量 .,46,插值举例,例,给出 的函数表(见表2-
13、2),求4次牛顿插 值多项式,并由此计算 的近似值.,首先根据给定函数表造出均差表.,47,插值举例,按牛顿插值公式,将数据代入,于是,截断误差,这说明截断误差很小,可忽略不计.,48,第二章 插值法, Hermite 插值法,49,Hermite插值,在许多实际应用中,不仅要求函数值相等,而且要求若干阶导数也相等,如机翼设计等。,(i = 0, 1, , n),满足函数值相等且导数也相等的插值方法成为 Hermite插值,50,Hermite插值,典型的 Hermite 插值,两点三次 Hermite 插值,插值节点:x0 , x1 插值条件:P(xi) = f(xi),P(xi) = f(
14、xi) ,i = 0, 1,考虑插值问题,插值条件2n+2个,确定2n+2个待定系数。因此插值多项式最高次为2n+1,51,两点三次Hermite 插值,插值节点:x0 , x1 插值条件:P(xi) = f(xi) = yi,P(xi) = f(xi) = mi,i = 0, 1,模仿 Lagrange 多项式的思想,设,其中 均为 3 次多项式,且满足,i, j= 0, 1,52,两点三次Hermite 插值,将插值条件代入立即可得,0(x), 1(x), 0(x), 1(x) 的表达式?,53,两点三次Hermite 插值,0(x),54,两点三次Hermite 插值,同理可得,55,两
15、点三次Hermite 插值,满足插值条件,P(x0) = f(x0) = y0,P(x0) = f(x0) = m0 P(x1) = f(x1) = y1,P(x1) = f(x1) = m1,的三次 Hermite 插值多项式为,余项,56,非标准型Hermite插值,例如 求满足下列条件的ermite插值多项式。,基本方法为待定系数法利用重节点差商构造Hermite插值,57,三点三次Hermite 插值,插值节点:x0 , x1 , x2 插值条件:P(xi) = f(xi),i = 0, 1, 2,P(x1) = f(x1),设,将 P(x1) = f(x1) 代入可得,58,三点三次Hermite 插值,由于 x0 , x1 , x2 是 R(x) 的零点,且 x1 是二重零点,故可设,余项公式,与 Lagrange 插值余项公式的推导过程类似,可得,