函数矩的约束条件下对范数的优化问题

问题0

设 $f \in L^{\infty} ([0, 1] \to R)$ 满足 $\int_{0}^{1} x^{k} f (x) d x = 0, (k = 0, 1, \dots, n - 1), \int_{0}^{1} x^{n} f (x) d x = 1$ 证明 $∣∣ f ∣ ∣_{L^{\infty}} \geq 2^{n} (n + 1)$

这里的下界远不是最优的结果，最优下界为 $∣∣ f ∣ ∣_{L^{\infty}} \geq 2^{2 n}$

1.从多个角度来说明，为什么原问题中的估计很松？

1.1 从寻找L1范数尽可能小的n次首1多项式入手

令 $V_{n} := span {1, x, \dots, x^{n}}$ ,根据题目给的关于函数矩的信息，我们可以推断出关于 $\int_{[0, 1]} P (x) f (x) d x$ 的信息。

具体来说，对任意确定的 $P (x) := a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{1} x + a_{0}$ 我们有 $\int_{[0, 1]} P (x) f (x) d x = a_{n}$ 于是很自然想到借助于Holder不等式估计 $f$ 的范数。此处我们需要的是 $f$ 的 $L^{\infty}$ 范数，因此使用 $1, \infty$ 型的Holder不等式： $∣ a_{n} ∣ \leq ∣∣ f ∣ ∣_{L^{\infty}} \cdot ∣∣ P ∣ ∣_{L^{1}}$ 从而 $∣∣ f ∣ ∣_{L^{\infty}} \geq \frac{∣ a _{n} ∣}{∣∣ P ∣ ∣ _{L^{1}}}, P \neq = 0$ 从而问题就变成了求 $I_{n} := sup_{P \in V_{n}, P \neq = 0} \frac{∣ a _{n} ∣}{∣∣ P ∣ ∣ _{L^{1}}}$ 进一步还可以简化，由于积分的线性性，我们可以把 $∣ a_{n} ∣$ 移到分母上从而把所有需要优化的对象集中在一个位置，于是

I_{n} := P \in V_{n}, monic sup \frac{1}{∣∣ P ∣ ∣ _{L^{1}}} (1.1.A)

也就是求

J_{n} := P \in V_{n}, monic in f ∣∣ P ∣ ∣_{L^{1}} (1.1.B)

一旦得到 $(1.1. B)$ 那么 $(1.1. A)$ 可以根据 $I_{n} = \frac{1}{J _{n}}$ 得到。

如果我们不执着于明确给出 $(1.1. B)$ 当中这个下确界，而是取特殊的首1多项式 $P (x)$ 使得其 $L^{1}$ 范数尽可能小，我们应该怎么做？

接下来我们通过两种不同角度，论证，满足”问题0”中的下界估计，这样的n次首1多项式，其实很多！

我们不妨来想一想，使得 $\int_{0}^{1} ∣ P (x) ∣ d x$ 最小的n次首1多项式，不应该长什么样子？

首先， $P$ 应该在 $(0, 1)$ 中应该存在零点吗？

此处我们想要证明，如果 $P$ 在 $(0, 1)$ 中不存在零点，不妨假设 $P (x) > 0, \forall x \in (0, 1)$ 那么我们可以通过给 $P$ 施加一个小的扰动的方式把多项式变成 $P_{ε} := P - ε$ 从而扰动后 $∣∣ P_{ε} ∣ ∣_{L^{1}} < ∣∣ P ∣ ∣_{L^{1}}$ 从而证明扰动后的n次首1多项式的 $L^{1}$ 更小，从而否定 $P$ 是最小候选的可能。

要实现这个目的，我们无非就是证明 $\int_{0}^{1} ∣ P - ε ∣ < \int_{0}^{1} ∣ P ∣$ 如果 $P$ 在 $(0, 1)$ 上存在正的下界，那么只要 $ε > 0$ 足够小，就可以把上面积分中的绝对值去掉。但是考虑到类似于 $x^{n}$ 或者 $x (x - 1)^{n - 1}$ 这种零点取在 ${0, 1}$ 端点的情况，可能会出现 $in f_{x \in (0, 1)} P (x) = 0$ 的情况。

