当前位置：文档之家 › 牛顿插值_拉格朗日插值1

牛顿插值_拉格朗日插值1

  • 格式：doc
  • 大小：117.00 KB
  • 文档页数：7

实验一 插值与拟合1 实验目的(1) 明确插值多项式和三次样条插值多项式各自的优缺点；(2) 编程实现拉格朗日插值算法，分析实验结果体会高次插值产生的龙格现象；(3) 理解最小二乘拟合，并编程实现线性拟合，掌握非线性拟合转化为线性拟合的方法 (4) 运用常用的插值和拟合方法解决实际问题。

2 实验内容(1) 对于55,11)(2≤≤-+=x x x f 要求选取11个等距插值节点，分别采用拉格朗日插值和三次样条插值，计算x 为0.5, 4.5处的函数值并将结果与精确值进行比较。

输入：区间长度，n(即n+1个节点)，预测点 输出：预测点的近似函数值，精确值，及误差(2) 对下表求出拟合直线 i 1 2 3 4 5 xi 165 123 150 123 141 yi 1871261721251483 算法基本原理当精确函数 y = f(x) 非常复杂或未知，在一系列节点 x 0 … x n 处测得函数值 y 0 = f(x 0), … y n = f(x n )， 希望由此构造一个简单易算的近似函数 g(x) ≈ f(x)，满足条件g(x i ) = f(x i ) (i = 0, … n)。

这里的 g(x) 称为f(x) 的插值函数，由插值函数可以去近似估计f(x)在一些未知点处的函数值。

最常用的插值函数是多项式插值。

所谓多项式插值即求 n 次多项式x a x a a x P n n +++= 10)(使得)()(i i n x f x P = 基于基函数的拉格朗日插值是构造多项式插值最基本方法。

也是推导数值微积分和微分方程数值解的公式的理论基础。

拉格朗日插值公式为：∑==nk kk n x ly x p 0)()( 其中∏≠=--=nkj j jk j k x x x x x l 0)(当结点比较多，次数较高的插值多项式往往发生Runge 现象，分段低次插值是避免Runge 现象的重要手段。

分段一次插值将整个区间分段，在每个小区间上，用一次多项式逼近 f (x)，直观上即用折线代替曲线，只要区间足够小就可以保证很好的逼近效果，但曲线缺乏光滑性。

称具有分划：01:n a x x x b ∆ = <<<=的分段k 次式()k S x 为k 次样条函数，如果它在每个内节点i 11)x i n ≤≤-（上具有直到k-1阶连续导数。

三次样条插值函数：3011011112201()()()()(),()(1)(21),()(23)i i i ii i i i i i i i i ii i i i i x x x x x x x x S x y y h m h m h h h h h x x x x x x x x x x x ϕϕφϕϕϕ++++----=+++ =- ≤≤ = -+ = -+ (*) 2201()(1),()(1)x x x x x x φφ = - = -除了插值，逼近复杂函数f(x)的另一种方法是拟合。

结点数据比较多，或者不够精确，往往采用拟合的方法。

