切比雪夫插值介绍与应用
创始人
2024-06-01 04:12:25
0

  在文章拉格朗日插值多项式的原理介绍及其应用中,笔者介绍了拉格朗日插值多项式及其应用,在文章插值多项式的龙格现象的介绍与模拟,我们发现插值多项式会在端点附近发生较大的扭动,即龙格现象。而切比雪夫插值是一种特定最优的点间距选取方式,其可以尽量减少插值误差。

插值误差

  在数值分析中,有如下定理:
  (定理1 插值误差公式)假设P(x)是n-1或者更低阶的插值多项式,其拟合n个点(x1,y1),⋯,(xn,yn)(x_{1}, y_{1}), \cdots, (x_{n}, y_{n})(x1​,y1​),⋯,(xn​,yn​),则插值误差是:

f(x)−P(x)=1n!(x−x1)(x−x2)⋯(x−xn)f(n)(c)f(x)-P(x)=\frac{1}{n!}(x-x_{1})(x-x_{2})\cdots(x-x_{n})f^{(n)}(c)f(x)−P(x)=n!1​(x−x1​)(x−x2​)⋯(x−xn​)f(n)(c)

其中c在最小和最大的n+1个数字x,x1,⋯,xnx,x_{1},\cdots,x_{n}x,x1​,⋯,xn​之间。

  从中我们可以发现,如果n确定,x1,⋯,xnx_{1},\cdots,x_{n}x1​,⋯,xn​是自由选取的n个点,那么插值误差的大小将取决于∣(x−x1)(x−x2)⋯(x−xn)∣|(x-x_{1})(x-x_{2})\cdots(x-x_{n})|∣(x−x1​)(x−x2​)⋯(x−xn​)∣和f(n)(c)f^{(n)}(c)f(n)(c),而f(n)(c)f^{(n)}(c)f(n)(c)视函数f(x)而定,因此我们重点讨论∣(x−x1)(x−x2)⋯(x−xn)∣|(x-x_{1})(x-x_{2})\cdots(x-x_{n})|∣(x−x1​)(x−x2​)⋯(x−xn​)∣,我们将x的取值范围限定在区间[-1, 1],有如下定理:

  (定理2)选择实数−1≤x1,⋯,xn≤1-1\leq x_{1}, \cdots, x_{n}\leq 1−1≤x1​,⋯,xn​≤1,使得max⁡−1≤x≤1∣(x−x1)⋯(x−xn)∣\max\limits_{-1\leq x \leq 1}|(x-x_{1}) \cdots (x-x_{n})|−1≤x≤1max​∣(x−x1​)⋯(x−xn​)∣尽可能小,则xi=cos⁡(2i−1)π2n,i=1,⋯,nx_{i}=\cos{\frac{(2i-1)\pi}{2n}}, i=1, \cdots, nxi​=cos2n(2i−1)π​,i=1,⋯,n,对应的最小值是1/2n−11/2^{n-1}1/2n−1,实际上,通过(x−x1)⋯(x−xn)=12n−1Tn(x)(x-x_{1}) \cdots (x-x_{n})=\frac{1}{2^{n-1}}T_{n}(x)(x−x1​)⋯(x−xn​)=2n−11​Tn​(x)可以得到极小值,其中Tn(x)T_{n}(x)Tn​(x)表示n阶切比雪夫多项式。

  我们将上述定理中的xi=cos⁡(2i−1)π2nx_{i}=\cos{\frac{(2i-1)\pi}{2n}}xi​=cos2n(2i−1)π​记为xi=cos⁡oddπ2nx_{i}=\cos{\frac{odd\pi}{2n}}xi​=cos2noddπ​,其中odd表示1到2n之间的奇数,将这样的根记为切比雪夫根。我们将使用切比雪夫根作为基点的插值多项式叫作切比雪夫插值多项式

切比雪夫多项式

  定义n阶切比雪夫多项式 Tn(x)=cos⁡(narccos⁡x)T_{n}(x)=\cos{(n \arccos x)}Tn​(x)=cos(narccosx),其中−1≤x≤1-1\leq x \leq 1−1≤x≤1。对于切比雪夫多项式,有如下归纳公式:

Tn+1(x)=2xTn(x)−Tn−1(x)T_{n+1}(x)=2xT_{n}(x)-T_{n-1}(x)Tn+1​(x)=2xTn​(x)−Tn−1​(x)

由此,根据数学归纳法,不难证明,Tn(x)T_{n}(x)Tn​(x)是关于x的多项式,事实上,前几个切比雪夫多项式如下:

T0(x)=1T1(x)=xT2(x)=2x2−1T3(x)=4x3−3xT_{0}(x)=1\\ T_{1}(x)=x\\ T_{2}(x)=2x^{2}-1\\ T_{3}(x)=4x^{3}-3xT0​(x)=1T1​(x)=xT2​(x)=2x2−1T3​(x)=4x3−3x

根据切比雪夫多项式的一些基本性质,我们可以证明定理2,但这里省略,如有兴趣,可以查阅文章最后的参考文献。
  在定理2中,当x的取值区间从[-1, 1]变成任意闭区间[a, b]时,我们只需对区间做伸缩变换,则有:

  (定理3 切比雪夫插值节点)在区间[a, b], x=a+b2+b−a2cos⁡(2i−1)π2n,i=1,2,⋯,nx=\frac{a+b}{2}+\frac{b-a}{2}\cos{\frac{(2i-1)\pi}{2n}}, i=1, 2, \cdots, nx=2a+b​+2b−a​cos2n(2i−1)π​,i=1,2,⋯,n,不等式∣(x−x1)⋯(x−xn)∣≤(b−a2)n2n−1|(x-x_{1})\cdots (x-x_{n})|\leq \frac{(\frac{b-a}{2})^{n}}{2^{n-1}}∣(x−x1​)⋯(x−xn​)∣≤2n−1(2b−a​)n​在区间[a, b]上恒成立。

应用

应用1 观察切比雪夫点的插值多项式的拟合结果

  我们对函数f(x)=11+12x2f(x)=\frac{1}{1+12x^{2}}f(x)=1+12x21​在区间[-1, 1]上,我们选取n个切比雪夫根及其对应的函数值,对这些样本点进行多项式插值。
  Python实现程序如下:

# -*- coding: utf-8 -*-
# @Time : 2023/3/8 23:40
# @Author : Jclian91
# @File : chebyshev_ploy.py
# @Place : Xuhui, Shanghai
import math
import matplotlib.pyplot as plt# sample function
# 函数f(x)=1/(1+12*x**2)
def sample_func(x):return 1 / (1 + 12 * x ** 2)# get chebyshev points from sample function with interval [-1, 1]
def get_chebyshev_points(n):# n: number of chebyshev pointsstep = 2 / (n-1)x_values = [math.cos((2*i+1)*math.pi/(2*n)) for i in range(n)]y_values = [sample_func(x) for x in x_values]return x_values, y_values# get basic lagrange polynomial unit
def get_lagrange_polynomial_unit(x_values, k, x):# x_values: values of x in list x_values# k: kth lagrange polynomial unit# x: variable in kth lagrange polynomial unitpoly_unit = 1for i in range(len(x_values)):if i != k:poly_unit *= (x-x_values[i])/(x_values[k]-x_values[i])return poly_unit# get lagrange polynomial
def get_lagrange_polynomial(x_values, y_values, x):poly = 0for i, y in enumerate(y_values):poly += y * get_lagrange_polynomial_unit(x_values, i, x)return poly# plot curves with matplotlib
def plot_function(n):# plot lagrange polynomial with n sample points from sample functionsample_x_values, sample_y_values = get_chebyshev_points(n)sample_points_number = 500x_list = [-1 + i * 2 / (sample_points_number-1) for i in range(sample_points_number)]original_y_list = [sample_func(x) for x in x_list]y_list = [get_lagrange_polynomial(sample_x_values, sample_y_values, x)for x in x_list]plt.plot(x_list, original_y_list, label='f(x)=1/(1+12*x**2)')plt.plot(x_list, y_list, label='lagrange polynomial')plt.title(f'Runge phenomenon with {n} chebyshev points in function f(x)=1/(1+12*x**2)')plt.legend()plt.show()# plt.savefig(f"{n}_basic_points.png")if __name__ == '__main__':n_points = 10plot_function(n_points)