不过我们可以想办法把这端点部分“挖掉”一块很小的区域，并证明这些区域并不会影响最终的结论。具体操作如下：

令 $A_{ε} := {x \in [0, 1] : P (x) \leq ε}$ 于是 $∣∣ P - ε ∣ ∣_{L^{1}} = \int_{A_{ε}} ∣ P - ε ∣ + \int_{[0, 1] ∖ A_{ε}} ∣ P - ε ∣ = \int_{A_{ε}} (- P + ε) + \int_{[0, 1] ∖ A_{ε}} (P - ε) = ∣∣ P ∣ ∣_{L^{1}} - ε + 2 ε ∣ A_{ε} ∣$ 因为 $ε ↓ 0$ 的时候 $A_{ε} ↓ {x : P (x) = 0} \subseteq {0, 1}$ ，从而 $∣ A_{ε} ∣ \to 0$ 于是只要 $ε$ 足够小，就可以使得 $2∣ A_{ε} ∣ < \frac{1}{2}$ 从而 $∣∣ P - ε ∣ ∣_{L^{1}} < ∣∣ P ∣ ∣_{L^{1}} - \frac{ε}{2} < ∣∣ P ∣ ∣_{L^{1}}$ 从而证明了，如果 $P$ 在 $(0, 1)$ 上没有零点，那么 $P$ 必然不可能是最优的多项式。

$P$ 在 $(0, 1)$ 上应该变号吗？变号的次数是越多越好，还是越少越好？

命题1.1.1

若 $P$ 是达到 $J_{n}$ 的 $n$ 次首1多项式，即 $∥ P ∥_{L^{1} ([0, 1])} = J_{n}$ 那么 $P$ 在 $(0, 1)$ 中必须有 $n$ 个不同的根。

也即是说， $P$ 不仅要在 $(0, 1)$ 当中变号，而且应该变号 $n$ 次。

设 $ξ_{1} < ξ_{2} < \dots < ξ_{m}$ 是 $P$ 在 $(0, 1)$ 中所有的奇重根，也就是所有变号点。假设 $m < n$ ,定义 $Q (x) := σ \prod_{j = 1}^{m} (x - ξ_{j}),$ 其中 $σ = \pm 1$ 选成使得 $Q$ 与 $P$ 在第一个区间上同号。

这样定义以后, $P$ 与 $Q$ 会在每个由 $ξ_{1}, \dots, ξ_{m}$ 划分出来的区间上同号。因为它们都只会在这些点处变号，而且变号方式同步。

又由于 $de g Q = m < n$ ,所以对任意 $ε > 0$ ， $P_{ε} := P - εQ$ 仍然是一个 $n$ 次首1多项式。接下来我们要证明，只要 $ε$ 足够小，那么就有 $∣∣ P_{ε} ∣ ∣_{L^{1}} < ∣∣ P ∣ ∣_{L^{1}}$ 从而 $P$ 必然不是最优的多项式，从而命题成立。

如果在 $I \subset (0, 1)$ 上， $P, Q, P_{ε}$ 在此区间上不变号，比如都严格大于0，那么 $\int_{I} ∣ P_{ε} ∣ = \int_{I} ∣ P ∣ - ε \int ∣ Q ∣ < \int_{I} ∣ P ∣$ 于是我们想到，是否可以令 $I = (ξ_{i - 1}, ξ_{i})$ 从而把 $(0, 1)$ 用 $ξ_{1}, \dots, ξ_{m}$ 进行拆分，然后在每一段上实现上面的不等式，似乎就能证明 $P, P_{ε}$ 的范数的关系。但是 $(ξ_{i - 1}, ξ_{i})$ 上 $P, Q, P_{ε}$ 可能并不同号。因为虽然 $P, Q$ 在 $(ξ_{i - 1}, ξ_{i})$ 不变号，但是可能对任意 $ε > 0$ 多项式 $P_{ε}$ 都会变号。

