ñòð. 17 |

z J +1 cJ +1

i

f(z) = ci z + Â·Â·Â· : (4.10)

1 âˆ’ z 1J +1) âˆ’ 1 âˆ’ z(Ã¿1J +1) + 2J +1) ) âˆ’

( ( (

i=0

These expansions (4.9) and (4.10) of f(z) must be identical, and so (4.4) â€“ (4.7) follow by identi-

Ã¿cation of the coe cients.

The purpose of this algorithm is the iterative construction of the elements of the C-fraction (4.3)

starting from the coe cients ci of (4.1). However, the elements i( J ) ; Ã¿i( J ) are not vectors in the

algebra. Our next task is to reformulate this algorithm using vector quantities which are amenable

for computational purposes.

The recursion for the numerator and denominator polynomials was derived in (3.34) and (3.35)

for case of J = 0, and the more general sequence of approximants labelled by J Â¿0 was introduced

in (3.50) and (3.51). For them, the recursions are

A( J ) (z) = A( J ) (z) âˆ’ zA( J ) (z)ejâˆ’1 ej J ) ;

( J )âˆ’1 (

(4.11)

j

j+1 jâˆ’1

Bj+1 (z) = Bj J ) (z) âˆ’ zBjâˆ’1 (z)ejâˆ’1 ej J )

(J) ( (J) ( J )âˆ’1 (

(4.12)

and accuracy-through-order is expressed by

f(z)Bj J ) (z) = A( J ) (z) + ej J ) z j+J +1 + O(z j+J +2 )

( (

(4.13)

j

for j=0; 1; 2; : : : and J Â¿0. Eulerâ€™s formula shows that (4.11) and (4.12) are the recursions associated

with

J âˆ’1

cJ z J e0J ) z e0J )âˆ’1 e1J ) z e1J )âˆ’1 e2J ) z

