#### 期刊菜单

Runge现象的研究
Research on Runge Phenomenon

Abstract: Firstly, this paper explains the Runge phenomenon generated by high-order polynomial inter- polation, and proves that the interpolation polynomial divergence is obtained by calculating the systematic error. Secondly, taking the Runge function, inverse trigonometric function and fractional function as examples, the interpolation polynomial of the function is obtained by using the equally spaced Newton interpolation, and then the interpolation residual function expression is obtained, and then the midpoint of adjacent two nodes is calculated. The error at the location determines that the above three functions have generated the Runge phenomenon. Thirdly, the three algorithms of Chebyshev node, piecewise linear interpolation and cubic spline interpolation are introduced and verified, which can avoid the Runge phenomenon. Finally, the approximation performance index is proposed, and based on the optimal polynomial construction coefficient and order double determination method, the algorithm has excellent function approximation effect while avoiding the Runge phenomenon.

1. 引言

2. 分析Runge现象

20世纪初，数学家龙格指出，对于连续函数：

$R\left(x\right)=\frac{1}{1+25{x}^{2}}$

$\left\{\left({x}_{i},{y}_{i}\right)|{x}_{i}=-1+2i/n,{y}_{i}=R\left({x}_{i}\right),i=0,1,\cdots ,n\right\}$

${p}_{n}\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\cdots +{a}_{0}$

$\begin{array}{l}a={\left[{a}_{0},{a}_{1},\cdots ,{a}_{n}\right]}^{\text{T}}\in {R}^{n+1}\\ V=\left(\begin{array}{cccc}1& {x}_{0}& \cdots & {x}_{0}^{n}\\ 1& {x}_{1}& \cdots & {x}_{1}^{n}\\ ⋮& ⋮& & ⋮\\ 1& {x}_{n}& \cdots & {x}_{n}^{n}\end{array}\right)\in {R}^{\left(n+1\right)×\left(n+1\right)}\\ y={\left[{y}_{0},{y}_{1},\cdots ,{y}_{n}\right]}^{\text{T}}\in {R}^{n+1}\end{array}$

$a={V}^{-1}y$

${p}_{n}\left(x\right)={\sum }_{k=0}^{0}{y}_{k}{L}_{n,k}\left(x\right)$

${L}_{n,k}\left(x\right)=\frac{\underset{\begin{array}{l}i=0\\ i\ne k\end{array}}{\overset{n}{\prod }}\left(x-{x}_{i}\right)}{\underset{\begin{array}{l}i=0\\ i\ne k\end{array}}{\overset{n}{\prod }}\left({x}_{k}-{x}_{i}\right)}$

$R\left(x\right)=\frac{1}{1+25{x}^{2}}$

Figure 1. Runge function equidistant node langrage interpolation

$f\left(x\right)=\mathrm{arctan}\left(x\right)$

Figure 2. Anti-triangular function equidistant node Langrage interpolation

$g\left(x\right)=\frac{x}{1+{x}^{4}}$

Figure 3. Fractional function equidistant node Langrage interpolation

3. Runge现象产生的原因

Runge现象是由系统误差造成的。一般的插值余项公式为：

${R}_{n}\left(x\right)=f\left(x\right)-{p}_{n}\left(x\right)=\frac{1}{\left(n+1\right)!}\underset{j=0}{\overset{n}{\prod }}\left(x-{x}_{j}^{\left(n\right)}\right)\text{ }{f}^{\left(n+1\right)}\left(\xi \right)$

$|{R}_{n}\left(x\right)|\le \frac{1}{\left(n+1\right)!}\mathrm{max}\left\{\underset{j=1}{\overset{n}{\prod }}\left(x-{x}_{j}^{\left(n\right)}\right)\right\}\mathrm{max}\left\{{f}^{\left(n+1\right)}\left(x\right)\right\}$

${w}_{n}\left(x\right)=\underset{j=0}{\overset{n}{\prod }}\left(x-{x}_{j}^{\left(n\right)}\right)$

