uj z = uj’1 + bj uj j0 + 1 ¡ j6k; j = ji + 1; i = 0; : : : ; q ’ 1: (84)

Eqs. (81) and (82) are obvious and (83) and (84) follow from (74). The rest of the proof consists

in comparing coe cients.

k+1 k

Remark. (i) The arithmetical complexity for computing (c1; j )j=1; :::; k+1 from (c1; j )j=1; :::; k and

(c2; j )j=1; :::; k according to (57) “ (64) in cases (i) or (ii) is O(k + 1 + q (nr ’ 1)2 ) and O(k + 1) in

k

r=0

case (iii).

(ii) It should be noticed that the ÿrst term in (58) resp. (61) is the recursion (36) with p1 ; p2

k k

replaced by c1; j ; c2; j and with z = bj : Similarly, the ÿrst term in (57), (60), (62) and (63) is recursion

k k

(37) with p1 ; p2 replaced by c1; j ; c2; j and with z = bj :

Consider once more the example given in Section 2.3. According to Proposition 5 we compute

the triangular ÿeld of solutions

k

u ; : : : ; uk

=p 1

pik k

=: ci; j · uj ; k = 1; : : : ; 5; i = 1; : : : ; 6 ’ k:

ai ; : : : ; ai+k j=1

The initializations which are certain generalized Taylor polynomials of f are computed according

to Proposition 4, or alternatively, according to (38) and (39).

220 G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222

u1 u1 u2 u1 u2 u3

ai p p p

· ·· ···

3

u1

0 p = · u1

0 2

3

u1 u2

0 p = ’2·z

0 0 2

3 33 1 51

u1 u u2 u1 u2 u3

p1

1 p = · u1 = ’ ·z p = ’2 + · z +

1 0 1 001

4 24 2 2 z+1

93 31

u1 u2 uuu

p 123=

1 p = ’ ·z

0 1 011

88 2 z+1

9 1 1 1 11 1

u1 u1 u2 uuu

p 1 2 3 =’ +

’2 p = ’ · u1 p = ’ +z ·z+

’2 1 ’2 1 1 ’2

8 4 4 12 6 z+1

1 51 1

u1 u2 u3 u4

p =2’ z’ +2 ;

0011 2 2 z+1 (z + 1)2

1 1 11 1 1 1

u1 u2 u3 u4

p =’ + z+ ’ ;

0 1 1 ’2 6 24 6 z + 1 6 (z + 1)2

1 7 73 1 5 1 13 1

u1 u2 u3 u4 u5

p =’ + z+ + + :

0 0 1 1 ’2 54 z + 1 9 (z + 1]2 27 z ’ 2

6 12

For a theory of convergence of rational interpolants with prescribed poles to analytic functions as

N ’ ∞ confer [1].

5. Applications

CV-systems have been used to construct rational B-splines with prescribed poles. A. Gresbrand

[8] has found a recursion fomula for such splines that reduces to de Boor™s recursion when all poles

are at inÿnity. Given a weakly increasing sequence t = (tj )m+1 of knots in [a; b] where t0 = a and

j=0

tm+1 = b are simple knots and ti ¡ ti+n’1 for all i. The extended knot sequence is text = (tj )m+n

j=’n+1

where a and b are repeated precisely n times each. Given a pole sequence (b1 ; : : : ; bn ) ∈ R \ [a; b]

that is consistently ordered with b1 = ∞, then for j = 0; : : : ; m deÿne

1 1

B0 := and Bj :=

[t0 ;t1 ] (tj ;tj+1 ]

with S denoting the characteristic function of a set S and for k = 2; : : : ; n and for j = ’k + 2; : : : ; m

deÿne

˜=1; :::; k’1

perm (tj+i ’ b˜+1 )i=1; :::; k’1

x ’ tj 1

k

j (x):= ;

˜=1; :::; k’2

tj+k’1 ’ tj (k ’ 1)(x ’ bk )— perm (tj+i ’ b˜+1 )i=1; :::; k’2

˜=1; :::; k’1

perm (tj+i’1 ’ b˜+1 )i=1; :::; k’1

tj+k’ 1 ’ x 1

k

j (x):= ;

˜=1; :::; k’2

tj+k’1 ’ tj (k ’ 1)(x ’ bk )— perm (tj+i ’ b˜+1 )i=1; :::; k’2

G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222 221

where the permanent of a matrix A = (ai; j ) ∈ Kn—n is deÿned as

n