当n=5时,图像如下:

当n=10时,图像如下:

当n=15时,图像如下:

当n=25时,图像如下:

从中我们可以发现,当n越大,插值多项式越逼近原函数,拟合误差越小,并且我们避免了插值多项式的龙格现象,这是因为我们选取的区间点是切比雪夫点。

应用2 数值逼近

  设计程序,使得在区间[0,π2][0, \frac{\pi}{2}][0,2π​]上sin(x)sin(x)sin(x)的数值精确到小数点后10位。
  在区间[0,π2][0, \frac{\pi}{2}][0,2π​]上,取n个切比雪夫根,对于插值多项式Pn−1(x)P_{n-1}(x)Pn−1​(x)在区间[0,π2][0, \frac{\pi}{2}][0,2π​]上的最大插值误差有:

∣sin⁡x−Pn−1(x)∣=1n!∣(x−x1)⋯(x−xn))∣∣f(n)(c)∣≤(π2−02)nn!2n−1⋅1|\sin{x}-P_{n-1}(x)|=\frac{1}{n!}|(x-x_{1})\cdots(x-x_{n}))||f^{(n)}(c)|\leq \frac{(\frac{\frac{\pi}{2}-0}{2})^{n}}{n!2^{n-1}}\cdot 1∣sinx−Pn−1​(x)∣=n!1​∣(x−x1​)⋯(x−xn​))∣∣f(n)(c)∣≤n!2n−1(22π​−0​)n​⋅1

经计算,当n=10时,误差界满足要求,可以精确到小数点后10位,此时切比雪夫根应为π4+π4cos⁡(oddπ/20)\frac{\pi}{4}+\frac{\pi}{4}\cos{(odd\pi/20)}4π​+4π​cos(oddπ/20).
  Python实现程序如下:

# -*- coding: utf-8 -*-
# @Time : 2023/3/9 10:37
# @Author : Jclian91
# @File : similar_to_sine_function.py
# @Place : Xuhui, Shanghai
# 利用切比雪夫多项式逼近sin(x)函数,区间为[0, pi/2]
import mathPI = math.pi    # pi in math# sample function
# 函数f(x)=sin(x)
def sample_func(x):return math.sin(x)# get chebyshev points from sample function
def get_chebyshev_points(n):# n: number of chebyshev pointsx_values = [PI/4 + PI/4 * math.cos((2*i+1)*PI/(2*n)) for i in range(n)]y_values = [sample_func(x) for x in x_values]return x_values, y_values# get basic lagrange polynomial unit
def get_lagrange_polynomial_unit(x_values, k, x):# x_values: values of x in list x_values# k: kth lagrange polynomial unit# x: variable in kth lagrange polynomial unitpoly_unit = 1for i in range(len(x_values)):if i != k:poly_unit *= (x-x_values[i])/(x_values[k]-x_values[i])return poly_unit# get lagrange polynomial
def get_lagrange_polynomial(x_values, y_values, x):poly = 0for i, y in enumerate(y_values):poly += y * get_lagrange_polynomial_unit(x_values, i, x)return poly# get similar value to sin(x) function
def get_similar_value(x):# x: real number in interval [0, pi/2]true_value = sample_func(x)n = 10      # chebyshev basic points number, with error < 10^-10x_list, y_list = get_chebyshev_points(n)similar_value = get_lagrange_polynomial(x_list, y_list, x)error = true_value - similar_valuereturn f"{true_value}\t{similar_value}\t{error}"if __name__ == '__main__':for x0 in [0, 0.25, 0.5, 0.75, 1, 1.25, 1.5]:d = get_similar_value(x0)print(d)

输出结果如下:

x值sinx值逼近值误差
00.03.104458877467575e-11-3.104458877467575e-11
0.250.247403959254522940.247403959243490761.1032175173397718e-11
0.50.4794255386042030.4794255386316042-2.7401192426168564e-11
0.750.68163876002333410.6816387599931943.0140112627918825e-11
10.84147098480789650.8414709848397693-3.1872837702451307e-11
1.250.94898461935558620.94898461932066463.492162115037445e-11
1.50.99749498660405440.99749498658907021.4984236074155888e-11

