ñòð. 46 |

discussed. c 2000 Elsevier Science B.V. All rights reserved.

MSC: 41A05; 65D05

Keywords: Prescribed poles; Cauchyâ€“Vandermonde systems; Interpolation algorithms

1. Cauchyâ€“Vandermonde systems; deÃ¿nitions and notations

Let

B = (b1 ; b2 ; : : :) (1)

be a given sequence of not necessarily distinct points of the extended complex plane C = C âˆª {âˆž}:

With B we associate a system

U = (u1 ; u2 ; : : :) (2)

of basic rational functions deÃ¿ned by

z j (bj ) if bj = âˆž;

uj (z) = (3)

(z âˆ’ bj )âˆ’( j (bj )+1) if bj âˆˆ C:

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 4 - 2

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

Here

j (b) is the multiplicity of b in the sequence (b1 ; : : : ; bjâˆ’1 ): (4)

The system U has been called [18,17,15,13,12,5] the Cauchyâ€“Vandermonde system (CV-system for

brevity) associated with the pole sequence B. By N we denote the set of positive integers. For any

Ã¿xed N âˆˆ N to the initial section of B

BN = (b1 ; : : : ; bN ) (5)

there corresponds the basis

UN = (u1 ; : : : ; uN ) (6)

of the N -dimensional Cauchyâ€“Vandermonde space UN :=span UN : Indeed, for every N âˆˆ N UN is

Ã„s

an extended complete CebyÃ„ev system on C \ {b1 ; : : : ; bN }: This follows from

Proposition 1. For any system

A = (a1 ; a2 ; : : :) (7)

of not necessarily distinct complex numbers ai such that A and B have no common point, for

every N âˆˆ N and for every complex function f which is deÃ¿ned and su ciently often di erentiable

at the multiple nodes of the initial section

AN = (a1 ; : : : ; aN ) (8)

of A there is a unique p âˆˆ UN that satisÃ¿es the interpolation conditions

i (ai )

d

(p âˆ’ f)(ai ) = 0; i = 1; : : : ; N: (9)

dz

Here

i (a) is the multiplicity of a in the sequence (a1 ; : : : ; aiâˆ’1 ): (10)

We also express the interpolation conditions by saying that u agrees with f at a1 ; : : : ; aN counting

multiplicities. There is a simple proof due to Walsh [20] reducing it to interpolation by algebraic

polynomials. Before repeating this proof we will introduce some notations to simplify formulas to

be derived later. We sometimes will assume that the systems AN of nodes and BN of poles are

consistently ordered, i.e.,

AN = ( 1 ; : : : ; 1; 2; : : : ; 2; : : : ; p; : : : ; p ); (11)

m1 m2 mp

BN = (Ã¿0 ; : : : ; Ã¿0 ; Ã¿1 ; : : : ; Ã¿1 ; : : : ; Ã¿qâˆ’1 ; Ã¿q ; : : : ; Ã¿q ) (12)

n0 n1 nq

corresponding with

1 1 1 1

UN = 1; z; : : : ; z n0 âˆ’1 ; ;:::; ;:::; ;:::; ; (13)

z âˆ’ Ã¿1 (z âˆ’ Ã¿1 )n1 z âˆ’ Ã¿q (z âˆ’ Ã¿q )nq

where 1 ; : : : ; p and Ã¿0 ; Ã¿1 ; : : : ; Ã¿q are pairwise distinct and m1 + Â· Â· Â· + mp = N; mi Â¿0 and n0 + n1 +

Â· Â· Â· + nq = N; n0 Â¿0; ni Â¿1 for i âˆˆ {1; : : : ; q}, respectively. In most cases, we will assume Ã¿0 = âˆž to

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

be in front of the other poles corresponding with (13), in some considerations we assume Ã¿0 = âˆž

at the end of the pole sequence (12),

BN = (Ã¿1 ; : : : ; Ã¿1 ; : : : ; Ã¿qâˆ’1 ; Ã¿q ; : : : ; Ã¿q ; Ã¿0 ; : : : ; Ã¿0 ; ) (14)

n1 n0

nq

