龍格現象產生的原因？

01-07

在數值分析中，高次插值會產生龍格現象。即在兩端處波動極大，產生明顯的震蕩。這種現象產生的原因是什麼？是截斷誤差的增大還是舍入誤差的增大？為什麼兩端波動大而中間部分仍有較好的精度？？

首先，不是舍入誤差，而是系統誤差（應該是這個名字？總之就是多項式插值本身的性質）

詳細算一下這個誤差。

一般的插值余項公式為

$R_n(x)=f(x)-p_n(x)=frac{1}{(n+1)!}{prod_{j=0}^n(x-x_j^{(n)})}f^{(n+1)}(xi)label{1}$

這裡 ${x_j^{(n)}}_{j=0}^n$ 為插值區間 $[a,b]$ 中的插值節點， $xi$ 為 $[a,b]$ 區間中一點。

Runge現象說的是，對 $f(x)=frac{1}{1+x^2}$ 在區間 $[-5,5]$ 上進行n次多項式插值，當 $n ightarrow infty$ 時， $p_n(x) rightarrow f(x)$ 。更確切的說，當 $|x|<x_capprox3.63$ 時， $p_n(x) ightarrow f(x)$ $max |R_n(x)| ightarrow 0$ ,當 $x_c<|x|<5$ 時， $p_n(x) rightarrow f(x)$ , $max |R_n(x)| rightarrow 0$ 。

解釋這一現象，直接計算

$|R_n(x)| leq frac{1}{(n+1)!}max{Pi_{j=1}^{n}(x-x_j^{(n)}}max{{f^{(n+1)}(x)}}$

很困難，因為微分項 $max{f^{(n+1)}(x)}$ 不太容易直接求導計算。為方便起見，令 $w_n(x)=Pi_{j=0}^{n}(x-x_j^{(n)})$ .

複變函數中的Cauchy積分公式 $f^{(n)}(xi)=frac{n!}{2pi i}int_Cfrac{f(z)}{(z-xi)^{n+1}}dz$ 可以很方便的計算 $f^{(n)}(xi)$ 的值，故將插值余項公式延拓到複平面上，並應用Cauchy積分公式，得

$R_n(z)=frac{1}{(n+1)!}w_n(z)frac{(n+1)!}{2pi i}int_{C_T}frac{f(xi)}{w_n(xi)(xi-z)}dxi$

其中 $C_T$ 是區域 $T$ 的邊界，區域 $T$ 應滿足 $f$ 在 $T$ 中解析且所有插值節點都在 $T$ 中。（注意， $f(z)=frac{1}{1+x^2}$ 的奇點為 $pm i$ 故區域不能包含 $pm i$ ）

化簡，得到

$R_n(z)=frac{1}{2pi i}int_{C_T}frac{w_n(z)}{w_n(xi)}frac{f(xi)}{xi-z}dxi$

所以現在的關鍵就是通過分析函數 $w_n(z)$ 在 $n ightarrow infty$ 時的性態，選擇一個圍道，來估計積分的值。

$w_n(z)=r^n$ 的圖象大概是這樣的（來自【2】）

這是當 $n=3$ 時，三個節點分別取0，1，2i 時的圖象。隨著r的增大，圖象逐漸外擴。當r足夠大時， $w_n(z)=r^n$ 的圖象很接近一個包含所有節點的圓。因此我們可以選取 $w_n(xi)=r^n$ 作為積分的圍道 $C_1$

有一個很好的結論：此時對 $C_1$ 內部任意的 $z$ , $lim_{n ightarrowinfty}|frac{w_n(z)}{w_n(xi)}|=0$ （ $w_n(z)=r_1^n$ 且 $r_1<r$ ）而對於 $C_1$ 外部任意的 $z$ , $lim_{n ightarrowinfty}|frac{w_n(z)}{w_n(xi)}|=infty$ （ $w_n(z)=r_2$ 且 $r_2>r$ ）

於是，當 $C_1$ 不包含 $f(z)$ 的奇點 $pm i$ 時，可以直接選取 $C_1$ 做圍道計算 $R_n(z)$ ，此時

$lim_{n ightarrowinfty}R_n(z)=Mlim_{n ightarrowinfty}|frac{w_n(z)}{w_n(xi)}|=0$

隨著 $r$ 變大，曲線 $C_1$ 與 $x$ 軸正方向交點向右移動。當 $C_1$ 恰好經過 $pm i$ 時，曲線 $C_1$ 與 $x$ 軸正方向交點為 $x_capprox3.63$ .也就是說，當 $|x|<x_c$ 時，可以選取 $C_1$ 使 $x$ 在 $C_1$ 內部而 $pm i$ 在 $C_1$ 外部，這時誤差估計滿足上式，插值多項式收斂。

而當 $r>x_c$ 時，奇點 $pm i$ 在 $C_1$ 的內部，因此需在奇點附近挖「洞」，記「洞」的邊緣為 $C^*$ ，此時有

$lim_{n ightarrowinfty}R_n(z)=lim_{n ightarrowinfty}frac{1}{zpi i}(int_{C_1}frac{w_n(z)}{w_n(xi)}frac{f(xi)}{xi-z}-int_{C^*}frac{w_n(z)}{w_n(xi)}frac{f(xi)}{xi-z})=0-infty=infty$

此時插值多項式發散。

為什麼將等距節點換成Chebyshev節點時就不會出現發散的情況呢？因為Chebyshev節點對應的 $w_n(z)$ $=r^n$ 在經過奇點 $pm i$ 時是一個以 $pm 5$ 為焦點的橢圓，因此對於任意 $xin[-5,5]$ ,都可找到一個r，使得 $w_n(xi)=r^n$ 包含 $x$ 而不包含 $pm i$ ,和上面同理，插值多項式收斂。

參考材料

【1】James F. Epperson , "On the Runge Example " , Amer. Math. Monthly, 94(1987), 329-341

這篇文章以本科知識的角度解釋了Runge現象，並附加了幾個例子。

【2】Phillip J. Davis, Interpolation and Approximation, Dover, New York, 1975

這本書的第三章、第四章詳細的討論了高次多項式插值的余項和收斂性。

簡單地講，並不是所有函數都長得很像多項式。

總存在一些不像多項式的，如果你強行按照等距節點的方式取插值多項式，就可能出現這問題。

英文維基上有一些提示，Runge"s phenomenon https://en.wikipedia.org/wiki/Runge%27s_phenomenon

感謝樓上貼出wiki的回答，主要是因為誤差項里的高階導數產生的誤差一級一級傳播

我和你抱著同樣的問題在百度里尋找答案，可惜沒有找到，但我想把我的想法說給你聽，交流才能得到解決——這是我一直的看法。

在做插值的時候，我們選取的是等距的節點，而有一種修正龍格現象的方法就是切比雪夫多項式零點插值。這種方法選取的節點在端點處是密集的。我們可以想像無論節點選取的多少，插值多項式總是在區間的某個中間區域是逼近的很好的！（至於原因，應該和插值函數的構造原理有關，留待討論吧）這一點龍格證明過，可是證明的過程我沒有找到。而在區間端點大量取值，使得端點的模擬就更可能的逼近，我們可以想像成我們分別對區間的端點附近做插值，而區間中間則是無論如何都收斂的。這裡大部分都是一些想法，我沒有動筆算，畢竟我也是不想動太多腦子才到網上去查現有的答案的，希望能有更好的解答！而這種現象出現的原因應該是舍入誤差，而為何會對短點附近影響會比中間的大我也不太清楚