ñòð. 73 |

(1998) 636â€“666.

[30] M. Rauth, T. Strohmer, Smooth approximation of potential Ã¿elds from noisy scattered data, Geophysics 63 (1)

(1998) 85â€“94.

[31] L. Reichel, G. Ammar, W. Gragg, Discrete least squares approximation by trigonometric polynomials, Math. Comp.

57 (1991) 273â€“289.

[32] R.D. Richtmeyer, K.W. Morton, Di erence Methods for Initial-Value Problems, Krieger, Malabar, FL, 1994.

[33] I.W. Sandberg, The reconstruction of band-limited signals from nonuniformly spaced samples, IEEE Trans. Circuit

Theory 41 (1) (1994) 64â€“66.

[34] O. Scherzer, T. Strohmer, A multi-level algorithm for the solution of moment problems, Numer. Funct. Anal. Opt.

19 (3â€“ 4) (1998) 353â€“375.

[35] C. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948) 379â€“623.

[36] D. Slepian, Prolate spheroidal wave functions, fourier analysis and uncertainty V: the discrete case, Bell System

Tech. 57 (1978) 1371â€“1430.

[37] T. Strohmer, Computationally attractive reconstruction of band-limited images from irregular samples, IEEE Trans.

Image Proc. 6 (4) (1997) 540â€“548.

[38] E.E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra

Appl. 232 (1996) 1â€“43.

[39] J.M. Varah, The prolate matrix, Linear Algebra Appl. 187 (1993) 269â€“278.

[40] D.J. Wingham, The reconstruction of a band-limited function and its Fourier transform from a Ã¿nite number of

samples at arbitrary locations by singular value decomposition, IEEE Trans. Circuit Theory 40 (1992) 559â€“570.

[41] K. Yao, J.O. Thomas, On some stability and interpolatory properties of nonuniform sampling expansions, IEEE

Trans. Circuit Theory 14 (1967) 404â€“408.

[42] J.L. Yen, On nonuniform sampling of bandwidth-limited signals, IRE Trans. Circuit Theory CT-3 (1956) 251â€“257.

[43] M.C. Yeung, R.H. Chan, Circulant preconditioners for Toeplitz matrices with piecewise continuous generating

functions, Math. Comp. 61 (204) (1993) 701â€“718.

[44] A.I. Zayed, Advances in Shannonâ€™s Sampling Theory, CRC Press, Boca Raton, FL, 1993.

Journal of Computational and Applied Mathematics 122 (2000) 317â€“328

www.elsevier.nl/locate/cam

Asymptotic expansions for multivariate polynomial

approximation

Guido Walz âˆ—

Department of Mathematics and Computer Science, University of Mannheim, D-68131 Mannheim, Germany

Received 29 January 1999; received in revised form 30 August 1999

Abstract

In this paper the approximation of multivariate functions by (multivariate) Bernstein polynomials is considered. Building

on recent work of Lai (J. Approx. Theory 70 (1992) 229 â€“242), we can prove that the sequence of these Bernstein

polynomials possesses an asymptotic expansion with respect to the index n. This generalizes a corresponding result due

to Costabile et al. (BIT 36 (1996) 676 â€“ 687) on univariate Bernstein polynomials, providing at the same time a new

proof for it. After having shown the existence of an asymptotic expansion we can apply an extrapolation algorithm which

accelerates the convergence of the Bernstein polynomials considerably; this leads to a new and very e cient method for

polynomial approximation of multivariate functions. Numerical examples illustrate our approach. c 2000 Elsevier Science

B.V. All rights reserved.

Keywords: Asymptotic expansion; Bernstein operator; Convergence acceleration; Extrapolation; Multivariate polynomial

approximation

1. Introduction and preliminaries

One of the fundamental questions in extrapolation theory is the following one: Can the convergence

of a given sequence be accelerated by a suitable extrapolation algorithm or not? The oldest and up

the present day most widespread criterion for a positive answer to this question is the existence of an

asymptotic expansion for the sequence to be accelerated (see the next section for exact deÃ¿nitions).

This is the reason why the terms asymptotic expansion and extrapolation are so deeply connected.

Now, the next question is: Where in Applied Analysis do exist sequences with this property? It is

