Vol. 277
1977

BEST UNIFORM APPROXIMATION \(\overline{\varphi}(x)\) TO A GIVEN CONTINUOUS FUNCTION \(f(x)\) ON THE INTERVAL \(a \le x \le b\) AND COMPUTATION OF THE BEST UNIFORM APPROXIMATION \(\varphi(x)\)

B. F. Krutoi

(Presented by the scientific seminar of the Department of Engineering and Computational Mathematics)

1. Let \(f(x)\) be a given continuous function \(f(x)\) on the interval \(a \le x \le b\). If the function \(f(x)\) has a very complicated form, then, in calculations on a digital computer, it is expedient to replace the function \(f(x)\) on the interval \(a \le x \le b\) by its best uniform approximation \(\overline{\varphi}(x)\), selected from some family \(M(\varphi)\) of functions \(\varphi(x)\) continuous on \(a \le x \le b\).

Finding the sought function \(\overline{\varphi}(x)\), which best uniformly approximates the given function \(f(x)\) on the interval \(a \le x \le b\), is equivalent to the requirement of finding, among the family \(M(\varphi)\) of functions \(\varphi(x)\) continuous on \(a \le x \le b\), a function \(\overline{\varphi}(x)\) for which the greatest deviation \(\overline{\Delta}\)

\[ \overline{\Delta}=\max |f(x)-\overline{\varphi}(x)|,\quad (a\le x\le b) \tag{1} \]

has the least value among the set of deviations \(\Delta_{\varphi}\),

\[ \Delta_{\varphi}=\max |f(x)-\varphi(x)|,\quad (a\le x\le b) \tag{2} \]

in the corresponding set of functions \(\varphi(x)\) from the chosen family \(M(\varphi)\). Hence it is clear that, for a given function \(f(x)\) continuous on \(a \le x \le b\), its best uniform approximation \(\overline{\varphi}(x)\) on \(a \le x \le b\), selected from the chosen family \(M(\varphi)\) of functions \(\varphi(x)\) continuous on \(a \le x \le b\), may be determined by the condition

\[ \varepsilon=\overline{\Delta}=\max |f(x)-\varphi(x)|=\min \ \text{of } \max |f(x)-\varphi(x)|, \tag{3} \]

\[ (a\le x\le b) \]

where \(\overline{\Delta}=\varepsilon\) is the unknown greatest deviation on \(a \le x \le b\).

The same thing can be expressed more briefly and just as precisely in the language of functional analysis. Denote by \(C(a,b)\) the space of functions \(\chi(x)\) continuous on \(a \le x \le b\), and define the distance \(\Delta_{ij}\) in this space \(C(a,b)\) between two of its functions-vectors \(\chi_i(x)\), \(\chi_j(x)\) by the expression

\[ \Delta_{ij}=\max |\chi_i(x)-\chi_j(x)|. \tag{4} \]

\[ (a\le x\le b) \]

Moreover, let us stipulate that in the space \(C(a,b)\) the following two basic operations are defined on the function-vectors belonging to it \(\varphi(x)=\varphi,\ \psi(x)=\psi,\ \vartheta(x)=\vartheta\):

\[ 1)\ \psi=\lambda\varphi,\qquad 2)\ \vartheta=\lambda\varphi+\mu\psi, \tag{5} \]

where \(\lambda\) and \(\mu\) are certain prescribed numbers.

Now the problem posed above of finding the best uniform approximation \(\varphi(x)\) on the interval \(a\le x\le b\) for a given function \(f(x)\), continuous on \(a\le x\le b\), can be expressed briefly and precisely as follows:

For a function \(f(x)\in C(a,b)\), find a function \(\overline{\varphi}(x)\), \(\varphi(x)\in M(\varphi)\subset C(a,b)\), such that for a definite family \(M(\varphi)\) of functions \(\varphi(x)\) condition (3) is satisfied with unknown greatest deviation \(\overline{\Delta}=\varepsilon\):

\[ \varepsilon=\overline{\Delta} =\max_{\overline{\varphi}(x)\in M(\varphi)\subset C(a,b)} \left|f(x)-\overline{\varphi}(x)\right| = \min_{\varphi(x)\in M(\varphi)\subset C(a,b)} \max \left|f(x)-\varphi(x)\right|. \tag{3} \]

