多项式插值
The Vandermonde determinant
Definition 2.3. 对 \(n+1\) 个给定的点 \(x_0,x_1,\cdots,x_n\in\mathbb{R}\) ，范德蒙矩阵 Vandermonde matrix \(V\in\mathbb{R}^{(n+1)\times(n+1)}\) 定义为
\[V(x_0,x_1,\cdots,x_n) = \left( \begin{matrix} 1 & x_0 & \cdots & x_0^n\\ 1 & x_1 & \cdots & x_1^n\\ \vdots & \vdots & \ddots & \vdots\\ 1 & x_n & \cdots & x_n^n\\ \end{matrix} \right) \tag{2.1} \]Lemma 2.4. 范德蒙矩阵的行列式可表达为
\[\det\ V(x_0,x_1,\cdots,x_n) = \prod_{i>j}(x_i-x_j) \tag{2.2} \]Theorem 2.5 (Uniqueness of polynomial interpolation). 给定互异点 \(x_0,x_1,\cdots,x_n\in\mathbb{C}\) 以及对应的值 \(f_0,f_1,\cdots,f_n\in\mathbb{C}\) ，用 \(\mathbb{P}_n\) 表示次数不高于 \(n\) 的多项式类，则存在唯一多项式 \(p_n(x)\in\mathbb{P}_n\) 使得
\[\forall i=0,1,\cdots,n,\quad p_n(x_i) = f_i \tag{2.3} \]\(Proof.\) 不妨设该多项式为 \(\sum_{i=0}^na_ix^i\) ，则代入初始条件可得 \(n+1\) 个线性多项式方程，并且其系数矩阵恰为范德蒙矩阵，由各点互异显然其行列式不为零，因而存在唯一的解.
The Cauchy remainder
Theorem 2.6 (Generalized Rolle). 令 \(n\ge 2\) ，设 \(f\in\mathcal{C}^{n-1}[a,b]\) 以及 \(f^{(n)}(x)\) 在 \([a,b]\) 上存在。若对 \(a\le x_0 < x_1 < \cdots < x_n \le b\) 有 \(f(x_0)=f(x_1)=\cdots=f(x_n)=0\) ，则存在点 \(\xi\in(x_0, x_n)\) 使得 \(f^{(n)}(\xi) = 0\) .
\(Proof.\) 运用罗尔定理，在 \([x_0,x_n]\) 上得到 \(n\) 个 \(f^{\prime}\) 的零点，反复使用即证.
Theorem 2.7 (Cauchy remainder of polynomial interpolation). 令 \(f\in\mathcal{C}^n[a,b]\) 并假设 \(f^{(n+1)}(x)\) 在 \((a,b)\) 上存在，令 \(p_n(f;x)\in\mathbb{P}_n\) 表示在 \(x_0,x_1,\cdots,x_n\) 处符合 \(f\) 的唯一多项式，定义
\[R_n(f;x) = f(x) - p_n(f;x) \tag{2.4} \]为多项式插值的柯西余项 Cauchy remainder of the polynomial interpolation ；若 \(a\le x_0 < x_1 < \cdots < x_n \le b\) ，则有 \(\xi\in(a,b)\) 使得
\[R_n(f;x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i) \tag{2.5} \]\(Proof.\) 由于 \(f(x_k) = p_n(f;x_k)\) ，则余项在 \(x_k\) 处归零。选取 \(x\neq x_0,x_1,\cdots,x_n\) ，定义
\[K(x) = \dfrac{f(x)-p_n(f;x)}{\prod_{i=0}^n(x-x_i)} \]也就是说，我们想证明不变的量
\[\dfrac{R_n(f;x)}{K(x)} = \dfrac{f^{(n+1)}(\xi)}{(n+1)!} \]于是我们定义
\[W(t) = R_n(f;t) - K(x)\prod_{i=0}^n(t-x_i) \]注意到 \(W(t)\) 在 \(x_k\) 处归零，并且 \(W(x)=0\) ，共有 \(n+2\) 个零点，这样可以应用 Theorem 2.6 得到
\[0 = W^{(n+1)}(\xi) = f^{(n+1)}(\xi) - (n+1)!K(x),\quad \xi\in (a,b) \]即证.
Corollary 2.8. 设 \(f(x)\in\mathcal{C}^{n+1}[a,b]\) ，则
\[|R_n(f;x)| \le \dfrac{M_{n+1}}{(n+1)!}\prod_{i=0}^n|x-x_i| \le \dfrac{M_{n+1}}{(n+1)!}(b-a)^{n+1} \tag{2.6} \]其中 \(M_{n+1} = \max_{x\in[a,b]}\left|f^{(n+1)}(x)\right|\) .
The Lagrange formula
Definition 2.10. 在互异点 \(x_0,x_1,\cdots,x_n\) 处插值 \(f_0,f_1,\cdots,f_n\) ，拉格朗日公式 Lagrange formula 为
\[p_n(x) = \sum_{k=0}^n f_kl_k(x) \tag{2.7} \]其中初等拉格朗日插值多项式 elementary Lagrange interpolation polynomial 为
\[l_k(x) = \prod_{i\neq k;i=0}^n\dfrac{x-x_i}{x_k-x_i} \tag{2.8} \]特别的，当 \(n=0\) ，有 \(l_0 = 1\) .
Lemma 2.12. 定义对称多项式
\[\pi_n(x) = \left\{ \begin{aligned} &1,\ &n=0\\ &\prod_{i=0}^{n-1}(x-x_i),\ &n>0 \end{aligned} \right. \tag{2.9} \]则 \(n>0\) 的逐点插值基本多项式 fundamental polynomial for pointwise interpolation 可以表示为
\[\forall x\neq x_k,\quad l_k(x) = \dfrac{\pi_{n+1}(x)}{(x-x_k)\pi^{\prime}_{n+1}(x_k)} \tag{2.10} \]Lemma 2.13 (Cauchy relations). 基本多项式 \(l_k(x)\) 满足如下的柯西关系
\[\sum_{k=0}^nl_k(x) \equiv 1 \tag{2.11} \]\[\forall j=1,\cdots,n,\quad \sum_{k=0}^n(x_k-x)^jl_k(x) \equiv 0 \tag{2.12} \]\(Proof.\) 分别对 \(f(x)\equiv 1\) 和 \(q(u) = (u-x)^j,\ j=1,\cdots,n\) 插值即证；其中对 \(q(u)\) 在 \(x_0,x_1,\cdots,x_n\) 的插值多项式为
\[p(u) = \sum_{k=0}^n(x_k-x)^jl_k(u)\ \Rightarrow\ \sum_{k=0}^n(x_k-x)^jl_k(x) = p(x) = q(x) = 0 \]巧妙的代换.
The Newton formula
Definition 2.14 (Divided difference and the Newton formula). 在互异点 \(x_0,x_1,\cdots,x_n\) 处插值 \(f_0,f_1,\cdots,f_n\) ，牛顿公式 Newton formula 为
\[p_n(x) = \sum_{k=0}^n a_k\pi_k(x) \tag{2.13} \]其中 \(\pi_k\) 定义如前，第 \(k\) 个差分 divided difference \(a_k\) 定义为 \(p_k(f;x)\) 中 \(x^k\) 的系数，表示为 \(f[x_0,x_1,\cdots,x_k]\) .
Corollary 2.15. \(f[x_0,x_1,\cdots,x_k]\) 与插值点的顺序无关.
Corollary 2.16. 第 \(k\) 个差分 \(a_k\) 可表示为
\[f[x_0,x_1,\cdots,x_k] = \sum_{i=0}^k\dfrac{f_i}{\prod_{j\neq i;j=0}^{k}(x_i-x_j)} = \sum_{i=0}^k\dfrac{f_i}{\pi_{k+1}^{\prime}(x_i)} \tag{2.14} \]\(Proof.\) 我们发现对于互异点 \(x_0,x_1,\cdots,x_{k-1}\) 进行插值后，当加入新的点 \(x_{k}\) 时，之前的 \(k\) 项都不变，只添加一项 \(k\) 次多项式
\[a_{k}\pi_{k}(x) = a_{k}\prod_{i=0}^{k-1}(x-x_i) \]由于插值多项式的唯一性，对比 Lagrange 插值公式即证.
Theorem 2.17. 差分满足递推式
\[f[x_0,x_1,\cdots,x_k] = \dfrac{f[x_1,x_2,\cdots,x_{k}]-f[x_0,x_1,\cdots,x_{k-1}]}{x_{k}-x_0} \tag{2.15} \]\(Proof.\) 由差分的定义， \(f[x_1,x_2,\cdots,x_k]\) 是 \(k-1\) 次插值多项式 \(P_2(x)\) 中 \(x^{k-1}\) 的系数，不妨再令 \(P_1(x)\) 表示 \(x^{k-1}\) 系数为 \(f[x_0,x_1,\cdots,x_{k-1}]\) 的 \(k-1\) 次插值多项式，仿照递推式构造
\[P(x) = P_1(x) + \dfrac{x-x_0}{x_k-x_0}(P_2(x)-P_1(x)) \]容易验证 \(P(x)\) 恰为在 \(x_0,x_1,\cdots,x_k\) 的插值多项式，注意到 \(x^k\) 出现在
\[\dfrac{x}{x_k-x_0}(P_2(x)-P_1(x)) \in \mathbb{P}_k \]并且其系数 \(f[x_0,x_1,\cdots,x_k]\) 显然满足递推式.
Definition 2.18. 第 \(k\) 个差分在差分表中 \((k\in\mathbb{N}^+)\)
\[\begin{matrix} x_0 & f[x_0]\\ x_1 & f[x_1] & f[x_0,x_1]\\ x_2 & f[x_2] & f[x_1,x_2] & f[x_0,x_1,x_2]\\ x_3 & f[x_3] & f[x_2,x_3] & f[x_1,x_2,x_3] & f[x_0,x_1,x_2,x_3]\\ \cdots & \cdots & \cdots & \cdots & \cdots \end{matrix} \]每次通过递推式从左上向右下计算差分，取对角线上的系数 \(f[x_0,x_1,\cdots,x_k]\) .
Theorem 2.21. 对互异点 \(x_0,x_1,\cdots,x_n\) 和 \(x\) 有
\[f(x) = f[x_0] + f[x_0,x_1](x-x_0) + \cdots + f[x_0,x_1,\cdots,x_n]\prod_{i=0}^{n-1}(x-x_i) + f[x_0,x_1,\cdots,x_n,x]\prod_{i=0}^{n}(x-x_i) \tag{2.16} \]\(Proof.\) 注意 \(f\) 不是给定的函数，此定理是未知的 \(f\) 在 \(x\) 处的值满足的公式。不妨设另一个点 \(z\neq x_i\) ，对 \(x_0,x_1,\cdots,x_n,z\) 运用牛顿公式得到
\[Q(x) = f[x_0] + f[x_0,x_1](x-x_0) + \cdots + f[x_0,x_1,\cdots,x_n]\prod_{i=0}^{n-1}(x-x_i) + f[x_0,x_1,\cdots,x_n,z]\prod_{i=0}^{n}(x-x_i) \]由插值条件有 \(Q(z) = f(z)\) ，从而
\[f(z) = Q(z) = f[x_0] + f[x_0,x_1](z-x_0) + \cdots + f[x_0,x_1,\cdots,x_n]\prod_{i=0}^{n-1}(z-x_i) + f[x_0,x_1,\cdots,x_n,z]\prod_{i=0}^{n}(z-x_i) \]将 \(z\) 替换为 \(x\) 即证；若 \(x = x_j\) ，则令 \(f(x) = p_n(f;x)+R(x)\) ，其中
\[R(x) = f[x_0,x_1,\cdots,x_n,x]\prod_{i=0}^{n}(x-x_i) \]我们需要证明
\[\forall j=0,1,\cdots,n,\quad p_n(f;x_j) + R(x_j) - f(x_j) = 0 \]这实际上是显然的，因为 \(R(x_j) = 0\) ，并且 \(p_n(f;x_j) = f(x_j)\) .
Corollary 2.22. 设 \(f\in\mathcal{C}^n[a,b]\) 及 \(f^{(n+1)}(x)\) 在 \((a,b)\) 上存在，若 \(a\le x_0 < x_1 < \cdots < x_n \le b\) ，则有 \(\xi(x)\in(a,b)\) 使得
\[f[x_0,x_1,\cdots,x_n,x] = \dfrac{1}{(n+1)!}f^{(n+1)}(\xi(x)) \tag{2.17} \]\(Proof.\) 由 Theorem 2.21 及 Theorem 2.7 中的柯西余项即证；此推论说明了一个重要的结论： \(n\) 次多项式 \(f\) 的差分满足
\[f[x_0,x_1,\cdots,x_n,x_{n+1}] = 0 \]因此对 \(n\) 次多项式多于 \(n+1\) 个点的插值多项式也是 \(n\) 次多项式.
Corollary 2.23. 若 \(x_0 < x_1 < \cdots < x_n\) 及 \(f\in\mathcal{C}^n[x_0,x_n]\) ，则有
\[\lim_{x_n\to x_0}f[x_0,x_1,\cdots,x_n] = \dfrac{1}{n!}f^{(n)}(x_0) \tag{2.18} \]\(Proof.\) 在 Corollary 2.22 中令 \(x = x_{n+1}\) 即证.
Definition 2.24. 双序列 bisequence 是一个函数 \(f:\mathbb{Z}\to\mathbb{R}\) .
Definition 2.25. 前移 forword shift \(E\) 和 后移 backward shift \(B\) 是双序列的线性空间 \(V\) 上的线性算子 \(V\mapsto V\) ，给出
\[(Ef)(i) = f(i+1),\quad (Bf)(i) = f(i-1) \tag{2.19} \]向前差分 forward difference \(\Delta\) 和向后差分 backward difference \(\nabla\) 是线性算子 \(V\mapsto V\) ，给出
\[\Delta = E-I,\quad \nabla = I-B \tag{2.20} \]其中 \(I\) 是 \(V\) 上的单位算子.
Theorem 2.27. 向前差分和向后差分有关系
\[\forall n\in\mathbb{N}^+,\quad \Delta^nf_i = \nabla^nf_{i+n} \tag{2.21} \]\(Proof.\) 应用归纳法即证；从含义来看，左边在向前差分时左移了 \(n\) 次，因此计算向后差分就要提前左移 \(n\) 步.
Theorem 2.28. 向前差分可表示为
\[\Delta^nf_i = \sum_{k=0}^n(-1)^{n-k}\left( \begin{matrix} n\\ k \end{matrix} \right)f_{i+k} \tag{2.22} \]\(Proof.\) 利用组合数等式
\[\left( \begin{matrix} n\\ k \end{matrix} \right) + \left( \begin{matrix} n\\ k-1 \end{matrix} \right) = \left( \begin{matrix} n+1\\ k \end{matrix} \right) \]对 \(n\) 进行归纳即证.
Theorem 2.29. 网格 \(x_i = x_0 + ih\) 是关于 \(h\) 均匀的，序列 \(f_i = f(x_i)\) 满足
\[\forall n\in\mathbb{N}^+,\quad f[x_0,x_1,\cdots,x_n] = \dfrac{\Delta^nf_0}{n!h^n} \tag{2.23} \]\(Proof.\) 应用归纳法即证；注意到 \(f[x_0,x_1,\cdots,x_n]\) 从 \(0\) 左移 \(n\) 位进行差分，因此有 \(\Delta^nf_0\) 项，相应的每一位都要除以左右两端的差 \(kh\) ，累乘得到 \(n!h^n\) 项.
Theorem 2.30 (Newton's forward difference formula). 设 \(p_n(f;x)\in\mathbb{P}_n\) 是在均匀网格 \(x_i = x_0 + ih\) 上的插值多项式，则
\[\forall s\in\mathbb{R},\quad p_n(f;x_0+sh) = \sum_{k=0}^n\left( \begin{matrix} s\\ k \end{matrix} \right)\Delta^kf_0 \tag{2.24} \]其中 \(\Delta^0f_0 = f_0\) 并且
\[\left( \begin{matrix} s\\ k \end{matrix} \right) = \dfrac{s(s-1)\cdots(s-k+1)}{k!} \tag{2.25} \]\(Proof.\) 在 Theorem 2.21 中令 \(f(x) = p_n(f;x)\) ，则有
\[p(x) = f[x_0] + f[x_0,x_1](x-x_0) + \cdots + f[x_0,x_1,\cdots,x_n]\prod_{i=0}^{n-1}(x-x_i) \]由于 \(p(x)\in\mathbb{P}_n\) ，因此没有余项；再应用 Theorem 2.29 得到
\[p(x) = f_0 + \sum_{k=0}^n\dfrac{\Delta^kf_0}{k!h^k}\prod_{i=0}^{k-1}(x-x_i) \]注意到 \(x-x_i = (x_0+sh)-(x_0+ih) = (s-i)h\) ，代入即证.
The Neville-Aitken algorithm
Theorem 2.31. 记 \(p_0^{[i]}=f(x_i),\ i=0,1,\cdots,n\) ，则对任意 \(k=0,1,\cdots,n-1\) 及 \(i=0,1,\cdots,n-k-1\) ，定义
\[p_{k+1}^{[i]}(x) = \dfrac{(x-x_i)p_k^{[i+1]}(x)-(x-x_{i+k+1})p_k^{[i]}(x)}{x_{i+k+1}-x_i} \tag{2.26} \]其中 \(p_k^{[i]}\) 是在点 \(x_i,x_{i+1},\cdots,x_{i+k}\) 上的插值多项式。特别的， \(p_n^{[0]}\) 是在 \(x_0,x_1,\cdots,x_n\) 上的 \(n\) 次插值多项式.
\(Proof.\) 对 \(k\) 运用归纳法，代入插值点 \(x_i,x_{i+1},\cdots,x_{i+k+1}\) 都成立，即证。需要注意，此算法是在不计算插值多项式的情况下，直接计算插值多项式在 \(x\) 处的值.
Note. 我们通过表格法进行算法过程，不妨假设在 \(x_0,x_1,x_2\) 进行插值，然后估计 \(x\) 处的值
\[\begin{matrix} x_i & x-x_i & p_0^{[i]} & p_1^{[i]} & p_2^{[i]}\\ \hline x_0 & x-x_0 & f_0 & \frac{(x-x_0)f_1-(x-x_1)f_0}{x_1-x_0} & \frac{(x-x_0)p_1^{[1]}-(x-x_2)p_1^{[0]}}{x_2-x_0}\\ x_1 & x-x_1 & f_1 & \frac{(x-x_1)f_2-(x-x_2)f_1}{x_2-x_1}\\ x_2 & x-x_2 & f_2 \end{matrix} \]计算 \(p_{k+1}^{[i]}\) 所在列时，每次计算一个行列式，然后除以 \(x_{i+k+1}-x_i\)
\[\det\left(\begin{matrix} x-x_i & p_k^{[i]}\\ x-x_{i+k+1} & p_k^{[i+1]} \end{matrix}\right) \]注意，左边两个 \(x-x_i\) 之间要相隔 \(k+1\)，而右边两个 \(p_k^{[i]}\) 是相邻的.
The Hermite interpolation
Definition 2.33. 给定 \([a,b]\) 上的互异点 \(x_0,x_1,\cdots,x_k\) ，非负整数 \(m_0,m_1,\cdots,m_k\) ，以及函数 \(f\in\mathcal{C}^M[a,b],\ M=\max_im_i\) ，埃尔米特插值问题 Hermite interpolation problem 寻找最低次的多项式 \(p\) 使得
\[\forall i=0,1,\cdots,k,\ \forall \mu=0,1,\cdots, m_i,\quad p^{(\mu)}(x_i) = f_i^{(\mu)} \tag{2.27} \]其中 \(f_i^{(\mu)} = f^{(\mu)}(x_i)\) 为 \(f\) 在 \(x_i\) 处的 \(\mu\) 阶导数。特别的， \(f_i^{(0)} = f(x_i)\) .
Definition 2.34. 在 \(n+1\) 个相同点的第 \(n\) 个差分定义为
\[f[x_0,x_0,\cdots,x_0] = \dfrac{1}{n!}f^{(n)}(x_0) \tag{2.28} \]其中 \(x_0\) 重复出现 \(n+1\) 次.
Theorem 2.35. 在埃尔米特插值问题中，记 \(N=k+\sum_{i}m_i\) ，用 \(p_N(f;x)\in\mathbb{P}_N\) 表示满足条件的唯一多项式，设 \(f^{(N+1)}(x)\) 在 \((a,b)\) 上存在，则有 \(\xi\in(a,b)\) 使得
\[f(x) - p_N(f;x) = \dfrac{f^{(N+1)}(\xi)}{(N+1)!}\prod_{i=0}^{k}(x-x_i)^{m_i+1} \tag{2.29} \]\(Proof.\) 类似于 Theorem 2.7 ，考虑
\[K(x) = \dfrac{f(x) - p_N(f;x)}{\prod_{i=0}^{k}(x-x_i)^{m_i+1}} \]对于固定的 \(x\neq x_0,x_1,\cdots,x_k\) ，构造函数 \(W(t)\) 在 \(x_0,x_1,\cdots,x_k,x\) 处为零，然后应用罗尔定理
\[W(t) = f(t) - p_N(f;t) - K(x)\prod_{i=0}^{k}(t-x_i)^{m_i+1} \]注意到每次对 \(W^{(i)}\) 使用罗尔定理，总零点数减少一个，然后增加 \(W^{(i+1)}\) 的零点数，因此应用 \(N\) 次罗尔定理即证.
The Chebyshev polynomials
Example 2.38 (Runge phenomenon). 点 \(x_0,x_1,\cdots,x_k\) 给出一个先验 priori ，例如在区间 \([x_0,x_n]\) 上的均匀分布。随着 \(n\) 的增加，插值多项式的次数也在增加，理想情况下我们希望有
\[\forall f\in\mathcal{C}[x_0,x_n],\ \forall x\in[x_0,x_n],\ \lim_{n\to\infty}p_n(f;x) = f(x) \]然而，在等距点插值的多项式并非如此。通过对
\[f(x) = \dfrac{1}{1+x^2} \]在 \(x_i = -5+10\frac{i}{n},\ i=0,1,\cdots,n\) 进行插值
得到的曲线在实际曲线附近不断振荡.
Definition 2.39. \(n\) 次第一类切比雪夫多项式 Chebyshev polynomial 是多项式 \(T_n:[-1,1]\to[-1,1]\)
\[T_n(x) = \cos(n\arccos x) \tag{2.30} \]Theorem 2.40. 第一类切比雪夫多项式满足递推关系
\[\forall n\in\mathbb{N}^+,\quad T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x) \tag{2.31} \]\(Proof.\) 设 \(x = \cos t\) ，则有
\[T_{n+1}(x) = \cos (n+1)t = \cos nt\cos t - \sin nt\sin t = xT_n(x) - \sin nt\sin t\\ T_{n-1}(x) = \cos (n-1)t = \cos nt\cos t + \sin nt\sin t = xT_n(x) + \sin nt\sin t \]上下两式相加即证.
Corollary 2.41. 对 \(n>0\) ， \(T_n\) 中 \(x^n\) 的系数为 \(2^{n-1}\) .
Theorem 2.42. \(T_n(x)\) 有 \(n\) 个单零点
\[x_k = \cos\dfrac{2k-1}{2n}\pi,\quad k=1,2,\cdots,n \tag{2.32} \]对 \(x\in[-1,1]\) 及 \(n\in\mathbb{N}^+\) ， \(T_n(x)\) 有 \(n+1\) 个极值点
\[x_k^{\prime} = \cos\dfrac{k}{n}\pi,\quad k=0,1,\cdots,n \tag{2.33} \]其中每个极值点的值为 \((-1)^k\) .
\(Proof.\) 直接代入验证即得 \(x_k\) 均为零点，由于 \(T_n(x)\in\mathbb{P}_n\) ，它们就是所有的零点；求导得
\[T_n^{\prime}(x) = \dfrac{n}{\sqrt{1-x^2}}\sin(n\arccos x) \]由于 \(T_n^{\prime}(x_k) \neq 0\) ，它们都是单零点。类似的，可以验证 \(T_n^{\prime}(x_k^{\prime})=0,\ T_n^{\prime\prime}(x_k^{\prime})\neq 0,\ k=1,2,\cdots,n-1\) ，从而这 \(n-1\) 个点都是极值点，由于 \(T_n^{\prime}(x)\in\mathbb{P}_{n-1}\) ，它们是仅有的极值点，每个极值点的值为 \((-1)^k\) 。注意到端点 \(k=0,n\) 时也可取极值，即证.
Theorem 2.43 (Chebyshev). 记 \(\mathbb{\tilde{P}}_n\) 为全体 \(n\in\mathbb{N}^+\) 次首一多项式的类，则
\[\forall p\in\mathbb{\tilde{P}}_n,\quad \max_{x\in[-1,1]}\left|\dfrac{T_n(x)}{2^{n-1}}\right| \le \max_{x\in[-1,1]}|p(x)| \tag{2.34} \]\(Proof.\) 事实上，由 Theorem 2.42 ，有 \(|T_n(x)|\le 1\) ，因此不妨假设
\[\exists p\in\mathbb{\tilde{P}}_n,\quad \mathrm{s.t.}\quad \max_{x\in[-1,1]}|p(x)| < \dfrac{1}{2^{n-1}} \]构造多项式
\[Q(x) = \frac{T_n(x)}{2^{n-1}}-p(x)\ \Rightarrow\ Q(x_k^{\prime}) = \dfrac{(-1)^k}{2^{n-1}} - p(x_k^{\prime}) \]这意味着在 \(x_k^{\prime}\) 处 \(p(x)\) 总是会改变符号，因此它有至少 \(n\) 个零点。然而，在构造 \(Q(x)\) 时，两个首一多项式相减，得到 \(n-1\) 次多项式，从而 \(Q(x)\) 只能为零，矛盾.
Corollary 2.45. 对 \(n\in\mathbb{N}^+\) ，有
\[\max_{x\in[-1,1]}\left|x^n+a_1x^{n-1}+\cdots+a_n\right|\ge \dfrac{1}{2^{n-1}} \tag{2.35} \]\(Proof.\) 此推论是上述定理的直接结论.
Corollary 2.46. 设多项式插值在 \(T_n(x)\) 的 \(n+1\) 个零点上进行，则柯西余项满足
\[|R_n(f;x)| \le \dfrac{1}{2^n(n+1)!}\max_{x\in[-1,1]}\left|f^{(n+1)}(x)\right| \tag{2.36} \]\(Proof.\) 应用 Theorem 2.7 有
\[|R_n(f;x)| = \dfrac{\left|f^{(n+1)}(\xi)\right|}{(n+1)!}\left|\prod_{i=0}^{n}(x-x_i)\right| \le \dfrac{\left|f^{(n+1)}(\xi)\right|}{2^n(n+1)!} \]即证.
The Bernstein polynomials
Definition 2.47. 单位区间 \([0,1]\) 上的 \(n\) 次伯恩斯坦基本多项式 Bernstein base polynomials 为
\[b_{n,k}(t) = \left( \begin{matrix} n\\ k \end{matrix} \right)t^k(1-t)^{n-k} \tag{2.37} \]其中 \(k=0,1,\cdots,n\) .
Lemma 2.48. 伯恩斯坦基本多项式满足 \(\forall k=0,1,\cdots,n,\ \forall t\in(0,1)\) ，有
\[\begin{aligned} b_{n,k}(t) &> 0,\\ \sum_{k=0}^{n}b_{n,k}(t) &= 1,\\ \sum_{k=0}^{n}kb_{n,k}(t) &= nt,\\ \sum_{k=0}^{n}(k-nt)^2b_{n,k}(t) &= nt(1-t) \end{aligned} \tag{2.38} \]\(Proof.\) 可以看出伯恩斯坦多项式的格式恰为二项分布，从而根据二项分布的性质易得
\[\begin{aligned} b_{n,k}(t) &= P(X=k) > 0,\\ \sum_{k=0}^{n}b_{n,k}(t) &= \sum_{k=0}^nP(X=k) = 1,\\ \sum_{k=0}^{n}kb_{n,k}(t) &= EX = nt,\\ \sum_{k=0}^{n}(k-nt)^2b_{n,k}(t) &= DX = nt(1-t) \end{aligned} \]即证.
Lemma 2.49. \(n\) 次伯恩斯坦基本多项式构成 \(\mathbb{P}_n\) 的一组基.
Definition 2.50. 映射 \(f\in\mathcal{C}[0,1]\) 的第 \(n\) 伯恩斯坦多项式为
\[(B_nf)(t) = \sum_{k=0}^{n}f\left(\dfrac{k}{n}\right)b_{n,k}(t) \tag{2.39} \]Theorem 2.51 (Weierstrass approximation). 任意连续函数 \(f:[a,b]\to\mathbb{R}\) 可以被多项式函数一致逼近，即
\[\forall f\in\mathcal{C}[a,b],\ \forall \epsilon > 0,\ \exists N\in\mathbb{N}^+,\quad \mathrm{s.t.}\quad \forall n>N,\ \exists p_n\in\mathbb{P}_n,\quad \mathrm{s.t.}\quad \forall x\in[a,b],\ |p_n(x)-f(x)|<\epsilon \tag{2.40} \]此定理证明了多项式函数是在连续函数集上是稠密的.