Guiqiao XU Zehong LIU Hui WANG

Abstract This paper investigates the optimal recovery of Sobolev spaces −1,1],r∈N in the space L1[−1,1].They obtain the values of the sampling numbers of [−1,1]in L1[−1,1]and show that the Lagrange interpolation algorithms based on the extreme points of Chebyshev polynomials are optimal algorithms.Meanwhile,they prove that the extreme points of Chebyshev polynomials are optimal Lagrange interpolation nodes.

Keywords Worst case setting,Sampling number,Optimal Lagrange interpolation nodes,Sobolev space

1 Introduction and Main Results

Let F be a Banach space of functions defined on a compact set D that can be continuously embedded in C(D),BF is the unit ball of F,and G(F)is a normed linear space with norm‖·‖G.We want to approximate functions f from BF by using a finite number of arbitrary function values f(t)(standard information)for some t∈D.We consider only nonadaptive information.For x=(x1,x2,···,xn)∈Dn,we use Ixto denote the nonadaptive information operator,i.e.,

We say that An=ϕ◦Ixis an algorithm based on the information operator Ix,where ϕ is an arbitrary mapping from Rnto G.We also consider linear algorithms,i.e.,algorithms of the form

We use an algorithm Anto reconstruct functions from BF.The worst case error of the algorithm Anfor BF in G is defined by

For a given x=(x1,x2,···,xn)∈Dn,the worst case error for BF in G based on the information operator Ixis defined by

where the infimum is taken over all mappings ϕ from Rnto G.

We define the linear sampling numbers and the sampling numbers for BF in G by

and

respectively.If there exists an information operator Ix*and a mapping ϕ*such that the algorithm=ϕ*◦Ix*satisfies

then we call Ix*the nth optimal information andthe nth optimal algorithm.

The sampling numbers are closely related to many classical approximation problems such as width and information-based complexity,and they have a wide range of applications in numerical analysis.The aim of studying sampling numbers is to find optimal or nearly optimal information,construct optimal or nearly optimal algorithms according to the known standard information,and determine orders(or values)of the sampling numbers.

Let L1≡L1[−1,1]be the space of measurable functions defined on[−1,1],for which the norm

In recent years,the study of sampling numbers has attracted much interest,and a great number of interesting results have been obtained(see[1–15]).This paper investigates the sampling numbers of Sobolev spacesin L1.We remark that,in most cases,we can achieve only weak equivalences(orders)of the sampling numbers.In this paper,we obtain the values of the sampling numbers of Sobolev spacesin L1.To show our results,we introduce the following Lagrange interpolation algorithms.

Let x1,x2,···,xnbe n distinct points in[−1,1].Write x=(x1,x2,···,xn).Then,the Lagrange interpolation polynomial Lx(f)of a function f:[−1,1]→R based on the knots x=(x1,x2,···,xn)is defined by

where and in the following,Pnrepresents the space of all algebraic polynomials of degree at most n.The classical Lagrange interpolation formula gives

where

First,we obtain the following results.

Theorem 1.1For r∈N,we have

where

is the set of extreme points of(r+1)th Chebyshev polynomial Tr+1(x)=cos((r+1)arccosx),and

Choosing nodes is important for interpolation algorithms.Given a sufficiently smooth function,if nodes are not suitably chosen,then the interpolation polynomials do not converge to the function as the number of nodes tends to infinity.A well-known example is the Runge’s phenomenon.Hence the study of optimal interpolation nodes is a hot topic,see[16–19]and the references therein.In general,if nodes c=(c1,c2,···,cn)∈[−1,1]nsatisfies

then we call c=(c1,c2,···,cn)the nth optimal Lagrange interpolation nodes and Lcthe nth optimal Lagrange interpolation algorithm for BF in G.The value e(BF,Lc,G)is called the nth optimal Lagrange interpolation error for BF in G and we denote it as e(n,BF,G).

Using Cr≡Cr[−1,1],r=0,1,2,···represents the spaces of functions with rth order continuous derivative on[−1,1],respectively.The most important optimal Lagrange interpolation nodes problem is for C0in L∞.For n=3 and n=4,the results can be found in[20]and[21],respectively.For n≥5,it is still an open problem.For r≥1,it is well known that the rth optimal Lagrange interpolation nodes are the zeros of the rth Chebyshev polynomial Tr(x)=cos(r arccosx)for Crin L∞.In this paper,we give the rth optimal Lagrange interpolation nodes forin L1.The result is as follows.

Theorem 1.2Let r∈N.Then we have

where xrand Crare given by(1.5)and(1.6),respectively.

The remainder of this paper is organized as follows.In Section 2,we give some lemmas related to the proof of our main results.The proofs of Theorems 1.1 and 1.2 are given in Section 3 respectively.

2 Background Information

