Chap 8: Approximation Theory⚓︎

Discrete Least Square Approximation⚓︎

目标：确定一个多项式 \(P_n(x) = a_0 + a_1 x + \dots a_n x^n\)，用于近似表示一组数据 \(\{(x_i, y_i)\ |\ i = 1, 2, \dots, m\}\)，使得最小二乘误差 \(E_2 = \sum\limits_{i=1}^m [P_N(x_i) - y_i]^2\) 最小化，其中 \(n \ll m\)

关键：\(E_2\) 实际上是一个关于 \(a_0, a_1, \dots, a_n\) 的函数，也就是说 \(E_2(a_0, a_1, \dots, a_n) = \sum\limits_{i=1}^m [a_0 + a_1 x_i + \dots + a_n x_i^n - y_i]^2\)。要想让 \(E_2\) 最小化，必要条件是 \(\dfrac{\partial E_2}{\partial a_k} = 0, k = 0, \dots, n\)

令 \(b_k = \sum\limits_{i=1}^m x_i^k, c_k = \sum\limits_{i=1}^m y_i x_i^k\)，那么：

题目解答法 1 法 2

令 \(y \approx P(x) = \dfrac{x}{ax + b}\)，寻找 \(a, b\)，使得 \(E_2(a, b) = \sum\limits_{i=1}^m \Big(\dfrac{x_i}{ax_i + b} - y_i\Big)\)^2 最小化。

线性化(linearization)：令 \(Y = \dfrac{1}{y}, X = \dfrac{1}{x}\)，那么 \(Y \approx a + b X\) 就是一个线性问题了。

将 \((x_i, y_i)\) 转换为 \((X_i, Y_i)\)，\(a, b\) 就能被解出来了。

令 \(y \approx P(x) = ae^{-\frac{b}{x}}\)，不难发现 \(\ln y \approx \ln a - \dfrac{b}{x}\)

线性化：令 \(Y = \ln y, X = \dfrac{1}{x}, A = \ln a, B = -b\)，得到 \(Y \approx A + BX\) 这样一个线性问题。

将 \((x_i, y_i)\) 转换为 \((X_i, Y_i)\)，\(a, b\) 就能被解出来了（\(a = e^A, b = -B, P(x) = ae^{-\frac{b}{x}}\)）

Orthorgonal Polynomials and Least Squares Approximation⚓︎

• 离散版本：给定 \(x_1, \dots, x_m;\ y_1, \dots, y_m\)，找到更简单的函数 \(P(x) \approx f(x)\)，使得 \(E = \sum\limits_{i=1}^m |P(x_i) - y_i|^2\) 最小化。
• 连续版本：离散版本：给定在 \([a, b]\) 上的函数 \(f(x)\)，找到更简单的函数 \(P(x) \approx f(x)\)，使得 \(E = \int_a^b [P(x) - f(x)]^2 dx\) 最小化。

其他多项式：

• \(\{\varphi_j(x) = \cos jx\}, \{\psi_j(x) = \sin jx\} \Rightarrow \{\varphi_j(x), \psi_j(x)\}\) 得到的是三角多项式(trigonometric polynomial)
• \(\{\varphi_j(x) = e^{kjx}, k_i \ne k_j\}\) 得到的是指数多项式(exponential polynomial)

对于 \((f, g) = \begin{cases}\sum\limits_{i=1}^m w_i f(x_i) g(x_i) \\ \int_a^b w(x) f(x) g(x) dx\end{cases}\)，可以证明它表示的是一个内积(inner product)，且 \(\|f\| = \sqrt{(f, f)}\) 是一个范数。

因此一般的最小二乘近似问题可以被转换为：寻找一个广义多项式 \(P(x)\)，使得 \(E = (P - y, P - y) = \| P - y \|^2\) 最小化。

令 \(P(x) = a_0 \varphi_0(x) + a_1 \varphi_1(x) + \dots + a_n \varphi_n(x)\)，然后与求解离散问题类似（？）：\(\dfrac{\partial E}{\partial a_k} = 0 \Rightarrow \sum\limits_{j=0}^n (\varphi_k, \varphi_j) a_j = (\varphi_k, f), k = 0, \dots, n\)，也就是说：

例子

题目解答

使用 \(y = a_0 + a_1 x + a_2 x^2\) 近似点集 \(\{(1, 4), (2, 10), (3, 18), (4, 26)\}\)

