<<

. 73
( 83 .)



>>

[29] A. Neumaier, Solving ill-conditioned and singular linear systems: a tutorial on regularization, SIAM Rev. 40 (3)
(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
( 83 .)



>>