( ( ( ( (

i

f(z) = ci z + Â·Â·Â· : (4.14)

1âˆ’1âˆ’ âˆ’ âˆ’

1 1

i=0

76 P.R. Graves-Morris et al. / Journal of Computational and Applied Mathematics 122 (2000) 51â€“80

As was noted for (3.55), the approximant of (operator) type [J + m=m] arising from (4.14) is also

a convergent of (4.14) with J â†’ J + 1. We Ã¿nd that

A( J ) (z)[B2m) (z)]âˆ’1 = [J + m=m](z) = A( J +1) [B2mâˆ’1 (z)]âˆ’1

(J ( J +1)

(4.15)

2m 2mâˆ’1

and their error coe cients in (4.13) are also the same:

e2m) = e2mâˆ’1 ;

(J ( J +1)

m; J = 0; 1; 2; : : : : (4.16)

These error vectors ei( J ) âˆˆ V obey the following identity.

C

Theorem 4.2 (The cross-rule [27,40,41,46]). With the partly artiÃ¿cial initialisation

eâˆ’2+1) = âˆž;

(J

e0J ) = cJ +1

(

for J = 0; 1; 2; : : : ; (4.17)

the error vectors obey the identity

ei+2 = ei( J +1) + ei( J ) [eiâˆ’2

( J âˆ’1) ( J +1)âˆ’1

âˆ’ ei( J âˆ’1)âˆ’1 ]ei( J ) (4.18)

for J Â¿0 and iÂ¿0.

Remark. These entries are displayed in Fig. 9 at positions corresponding to their associated approx-

imants (see (4.13)) which satisfy the compass rule.

Proof. We identify the elements of (4.3) and (4.14) and obtain

(J)

= e2jâˆ’1 e2j ) ;

( J )âˆ’1 ( J

Ã¿j+1 = e2j )âˆ’1 e2j+1 :

(J) (J (J)

(4.19)

j+1

We use (4.16) to standardise on even-valued subscripts for the error vectors in (4.19):

(J)

= e2j âˆ’1)âˆ’1 e2j ) ;

(J (J

Ã¿j+1 = e2j )âˆ’1 e2j+2 :

(J) (J ( J âˆ’1)

(4.20)

j+1

Substitute (4.20) in (4.6) with m = j + 1 and i = 2j, giving

ei( J âˆ’1)âˆ’1 ei( J ) + ei( J )âˆ’1 ei+2 = ei( J )âˆ’1 ei( J +1) + eiâˆ’2

( J âˆ’1) ( J +1)âˆ’1 ( J )

ei : (4.21)

Result (4.18) follows from (4.21) directly if i is even, but from (4.16) and (4.20) if i is odd.

Initialisation (4.17) follows from (3.50).

From Fig. 9, we note that the cross-rule can be informally expressed as

âˆ’1 âˆ’1

eS = eE + eC (eN âˆ’ eW )eC (4.22)

where e âˆˆ VC for = N; S; E; W and C. Because these error vectors are designants (see (3.31b)),

Eq. (4.22) is clearly a fundamental compass identity amongst designants.

In fact, this identity has also been established for the leading coe cients p of the numerator

Ë™

polynomials [23]. If we were to use monic normalisation for the denominators

Ë™( J )

Ë™( J )

Ë™

Q (z) = 1; Bj (z) = I; p := Aj (z)

Ë™ (4.23)

(where the dot denotes that the leading coe cient of the polynomial beneath the dot is required),

we would Ã¿nd that

pS = pE + pC (pâˆ’1 âˆ’ pâˆ’1 )pC ;

Ë™ Ë™ Ë™ Ë™N Ë™W Ë™ (4.24)

corresponding to the same compass identity amongst designants.

P.R. Graves-Morris et al. / Journal of Computational and Applied Mathematics 122 (2000) 51â€“80 77

Fig. 9. Position of error vectors obeying the cross-rule.

Reverting to the normalisation of (3.64) with q (0) = I and Q (0) = 1, we note that formula

(3.28) is required to convert (4.22) to a usable relation amongst vectors e âˆˆ Cd . We Ã¿nd that

eN eW eN eW

eS = eE âˆ’ |eC |2 H

âˆ’ + 2eC Re eC âˆ’

|eN | |eW | |eN |2 |eW |2

2 2

and this formula is computationally executable.

Implementation of this formula enables the calculation of the vectors e in Cd in a rowwise

fashion (see Fig. 9). For the case of vector-valued meromorphic functions of the type described

following (3.69) it is shown in [40] that asymptotic (i.e., as J tends to inÃ¿nity) results similar

to the scalar case are valid, with an interesting interpretation for the behaviour of the vectors ei( J )

as J tends to inÃ¿nity. It is also shown in [40] that, as in the scalar case, the above procedure is

numerically unstable, while a column-by-column computation retains stability â€“ i.e., (4.22) is used

to evaluate eE . There are also considerations of under ow and over ow which can be dealt with by

a mild adaptation of the cross-rule.

Orthogonal polynomials lie at the heart of many approximation methods. In this context, the

orthogonal polynomials are operators i ( ) âˆˆ A[ ], and they are deÃ¿ned using the functionals c{Â·}

and c{Â·}. These functionals are deÃ¿ned by their action on monomials:

c{ i } = ci ; c{ i } = ci : (4.25)

By linearity, we can normally deÃ¿ne monic vector orthogonal polynomials by 0( ) = I and, for

i = 1; 2; 3; : : : ; by

c{ i ( ) j } = 0; j = 0; 1; : : : ; i âˆ’ 1: (4.26)

The connection with the denominator polynomials (3.35) is

Theorem 4.3. For i = 0; 1; 2; : : :

) = i B2iâˆ’1 ( âˆ’1

i( ):

78 P.R. Graves-Morris et al. / Journal of Computational and Applied Mathematics 122 (2000) 51â€“80

Proof. Since B2iâˆ’1 (z) is an operator polynomial of degree i, so is i( ). Moreover, for j = 0; 1;

: : : ; i âˆ’ 1,

i i

(2iâˆ’1) (2iâˆ’1)

j i+j âˆ’1 i+jâˆ’â€˜

c{ i( )} = c{ B2iâˆ’1 ( )} = c{ Bâ€˜ } = ci+jâˆ’â€˜ Bâ€˜

â€˜=0 â€˜=0

= [f(z)B2iâˆ’1 (z)]i+j = 0

as is required for (4.26).

This theorem establishes an equivalence between approximation methods based on vector orthogo-

nal polynomials and those based on vector PadÃƒ approximation. To take account of noncommutativity,

e

more care is needed over the issue of linearity with respect to multipliers from A than is shown in

(4.26). Much fuller accounts, using variants of (4.26), are given by Roberts [41] and Salam [44,45].

In this section, we have focussed on the construction and properties of the continued fractions

associated with the leading diagonal sequence of vector PadÃƒ approximants. When these approximants

e

(0)

are evaluated at z = 1, they equal 2k , the entries on the leading diagonal of the vector epsilon table.

These entries are our natural Ã¿rst choice for use in the acceleration of convergence of a sequence

of vectors.

Acknowledgements

Peter Graves-Morris is grateful to Dr. Simon Chandler-Wilde for making his computer programs

available to us, and to Professor Ernst Weniger for his helpful review of the manuscript.

References

[1] G.A. Baker, Essentials of PadÃƒ Approximants, Academic Press, New York, 1975.

e

[2] G.A. Baker Jr., P.R. Graves-Morris, PadÃƒ approximants, Encyclopedia of Mathematics and its Applications, 2nd

e

Edition, Vol. 59, Cambridge University Press, New York, 1996.

[3] E.R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.

[4] C. Brezinski, Etude sur les -et -algorithmes, Numer. Math. 17 (1971) 153â€“162.

[5] C. Brezinski, GÃƒ nÃƒ ralisations de la transformation de Shanks, de la table de PadÃƒ et de lâ€™ -algorithme, Calcolo 12

ee e

(1975) 317â€“360.

[6] C. Brezinski, AccÃƒ lÃƒ ration de la Convergence en Analyse NumÃƒ rique, Lecture Notes in Mathematics, Vol. 584,

ee e

Springer, Berlin, 1977.

[7] C. Brezinski, Convergence acceleration of some sequences by the -algorithm, Numer. Math. 29 (1978) 173â€“177.

[8] C. Brezinski, PadÃƒ -Type Approximation and General Orthogonal Polynomials, Birkhauser, Basel, 1980.

e

[9] C. Brezinski, M. Redivo-Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, Amsterdam, 1991.

[10] S.N. Chandler-Wilde, D. Hothersall, E cient calculation of the Green function for acoustic propagation above a

homogeneous impedance plane, J. Sound Vibr. 180 (1995) 705â€“724.

[11] S.N. Chandler-Wilde, M. Rahman, C.R. Ross, A fast, two-grid method for the impedance problem in a half-plane,

Proceedings of the Fourth International Conference on Mathematical Aspects of Wave Propagation, SIAM,

Philadelphia, PA, 1998.

[12] D. Colton, R. Kress, Integral Equations Methods in Scattering Theory, Wiley, New York, 1983.

[13] F. Cordellier, Lâ€™ -algorithme vectoriel, interprÃƒ tation gÃƒ ometrique et rÃ‚ gles singuliÃ‚ res, ExposÃƒ au Colloque dâ€™Analyse

e e e e e

NumÃƒ rique de Gourette, 1974.

e

P.R. Graves-Morris et al. / Journal of Computational and Applied Mathematics 122 (2000) 51â€“80 79

[14] F. Cordellier, DÃƒ monstration algÃƒ brique de lâ€™extension de lâ€™identitÃƒ de Wynn aux tables de PadÃƒ non-normales,

e e e e

in: L. Wuytack (Ed.), PadÃƒ Approximation and its Applications, Springer, Berlin, Lecture Notes in Mathematics,

e

Vol. 765, 1979, pp. 36 â€“ 60.

[15] F. Cordellier, Utilisation de lâ€™invariance homographique dans les algorithmes de losange, in: H. Werner,

H.J. Bunger (Eds.), PadÃƒ Approximation and its Applications, Bad Honnef 1983, Lecture Notes in Mathematics,

e

Vol. 1071, Springer, Berlin, 1984, pp. 62â€“94.

[16] F. Cordellier, Thesis, University of Lille, 1989.

[17] A. Cuyt, L. Wuytack, Nonlinear Methods in Numerical Analysis, North-Holland, Amsterdam, 1987.

[18] J.-P. Delahaye, B. Germain-Bonne, The set of logarithmically convergent sequences cannot be accelerated, SIAM J.

Numer. Anal. 19 (1982) 840â€“844.

[19] J.-P. Delahaye, Sequence Transformations, Springer, Berlin, 1988.

[20] W. Gander, E.H. Golub, D. Gruntz, Solving linear systems by extrapolation in Supercomputing, Trondheim, Computer

Systems Science, Vol. 62, Springer, Berlin, 1989, pp. 279 â€“293.

[21] S. Gra , V. Grecchi, Borel summability and indeterminancy of the Stieltjes moment problem: Application to

anharmonic oscillators, J. Math. Phys. 19 (1978) 1002â€“1006.

[22] P.R. Graves-Morris, Vector valued rational interpolants I, Numer. Math. 42 (1983) 331â€“348.

[23] P.R. Graves-Morris, B. Beckermann, The compass (star) identity for vector-valued rational interpolants, Adv. Comput.

Math. 7 (1997) 279â€“294.

[24] P.R. Graves-Morris, C.D. Jenkins, Generalised inverse vector-valued rational interpolation, in: H. Werner, H.J. Bunger

(Eds.), PadÃƒ Approximation and its Applications, Vol. 1071, Springer, Berlin, 1984, pp. 144â€“156.

e

[25] P.R. Graves-Morris, C.D. Jenkins, Vector-valued rational interpolants III, Constr. Approx. 2 (1986) 263â€“289.

[26] P.R. Graves-Morris, D.E. Roberts, From matrix to vector PadÃƒ approximants, J. Comput. Appl. Math. 51 (1994)

e

205â€“236.

[27] P.R. Graves-Morris, D.E. Roberts, Problems and progress in vector PadÃƒ approximation, J. Comput. Appl. Math. 77

e

(1997) 173â€“200.

[28] P.R. Graves-Morris, E.B. Sa , Row convergence theorems for generalised inverse vector-valued PadÃƒ approximants,

e

J. Comput. Appl. Math. 23 (1988) 63â€“85.

[29] P.R. Graves-Morris, E.B. Sa , An extension of a row convergence theorem for vector PadÃƒ approximants, J. Comput.

e

Appl. Math. 34 (1991) 315â€“324.

[30] P.R. Graves-Morris, J. Van Iseghem, Row convergence theorems for vector-valued PadÃƒ approximants, J. Approx.

e

Theory 90 (1997) 153â€“173.

[31] M.H. Gutknecht, Lanczos type solvers for non-symmetric systems of linear equations, Acta Numer. 6 (1997) 271â€“

397.

[32] A. Heyting, Die Theorie der linear Gleichungen in einer Zahlenspezies mit nichtkommutatives Multiplikation, Math.

Ann. 98 (1927) 465â€“490.

[33] H.H.H. Homeier, Scalar Levin-type sequence transformations, this volume, J. Comput. Appl. Math. 122 (2000)

81â€“147.

ñòð. 17 |