the main reason of this paper, which is both a survey and a research paper, to convince the reader

that this is the case also in a Ã¿eld where this was not so well-known until now: Approximation of

multivariate functions by polynomials.

âˆ—

Tel.: +49-621-292-5341; fax: +49-621-292-1064.

E-mail address: walz@math.uni-mannheim.de (G. Walz)

0377-0427/00/$ - see front matter c 2000 Elsevier Science B.V. All rights reserved.

PII: S 0 3 7 7 - 0 4 2 7 ( 0 0 ) 0 0 3 5 8 - 7

318 G. Walz / Journal of Computational and Applied Mathematics 122 (2000) 317â€“328

We Ã¿rst shortly review what kind of asymptotic expansion we are looking at, and what the

corresponding extrapolation process looks like. For more details on these topics, see [7].

DeÃ¿nition. Let there be given a sequence of real or complex numbers { n } and natural numbers m

and N . The sequence { n } is said to possess an asymptotic expansion of order m, if each n for

n Â¿ N can be written in the form

m m

c c

âˆ’Re m

+ o(nâˆ’Re m ) for n â†’ âˆž:

n= + o(n ) = c0 + (1)

n n

=0 =1

Here, the exponents { } are real or complex numbers with the property

= 0 and Re Â¡ Re for all âˆˆ N0 :

0 +1

Moreover, if a sequence { n } possesses an expansion of type (1) for all m âˆˆ N, then we say that

the expansion is of arbitrary order, and write

c

n = c0 + (2)

n

=1

for short.

Asymptotic expansions if the type (1) are sometimes also denoted in more detail as logarithmic

asymptotic expansions (see [5] or [7]). In this paper, we will use the abbrevatied notation asymptotic

expansion only.

It is well known (cf., e.g., [1,7]) that the basic idea of extrapolation applied to such sequences is to

compute the values of n for several choices of n, say n=n0 Â¡ n1 Â¡ n2 Â¡ Â· Â· Â·, and to combine them in

order to obtain new sequences, which converge faster than the original ones. For many applications

it is convenient to choose the sequence {ni } not just anyhow, but as a geometric progression: With

natural numbers n0 and b, bÂ¿2, we put

ni :=n0 bi ; i = 0; 1; 2; : : : : (3)

Then the extrapolation process reads as follows (cf. (4)):

Lemma 1. Let there be given a sequence { n }; which possesses an asymptotic expansion of the

form (1); and a sequence of natural numbers {ni }; satisfying (3). Furthermore; choose some K âˆˆ N;

K6m and deÃ¿ne for k = 0; : : : ; K new sequences {yi(k) }iâˆˆN through the process

yi(0) = ni ; i = 0; 1; : : : ;

b k Â· yi+1 âˆ’ yi(kâˆ’1)

(kâˆ’1)

k = 1; 2; : : : ; K;

yi(k) = (4)

i = 0; 1; : : : :

b k âˆ’1

Then each of the sequences {yi(k) }iâˆˆN possesses an asymptotic expansion of the form

m

c(k)

yi(k) + o(nâˆ’Re m )

= c0 + for ni â†’ âˆž (5)

i

ni

=k+1

with coe cients c(k) independent of ni . In particular; each of the sequences {yi(k) } converges faster

to the limit c0 than its precedessor.

G. Walz / Journal of Computational and Applied Mathematics 122 (2000) 317â€“328 319

So, the message is: If one has a convergent numerical process of whatever kind, say, a discretized

di erential equation or a quadrature formula, one should always check whether the output of this

process has a asymptotic expansion. Experience says that this is indeed the case in much more

situations than commonly expected or known.

To illustrate and to support this remark, we consider in this paper the Bernstein polynomial

operators (or Bernstein polynomials), which are in Approximation Theory well known as a tool

for polynomial approximation of functions. It will be shown that the sequence of these operators

also possesses an asymptotic expansion, and thus that their order of convergence can be improved

considerably using extrapolation. In the univariate case, this result was proved quite recently in [2]

(see Theorem 2). As the main new contribution, we develop an anloguous result for the multivariate

case. Since the proof in [2] cannot be adopted for the multivariate case, we had to develop a new

approach, building on results published in [3]. This provides at the same time a new proof also for

the univariate case.

