专题：Chebyshev多项式
我们先给出两类Chebyshev多项式的定义：
第一类Chebyshev多项式：由递推式 T_{0}\left( x \right)=1, T_{1}\left( x \right)=x,T_{n +1}\left( x \right)=2x T_{n }\left( x \right)-T_{n -1}\left( x \right) 所确立的一系列多项式称为第一类Chebyshev多项式.
第二类Chebyshev多项式：由递推式 U_{0}\left( x \right)=1, U_{1}\left( x \right)=2x,U_{n +1}\left( x \right)=2x U_{n }\left( x \right)-U_{n -1}\left( x \right) 所确立的一系列多项式称为第二类Chebyshev多项式.
在本专题中，我们主要研究第一类Chebyshev多项式.
一个比较简陋的目录：
- 第一类Chebyshev多项式的相关简单性质
- Chebyshev逼近理论（简）
- 第一类Chebyshev多项式的相关性质（比1深一点）及常用引理
- 练习
第一类Chebyshev多项式的相关简单性质
这里我们来研究第一类Chebyshev多项式的性质.
注意第一类Chebyshev多项式的三角形式：
T_n(x)=\cos(n\arccos x),-1\leq x\leq 1
由此我们知道这类多项式满足的重要性质（其实也可以作为定义）：
性质1： T_n(\cos\theta)=\cos{n\theta}
由上面的递推式归纳我们可以得出：
性质2：Chebyshev多项式 T_n(x) 是n次代数多项式.
性质3：Chebyshev多项式 T_n(x) 的最高次幂项 x^n 的系数为 2^{n-1} .
归纳易证，这里给出一种非归纳的证明.
T_n(x)=\cos n\theta=\frac{e^{in\theta}+e^{-in\theta}}{2}=\frac{(\cos\theta+i\sin\theta)^n+(\cos\theta-i\sin\theta)^n}{2}=\frac{(x+\sqrt{x^2-1})^n+(x-\sqrt{x^2-1})^n}{2}
记 a_n 为 x^n 的系数，有：
a_n=\lim_{x \rightarrow \infty}{\frac{T_n(x)}{x^n}}=\lim_{x \rightarrow \infty}\frac{(1+\sqrt{1-\frac{1}{x^2}})^n+(1+\sqrt{1-\frac{1}{x^2}})^n}{2}=2^{n-1}
证毕.
性质4： |x|\leq1 时有 |T_n(x)|\leq 1 (由性质1平凡)
下面的性质给出了这类多项式的根的分布.
性质5：
T_n(x)
在
\left[ -1,1 \right]
中有n个不同的实根
x_k=\cos\frac{(2k-1)\pi}{2n},k=1,2,3,...,n
其实由性质1也是平凡的.
性质6： T_n(x) 在 \left[ -1,1 \right] 中有n+1个点 x_k^{*}=\cos\frac{k\pi}{n},k=0,1,2,...,n ,轮流取最大值1和最小值-1.
其实由性质1还是平凡的.
性质7：当n为奇数时， T_n(x) 是奇函数；当n为偶数时， T_n(x) 是偶函数.
仍然由性质1平凡.
Chebyshev逼近理论（简）
下面来阐述一些Chebyshev逼近的相关理论：
在这之前，我们先对一些基本的概念作一定了解，这些概念包括： 线性空间的定义，线性无关组和线性相关组的定义，线性空间模的定义, C[a,b] 上的模运算定义,交错点组的定义,最佳一致逼近的定义，标记：C[a,b]以及 Span\{x_1,x_2,...,x_n\}
对这些概念有基本了解的可以继续往下读，不了解这些基本概念则可先转到文章 马康哲：对Chebyshev多项式专题的几个概念的解释 对这些概念进行一定了解再往下读.
下面是正文：
我们介绍一个关于Chebyshev逼近的一个重要定理：
定理1：在 -1\leq x\leq 1 上 ，在首项系数为1的一切n次多项式 P_n(x) 中， w_n(x)=2^{1-n}T_n(x) 对0的偏差最小，即：
\max_{-1\leq x\leq1}|w_n(x)-0|\leq\max_{-1\leq x\leq1}|P_n(x)-0|
证明：反证法.
若存在另一n次首一多项式
P_n(x)
使得
\max_{-1\leq x\leq1}|P_n(x)-0|＜\max_{-1\leq x\leq1}|w_n(x)-0|=2^{1-n}
由于
x_k^{*}=\cos\frac{k\pi}{n},k=0,1,2,...,n
是
T_n(x)
的交错点组，故
w_n(x)
在
x_k^{*}
处轮流取
(-1)^k2^{1-n}
,根据上述不等式，易知：
P_n(x_i^*)-w_n(x_i^*)＜0,i=2m,m\in Z
P_n(x_i^*)-w_n(x_i^*)＞0,i=2m+1,m\in Z
因此 P_n(x)-w_n(x) 在 x_k^{*}=\cos\frac{k\pi}{n},k=0,1,2,...,n 轮流取正负号.
由零点存在性定理知： P_n(x)-w_n(x) 至少有n个零点.
但由于 P_n(x),w_n(x) 均为n次首一多项式，故： P_n(x)-w_n(x) 为次数不超过n-1的多项式，由多项式恒等定理， P_n(x)-w_n(x)\equiv0 ，即 P_n(x)\equiv w_n(x) 与假设矛盾，从而定理1成立，证毕.
注： 1.由定理1推知所有n次首一多项式在区间[-1,1]的最大值满足： \max_{-1\leq x\leq 1}P_n(x)\geq 2^{1-n}
2.注意定理1证明的手法，在后面的定理证明中我们经常会使用这种手法.
定理2：如果 f\in C[a,b] ,则集 \mathscr{P}_n 中存在一个元素是 f 的最佳Chebyshev逼近元素.
证略.
定理3：假设 f\in C[a,b],P\in\mathscr{P}_n ,那么 P 是 f 的最佳Chebyshev逼近元素的充要条件是：误差曲线 f-P 在 [a,b] 有一个至少有n+2个点的交错点组.
这里我们只证充分性.
假设 f-P 有一个交错点组，它包含有n+2个点 x_0<x_1<...<x_{n+1} .
若 P 不是 f 的最佳Chebyshev逼近元素，则存在某一异于P的多项式 q\in\mathscr{P}_n 使：
||f-q||<||f-P||
按照模的定义 f(x_j)-P(x_j)=(-1)^j\sigma||f-P|| ,这里 \sigma 取-1或1，此处不妨设取1.
我们有： f(x_i)-q(x_i)\leq||f-q||<||f-P||=f(x_i)-P(x_i),i=2m,m\in Z,i\in\{0,1,2,...,n+1\} \Leftrightarrow P(x_i)-f(x_i)<0,i=2m,m\in Z,i\in\{0,1,2,...,n+1\} f(x_i)-q(x_i)\geq-||f-q||>-||f-P||=f(x_i)-P(x_i),i=2m+1,m\in Z,i\in\{0,1,2,...,n+1\} \Leftrightarrow P(x_i)-f(x_i)>0,i=2m+1,m\in Z,i\in\{0,1,2,...,n+1\}
由上我们可知 P-q 在n+2个点 x_0，x_1，...，x_{n+1} 交替变号，也就是说 P-q 在 [a,b] 上至少有n+1个根，由于 \deg(P-q)<n+1 ，由多项式恒等定理可知： P-q\equiv0 ，矛盾，故假设不成立，从而定理三充分性获证.
推论一：如果 f\in C[a,b] ,那么在 \mathscr{P}_n 中存在唯一的元素为 f 的最佳Chebyshev逼近.
推论二：如果 f\in C[a,b] ,则其最佳一致逼近n次多项式就是 f 在 [a,b] 上的某个n次Lagrange插值多项式.
推论三：如果函数 f(x) 在 [a,b] 有n+1阶导数且 f^{(n+1)}(x) 在区间 [a,b] 保号，那么区间 [a,b] 的端点属于 f-P 的交错点组.
三个推论的证明：
推论一的证明： 假设 P_1 和 P_2 都属于 \mathscr{P}_n 并且都是 f 的最佳逼近.现在定义： P_0=\frac{P_1+P_2}{2}
并记： E=||f-P_1||=||f-P_2||
那么： E\leq||f-P_0||=||\frac{f-P_1}{2}+\frac{f-P_2}{2}||\leq\frac{||f-P_1||}{2}+\frac{||f-P_2||}{2}=E
从而 P_0 也是 f 的最佳逼近.于是有点集： x_0<x_1<...<x_{n+1}
满足 f(x_j)-P_0(x_j)=(-1)^j\sigma E,j=0,1,...,n+1
由上式对于 j=0,1,...,n+1 ，有： E=|f(x_j)-P_0(x_j)|=|\frac{f(x_j)-P_1(x_j)}{2}+\frac{f(x_j)-P_2(x_j)}{2}|
\leq|\frac{f(x_j)-P_1(x_j)}{2}|+|\frac{f(x_j)-P_2(x_j)}{2}|\leq\frac{E}{2}+\frac{E}{2}=E
易知所有不等号取等.
从而有 f(x_j)-P_2(x_j)=f(x_j)-P_1(x_j)=E
\Leftrightarrow P_1(x_j)=P_2(x_j)
这意味着有n+2个根，而只有 P_1(x)\equiv P_2(x) 才有可能，故推论一得证.
推论二的证明： 令 P 是 f 的最佳逼近n次多项式，由定理3知： P-f 要么恒为0，要么在 [a,b] 中有n+2个点交替变号，而后一种情形，意味着 P-f 在 [a,b] 至少有n+1个根，于是 P 刚好是以这n+1个根为插值节点的Lagrange插值多项式，推论二得证.
推论三的证明： 反证法.
设a或b不属于 P-f 的交错点组，那么 R(x)=P(x)-f(x) 在开区间 (a,b) 至少有n+1个点 a<\xi_1<\xi_2<...<\xi_{n+1}<b ，使得 R^\prime(\xi_i)=0,i=1,2,...,n+1
由Rolle定理容易明白在 (a,b) 必有一数 \eta ，使： R^{(n+1)}(\eta)=0
但是 R^{(n+1)}(x)=P^{(n+1)}(x)-f^{(n+1)}(x)=-f^{(n+1)}(x)
从而推出有一数 \eta,a<\eta<b ，使： f^{(n+1)}(x)=0
而这跟 f^{(n+1)}(x) 在 [a,b] 保号的假设矛盾，推论三得证,
关于Chebyshev逼近理论的内容到此为止，我们来探究Chebyshev多项式的其他美妙性质.
第一类Chebyshev多项式的相关性质（比1深一点）及常用引理
1. T_n(x) 的其他表示形式：
表示1： T_n(x)=\sum_{k=0}^{[\frac{n}{2}]}(-1)^kC_{n}^{2k}x^{n-2k}(1-x^2)^k
表示2： T_n(x)=\sum_{l=0}^{[\frac{n}{2}]}x^{n-2l}\sum_{k=l}^{[\frac{n}{2}]}(-1)^lC_n^{2k}C_k^l
两种表示的证明：
表示1的证明：由多项式恒等定理，我们只需证明 |x|\leq1 该表示成立即可.
此时令 x=\cos\theta .
则:
T_n(x)=\cos n\theta=Re(e^{in\theta})
=Re[(\cos\theta+i\sin\theta)^n]
=Re[\sum_{r=0}^{n}C_n^r\cos^{n-r}\theta(i\sin\theta)^r]
=\sum_{k=0}^{[\frac{n}2]}C_n^{2k}\cos^{n-2k}\theta(-1)^k\sin^{2k}\theta
=\sum_{k=0}^{[\frac{n}2]}(-1)^kC_n^{2k}x^{n-2k}(1-x^2)^k
从而表示1得证.
表示2只需通过表示1二项式展开.
实际上，第二类Chebyshev多项式也有类似的拓广形式，即：
U_n(x)=\sum_{k\geq0}(-1)^kC_{n+1}^{2k+1}x^{n-2k}(1-x^2)^k
此处不赘述证明.
2. T_n(x) 的另一种递推式：
T_n(\frac{y+y^{-1}}{2})=\frac{y^n+y^{-n}}{2},y\in C,y\ne0
用开头的递推式易证.
3.函数列 \{T_n(x)\} 的生成函数. （其实感觉好像没什么大用但是感觉很漂亮所以也放上来啦）
\sum_{n\geq0}T_n(x) t^n=\frac{1-tx}{1-2tx+t^2}
证明：令 x=cos\theta 有：
\sum_{n\geq0}T_n(x) t^n=\sum_{n\geq0}t^n\cos n\theta =\frac{1}{2}\sum_{n\geq0}(t^ne^{in\theta}+t^ne^{-in\theta})
=\frac{1}{2}(\frac{1}{1-te^{i\theta}}+\frac{1}{1-te^{-i\theta}})
=\frac{1-t\cos\theta}{1-2t\cos\theta+t^2}
=\frac{1-tx}{1-2tx+t^2}
4.重要引理： T_n(x)={\sum}^\prime a_{k,n}\cdot2^{k-1}x^k,其中a_{k,n}\in Z
其中 {\sum}^\prime 表示对 k=n,n-2,n-4,... 求和.
证明：数学归纳法.
归纳奠基平凡.假设结论对n-1，n成立.
由开头给出的递推式易知：
T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)={\sum}^\prime a_{k,n}\cdot2^{k}x^{k+1}-{\sum}^\prime a_{k,n-1}\cdot2^{k-1}x^k
={\sum}^\prime(a_{k,n}-a_{k+1,n-1})2^{k}x^{k+1}
于是 a_{k+1,n+1}=a_{k,n}-a_{k+1,n-1}\in Z
所以n+1的情形也成立，由归纳法原理引理得证.
5.一个特殊形式的Chebyshev多项式（ T_n(x) 变式）： F_n(2\cos\theta)=2\cos n\theta
相比于 T_n(x) ,这种形式的多项式有一个优点.
即： 它们都首一！
由此多项式我们可以仿照 T_n(x) 的性质探究得出下列性质：
1） F_n(y+y^{-1})=y^n+y^{-n},y\in C,y\ne0
2） |x|\leq2 时有 |F_n(x)|\leq 2
...
还有一些根的分布的性质，此处不再赘述（因为完全可以换元转化为 T_n(x) ）
好像差不多了，下面是练习
练习
1.求出一个最大的A，对于A存在一个实系数多项式 p(x)=Ax^4+Bx^3+Cx^2+Dx+E 满足 0\leq p(x)\leq1,这里-1\leq x\leq1 .
2.(高考题)函数 g(x)=|-x^2+\frac{2}{3}bx+\frac{1}{3}c|,-1\leq x\leq 1 的最大值为M，求M的最小值.
3.用非代数数论方法证明： 马康哲：一个经典结论
4.将16个数： \frac{1}{2002},\frac{1}{2003},...,\frac{1}{2017} 分为两组，每组8个数，记其中一组的8个数为A，另一组的8个数为B.请给出一种分组方案使 |A-B| 最小，并说明理由.（2017CGMO p4）
正式更完w