${R}_{n}\left(z\right)=\frac{1}{\left(n+1\right)!}{w}_{n}\left(z\right)\frac{\left(n+1\right)!}{2\text{π}i}\underset{{C}_{T}}{\int }\frac{f\left(\xi \right)}{{w}_{n}\left(\xi \right)\left(\xi -z\right)}\text{d}\xi$

${f}^{\left(n\right)}\left(\xi \right)=\frac{1}{2\text{π}i}\underset{C}{\int }\frac{{w}_{n}\left(z\right)}{{w}_{n}\left(\xi \right)}\frac{f\left(\xi \right)}{\xi -z}\text{d}\xi$

${w}_{n}\left(z\right)={r}^{n}$ 的图像如图4

Figure 4. Function image

$\underset{n\to \infty }{\mathrm{lim}}{R}_{n}\left(z\right)=M\underset{n\to \infty }{\mathrm{lim}}|\frac{{w}_{n}\left(z\right)}{{w}_{n}\left(\xi \right)}|=0$

$\underset{n\to \infty }{\mathrm{lim}}{R}_{n}\left(z\right)=\underset{n\to \infty }{\mathrm{lim}}\frac{1}{z\text{π}i}\left(\underset{{C}_{1}}{\int }\frac{{w}_{n}\left(z\right)}{{w}_{n}\left(\xi \right)}\frac{f\left(\xi \right)}{\xi -z}-\underset{{C}^{*}}{\int }\frac{{w}_{n}\left(z\right)}{{w}_{n}\left(\xi \right)}\frac{f\left(\xi \right)}{\xi -z}\right)=0-\infty =\infty$

4. 避免Runge现象的算法

4.1. 常用算法

$R\left(x\right)=\frac{1}{1+25{x}^{2}}$$f\left(x\right)=\mathrm{arctan}\left(x\right)$$g\left(x\right)=\frac{x}{1+{x}^{4}}$

4.1.1. 采用切比雪夫节点

${x}_{i}=\mathrm{cos}\left(\frac{2i+1}{42}\text{π}\right)\left(i=0,1,2,\cdots ,20\right)$

Figure 5. Runge function Chebyshev node Langrage interpolation

Figure 6. Anti-triangular function Chebyshev node Langrage interpolation

Figure 7. Fractional function Chebyshev node Langrage interpolation

${x}_{k}=\frac{b+a}{2}+\frac{b-a}{2}\mathrm{cos}\left(\frac{\left(2k-1\right)\text{π}}{2\left(n+1\right)}\right),k=1,2,\cdots ,n+1$

4.1.2. 采用分段线性插值

Figure 8. Runge function isometric node piecewise linear interpolation

Figure 9. Inverse trigonometric function equidistant node piecewise linear interpolation

Figure 10. Fractional function equidistant node piecewise linear interpolation

4.1.3. 采用三次样条插值

Figure 11. Runge function equidistant node cubic spline interpolation

Figure 12. Anti-triangular function equidistant node cubic spline interpolation

Figure 13. Fractional function equidistant node cubic spline interpolation

4.2. 结果分析

1) 对于高次插值多项式，若适当选取插值节点能够在一定程度上抑制Runge现象。本文中，各函数采用切比雪夫节点Lagrange插值多项式，由于采用了中间疏两边密的非等距结点，而不是Newton插值多项式所用的等距节点，有效地抑制或消除了本应出现的Runge现象。

2) 降低插值多项式的次数能有效避免Runge现象。本实验中，分段线性插值法(各区间上均为1次)和三次样条插值法(最高次数为3)都取得了较为理想的差值逼近效果，没有出现Runge现象，且在整个插值区间都与原函数的图像吻合的很好。

5. 结论

 [1] 张雨浓, 李名鸣, 陈锦浩, 等. 龙格现象难题破解之系数与阶次双确定方法[J]. 计算机工程与应用, 2013, 49(3): 44-49. [2] 李庆杨, 王能超, 易大义, 编. 数值分析[M]. 第4版. 武汉: 华中科技大学出版社, 2006: 13-24. [3] 张志涌, 等, 编著. MATLAB教程R2012a [M]. 北京: 北京航空航天大学出版社, 2010.