参考文献

  1. 数值分析(原书第2版) (美)Timothy Sauer著,裴玉茹 马赓宇译, 机械工业出版社

相关内容

热门资讯

安卓系统查询充电次数,轻松掌握... 手机电池的充电次数,这个数字是不是让你好奇又有点小紧张呢?想知道自己的手机电池到底充过多少次电,其实...
蝴蝶影app安卓系统,畅享高清... 你有没有听说过那个超火的蝴蝶影app?最近,这款应用在安卓系统用户中可是掀起了一股热潮呢!它不仅功能...
鸿蒙系统对标安卓,构建全场景分... 你知道吗?在科技圈里,最近可是有个大新闻呢!那就是华为的鸿蒙系统,它可是要和安卓系统一较高下了。想象...
安装安卓软件的系统,POS机安... 你有没有想过,为什么你的手机里那么多安卓软件,而你的电脑却只能用那些固定的程序呢?其实,这背后有一个...
鸿蒙系统会取代安卓,引领未来移... 你知道吗?最近手机圈里可是炸开了锅,因为鸿蒙系统这个“小萌新”竟然要挑战安卓这个“老大哥”的地位啦!...
橘子系统和安卓系统关系,探索安... 你知道吗?在手机的世界里,有两个超级明星系统,它们就像是一对好搭档,一个叫橘子系统,一个叫安卓系统。...
越狱安卓版本升级系统,苹果越狱... 亲爱的手机控们,你们有没有想过,你的安卓手机是不是已经有点“老态龙钟”了呢?别急,今天就来给你支个招...
me74 安卓系统,功能与特色... 你有没有发现,自从入手了那款me74安卓手机,生活仿佛开启了一扇新的大门?这款手机不仅外观时尚,功能...
安卓系统安装歌曲软件,畅享海量... 手机里歌曲太多,不知道怎么管理?别急,今天就来给你安利几款安卓系统上安装歌曲的软件,让你的音乐库井井...
安卓系统抄袭了苹果,苹果创新之... 你知道吗?最近手机圈里可是热闹非凡呢!安卓系统竟然被说成是抄袭了苹果!这可真是让人大跌眼镜啊。咱们一...
我们的安卓系统英文,Explo... 探索安卓世界的奥秘:我们的安卓系统英文之旅亲爱的读者们,你是否曾在手机屏幕上滑动,解锁那充满活力的安...
电脑安装多个安卓系统,轻松体验... 你有没有想过,你的电脑也能像手机一样,装上好几个安卓系统呢?没错,就是那种可以一边玩《王者荣耀》,一...
安卓官改11系统,深度解析官方... 你知道吗?最近科技圈可是炸开了锅,因为安卓官改11系统终于要和大家见面啦!这可不是一个小小的更新,而...
3607x安卓系统,深度解析与... 你有没有想过,你的电脑也能装上安卓系统呢?没错,就是那个让你在手机上畅游的安卓系统,现在它也能在你的...
新机安卓系统怎么升级,畅享智能... 亲爱的手机控们,你是否也和我一样,对手机的新鲜感总是那么强烈?这不,最近又听说安卓系统升级了,是不是...
微软系统能刷安卓系统吗,共创多... 亲爱的读者们,你是否曾想过,有一天你的电脑上不仅能运行Windows应用,还能轻松刷上安卓系统?没错...
微信8.0 安卓系统,畅享社交... 亲爱的手机控们,你们有没有发现,最近微信又来搞事情啦?没错,就是那个我们每天离不开的微信,它又升级啦...
安卓怎么用系统代理,利用安卓系... 亲爱的手机控们,你是否曾想过,你的安卓手机其实是个隐藏的特工,可以穿梭在网络的海洋中,自由自在地探索...
安卓系统用日语说,「Andro... 你有没有想过,用安卓手机也能轻松说日语呢?没错,就是那种听起来就让人心情愉悦的日语!今天,就让我带你...
鸿蒙系统下载安卓版,畅享智能生... 你知道吗?最近手机圈里可是炸开了锅,华为的鸿蒙系统安卓版终于来了!这可不是什么小道消息,而是实实在在...