19.6.3 切比雪夫逼近

19.6.3.1 问题的定义和交替点定理

1. 切比雪夫逼近原理

连续情况的切比雪夫逼近或一致逼近如下: 函数 $f\left(x\right)$ 在区间 $\left[a,b\right]$ 内被函数 $g\left(x\right)=g\left(x;a_0,a_1,\cdots ,a_n\right)$ 逼近,使得由

$$\begin{array}{}\text{(19.195)}& \underset{a\le x\le b}{max}\left|f\left(x\right)-g\left(x;a_0,a_1,\cdots ,a_n\right)\right|=\mathrm{\Phi }\left(a_0,a_1,\cdots ,a_n\right)\end{array}$$

定义的误差对于适当选取的参数 $a_i\left(i=0,1,\cdots ,n\right)$ 尽可能小. 如果 $f\left(x\right)$ 存在这样的近似函数,则误差的绝对值至少在区间的 $n+2$ 点 $x_{\nu }$ 上取得极大,在这些所谓的交替点误差变号 (图 19.10). 这正是交替点定理对于切比雪夫多项式逼近问题的解的特征化的含义.

若函数 $f\left(x\right)=x^n$ 在区间 $\left[-1,1\right]$ 上在切比雪夫意义下被次数 $\le n-1$ 的多项式近似,则切比雪夫多项式 $T_n\left(x\right)$ 可作为最大模为 1 的误差函数. 位于区间端点和区间内 $n-1$ 个点的交替点恰好相应于 $T_n\left(x\right)$ 的极值点 (图 19.11(a) $\sim$ (f)).

19.6.3.2 切比雪夫多项式的性质

1. 表达式

