数值计算方法课程设计报告课程设计名称：数值计算方法课程设计题目：插值算法年级专业：信计1302班组员姓名学号：高育坤 43王冬妮 44韩建 46李婧 47指导教师：刘丽华完成时间： 2015年6月17日插值算法一、问题提出插值法是实用的数值方法，是函数逼近的重要方法。

在生产和科学实验中，自变量x与因变量y的函数y = f(x)的关系式有时不能直接写出表达式，而只能得到函数在若干个点的函数值或导数值。

当要求知道观测点之外的函数值时，需要估计函数值在该点的值。

如何根据观测点的值，构造一个比较简单的函数y=φ(x)，使函数在观测点的值等于已知的数值或导数值，进而用简单函数y=φ(x)在点x处的值来估计未知函数y=f(x)在x点的值。

寻找这样的函数φ(x)，办法是很多的。

φ(x)可以是一个代数多项式，或是三角多项式，也可以是有理分式；φ(x)可以是任意光滑（任意阶导数连续）的函数或是分段函数；函数类的不同，自然地有不同的逼近效果。

二、背景分析在许多实际问题及科学研究中，因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达，通常只是由观察与测试得到一些离散数值。

有时，即使给出了解析表达式，却由于表达式过于复杂，不仅使用不便，而且不易于进行计算与理论分析。

解决这类问题的方法有两种：一种是插值法插值法，另一种是一拟合法。

插值法是一种古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机软件中，许多库函数，如 ,cos,sinex 等的计算实际上归结于它的逼近函数的计算。

逼近函数一般为只含有算术运算的简单函数，如多项式、有理分式（即多项式的商）。

在工程实际问题当中，我们也经常会碰到诸如此类的函数值计算问题。

被计算的函数有时不容易直接计算，如表达式过于复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或者导数值信息等。

因此，我们希望能用一个“简单函数”逼近被计算函数，然后用该简单函数的函数值近似替代被计算函数的函数值。

这种方法就叫插值逼近或者插值法。

插值法要求给出函数f（x）的一个函数表，然后选定一种简单的函数形式，比如多项式、分段线性函数及三角多项式等，通过已知的函数表来确定一个简单的函数作为f（x）的近似，概括地说，就是用简单函数为离散数组建立连续模型。

