代数插值法的论述

1、代数插值法的论述代数插值法1. 插值法概述插值法是函数逼近的重要方法之一，有着广泛的应用 。在生产和实验中，函数f(x)或者其表达式不便于计算复杂或者无表达式而只有函数在给定点的函数值(或其导数值) ，此时我们希望建立一个简单的而便于计算的函数j(x)，使其近似的代替f(x)，有很多种插值法,其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点,常用的插值还有Hermit插值,分段插值和样条插值.这里主要介绍拉格朗日(Lagrange)插值和牛顿(Newton)插值。1.1拉格朗日插值1.1.1基本原理构造n次多项式Pn (x)= yk lk (x)=y0

2、l0 (x)+y1l1 (x)+ynln (x)，这是不超过n次的多项式，其中基函数lk(x)=显然lk (x)满足lk (xi)=此时 Pn(x)f(x),误差Rn(x)=f(x)-Pn(x)= 其中(a,b)且依赖于x，=（x-x0）(x-x1)(x-xn)很显然，当n=1、插值节点只有两个xk,xk+1时 P1(x)=yklk(x)+yk+1lk+1(x)其中基函数lk(x)= lk+1(x)= 1.1.2优缺点可对插值函数选择多种不同的函数类型，由于代数多项式具有简单和一些良好的特性，故常选用代数多项式作为插值函数。利用插值基函数很容易得到拉格朗日插值多项式，公式结构紧凑，在理论分析中

3、甚为方便，但当插值节点增减时全部插值基函数Lk(x)(k=0,1,n)均要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值可以克服这一缺点。1.1.3数值实验程序如下：#include<stdio.h>#define TRUE 1#define FALSE 0#define N 10#define M 2void main(void) double xN,yN,a,lN; int i,j,n,flag; double answer=0.00f; do printf("创建Lagrange插值多项式共用到N组(X,Y)值，请输入N

4、:"); scanf("%d",&n); if(n<=N&&n>=M) flag=FALSE; else if(n>N|n<=1) printf("对不起，你输入错误!n请确保你输入的N满足2<=N<=%d.",N); printf("n"); flag=TRUE; while(flag=TRUE); printf("n请输入需要计算的X值:"); scanf("%lf",&a); for(i=0;i<n;i+)

5、 printf("请输入第%d组(X,Y)的值:",i+1); scanf("%lf%lf",x+i,y+i); for(i=0;i<n;i+) li=1.0f; for(j=0;j<N;j+) if(i!=j) li*=(a-xj)/(xi-xj); else continue; answer+=li*yi; printf("f(%.3lf)=%lfn",a,answer); 实验结果Input n:4Input xn:O,4 0.55 0.65 0.8 0.9Input yn0.41075 0.57815 0.6967

6、5 0.88811 1.02652Please input x:0.596Nn(0.596)=0.6319141.2牛顿插值1.2.1基本原理构造n次多项式Nn(x)=f(x0)+f(x0,x1)(x-x0)+f(x0,x1,x2)(x-x0)(x-x1)+f(x0,x1,x2,xn)(x-x0)(x-x1)(x-xn)称为牛顿插值多项式，其中 (二个节点，一阶差商) (三个节点，二阶差商) (n+1个节点，n阶差商)注意：由于插值多项式的唯一性，有时为了避免拉格朗日余项Rn(x)中n+1阶导数的运算，用牛顿插值公式Rn (x)=f(x)-Nn(x)=f(x,x0,xn)n+1(x),其中n+

7、1(x)=(x-x0)(x-x1)(x-xn)1.2.2优缺点牛顿插值法具有承袭性和易变性的特点，当增加一个节点时，只要再增加一项就可以了即而拉格朗日插值若要增加一个节点时全部基函数都需要重新算过。牛顿插值法既适合于用来计算函数值，也适合于做理论推导，比如说可用来推导微分方程的数值求解公式。 1.2.3数值实验一、差商相关公式二、题目已知函数表如下：0.00.51.01.52.02.50.841470.857700.899240.948980.987770.999551计算用3次Newton插值多项式。2计算用5次Newton插值多项式。三、程序思想 根据实际计算理论，利用Newton插值多项

8、式计算，事先应知道其节点个数。所以，本程序设置在100个节点即最高次可达99次的多项式计算，通过输入节点个数来控制每次要计算的多项式的次数。 首先，计算各阶的函数值。 根据节点的个数与每阶阶商具有的阶商个数循环计算各阶商的值，并根据相应的节点下标控制输出各阶商值。 其次，输出最高阶表达式。 由于最高阶表达式是从0位开始计算的，所以，在知道节点下标的基础上，每次以二维数组两下标是否相等来输出相应的阶商，及x的值与节点的起止下标输出相应的表达式。 最后，根据输入的节点数计算其对应的函数值。3阶计算表达式，任意输入节点值，根据输入的节点值的大小判断其所在的范围，以输出表达式同样的思想计算节点对应的函