\[ (a\le x\le b) \]

The problem under consideration was first posed and comprehensively investigated by Acad. P. L. Chebyshev—the proof of existence, uniqueness, and various properties of the best uniform approximation \(\overline{\varphi}(x)\) on \(a\le x\le b\) to a function \(f(x)\), continuous on \(a\le x\le b\). Then K. Weierstrass proved that for every \(\varepsilon>0\) there exists a polynomial \(P(x)\) such that for all \(x\in [a,b]\) we have

\[ |f(x)-P(x)|<\varepsilon. \tag{6} \]

Finally, É. Borel established the existence on \(a\le x\le b\) of such a polynomial \(P(x)\) for which, for some greatest deviation \(\varepsilon\),

\[ |f(x)-P(x)|=\varepsilon. \tag{7} \]

However, in their investigations these scholars confined themselves to those two, though important, special cases when the function \(\varphi(x)\) is an algebraic or a trigonometric polynomial:

\[ 1)\ \overline{\varphi}(x)=\sum_{s=0}^{n} b_s x^s,\qquad 2)\ \overline{\varphi}(x)=a_0+\sum_{x=1}^{n}\left(a_x\cos x x+b_x\sin x x\right). \tag{8} \]

Moreover, these scholars did not propose any methods for calculating the best uniform approximation \(\overline{\varphi}(x)\) in the two indicated cases.

The present problem is solved more fully in the book [2]. In this book:

a) a proof is given of the existence and uniqueness of the function \(\overline{\varphi}(x)\), the best uniform approximation in any family \(M(\varphi)\) of functions \(\varphi(x)\) from \(C(a,b)\);

b) the investigations of A. Haar and A. N. Kolmogorov, devoted to generalized polynomials of best uniform approximation, are considered, and the corresponding extended Chebyshev theorem for such generalized polynomials is given;

c) two methods of successive approximation are indicated and justified for constructing the function \(\overline{\varphi}(x)\) of best uniform approxima-

... in that simplest case when \(\overline{\varphi}(x)\) is an ordinary algebraic polynomial of the form (8.1).

Taking into account, therefore, everything that has already been done in this area of applied mathematics, we shall set as our goal, for some family \(M(\varphi)\) of functions \(\varphi(x)\) from \(C(a,b)\) chosen by us, to construct a system of finite equations from which the desired best uniform approximation \(\overline{\varphi}(x)\in M(\varphi)\) to a given function \(f(x)\in C(a,b)\) can be found, and the corresponding greatest deviation \(\Delta=\varepsilon\) established.

1. Let us proceed to the solution of the problem under consideration. To this end, we shall first assume that the family \(M(\varphi)\subset C(a,b)\) of functions \(\varphi(x)\in M(\varphi)\) taken by us possesses properties (4), (5) of the space \(C(a,b)\) and is an \((m+1)\)-dimensional subspace \(\Omega_{m+1}\) contained in \(C(a,b)\). Thus,

\[ \begin{gathered} 1)\ f(x)\in C(a,b), \qquad 2)\ \varphi(x)=\varphi_{m+1}(x)\in \Omega_{m+1}\subset C(a,b),\\ 3)\ \varphi(x)=\overline{\varphi}_{m+1}(x)\in \Omega_{m+1}\subset C(a,b). \end{gathered} \tag{9} \]

Taking further into account the possibility of performing in \(\Omega_{m+1}\subset C(a,b)\) operations of the form (4), (5), we represent the function \(\overline{\varphi}_{m+1}(x)\) of the best uniform approximation to \(f(x)\) in the form of the expansion

\[ \overline{\varphi}_{m+1}(x)=\sum_{\nu=0}^{m} c_{\nu}\varphi_{\nu}(x)=\overline{\varphi}(x) \tag{10} \]

in terms of the given \(m+1\) basic mutually independent functions \(\varphi_{\nu}(x)\in \Omega_{m+1}\) and with as yet unknown \(m+1\) coefficients \(c_{\nu}\). Substituting then the expansion (7) for \(\overline{\varphi}_{m+1}(x)=\overline{\varphi}(x)\) into condition (3), we obtain