\(\varphi_0(x) = 1, \varphi_1(x) = x, \varphi_2(x) = x^2\)，可以计算出：

\(\|B\|_{\infty} = 484, \|B^{-1}\|_{\infty} = \dfrac{63}{4} \Rightarrow K(B) = 7623\)

下面考虑构造正交多项式(orthogonal polynomials)。

例子

题目解答

（和之前基本一样的）使用 \(y = c_0 + c_1 x + c_2 x^2, w \equiv 1\) 近似点集 \(\{(1, 4), (2, 10), (3, 18), (4, 26)\}\)

首先构造正交多项式 \(\varphi_0(x), \varphi_1(x), \varphi_2(x)\)，令 \(y = a_0 \varphi_0(x) + a_1 \varphi_1(x) + a_2 \varphi_2(x)\)（\(a_k = \dfrac{(\varphi_k, y)}{\varphi_k, \varphi_k}\)）。接下来就计算出这些值：

最终解得 \(y = \dfrac{1}{2}x^2 + \dfrac{49}{10}x - \dfrac{3}{2}\)

Chebyshev Polynomials and Economization of Power Series⚓︎

一般的最小二乘近似问题是要找到一个广义多项式 \(P(x)\)，使得 \(E = (P - y, P - y) = \|P - y\|^2\) 最小化。

现在的目标是最小化 \(\|P - y\|_{\infty}\)——极小化极大问题(minimax problem)。

Goals⚓︎

目标 1.0：找到 \(n\) 阶多项式 \(P_n(x)\) 使得 \(\|P_n - f\|_{\infty}\) 最小化。

定义：如果 \(P(x_0) - f(x_0) = \pm \|P - f\|_{\infty}\)，那么此时 \(x_0\) 被称为 \((\pm)\) 偏差点(deviation point)。

从任意地方构造出多项式并不容易，但我们能够检验多项式的一些特征：

• 如果 \(f \in C[a, b]\) 且 \(f\) 不是一个 \(n\) 阶多项式，那么存在一个唯一的多项式 \(P_n(x)\)，使得 \(\|P_n - f\|_{\infty}\) 最小化
• \(P_n(x)\) 存在，且必须同时有正负偏差点
• 切比雪夫定理(Chebyshev Theorem)：\(P_n(x)\) 最小化 \(\|P_n - f\|_{\infty}\ \Leftrightarrow P_n(x)\) 至少有 \(n+2\) 个关于 \(f\) 的正负偏差点。也就是说，存在一组点 \(a \le t_1 < \dots < t_{n+2} \le b\) 使得 \(P_n(t_k) - f(t_k) = \pm(-1)^k \|P_n - f\|_{\infty}\)。集合 \(\{t_k\}\) 被称为切比雪夫交替序列(Chebyshev alternating sequence)。

其中 \(P_n(x)\) 是 \(f(x)\) 的插值多项式。

目标 2.0：确定插值点 \(\{x_0, \dots, x_n\}\) 使得 \(P_n(x)\) 最小化余项 \(|P_n(x) - f(x)| = |R_n(x)| = \Big|\dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod\limits_{i=0}^n (x - x_i)\Big|\)

目标 2.1：找到 \(\{x_1, \dots, x_n\}\) 使得 \(\|w_n\|_{\infty}\) 在 \([-1, 1]\) 最小化，其中 \(w_n(x) = \prod\limits_{i=1}^n (x - x_i)\)

注意到 \(w_n(x) = x^n - P_{n-1}(x)\)，问题就变成了：

目标 3.0：找到多项式 \(P_{n-1}(x)\)，使得 \(\|x^n - P_{n-1}(x)\|_{\infty}\) 在 \([-1, 1]\) 上最小。

根据切比雪夫定理，我们知道 \(P_{n-1}(x)\) 有 \(n+1\) 个关于 \(x^n\) 个偏差点，也就是说 \(w_n(x)\) 在 \(n+1\) 个点上交替获得最大值和最小值。

Chebyshev Polynomials⚓︎

考虑 \(\cos (n \theta)\) 在 \([0, \pi]\) 上的 \(n+1\) 个极值。

令 \(x = \cos (\theta)\)，那么 \(x \in [-1, 1]\)。我们称 \(T_n(x) = \cos (n\theta) = \cos (n \cdot \text{arc} \cos x)\) 为切比雪夫多项式(Chebyshev polonomial)。

