<<

. 17
( 83 .)



>>

( (
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
( 83 .)



>>