<<

. 46
( 83 .)



>>

additional partial fraction decompositions. As an application construction of rational B-splines with prescribed poles is
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
( 83 .)



>>