$$\begin{array}{}\text{(19.196a)}& T_n\left(x\right)=\cos \left(n\arccos x\right),\end{array}$$$$\begin{array}{}\text{(19.196b)}& T_n\left(x\right)=\frac{1}{2}\left[{(x+\sqrt{x^2-1})}^n+{(x-\sqrt{x^2-1})}^n\right],\end{array}$$$$\begin{array}{}\text{(19.196c)}& T_n\left(x\right)=\{\begin{array}{lll}\cos nt,& x=\cos t,& \left|x\right|<1,\\ \cosh nt,& x=\cosh t,& \left|x\right|>1\end{array}\left(n=1,2,\cdots \right).\end{array}$$

2. $T_n\left(x\right)$ 的根

$$\begin{array}{}\text{(19.197)}& x_{\mu }=\cos \frac{\left(2\mu -1\right)\pi }{2n}\left(\mu =1,2,\cdots ,n\right).\end{array}$$

3. 当 $x\in \left[-1,1\right]$ 时 $T_n\left(x\right)$ 极值点的位置

$$\begin{array}{}\text{(19.198)}& x_{\nu }=\cos \frac{\nu \pi }{n}\left(\nu =0,1,2,\cdots ,n\right).\end{array}$$

4. 递推公式

$$\begin{array}{}\text{(19.199)}& T_{n+1}=2x{T}_n\left(x\right)-T_{n-1}\left(x\right)\left(n=1,2,\cdots ;T_0\left(x\right)=1,T_1\left(x\right)=x\right).\end{array}$$

例如, 递推得到

$$\begin{array}{}\text{(19.200a)}& T_2\left(x\right)=2x^2-1,T_3\left(x\right)=4x^3-3x,\end{array}$$$$\begin{array}{}\text{(19.200b)}& T_4\left(x\right)=8x^4-8x^2+1,T_5\left(x\right)=16x^5-20x^3+5x,\end{array}$$$$\begin{array}{}\text{(19.200c)}& T_6\left(x\right)=32x^6-48x^4+18x^2-1,\end{array}$$$$\begin{array}{}\text{(19.200d)}& T_7\left(x\right)=64x^7-112x^5+56x^3-7x,\end{array}$$$$\begin{array}{}\text{(19.200e)}& T_8\left(x\right)=128x^8-256x^6+160x^4-32x^2+1,\end{array}$$$$\begin{array}{}\text{(19.200f)}& T_9\left(x\right)=256x^9-576x^7+432x^5-120x^3+9x,\end{array}$$$$\begin{array}{}\text{(19.200g)}& T_{10}\left(x\right)=512x^{10}-1280x^8+1120x^6-400x^4+50x^2-1.\end{array}$$

19.6.3.3 列梅兹 (Remes) 算法

1. 交替点定理的推论

数值求解连续切比雪夫逼近问题源于交替点定理. 逼近函数选为

$$\begin{array}{}\text{(19.201)}& g\left(x\right)=\sum _{i=0}^n{a}_i{g}_i\left(x\right),\end{array}$$

有 $n+1$ 个线性无关的已知函数,切比雪夫问题的解的系数记为 $a_i^{\ast }\left(i=0,1,\cdots ,n\right)$ , 根据 (19.195) 最小偏差记为 $\rho =\mathrm{\Phi }\left(a_0^{\ast },a_1^{\ast },\cdots ,a_n^{\ast }\right)$ . 此时当函数 $f$ 和 $g_i(i=0,1,\cdots$ , $n)$ 可微,由交替点定理有

$$\sum _{i=0}^n{a}_i^{\ast }{g}_i\left(x_{\nu }\right)+{(-1)}^{\nu }\varrho =f\left(x_{\nu }\right),\sum _{i=0}^n{a}_i^{\ast }{g}_i^{\prime }\left(x_{\nu }\right)=f^{\prime }\left(x_{\nu }\right)\left(\nu =1,2,\cdots ,n+2\right).$$

(19.202)

交替点 $x_{\nu }$ 满足

$$\begin{array}{}\text{(19.203)}& a\le x_1<x_2<\cdots <x_{n+2}\le b.\end{array}$$

方程组 (19.202) 对切比雪夫逼近问题的 $2n+4$ 个未知量,包括 $n+1$ 个系数、 $n+2$ 个交替点及最小偏差 $\rho$ ,给出了 $2n+4$ 个条件. 若区间端点也是交替点,则在该处导数条件不是必要条件.

2. 根据列梅兹算法确定最小解

根据列梅兹算法, 数值确定最小解的步骤如下.

(1) 根据 (19.203) 确定交替点 $x_{\nu }^{\left(0\right)}\left(i=1,2,\cdots ,n+2\right)$ 的近似值,例如等距节点或 $T_{n+1}\left(x\right)$ 的极值点 (见 19.6.3.2).

(2)求解线性方程组

$$\sum _{i=0}^n{a}_i{g}_i\left(x_{\nu }{}^{\left(0\right)}\right)+{(-1)}^{\nu }\varrho =f\left(x_{\nu }{}^{\left(0\right)}\right)\left(\nu =1,2,\cdots ,n+2\right),$$

其解为近似值 $a_i^{\left(0\right)}\left(i=0,1,\cdots ,n\right)$ 和 ${\rho }_0$ .

(3) 确定交替点新的近似值 $x_{\nu }^{\left(1\right)}\left(i=1,2,\cdots ,n+2\right)$ ,例如误差函数 $f\left(x\right)-$ $\sum _{i=0}^n{a}_i^{\left(0\right)}{g}_i\left(x\right)$ 极值点的位置. 此时可以应用这些点作为近似值.

以 $x_{\nu }^{\left(1\right)},a_{\nu }^{\left(1\right)}$ 代替 $x_{\nu }^{\left(0\right)},a_{\nu }^{\left(0\right)}$ ,重复步骤 2 和步骤 3,等等,即得到关于系数和交替点的逼近序列,其收敛性在某些条件下可以得到 (见 [19.33]). 若某个迭代指标 $\mu$ 使得

$$\begin{array}{}\text{(19.204)}& \left|{\varrho }_{\mu }\right|=\underset{a\le x\le b}{max}\left|f\left(x\right)-\sum _{i=0}^n{a}_i{}^{\left(\mu \right)}{g}_i\left(x\right)\right|\end{array}$$

满足充分的精度, 则计算停止.

19.6.3.4 离散切比雪夫逼近和最优化

从连续切比雪夫逼近问题

$$\begin{array}{}\text{(19.205)}& \underset{a\le x\le b}{max}\left|f\left(x\right)-\sum _{i=0}^n{a}_i{g}_i\left(x\right)\right|=min!\end{array}$$

若选取 $N$ 个点 $x_{\nu }\left(\nu =1,2,\cdots ,N;N\ge n+2\right)$ 满足性质 $a\le x_1<x_2<\cdots \le$ $x_N\le b$ 并要求:

$$\begin{array}{}\text{(19.206)}& \underset{\nu =1,2,\cdots ,N}{max}\left|f\left(x_{\nu }\right)-\sum _{i=0}^n{a}_i{g}_i\left(x_{\nu }\right)\right|=min!\end{array}$$

可得相应的离散问题, 代入

$$\begin{array}{}\text{(19.207)}& \gamma =\underset{\nu =1,2,\cdots ,N}{max}\left|f\left(x_{\nu }\right)-\sum _{i=0}^n{a}_i{g}_i\left(x_{\nu }\right)\right|,\end{array}$$

显然有推论

$$\begin{array}{}\text{(19.208)}& \left|f\left(x_{\nu }\right)-\sum _{i=0}^n{a}_i{g}_i\left(x_{\nu }\right)\right|\le \gamma \left(\nu =1,2,\cdots ,N\right).\end{array}$$

从 (19.208) 消去绝对值,得到关于系数 $a_i$ 和 $\gamma$ 的线性不等式组,从而 (19.206) 化为线性规划问题 (参见第 1179 页 18.1.1.1):

$$\begin{array}{}\text{(19.209)}& \gamma =min!\text{,满足}\{\begin{array}{c}\gamma +\sum _{i=0}^n{a}_i{g}_i\left(x_{\nu }\right)\ge f\left(x_{\nu }\right),\\ \gamma -\sum _{i=0}^n{a}_i{g}_i\left(x_{\nu }\right)\ge -f\left(x_{\nu }\right)\end{array}\left(\nu =1,2,\cdots ,N\right).\end{array}$$

对 $\gamma >0$ 方程 (19.209) 有极小解. 对于足够大的点数 $N$ 及某些进一步的条件,离散问题的解可看作连续问题的解.

若用非线性依赖参数 $a_0,a_1,\cdots ,a_n$ 的非线性逼近函数 $g\left(x\right)=g(x;a_0,a_1$ , $\cdots ,a_n)$ 代替线性逼近函数 $g\left(x\right)=\sum _{i=0}^n{a}_i{g}_i\left(x\right)$ ,则类似可得非线性最优化问题. 其通常即使在简单函数形式下也是非凸的. 这从本质上减少了非线性最优化问题的数值解法 (参见第 1203 页 18.2.2.1).