在數值分析中，插值方法是基礎且重要的，本文將介紹Lagrange插值公式與Newton插值公式，此外，針對Runge現象，本文給出了稍稍詳細的討論，
一、Lagrange插值公式
假設函式 \(y=f(x)\) 在取定的\(n+1\)個互異的基點 \(x_0,x_1,\cdots,x_n\) 處的值已知分別為 \(y_0=f(x_0),y_1=f(x_1),\cdots,y_n=f(x_n)\)，現在要尋找多項式 \(p(x)\) 使得 $$p(x_k)=f(x_k), \quad k=0,1,\cdots,n$$
記
令
\[p_n(x)=\sum_{i=0}^nf(x_i)l_i(x) \]這就是滿足條件的多項式，
例 利用等距基點計算函式 \(f(x)=\frac{\sin{e^{-x^2}}}{\sqrt{x+2}}\) 在區間 \([-1,1]\) 上的值，
import math
def fun1(t):
return math.sin(math.exp(-t**2))/math.sqrt(t+2)
def LagIn(X,P,x):
Pol=0
length=len(P)
count1=0
while count1 <= length-1:
lpoly=P[count1]
count2=0
while count2 <= length-1:
if count1 != count2:
lpoly=lpoly*(x-X[count2])/(X[count1]-X[count2])
else:
lpoly=lpoly
count2=count2+1
Pol=Pol+lpoly
count1=count1+1
return Pol
n=int(input("輸入基點個數："))
A=[]
K=[]
Result=[]
count=0
while count <= n:
A.append(fun1(-1+count*2/n))
K.append(-1+count*2/n)
count=count+1
count=0
print(LagIn(K,A,0.1))
考慮誤差問題，記
\[r_n(x)=f(x)-p_n(x) \]若\(f(x)\)在包含\(n+1\)個插值基點\(x_0,x_1,\cdots,x_n\)的區間\([a,b]\)上有\(n\)階連續導數，且在\((a,b)\)記憶體在\(n+1\)階有界導數，那么對\([a,b]\)上的每一點\(x\)必存在一點\(\eta \in (a,b)\)使得
\[r_n(x)=\frac{f^{(n+1)}(\eta)}{(n+1)!}\prod_{i=0}^n(x-x_i) \]二、均差與Newton插值公式
仍然使用上一節的記號，考慮形如
\[N_n(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_n(x-x_0)(x-x_1)\cdots(x-x_{n-1}) \]的多項式，滿足條件
\[N_n(x_i)=f(x_i),\quad i=0,1,\cdots,n \]由線性代數的知識容易知道，\(a_0,a_1,\cdots,a_n\)是唯一確定的，考慮這種形式的多項式的好處是，當需要增加基點時，可以減少計算量，
下面引入均差的概念來確定該插值多項式的系數，
\(f(x)\)關于基點\(x_0,x_1,\cdots,x_n\)的n階均差定義為
規定
\[f[x_i]=f(x_i) \]是\(f(x)\)關于基點\(x_i\)的零階均差，
利用數學歸納法可以證明：n階均差可以寫成
\[f[x_0,x_1,\cdots,x_n]=\sum_{i=0}^n\frac{f(x_i)}{\prod_{j=0,j\neq i}^n(x_i-x_j)} \]與利用Lagrange插值法得到的多項式比較可知，\(N_n(x)\)的系數
\[a_k=f[x_0,x_1,\cdots,x_k],\quad k=0,1,\cdots,n \]三、Runge現象
考慮函式
\[f(x)=\frac{1}{1+x^2},\quad x\in [-5,5] \]對該函式在等距基點上插值，分別取插值基點個數為5，10，15，20，30，作出誤差影像，如下所示：
import math
import matplotlib.pyplot as mpl
def fun1(t):
return (1+t**2)**(-1)
def LagIn(X,P,x):
Pol=0
length=len(P)
count1=0
while count1 <= length-1:
lpoly=P[count1]
count2=0
while count2 <= length-1:
if count1 != count2:
lpoly=lpoly*(x-X[count2])/(X[count1]-X[count2])
else:
lpoly=lpoly
count2=count2+1
Pol=Pol+lpoly
count1=count1+1
return Pol
n=int(input("輸入基點個數："))
A=[]
K=[]
Result=[]
count=0
while count <= n:
A.append(fun1(-5+count*10/n))
K.append(-5+count*10/n)
count=count+1
count=0
B=[]
F=[]
while count <= 10000:
B.append(-5.01+count*10.02/10000)
F.append((fun1(B[count])-LagIn(K,A,B[count])))
count=count+1
mpl.plot(B,F)
mpl.show()
可以看到，插值多項式在端點附近有較大的誤差，事實上可以證明
\[\lim_{n \to \infty}\max_{x \in [-5,5]}|f(x)-p_n(x)|= \infty \]這就是所謂的Runge現象，下面將進行仔細討論，
在區間\([a,b]\)上，記插值基點為\(\{x_j^{(n)}\},\quad j=0,1,\cdots,n\)，插值多項式為\(p_n(x)\)，首先估計誤差項\(f(x)-p_n(x)\)，
由Newton插值法，在區間\([a,b]\)上取與插值基點相異的一個基點 \(x=t\)，得到
由于\(p_{n+1}(t)=f(t)\)，因此
\[f(x)-p_n(x)=f[x_0,x_1,\cdots,x_n,x]\prod_{j=0}^n(x-x_{j}^{(n)}) \]下面記
\[\omega_n(x)=\prod_{j=0}^n(x-x_{j}^{(n)}) \]下面在復平面上考慮問題，插值基點視作實軸上的點，仍保留原來的記號，
由留數定理
\[f[x_0,x_1,\cdots,x_n]=\sum_{i=0}^n\frac{f(x_i)}{\prod_{j=0,j\neq i}^n(x_i-x_j)}=\sum_{i=0}^n\mathrm{Res}(\mathrm{g},x_i)=\frac{1}{2\pi i}\int_Cg(z)\mathrm{d}z \]其中
\[g(z)=\frac{f(z)}{\prod_{i=0}^n(z-x_i)} \]C是曲線，使得插值基點在它內部，\(f\)在其內部決議，類似可以求得\(f[z,x_0,x_1,\cdots,x_n]\)的運算式，從而得到
\[f(z)-p_n(z)=\frac{1}{2\pi i}\int_C\frac{\omega_n(z)}{\omega_n(\eta)}\frac{f(\eta)}{\eta-z}\mathrm{d}\eta \]為了進一步估計，需要先證明以下引理：
引理 假設\(\{x_j^{(n)}\}\)是區間\([a,b]\)上的等距基點，定義
\[\sigma_n(z)=|\omega_n(z)|^{\frac{1}{n+1}} \]則
\[\lim_{n\to \infty}\sigma_n(z)=\sigma(z)=\mathrm{exp}\{\frac{1}{b-a}\int_a^b \mathrm{ln}|z-s|\mathrm{d}s\} \]證明：
\[\mathrm{ln}\sigma_n(z)=\frac{1}{n+1}\sum_{i=0}^n \mathrm{ln}|z-a-\frac{b-a}{n}i| \]由黎曼積分的定義知
\[\lim_{n\to \infty}\mathrm{ln}\sigma_n(z)=\frac{1}{b-a}\int_a^b\mathrm{ln}|z-s|\mathrm{d}s \]引理成立，
考慮曲線
\[C(\rho)=\{z \in \mathbb{C}|\sigma(z)=\rho \} \]命題 \(\{x_j^{(n)}\}\)是包含在曲線\(C(\rho)\)中的等距插值基點，若\(f\)在\(C(\rho)\)中決議，則\(p_n\)在\(C(\rho'),\rho' < \rho\)上一致收斂于\(f\)，
證明：假設\(z\)在曲線\(C(\rho')\)上，顯然\(C(\rho)\)和\(C(\rho')\)是不交的，因此有以下估計：
由于\(|f(\eta)|\)和\(|\eta-z|\)在\(C(\rho)\)上分別由上界和下界，因此
\[|f(z)-p_n(z)|\leq A \max_{\eta \in C(\rho)}|\frac{\omega_n(z)}{\omega_n(\eta)}| \]考慮引理中的結果，由\(\lim_{n \to \infty}\sigma_n(z)=\rho'\)及\(\lim_{n \to \infty}\sigma_n(\eta)=\rho\)，對\(\epsilon < \frac{|p-p'|}{3}\)能夠取到\(n\)使得
\[|\frac{\omega_n(z)}{\omega_n(\eta)}|^\frac{1}{n+1}=\frac{\sigma_n(z)}{\sigma_n(\eta)}\leq \frac{\rho'+\epsilon}{\rho-\epsilon}<1 \]從而可以證明一致收斂，
考慮\(f\)在\(C(\rho)\)中并不決議的情況，僅僅討論一種特殊情況：若只有一個一階極點\(z^*\)，此時
\[f(z)-p_n(z)=\frac{1}{2\pi i}\int_{C(\rho)}\frac{\omega_n(z)}{\omega_n(\eta)}\frac{f(\eta)}{\eta-z}\mathrm{d}\eta+\frac{1}{2\pi i}\int_{C^*}\frac{\omega_n(z)}{\omega_n(\eta)}\frac{f(\eta)}{\eta-z}\mathrm{d}\eta \]其中\(C^*=C(\rho^*)\)是圍繞極點的一條路徑，由上面的討論知，第一項趨于零，利用留數定理，第二項可以寫成
\[B\frac{\omega_n(z)}{\omega_n(z^*)} \]其中
\[B=\lim_{\eta \to z^*}\frac{f(\eta)}{(\eta-z^*)(\eta-z)} \]是有界的，
\[|\frac{\omega_n(z)}{\omega_n(z^*)}|^\frac{1}{n+1}=\frac{\sigma_n(z)}{\sigma_n(z^*)}\geq\frac{\rho'-\epsilon}{\rho^*+\epsilon}>1 \]此時\(f(z)-p_n(z)\)并不收斂，
上面的討論并沒有給出Runge現象的充要條件，當插值區間過大時，可能會出現Runge現象；縮小插值區間，可以避免Runge現象，因此可以考慮分段插值的方法，此外也可以采用Chebyshev基點進行插值，這就不在本文的討論范圍內了，
參考
[1]Epperson J. On the Runge Example[J]. The American Mathematical Monthly, 1987, 94(4):329-341.
[2]林成森. 數值計算方法[M]. 科學出版社, 2005.
[3]作者本人的實驗報告.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502011.html
標籤：其他