corresponding with

1 1 1 1

; 1; z; : : : ; z n0 âˆ’1 :

UN = ;:::; ;:::; ;:::; (15)

z âˆ’ Ã¿1 (z âˆ’ Ã¿1 ) z âˆ’ Ã¿q (z âˆ’ Ã¿q ) nq

n1

Notice that p; m1 ; : : : ; mp as well as q; n0 ; : : : ; nq do depend on N . Of course, there is no loss of

generality in assuming that the nodes and poles are ordered consistently. This only means reordering

Ã„

the system UN keeping it to be an extended complete CebyÃ„ev system on C \ {b1 ; : : : ; bN } and

s

reordering Eq. (9) according to a permutation of AN to get the node system consistently ordered.

Another simpliÃ¿cation results from adopting the following notation. If ( 1 ; : : : ; k ) is a sequence

in C, then

if âˆˆ C; j = 0;

j j

âˆ—

j := (16)

1 if j = âˆž or j = 0;

k k

âˆ— âˆ—

j := j; (17)

j=1 j=1

âˆ—

i.e., the symbol means that each factor equal to âˆž or to zero is replaced by a factor 1.

Proof of Proposition 1. Let AN (z) = (z âˆ’ a1 ) Â· : : : Â· (z âˆ’ aN ) be the node polynomial and BN = (z âˆ’

b1 )âˆ— Â· : : : Â· (z âˆ’ bN )âˆ— be the pole polynomial associated with the systems AN and BN , respectively.

Let â€™ be the polynomial of degree N âˆ’ 1 at most that interpolates BN f at the nodes of AN

counting multiplicites.Then p:=â€™=BN satisÃ¿es (9). Indeed, p âˆˆ UN follows from the partial fraction

decomposition theorem and, since BN and AN are prime, Leibnizâ€™ rule combined with an induction

argument yields

i (ai ) i (ai )

d d

(f âˆ’ p)(ai ) = 0; i = 1; : : : ; N â‡” (Bn f âˆ’ â€™)(ai ) = 0; i = 1; : : : ; N:

dz dz

2. Interpolation by Cauchyâ€“Vandermonde systems

With the node sequence (7) there is naturally associated a sequence

d i (ai )

L = (L1 ; L2 ; : : :); u â†’ Li = u(ai ) (18)

dz

of Hermite-type linear functionals where i (a) is deÃ¿ned by (10). For interpolation by algebraic

polynomials there are well-known classical formulas connected with the names of Lagrange, Newton,

Neville and Aitken expressing the interpolant in terms of the nodes and interpolation data

i (ai )

d

wi = f(ai ); i = 1; : : : ; N: (19)

dz

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

Since CV-systems in many aspects are close to algebraic polynomials it should be expected that

there are similar interpolation formulas for CV-systems. Such formulas are given in the next three

subsections.

2.1. Lagrangeâ€™s interpolation formula

The basic Lagrange functions â€˜j (j = 1; : : : ; N ) for the N -dimensional CV-space UN are uniquely

determined by the conditions of biorthogonality

Li ; â€˜j = i; j ; i; j = 1; : : : ; N: (20)

For certain purposes it is important that we are able to change easily between the one-index enu-

meration of Hermite functionals (18) corresponding to the one-index enumeration (7) of the nodes

and the two-index enumeration

d

Li ; f = f( r ); r = 1; : : : ; p; = 0; : : : ; mr âˆ’ 1; (21)

dz

where we assume that AN is consistently ordered as in (11). This is done by the one-to-one mapping

â€™ = â€™N :

â€™

(r; ) â†’ i = â€™(r; ) = m1 + Â· Â· Â· + mrâˆ’1 + + 1: (22)

Similarly, between the enumeration of the CV functions (2) corresponding to the one-index enumer-

ation (1) of the poles and the two-index enumeration

uj = us; ; s = 0; : : : ; q; = 1; : : : ; ns ; (23)

where

ï£±

1

ï£´

ï£² s = 1; : : : ; q; = 1; : : : ; ns ;

us; (z) = (z âˆ’ bs ) (24)

ï£´ âˆ’1

