- 浏览: 12848184 次
- 性别:
- 来自: 大连
文章分类
最新评论
-
sanrenxing_1:
GoEasy 实时推送支持IE6-IE11及大多数主流浏览器的 ...
WindowsPhone消息推送服务 -
张砚辉:
两侧照片绕Y轴旋转后有锯齿,请问锯齿解决方案,很长时间没解决
自定义带倒影和偏转的超炫Gallery -
knight_black_bob:
能不能把你自己的博客整理下分类下,写了这么多 ,都不知道怎么查 ...
Android_View,ViewGroup,Window之间的关系 -
jeasonyoung:
你这个代码实现在iOS8下应该是滑不动的
UISlider 滑块控件—IOS开发 -
wx_hello:
如果能写个可运行的java程序,不胜感激。。。
rs232串口通信原理
拉格朗日插值法
拉格朗日插值法<wbr style="line-height:25px"><br style="line-height:25px"><span style="color:#ff00ff; line-height:25px">拉格朗日插值法</span>可以帮助我们解决以下的问题<br style="line-height:25px"><span style="color:#000080; line-height:25px"><wbr style="line-height:25px">已知x取值0,1,-1,2时,f{x}取值2,2,0,6<br style="line-height:25px">
求x=3时f{x}的值。</wbr></span><wbr style="line-height:25px"><br style="line-height:25px"><span style="line-height:25px">示例1</span>:<br style="line-height:25px"><span style="color:#3366ff; line-height:25px">intxs[]={0,1,-1,2};<br style="line-height:25px">
intys[]={2,2,0,6};<br style="line-height:25px"></span><span style="color:#808080; line-height:25px">//f(3)?</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">intval=lagrangePolynomial(3,xs,ys);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">staticint</span><span style="color:#3366ff; line-height:25px">lagrangePolynomial(intx,intxs[],intys[])</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">intc1,c2;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">inti,j,n;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">n=xs.length;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">c1=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(i=0;i<n;i++){</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">c2=ys[i]</span><span style="color:#3366ff; line-height:25px">;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(j=0;j<n;j++)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">if(j!=i)</span><br style="line-height:25px"><span style="line-height:25px; font-style:normal"><span style="color:#3366ff; line-height:25px">c2=c2*(x-xs[j])/(xs<wbr style="line-height:25px">-xs[j]);<br style="line-height:25px">
}<br style="line-height:25px">
c1+=c2;<br style="line-height:25px">
}<br style="line-height:25px"></wbr></span><span style="color:#993300; line-height:25px">return</span><span style="color:#3366ff; line-height:25px">c1;<br style="line-height:25px">
}</span></span><br style="line-height:25px"><span style="line-height:25px"><wbr style="line-height:25px">Lagrange插值方法的核心就是构造一组基函数</wbr></span><wbr style="line-height:25px">。<br style="line-height:25px"><span style="color:#003366; line-height:25px">如果插值点是</span><span style="color:#0000ff; line-height:25px">{(x_i,y_i)}i=1..n</span><span style="color:#003366; line-height:25px">,那么希望构造出一组多项式</span><span style="color:#ff6600; line-height:25px">F_i(x)</span><span style="color:#003366; line-height:25px">使得</span><br style="line-height:25px"><span style="color:#0000ff; line-height:25px">F_i(x_i)=1,F_i(x_j)=0(j!=i)</span><br style="line-height:25px"><span style="color:#003366; line-height:25px">其实就是构造一个函数,这个函数在其中一点的值为1,其它点的值为0。</span><br style="line-height:25px"><span style="color:#003366; line-height:25px">这样的话把n个这样的函数加权加起来得到的函数就是在每个点上的值都是需要的了。</span><br style="line-height:25px"><span style="line-height:25px">注意1</span>:<wbr style="line-height:25px">这里的多项式是一组。函数即是指多项式。其实针对每个插入点构造一个多项式(函数)<wbr style="line-height:25px">。<br style="line-height:25px"><span style="line-height:25px"><wbr style="line-height:25px">注意2:</wbr></span>关于如何得到多项式的请参阅<a target="_blank" href="http://hwiechern.blog.163.com/blog/static/106796622007913104859712/" style="color:rgb(207,121,28); line-height:25px; text-decoration:none">http://hwiechern.blog.163.com/blog/static/106796622007913104859712/</a><br style="line-height:25px">
也就是说要构造“只受其中一个点影响”(这种讲法比较粗糙,因为和其他点的位置还是有关系)的函数。<br style="line-height:25px">
如果这一点能办到,那么只要取<span style="color:#ff6600; line-height:25px">f(x)=sum(y_i*F_i(x))</span>就是所要的插值多项式。<br style="line-height:25px">
Lagrange的插值方法其实就是直接构造出上述基函数:<br style="line-height:25px"><span style="color:#0000ff; line-height:25px">F_i(x)=prod(x-x_j)/prod(x_i-x_j)</span>,其中<span style="color:#800000; line-height:25px">prod</span>是关于所有不等于i的j求乘积,<br style="line-height:25px"><span style="color:#000080; line-height:25px">直接就可以验证F_i(x)满足前面提到的条件,<br style="line-height:25px">
因为分子相当于确定了F_i(x)的所有根,分母则是归一化系数。</span><br style="line-height:25px"><br style="line-height:25px"><wbr style="line-height:25px"><span style="color:#003366; line-height:25px">对于一些很复杂的函数运算。也可以用拉格朗日插值法来计算以提高效率<wbr style="line-height:25px">。</wbr></span><br style="line-height:25px">
我们可以先用函数运算均匀的生成一些x点和其对应得数值对。<br style="line-height:25px">
然后就可以用拉格朗日插值法来计算以提高效率。<br style="line-height:25px">
具体使用见<span style="line-height:25px"><wbr style="line-height:25px">实例1</wbr></span><wbr style="line-height:25px">:<br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">staticvoid</span><span style="color:#3366ff; line-height:25px"></span><span style="color:#ff6600; line-height:25px">lagrangeDemo</span><span style="color:#3366ff; line-height:25px">()</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">intk=10000;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">inta=2;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">intx=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">inty=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">intm=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatdata[]=newfloat[k];</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">Randomrandom=newRandom(System.currentTimeMillis());</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(inti=0;i<k;i++)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">do{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">m=random.nextInt((int)(kMaxX-kMinX));</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px">=m+1/random.nextInt();</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><span style="color:#993300; line-height:25px">while</span><span style="color:#3366ff; line-height:25px">(data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px"><kMinX||data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px">>kMaxX);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatres0,res1;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatdiff=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatdiffMax=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatdiffRate=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatdiffRateMax=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">floatdiffAll=0;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(inti=0;i<k;i++)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">res0=count(a,data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px">);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">res1=function(a,data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px">);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">diff=(res1-res0);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">if(Math.abs(diff)>diffMax)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">diffMax=diff;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">diffAll+=diff;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">if</span><span style="color:#3366ff; line-height:25px">(res1!=0)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">diffRate=diff*100/res1;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">if</span><span style="color:#3366ff; line-height:25px">(Math.abs(diffRate)>diffRateMax)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">diffRateMax=diffRate;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">System.out.println("diffAll:"+diffAll+"diffMax:"+(diffMax)+"diffRateMax:"+diffRateMax+"%");</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">longtime=System.currentTimeMillis();</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(inti=0;i<k;i++)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">res0=count(a,data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px">);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">System.out.println("lagrangetime:"+(System.currentTimeMillis()-time));</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">time=System.currentTimeMillis();</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(inti=0;i<k;i++)</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">{</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">res1=function(a,data</span><wbr style="line-height:25px"><span style="color:#3366ff; line-height:25px">);</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">System.out.println("Normaltime:"+(System.currentTimeMillis()-time));</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px">}</span><span style="color:#808080; line-height:25px"><br style="line-height:25px"></span><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">static</span><span style="color:#3366ff; line-height:25px">HashMap<String,float[][]>hashMap=newHashMap<String,float[][]>();</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">finalstaticint</span><span style="color:#3366ff; line-height:25px">kSection=100;</span><br style="line-height:25px"><span style="color:#3366ff; line-height:25px"></span><span style="color:#993300; line-height:25px">staticfloat</span><span style="color:#3366ff; line-height:25px">count(inta,floatx)<br style="line-height:25px">
{<br style="line-height:25px">
Stringkey=""+a;<br style="line-height:25px">
floatf[][]=hashMap.get(key);<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">if</span><span style="color:#3366ff; line-height:25px">(f==null)</span>
<div style="line-height:25px">
<span style="color:#3366ff; line-height:25px"> {<br style="line-height:25px">
f=getPairs(a);<br style="line-height:25px">
hashMap.put(key,f);<br style="line-height:25px">
}<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">return</span><span style="color:#3366ff; line-height:25px">lagrangePolynomial(x,f[0],f[1]);<br style="line-height:25px">
}<br style="line-height:25px">
finalstaticfloatkMinX=0;<br style="line-height:25px">
finalstaticfloatkMaxX=100;<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">staticfloat</span><span style="color:#3366ff; line-height:25px">[][]getPairs(inta)<br style="line-height:25px">
{<br style="line-height:25px">
floatpairs[][]=newfloat[2][kSection+1];<br style="line-height:25px">
floatxs[]=pairs[0];<br style="line-height:25px">
floatys[]=pairs[1];<br style="line-height:25px">
intn=kSection;<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(inti=0;i<=n;i++)<br style="line-height:25px">
{<br style="line-height:25px">
xs<wbr style="line-height:25px">=kMinX+(kMaxX-kMinX)*i/n;<br style="line-height:25px">
ys<wbr style="line-height:25px">=function(a,xs<wbr style="line-height:25px">);<br style="line-height:25px">
}<br style="line-height:25px"></wbr></wbr></wbr></span><span style="color:#993300; line-height:25px">return</span><span style="color:#3366ff; line-height:25px">pairs;<br style="line-height:25px">
}<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">staticfloat</span><span style="color:#3366ff; line-height:25px">function(inta,floatx)<br style="line-height:25px">
{<br style="line-height:25px">
floaty=x*x*x*x/(a*a+x*x*x*x+x*x);<br style="line-height:25px">
intn=1000;<br style="line-height:25px">
inti,j;<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(i=0;i<n;i++)<br style="line-height:25px">
{<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(j=0;j<n;j++)<br style="line-height:25px">
{<br style="line-height:25px">
y=y*n*(n+2)/((n+1)*(n+3))-1;<br style="line-height:25px">
}<br style="line-height:25px">
}<br style="line-height:25px">
returny;<br style="line-height:25px">
}<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">staticint</span><span style="color:#3366ff; line-height:25px">lagrangePolynomial(intx,intxs[],intys[])<br style="line-height:25px">
{<br style="line-height:25px">
intc1,c2;<br style="line-height:25px">
inti,j,n;<br style="line-height:25px">
n=xs.length;<br style="line-height:25px">
c1=0;<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(i=0;i<n;i++){<br style="line-height:25px">
c2=ys<wbr style="line-height:25px">;<br style="line-height:25px"></wbr></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(j=0;j<n;j++)<br style="line-height:25px">
{<br style="line-height:25px">
if(j!=i)<br style="line-height:25px">
c2=c2*(x-xs[j])/(xs<wbr style="line-height:25px">-xs[j]);<br style="line-height:25px">
}<br style="line-height:25px">
c1+=c2;<br style="line-height:25px">
}<br style="line-height:25px"></wbr></span><span style="color:#993300; line-height:25px">return</span><span style="color:#3366ff; line-height:25px">c1;<br style="line-height:25px">
}<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">staticfloat</span><span style="color:#3366ff; line-height:25px"></span><span style="color:#ff6600; line-height:25px">lagrangePolynomial</span><span style="color:#3366ff; line-height:25px">(floatx,floatxs[],floatys[])<br style="line-height:25px">
{<br style="line-height:25px">
floatc1,c2;<br style="line-height:25px">
inti,j,n;<br style="line-height:25px">
n=xs.length;<br style="line-height:25px">
c1=0;<br style="line-height:25px"></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(i=0;i<n;i++){<br style="line-height:25px">
c2=ys<wbr style="line-height:25px">;<br style="line-height:25px"></wbr></span><span style="color:#993300; line-height:25px">for</span><span style="color:#3366ff; line-height:25px">(j=0;j<n;j++)<br style="line-height:25px">
{<br style="line-height:25px">
if(j!=i)<br style="line-height:25px">
c2=c2*(x-xs[j])/(xs<wbr style="line-height:25px">-xs[j]);<br style="line-height:25px">
}<br style="line-height:25px">
c1+=c2;<br style="line-height:25px">
}<br style="line-height:25px"></wbr></span><span style="color:#993300; line-height:25px">return</span><span style="color:#3366ff; line-height:25px">c1;<br style="line-height:25px">
}</span><br style="line-height:25px"><span style="line-height:25px"><wbr style="line-height:25px">运行结果</wbr></span><wbr style="line-height:25px">:<br style="line-height:25px"><span style="color:#3366ff; line-height:25px">diffAll:NaNdiffMax:4.8828125E-4diffRateMax:-6.088556E-6%<br style="line-height:25px">
lagrangetime:687<br style="line-height:25px">
Normaltime:99359</span><br style="line-height:25px"><span style="line-height:25px">注意</span>:只有函数f(x)非常复杂,且f(x)的值随X变化不是很大时,用拉格朗日插值法来计算才有意义。<br style="line-height:25px">
否则拉格朗日插值法的效率比直接用函数计算还要低。<br style="line-height:25px"><wbr style="line-height:25px">关于拉格朗日插值法的更多数学知识请参考<br style="line-height:25px"><a target="_blank" href="http://hwiechern.blog.163.com/blog/static/106796622007913104859712/" style="color:rgb(207,121,28); line-height:25px; text-decoration:none">http://hwiechern.blog.163.com/blog/static/106796622007913104859712/</a></wbr></wbr>
</div>
</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
相关推荐
拉格朗日插值法 拉格朗日插值法MATLAB实现(附代码、实例、详解).pdf 拉格朗日插值法MATLAB实现(附代码、实例、详解).pdf 拉格朗日插值法MATLAB实现(附代码、实例、详解).pdf 拉格朗日插值法MATLAB实现(附代码...
用C++代码来编写相应的拉格朗日插值法,解决拉格朗日插值法的相关问题.
本程序使用java实现拉格朗日插值法,使用者可以根据自己需要进行修改
数值分析中的拉格朗日插值法,牛顿插值法,三次样条插值法的matlab代码描述。
运用拉格朗日插值法给空缺数据进行插值,通过调用scipy中的lagrange实现
数值分析中牛顿插值与拉格朗日插值法的代码
在数值分析中,拉格朗日插值法是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。许多实际问题中都用函数来表示某种内在联系或规律,而不少函数都只能通过实验和观测来了解。如对实践中的某个物理量...
拉格朗日插值法(理论详解).pdf 拉格朗日插值法(理论详解).pdf 拉格朗日插值法(理论详解).pdf 拉格朗日插值法(理论详解).pdf 拉格朗日插值法(理论详解).pdf 拉格朗日插值法(理论详解).pdf 拉格朗日插值法...
拉格朗日插值法python运用拉格朗日插值法给空缺数据进行插值,通过调用scipy中的lagrange实现(1).zip
内容概要:拉格朗日插值法是一种用于给定一些数据点的函数近似的方法,它可以通过一个简单的公式来构造一个多项式,使得该多项式可以通过给定的数据点并且尽可能地符合数据点的分布。 适合人群:新手小白,有些编程...
数值计算中关于拉格朗日插值的描述及matlab程序
c++拉格朗日插值法 数值分析 c++拉格朗日插值法 数值分析
拉格朗日插值法
根据拉格朗日插值法编写的完整C代码,很方便,只需输入节点数和节点数据以及插入的数据。
拉格朗日插值法(Lagrange Interpolation)是一种用于估算函数在离散数据点之间值的插值方法。它在数学、工程和计算机科学领域都有广泛的应用。本博客将深入探讨拉格朗日插值法的原理、实现步骤、优点和限制,并提供...
拉格朗日 插值法 课后作业 绝对正确.......... 上机程序
这是一个基于计算方法拉格朗日插值法实现的C语言版本的小程序,可以计算不同节点分割下的估计值及其误差值
拉格朗日插值法就是构造一个多项式,使得恰好在每一个x处取到对应的y 首先,n+1个点(xi,yi)若xi不同,则可以确定唯一的最高幂次不超过n的多项式。而如果题目直接或是间接给出了n+1个点,让我们求由这些点构成的...
数值分析作业 拉格朗日插值法 c程序语言 编程