《数值分析》第五章 插值法

数值分析插值法插值法是数值分析中的一种方法，用于通过已知数据点的函数值来估计介于这些数据点之间的未知函数值。

插值法在科学计算、数据处理、图像处理等领域中得到广泛应用。

插值法的基本思想是通过已知数据点构造一个函数，使得该函数逼近未知函数，并在已知数据点处与未知函数值相等。

插值法的关键是选择适当的插值函数，以保证估计值在插值区间内具有良好的近似性质。

常用的插值法有拉格朗日插值法、牛顿插值法和埃尔米特插值法等。

以下将分别介绍这些插值法的原理及步骤：1. 拉格朗日插值法：拉格朗日插值法通过构造一个多项式函数来逼近未知函数。

假设已知n+1个数据点(x0, y0), (x1, y1), ..., (xn, yn)，其中x0, x1, ..., xn为给定的节点，y0, y1, ..., yn为对应的函数值。

拉格朗日插值多项式的一般形式为：L(x) = y0 * l0(x) + y1 * l1(x) + ... + yn * ln(x)其中l0(x), l1(x), ..., ln(x)为拉格朗日基函数，定义为：li(x) = (x - x0)(x - x1)...(x - xi-1)(x - xi+1)...(x - xn) / (xi - x0)(xi - x1)...(xi - xi-1)(xi - xi+1)...(xi - xn)拉格朗日插值法的步骤为：a. 计算基函数li(xi)的值。

b.构造插值多项式L(x)。

c.计算L(x)在需要估计的插值点上的函数值f(x)。

2.牛顿插值法：牛顿插值法通过构造一个差商表来逼近未知函数。

差商表的第一列为已知数据点的函数值，第二列为相邻数据点的差商，第三列为相邻差商的差商，以此类推。

最终，根据差商表中的数值，构造一个差商表与未知函数值相等的多项式函数。

牛顿插值法的步骤为：a.计算差商表的第一列。

b.计算差商表的其他列，直至最后一列。

c.根据差商表构造插值多项式N(x)。

数值分析第五章插值法插值法是数值分析中常用的一种数值逼近方法，它的目的是通过已知数据点之间的插值多项式来逼近未知数据点的函数值。

插值法可以在信号处理、图像处理、计算机图形学等领域中广泛应用。

在插值法中，最常用的方法有拉格朗日插值法和牛顿插值法。

拉格朗日插值法是一种利用拉格朗日插值多项式来逼近函数的方法。

对于n个已知数据点(xi, yi)，拉格朗日插值多项式L(x)可以表示为：L(x) = ∑(yi * li(x))其中，li(x)表示拉格朗日基函数，定义为：li(x) = ∏[(x - xj)/(xi - xj)] (j≠i)可以证明，在给定的n个数据点上，拉格朗日插值多项式L(x)满足：L(xi) = yi牛顿插值法是另一种常用的插值方法，它利用差商的概念来逼近函数。

