切比雪夫插值介绍与应用
创始人
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著,裴玉茹 马赓宇译, 机械工业出版社

相关内容

热门资讯

安卓能刷索尼系统,索尼系统升级... 你有没有想过,你的安卓手机竟然也能变身成为索尼的忠实粉丝呢?没错,就是那个以高品质影音设备闻名的索尼...
yunos系统能刷安卓系统吗,... 亲爱的读者们,今天我要和你聊聊一个超级实用的话题——YunOS系统能不能刷安卓系统呢?是不是觉得有点...
安卓系统禁用菜单键,全面解析禁... 手机里的菜单键是不是有时候让你头疼?比如,你正全神贯注玩游戏,突然一个不小心按到了菜单键,游戏就中断...
安卓系统是什么钱包,一触即达 你知道吗?现在手机可是我们生活中不可或缺的好伙伴,而在这众多手机应用中,有一种特别的存在,那就是安卓...
安卓系统计步器设置,功能实现与... 你有没有发现,现在的人越来越注重健康生活了?手机上的各种健康应用也跟着火了起来,其中最火的莫过于计步...
安卓系统画画拍照软件,轻松创作 你有没有想过,用手机画画拍照也能变得这么有趣呢?现在,我就要给你揭秘那些在安卓系统上超好用的画画拍照...
安卓设备文件系统,安卓设备文件... 你有没有想过,你的安卓手机里那些密密麻麻的文件夹,它们其实就像是一个个神秘的宝藏库呢?今天,就让我带...
安卓系统9跟10,Androi... 你有没有发现,手机里的安卓系统就像是个不断成长的娃,从安卓9到安卓10,简直就像是从青涩的小伙子变成...
安卓系统怎么选择北斗,如何轻松... 亲爱的手机控们,你们有没有想过,你的安卓手机里藏着一个强大的北斗导航系统呢?没错,就是那个咱们国家自...
车载安卓系统怎么清理,畅享驾驶... 亲爱的车主朋友们,你们的车载安卓系统是不是也像你的手机一样,用久了就变得有点“臃肿”了呢?别急,今天...
在线安卓系统升级,安卓系统在线... 哇哦,你有没有发现,你的手机最近是不是变得有点儿“活泼”了?没错,说的就是你,那个陪伴你日常生活的安...
miui8.5安卓系统,安卓系... 亲爱的手机控们,今天我要和你聊聊一个超级实用的手机系统——MIUI 8.5,它可是基于安卓系统的一款...
纯c 的安卓系统,纯C语言构建... 亲爱的读者们,你是否曾想过,手机里的安卓系统竟然可以只用纯C语言编写?没错,这就是今天我们要探索的神...
mac苹果系统怎么切换安卓系统... 亲爱的果粉们,你是否曾想过,在苹果的优雅世界里,也能体验到安卓的狂野与自由?今天,就让我带你一起探索...
黑莓安卓系统格机,轻松恢复手机... 亲爱的手机控们,你们有没有想过,那些曾经陪伴我们度过无数时光的黑莓手机,竟然也能玩转安卓系统呢?没错...
安卓系统苹果占用大小,安卓与苹... 你有没有发现,现在手机圈里有个大话题:为什么安卓手机的运存和苹果手机差那么多呢?这就像两个好朋友,一...
电脑原生运行安卓系统,开启智能... 你有没有想过,在电脑上也能像玩手机一样,轻松运行安卓系统呢?没错,这就是今天我要跟你分享的神奇技能—...
安卓系统 蓝牙键盘对应,连接、... 你有没有想过,用手机打字的时候,是不是有时候觉得屏幕键盘太小,手指头跳来跳去,就像在键盘上跳迪斯科一...
怎么体验原生安卓系统,探索系统... 亲爱的手机控们,你是否曾对那些简洁流畅、原生味道十足的手机系统心生向往?没错,我说的就是原生安卓系统...
安卓录音系统音频,音频采集、处... 你有没有想过,你的安卓手机里藏着一个小小的录音师呢?没错,就是那个看似普通的录音功能,它可是有着大大...