Runge现象：多项式插值不见得次数越高越准确
icon2 Brain Storm | icon4 2009-12-06 18:35| icon330 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    今天学到了一个新的名词，Runge现象。1901年，Carl David Tolmé Runge意外地发现，用差值插值多项式逼近函数f(x)=1/(1+25x^2)时出现了一些反常的现象。如图，灰色的粗线就是Runge函数在[-1,1]上的图象。蓝色虚线是过[-1,1]上的6个等距点所得到的5次多项式，红色虚线是过[-1,1]上的10个等距点所得到的9次多项式。可以看到，当次数变高时，插值多项式反而变得更不准确。


 
    事实上，当次数n趋于无穷时，该区间上的最大误差值也将趋于无穷大！

Posted in Brain Storm
Tags: , , ,
Trackback: http://www.matrix67.com/blog/archives/2599/trackback
我猜您可能还喜欢：

30 条回复

  • 楼层: 沙发 | 2009-12-06 18:38 | www.3158.cn 说：

    第一次听过这种现象。。。

  • 楼层: 板凳 | 2009-12-06 18:39 | 3158.cn 说：

    不过看起来，好像有点难懂。。

  • 楼层: 地毯 | 2009-12-06 19:36 | xxwzy 说：

    膜拜LS小广告。。

  • 楼层: 地板 | 2009-12-06 20:10 | 3WATER 说：

    刚刚交了这个的作业
    用cos(2pi i/n)作为插值点的话逼近效果不错

  • 楼层: 地下室 | 2009-12-06 20:27 | chys 说：

    interpolation叫插值不叫差值吧。。

  • 楼层: 地基 | 2009-12-06 20:43 | Googol 说：

    这个就是信号里对模拟信号采样成数字信号时出现的问题。那个误差很小的地方似乎是叫主瓣，很大的地方叫副瓣。主瓣的误差越小，副瓣的误差越大。不过具体细节记不清了，大学学的，多年没用过的知识了……

  • 楼层: 地壳 | 2009-12-06 20:56 | Магсн 说：

    汗，只知道泰勒展开。。

  • 楼层: 地幔 | 2009-12-06 21:01 | Магсн 说：

    matrix67大大，为什么会有这种现象？

  • 楼层: 地核 | 2009-12-06 21:18 | wuzhengkai 说：

    为什么啊？

  • 楼层: 10楼 | 2009-12-06 23:00 | picture 说：

    感觉应该是过拟合了...

  • 楼层: 11楼 | 2009-12-06 23:13 | tigertooth4 说：

    还有gibbs现象，也是类似问题 http://en.wikipedia.org/wiki/Gibbs_phenomenon

  • 楼层: 12楼 | 2009-12-06 23:31 | cykerway 说：

    上学期数值分析的作业就是这个……感觉多项式本身的弯曲特性，为了适应某些点会导致其他点误差增大，这个变化是整体的。打碎成样条插值就不会了。

  • 楼层: 12a楼 | 2009-12-07 8:17 | 老杨 说：

    就是加窗之后旁瓣泄露啊

  • 楼层: 14楼 | 2009-12-07 14:03 | Tweets that mention Matrix67: My Blog » Blog Archive » Runge现象：多项式插值不见得次数越高越准确 -- Topsy.com 说：

    [...] This post was mentioned on Twitter by zeqing and 阳阳猪的 GR Share, FXCarl. FXCarl said: Runge现象：多项式插值不见得次数越高越准确 http://ff.im/-cxqoi [...]

  • 楼层: 15楼 | 2009-12-07 17:11 | ivan 说：

    So queer……

  • 楼层: 16楼 | 2009-12-07 23:21 | 严酷的魔王 说：

    貌似有中文翻译为龙格现象

    http://zh.wikipedia.org/wiki/%E9%BE%99%E6%A0%BC%E7%8E%B0%E8%B1%A1

  • 楼层: 17楼 | 2009-12-08 12:09 | fdsafasdfg 说：

    的确，误差在插值计算中可能被扩散或方法，在大范围使用高次代数插值不适宜的，一般来说，Runge现象是由函数的高阶导数无界导致的，要提高差值函数的逼近效果，可以采取分段低次插值和分段光滑插值

  • 楼层: 18楼 | 2009-12-08 15:12 | biohu 说：

    看来不能迷信多项展开式

  • 楼层: 19楼 | 2009-12-08 15:52 | yh 说：

    考虑信息论。。
    应该就好理解了？

  • 楼层: 20楼 | 2009-12-08 15:57 | yh 说：

    比如朴素的科学理论的公理和假设比非常复杂的宗教准确的多

  • 楼层: 21楼 | 2009-12-08 19:49 | 白左 说：

    哇哈哈~我们在第一次学用matlab的时候就学习了这个东西了~~只是讲的不是很深。。也没有给出证明。。。

  • 楼层: 22楼 | 2009-12-08 22:14 | 3.1415926 坚持每天进步一点！ » 埃尔米特插值多项式 说：

    [...] [1] http://www.matrix67.com/blog/archives/2599 [2] http://zh.wikipedia.org/wiki/%E9%BE%99%E6%A0%BC%E7%8E%B0%E8%B1%A1 [3] [...]

  • 楼层: 23楼 | 2009-12-09 9:49 | ykzls 说：

    试过.

  • 楼层: 24楼 | 2009-12-10 20:04 | NirViaje 说：

    这个就是信号里对模拟信号采样成数字信号时出现的问题。那个误差很小的地方似乎是叫主瓣，很大的地方叫副瓣。主瓣的误差越小，副瓣的误差越大。不过具体细节记不清了，大学学的，多年没用过的知识了……
    =-=-=-=-=-=-=-=
    完全两回事，矩形窗的Fourier Trans是sinc，由此造成的旁瓣，完全是个超越函数

    解决Runge现象->分段spline

  • 楼层: 25楼 | 2009-12-12 1:01 | imstupid 说：

    这个不是大一的数分教材里就有么

  • 楼层: 26楼 | 2009-12-12 1:52 | pchu 说：

    同意24L，应该不是窗的问题（嘛我也没系统学过），是等距采样的结果，而且也和Fourier没什么关系吧。还是spline和Bernstein多项式好

  • 楼层: 27楼 | 2009-12-12 19:36 | 仙雾 说：

    在某一段拟合得越来越像 不在这一段上时就不像了

  • 楼层: 28楼 | 2009-12-14 8:51 | 两仪 说：

    其实是因为Runge方程的特点吧，这样还要取equal-space的点的话会使得两边的拟合出现非常大的误差。。。有两个方法，一个方法就是不用多项式插值，或者改变选点的方法，最有名的是取Chebyshev点

  • 楼层: 29楼 | 2011-08-19 9:40 | trek jersey 说：

    没学过！

  • 楼层: 30楼 | 2011-11-18 13:23 | titanlizard 说：

    求InterpolatingPolynomial程序源码

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。