比如，如果 $P (x) := (x - 1/2)^{2}$ 它在 $(0, 1)$ 当中完全不变号，因此我们可以考虑 $Q (x) \equiv 1$ 。从而 $P_{ε} (x) := (x - 1/2)^{2} - ε$ 是有可能在 $(0, 1)$ 当中变号的。

此处的想法

原来那种“在每个分段上直接比较 $∣ P_{ε} ∣$ 与 $∣ P ∣$ ”的做法，真正的障碍在于：
我们虽然只把 $P$ 的变号点 $ξ_{1}, \dots, ξ_{m}$ 放进了 $Q (x) := σ \prod_{j = 1}^{m} (x - ξ_{j})$ 从而保证 $P, Q$ 在每个区间 $(ξ_{i - 1}, ξ_{i})$ 上同号，但这并不意味着 $P_{ε} := P - εQ$ 在这些区间内仍然保持原来的符号。

问题出在，在某个区间 $(ξ_{i - 1}, ξ_{i})$ 内，除了变号点以外， $P$ 还可能有不变号的零点，也就是偶重根。若 $a$ 是这样的一个点，那么在 $a$ 附近有 $P (x) \approx 0$ ，而 $Q (x)$ 一般并不会同时变得很小。因此即使 $ε > 0$ 很小， $P (x) - εQ (x)$ 仍然可能在 $a$ 附近改变符号，甚至长出新的零点。

于是即使 $P$ 与 $Q$ 在每个大区间上同号，我们也不能直接断言 $∣ P - εQ ∣ = ∣ P ∣ - ε ∣ Q ∣$

不过紧接着可以想到，这些麻烦只会出现在 $P$ 的零点附近，而零点总共只有有限个。因此我们可以把这些零点附近的小邻域单独挖出来，视为“坏区域”；在其余远离零点的部分， $P$ 有正下界，此时足够小的扰动不会改变符号，于是就可以精确比较 $∣ P_{ε} ∣$ 与 $∣ P ∣$ 。
至于被挖掉的那些小邻域，由于它们的总长度可以取得任意小，只需再做一个粗略的误差估计，就可以证明它们不会影响最终结论。

于是令 $Z$ 为 $P$ 在 $[0, 1]$ 内的全部零点。取很小的 $δ > 0$ ，令

U_{δ} := a \in Z ⋃ ((a - δ, a + δ) \cap [0, 1]), K_{δ} := [0, 1] ∖ U_{δ}

$U_{δ}$ 是零点附近的小邻域，是“坏区域”；
$K_{δ}$ 是远离零点的部分，是“好区域”。

由于 $P$ 在紧集 $K_{δ}$ 上连续且没有零点，所以存在常数 $η_{δ} > 0$ ，使得 $∣ P (x) ∣ \geq η_{δ}, x \in K_{δ}$ 再令 $M := ∥ Q ∥_{L^{\infty} ([0, 1])}$ 那么只要取 $ε > 0$ 足够小，使 $εM < η_{δ}$ 就可以保证在 $K_{δ}$ 上， $P - εQ$ 与 $P$ 同号。又因为 $P$ 与 $Q$ 本来就在 $K_{δ}$ 上同号，于是 $∣ P - εQ ∣ = ∣ P ∣ - ε ∣ Q ∣, x \in K_{δ}$ 从而

\int_{K_{δ}} ∣ P - εQ ∣ = \int_{K_{δ}} ∣ P ∣ - ε \int_{K_{δ}} ∣ Q ∣

另一方面，在 $U_{δ}$ 上我们只用三角不等式粗略估计： $∣ P - εQ ∣ \leq ∣ P ∣ + ε ∣ Q ∣$ 因此

\int_{U_{δ}} ∣ P - εQ ∣ \leq \int_{U_{δ}} ∣ P ∣ + ε \int_{U_{δ}} ∣ Q ∣

由 $[0, 1] = K_{δ} \cup U_{δ}$ 可得

∥ P - εQ ∥_{L^{1}} \leq ∥ P ∥_{L^{1}} - ε \int_{K_{δ}} ∣ Q ∣ + ε \int_{U_{δ}} ∣ Q ∣