ï£³z s = 0; = 1; : : : ; n0

corresponding to the consistently ordered pole system (15), there is the one-to-one mapping = N:

(s; ) â†’ j = (s; ) = n1 + Â· Â· Â· + nsâˆ’1 + : (25)

In order to give a Lagrange-type formula the following notation is needed:

q

N

âˆ—

(z âˆ’ Ã¿t )nt ;

BN (z) = (z âˆ’ bj ) =

j=1 t=1

p

ms

!â€˜ (z) = (z âˆ’ s) ; â€˜ = 1; : : : ; p;

s=1

s=â€˜

1

vâ€˜; (z) = (z âˆ’ â€˜) ; â€˜ = 1; : : : ; p; = 0; : : : ; mâ€˜ âˆ’ 1;

!

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

mâ€˜ âˆ’ âˆ’1 i

1 d BN i

Pâ€˜; (z) = ( â€˜ )(z âˆ’ â€˜) ;

i! dz !â€˜

i=0

i

d

diâ€˜ (Â·) = ( Â· )z= â€˜ ; â€˜ = 1; : : : ; p; i = 0; : : : ; mâ€˜ âˆ’ 1:

dz

Proposition 2. Assume that node system (8) and pole system (5) when consistently ordered are

identical with (11) and (14); respectively. Given a function f that is deÃ¿ned on AN and su -

ciently often di erentiable at the multiple nodes; the interpolant p âˆˆ UN of f at AN admits the

Lagrange-type representation;

p mâ€˜ âˆ’1

N i (ai )

d d

u ; : : : ; uN

p=p 1 N

f = p1 f = f(ai )â€˜i = f( â€˜ )!â€˜ ; (26)

a1 ; : : : ; aN dz dz

i=1 â€˜=1 =0

where the Lagrange-type basis functions are

!â€˜ (z)

â€˜i (z) = â€˜â€™(â€˜; ) (z) = !â€˜ (z) = Pâ€˜; (z)vâ€˜; (z): (27)

BN (z)

Observe that in case all poles are at inÃ¿nity formula (26) reduces to the well-known Lagrangeâ€“

Hermite interpolation formula [2] for interpolation by algebraic polynomials.

The proof [12] is simple. One only has to check that the functions !â€˜ âˆˆ UN are biorthogonal to

the functionals ds which can be veriÃ¿ed by repeatedly using the Leibnizâ€™ formula.

It is another simple task to Ã¿nd the coe cients Aâ€˜; of the partial fraction decomposition in

s;

q ns

Aâ€˜; us; ;

!â€˜ = s;

s=0 =1

ï£±

Ds s âˆ’ [!â€˜ Pâ€˜; vâ€˜; ]

n

ï£´

ï£´

ï£´ (n âˆ’ )! q (Ã¿ âˆ’ Ã¿ )nt ; s = 1; : : : ; q; = 1; : : : ; ns ;

ï£´

ï£²s s t

t=1

Aâ€˜; = (28)

t=s

s;

ï£´ D00 âˆ’

n

ï£´ !â€˜ Pâ€˜; vâ€˜;

ï£´

ï£´ ; s = 0; = 1; : : : ; n0 :

ï£³

(n0 âˆ’ )! BN z n0 âˆ’1

Here the di erentiation Ds is deÃ¿ned by Ds (Â·) = (d=d z) (Â·)z=Ã¿s :

By somewhat tedious but elementary calculations it is possible to express the coe cients (28)

âˆ’1

solely in terms of the nodes and poles [12]. If one knows the coe cients cj; t = Aâ€™âˆ’1 (t) of the

( j)

expansion

N

â€˜j = cj; t ut ; j = 1; : : : ; N; (29)

t=1

it is easy to give an explicit formula of the inverse of the Cauchyâ€“Vandermonde matrix

u1 ; : : : ; uN j=1; :::; N

V :=V = ( Li ; uj )i=1; :::; N : (30)

L1 ; : : : ; LN

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

In fact, since for j = 1; : : : ; N ,

L1 ; u1 ::: ::: ::: L1 ; uN

ñòð. 46 |