perm A = ai; (i) :

∈Sn i=1

Here Sn denotes the symmetric group of all permutations of order n. Then for k = 2; : : : ; n and

j = ’k + 1; : : : ; m

k k k’1 k k’1

Bj (x):= j (x)Bj (x) + j+1 (x)Bj+1 (x) (85)

are rational B-splines of order k with prescribed poles (b1 ; : : : ; bk ), i.e., when restricted to any knot

k

interval then Bj belongs to the CV-space Uk . Gresbrand [8] has proved that

˜=1; :::; k’1

perm (tj+i ’ b˜+1 )i=1; :::; k’1 k

k

Bj (x) = Nj (x); (86)

(k ’ 1)!Bk (x)

where Bk is the pole polynomial associated with the pole system (b1 ; : : : ; bk ) and Njk (x) = (tj+k ’

k’1

tj )[tj ; : : : ; tj+k ](· ’ x)+ is the ordinary polynomial B-spline function of order k with knots tj ; : : : ; tj+k .

The rational B-splines with prescribed poles (84) share many properties with the de Boor B-splines

[8]:

1. They can be computed recursively by a de Boor like algorithm, see (83).

supp Bj = supp Njk = [tj ; tj+k ]:

k

2.

Bj has precisely the same smoothness as Njk i all poles are chosen in the exterior of [a; b].

k

3.

k

4. Bj is nonnegative.

k

5. The Bj form a partition of unity.

6. There are knot insertion algorithms.

7. There is a simple connection with NURBS.

The prescribed poles can serve as additional shape-controlling parameters. Given a knot sequence t

and a controll polygon corresponding to text by suitably choosing the poles “corners” of the B-spline

curve can be generated which are more or less sharp while maintaining the smoothness properties

„

controlled by the knot sequence. The splines (84) are an example of Ceby„evian splines which

s

when restricted to any knot interval belong to the same CV-space Uk . In other words for each knot

interval the spline curve has the same poles outside of [a; b]: Clearly, one can consider also the

more general case where in each knot interval (ti ; ti+1 ] individually for the spline curve poles are

prescribed outside [ti ; ti+1 ]. Not surprisingly, then the computation is more laborous, but we expect

also in the general case existence of a recursive procedure [4].

We conclude with mentioning another application. Recently, interpolants from CV-spaces have

been proved useful for approximation of transfer functions of inÿnite-dimensional dynamical systems

[19].

References

[1] A. Ambroladze, H. Wallin, Rational interpolants with prescribed poles, theory and practice, Complex Variables 34

(1997) 399“413.

[2] I. Berezin, N. Zhidkov, Computing Methods, Vol. 1, Addison-Wesley, Reading, MA, 1965.

222 G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222

[3] C. Brezinski, The Muhlbach“Neville“Aitken algorithm and some extensions, BIT 20 (1980) 444“451.

[4] B. Buchwald, Computation of rational B-splines with prescribed poles, in preparation.

[5] C. Carstensen, G. Muhlbach, The Neville“Aitken formula for rational interpolants with prescribed poles, J. Comput.

Appl. Math. 26 (1992) 297“309.

[6] T. Finck, G. Heinig, K. Rost, An inversion formula and fast algorithm for Cauchy“Vandermonde matrices, Linear

Algebra Appl. 183 (1995) 179“191.

[7] M. Gasca, J.J. Martinez, G. Muhlbach, Computation of rational interpolants with prescribed poles, J. Comput. Appl.

Math. 26 (1989) 297“309.

[8] A. Gresbrand, Rational B-splines with prescribed poles, Numer. Algorithms 12 (1996) 151“158.

[9] G. Heinig, K. Rost, Recursive solution of Cauchy“Vandermonde systems of equations, Linear Algebra Appl. 218

(1995) 59“72.

[10] G. Muhlbach, A recurrence formula for generalized divided di erences and some applications, J. Approx. Theory 9

(1973) 165“172.

„

[11] G. Muhlbach, Neville-Aitken algorithms for interpolation of Ceby„ev systems in the sense of Newton and in a

s

generalized sense of Hermite, in: A.G. Law, B.N. Sahney (Eds.), Theory of Approximation and Applications,

Academic Press, New York, 1976, pp. 200“212.

[12] G. Muhlbach, On Hermite interpolation by Cauchy“Vandermonde systems: the Lagrange formula, the adjoint and

the inverse of a Cauchy“Vandermonde matrix, J. Comput. Appl. Math. 67 (1996) 147“159.

