第一讲-插值方法

1、19761976年出生年出生于云南宣威于云南宣威，乌蒙山。，乌蒙山。2000-20032000-2003在在西安交通大学西安交通大学，博士。，博士。1997-20001997-2000在在兰州大学，学兰州大学，学士和硕士。士和硕士。2003-20112003-2011电子电子科技大学，数学科技大学，数学学院教学学院教学20122012至今至今华东理工华东理工大学。大学。计算方法的研究目标：计算方法的研究目标：研究科学问题的求解方法和过程设计研究科学问题的求解方法和过程设计科学问题科学问题模型建立模型建立计算方法和算法设计计算方法和算法设计程序语言程序语言结论展示或集成系统结论展示或集成系统研究

2、内容研究内容信息安全；信息安全；云计算；云计算；大数据；大数据；物联网；物联网；决策支持等决策支持等42022-4-29 3 54 3 32 插值平均插值平均 Lagrange插值公式插值公式Aitken逐步插值算法逐步插值算法插值逼近插值逼近分段插值分段插值 3 1样条插值样条插值6 3 7曲线拟合的最小二乘法曲线拟合的最小二乘法52022-4-29实例实例1求求 sin3813查查 函函 数数 表表sinx62022-4-29实例实例2xy机翼下轮廓线求机翼下轮廓线上一点的近似数值求机翼下轮廓线上一点的近似数值该点的值是多少该点的值是多少?72022-4-29v对于诸如此类的问题，设法利用

3、已给数据表求出给定点x的函数值y，称为插值。目的在于通过尽可能简便的方法，利用所给数据表加工出插值点x上具有足够精度的插值结果yvxi 称为插值节点，所要插值的点x称为插值点v现在的考虑：能否通过对表中数据进行适当的加权平均来得到想要的插值结果？即用y来近似f(x) ，其中v可以，关键在于i的选取yxf)(niiiniiixfyy00)(82022-4-29v 定义1：称近似关系式 具有m阶精度，如果它对于次数m的多项式均能准确成立v 特别地，当y1时， 。所以，插值方法是平均化的过程，故称为插值平均niiiyxf0)(nii01插值的几何意义插值的几何意义92022-4-29102022-4

4、-29 2. Lagrange（拉格朗日）（拉格朗日）插值公式n 两点插值：u 形式形式u 插值公式插值公式n 三点插值：n 形式形式n 插值公式插值公式1100yyy10100101yxxxxyxxxxy221100yyyy212021012101200201021)()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxy112022-4-29n 多点插值：u 形式形式u 插值公式插值公式 niiiyy0ininijjjijyxxxxy 00Lagrange插值公式特点：插值公式特点：各节点地位相同，形式对各节点地位相同，形式对称，但增加节点时，所有系数需要重新计算称，

5、但增加节点时，所有系数需要重新计算122022-4-29例：利用例：利用100、121和和144开平方值计算开平方值计算115解：解： 令令 ，利用三点，利用三点Lagrange公式公式xy 212021012101200201021)()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxy221100yyyy其中：其中：x0=100, y0=10, x1=121, y0=11, x2=144, y2=12, x=115，将这些信息代入上面的公式，有，将这些信息代入上面的公式，有7228.10115 同精确值比较，该结果有同精确值比较，该结果有4位有效数字。位有效数字。1

6、32022-4-293. Aitken（埃特金）（埃特金）逐步插值算法n 化三点插值为两点插值：u 对于点对于点 (x0, y0), (x1, y1)和(x0, y0), (x2, y2)u 插值公式插值公式u 以以(x1, y01), (x2, y02)作为节点构造两点插值公式：作为节点构造两点插值公式：1010010101yxxxxyxxxxy2020020202yxxxxyxxxxy021210121212yxxxxyxxxxy142022-4-29 Aitken逐步插值算法：x0 y0 x1 y1x2 y2x3 y3x4 y4xn yny01y02y03y04y0ny12y13y14y