\[ \varepsilon=\Delta=\operatorname{greatest}\,|f(x)-\overline{\varphi}_{m+1}(x)| =\operatorname{least\ among\ greatest}\,|f(x)-\varphi_{m+1}(x)|= \]

\[ [f(x)\in C(a,b)]. \]

\[ [\overline{\varphi}_{m+1}(x)\in \Omega_{m+1}\subset C(a,b)] [\varphi_{m+1}(x)\in \Omega_{m+1}\subset C(a,b)]. \]

\[ (a\le x\le b). \]

\[ =\operatorname{greatest}\left|f(x)-\sum_{\nu=0}^{m}c_{\nu}\varphi_{\nu}(x)\right|. \]

\[ [\varphi_{\nu}(x)\in \Omega_{m+1}\subset C(a,b)]. \tag{11} \]

We shall now find the function \(\overline{\varphi}_{m+1}(x)=\overline{\varphi}(x)\) of the best uniform approximation to the given continuous function \(f(x)\) on \(a\le x\le b\), determined by condition (11), by requiring that at some number \(r\) of points \(x_s\) of the interval \(a\le x\le b\), the \(r\) equalities following from (7) be satisfied:

\[ \left|\sum_{\nu=0}^{m}c_{\nu}\varphi_{\nu}(x_s)-f(x_s)\right| =\varepsilon,\quad (s=1,2,\ldots,r). \tag{12} \]

If we assume that the indicated \(r\) points \(x_s\) of the interval \(a\le x\le b\) at which requirement (12) is fulfilled are already known to us, then the determination of the remaining \(m+2\) unknowns \(\varepsilon, c_0, c_1,\ldots,c_m\) from the \(r\) equalities (12) will be possible by taking \(r=m+2\).

But the above-indicated \(r=m+2\) points \(x_s\) of the interval \(a\le x\le b\) are still unknown to us in advance. Therefore, in order to determine these \(m+2\) points \(x_s\), we shall take into account that, according to (11),

\[ \varepsilon=\max \left|\sum_{\nu=0}^{m} c_\nu \varphi_\nu(x)-f(x)\right|,\quad [\varphi_\nu(x)\in \Omega_{m+1}\subset C(a,b)]. \tag{11} \]

Hence, under the assumption not only of continuity but also of differentiability of the functions \(f(x)\), \(\varphi_\nu(x)\) on the interval \(a\le x\le b\), which is almost always valid, we obtain, by the known rule, another \(m+2\) equalities

\[ \left(\frac{\partial \varepsilon}{\partial x}\right)=0= \left|\sum_{\nu=0}^{m} c_\nu \varphi'_\nu(x_s)-f'(x_s)\right|,\quad (s=1,2,\ldots,m+2). \tag{13} \]

Finally, combining the \(m+2\) equalities (9) with the \(m+2\) equalities (13), we ultimately obtain a system of \(2m+4\) nonlinear equations with \(2m+4\) unknowns \(\varepsilon, c_0, c_1,\ldots,c_m, x_1, x_2,\ldots,x_{m+2}\).

\[ \left\{ \begin{aligned} 1)\;&\left|\sum_{\nu=0}^{m} c_\nu\varphi_\nu(x_s)-f(x_s)\right|=\varepsilon,\\[4pt] 2)\;&\left|\sum_{\nu=0}^{m} c_\nu\varphi'_\nu(x_s)-f'(x_s)\right|=0, \end{aligned} \right. \qquad (s=1,2,\ldots,m+2). \tag{14} \]

The solution of the system of \((2m+4)\) nonlinear equations (14) can be carried out, first of all, by one of the descent methods [3]. In addition, if we have somehow established approximate values \(\varepsilon^0, c_\nu^0, x_s^0\) for the \(2m+4\) unknowns \(\varepsilon, c_\nu, x_s\), then the system of equations (14) can be solved exactly by Newton’s method or by some method related to it [3]. Finally, the system of equations (14) can be solved by continuation—as a sequence of systems of the form (14) for \(m=0,1,2,\ldots,N\), where \(N+1\) is the desired number of terms in the expansion (7) for \(\varphi_{m+1}(x)\).

Example. Let \(m=1\). Then \(c=c_0,c_1\) and \(x_s=x_1,x_2,x_3\). Therefore the system \(2m+4=6\) of nonlinear equations (14) is written in this case as follows:

\[ \begin{aligned} 1)\;&|c_0\varphi_0(x_1)+c_1\varphi_1(x_1)-f(x_1)|=\varepsilon,\\ 2)\;&|c_0\varphi_0(x_2)+c_1\varphi_1(x_2)-f(x_2)|=\varepsilon,\\ 3)\;&|c_0\varphi_0(x_3)+c_1\varphi_1(x_3)-f(x_3)|=\varepsilon,\\ 4)\;&|c_0\varphi'_0(x_1)+c_1\varphi'_1(x_1)-f'(x_1)|=0,\\ 5)\;&|c_0\varphi'_0(x_2)+c_2\varphi'(x_2)-f'(x_2)|=0,\\ 6)\;&|c_0\varphi'(x_3)+c_2\varphi'(x_3)-f'(x_3)|=0. \end{aligned} \]

Here \(f(x)\), \(\varphi_0(x)\), \(\varphi_1(x)\), \(\varphi_2(x)\) are given functions, while \(\varepsilon>0\), \(c_0,c_1\) and \(x_1,x_2,x_3=x_s\in [a,b]\) are unknown numbers.

The example given clearly shows the difficulty of calculating the function \(\overline{\varphi}(x)=\varphi_{m+1}(x)\) of best uniform approximation to the function \(f(x)\), continuous on \(a\le x\le b\). This explains why, instead of the present method of approximate representation of \(\varphi_{m+1}(x)\) for the function \(f(x)\), simpler computational methods of partial matching and least-squares approximation are usually used, which are determined by the conditions [2]:

a) The method of partial matching of the functions \(\overline{\varphi}_{m+1}(x)\) and \(f(x)\) at \(m+1\) points of the interval \(a\le x\le b\):

\[ 1)\quad \overline{\varphi}_{m+1}(x)=\sum_{\nu=0}^{m} c_\nu\varphi_\nu(x),\qquad (a\le x\le b), \tag{15} \]

\[ \begin{gathered} 2)\quad \varepsilon_s=\overline{\varphi}_{m+1}(x_s)-f(x_s) =\sum_{\nu=0}^{m}c_\nu\varphi_\nu(x_s)-f(x_s)=0, \quad (s=1,2,\ldots,m+1),\\ 3)\quad \varphi_\nu(x),\ \overline{\varphi}_{m+1}(x)\in R_{m+1}\subset L, \end{gathered} \]

where \(L\) is a linear space on \(a\le x\le b\) [3].

b) The method of root-mean-square approximation, with weight \(p(x)\), of \(\overline{\varphi}_{m+1}(x)\) to \(f(x)\) on the interval \(a\le x\le b\):

\[ \begin{gathered} 1)\quad \overline{\varphi}_{m+1}(x)=\sum_{\nu=0}^{m}c_\nu\varphi_\nu(x), \qquad 2)\quad \overline{\varepsilon}(x)=\overline{\varphi}_{m+1}(x)-f(x),\\[6pt] 3)\quad [p(x)\overline{\varepsilon}(x),\overline{\varepsilon}(x)] =\int_a^b p(x)\,[\overline{\varphi}_{m+1}(x)-f(x)]^2\,dx= \end{gathered} \tag{16} \]

\[ =Q^2=\min.\int_a^b p(x)[\varphi_{m+1}(x)-f(x)]^2\,dx, \]

where \(\overline{\varphi}_{m+1}(x),\varphi_{m+1}(x)\in\overline{\Omega}_{m+1}\subset\check H\), and \(\overline{\Omega}_{m+1}\) is a closed \(m+1\)-dimensional subspace contained in the complete Hilbert space \(H\) [3].

Let us note that the functions \(\varphi_\nu(x)\) appearing in (15.1) and (16.1) are \(m+1\) supporting mutually independent functions from the corresponding subspaces \(R_{m+1}\) and \(\overline{\Omega}_{m+1}\).

REFERENCES

1. I. P. Natanson, Constructive Theory of Functions. Moscow–Leningrad, GITTL, 1949.

2. I. S. Berezin and N. P. Zhidkov, Methods of Computation. Vol. 1, Moscow, Fizmatgiz, 1966.

3. G. E. Shilov, Mathematical Analysis, Special Course. Moscow, Fizmatgiz, 1960.