Approximation Theory and Method ch7

~~part 1, part 2, part 3, ch7, 命名乱了——致敬微软~~

... as the sign of \(p(x)\). It follows that \(p^{*}\) is a best minimax approximation from \(\mathscr{A}\) to \(f\) if there is no function \(p\) in \(\mathscr{A}\) that satisfies the condition

\[\left[f(x)-p^{*}(x)\right] p(x)>0, \quad x \in \mathscr{Z}_{\mathrm{M}}\quad \text {. (7.6) } \]

Because of the way in which the exchange algorithm works, we generalize the problem of minimizing \(\|f-p\|_{\infty}\), to the problem of minimizing the expression

\[\max _{x \in \mathscr{X}}|f(x)-p(x)|, \quad p \in \mathscr{A}\quad \text{(7.7)} \]

where \(\mathscr{Z}\) is any closed subset of \([a, b]\), which may be \([a, b]\) itself, but in the exchange algorithm the set \(\mathscr{Z}\) is composed of a finite number of points. The next theorem allows \(\mathscr{Z}\) to be general.

Theorem 7.1 Let \(\mathscr{A}\) be a linear subspace of \(\mathscr{C}[a, b]\), let \(f\) be any function in \(\mathscr{C}[a, b]\), let \(\mathscr{Z}\) be any closed subset of \([a, b]\), let \(p^{*}\) be any element of \(\mathscr{A}\), and let \(\mathscr{Z}_{\mathrm{M}}\) be the set of points of \(\mathscr{Z}\) at which the error \(\left\{\left|f(x)-p^{*}(x)\right| ; x \in\right.\) \(\mathscr{Z}\) } takes its maximum value. Then \(p^{*}\) is an element of \(\mathscr{A}\) that minimizes expression (7.7) if and only if there is no function \(p\) in \(\mathscr{A}\) that satisfies condition (7.6).

不严谨说，如果能找到一个 \(p(x) \in \mathscr A\), 使得 \(p(x)\) 和 \(f(x)-p^{*}(x)\) 符号一样，那么这个 \(p(x)\) 肯定可以让 \(\|f-p\|_{\infty}\) 更小——通过找一个比较合适的 \(\theta\)，这个 \(\theta\) 要足够小——小到在每一个点 \(x \in \mathscr Z_M\) 处都不会减爆. 因为可以任意小，所以这样的 \(\theta\) 肯定存在.

\[\max _{x \in \mathscr{I}}\left|e^{*}(x)-\theta p(x)\right|<\max _{x \in \mathscr{I}}\left|e^{*}(x)\right| \]

Haar Condition

(1) If an element of \(\mathscr{P}_{n}\) has more than \(n\) zeros, then it is identically zero.

大概就是说，最高次数是 \(n\) 的多项式最多有 \(n\) 个零点——

或者有无穷多个零点，处处都是 \(0\).

(2) Let \(\left\{\zeta_{j} ; j=1,2, \ldots, k\right\}\) be any set of distinct points in the open interval \((a, b)\), where \(k \leqslant n\). There exists an element of \(\mathscr{P}_{n}\) that changes sign at these points, and that has no other zeros. Moreover, there is a function in \(\mathscr{P}_{n}\) that has no zeros in \([a, b]\). The following two properties of polynomials are required later:

给出了多项式的存在性，任意给定一些点，肯定有一个多项式在这些地方变号，只要变号的次数小于等于 \(n\).

(3) If a function in \(\mathscr{P}_{n}\), that is not identically zero, has \(j\) zeros, and if \(k\) of these zeros are interior points of \([a, b]\) at which the function does not change sign, then the number \((j+k)\) is not greater than \(n\).

\[p(x) = \prod (x - x_i)^{n_i} \]

不变号的零点肯定是多项式里某些要素是偶数次方，所以至少贡献两个 degree.

(4) Let \(\left\{\xi_{j} ; j=0,1, \ldots, n\right\}\) be any set of distinct points in \([a, b]\), and let \(\left\{\phi_{i} ; i=0,1, \ldots, n\right\}\) be any basis of \(\mathscr{P}_{n}\). Then the \((n+1) \times\) \((n+1)\) matrix whose elements have the values \(\left\{\phi_{i}\left(\xi_{j}\right)\right.\); \(i=0,1, \ldots, n ; j=0,1, \ldots, n\}\) is non-singular.

大概就是任意一些不一样的点换基换到多项式空间，都是不会丢失维数的. (?) 忘了x

Haar Condition 就是多项式空间满足的一些性质，在下面有关的证明里面实际上我们只用到多项式的一部分性质，有这些性质就够用了. 于是可以做一些拓展，把这些一部分的性质拿出来，毕竟我们只要用这么多东西，那其他满足这些东西的线性空间也是适用的.

An \((n+1)\)-dimensional linear subspace \(\mathscr{A}\) of \(\mathscr{C}[a, b]\) is said to satisfy the 'Haar condition' if these four statements remain true when \(\mathscr{P}_{n}\) is replaced by the set \(\mathscr{A}\). Equivalently, any basis of \(\mathscr{A}\) is called a 'Chebyshev set'.

It is proved that properties \((\mathbf{1}),(3)\) and (4) are equivalent, and that these properties imply condition (2).

这里相关的证明，一般就看 \((1)\) 就行了.

Theorem 7.2 (Characterization Theorem)

Let \(\mathscr{A}\) be an \((n+1)\)-dimensional linear subspace of \(\mathscr{C}[a, b]\) that satisfies the Haar condition, and let \(f\) be any function in \(\mathscr{C}[a, b]\). Then \(p^{*}\) is the best minimax approximation from \(\mathscr{A}\) to \(f\), if and only if there exist \((n+2)\) points \(\left\{\xi_{i}^{*} ; i=0,1, \ldots, n+1\right\}\), such that the conditions

\[\begin{aligned} & a \leqslant \xi_{0}^{*}<\xi_{1}^{*}<\ldots<\xi_{n+1}^{*} \leqslant b, \\ & \left|f\left(\xi_{i}^{*}\right)-p^{*}\left(\xi_{i}^{*}\right)\right|=\left\|f-p^{*}\right\|_{\infty}, \quad i=0,1, \ldots, n+1, \end{aligned} \]

and

\[f\left(\xi_{i+1}^{*}\right)-p^{*}\left(\xi_{i+1}^{*}\right)=-\left[f\left(\xi_{i}^{*}\right)-p^{*}\left(\xi_{i}^{*}\right)\right], \quad i=0,1, \ldots, n, \]

are obtained.

只要不存在 \(p\) 使得 \(\left[f(x)-p^{*}(x)\right] p(x)>0\) 那么就有最优.

嘛……大概说说自己的思路，不一定对. 姑且把 \(\mathscr{A}\) 当成 \(\mathscr P_n\) 来想，因为 \(p(x)\) 在他所在的空间 \(\mathscr P_n\) 里面，只要是有 \(n\) 个零点的东西都能找到一个 \(p(x)\) 使得他们零点构成一样——所以就要 \(\left[f(x)-p^{*}(x)\right]\) 有更多的零点，至少要 \(n+1\) 个. 想要 \(n+1\) 个零点，那这个连续函数至少要 \(n +2\) 个交替分布在横轴上下的一些点，也就是这里说的 \(\left\{\xi_{i}^{*} ; i=0,1, \ldots, n+1\right\}\).