对于n个已知数据点(xi, yi)，差商可以定义为：f[xi] = yif[xi, xi+1] = (f[xi+1] - f[xi]) / (xi+1 - xi)f[xi, xi+1, ..., xi+k] = (f[xi+1, ..., xi+k] - f[xi, ...,xi+k-1]) / (xi+k - xi)通过差商的递归定义，可以得到牛顿插值多项式N(x)的表达式，其中：N(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...与拉格朗日插值法类似，牛顿插值多项式N(x)也满足：N(xi) = yi这两种插值方法都有自己的优点和缺点。

拉格朗日插值法简单易懂，计算量小，但当数据点较多时，多项式的次数会很高，容易出现龙格现象。

而牛顿插值法可以通过求差商一次次递推得到插值多项式，计算效率较高，且具备局部逼近性，不易出现龙格现象。

除了拉格朗日插值法和牛顿插值法，还有其他插值方法，如分段线性插值、样条插值等。

分段线性插值是利用线性多项式逼近函数，将数据点之间的区间分为若干段，每段内使用一条线性多项式进行插值。

数值分析插值法数值分析是数学的一个分支，用于研究如何使用数值方法来近似和解决数学问题。

插值是数值分析的一个重要概念，它涉及到如何通过已知数据点的信息来估计未知数据点的值。

在本文中，我们将着重讨论插值法。

插值法是一种基于已知数据点的函数值，通过建立适当的插值函数来估计未知数据点的函数值的方法。

插值问题的目标是找到一个函数f(x)，使得f(x_i)=y_i(i=0,1,2,...,n)，其中x_i是已知的数据点，y_i是相应的函数值，n是已知数据点的数量。

然后，通过插值函数可以近似估计任意一个未知数据点的函数值。

常见的插值方法包括拉格朗日插值、牛顿插值和埃尔米特插值等。

下面我们将逐一介绍这些插值方法。

拉格朗日插值是一种利用拉格朗日多项式进行插值的方法。

拉格朗日多项式是一个多项式函数，满足通过已知数据点的函数值。

具体地说，设给定的已知数据点为(x_i,y_i)，我们需要找到一个多项式P(x)=y，使得P(x_i)=y_i。

拉格朗日插值多项式的形式如下：P(x)=Σ(y_i*l_i(x))其中l_i(x)是拉格朗日基函数，它定义为：l_i(x)=Π((x-x_j)/(x_i-x_j))(j≠i)牛顿插值是另一种常用的插值方法。

它通过使用差商来递归地计算插值多项式。

差商是一个递归定义的函数，用于计算多项式的系数。

设给定的已知数据点为(x_i,y_i)，我们需要找到一个多项式P(x)=y，使得P(x_i)=y_i。

牛顿插值多项式的形式如下：P(x)=y_0+(x-x_0)*f[x_0,x_1]+(x-x_0)*(x-x_1)*f[x_0,x_1,x_2]+...其中，f[x_i,x_j,...,x_k]是差商的定义，它可以通过递归公式计算得到：f[x_i,x_j,...,x_k]=(f[x_j,...,x_k]-f[x_i,...,x_{k-1}])/(x_k-x_i)埃尔米特插值是一种利用已知数据点及其导数信息进行插值的方法。

第五章函数插值§1 插值问题与插值多项式§2 Lagrange插值法§3 Newton插值法§4 等距节点插值§5 Hermite插值§6 分段低次插值§7 三次样条插值西北工业大学理学院欧阳洁1问题提出仅有采样值，但需要知道非采样点处的函数值。

解决上述问题的一种思路：对用数据表给出的未知函数，建立一个便于计算的近似函数作为表达式。

函数插值法是建立近似函数表达式的一种基本方法。

西北工业大学理学院欧阳洁2§1 插值问题与插值多项式一插值问题二插值多项式西北工业大学理学院欧阳洁3西北工业大学理学院欧阳洁4一插值问题ni x f x i i ,,1,0),()(L ==ϕ已知定义于区间[a,b ]上的实值函数f (x )在n+1 个互异节点处的函数值。

若函数集合Φ中的函数ϕ(x )满足{}n i i x f 0)(={}],[0b a x n i i ⊂={}n i i x 0=则称ϕ(x )为f (x )在函数集合Φ中关于节点的一个插值函数，称f (x )为被插值函数,[a,b ]为插值区间。

{}ni i x 0=称为插值节点。

n i x f x i i ,,1,0),()(L ==ϕ称为插值条件。

如何求插值函数ϕ(x )称为插值问题。

西北工业大学理学院欧阳洁71 代数插值多项式的存在唯一性分析：对于多项式插值问题，插值条件等价于确定多项式的系数，使得满足如下的线性方程组：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡)()()()(111210210212110200n n n n nn n n x f x f x f x f a a a a x x x x x x x x x M M L L L L L L L L 当节点互异, 系数矩阵非奇异, 故满足插值条件的不超过n 次的插值多项式是存在惟一的。

数值分析-插值法我们能得到⼀个函数f在区间[a,b]上某些点的值或者这些点上的⾼阶导数我们就能通过插值法去得到⼀个函数g，g与f是⾮常相近的⼀般来说g分为三类，⼀类是n次多项式 a n*x n +a n-1*x n-1 + .......+a0，⼀类是三⾓多项式，最后⼀类是分段n次多项式多项式插值这个可以说是最简单的插值了对于a n*x n +a n-1*x n-1 + .......+a0，我们有n+1个未知数，我只需要知道n+1个点的函数值就可以解出这n+1个未知数将解出的值带⼊即可优点:简单粗暴缺点:要解n+1个⽅程，时间复杂度较⾼，n不好确定，若n过⼤，容易过拟合，若n过⼩，容易⽋拟合拉格朗⽇插值先说⼀阶多项式我们有两点式f(x) = y k*(x k+1 - x) / (x k-x k+1) + y k+1*(x-x k) / (x k+1 - x k)此两点式可以看做∂ * y k + (1-∂) * y k+1那么⾃然的在x=x k的时候 ∂=0 在x=x k+1的时候∂=1这⾥的∂其实是与x相关的⼀阶多项式再说⼆阶多项式对于⼀个⼆次函数，我们有三个点(x k-1,y k-1) ,(x k,y k) ,(x k+1,y k+1)我们有l k-1,l k,l k+1f(x) = l k-1*y k-1 + l k*y k + l k+1*y k+1其中l是与x相关的⼆次多项式我们可以把l当作基函数这样的话就有x = x k-1 时l k-1 = 1, l k=0, l k+1 = 0x = x k时 l k-1 = 0, l k=1, l k+1 = 0x = x k+1时l k-1 = 0, l k=0, l k+1 = 1那么这个插值基函数是很好求的因为每个插值函数都有两个零点对于l k-1来说有零点x k,x k+1那么lk-1就可以表⽰为l k-1 = A*(x-x k)*(x-x k+1)因为x=xk-1时l k-1 = 1所以A = 1 / (（x k-1 - x k）* (x k-1 - x k+1) )那么同理l k和l k+1也能求出来了那我们得到⼆阶的拉格朗⽇插值多项式现在将⼆阶推⼴到n阶得到n接的拉格朗⽇插值多项式余项:R n(x) = f(x) - L n(x) R n(x)表⽰n次拉格朗⽇多项式的插值余项R n(x) = f n+1(e)/(n+1)! * w n+1(x) e属于[a,b]且依赖与x w n+1(x) = (x-x0)(x-x1).......(x-x n)优点:算法较为简单缺点:⽆法处理动态增加节点的情况⽜顿插值还是先从⼀阶到⼆阶进⾏说明我先得到了⼀阶差值多项式P1(x),P1(x) 满⾜过点(x1, f(x1)), (x2,f(x2))假设现在有第三个点(x3,f(x3))我们要通过这个点去得到⼆阶差值多项式P2(x) 使得P2(x)过这三个点可以设P2(x) = P1(x) + a2*(x-x0)*(x-x1)通过第三个点解出a2就⾏了推⼴到多阶那么可以得到P n(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + a3(x-x0)(x-x1)(x-x2) + ......求这个插值多项式的值可以通过递推⼀步⼀步的求这样就实现了动态增删可以看到计算a k需要计算(k-1)2次，那么⽜顿插值法就是⼀个快速的计算⽅法均差⼀阶均差 f[x0, x k] = ( f(x k) - f(x0) ) / (x k - x0)⼆阶均差 f[x0, x1, x2] = (f[x0, x2] -f[x0, x1] ) / (x2 - x1)可以看到⼀阶均差就是简单的求斜率⼆阶均差就是对⼀阶均差求斜率那么k阶均差就是f[x0, x1,,,,,,x k] = (f[x0,,,,,x k-2, x k] -f[x0, ,,,,,,,x k-2,x k-1] ) / (x k - x k-1)f[x0, x1,,,,,,x k] = f n(ε) / n!均差的性质k阶均差可表⽰为f(x0),f(x1), f(x2),,,,,,,,, f(x k)的线性组合⽜顿插值中的a就是均差，可以从⼀阶开始推，然后使⽤数学归纳法证明那么⽜顿插值多项式就是：在计算f[x0,x1,,,,,,,,,,x n]时，⼀般使⽤均差表均差表的计算⽅式为a[i,j] = ( a[i-1][j] - a[i-1][j-1] ) / (末尾的x - 最开始的x)误差:误差为最后⼀阶的均差 * w(x)优点:可动态增删节点缺点:⽆法处理要求导数相同的情况埃尔⽶特插值法实验报告⼀个点，多个导数:⽜顿插值中的均差在xi->x0时其实分别是i阶导数，这样就是我们熟悉的泰勒多项式此时的插值函数就是泰勒多项式两个点，⼀个导数我们有三个条件，也就是说我们能求出三次插值多项式这时我们先写出过这两个点的⽜顿插值多项式在这个多项式的基础上我们再加上⼀个三次项搞定，可以观察到，这三个项数其实可以算是正交的，因为当x=x1或者x=x2时最后⼀项是0满⾜条件的两个点，两个导数这也是题⽬所要求的情况因为有两个导数，所以⽜顿插值法⽆法解决，这⾥只能使⽤基函数⽅法设插值函数为H(x), 点与导数分别为(x1,y1,m1),(x2,y2,m2)H(x)满⾜：H(x1) =y1, H(x2) = y2, H(x1)’ = m1,H(x2)=m2H(x) = a1*x1 + a2*x2 + b1*m1 + b2*m2其中 a1, a2, b1, b2均为三层插值多项式X=x1时 a1(x1) = 1,a2(x1) = 0, b1(x1) = 0,b2(x1) = 0,a1’(x1) = 1,a2’(x1) = 0X=x2时 a1(x2) = 0,a2(x2) = 1, b1(x2) = 0,b2(x2) = 0,a1’(x2) = 1,a2’(x2) = 0X=x1时 b1’(x1) = 1,b2’(x1) = 0X=x2时b1’(x1) = 0,b2’(x1) = 1然后⽤了⼀个很巧妙的⽅法设基函数，解出来值和就是这样⼦的R3(x) = 1/4! * (x-x k)2(x-x k+1)2*f4(ε)两个点，两个导数2直接使⽤泰勒多项式，并把将余项改为未知数，使⽤多余的⼀个条件去求余项的值例如:求次数⼩于等于3的多项式P(x)，使满⾜条件P(x0)=f(x0)，P'(x0)=f'(x0)，P"(x0)=f"(x0)，P(x1)=f(x1)。

实验报告专用纸实验项目名称插值法课程名称计算机数值方法教师评语及成绩：实验成绩：教师签字：（请按照实验报告的有关要求书写，一般必须包括：1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题及解决方法；6、实验结果、结果分析与体会等内容。

）1、实验目的（1）学会Lagrange插值、Newton插值、分段线性插值等基本插值方法；（2）讨论插值的Runge现象，掌握分段线性插值方法；（3）学会用Matlab或C等实现多项式拟合。

2、实验内容（1）用Newton插值多项式及分段线性插值函数对数据进行插值；（2）比较牛顿插值与分段线性插值法；（3）函数f(x)的多项式拟合；输入：拟合数据序列{x i，y i}，i=0,1,2,…,m；输出：多项式拟合函数，并画出拟合曲线和f(x)。

3、实验步骤（1）用MATLAB编写独立的拉格朗日插值多项式的函数（2）用MATLAB编写独立的牛顿插值多项式（3）利用编写好的函数计算实际问题（4）记录实验数据（5）对运行结果进行分析（6）根据实验情况和结果撰写并提交实验报告。

4、实验原理（1）拉格朗日插值多项式（2）牛顿插值多项式（3）分段线性插值5、实验程序(MATLAB)6、实验结果与分析（1）实验结果图1龙格函数图形图2Runge(10)的图形图3Runge(12)的图形图4Runge(20)的图形输入：拟合数据序列{x i，y i}，i=0,1,2,…,m；01491625364964xi012345678yi输出：多项式拟合函数，并画出拟合曲线和f(x)。

图5拟合曲线图（2）结果分析在本题中，据Runge图形可知，在区间两端点附近，节点等距的条件下，n越大，插值多项式的值与f(x)的偏离程度越大。

因此，Runge现象说明，并非插值多项式的次数越高，其近似代替f(x)的精度就越高。

分段线性插值法可以解决Runge现象。

牛顿插值法克服了拉格朗日插值法不具有继承性的缺点。

第五章 插值与逼近--------学习小节一． 本章学习体会本章学习了插值与逼近，经过本章的学习我对插值法有了进一步的认识。

插值与逼近就是寻找一个简单的函数来代替表达式复杂甚至无法写出表达式的函数。

可以说我们现在学习推导出来的方法公式等都是前人的辛苦钻研的结果，本章除了学到了许多的插值与逼近方法，更重要的是了解了许多科学前辈的故事以及他们许多做研究的态度与方法。

我感觉了解一下数学家的人生故事对我们学习数值分析或别的数学知识有很大的帮助。

上课时王老师给我们讲了数学奇才Hermite 的传奇故事，一个不会考试，基本上每次考数学都不及格的‘笨学生’，后来成为了伟大的数学家。

不是每个数学家都特别聪明，他们所具有的是作为一名科学家的品质，想别人没有想过的问题，在研究中创新，我们应该学习他们那种做研究的态度与精神。

学习这章时有一个小小的困惑，在曲线拟合的求法时，求多元函数的极小值*2200[()()]min [()()]im nm njj i i j j i i c i j i j cx f x c x f x φφ====-=-∑∑∑∑2010(,,,)[()()]mnn j j i i i j F c c c c x f x φ===-∑∑ 老师讲时说用0kFc ∂=∂求得，那万一求出的是极大值呢？ 二．本章知识梳理数值分析中的插值是一种有力的工具，它最终得出的曲线图像都是过节点的，我们的目的使用它得出的图像来近似估计插值点的函数值。

我们首先学了代数插值中的一元函数插值，一元函数插值中学了拉格朗日插值但其插值公式没有延续性，后来学了牛顿插值，其优点是插值公式具有延续性，但前两者都有缺点，就是插值节点一般不超过三个，否则会有很大误差。

但实际工程中我们会测的许多的数据，也就有许多的节点，这样前两种差值方法就不能用了，后来我们又引进了分段线性插值，就是将这许多的节点进行分段，在每段中应用拉格朗日插值或牛顿差值。

第五章 插值法与最小二乘法第一节 问题的提法和多项式插值一、问题提法函数是描述客观规律的重要工具。

在实际应用中许多函数是通过科学实验或观测得到的，通常是一个列表函数或复杂函数的解析表达式的列表形式。

设)(x f y =在已知点b x x x a n ≤<<<≤ 10上的函数值为0y ，1y ，n y ，记为(){}n i y x i i ,,1,0,, =，如何用一个简单的函数)(x p 近似，使得在[]b a ,上，)()(x f x p ≈，这就是本章要解决的问题。

通常有两类提法：1） 通过给定点()n i y x i i ,,1,0,, =，作一曲线，其方程为)(x p y =，)(x p 为一简单函数，n i y x p i i ,,1,0,)( ==。

)(x p 为插值函数，i x 为插值点，[]b a ,为插值区间，)(i i x f y =为样本值。

2）作一指定类型的曲线)(x p y =，使曲线在“一定意义”下逼近给定的列表函数(){}n i y x i i ,,1,0,, =，此为曲线的拟合问题。

本章采用做小二乘法解决。

二、多项式插值通过两个插值点()00,y x 和()11,y x 的为一条直线，方程为：10100101y x x x x y x x x x y --+--=推广到在[]b a ,上的1+n 个插值点b x x x a n ≤<<<≤ 10，对应的函数值为0y ，1y ，n y ，求次数不超过n 的多项式n n x a x a a x p +++= 10)(，其中0a ，1a ，n a 为待定系数。

使n i y x p i i ,,1,0,)( ==即⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn n n n nn nn y x a x a a y x a x a a y x a x a a 101111000010，i x 互异，故由Vandermande 定理知方程组方程组的解0a ，1a ，n a 唯一存在。