《数值分析课件chapter2章节》由会员分享，可在线阅读，更多相关《数值分析课件chapter2章节（74页珍藏版）》请在金锄头文库上搜索。
1、1,第二章 函数基本逼近(一) -插值逼近,2,许多实际问题都用函数 来表示某种内在规律的数量关系,其中相当一部分函数是通过实验或观测得到的.虽然 在某个区间a，b上是存在的，有的还是连续的，但却只能给出a,b上一系列点 这只是一张函数表；有的函数虽然有解析表达式,但由于计算复杂,使用不方便,通常也构造一个函数表。如三角函数表、对数表、平方根表、立方根表等等。,3,若经测量或实验得到某一函数y=f(x)在一系列点 处的值 即如下数据点：,则 希望找到易于计算的函数 且满足 这类问题称为插值问题。,4,插值函数,几何解释,（插值）节点,插值条件,插值函数就是通过n+1个给定点 的几何曲线。,插值
2、区间,5,对于给定的插值节点, 选用多项式作为插值函数进行插值， 即构造n次多项式 使满足插值条件 这类问题称为多项式插值问题。,插值函数可以是多项式、有理分式、三角函数、指数 函数等。本章只讨论多项式插值，即,6,1 拉格朗日多项式 /* Lagrange Polynomial */,7,每个 li 有 n 个根 x0 xi-1 xi+1 xn,=,-,=,n,j,j i,j,i,i,x,x,C,x,l,0,),(,),(,Lagrange 多项式,与 有关，而与 无关,节点,f,线性插值,9,二次插值,10,例：已知 ,求插值多项式,11,证明： ( ),反证：若不唯一，则除了Ln(x)
3、外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。,考察 则 Qn 的阶数, n,而 Qn 有 个不同的根,注：若不将多项式次数限制为 n ，则插值多项式不唯一。,例如 也是一个插值多项式，其中 可以是任意多项式。,3,12,13,每个 li 有 n 个根 x0 xi-1 xi+1 xn,=,-,=,n,j,j i,j,i,i,x,x,C,x,l,0,),(,),(,Lagrange 多项式,与 有关，而与 无关,节点,f,14,15, 插值余项 /* Remainder */,Rolles Theorem: 若 充分光滑， ，则 存在 使得 。,推广：若,使得,Rn(x)
4、 至少有 个根,n+1,(t)有 n+2 个不同的根 x0 xn x,注意这里是对 t 求导,16,注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。,当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的。,17,解：,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,这里,而,sin 50 = 0.7660444,外推 /* extrapolation */ 的实际误差 0.01010,利用,内插 /* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x
5、所在的区间的端点，插值效果较好。,18,n = 2,sin 50 = 0.7660444,2次插值的实际误差 0.00061,高次插值通常优于低次插值,但绝对不是次数越高就越好，,19,计算机上算法实现,在计算机上实现：,20,Lagrange插值算法,21,22,Lagrange插值公式的优缺点：,优点：形式简洁 便于理论分析和许多数值计算公式的推导 缺点：没有承袭性 即当增加新的节点时 所有Lagrange因子必须重新计算,23,作业: p.56-58 1题(1), 2题，3题, 6题, 7题，10题,24,2 牛顿插值 /* Newtons Interpolation */,Lagran
6、ge 插值虽然易算，但若要增加一个节点时，全部基函数 li(x) 都需重新算过。, 差商(亦称均差) /* divided difference */,1阶差商,2阶差商,25,(k+1)阶差商：,差商的值与 xi 的顺序无关！,26, 牛顿插值 /* Newtons Interpolation */, ,Nn(x),Rn(x),ai =,f x0, , xi ,4,27,注： 由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其余项也相同，即, 实际计算过程为,f (x0) f (x1) f (x2) f (xn1) f (xn),f x0, x1 f x1, x2 f xn1, xn
7、,f x0, x1 , x2 f xn2, xn1, xn,f x0, , xn,f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1,28,差商表,29,30,31, 等距节点公式 /* Formulae with Equal Spacing */,向前差分 /* forward difference */,向后差分 /* backward difference */,中心差分 /* centered difference */,其中,当节点等距分布时:,32, 差分的重要性质：, 线性：例如, 若 f (x)是 m 次多
8、项式，则 是 次多项式，而, 差分值可由函数值算出：, 函数值可由差分值算出：,33,牛顿公式, 牛顿向前插值公式, 牛顿向后插值公式,将节点顺序倒置：,注：一般当 x 靠近 x0 时用牛顿向前插值公式，靠近 xn 时用牛顿向后插值公式。,34,3 埃尔米特插值 /* Hermite Interpolation */,现代的仿生学就是一个典型的例子。在设计交通工具的外形，就是参照海豚的标本上已知点及已知点的导数，做插值在计算机上模拟海豚的外形制成飞机、汽车等外形。,Lagrange插值公式所求的 保证了节点处的函数值相等，从而保证了函数的连续性，但不少实际问题还需要插值具有光滑度，即要求在节点
9、处的导数值也相等。导数的阶数越高则光滑度越高。,35,不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), , (mi) (xi) = f (mi) (xi).,注： N 个条件可以确定 阶多项式。,N 1,一般只考虑 f 与f 的值。,36,例：设 x0 x1 x2, 已知 f(x0)、 f(x1)、 f(x2) 和 f (x1), 求多项式 P(x) 满足 P(xi) = f (xi)，i = 0, 1, 2，且 P(x1) = f (x1), 并估计误差。,模仿 Lagrange 多项式的思想，设,解：
10、首先，P 的阶数 =,3,h0(x),有根,x1, x2，且 h0(x1) = 0 x1 是重根。,又: h0(x0) = 1 C0,h2(x),h1(x),有根 x0, x2 ,由余下条件 h1(x1) = 1 和 h1(x1) = 0 可解。,与h0(x) 完全类似。,有根 x0, x1, x2 ,与 Lagrange 分析完全类似,37,一般地，已知 x0 , , xn 处有 y0 , , yn 和 y0 , , yn ，求 H2n+1(x) 满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。,解：设,hi(x),由余下条件 hi(xi) = 1 和 hi(xi) =
11、 0 可解Ai 和 Bi ,有根 x0 , , xn, 除了xi 外都是2重根 ,这样的Hermite 插值唯一,38, 求Hermite多项式的基本步骤：, 根据多项式的总阶数和根的个数写出表达式；, 根据尚未利用的条件解出表达式中的待定系数；, 最后完整写出H(x)。,39,问题：是否节点越密，插值函数越接近原函数？,（1）收敛性问题,Runge的例子：原函数,取插值节点,建立n次插值多项式,观察n逐渐增大时 与原函数的接近程度。,4 分段低次插值 /* piecewise polynomial approximation */,40,41,42,43,n 越大， 端点附近抖动 越大，称为
12、 Runge 现象,44,结论：并非节点越密，插值函数越接近原函数。,实际应用中通常采用分段低次多项式插值。,以上随n增大，插值多项式反而远离原函数的现象 称为Runge现象。,45,Newton向前插值多项式：,，则：,若,不精确，成为,（2）数值稳定性问题,46,这时,若：,则：,. 得表：,47,48,算法数值稳定性得不到保证 舍入误差严重影响高阶差商或差分的准确性 最终严重影响到插值结果的精度.,49, 分段线性插值 /* piecewise linear interpolation */,在每个区间 上，用1阶多项式 (直线) 逼近 f (x):,50,51, 分段Hermite插值
13、 /* Hermite piecewise polynomials */,6,其误差估计：,记,有：,52,5 三次样条 /* Cubic Spline */,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,f(x),H(x),S(x),53, 构造三次样条插值函数的三弯矩法 /* method of bending moment */,对每个j, 此为3次多项式,则 Sj”(x) 为 次多项式，需 个点的值确定之。,1,2,设 Sj”(xj1) = Mj1， Sj
14、”(xj) = Mj,对应力学中的梁弯矩，故名,对于x xj1, xj 可得到,Sj”(x) =,积分2次，可得 Sj(x) 和 Sj(x) ：,54,55,下面解决 Mj ：,利用S 在 xj 的连续性,xj1, xj : Sj(x) =,xj , xj+1: Sj+1(x) =, j ,1,n1,即：有 个未知数， 个方程。,n1,n+1,还需2个边界条件 /* boundary conditions */,56, 第1类边界条件 /* clamped boundary */： S(a) = y0， S(b) = yn,类似地利用 xn1, b 上的 Sn(x),57, 第2类边界条件： S”(a) = y0” = M0， S”(b) = yn” = Mn,这时：,58, 第3类边界条件 /* periodic boundary */ ： 当 f 为周期函数时， yn = y0 ， S(a+) = S(b) ， S” (a+) = S”(b) M0 = Mn,59,例 给定插值条件,附加边界条件为：,.试求,满足上述条件的三次插值样条函数的分段表达式.,解：（三弯矩方法）,利用二阶导数,为待定参数,得,60,边界条件方程
