ABSTRACT
We studied the optimal convergence rate of algorithm for approximation and integration problems from some periodic analytic classes. For approximation problem we determine the optimal convergence rate of Dirichlet interpolating algorithm over periodic functions admitting analytic regularities. The optimal order of m-th minimum linear intrinsic error is also determined. By means of previous results about n-widths, we discuss the optimality of interpolation method. For integration problem we determine the optimal convergence rate of the rectangle formula over the class . We conjecture that the rectangle formula is optimal among all linear quadrature formulas.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/itj.2011.2196.2201
URL: https://scialert.net/abstract/?doi=itj.2011.2196.2201
INTRODUCTION
We consider the problem of approximate recovery of function and integral from values at m points. There have been many beautiful results for various finitely smooth functions such as functions which have Sobolev regularities or Besov regularities. So far there are relatively few results obtained on infinitely differentiable functions which are also important in many applications, such as information-based complexity theory, machine learning theory (Novak and Wozniakowski, 2008; Smale and Zhou, 2003; Traub et al., 1988).
In this study, we consider the algorithm and complexity for approximation and integration problems over some periodic analytic classes. Let f be a measurable, almost finite function which is 2π-periodic. We write f∈LP for 1≤p < ∞ if:
(1) |
where, the integral is considered as a Lebesgue integral. In the case p = ∞ it will be convenient for us to assume that the space L∞ is the space of continuous functions f with:
(2) |
Let 1≤p≤∞, f ∈ Lp and K ∈ L1. We define the convolution of the functions f and K by:
(3) |
We will use the well-known Young inequality:
(4) |
For a function f∈L1 we define the Fourier coefficients:
(5) |
where, . It is well-known that:
(6) |
We formulate the question of approximate recovery of functions from values at m points. Let f be a continuous and 2π-periodic function. For fixed m, Ψ1 (x), , Ψm (x), ς1, ,ςm, we define the linear operator:
(7) |
And for a class of functions F, we define the quantities:
(8) |
and characterize the optimal possibility of linearly approximating a class of functions by means of different tools as:
(9) |
The Dirichlet kernel of order n is:
(10) |
This Dirichlet kernel may be used to define an interpolation algorithm. We consider the recovering operator of Dirichlet interpolation algorithm:
(11) |
where, x1 = 2πl/(2m + 1). We call the functions of the form:
(12) |
trigonometric polynomials of order m. We denote by T (m) the set of such polynomials. It is known that the operator Im maps a continuous function f to the trigonometric polynomial Im (f) ∈ T (m) such that:
(13) |
Therefore Im is an interpolation operator.
For a function class F, we will study the convergence rate of the quantity:
(14) |
For this purpose, it is convenient to use the notation << and ><. For two non-negative sequences an and bn, the notation an << bn means that there are some constant C and some n0 ∈ N such that an ≤ cbn for all n≥n0. The asymptotic notation an >< bn means that an << bn and bn << an. Throughout the paper we use β = max {a/q-1/p, 0} which will be used in our error estimates. Now we recall the fundamental result on periodic Sobolev classes. For r<0 and a∈R, the function:
(15) |
is called a Bernoulli kernel. For 1 ≤ q ≤ ∞, the Sobolev class is the set of functions representable in the form:
(16) |
where, is the derivative of f in the sense of Weil. Temlyakov (1985) obtained the following fundamental result.
Theorem 1: Let 1 ≤ p ∞, 1 ≤ q ≤ ∞ and r > 1/p. We have:
(17) |
In present study, we study functions whose smoothness is essentially different from that of functions in . Let r and b be positive real numbers. We set:
(18) |
and denote by the class the set of functions representable in the form:
(19) |
We note that in the case b = 1, the function gr, 1 coincides with the Poisson kernel:
(20) |
Let us separately consider two cases: b≥ 1 and 0 < n< 1. Present results are stated as follows.
Theorem 2: Let 1≤ p < ∞, 1≤ q ≤ ∞., b ≥ 1, n denote 2m + 2 or 2m. Then:
(21) |
Theorem 3: Let 1 ≤ p < ∞, 1 ≤ q ≤ ∞, 0 < b < 1. Then:
(22) |
When 0 < b < 1, the determination of the optimal bound is a much more complicated problem. We have partial results. Let:
(23) |
D1 = {(p, q): 1 ≤ q < 2 and 2 < p ≤ ∞} and D2 = D/D1.
Corollary: Let (p, q) ∈ D2 Then:
(24) |
Next we consider the approximation of integration. Let f be a continuous and 2π-periodic function. We consider the rectangle quadrature formula:
(25) |
For a class of functions F, we define the quantities:
(26) |
Note that:
(27) |
This enables us to use tools from Fourier analysis to estimate qm (F). Temlyakov (1994) obtained the result on Sobolev classes.
Theorem 4: Let 1≤p≤∞ and 1≤p≤∞. Then:
(28) |
For the integration error of functions from , we obtain the following result.
Theorem 5: Let 0<b<∞, 1≤p≤∞ .Then:
(29) |
APPROXIMATION OF FUNCTIONS
For f ∈ Lp, the error of the best approximation of f by the elements of T (m) in the Lp-norm is defined by:
(30) |
And for a class of functions F, we define the worst case error of the best approximation by:
(31) |
We denote by Sm the operator of taking the partial sum of order m. Then for f ∈ L1, we have:
(32) |
For a class of functions F, let us denote the error of Fourier method on F by:
(33) |
For F ⊂ Lp, the quantities (m = 1, 2, ):
(34) |
are called Kolmogorov widths of F in L. Kolmogorov widths characterize the optimal possibility of approximating a class of functions by means of elements from a subspace with dimension m when we have various restrictions on a method of constructing an approximating element. In the definition of the Kolmogorov widths, we take f ∈ F for an approximating element from U = lin {u1, u2, , um}, the element of best approximation. This means in general this method of approximation is not linear. Let us consider the quantities in the definitions of which we require the linearity of an approximating method. The quantities:
(35) |
are called linear widths of F in Lp. Here the infimum is taken over all linear operators A acting from F to Lp such that the dimension of the ranges of the operators A is not greater than m.
Theorem 6 (Temlyakov, 1994): Let b≤1 and n denote 2m or 2m-1. For all 1 ≤q, p ≤ ∞, we have the relations:
(36) |
Theorem 7: Let 1 ≤ q, p ≤ ∞, and β = max {1/q-1/p, 0). Then:
(37) |
Proof: The case of 0 < b < 1 was proved by Temlyakov (1985). We proceed to the case b ≤ 1:
(38) |
Therefore, the desired result follows directly from Theorem 6.
Lemma 1: Let 1 < p < ∞ and n ≤ m. Then for t ∈ T (n):
(39) |
Proof: First we recall de la Vallee-Poussin kernel:
(40) |
We define the operator on L1 by the formula:
(41) |
Noting that Vn (t) = t, we have:
(42) |
It is proved that:
(43) |
Thus, we get the required result.
Proof of theorem 2: It is known from the definitions that:
So it suffices to prove the upper bounds for and the lower bounds for = .
We first prove the upper estimates. By the monotonicity of Lp-norms, we have for for p < q. So to prove the upper bounds, it suffices to consider . Furthermore we only need to prove for 1 < p < ∞. It is known that the Fourier series of a function converges uniformly. For convenience, we set ek (x) = eikx. We represent in the form:
(44) |
Let . Then . Using the property Im (t) = t, t ∈ T (m), we have:
(45) |
which completes the proof of the upper bounds. Now we turn to the lower bounds. Note that T (m) is a 2m + 1-dimensional linear space. It follows from the definitions of ρn and d2m + 2 that:
(46) |
Therefore, by Theorem 6, we have:
(47) |
which completes the proof of the lower bounds.
Now we turn to the proof of Theorem 3. For 0 < b < 1, we construct the sequence of integral numbers such that N1 = 1 and .
Denote ns = Ns +1. It follows from the definition that for all s:
(48) |
and ns>< s1/b-1.
We define the following functions:
(49) |
and:
(50) |
For f ∈ L1, define the operator Ab, S by:
(51) |
Then we recall the following known results from Temlyakov (1985).
Lemma 2: Let 1 ≤ p ≤ ∞, f, g ∈ Lp and for all k. Then g = g a.e.. Moreover, if f and g are continuous, they coincide.
Lemma 3: We have:
(52) |
Lemma 4: Let . Then:
(53) |
Now we proceed to prove the following expansion Theorem.
Theorem 8: For , 0 < b < 1, we have:
(54) |
Proof: By lemma 4, we have:
(55) |
Thus:
converges to a function in Lp. Let's denote it by g. The function Ab, s (f) can have nonzero Fourier coefficients only in (-Ns + 1, -Ns-1). It is not difficult to check that for any k, . Thus by lemma 2, f = g.
Proof of theorem 3: For a given m, we choose a positive integer l such that m ∈ [Nl, Nl + 1] By Theorem 8 we represent as:
Use the fact Ab, s (f) ∈ T (Ns + 1-1). Note that the function Ab, s (f) can have nonzero Fourier coefficients only in (-Ns + 1, -Ns-1) ∪ (ns-1, Ns + 1). By Nikol'ski inequality, we have:
Then:
(56) |
where, we use the asymptotic relationship 11/b >< m. Noting that , we have:
Thus:
(57) |
Now we turn to the lower bounds. The lower estimate follows from and Theorem 7.
The following result can be derived from Kushpel (1990).
Theorem 9: Let 1 ≤ q, p ≤ ∞, 0 < b < 1, n, denote 2m or 2m + 1and β = max {1/q-1/p, 0}. Then:
(58) |
Proof of corollary: It can be derived directly from the relation λn ≤ ρn ≤ Im and the results of Theorem 3 and Theorem 9.
APPROXIMATION OF INTEGRATION
Lemma 5: Let 1 ≤ p ≤ ∞, t ∈ T (n), Then:
(59) |
Proof of theorem 5: We first prove the upper estimates. Let us consider separately two cases: b ≥ 1and 0 < b < 1. By the monotonicity of Lp-norms, we have for p < q. So to prove the upper bound it suffices to consider . We first consider the case b ≥ 1. Since the Fourier series of a function converges uniformly. Then from the relation:
(60) |
we get:
(61) |
So we have:
(62) |
Let , then . Then:
(63) |
Now we consider 0 < b < 1. For a given m, we choose l such that m = [N1, Nl + 1]
(64) |
Using the fact Ab, s (f) ∈ T (Ns + 1):
(65) |
where, we use the asymptotic relationship 11/b >< m. Note that , then:
(66) |
Thus:
(67) |
Now we turn to the lower bounds. We consider the function:
(68) |
Set h (x) = eimx. Clearly . It is easy to prove that . Therefore we prove the lower bound.
CONCLUSION
We conjecture that the rectangle formula is optimal among all linear quadrature formulas. Note that the upper bound follows directly from Theorem 5. However it is very difficult to prove the lower bound. We will study this problem in the future work.
ACKNOWLEDGMENT
Project is supported by the Natural Science Foundation of China (Grant No. 10501026 and 10971251) and Chinese universities Scientific Fund (Grant No. 2009-2-05). Ye Peixin is supported by Program for New Century Excellent Talents in University of China.
REFERENCES
- Smale, S. and D.X. Zhou, 2003. Estimating the approximation error in learning theory. Anal. Appl., 1: 1-25.
Direct Link - Kushpel, A.K., 1990. Estimation of the widths of classes of smooth functions in the space Lq. Ukrainian Math. J., 42: 248-249.
CrossRefDirect Link