再写成

∥ P - εQ ∥_{L^{1}} \leq ∥ P ∥_{L^{1}} - ε ∥ Q ∥_{L^{1}} + 2 ε \int_{U_{δ}} ∣ Q ∣

因为 $Q \neq \equiv 0$ ，所以 $∥ Q ∥_{L^{1}} > 0$ 又因为 $U_{δ}$ 的长度可以取得任意小，所以先取 $δ$ 足够小，使 $2 \int_{U_{δ}} ∣ Q ∣ < ∥ Q ∥_{L^{1}}$ 于是再取 $ε > 0$ 足够小，就得到 $∥ P - εQ ∥_{L^{1}} < ∥ P ∥_{L^{1}}$ 这与 $P$ 的极小性矛盾。因此假设不成立，必有 $m = n$

所以我们知道，一般对该问题解答中，构造出来的 $n$ 个重根的情形，绝对不可能是最优结果。

例子1.1.2

$P$ 是 $V_{n}$ 当中的首1多项式，并且 $P$ 在 $(0, 1)$ 当中具有 $n$ 个重根： $∣∣ P ∣ ∣_{L^{1}} = \int_{0}^{1} ∣ x - h ∣^{n} d x \geq \int_{0}^{1} ∣ x - 1/2 ∣^{n} d x = \int_{0}^{1/2} * + \int_{1/2}^{1} * = 2 \int_{0}^{1/2} (1/2 - x)^{n} = \frac{1}{( n + 1 ) 2 ^{n}}$

这个例子告诉我们 $J_{n} \leq \frac{1}{( n + 1 ) 2 ^{n}}$

此外下面这个例子可以告诉我们，其实零点集中在一起的构造是很平凡的构造。

例子1.1.3

令 $X_{1}, \dots, X_{n}$ 独立同分布 $U (0, 1)$ ，定义n阶首1，在 $(0, 1)$ 中有 $n$ 个随机的根的多项式 $P (x) := \prod_{j = 1}^{n} (x - X_{j})$ 我们希望求 $P$ 在 $[0, 1]$ 上 $L^{1}$ 范数的期望 $E ∣∣ P ∣ ∣_{L^{1}}$ 。

借助Fubini/Tonelli定理，并且借助 $X_{j}$ 之间相互独立的假设，我们有 $E ∣∣ P ∣ ∣_{L^{1}} = \int_{0}^{1} E (j = 1 \prod n ∣ x - X_{j} ∣) d x = \int_{0}^{1} j = 1 \prod n E ∣ x - X_{j} ∣ d x = \int_{0}^{1} (E ∣ x - X_{1} ∣)^{n} d x = \int_{0}^{1} (x^{2} - x + \frac{1}{2})^{n} d x = \int_{0}^{1} (x^{2} - x + \frac{1}{2})^{n} d x = \int_{0}^{1} [(x - 1/2)^{2} + \frac{1}{4}]^{n} d x = \int_{- 1/2}^{1/2} (t^{2} + \frac{1}{4})^{n} d t = \frac{1}{4 ^{n}} \int_{0}^{1} (u^{2} + 1)^{n} d u$ 借助Laplace方法我们可以证明 $E ∣∣ P ∣ ∣_{L^{1}} \sim \frac{1}{n 2 ^{n}}$

$P$ 在 $(0, 1)$ 中的 $n$ 个不同的根，应该如何分布才能尽可能取到最优？

我们先考虑一个简单的情形，比如“等距分布”如何？

例子1.1.4

$P$ 是 $V_{n}$ 当中的首1多项式，并且 $P$ 在 $(0, 1)$ 当中具有 $n$ 个不同的根，并且根等距分布：

$P$ 在 $(0, 1)$ 当中有 $n$ 个不同的根，这些根可以表示为 $x_{k} := \frac{k}{n + 1}, k = 1, \dots, n$ 从而依照分段求积分，并令 $h = \frac{1}{n + 1}$ 于是