7、1ny23y24y2ny34y3nyn-1,nn+1点插值点插值 n点插值点插值 n-1点插值点插值 1点插值点插值 152022-4-29例：用下表中第例：用下表中第1、2列的值求解列的值求解f(0.462)的值的值xdtttxfsin)(解：解： 利用所给数值及利用所给数值及Aitken公式，有公式，有 xi yi y0i y1i y2i456557.0sin)(xdtttxf162022-4-29Neville（内维尔）逐步插值算法：x0 y0 x1 y1x2 y2x3 y3x4 y4xn yny01y12y23y34yn-1,ny02y13y24yn-2,ny03y14yn-3,ny0

8、4yn-4,ny0,nn+1点插值点插值 n点插值点插值 n-1点插值点插值 1点插值点插值 172022-4-29vAitken算法和Neville算法是逐步插值的两种基本形式v共同特点：都是将高阶插值逐步归结为线性插值（最简单、最基本）的重复182022-4-29u*x*y求任一插值点求任一插值点)(*ixx 处的插值处的插值.*y0 x1xnx0y1y这些点可视为由这些点可视为由y=f(x)产生，但产生，但f表表达式复杂，或根达式复杂，或根本无法提供本无法提供已知已知 n+1个点个点, 1 , 0(),(niyxii其中其中ix互不相同，不妨设互不相同，不妨设),10bxxxan问题的提

9、出问题的提出 4. 插值逼近192022-4-290 x1xnx0y1y 构造一个相对简单的函数构造一个相对简单的函数),(xgy 通过全部点，即通过全部点，即), 1 , 0()(niyxgii再用再用)(xg计算插值，即计算插值，即).(*xgy u*x*y求解插值问题的基本思路求解插值问题的基本思路202022-4-29插值与逼近插值与逼近u 上述过程就是逼近过程，上述方法就称为逼近方法，即构造一个简单函数构造一个简单函数g(x)作为作为f(x)的近似的近似，然后通过处理，然后通过处理g(x)获得关于获得关于f(x)所要的结果所要的结果u 插值方法是逼近方法的一种u 如果要求逼近函数g(

10、x)与其所逼近的函数f(x)在若干节点上取相同的离散信息（函数值、导数值），这种逼近方法称为插值方法，逼近函数g(x)称为插值函数 212022-4-29u 如果限定插值函数为代数多项式pn(x)。这类插值方法称为代数插值，相应的插值函数称为插值多项式u 如果插值函数为分段多项式，就称为分段插值，如果为三角多项式，就称为三角插值u 本章只讨论代数插值和分段插值 我们的问题是如何确定我们的问题是如何确定 ?.)(2210nnnxxxxp)(*xpyn 进而求得进而求得 222022-4-29事实上，方程组的解事实上，方程组的解0, 1, , n存在且唯一。解出存在且唯一。解出i (i=0, 1,

11、 2, , n)， pn(x)就可构造出来了。但遗憾的是就可构造出来了。但遗憾的是此此方程组是病态方程组，方程组是病态方程组，当阶数当阶数n越越高时，病态越重高时，病态越重。为此我们从另一途径来寻求获得为此我们从另一途径来寻求获得pn(x)常用的代数插值方法常用的代数插值方法 Taylor插值 Lagrange插值 Hermite插值232022-4-29Taylor插值插值 在给定点x0邻近用Taylor展开式 pn(x) 来逼近： nnnxxnxfxxxfxxxfxfxp)(!)(.)(2)()()()(00)(200000 nixfxpiin, 1 ,0 )()(0)(0)( 该多项式满

12、足： Taylor插值的特点：插值的特点：原理简单，但要求插值函数原理简单，但要求插值函数p(x)与所逼与所逼近的函数近的函数f(x)在展开点在展开点x0处具有相同的直到处具有相同的直到n阶的导数值阶的导数值 242022-4-29kx1 kxky1 ky)(xfy )(1xpy Lagrange 插值插值线性插值(n=1)：假定给定区间xk,xk+1及端点的函数值111)()()(kkkkyxyxxp252022-4-29)()(111kkkkkkxxxxyyyxp)(点斜式点斜式11111)(kkkkkkkkyxxxxyxxxxxp)(两点式两点式令令,)(11kkkkxxxxxkkkkx

13、xxxx11)(上满足条件上满足条件及及在节点在节点1 kkxx. 1, 0; 0)(, 11111kkkkkkkkxxxxkx1 kx10)(xk)(1xk插值基函数插值基函数262022-4-29)()()()()()(11112kkkkkkxfxxfxxfxxp）（1 kx1 kx10)(xk)(1xkkx)(1xk基基函函数数的的图图形形同理，当n=2时，即利用二次插值基函数立即得到二次插值多项式插值基函数满足条件1, 1 0)( , 1)(kkjxxjkkk272022-4-29n 2时，插值多项式nkkknxfxxp0)()()(nkxxxxxnkjjjkjk, 1 ,0 )(0插

14、值基函数优点优点: 结构紧凑结构紧凑, 理论分析方便理论分析方便 缺点缺点: 改变一个节点则全改变一个节点则全部的插值基函数都改变，部的插值基函数都改变，即节点增加，基函数失效即节点增加，基函数失效 282022-4-29.352274. 0,36. 0,333487. 0,34. 0,314567. 0,32. 0221100yxyxyx得得)3367. 0(3367. 0sin1p)3367. 0(001010 xxxyyy330365. 00167. 002. 001892. 0314567. 0,333487. 034. 0sin314567. 032. 0sin，已给已给)3367.