9、数值。最高阶表达式，亦是通过循环计算获得相应的函数值。四、计算结果：五、程序源代码。#include "stdafx.h"#include<stdio.h>void main(int argc,char* argv) int i1,i2,p,j,k,w,n=0; float x100,f100100,f1100,x1,x2,N1,N2=1.0,N3=0.0; printf("请输入节点个数w<=100: "); /输入节点个数 scanf("%d",&w); for(n=0;n<w;n+) /根据节点个

10、数和阶商的关系，用节点控制输入节点及对应的函数值 printf("x="); scanf("%f",&xn); printf("f(x)="); scanf("%f",&f1n); for(n=0;n<w;n+) /将节点对应的函数值送给二维数组 fn0=f1n; for(j=1;j<n;j+) /循环计算差商的值 k=j; for(p=0;k<n;k+,p+) /用k控制同一维的下标，用j控制维数，用p控制节点的起始下标 fkj=(fkj-1-fk-1j-1)/(xk-xp);

11、printf(" xi f(xi) 1阶差商"); /输出固定格式 for(i1=1;i1<n-1;i1+) /用i1作循环，循环输出（i1+1)阶差商作固定格式 printf(" %d阶差商",(i1+1); for(i1=0;i1<n;i1+) /循环输出节点的值 if(xi1>=0) /作判断一控制输出空格的长度以使每次输出起始位置对齐 if(xi1>=10&&xi1<100) printf("n%.5f ",xi1); else if(xi1>=100) printf(&qu

12、ot;n%.5f ",xi1); else printf("n%.5f ",xi1); else if(xi1<=-10) printf("n%.5f ",xi1); else if(xi1<=-100) printf("n%.5f ",xi1); else printf("n%.5f ",xi1); for(i2=0;i2<=i1;i2+) /此循环嵌在上一循环里作循环输出并判断，控制输出空格的长度使输出对齐 if(fi1i2>=0) if(fi1i2>10) if(fi1

13、i2>=100) printf("%.5f ",fi1i2); else printf("%.5f ",fi1i2); else printf("%.5f ",fi1i2); else if(fi1i2<=-10) if(fi1i2<=-100) printf("%.5f ",fi1i2); else printf("%.5f ",fi1i2); else printf("%.5f ",fi1i2); printf("nN%d(x)=%.5f+&q

14、uot;,n-1,f00); /输出最高阶表达式 for(i1=1;i1<n;i1+) for(j=1;j<n;j+) if(i1=j) /用i1,j的下标相等的差商值输出 if(fi1j<0) /负数加括号输出 printf("(%.5f)",fi1j); else printf("%.5f",fi1j); for(k=0;k<j;k+) /用k循环控制输出节点的值 printf("(x-%.5f)",xk); printf("n"); if(j<n-1) /根据判断在输出每一项后是

15、否输出“+” printf(" +"); printf("输入节点x1(用3次多项式计算)，x2(用%d次多项式计算):n",n-1); scanf("%f%f",&x1,&x2); /提示输入两个要计算的节点 for(i1=0;i1<n;i1+) /对x1进行判断早出其所在的区间的节点的下标值 if(x1>xi1) break; /判断下标后退出 if(n-i1)>=3) /判断其下标后是否还有3个节点，如果有就以次区间作计算 i2=i1; else /如果次下标后没有3个节点，将下标i1减2再作判

16、断 i1=i1-2; if(i1>=0) i2=i1; /此时i1>=0就以次下标开始作区间 else i2=i1+1; /在前边i1-2如果<0,则将其下标加1 i1=i2; N1=fi10; for(j=1;j<4;j+,i1+) N2=N2*fi1+1i1+1; /根据节点的区间和阶商的具有同一下标的关系，循环计算阶商的值 for(k=i2;k<i2+j;k+) /在前一循环基础上循环计算每阶商后对应节点间的值，并控制节点的末位 N2=N2*(x1-xk); N3=N2+N3; N2=1.0; N3=N1+N3; /将计算的值赋给N3并输出 printf("N3(%.5f)=%.5fn",x1,N3); N3=0.0; N1=f00; for(i1=1;i1<n;i1+) /以同样的方式计算最高阶的值 for(i2=0;i2<i1;i2+) N2=N2*(x2-xi2); N2=N2*fi1i1; N3=N2+N3; N2=1.0; N3=N1+N3; printf("N%d(%.5f)=%.5fn",n-1,x2,N3); /输出最高阶计算节点的值2.误差分析 依据f（x）数据表构造出来它的插值函数P（x）,然后，在给定点x计算P（x）的值作为