∣∣ P ∣ ∣_{L^{1}} = \int_{0}^{1} k = 1 \prod n ∣ x - x_{k} ∣ d x = h^{n + 1} \int_{0}^{n + 1} k = 1 \prod n ∣ y - k ∣ d y = \frac{K _{n}}{( n + 1 ) ^{n + 1}} (3)

接下来我们证明 $K_{n} < n!, \forall n \geq 2$ 。

令 $Q_{n} (y) := \prod_{k = 1}^{n} (y - k)$ 于是 $K_{n} = \sum_{m = 0}^{n} \int_{m}^{m + 1} ∣ Q_{n} (y) ∣ d y$ 接下来我们来拆除绝对值。对每个 $m$ ，令 $y = m + u$ 其中 $u \in (0, 1)$ 于是 $Q (m + u) = \prod_{k = 1}^{n} (m + u - k)$

$k \leq m$ 的时候： $m + u - k = u + (m - k)$ ，相当于 $u, u + 1, \dots, u + m - 1$ 以此相乘，并且每一个都是非负实数。

$k \geq m + 1$ 的时候： $m + u - k = (m + u) - k < 0$ 因此绝对值依次分别为 $1 - u, 2 - u, \dots, n - m - u$ 一共是 $n - m$ 项。

因此 $∣ Q (m + u) ∣ = (\prod_{j = 0}^{m - 1} (u + j)) (\prod_{j = 0}^{n - m - 1} (1 - u + j))$ 定义上升阶乘（rising factorial）: $u^{(m)} := \prod_{j = 0}^{m - 1} (u + j), (1 - u)^{(n - m)} = \prod_{j = 0}^{n - m - 1} (1 - u + j)$ 于是 $K_{n} = \sum_{m = 0}^{n} \int_{0}^{1} u^{(m)} (1 - u)^{(n - m)} d u = \int_{0}^{1} F_{n} (u) d u$ 其中 $F_{n} (u) := \sum_{m = 0}^{n} u^{(m)} (1 - u)^{(n - m)}$ 。

由于 $u^{(m)} (1 - u)^{(n - m)}$ 非负，以及恒等式 $\sum_{m = 0}^{n} (m n) u^{(m)} (1 - u)^{(n - m)} = n!$ 从而当 $n \geq 2$ 的时候 $F_{n} (u) < \sum_{m = 0}^{n} (m n) u^{(m)} (1 - u)^{(n - m)} = n!$ 于是根据 $(3)$ 我们得到在 $n \geq 2$ 的时候 $∣∣ P ∣ ∣_{L^{1}} = \frac{K _{n}}{( n + 1 ) ^{n + 1}} < \frac{n !}{( n + 1 ) ^{n + 1}} < \frac{1}{( n + 1 ) 2 ^{n}}$

这个例子可以知道 $J_{n} \leq \frac{n !}{( n + 1 ) ^{n + 1}}$ 借助Stirling公式（参考Stirling渐近公式及不等式）这个上界的渐近展开为 $\frac{n !}{( n + 1 ) ^{n + 1}} \sim \frac{2 π n}{e ^{n}} \cdot \frac{n ^{n}}{( n + 1 ) ^{n + 1}} \sim \frac{2 π}{n e ^{n}} \cdot (\frac{n}{n + 1})^{n} = \frac{2 π}{n e ^{n}} \cdot (e^{- 1} + o (1)) ≍ \frac{1}{n ^{1/2} e ^{n}}$ 从衰减速度上来说，这要比之前的例子提供的 $\frac{1}{n 2 ^{n}}$ 要快得多。因此 $n$ 个零点均匀分布的情况下多项式 $L^{1}$ 范数要比 $n$ 个点集中在一起要小得多。

最优的情况：

命题1.1.5：Korkin-Zolotarev(1873)

令 $P (x) := 4^{- n} \cdot U_{n} (2 x - 1)$ ，其中 $U (x)$ 为 $[- 1, 1]$ 定义的n阶第二类Chebyshev多项式，那么 $J_{n} = ∣∣ P ∣ ∣_{L^{1}} = \frac{1}{4 ^{n}}$

