拉格朗日插值法
拉格朗日插值法可以帮助我们解决以下的问题
求x=3时f{x}的值。
示例1:
int xs[]={0,1,-1,2};
int ys[]={2,2,0,6};
//f(3)?
int val=lagrangePolynomial(3,xs,ys);
static int lagrangePolynomial(int x, int xs[],int ys[])
{
int c1,c2;
int i,j,n;
n=xs.length;
c1=0;
for(i=0;i<n;i++){
c2=ys[i];
for(j=0;j<n;j++)
{
if(j!=i)
c2=c2*(x-xs[j])/(xs
}
c1+=c2;
}
}
如果插值点是{(x_i,y_i)}i=1..n,那么希望构造出一组多项式F_i(x)使得
F_i(x_i)=1, F_i(x_j)=0 (j!=i)
其实就是构造一个函数, 这个函数在其中一点的值为1, 其它点的值为0 。
这样的话把n个这样的函数加权加起来得到的函数就是在每个点上的值都是需要的了。
注意1:
也就是说要构造“只受其中一个点影响”(这种讲法比较粗糙,因为和其他点的位置还是有关系)的函数。
如果这一点能办到,那么只要取f(x)=sum(y_i*F_i(x))就是所要的插值多项式。
Lagrange的插值方法其实就是直接构造出上述基函数:
F_i(x) = prod(x-x_j) / prod(x_i-x_j),其中prod是关于所有不等于i的j求乘积,
直接就可以验证F_i(x)满足前面提到的条件,
因为分子相当于确定了F_i(x)的所有根,分母则是归一化系数。
我们可以先用函数运算均匀的生成一些x点和其对应得数值对。
然后就可以用拉格朗日插值法来计算以提高效率。
具体使用见
static void lagrangeDemo()
{
int k=10000;
int a=2;
int x=0;
int y=0;
int m=0;
float data[]=new float[k];
Random random=new Random(System.currentTimeMillis());
for(int i=0;i<k;i++)
{
do{
m=random.nextInt((int)(kMaxX-kMinX));
data
}while(data
}
float res0,res1;
float diff=0;
float diffMax=0;
float diffRate=0;
float diffRateMax=0;
float diffAll=0;
for(int i=0;i<k;i++)
{
res0=count(a,data
res1=function(a,data
diff=(res1-res0);
if(Math.abs(diff)>diffMax)
diffMax=diff;
diffAll+=diff;
if(res1!=0)
{
diffRate=diff*100/res1;
if(Math.abs(diffRate)>diffRateMax)
diffRateMax=diffRate;
}
}
System.out.println("diffAll:"+diffAll+"diffMax:"+(diffMax)+"diffRateMax:"+diffRateMax+"%");
long time=System.currentTimeMillis();
for(int i=0;i<k;i++)
{
res0=count(a,data
}
System.out.println(" lagrange time:"+(System.currentTimeMillis()-time));
time=System.currentTimeMillis();
for(int i=0;i<k;i++)
{
res1=function(a,data
}
System.out.println("Normal time:"+(System.currentTimeMillis()-time));
}
static HashMap <String,float[][]>hashMap=new HashMap<String,float[][]>();
final static int kSection=100;
static float count(int a,float x)
{
String key=""+a;
float f[][]=hashMap.get(key);
if(f==null)
f=getPairs(a);
hashMap.put(key, f);
}
return lagrangePolynomial(x,f[0],f[1]);
}
final static float kMinX=0;
final static float kMaxX=100;
static float[][] getPairs(int a)
{
float pairs[][]=new float[2][kSection+1];
float xs[]=pairs[0];
float ys[]=pairs[1];
int n=kSection;
for(int i=0;i<=n;i++)
{
xs
ys
}
}
static float function(int a,float x)
{
float y=x*x*x*x/(a*a+x*x*x*x+x*x);
int n=1000;
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
y=y*n*(n+2)/((n+1)*(n+3))-1;
}
}
return y;
}
static int lagrangePolynomial(int x, int xs[],int ys[])
{
int c1,c2;
int i,j,n;
n=xs.length;
c1=0;
for(i=0;i<n;i++){
c2=ys
{
if(j!=i)
c2=c2*(x-xs[j])/(xs
}
c1+=c2;
}
}
static float lagrangePolynomial(float x, float xs[],float ys[])
{
float c1,c2;
int i,j,n;
n=xs.length;
c1=0;
for(i=0;i<n;i++){
c2=ys
{
if(j!=i)
c2=c2*(x-xs[j])/(xs
}
c1+=c2;
}
}
diffAll:NaNdiffMax:4.8828125E-4diffRateMax:-6.088556E-6%
lagrange time:687
Normal time:99359
注意:只有函数f(x)非常复杂,且f(x)的值随X变化不是很大时,用拉格朗日插值法来计算才有意义。
否则拉格朗日插值法的效率比直接用函数计算还要低。
http://hwiechern.blog.163.com/blog/static/106796622007913104859712/