《数值计算插值法与最小二乘法插值法》由会员分享,可在线阅读,更多相关《数值计算插值法与最小二乘法插值法(44页珍藏版)》请在金锄头文库上搜索。
1、第三章 插值法与 最小二乘法,张红梅自动化学院2010年3月,数值计算方法,3.4 Newton 插值法,Lagrange 插值多项式的基函数:,优点:形式对称,有很强的规律性,便于记忆。,缺点:,(1) 重复计算多, 导致计算量大;,(2) 插值基函数 lj(x) 依赖于所有节点,当增加插值节点时,原来已算出的所有 lj(x) 都需要重新计算,使计算量加大。,Newton插值基函数 差商的定义和性质 差商表示的Newton插值多项式 差分的定义和性质 差分表示的Newton插值多项式,3.4 Newton 插值法,Newton (16241727),问:是否可以将这 n+1个多项式作为插值基
2、函数?,已知函数 f(x) 的插值节点 xi 及相应函数值 ,将上述线性无关的多项式取作Newton插值法的基函数,即令:,Newton插值基函数,则相应的插值多项式为:,式中, 为待定参数,它们可利用插值条件 来求,即令:,可以求得:,依此类推,可求得 .为标记、推导、记忆方便,给出均差定义,可得参数 的一般表达式。,为 关于节点 的一阶均差(差商),4-1 均差(差商),1.均差的定义:设给定函数 在 个互异的节点 处的函数值为 ,称,为 关于节点 的二阶均差(差商),缺倒数第二个节点,缺最后一个节点,最后一个节点倒数第二个节点,称,可见:一个高阶差商可由两个低一阶的差商得到,缺倒数第二个
3、节点,缺最后一个节点,称,为 关于节点 的 k 阶均差(差商),最后一个节点倒数第二个节点,由此定义,显然:,将上述结果代入:,2.差商的性质,例如:,利用对称性,可对 f(x) 关于 的 k 阶差商变形,注:上式是计算中常用的差商公式,可建立差商表.,缺第一个节点,缺最后一个节点,最后一个节点第一个节点,性质2:对称性 差商对于定义它的节点而言是对称的,也就是说任意调换节点的次序,差商的值不变,3. 差商的计算方法:差商表,规定函数值为零阶差商,补充两个性质,证明:稍后证明。,证:,等号右端分子是 m 次多项式,且当 x = xk +1 时,分子为0,故分子中必有因子 x xk +1 ,与分
4、母相消后,右端为 m -1次多项式.,性质5: 若 f(x) 是次数不超过 k 的代数多项式,则它的 k+1阶差商为零.,证: f (x)是 k 次多项式,则 f x, x0 是 k-1次多项式, f x, x0, x1 是 k-2次多项式,依此类推, k 阶差商 是0次多项式,即是常数,所以,性质4: 若 是 x 的 m 次多项式, 则 是 x 的 m -1次多项式,内容回顾,上次课中,给出Newton插值基函数:,并形式上给出Newton插值多项式:,式中, 待定.,通过引进均差/差商的概念,可以将系数表示为:,4-2 Newton插值公式及其余项公式,为 f (x) 关于节点 的 n 次
5、Newton插值多项式.,1.定义: 称,- (1),由插值多项式的唯一性, Newton 插值公式的余项为:,实用的余项估计式:,若将 视为一个节点,则由一阶均差定义,2. Newton插值余项的另一种表示,同理,由二阶均差定义,有,有,因此可得:,Newton插值多项式,差商型余项,- (3),因此,推广得:,4. Newton插值估计误差的实用公式:,3. 性质3 的证明,- (4),5. 分段Newton插值,用Newton插值法也要避免使用高次插值,当采用分段插值时,也应选择靠近插值点的节点作插值节点,这可减小截断误差.同Lagrange插值一样,计算前先确定插值点 x 属于哪一个子
6、区间,然后根据插值多项式的次数,选择靠近 x 的节点.,例1.已知 f (x) 的函数表如下所示:,用分段三次Newton插值多项式计算 f (0.596)的近似值,并估计误差.,解,并根据插值点 0. 596 在均差表中的位置,选择插值节点.,首先构造均差表,1.1161.1861.275731.384101.51533,0.280.358920.433480.52492,0.19730.213030.2286,0.031460.03114,-4.92310-4,如何选择插值节点?,插值多项式为:,截断误差为:,6. Newton向后插值公式,变为,同理,当 x 位于表末时, 可采用Newt
7、on向后插值公式进行计算. 此时, 可将节点视为按 的顺序排列, 即将,- (1),-(5),Newton向后插值公式,Newton向后插值余项公式,由均差的对称性,可知,因此,公式(5)和公式(1)中的各阶均差可在同一均差表中找到.,例2.利用例1中的均差表,用三次 Newton 插值多项式计算 f(0.955) 的近似值并估计误差.,解,根据插值点 0.955 在均差表中的位置,选择插值节点.,1.1161.1861.275731.384101.51533,0.400.550.650.800.901.05,0.410750.578150.696750.888111.026521.25382
8、,0.280.358920.433480.52492,0.19730.213030.2286,0.031460.03114,-4.92310-4,如何选择插值节点?,插值多项式为:,截断误差为:,4-3 差分,定义4.2 设 f (x) 在等距节点 处的函数值为 称,为 f (x)在 xk 处的 二阶向前差分,为 f (x)在 xk 处的 二阶向后差分,为 f (x)在 xk 处的 一阶向前差分,为 f (x)在 xk 处的 一阶向后差分,等距节点插值是比较常见的情况,为简化计算,引进差分的概念.,依此类推:,为 f (x)在 xk 处的 m 阶向前差分,为 f (x)在 xk 处的 m 阶向
9、后差分,向前差分和向后差分具有如下关系,由差分的定义和数学归纳法可以证明:,性质:,一阶差分:,二阶差分:,m 阶差分:,差分的计算方法:差分表,在等距节点的前提下,差商与差分有如下关系:,差商与差分的关系,依此类推:,4-4 差分表示的 Newton 插值公式,1. Newton向前(差分)插值公式及余项公式,记插值点:,如果节点 是等距的, 即,-(7),由均差与向前差分的关系:,-(6),以及,式(7)、(6)代入差商表示的插值公式:,-(8),Newton向前(差分)插值公式,得差分表示的 Newton 插值公式化为:,Newton 插值多项式的余项公式,节点等距时, 化为,-(9),
10、若由差分近似代替导数,上式可化为:,-(10),实用的估计式:,2. Newton向后(差分)插值公式及余项公式,则:,Newton 向后插值基本公式为:,当 x 位于表末时, 设:,Newton向后(差分)插值公式:,同时可得 Newton向后(差分)插值余项公式:,导数形式余项公式:,差分形式余项公式:,实用的估计式:,例3:,给定 f (x) = cos x 的函数表如下:,用四次Newton插值多项式计算cos0.048及cos0.566的近似值,并估计误差.,先构造差分表,解,再根据插值点在表中的位置选择插值节点.,-0.00500-0.01493-0.02473-0.03428-0
11、.04348-0.05224,-0.00993-0.00980-0.00955-0.00920-0.00876,0.000130.000250.000350.00044,0.000120.000100.00009,-0.00002-0.00001,0.00001,分别需要几个插值节点?如何选择?,显然, h = 0.1,当 x = 0.048 时, 用前向公式,当 x = 0.566 时, 用后向公式,当函数f(x)的解析式未知, 而仅知其在某区间上的函数表时, 如何求其在 a, b 上的零点呢?,一般地, 可先求 f(x) 在a,b上的插值函数 y(x), 然后求 y(x)的零点, 把此零点
12、作为 f(x) 的近似零点. 特别地, 若 f(x)的反函数存在, 记为 x = g(y). 于是求 f(x) 的零点问题就变成求函数值g(0) 的问题了. 若用插值法构造出 g(y), 从而可求得的零点的近似值. 称上述方法为“反插值”.,注: 反插值的条件是函数 y=f(x) 有反函数, 即要求 y=f(x) 单调.,本题中, 因为 yi 是按严格单调下降排列, 所以可用反插值法求f(x) 零点的近似值. 具体做法是, 先把原表变成反函数表:,-0.064516-0.095238,0.001182,然后构造反函数均差表:,根据上表, 构造 2 阶Newton插值公式:,由此得原函数 y = f(x) 在0,2上的零点为:,事实上, 此题中 在 0,2 之间的零点为 x*= 0.5,注: 当所给函数表不满足严格单调的条件时, 在利用反插值求根时会出错.,优点: 计算较简单, 尤其是增加节点时,计算只要增加一项, 这是Lagrange插值无法相比的.,缺点: 分段Newton插值仍然没有改变分段Lagrange插值的缺点,即插值曲线在节点处有尖点、不光滑、插值多项式在节点处不可导等缺点.,Newton 插值法的特点,