School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China

**Li Xuehua**

College of Science, China Agricultural University, Beijing 100083, China

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

Ye Peixin and Li Xuehua, 2011. Optimal Approximation of Function and Integration on Some Analytic Classes. *Information Technology Journal, 10: 2196-2201.*

**DOI:** 10.3923/itj.2011.2196.2201

**URL:** https://scialert.net/abstract/?doi=itj.2011.2196.2201

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∈L_{P} 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 ∈ L_{p} and K ∈ L_{1}. 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∈L_{1} 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, x^{1} = 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 I_{m} maps a continuous function f to the trigonometric polynomial I_{m} (f) ∈ T (m) such that:

(13) |

Therefore I_{m} 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 a_{n} and b_{n}, the notation a_{n} << b_{n} means that there are some constant C and some n_{0} ∈ N such that a_{n} ≤ cb_{n} for all n≥n_{0}. The asymptotic notation a_{n} >< b_{n} means that a_{n} << b_{n} and b_{n} << a_{n}. 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 g_{r, 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) |

D_{1} = {(p, q): 1 ≤ q < 2 and 2 < p ≤ ∞} and D_{2} = D/D1.

**Corollary:** Let (p, q) ∈ D_{2} 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 q_{m} (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 ∈ L_{p}, the error of the best approximation of f by the elements of T (m) in the L_{p}-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 S_{m} the operator of taking the partial sum of order m. Then for f ∈ L_{1}, we have:

(32) |

For a class of functions F, let us denote the error of Fourier method on F by:

(33) |

For F ⊂ L_{p}, 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 {u_{1}, u_{2}, …, u_{m}}, 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 L_{p}. Here the infimum is taken over all linear operators A acting from F to L_{p} 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 L_{1} by the formula:

(41) |

Noting that V_{n} (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 L_{p}-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 e_{k} (x) = e^{ikx}. We represent in the form:

(44) |

Let . Then . Using the property I_{m} (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 d_{2m + 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 N_{1} = 1 and .

Denote n_{s} = N_{s +1}. It follows from the definition that for all s:

(48) |

and n_{s}>< s^{1/b-1}.

We define the following functions:

(49) |

and:

(50) |

For f ∈ L_{1}, define the operator A_{b, S} by:

(51) |

Then we recall the following known results from Temlyakov (1985).

**Lemma 2:** Let 1 ≤ p ≤ ∞, f, g ∈ L_{p} 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 L_{p}. Let's denote it by g. The function A_{b, s} (f) can have nonzero Fourier coefficients only in (-N_{s + 1}, -N_{s-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 ∈ [N_{l}, N_{l + 1}] By Theorem 8 we represent as:

Use the fact A_{b, s} (f) ∈ T (N_{s + 1}-1). Note that the function A_{b, s} (f) can have nonzero Fourier coefficients only in (-N_{s + 1}, -N_{s-1}) ∪ (n_{s-1}, N_{s + 1}). By Nikol'ski inequality, we have:

Then:

(56) |

where, we use the asymptotic relationship 1^{1/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} ≤ I_{m} 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 L_{p}-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 = [N_{1}, N_{l + 1}]

(64) |

Using the fact A_{b, s} (f) ∈ T (N_{s + 1}):

(65) |

where, we use the asymptotic relationship 1^{1/b} >< m. Note that , then:

(66) |

Thus:

(67) |

Now we turn to the lower bounds. We consider the function:

(68) |

Set h (x) = e_{imx}. Clearly . It is easy to prove that . Therefore we prove the lower bound.

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.

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.

- 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 L
_{q}. Ukrainian Math. J., 42: 248-249.

CrossRefDirect Link