用来拟合的简单函数p(x)，不需严格通过给定结点，但在这些结点处总体误差2))((iiy x p Q -=∑达到极小，即满足最小二乘拟合的条件。

线性拟合是最简单的拟合方法，许多非线性问题都可以转化为线性拟合。

令线性函数为a 0+a 1x ，要确定a 0和a 1，最终求解如下线性方程组：4 算法描述(1) 拉格朗日插值算法见流程图(2) 样条性插值算法要注意以下关键点：A. 定位：预测点x 在第几个区间？B. 假定x 在第k 个区间，00210001=====⎡⎤⎡⎤+⎢⎥⎢⎥⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦⎢⎥⎢⎥⎣⎦⎣⎦∑∑∑∑∑nn i i i i n n n i i i i i i i n x y a a x x x y 图1.1拉格朗日插值算法11111110i 3(1)(1)2,i i i ii i i i i i i i i i i i i i i n n h h h y y y y h h m m m m y m y m αβααααβ- --+ - - + 0 =+⎡⎤-- =-+⎢⎥⎣⎦-++= ''= = 解出代入(*)(3) 线性拟合算法在没有讨论线性方程组数值解法的前提下，用最原始的消元法求解线性方程组5 输入输出A ．三次样条插值：输入文件（六个点加端点的两个导数）输出结果：结果分析对比书上标准值，精度达到0.0001，猜测原因：分段点较少，段间距较大。

B ．线性拟合最小二乘法输入文件：输出结果：对比标准，结果准确。

6 源代码A．三次样条：#include <iostream>#include <fstream>#include <cmath>#define Max 10#define playusing namespace std;int M, N;double m0, mn;double x[Max], y[Max], h[Max]; double a[Max], b[Max], c[Max], d[Max]; double fai0(double x){return (x-1)*(x-1)*(2*x+1);}double fai1(double x){return x*x*(-2*x+3);}double psi0(double x){return x*(x-1)*(x-1);}double psi1(double x){return x*x*(x-1);}double S3(double x0){int i, j;if (x0<x[0] || x0>x[N]) cerr<<"err\n";for (i=0;i<=N;++i)if (x0<x[i]) break;i--;// cout<<"i="<<i<<endl;double t, u = (x0-x[i])/h[i];t = fai0(u) * y[i] + fai1(u) * y[i+1];t += h[i]*psi0(u) * d[i] + h[i]*psi1(u) * d[i+1];return t;}int main(){int i, j, k;double t;fstream icin("inp1.txt", ios::in);icin>>N;N--;for (i=0;i<=N;++i) icin>>x[i]>>y[i];icin>>d[0]>>d[N];for (i=0;i<N;++i) h[i] = x[i+1] - x[i];for (i=1;i<N;++i){c[i] = h[i-1] / (h[i-1] + h[i]);a[i] = 1 - c[i];d[i] = a[i]*(y[i]-y[i-1])/h[i-1] + c[i]*(y[i+1]-y[i])/h[i];d[i] *= 3;b[i] = 2;}for (i=0;i<=N;++i) cout<<d[i]<<" ";cout<<endl;d[1] -= a[1] * d[0];d[N-1] -= c[N-1] * d[N];for (i=2;i<N;++i) cout<<a[i]<<" "; cout<<endl;for (i=1;i<N;++i) cout<<b[i]<<" ";cout<<endl;for (i=1;i<N-1;++i) cout<<c[i]<<" ";cout<<endl;for (i=0;i<=N;++i) cout<<d[i]<<" ";cout<<endl;for (i=0;i<=N;++i) cout<<x[i]<<" ";cout<<endl;icin.close();c[1] /= b[1];d[1] /= b[1];cout<<c[1]<<' '<<d[1]<<endl;for (i=2;i<N;++i){t = b[i] - c[i-1] * a[i];c[i] /= t;d[i] -= d[i-1] * a[i];d[i] /= t;cout<<c[i]<<' '<<d[i]<<endl;}for (i=N-2;i>0;--i){d[i] -= c[i] * d[i+1];cout<<d[i]<<endl;}cout<<"*********\n";for (i=0;i<N;i++){cout<<x[i]<<" "<<S3(x[i])<<endl;cout<<x[i]+0.2<<" "<<S3(x[i]+0.2)<<endl;cout<<x[i]+0.5<<" "<<S3(x[i]+0.5)<<endl;cout<<x[i]+0.7<<" "<<S3(x[i]+0.7)<<endl;}system("pause");return 0;}B.线性拟合#include <iostream>#include <cmath>#include <fstream>#define Max 10using namespace std;double x[Max], y[Max], N;double a, b;int main(){fstream icin("min.txt", ios::in);icin>>N;int i, j, k;for (i=0;i<N;++i)icin>>x[i]>>y[i];icin.close();double xx, xy, yy, x2;xx = xy = yy = x2 = 0.0;for (i=0;i<N;++i){xx += x[i];yy += y[i];xy += x[i] * y[i];x2 += x[i] * x[i];}cout<<xx<<" "<<yy<<" "<<xy<<" "<<x2<<endl;a = (N * xy - xx * yy);a /= (N * x2 - xx * xx);b = yy/N - a * xx/N;for (i=0;i<N;++i)cout<<i+1<<" "<<x[i]<<" "<<y[i]<<endl;char u = '+';if (b<0) u = '-', b = -b;printf("Y = %.6f * X %c %.6f\n", a, u ,b);system("pause");return 0;}7 总结这一次实验，编程实现了拉格朗日插值、三次样条插值、线性最小二乘拟合算法，使得对其理解和掌握更进了一步。

合集下载

拉格朗日插值牛顿插值

拉格朗日插值牛顿插值

杜丁坤 20171506003 自动化1班实验二 插值法一、实验目的和要求(1)学会Langrange 插值、Newton 插值和Hermite 插值等基本插值方法．(2)学会Matlab 提供的插值函数的使用方法，会用这些函数解决实际问题(3) 按照题目要求完成实验内容、写出相应的Matlab 程序给出实验结果．(4)对实验结果进行分析讨论．(5)写出相应的实验报告．一、 实验内容1. Lagrange 插值公式.练习11=2=3=，利用Lagrange 拉格朗日插值的函数%%%%%%%%%function yi=Lagrange(x,y,xi)n=length(x);m=length(y);if n~=merror('The length of X must be equal!');endp=zeros(1,n);for k=1:nt=ones(1,n);for j=1:nif j~=kif abs(x(k)-x(j))<epserror('the DATA is error');return;endt(j)=(xi-x(j))/(x(k)-x(j));endendp(k)=prod(t);endyi=sum(y.*p);%%%%%主函数是：%%%%%X=[1 3 9];Y=[1 2 3];Xi=5;Lagrange(X,Y,xi)练习21=2=3=，利用Newton 进行比较。

牛顿插值函数%%%%%%%%function yi=Newton(x,y,xi)n=length(x);m=length(y);if n~=merror('The length of X must be equal!');endA=zeros(n,n);A(:,1)=y;for j=2:nfor i=1:n-j+1A(i,j)=(A(i+1,j-1)-A(i,j-1))/(x(i+j-1)-x(i));endendX1=xi*ones(1,n)-x;X=ones(1,n);for p=2:nfor q=1:p-1X(p)=X(p)*X1(q);endendY=zeros(1,n);for r=1:nY(r)=A(1,r)*X(r);endyi=sum(Y);%%%%%%%%%%主函数：X=[1 3 9];Y=[1 2 3];Xi=5;Newton(X,Y,xi)三、实验要求要求在实验前必须预习，将实验内容事先准备好，否则不允许上机。

6.2 牛顿插值多项式

6.2 牛顿插值多项式

一阶均差 二阶均差 三阶均差 n阶均差 阶均差
x1 f [ x1 ] f [ x0 , x1 ]
x2 f [ x2 ] f [ x1 , x2 ] f [ x0 , x1 , x2 ]
x3 f [ x 3 ]
… …… x f [ xn ]
n
f [ x2 , x3 ]
f [ x1 , x2 , x3 ]
N n ( x ) = a0 + a1 ( x − x0 ) + a2 ( x − x0 )( x − x1 ) + L + an ( x − x0 )( x − x1 )L ( x − xn−1 )
ak ( k = 0,1,L , n) 为待定系数 形如上式的插值 待定系数.
多项式称为牛顿 插值多项式. 多项式称为牛顿(Newton)插值多项式 牛顿 插值多项式 由插值条件 N n ( x j ) = f ( x j ) ( j = 0,1,L , n),
证毕. 证毕.
的离散数据如下表： 例 1 已知 f ( x ) = shx 的离散数据如下表：
xi
0.00
0.20 0.20134
0.30 0.30452
0.50 0.52110
f ( xi ) 0.00000
用 Newton插值多项式 计算 f (0.23) 的近似值并 插值多项式, 插值多项式 估计误差. 估计误差
解 均差计算的结果如下表
xi
0.00 0.20 0.30 0.50
f [ xi ]
0.00000 0.20134 0.30452 0.52110
一阶均差
二阶均差
三阶均差
1.0067 1.0318 1.0829
0.08367 0.17033
数值计算方法插值法讲解

数值计算方法插值法讲解


又因为lk1(xk1) 1，故a(xk1 xk )(xk1 xk1) 1，得：
a

(xk 1

xk
1 )( xk 1

xk1) ，从而lk1(x)

(x (xk 1

xk xk
)(x xk1) ， )(xk1 xk1)
lk
(x)

(x ( xk

问题的提出
插值问题的数学提法：已知函数y f (x)在n 1个 点x0 , x1, , xn上的函数值yi f (xi ), (i 0,1, , n), 求一 个多项式y P(x)，使其满足P(xi ) yi , (i 0,1, , n). 即要求该多项式的函数曲线要经过y f (x)上已知的
平面上两点 xk , yk , xk1, yk1 ，求一条直线过该已
知两点。
线性插值
插值函数和插值基函数
由直线的点斜式公式可知：
P1(x)

yk

yk 1 xk 1

yk xk
(x
xk )，把此式按照
yk和yk1写成两项:P 1(x)
x xk1 xk xk 1
由于li (xk ) 0,k i，故li (x)有因子：
(x x0 ) (x xi1)(x xi1) (x xn )，因其已经是n 次多项式，故而仅相差一个常数因子。令：
li (x) a(x x0 ) (x xi1)(x xi1) (x xn )
插值法的概念
已知函数在n+1个点x0 ,x1 ,…,xn 上的函数值 yi=f(xi ), (i=0,1,…,n) ，求一个简单函数y=P(x),使其满 足: P(xi )=yi ,(i=0,1,…,n) 。即要求该简单函数的 曲线要经过y=f(x)上已知的这个n+1个 点： (x0 ,y0 ),(x1 ,y1 ),…,(xn ,yn ),同时在其它 x∈[a,b]上要估计误差: R(x) = f(x) - P(x)
几种常用的插值方法

几种常用的插值方法

几种常用的插值方法常用的插值方法包括线性插值、多项式插值、样条插值和径向基函数插值等，下面将依次介绍这些方法。

1.线性插值：线性插值是最简单的插值方法之一，它假设函数在两个已知点之间的变化是线性的。

对于给定的两个点(x0,y0)和(x1,y1)，线性插值公式为：y=y0+(x-x0)*(y1-y0)/(x1-x0)其中，y是需要插值的点对应的函数值，x是插值点的横坐标。

2.多项式插值：多项式插值方法通过在给定的一组点上构建一个多项式函数来进行插值。

常用的多项式插值方法包括拉格朗日插值和牛顿插值。

- 拉格朗日插值通过构建一个n次多项式来插值n+1个给定的点。

具体来说，对于给定的n+1个点(x0, y0), (x1, y1), ..., (xn, yn)，拉格朗日插值公式为：y = Σ(yk * lk(x))其中，lk(x)是拉格朗日基函数，计算公式为：lk(x) = Π((x - xj) / (xi - xj))，(j ≠ i)- 牛顿插值通过构建一个n次插值多项式来插值n+1个给定的点。

具体来说，对于给定的n+1个点(x0, y0), (x1, y1), ..., (xn, yn)，牛顿插值公式为：y = Σ(Π(x - xj) / Π(xi - xj) * finDiff(yj))其中，finDiff(yj)是每个节点的差商，计算公式为：finDiff(yj) = (ΣΠ(xj - xi) * yj) / ΣΠ(xi - xj)，(i ≠ j) 3.样条插值：样条插值方法通过使用分段函数来逼近给定的一组点。

常用的样条插值方法有线性样条插值和三次样条插值。

-线性样条插值在每两个相邻点之间使用线性函数进行插值，保证了插值函数的一阶导数是连续的。

-三次样条插值在每两个相邻点之间使用三次多项式进行插值，保证了插值函数的一阶和二阶导数都是连续的。

三次样条插值具有良好的平滑性和精度。

4.径向基函数插值：径向基函数插值是一种基于局部函数的插值方法，它假设函数值仅取决于与插值点的距离。