Abstract Generated abstract
This paper presents a successive approximation method for finding a best approximating polynomial, understood as an element of a finite-dimensional span in a normed space. The method constructs a sequence of auxiliary minimax problems involving finitely many norming functionals, each solvable by linear programming, and updates the functionals using points at which the current residual attains its norm. The authors prove that the resulting residual norms converge to the best approximation error, that the approximating polynomials are bounded, and that every convergent subsequence has a best approximation as its limit, with full convergence when the best approximating polynomial is unique. Extensions are noted for linear constraints on coefficients and for spaces such as continuous function spaces, differentiable function spaces, and \(L^p\) spaces.
Full Text
MATHEMATICS
G. P. Akilov, A. M. Rubinov
A METHOD OF SUCCESSIVE APPROXIMATIONS FOR FINDING THE POLYNOMIAL OF BEST APPROXIMATION
(Presented by Academician V. I. Smirnov on 26 II 1964)
-
Let \(X\) be a normed space (over the field of all real or all complex numbers); let \(x_1, x_2, \ldots, x_n\) be linearly independent vectors in \(X\); denote by \(\Omega=\mathcal{L}(\{x_k\})\) the elements of \(\Omega\)—linear combinations of the vectors \(x_1, x_2,\ldots,x_n\)—which we shall call polynomials; if \(u\) is a given element of the space \(X\), then a polynomial \(Q\) such that, for \(P=Q\), the functional \(\|u-P\|\) \((P\in\Omega)\) attains its least value \(\mu=\rho(u,\Omega)\), is called the polynomial of best approximation (to \(u\)), and the number \(\mu\) the best approximation.
-
The process of determining the polynomial of best approximation consists in the successive solution of a number of auxiliary problems: let \(g_k\in X^*\) \((k=1,2,\ldots,m;\ m\geq n)\); it is required to determine \(P'\in\Omega\) such that
\[ \max_{k\leq m}|g_k(P'-u)|=\min_{P\in\Omega}\left[\max_{k\leq m}|g_k(P-u)|\right]. \tag{1} \]
As is known, such problems can be solved by means of linear programming, for example with the aid of a certain modification of the simplex method.
- The construction of the polynomial of best approximation \(Q\) and the determination of the best approximation \(\mu\) are carried out according to the following scheme.
Denote by \(X_0\) the subspace of the space \(X\) spanned by the set \(\Omega\) and the element \(u\), and let \(\Gamma\subset X^*\) be a set of normalized functionals having the property that for every \(x\in X_0\) one can specify such an \(f_0\in\Gamma\) that \(|f_0(x)|=\|x\|\).
As is easy to see, in \(\Gamma\) there exist elements \(f_1, f_2,\ldots,f_n\) such that the determinant \(|f_i(x_k)|_{i,k=1,2,\ldots,n}\neq 0\), and then, evidently, there exists an “interpolation” polynomial \(P_n\in\Omega\), determined by the equalities
\[ f_i(u-P_n)=0 \qquad (i=1,2,\ldots,n). \]
It is clear that \(P_n\) is a solution of problem (1), if in it one takes \(m=n,\ g_k=f_k\) \((k=1,2,\ldots,n)\).
Let, for \(m\geq n\), functionals \(f_1, f_2,\ldots,f_m\in\Gamma\) and polynomials \(P_n, P_{n+1},\ldots,P_m\in\Omega\) be defined so that
\[ \max_{k\leq s}|f_k(P_s-u)|=\min_{P\in\Omega}\left[\max_{k\leq s}|f_k(P-u)|\right] \qquad (s=n,n+1,\ldots,m), \tag{2} \]
\[ |f_{k+1}(P_k-u)|=\|P_k-u\| \qquad (k=n,n+1,\ldots,m-1). \tag{3} \]
The functional \(f_{m+1}\) is found so that (3) is satisfied for \(k=m\), and the polynomial \(P_{m+1}\) is determined as the solution of problem (1), where \(g_k=f_k\) \((k=1,2,\ldots,m+1)\).
As a result of the process described, two sequences are obtained: \(\{f_k\}\) \((f_k\in\Gamma;\ k=1,2,\ldots)\) and \(\{P_s\}\) \((P_s\in\Omega;\ s=n,n+1,\ldots)\) such that (2) and (3) are satisfied for all \(k,\ s\geq n\). Denote \(\mu_m=\|P_m-u\|\) \((m\geq n)\).
Theorem. The sequence \(\{\mu_m\}\) converges to \(\mu\). The sequence \(\{P_m\}\) is bounded (in the space \(X\)). If \(\{P_{m_i}\}\) is any convergent subsequence of the sequence \(\{P_m\}\), then \(Q=\lim_{i\to\infty} P_{m_i}\) is a polynomial of best approximation. If the polynomial of best approximation \(Q\) is unique, then the sequence \(\{P_m\}\) itself converges to \(Q\).
- Before proving the theorem we give some preliminary considerations.
In the space \(X\) introduce seminorms \(\|\cdot\|_s\) \((s\ge n)\), putting
\[
\|x\|_s=\max_{k\le s}|f_k(x)|.
\]
Clearly,
\[
\|x\|_s\le \|x\|_{s+1}\le \|x\|\qquad (x\in X;\ s=n,n+1,\ldots).
\tag{4}
\]
Lemma 1. If \(s>m\), then \(\mu_m=\|P_m^*-u\|_s\).
Next, denote
\[
\lambda_m=\|P_m-u\|_m\qquad (m\ge n).
\]
Lemma 2. \(\lambda_n\le \lambda_{n+1}\le\cdots\).
Lemma 3. \(\lambda_m\le \mu\le \mu_m\) \((m\ge n)\).
Remark. If it turns out that \(\lambda_m=\mu_m\) for some \(m\), then \(\mu=\lambda_m=\mu_m\) and \(P_m\) will be a polynomial of best approximation. In this case the polynomials \(P_k\) \((k\ge m)\) will also be polynomials of best approximation.
- Proof of the theorem. It is not hard to see that in the space \(X_0\) the seminorm \(\|\cdot\|_{n+1}\) will be a norm. But then, since \(X_0\) is finite-dimensional, there is a number \(K\) such that \(\|x\|\le K\|x\|_{n+1}\) \((x\in X_0)\); then, on the basis of Lemma 3 and (4),
\[ \mu_m=\|P_m-u\|\le K\|P_m^*-u\|_{n+1}\le K\|P_m-u\|_m=K\lambda_m\le K\mu \qquad (m\ge n+1), \]
so that the sequence \(\{\mu_m\}\), and hence also the sequence \(\{P_m\}\), is bounded. Consider an arbitrary subsequence \(\{\mu_{m_i}\}\) and the corresponding sequence \(\{P_{m_i}\}\). Passing, if necessary, to a subsequence of this sequence, we may assume that there exists
\[ Q=\lim_{i\to\infty}P_{m_i}. \]
Then
\[ \mu_{m_i}=\|P_{m_i}-u\|\to \|Q-u\|. \]
Further,
\[ \lambda_{m_i}\to \lambda=\lim_{m\to\infty}\lambda_m. \]
According to Lemma 1, taking (4) into account, we may write
\[ \begin{aligned} \mu_{m_i} &=\|P_{m_i}-u\|_{m_i+1} \le \|P_{m_{i+1}}-u\|_{m_i+1} +\|P_{m_{i+1}}-P_{m_i}\|_{m_i+1} \\ &\le \lambda_{m_{i+1}}+\|P_{m_{i+1}}-P_{m_i}\| \qquad (i=1,2,\ldots). \end{aligned} \]
Passing here to the limit, we obtain
\[ \mu\le \|Q-u\|\le \lambda. \]
But, by Lemma 3, \(\lambda\le\mu\). Thus \(\|Q-u\|=\mu\), \(\mu_{m_i}\to\mu\). It follows that \(\mu_m\to\mu\).
The remaining assertions of the theorem follow in an obvious way from what was said above.
- Remarks.
\(1^\circ\). Since \(\lambda_m\to\lambda=\mu\), the result of Lemma 3 can be used to estimate the rate of convergence \(\mu_m\to\mu\) (and, of course, \(\lambda_m\to\mu\)).
\(2^\circ\). The method described above for finding a polynomial of best approximation can also be used in the case when it is required that the coefficients \(a_1,a_2,\ldots,a_n\) of the desired polynomial satisfy certain linear restrictions:
\[
\sum_{k=1}^{n} c_i^k a_k \le C_i\qquad (i=1,2,\ldots,\nu).
\tag{5}
\]
In this case it is only necessary to replace the set \(\Omega\) by the set of all such polynomials whose coefficients satisfy conditions analogous to (5).
\(3^\circ\). If the process described above is modified somewhat, then in the role of \(\Gamma\) one may consider such a set of normalized functionals that, for each \(x \in X_0\), one has
\[
\|x\|=\sup_{f\in\Gamma}|f(x)|.
\]
\(4^\circ\). Let us indicate some particular cases.
a) \(X=C(T)\), where \(T\) is a compact topological space. As \(\Gamma\) here one may take the set \(T\), i.e., more precisely, the set of all positive measures with singleton supports.
b) If \(T\) is a closed bounded set in Euclidean space and \(X=C^{(r)}(T)\), then one may take \(\Gamma=T\times\{0,1,\ldots,r\}\).
c) If \(X=L^p\) \((1\le p\le \infty)\), then in the case \(p<\infty\) one should take for \(\Gamma\) the set of all normalized functionals. For \(p=\infty\), it is expedient to understand \(\Gamma\) as the set of all absolutely continuous positive normalized measures.
Leningrad State University
named after A. A. Zhdanov
Received
30 I 1964