初识切比雪夫多项式
函数逼近卡壳了。搜了一些讲解和文章，跟着把切比雪夫多项式理一理，整理出文字版。
1、推导前用到的小知识
任意 n\ge1 的整数，有 1+C^2_n+C^4_n+...=2^{n-1}
证明： 二项式展开 (1+x)^n=1+C^1_nx+C^2_nx^2+...C^n_nx^n
令x=1,x=-1,将展开式相加即可
2、一个关于 cosn\theta 展开式的思考
观察如下式子
{cos\theta\\cos2\theta=2cos^2\theta-1\\cos4\theta=2cos^2\theta-1=2(2cos^2\theta-1)-1=8cos^4\theta-8cos^2\theta+1}
提出问题： cosn\theta 展开式是不是一个关于 cos\theta 的多项式呢？如果是，是几次的多项式呢？
下面再放一组展开，方便找规律
cos3\theta=cos\theta cos^2\theta-sin\theta sin2\theta=cos\theta(2cos^2\theta-1)-2cos\theta sin^2\theta=4cos^3\theta-3cos\theta
由此我们猜测， cos n\theta=g(cos\theta) , g(x) 是n次多项式， x^n 的系数是 2^{n-1}
证明： z=cos\theta+isin\theta
z^n=cosn\theta+isinn\theta
实部运算后的结果
{cosn\theta=cos^n\theta-C^2_ncos^{n-2}\theta sin^2\theta+C^4_ncos^{n-4}\theta sin^4\theta...\\\quad\quad\ =cos^n\theta-C^2_ncos^{n-2}\theta(1- cos^2\theta)+C^4_ncos^{n-4}\theta (1- cos^2\theta)^2+...\\\quad\quad\ =g(cos\theta)}
即 cos n\theta=g(cos\theta) , g(x) 是n次多项式
g 的首项系数： 1+C_n^2+C_n^4+...=2^{n-1}
证毕。
3、切比雪夫多项式的表达式
cosn\theta=g_n(cos\theta) 换元，令 x=cos\theta ，得到 g_n(x) 的表达式
g_n(x)=cos(narccosx),\quad n=1,2,3...
这种表达式要写出Chebyshev多项式的通项公式是困难的。
我们考虑递推公式，
g_{n+1}(cos\theta)=cos(n\theta+\theta)=cosn\theta cos\theta-sinn\theta sin\theta
sin 项难以处理，进而考虑
g_{n-1}(cos\theta)=cos(n\theta-\theta)=cosn\theta cos\theta+sinn\theta sin\theta
我们发现： g_{n-1}(cos\theta)+g_{n+1}(cos\theta)=2g_n(cos\theta) cos\theta
由此我们得到Chebyshev多项式的递推公式：
g_{n+1}(x)=2xg_n(x)-g_{n-1}(x)
4、切比雪夫多项式的性质
①零点和极值点
定理（Chebyshev多项式的零点）
T_n(x) 在 [-1,1] 中有 n 个单根，分别为 x_k=cos(\frac{2k-1}{2n}\pi),\ k=1,2,...,n
n确定的情况下，只需令 x=cos\theta,\quad 0\le \theta\le\pi\ \ , -1\le x\le 1
\theta=\pi/2n,3\pi/2n,...(2k-1)\pi/2n,...\pi 时
cosn\theta=0
定理（Chebyshev多项式的极值点）
T_n(x) 在 [-1,1] 中有 n+1 个极值点，为 x_k=cos(\frac{k}{n}\pi),\ k=0,1,...,n ，且对于每个极值点，其极值为 T_n(x_k)=(-1)^k
\theta=0,\pi/n,2\pi/n,...k\pi/n,...\pi 时
cosn\theta=1,-1,1,-1...(-1)^n
所以在 [-1,1] 上，切比雪夫多项式有 n 个单根和 n+1 个极值点
②切比雪夫多项式是无穷范数意义下0的最佳逼近
定理： 任给n次多项式，首项系数为1，那么一定有一个 x_0\in[-1,1] ，使得 |f(x_0)|\ge \frac{1}{2^{n-1}}
证明： 考虑 2^{n-1}f(x)=F(x) ，
反证法，若 x\in[-1,1] , |F(x)|<1
引入n次切比雪夫多项式 g(x)
已知 x=1,cos(\pi/n),cos(2\pi/n),...cos(k\pi/n),...-1 这n+1个点上
|g(x)|=1 ，且正负不断交替
F(x)-g(x) 作为n-1次的多项式（首项减没），在 x_0,x_1,x_2...x_n 这n+1个点上不断变换符号
由介值定理，有 y_1,y_2,...y_n 使得 F(y_k)=g(y_k)
n-1次多项式，有n个零点，说明 F(x)\equiv g(x)
切比雪夫多项式的最大值是1，取得等号，所以与 |F(x)|<1 矛盾！
进一步的，当且仅当 F(x) 为首一切比雪夫多项式时， |F(x)| 的最大值等于 \frac{1}{2^{n-1}} 。
这个定理告诉我们首一Chebyshev不等式具有独特的性质： 在 [-1,1] 上在所有首一多项式中使得绝对值的最大值最小的多项式，即其上 下界（min-max）是所有首一多项式中最紧的。
③带权正交性
取区间 [-1,1] ，权函数 w(x)=\frac{1}{\sqrt{1-x^2}} ，则由Gram-Schimidt方法生成的正交多项式就是Chebyshev多项式。
考虑 i\neq j,\ \int_{-1}^1\frac{T_i(x)T_j(x)}{\sqrt{1-x^2}}dx
令 x=cost,\ t\in [0,\pi]
则原式即为 \int_0^\pi cosit\ cosjt\ dt ，显然为 0 。
而再考虑 \int_{-1}^1\frac{T_i^2(x)}{\sqrt{1-x^2}}dx
同样地进行积分换元操作，令 x=cost,\ t\in [0,\pi]
原式即为 \int_0^\pi cos^2itdt=\frac{\pi}{2} 。
故我们成功地验证了Chebyshev多项式的正交性。
5、切比雪夫多项式的应用
①改进Lagrange插值方法中的结点选取方法。
读者应该还记得取定插值结点 x_0,...,x_n ， n 阶Lagrange插值多项式的余项为 \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)...(x-x_n) 。
我们现在的问题是：在区间 [-1,1] 上有函数 f(x) ，我们要如何取插值结点构造Lagrange插值多项式才能使其最优呢？
我们要最优化Lagrange多项式，一个很自然的想法就是去使得余项最小化。然而余项最小化的计算很复杂。我们退而求其次，不如最小化余项的最大值（即余项的界）。即我们要最小化 max|(x-x_0)(x-x_1)...(x-x_n)|\ \ ,x\in[-1,1]
我们的做法很简单：令 (x-x_0)(x-x_1)...(x-x_n)=\hat{T}_{n+1}(x) 即可。
那么我们选取的插值结点 x_0,...,x_n 就应该是 \hat{T}_{n+1}(x) 的所有零点。
故我们选取 \hat{T}_{n+1}(x) 的所有零点 x_0,...,x_n 作为插值结点得到Lagrange插值多项式 P(x) ，则我们不难得到： max|f(x)-P(x)|\leq \frac{max|f^{(n+1)}(x)|}{2^n(n+1)!},\ \ x\in[-1,1] 。
故由Chebyshev多项式的根进行Lagrange插值的插值结点选取所得到的插值多项式在误差上界的意义下是最优的。
推广：在任意区间 [a,b] 上，我们仅仅需要将其线性变换到 [-1,1] 上选取完结点后再变换回 [a,b] 即可。Chebyshev插值方法事实上对任意区间都能够进行。
此外，Chebyshev插值方法对于改善一般Lagrange插值方法所具有的Runge现象（回忆形如 \frac{1}{1+(kx)^2} 的Cauchy-Lorenz函数。由于其在区间 [-1,1] 端点处高阶导数太大，Lagrange插值方法会造成阶数越高则误差反而越大的现象）在估计区间内有着很好的效果。
②在允许的误差范围内尽量减少多项式估计的次数，使得新估计与原估计相差尽可能小 。
问题是：现在有 P_n(x),degP_n=n ，我们希望找到 P_{n-1},degP_{n-1}=n-1 ，使得 max|P_n(x)-P_{n-1}(x)|,\ x\in[-1,1] 尽可能地小。
我们假设 P_n(x)=a_nx^n+...+a_0 。
同样地，我们只需要令 \frac{P_n(x)-P_{n-1}(x)}{a_n}=\hat{T}_n(x) 即可利用到Chebyshev多项式min-max的性质，最小化误差上界。
那么 P_{n-1}=P_n-a_n\hat{T}_n 即为所求的低次多项式估计，且在误差上界的意义下是最优的。
而且， max|P_n(x)-P_{n-1}(x)|=\frac{|a_n|}{2^{n-1}},\ x\in[-1,1] 。
参考文章及资料：
1、课本和老师滴课件
3、 最美数学—切比雪夫多项式