<< Ïðåäûäóùàÿ ñòð. 46(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>
additional partial fraction decompositions. As an application construction of rational B-splines with prescribed poles is

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:

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 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>