三、基本算法思想与实现x 1x nx 0y 1y已知1+n 个数据节点:,,,...2,1,0),,(不相同其中j j j x n j y x =b x x x a n =<<<=...10不妨设构造一个(相对简单)函数)(x f y =(称为插值函数),通过全部结点即j j y x f =)(（j ＝0,1,…n ）再用)(x f 计算插值，即**)(y x f =数学上插值方法非常多，这里介绍几种常用方法： 1·Lagrange 插值函数Lagrange 插值函数的基本思想:将待求的n 次插值多项式()n P x 写成另一种表达方,式再利用插值条件()i i y f x = (0,1,2...)i =确定出插值基函()i l x 由基函数条件()1i i l x =,确定多项式系数，进而可得插值函数()n P x .（1）已知0011(),()f x y f x y ==，求满足条件的插值函数。

由题可知()y f x =表示过两点0011(,),(,)x y x y 的直线，这个问题是我们所熟悉的，它的解可表为下列对称式01010110x x x x y y y x x x x --=+--此类一次插值称为线性插值，若令01010110(),()x x x x l x l x x x x x --==--（由此可得：00011110()1,()0,()1,()0l x l x l x l x ====））则有10011()()()P x l x y l x y =+这里的01(),()l x l x 可以看作是满足条件00011110()1,()0()1,()0l x l x l x l x ====的插值多项式，这两个特殊的插值多项式称作上述问题的插值基函数。

（2）求过三点001122(,),(,),(,)x y x y x y 的插值函数。

为了得到插值多项式先解决一个特殊的二次插值问题。

求作二次式0()l x ，使满足000102()1,()()0l x l x l x === （2-1）这个问题是容易求解的，由式（2-1）的后两个条件知12,x x 是0()l x 的两个零点，因而012()()()l x c x x x x =-- 。

再用条件00()1l x =确定系数c .结果得 ：1200102()()()()()x x x x l x x x x x --=--类似可以分别构造出满足条件111012222021()1,()()0()1,()()0l x l x l x l x l x l x ======的插值多项式12(),()l x l x ；其表达式分别为0211012()()()()()x x x x l x x x x x --=--，0122021()()()()()x x x x l x x x x x --=--这样构造出的012(),(),()l x l x l x 称作问题（2）的插值基函数。

设取已知数据012,,y y y 作为组合系数，将插值基函数012(),(),()l x l x l x 组合得2001122()()()()P x l x y l x y l x y =++020112012010*********()()()()()()()()()()()()x x x x x x x x x x x x y y y x x x x x x x x x x x x ------=++------验证可知，这样构造的2()P x 满足已知条件，因而它就是问题（2）的解。

(3)推广到一般：已知函数在n+1个不同点01,,...nx x x 上的函数值分别为01,,...ny y y 求一个次数不超过n 的多项式()n P x ,使其满足:()(0,1,..)n i i P x y i n ==即1n +个不同的点可以决定的一个n 次多项式。

过1n +个不同的点分别决定1n +个n 次插值基函数。

01(),(),...,()n l x l x l x每个插值基多项式满足：a.()i l x 是n 次多项式;b.()1i l x =,而在其它n 个点()0,()i k l x k i =≠由于()0,()i k l x k i =≠故有因子:011()...()()...()i i n x x x x x x x x -+----因其已经是n 次多项式，故而仅相差一个常数因子。

令:011()()...()()...()i i i n l x a x x x x x x x x -+=----由()1i i l x =,可以定出a , 进而得到：011011()...()()...()()()...()()...()i i n i i i i i i i n x x x x x x x x l x x x x x x x x x -+-+----=----n 次拉格朗日型插值多项式()n P x()n P x 是1n +个n 次插值基本多项式01(),(),...,()n l x l x l x 的线性组合,相应的组合系数是01,,...ny y y 。

即:0011()()()...()n n n P x y l x y l x y l x =++从而()n P x 是一个次数不超过n 的多项式,且满足()(0,1,..)n i i P x y i n ==2·Newton 插值函数的构造Newton 插值法的基本思想：已知节点处的函数值或一元函数代数方程，将待求的n 次插值多项式()n P x 改写为具有承袭性的形式，然后根据插值条件或选取初值以求()n P x 得待定系数，进而求得所要的插值函数。

实践中的许多问题归结为求一元代数方程()0f x =的根，如果()f x 是线性函数，则它的求根较容易；对非线性方程，只有不高于4次的代数方程有求根公式，经常需求出高于4次 的满足一定精度要求的近似解。

Newton 法的简述设x k x -（）是()f x 的一个近似根，把()f x 在k x 处泰勒展开2()()()()()()...2k k k k f x f x f x f x x x x x '''=+-+-+若取前两项来近似代替()f x ，则()0f x =的近似线性方程()()()()0k k f x f x f x x x '=+-=设'()f x ≠0，设其根为1k x +，则1k x+的计算公式为1k x +=kx -()'()k k f x f x （k=0,1,2.....）这即为牛顿法，上式为牛顿迭代公式，其迭代函数为()()()f x x x f x ϕ=-'我们知道，牛顿法是解非线性方程最著名和最有效的方法之一，在单根附近它比一般的迭代格式有较快的收速度，但也要注意它也有缺点：首先，它对迭代初值选取要求较严，初值选取不好，可能导致吧收敛；其次，它每迭代一次要计算()k f x '的值，这势必增加可计算量。

为回避该问题，常用一个固定的()k f x '迭代若干步后再求()k f x '。

这就是下面要讲的简化牛顿法的基本思想。

简化牛顿法和下山牛顿法 简化牛顿法的公式为1()k k k x x cf x +=- (3-1)迭代函数 ()()x x cf x Φ=-若()1()1x cf x ''Φ=-<。

即0()2cf x '<< 在根*x 附近成立。

则迭代法（3-1）局部收敛。

此法显然化简了计算量。

牛顿下山法牛顿法的收敛依赖于初值x 的选取，若x 偏离*x 较远，则牛顿法可能发散。

为防止迭代发散，我们对迭代过程在附加一项条件，即具有单调性：1()()k k f x f x +< （3-2）保证函数值稳定下降，然后结合牛顿法加快收敛速度，即可达目的。

将牛顿法的计算结果1()()k k k k f x x x f x +=-' （3-3）于前一步的近似值k x 适当加权平均作为新的改进值11(1)k k k x x x λλ++=+- （3-4）其中称λ（01λ<≤）为下山因子，即为1()()k k k k f x x x f x λ+=-' （3-5）称为牛顿下山法。