15、 0sin(3522787. 036. 0sin计算计算值值，用线性插值及抛物插，用线性插值及抛物插例例由题意取由题意取解解用线性插值计算，取用线性插值计算，取 x0=0.32、x1=0.34292022-4-290201021)()(3367. 0sinyxxxxxxxx21202101210120)()()()(yxxxxxxxxyxxxxxxxx330374. 0)3367. 0(2 p 这个结果与六位有效数字的正弦函数表完全一样，这个结果与六位有效数字的正弦函数表完全一样，这说明查表时用二次插值精度已相当高了。这说明查表时用二次插值精度已相当高了。时，时，用抛物插值计算用抛物插值计算3

16、367. 0sin302022-4-29Hermite（埃尔米特）（埃尔米特） 插值插值 是Taylor插值与Lagrange插值的综合与推广。思想：在节点xi处插值函数pn(x)和要逼近的函数具有相同的函数值和导数值，这种插值方法称为Hermite插值 niyxpyxpiiniin, 1 , 0 )( ,)( 该多项式满足： 保持插值曲线在节点处有切线（光滑），使保持插值曲线在节点处有切线（光滑），使插值函数和被插函数的密合程度更好插值函数和被插函数的密合程度更好 。 312022-4-29112002002)( , )( ,)(yxpyxpyxp 最简单的形式： 对于该问题，有三种解决方法

17、：u待定系数法：待定系数法：解方程组解方程组 困难困难u余项校正法：余项校正法：用某个余项校正用某个余项校正p1(x)以获得以获得p2(x) 可行，但插值公式的次数不能高可行，但插值公式的次数不能高u基函数方法：基函数方法：将插值多项式的构造化归为求解将插值多项式的构造化归为求解几几 个特殊数据表的插值问题个特殊数据表的插值问题322022-4-29分别满足分别满足，设有两组函数：设有两组函数：)()(xxii), 1 , 0,(0)( , 1 , 0)( ), 1 , 0,(0)( , 1 , 0)( )2(njixijijxnjixijijxjiijjijiijji次多项式次多项式都是至多

18、都是至多12)( ),( ) 1 (nxxiiniiiiinyxyxxp012)()()(则则Hermite 插值多项式为插值多项式为：一般形式：332022-4-29,21)(21010100 xxxxxxxxx,)()(210100 xxxxxxx2010101121)(xxxxxxxxx201011)()(xxxxxxx特别：n=1时110011003)()()()()(yxyxyxyxxp342022-4-29 求过求过0、1两点构造一个三次插值多项式两点构造一个三次插值多项式，满足条件：满足条件： f(0)=1, f (0)=1/2 , f(1)=2, f (1) =1/2解解: :

19、 设 p3(x)=0(x) y0 + 1(x) y1 +0(x) y 0 +1(x) y 0 同理可得同理可得: 1(x)=(3-2x)x2 0(x)=x(x-1)2 1(x)=x2(x-1)例例2221010100) 1)(21 (1010102121)(xxxxxxxxxxxxx352022-4-295. 分段插值 一般来说，高次插值多项式的逼近效果并不好，从数值计算上可解释为高次插值多项式的计算会带来舍入误差的增大，从而引起计算失真。因此，实践上作插值时一般只用一次、二次最多用三次插值多项式。 Runge（龙格）（龙格）现象现象 那么如何提高插值精度呢？ 采用分段插值362022-4-2

20、9分段插值的含义分段插值的含义 选取分段多项式作为插值函数，即将插值函数逐段多项式化 将插值区间a, b 划分为若干个子段xi , xi+1 在每个子段上构造插值多项式 将每个子段上的插值多项式拼接在一起作为整个区间上的插值函数 若插值函数Sk(x)在分划的每个子段上都是k次式，则称Sk(x)为具有分划的分段k次式372022-4-29分段线性插值 都是线性函数都是线性函数在每个小区间上在每个小区间上)(),1,.,2 , 1 , 0(,)2(),.,2 , 1 , 0()() 1 (111xSnixxniyxSiiii则称S1(x)是f(x)在a ,b上的分段线性插值多项式。通过插值点用折线

21、连接起来逼近f(x)。设已知插值节点 上的函数值为nyyy,10bxxxan10构造插值函数S1(x)，使其满足：382022-4-29)( )(111111iiiiiiiiiixxxyxxxxyxxxxxS分段表达式分段表达式若采用若采用Lagrange插值多项式插值多项式)( )(11101iiiiiiiixxxyhxxyhxxxSxjxj-1xj+1x0 xnn越大，误差越小392022-4-29设设 （-1 x 1），），将将-1, 1 10等份等份，用分段线性插值近似计算用分段线性插值近似计算f(-0.96)。22511)(xxf 8 . 01) 1(2941. 0)8 . 0(1923. 02 . 01)8 . 0(2 . 08 . 0) 1()(1xxxxfxfxS解解：(1)插值节点为xi=-1+i/5 (i=0,1,10), h=1/5 因为-0.96-1,-0.8，取此区间为线性插值区 间，其上的插值函数为例例所以f(-0.96)=0.041597 S1(-0.96)=0.042532402022-4-29选取距节点选取距节点x最近的三个节点最近的三个节点xi-1、xi、x