也就是说，根的分布符合靠近端点处密集，在中间稀疏的方式可以使得多项式的 $L^{1}$ 范数更小。

1.2 从L2范数的下界角度考虑

想法1.2.1

虽然我们的目标是 $L^{\infty}$ 的下界，但是如果我们把 $f$ 的矩的约束理解为， $f$ 在某个多项式组成的 $L^{2}$ 空间的单位正交基下坐标的部分信息。那么其实 $L^{2}$ 范数的下界才是由约束信息能得到的最直接的结果。

类似的案例参考2.调和分析的思路。

至于两个范数的联系，好在 $[0, 1]$ 上建立的是单位测度，所以 $∣∣ f ∣ ∣_{L^{\infty}} \geq ∣∣ f ∣ ∣_{L^{2} ([0, 1])}$ 的关系表明，后者的下界就是前者的下界。至于说 $L^{2}$ 范数的下界如何得到，想法可以参考在Hilbert空间当中建立坐标系从而简化问题，具体经验参考^56572b的做法。

利用这种思路我们可以证明：

命题1.2.2

设 $f \in L^{\infty} ([0, 1] \to R)$ 满足 $\int_{0}^{1} x^{k} f (x) d x = 0, k = 0, 1, \dots, n - 1, \int_{0}^{1} x^{n} f (x) d x = 1.$ 那么 $∣∣ f ∣ ∣_{L^{2} ([0, 1])} \geq 2 n + 1 (n 2 n) .$ 从而 $∣∣ f ∣ ∣_{L^{\infty} ([0, 1])} \geq 2 n + 1 (n 2 n) .$

令 $L_{k} (t)$ 为定义在 $[- 1, 1]$ 上的 Legendre 多项式，并定义 $p_{k} (x) := 2 k + 1 L_{k} (2 x - 1), x \in [0, 1]$ 于是 ${p_{k}}_{k \geq 0}$ 是 $L^{2} ([0, 1])$ 中的一组单位正交基。

与已知函数与幂函数的内积估计函数L2范数下界情况类似，选用正交多项式作 $L^{2}$ 空间的基，是为了更好利用上内积 $⟨ f, x^{k} ⟩$ 的信息。

由 Bessel 不等式， $∣∣ f ∣ ∣_{L^{2} ([0, 1])}^{2} \geq \sum_{k \geq 0} ∣ ⟨ f, p_{k} ⟩ ∣^{2} \geq ∣ ⟨ f, p_{n} ⟩ ∣^{2}$ 令 $p_{n} (x) := \sum_{i = 0}^{n} a_{i} x^{i}$ ,再根据“问题0”中内积的信息， $⟨ p_{n}, f ⟩ = \sum_{i = 0}^{n} a_{i} ⟨ x^{i}, f ⟩ = a_{n}$ 于是由Bessel不等式可以得到 $∣∣ f ∣ ∣_{L^{2} ([0, 1])}^{2} \geq ∣ a_{n} ∣^{2}$ 。再根据Legendre多项式的性质 $p_{n}$ 的最高次项系数 $a_{n}$ 为 $2 n + 1 (n 2 n)$ 。于是 $∣∣ f ∣ ∣_{L^{2} ([0, 1])} \geq ∣ a_{n} ∣ = 2 n + 1 (n 2 n)$ 通过Stirling公式得到这个下界的渐近结果 $2 n + 1 (n 2 n) \sim \frac{2}{π} 4^{n} ≫ 2^{n} (n + 1)$ 也就是说对于足够大的 $n$ ，以上思路得到的关于 $∣∣ f ∣ ∣_{L^{\infty}}$ 的下界比“问题0”中要求的更紧。此外，更进一步可以证明，至少当 $n \geq 2$ 时， $2 n + 1 (n 2 n) \geq 2^{n} (n + 1)$

此处 $p_{n}$ 的最高次项系数

笔记目录

1.从多个角度来说明，为什么原问题中的估计很松？

1.1 从寻找L1范数尽可能小的n次首1多项式入手

1.2 从L2范数的下界角度考虑