First we introduce a remainder theorem about Lagrange interpolation(see[22]).Let x0,x1,x2,···,xnbe n+1 distinct points in[−1,1].For 0≤i≤n,let

In particular,if f(xi)=0 for 1≤i≤n,x0=x,then(2.2)becomes

where x=(x1,x2,···,xn)and

Noting that x0=x,for i=1,2,···,n,from(2.1)it is easy to verify that

Hence,it follows from(2.4)that

Since Lx(f)is an algebraic polynomial of degree at most n−1,we conclude that(f−Lx(f))(n)(t)=f(n)(t)and this means f−Lx(f)∈Combining these facts with(2.3)and(2.6),we obtain

Now we introduce some information about the norms of integral operators.Let K(x,t)be a piecewise continuous function on[−1,1]2.We define

It is known that S is a linear continuous operator from L1to L1.Furthermore,let‖S‖1,1be the operator norm of S from L1to L1.Then it is known that

Lemma 2.1Let−1≤x1

where Bx(x,t)is given by(2.5).

ProofIf f∈then it follows from(2.7)with n=r that

Let

Then it follows from(2.8)and(2.10)that

By(1.1)and(2.12),we conclude that

On the other hand,for any g∈L1[−1,1],let

By a direct computation,we obtain

From(2.10)and(2.14)it follows that

By(2.15),we obtain

From(1.1),(2.8)and(2.16)it follows that

Combining(2.13)with(2.17),we obtain(2.9).This completes the proof of Lemma 2.1.

An n-dimensional subspace G of C[−1,1]is called a weak Chebyshev subspace if every function g∈G has at most n−1 sign changes.By[23,Theorem 6.3]we know that for every n-dimensional weak Chebyshev subspace of C[−1,1],there exists a set of n-canonical points t1<···

holds for all g∈G,where t0=−1 and tn+1=1.

If G is a weak Chebyshev subspace of C[−1,1],then the set

is called the convexity cone of G.

Lemma 2.2(see[23,Theorem 6.6])Let G be an n-dimensional weak Chebyshev subspace of C[−1,1].If the set{t1,···,tn}of canonical points of G is poised with respect to G,then every function f∈K(G)has a unique best L1-approximation gffrom G and gfis uniquely determined by

Lemma 2.3(see[24,Lemma 4.3])For x=(x1,x2,···,xr)∈[−1,1]r,we have

3 Proofs of Theorem 1.1 and Theorem 1.2

Proof of Theorem 1.1We consider the upper estimate first.Let xrbe given by(1.5).Then,the Lagrange interpolation algorithm Lxris a linear algorithm.Hence,it follows from(2.9)that

We will compute the last integration in(3.1).For t=−1,we havePr−1.For t=1,we have=0∈Pr−1.Hence from(2.5)it follows that Bxr(x,t)=0 for t=±1.This means that

Next we consider t∈(−1,1).It is known that Pris a Chebyshev subspace of C[−1,1].Furthermore,from[23,Theorem 4.10]we know that the canonical points for Pron[−1,1]are the extreme points of the Chebyshev polynomial Tr+2in(−1,1),i.e.,

For t∈(−1,1),it is obvious that there exists an Ntwith 0≤Nt≤r such that t∈Then(3.4)becomes

By(3.5)and a direct computation,we obtain

From(3.1)–(3.2)and(3.6)we obtain the upper estimate.

Now we consider the lower estimate.Let x1,x2,···,xrbe r arbitrary distinct points in[−1,1]and x=(x1,x2,···,xr).Combining Lemma 2.3 with(2.6)as well as(f−Lx(f))(r)(x)=f(r)(x),we obtain

From(3.7)and(2.9)it follows that

From(1.2)and(3.8)–(3.9)we obtain the lower estimate.This completes the proof of Theorem 1.1.

Proof of Theorem 1.2From(1.4)we obtain the upper estimate.On the other hand,from(2.9),(3.9)and(1.7)we obtain the lower estimate.The proof of Theorem 1.2 is completed.

Note 1The values of Crcan be computed for r=1,2,···,respectively.For example,We guess that

where[x]represents the integer part of x.

Note 2In practice,one often wants to have boundary points as interpolation nodes,i.e.,

Then the following question arises:For which sets of points−1

Papers[15,18]considered this problem recently.Obviously,from(2.9)it follows that c=(−1,c2,···,cr−1,1)is the solution of(3.10)forin L1if and only if

To each integer r>2,we can compute the solution of(3.10)forin L1by using(3.11).But the explicit solution to this problem is an open problem.

Note 3When nr,the values of the sampling numbers and the nth optimal Lagrange interpolation nodes of the problems given by(1.7)and(3.10)forin L1are open problems.

AcknowledgementThe authors thank the referees for their valuable advices.