• \(T_n(x)\) 假设在 \(t_k = \cos \Big(\dfrac{k}{n} \pi\Big) (k = 0, 1, \dots, n)\) 上，在最大值 1 和最小值 -1 之间交替变换，也就是说 \(T_n(t_k) = (-1)^k \|T_n(x)\|_{\infty}\)
• \(T_n(x)\) 有 \(n\) 个根 \(x_k = \cos \Big(\dfrac{2k - 1}{2n} \pi \Big)(k = 1, \dots, n)\)
• \(T_n(x)\) 有递推关系式：\(T_0(x) = 1, T_1(x) = x, T_{n+1}(x) = 2x T_n(x) - T_{n-1}(x)\)
  • \(T_n(x)\) 是一个有 \(2^{n-1}\) 个系数的 \(n\) 阶多项式
• \(\{T_0(x), T_1(x), \dots\}\) 在 \([-1, 1]\) 上关于权重函数 \(w(x) = \dfrac{1}{\sqrt{1 - x^2}}\) 上正交，也就是说 \((T_n, T_m) = \int_{-1}^1 \dfrac{T_n(x) T_m(x)}{\sqrt{1-x^2}} dx = \begin{cases}0 & n \ne m \\ \pi & n = m = 0 \\ \dfrac{\pi}{2} & n = m \ne 0\end{cases}\)

回到之前介绍的目标：

• 目标 3.0：找到多项式 \(P_{n-1}(x)\)，使得 \(\|x^n - P_{n-1}(x)\|_{\infty}\) 在 \([-1, 1]\) 上最小。
  • 此时 \(w_n(x) = x^n - P_{n-1}(x) = \dfrac{T_n(x)}{2^{n-1}}\)
• 目标 2.1：找到 \(\{x_1, \dots, x_n\}\) 使得 \(\|w_n\|_{\infty}\) 在 \([-1, 1]\) 最小化，其中 \(w_n(x) = \prod\limits_{i=1}^n (x - x_i)\)
  • 此时 \(\min\limits_{w_n \in \widetilde{\Pi}_n} \|w_n\|_{\infty} = \Big\|\dfrac{1}{2^{n-1}} T_n(x)\Big\|_{\infty} = \dfrac{1}{2^{n-1}}\)。其中：\(\widetilde{\Pi}_n\) 是 \(n\) 阶的首一多项式 (monic polynomial)，\(\{x_1, \dots, x_n\}\) 是 \(T_n(x)\) 的 \(n\) 个根
• 目标 2.0：确定插值点 \(\{x_0, \dots, x_n\}\) 使得 \(P_n(x)\) 最小化余项 \(|P_n(x) - f(x)| = |R_n(x)| = \Big|\dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod\limits_{i=0}^n (x - x_i)\Big|\)
  • 取 \(T_{n+1}(x)\) 上的 \(n+1\) 个根作为插值点 \(\{x_0, \dots, x_n\}\)，然后关于 \(f(x)\) 的插值多项式 \(P_n(x)\) 假设绝对误差的最小上界为 \(\dfrac{M}{2^n (n+1)!}\)

Economization of Power Series⚓︎

目标：给定 \(P_n(x) \approx f(x)\)，幂级数经济化(economization) 的目标是在确保精度损失最小的情况下，降低多项式的次数。

考虑一个任意的 \(n\) 阶多项式 \(P_n(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0\)，对应的多项式 \(P_{n-1}(x)\) 通过移除 \(n\) 阶多项式 \(Q_n(x)\)（\(x^n\) 项的系数为 \(a_n\)）得到。那么 \(\max\limits_{[-1, 1]} |f(x) - P_{n-1}(x)| \le \max\limits_{[-1, 1]} |f(x) - P_n(x)| + \max\limits_{[-1, 1]} |Q_n(x)|\)，而 \(Q_n(x)\) 能够反映精度的损失。

为了最小化精度损失，\(Q_n(x)\) 必须为 \(a_n \times \dfrac{T_n(x)}{2^{n-1}}\)（？）

例子

题目解答

已知 \(f(x) = e^x\) 在 \([-1, 1]\) 上的 4 阶泰勒多项式为 \(P_4 = 1 + x + \dfrac{x^2}{2} + \dfrac{x^3}{6} + \dfrac{x^4}{24}\)。它的截断误差的上界为 \(|R_4(x)| \le \dfrac{e}{5!} |x^5| \approx 0.023\)。请将这个近似多项式的次数降至 2。

评论区