Runge Kutta 现象

多项式插值一般在2-5次为宜，最多不超过6，7次。也就是说，在节点数很多的时候，最好将它们分组，分段，对每段则分别用低次多项式插值，这样效果比较接近真实。片面的追求高次多项式，将不会得到好结果。

一个著名的例子是Runge给的，他是Weierstruss在Berlin的学生，也是F. Klein在Gottingen的同事。
用于模拟常微分方程的解的重要的一类迭代法，龙格－库塔法（Runge-Kutta）是由他和Kutta共同发明的。月球上的Runge陨石坑 (Runge crater) 以他命名。

f(x)=1/(1+25*x^2)
在[-1，1]内取n+1（在这里取n=10）个等距节点，做n次牛顿插值的结果如下，

其中红线为插值结果，黑线为被插值的函数，可以看出，在[-.2，.2]区间内，插值结果很好，但随着区域的扩大，出现了很大的偏差，特别是在-1，1两点附近，插值多项式基本不能描述被插函数。
这就是Runge-Kutta现象。


源代码如下，
=========demo_RungeKutta.m:

x_node =-1:.2:1;
y_node = 1./(1+25.*x_node.*x_node);
a = mynewtonCoeff(x_node,y_node);
x=-1:.01:1;
y = mynewtonPoly(a,x_node,x);
plot(x_node,y_node,'*b',x,y,'r',x,y1,'k');

===========mynewtonCoeff.m:

function a = mynewtonCoeff(xData,yData)
% Returns coefficients of Newton's polynomial.
% USAGE: a = newtonCoeff(xData,yData)
% xData = x-coordinates of data points.
% yData = y-coordinates of data points.

n = length(xData);
a = yData;
for k = 2:n
a(k:n) = (a(k:n) - a(k-1))./(xData(k:n) - xData(k-1));
end

=========mynewtonPoly.m

function p = mynewtonPoly(a,xData,x)
% evaluate the value of Newton's polynomial at x.
% USAGE: p = newtonPoly(a,xData,x)
% a = coefficient array of the polynomial;
% must be computed first by newtonCoeff.
% xData = x-coordinates of data points.

n = length(xData);

p = a(n)*ones(size(x));
for k = 1:n-1;
p = a(n-k) + (x - xData(n-k)).*p;
end