[13] G. Muhlbach, Linear and quasilinear extrapolation algorithms, in: R. Vichnevetsky, I. Vignes (Eds.), Numerical

Mathematics and Applications, Elsevier Science Publishers, IMACS, Amsterdam, 1986, pp. 65“71.

[14] G. Muhlbach, On interpolation by rational functions with prescribed poles with applications to multivariate

interpolation, J. Comput. Appl. Math. 32 (1990) 203“216.

[15] G. Muhlbach, Computation of Cauchy“Vandermonde determinants, J. Number Theory 43 (1993) 74“81.

[16] G. Muhlbach, The recurrence relation for generalized divided di erences with respect to ECT-systems, Numer.

Algorithms 22 (1999) 317“326.

[17] G. Muhlbach, L. Reimers, Linear extrapolation by rational functions, Exponentials and logarithmic functions,

J. Comput. Appl. Math. 17 (1987) 329“344.

[18] L. Reimers, Lineare Extrapolation mit Tschebysche -Systemen rationaler und logarithmischer Funktionen,

Dissertation, Universitat Hannover, 1984.

[19] A. Ribalta Stanford, G. LÃ pez Lagomasino, Approximation of transfer functions of inÿnite dimensional dynamical

o

systems by rational interpolants with prescribed poles, Report 433, Institut fur Dynamische Systeme, Universitat

Bremen, 1998.

[20] J. Walsh, Interpolation and approximation by rational functions in the complex domain, Amer. Math. Soc. Colloq.

Publ., Vol. 20, American Mathematical Society, Providence, RI, 1960.

Journal of Computational and Applied Mathematics 122 (2000) 223“230

www.elsevier.nl/locate/cam

The E-algorithm and the Ford“Sidi algorithm

Naoki Osada

Tokyo Woman™s Christian University, Zempukuji, Suginamiku, Tokyo 167-8585, Japan

Received 26 April 1999; received in revised form 15 February 2000

Abstract

The E-algorithm and the Ford“Sidi algorithm are two general extrapolation algorithms. It is proved that the E-algorithm

and the Ford“Sidi algorithm are mathematically (although not operationally) equivalent. A slightly more economical

algorithm is given. Operation counts are discussed. c 2000 Elsevier Science B.V. All rights reserved.

Keywords: Extrapolation method; Acceleration of convergence; E-algorithm; Ford“Sidi algorithm

1. Introduction

Let (sn ) be a sequence and (gj (n)), j = 1; 2; : : : ; be known auxiliary sequences. Suppose that there

exist unknown constants (cj ), j = 1; : : : ; k, such that

k

Tk(n)

sn+i = + cj gj (n + i); i = 0; : : : ; k: (1)

j=1

If the system of linear equations (1) is nonsingular, then by Cramer™s rule Tk(n) can be expressed as

the ratio of two determinants

sn · · · sn+k 1 ··· 1

g1 (n) · · · g1 (n + k) g1 (n) · · · g1 (n + k)

Tk(n) = : (2)

··· ···

gk (n) · · · gk (n + k) gk (n) · · · gk (n + k)

Many known sequence transformations which are used to accelerate the convergence are of the form

(sn ) ’ (Tk(n) ). (For a review, see [2].) Two famous recursive algorithms are known to compute

Tk(n) . One is the E-algorithm proposed by Schneider [6], Havie [5] and Brezinski [1], independently.

E-mail address: osada@twcu.ac.jp (N. Osada)

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 6 6 - 6

224 N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230

Schneider and Havie derived it using Gaussian elimination while Brezinski using Sylvester™s de-

terminantal identity. The other is the Ford“Sidi algorithm [4], which requires a smaller number of

arithmetic operations than the E-algorithm. Ford and Sidi derived their algorithm using Sylvester™s

identity.

Ford and Sidi [4] mentioned the main di erence of the recursion of the E-algorithm and that of

the Ford“Sidi algorithm. Brezinski and Redivo Zaglia [3] derived the E-algorithm and the Ford“Sidi

algorithm using annihilation di erence operators and gave the relations between the two algorithms.

In this paper we show that the E-algorithm and the Ford“Sidi algorithm are mathematically equiv-

alent in the following sense: two algorithms are computing the same quantities but in a di erent

way, and the recurrence relations of the E-algorithm can be derived from those of the Ford“Sidi

algorithm, and vice versa.

In Section 2 we review the recurrence relations and the number of operation counts of the two