欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

多项式插值

最编程 2024-06-30 14:50:17
...

目录
  • The Vandermonde determinant
  • The Cauchy remainder
  • The Lagrange formula
  • The Newton formula
  • The Neville-Aitken algorithm
  • The Hermite interpolation
  • The Chebyshev polynomials
  • The Bernstein polynomials
  • Problem

 

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\) 处的值，然后估计 \(x\) 处的值 \(p_2^{[0]}(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 插值问题 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. 在 Hermite 插值问题中，记 \(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+1}(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,\\ \mathrm{s.t.}\quad\forall x\in[a,b],\ |p_n(x)-f(x)|<\epsilon \tag{2.40} \]

此定理证明了多项式函数是在连续函数集上是稠密的.

 

Problem

\(\mathrm{II}.\) 对 \(f_i\ge 0,i=0,1,\cdots,n\) 构造非负的插值多项式

显然有拉格朗日插值多项式

\[p(x) = \sum_{i=0}^n f_il_i(x) \]

那么就可以直接平方

\[p(x) = \sum_{i=0}^n f_il_i^2(x) \]

就得到非负多项式.

 

\(\mathrm{V}.\) 利用柯西余项和差分估计余项函数 \(\xi\)

根据牛顿插值公式的余项和柯西余项对比

\[f[x_0,x_1,\cdots,x_n] = \dfrac{1}{n!}f^{(n)}(\xi) \]

而可以计算出 \(\xi\) .

 

\(\mathrm{VIII}.\) 设 \(f\) 在 \(x_0\) 处可导，证明

\[\dfrac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_{n+1}] = f[x_0,x_0,x_1,\dots,x_{n+1}] \]

\(Proof.\) 应用数学归纳法，对 $ n=0 $ 有 $ \frac{\partial}{\partial x_0}f[x_0] = \frac{\partial f(x_0)}{\partial x_0} = f[x_0,x_0] $ 成立；设对 $ n $ 成立，则有

\[\begin{aligned} \dfrac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_{n+1}] &= \dfrac{\partial}{\partial x_0} \dfrac{f[x_0,x_1,\dots,x_n]-f[x_1,x_2,\dots,x_{n+1}]}{x_{n+1}-x_0}\\ &= \dfrac{f[x_0,x_0,x_1,\dots,x_n](x_{n+1}-x_0)+f[x_0,x_1,\dots,x_n]-f[x_1,x_2,\dots,x_{n+1}]}{(x_{n+1}-x_0)^2}\\ &= \dfrac{f[x_0,x_0,x_1,\dots,x_n]-f[x_0,x_1,\dots,x_{n+1}]}{x_{n+1}-x_0}\\ &= f[x_0,x_0,x_1,\dots,x_{n+1}] \end{aligned} \]

由归纳假设即证.

 

\(\mathrm{IX}.\) 对 \(n\in\mathbb{N}^+\) ，确定

\[\min\max_{x\in[a,b]}|a_0x^n+a_1x^{n-1}+\cdots+a_n| \]

其中 \(a_0\neq0\) 固定，在 \(a_i\in\mathbb{R},\ i=1,2,\cdots,n\) 上取最小值.

对任意多项式

\[p(x) = a_0x^n+a_1x^{n-1}+\cdots+a_n,\ x\in[a,b] \]

做变量代换 \(x = \frac{b-a}{2}t + \frac{a+b}{2}\) 得到

\[\begin{aligned} p(t) &= a_0\left(\dfrac{b-a}{2}t + \dfrac{a+b}{2}\right)^n+a_1\left(\dfrac{b-a}{2}t+ \dfrac{a+b}{2}\right)^{n-1}+\cdots+a_n,\\ &= c_0t^n+c_1t^{n-1}+\cdots+c_n,\ t\in[-1,1] \end{aligned} \]

则其中 $ c_0 = a_0(\frac{b-a}{2})^n $ ；由 Corollary 3.41，首一多项式 $ \left|\frac{p(t)}{c_0}\right| $ 满足

\[\max_{t\in[-1,1]} \left|\dfrac{p(t)}{c_0}\right| \ge \dfrac{1}{2^{n-1}} \]

且存在首一化的 Chebyshev 多项式可取得等号，故有

\[\min\max_{t\in[-1,1]}|p(t)| = \dfrac{c_0}{2^{n-1}} = \dfrac{a_0(b-a)^n}{2^{2n-1}} \]

由于上述代换是可逆等价代换，从而有

\[\min\max_{x\in[a,b]}\left|a_0x^n+a_1x^{n-1}+\cdots+a_n\right| = \dfrac{a_0(b-a)^n}{2^{2n-1}} \]

即得.

 

\(\mathrm{X}.\) 对给定的 \(a>1\) ，定义 \(\mathbb{P}_n^a =\{p\in\mathbb{P}_n:p(a)=1\}\) ，多项式 \(\hat{p}_n(x)\in\mathbb{P}_n^a\) 满足

\[\hat{p}_n(x) = \dfrac{T_n(x)}{T_n(a)} \]

证明

\[\forall p\in\mathbb{P}_n^a,\quad \|\hat{p}_n\|_{\infty} \le \|p\|_{\infty} \]

其中函数 \(f:\mathbb{R}\to\mathbb{R}\) 的范数定义为 \(\|f\|_{\infty}=\max_{x\in[-1,1]}|f(x)|\) .

\(Proof.\) 反设

\[\exists p\in \mathbb{P}_n^a,\quad \mathrm{s.t.}\quad \lVert p\lVert_{\infty} \le \lVert \hat{p}_n(x)\lVert_{\infty} = \left|\frac{1}{T_n(a)}\right| \]

令 $ Q(x) = \hat{p}_n(x) - p $ ，则在 $ T_n(x) $ 的极值点 $ x_i$ 有

\[Q(x_i) = \frac{(-1)^k}{T_n(a)} - p(x_i),\quad i=0,1,\dots,n \]

从而 $ Q(x) $ 在 $ x_i $ 处交替符号，故在 $ [-1,1] $ 上有 $ n $ 个零点；而由 $ \hat{p}_n(x) $ 的构造

\[Q(a) = \hat{p}_n(a) - p(a) = 0 \]

则 $ x=a>1 $ 也是 $ Q(x) $ 的零点，从而 $ Q(x) $ 存在 $ n+1 $ 个零点，至少是 $ n+1 $ 阶多项式，而由 $ Q(x) $ 的构造， $ Q(x) $ 至多是 $ n $ 阶多项式，推出矛盾，即证.

上一篇： 插值相关总结

下一篇： 计算方法 - 第 2 章 插值法 - 问题解决

推荐阅读