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

相关内容

热门资讯

小米手机安卓系统rom,功能与... 你有没有发现,最近小米手机的热度又上来了?没错,就是那个以性价比著称的小米。今天,咱们就来聊聊小米手...
安卓8.0系统自动重启,安卓8... 最近你的安卓手机是不是也遇到了一个让人头疼的问题?没错,就是那个让人抓狂的自动重启!是不是每次正在关...
安卓导航进入系统设置,解锁个性... 亲爱的手机控们,你是否曾在某个午后,手捧着你的安卓手机,突然想探索一下它的深处,看看那些隐藏在系统设...
安卓系统爱疯7,兼容与创新的双... 你知道吗?在科技圈里,最近可是有个大热门呢!那就是安卓系统和爱疯7的较量。这两大操作系统,一个自由奔...
安卓系统第9代,新一代智能系统... 你知道吗?最近科技圈可是炸开了锅,安卓系统第9代横空出世,简直让人眼前一亮!这款全新的操作系统,不仅...
安卓系统屏幕复制软件,轻松实现... 你是不是也和我一样,有时候想分享手机屏幕上的精彩瞬间,但又不知道怎么操作呢?别急,今天就来给你揭秘安...
流量充值软件安卓系统,畅享无忧... 你有没有想过,手机里的流量用完了,却不想再办新卡或者去营业厅充值?现在,有了这些神奇的流量充值软件,...
soc系统和安卓系统的区别,架... 你有没有想过,为什么你的手机里装的是安卓系统而不是soc系统呢?这两种系统各有各的特色,今天就来给你...
宝马连不上安卓系统蓝牙,宝马车... 最近有个事儿让不少宝马车主头疼不已,那就是他们的爱车竟然连不上安卓系统的蓝牙!这可真是让人摸不着头脑...
安卓系统安装gps模块,安卓系... 你有没有想过,为什么你的安卓手机在户外旅行时总是能精准地告诉你位置呢?这背后可大有学问呢!今天,就让...
安卓手机如何修复系统,安卓手机... 手机突然卡顿,系统崩溃,是不是让你头疼不已?别担心,今天就来教你几招,让你的安卓手机焕然一新!一、重...
系统更新华为安卓,引领智能科技... 亲爱的手机控们,是不是最近你的华为手机突然变得有点儿“慢吞吞”了呢?别急,这可不是你的错觉哦!华为安...
安卓系统拦截怎么解除,轻松恢复... 你是不是也遇到了安卓系统拦截的问题,心里直痒痒想要解除它呢?别急,今天就来给你详细说说怎么搞定这个小...
老式平板装安卓系统,重温经典体... 你有没有想过,那些曾经陪伴我们度过无数时光的老式平板电脑,竟然还能装上安卓系统呢?这可不是什么天方夜...
系统如何与安卓互通,技术融合与... 你有没有想过,你的手机系统竟然能和安卓系统这么默契地互通有无?这就像是一场跨越科技界的友谊赛,让我们...
安卓系统 扫码枪,安卓系统下扫... 你有没有想过,在繁忙的超市收银台,那些快速流畅的扫码操作,背后其实隐藏着一个小小的英雄——安卓系统扫...
平板插卡推荐安卓系统,安卓系统... 你有没有想过,你的平板电脑是不是也能像智能手机一样,随时随地扩充存储空间呢?没错,这就是今天我要跟你...
安卓系统固件安装失败,原因排查... 最近是不是你也遇到了安卓系统固件安装失败的问题?别急,让我来给你详细说说这个让人头疼的小麻烦,让你一...
ios系统和安卓区别,系统差异... 你有没有发现,现在手机市场上,iOS系统和安卓系统就像是一对双胞胎,长得差不多,但性格却截然不同。今...
安卓系统2.3优酷,优酷的崛起... 你有没有发现,安卓系统2.3时代的那股怀旧风?那时候,优酷可是视频界的巨头,多少人都是看着优酷长大的...