2. Asymptotic expansion for the Bernstein operator

We Ã¿rst brie y review some results on the univariate case and then prove our main result

(Theorem 5) on the multivariate one.

The sequence of Bernstein operators

n

Bn (f; x):= f Bn; (x); (6)

n

=0

deÃ¿ned for any f âˆˆ C[0; 1], converges uniformly to f on [0; 1]. Here, Bn; (x) denotes the (univariate)

Bernstein polynomial

n

x (1 âˆ’ x)nâˆ’ :

Bn; (x):=

However, as shown by Voronowskaja [6], we have

x(1 âˆ’ x) (2)

lim n (Bn (f; x) âˆ’ f(x)) = f (x) (7)

2

nâ†’âˆž

in each point x âˆˆ [0; 1] where f(2) (x) exists.

This means that already quadratic polynomials are not reproduced by Bn (f; Â·), and that the order

of convergence is not better than O(1=n). Therefore, several attempts have been made to improve

this order of convergence, see [2] for an overview and some references.

In view of asymptotic expansion and extrapolation theory, a big step was done recently in [2],

who established the asymptotic expansion for the Bernstein operator Bn . Their main result can be

stated as follows:

Theorem 2. Let f âˆˆ C 2k [0; 1] with some k âˆˆ N. Then the sequence {Bn (f; x)}; deÃ¿ned in (6);

possesses an asymptotic expansion of the form

k

c (x)

+ o(nâˆ’k )

Bn (f; x) = f(x) + for n â†’ âˆž:

n

=1

320 G. Walz / Journal of Computational and Applied Mathematics 122 (2000) 317â€“328

It is our goal to develop an analoguous result for the multivariate case.

However, we do not generalize the proof given in [2], which could by the way be shortened

considerably by using the asymptotic results already to be found in [4]. Instead, we will make

use of some asymptotic relations for multivariate Bernstein polynomials, established quite recently

in [3].

Let v0 ; : : : ; vs be (s + 1) distinct points in Rs , such that the volume of the s-simplex T := v0 ; : : : ; vs

is positive. For each point x âˆˆ T , we denote by ( 0 ; : : : ; s ) the barycentric coordinates of x w.r.t. T .

It is well known that any polynomial pn (x) of total degree n can be expressed by using the basic

functions

| |!

âˆˆ Ns+1 with | | = n

B ( ):= ; 0

!

in the form

pn (x) = c B ( ); x âˆˆ T:

| |=n

âˆˆNs+1

0

Here, as usual, for any = ( 0 ; : : : ; s ) âˆˆ Ns+1 , we set | | = + Â·Â·Â· + and ! = 0! Â· Â· Â· s !. Also,

0 s

0

it is = 00 Â· Â· Â· s s .

For each âˆˆ Ns+1 , denote by x the point

0

s

1 i

x := iv :

|| i=0

We consider the approximation of a given function f âˆˆ C(T ) by the multivariate Bernstein polyno-

mial

Bn (f; x):= f(x )B ( ): (8)

| |=n

âˆˆNs+1

0

As in [3], we introduce the auxiliary polynomials

S n (x) = n| | (x âˆ’ x) B ( )

| |=n

âˆˆNs+1

0

âˆˆ Ns . The following results, which we will make use of below, were proved in [3].

for 0

Theorem 3. The polynomials S n possess the explicit representations

Sn â‰¡ 0 for | |61;

s

n j

S (x) = n j (v âˆ’ x) for | | = 2;

j=0

and ï£« ï£¶

| |âˆ’2 s

i

ï£ âˆ’ x)Ã¿ ï£¸

S n (x) = j

n(n âˆ’ 1) Â· Â· Â· (n âˆ’ + 1) j (v for | |Â¿3:

=1 i=1 j=0

Ã¿1 ;:::;Ã¿ âˆˆNs

0

Ã¿1 +Â·Â·Â·+Ã¿ =

|Ã¿i |Â¿2; i=1;:::;

G. Walz / Journal of Computational and Applied Mathematics 122 (2000) 317â€“328 321

Theorem 4. For k âˆˆ N and f âˆˆ C 2k (T ); we have

ï£® ï£¹

ï£¯ ï£º

1 S n (x)

ï£¯ ï£º

k

ñòð. 73 |