<<

. 48
( 83 .)



>>

k+1
c1; j (f)uj (z) + = 0
j=1
k+1
thus introducing a new unknown = ’p1 f(z) where z ∈ {a1 ; : : : ; ak+1 } is arbitrary. The new
system reads
« 
u1 ; : : : ; uk+1
c b
V 0
 L1 ; : : : ; Lk+1 = ; (47)
0
L; u1 : : : L; uk+1 1
k+1 k+1
where L; uj :=uj (z) (j = 1; : : : ; k + 1); c = (c1; 1 (f); : : : ; c1; k+1 (f)) and b = ( Li ; f )i=1; :::; k+1 with
L; f :=0. By block elimination of the unknowns c1 ; : : : ; ck in the last equation of the bordered
system using
u1 ; : : : ; uk
V
L1 ; : : : ; Lk
as pivot we get the equation
k+1
1 c1; k+1 (f) + = ÿ1 :
Here 1 ; ÿ1 are certain Schur complements:
u1 ; : : : ; uk ; uk+1 u1 ; : : : ; uk k
= det V det V = L; r1 uk+1
1
L1 ; : : : ; Lk ; L L1 ; : : : ; Lk
« 
L1 ; uk+1
’1
u1 ; : : : ; uk .
¬ ·
.
= L; uk+1 ’ ( L; u1 ; : : : ; L; uk )V ; (48)
 .
L1 ; : : : ; Lk
Lk ; uk+1
similarly,
u1 ; : : : ; uk ; f u1 ; : : : ; uk k
ÿ1 = V V = ’p1 f(z):
L1 ; : : : ; Lk ; L L1 ; : : : ; Lk
Since z is arbitrary this yields Eq. (41). It holds trivially for z ∈ {a1 ; : : : ; ak }.
The proof of (42) starts from the obvious representation
Ak (z)
u1 ; : : : ; uk ; uk+1
det V =e ; (49)
L1 ; : : : ; Lk ; L Bk+1 (z)
where Ak is the node polynomial associated with Ak and Bk+1 is the pole polynomial associated with
Bk+1 and where e must be a constant. To determine e consider the partial fraction decomposition
of Ak (z)=Bk+1 (z) = k+1 dj uj (z). It is easy to see that in any case
j=1

Ak (bk+1 )
dk+1 = : (50)
Bk (bk+1 )
By comparing coe cients of uk+1 on both sides of (49) we ÿnd
u1 ; : : : ; uk
det V = edk+1 : (51)
L1 ; : : : ; Lk
Now (42) follows from (48) “ (51).
G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222 213

˜
To prove the remainder formulas (44) and (46) consider the node system Ak+1 :=(a1 ; : : : ; ak ; z)
with z ∈ C\Bk . From Walsh™s proof of Proposition 1 we see that for z ∈ {a1 ; : : : ; ak } the interpolation
error is
Ak (z)
k k+1 k
r1 f(z) = p1 f(z) ’ p1 f(z) = [a1 ; : : : ; ak ; z](Bk f) : (52)
Bk (z)
If z ∈ {a1 ; : : : ; ak } (44) holds trivially. Eq. (45) results by application of Leibniz™ rule for ordinary
˜
divided di erences. Let bk+1 ∈ C be arbitrary. By applying (41) to Ak+1 with z ∈ C \ (Bk ∪ Ak )
(46) results. Again, (46) holds trivially, if z ∈ Ak .
By comparison of (46) and (44) the following relation between ordinary and generalized divided
di erences obtains
Ak (bk+1 )
u1 ; : : : ; uk+1 f
= (z ’ bk+1 )— [a1 ; : : : ; ak ; z](Bk f): (53)
a1 ; : : : ; ak ; z k + 1 Bk (bk+1 )
Clearly, Eq. (53) holding for all z ∈ {a1 ; : : : ; ak } remains true for arbitrary z = ak+1 ∈ C \ Bk+1
by continuity of ordinary divided di erences as functions of the nodes showing that the general-
ized divided di erences on the left-hand side share this property. Moreover, using the well-known
recurrence relation for ordinary divided di erences from (53) with z =: ak+1 yields
Ak (bk+1 ) [a2 ; : : : ; ak+1 ](Bk · f) ’ [a1 ; : : : ; ak ](Bk f)
u1 ; : : : ; uk+1 f
= (ak+1 ’ bk+1 )— : (54)
a1 ; : : : ; ak+1 k + 1 Bk (bk+1 ) ak+1 ’ a1
Leibniz™ rule for ordinary divided di erences gives
[a2 ; : : : ; ak+1 ](Bk f) = [a2 ; : : : ; ak+1 ]((z ’ bk )Bk’1 f)
= (ak+1 ’ bk )— [a2 ; : : : ; ak+1 ](Bk’1 f) + 1[a2 ; : : : ; ak ](Bk’1 f);

[a1 ; : : : ; ak ](Bk f) = [a1 ; : : : ; ak ]((z ’ bk )Bk’1 f)
= (a1 ’ bk )— [a1 ; : : : ; ak ](Bk’1 f) + 1[a2 ; : : : ; ak ](Bk’1 f)
and by subtraction
[a2 ; : : : ; ak+1 ](Bk f) ’ [a1 ; : : : ; ak ](Bk f)
ak+1 ’ a1
(ak+1 ’ bk )— [a2 ; : : : ; ak+1 ](Bk’1 f) ’ (a1 ’ bk )— [a1 ; : : : ; ak ](Bk’1 f)
= :
ak+1 ’ a1
Now (43) follows if the last expression is inserted on the right-hand side of (54).

Example. Given A5 = (0; 0; 1; 1; ’2) and B5 = (∞; ∞; ’1; ’1; 2) corresponding with U5 =
(u1 ; u2 ; u3 ; u4 ; u5 ) with
1 1 1
u1 (z) = 1; u2 (z) = z; u3 (z) = ; u4 (z) = ; u5 (z) = :
z+1 (z + 1)2 z’2
Given of a function f the interpolation data
f(0) = 3 ; f(1) = 3 ; f (1) = ’ 3 ; f(’2) = ’ 9 ;
f (0) = ’2;
2 4 8 8

ÿnd p ∈ U5 that agrees with f at A5 .
214 G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222


According to (43) we easily compute the table of divided di erences of f:

u1 f u1 u2 f u1 u2 u3 f u1 u2 u3 u4 f
zi
·1 ··2 ···3 ····4

u1 f 3
0 =
01 2

u1 u2 f
0 = ’2
0 02
u1 f u1 u2 f u1 u2 u3 f
3
= ’3 =5
1 =
11 0 12 0 0 13
4 4 2

u1 u2 f u1 u2 u3 f u1 u2 u3 u4 f
= ’3 =3
1 =2
1 12 0 0 13 00114
8 2

u1 f u1 u2 f u1 u2 u3 f uuuuf
= 11 1 2 3 4
= ’9 = ’1
’2 =1
’2 1 1 ’2 2 1 1 ’2 3 0 1 1 ’2 4
4 6 6


u1 u2 u3 u4 u5 f 13
= .
0 0 1 1 ’2 5 27


From Newton™s formula (41) we get the interpolant in Newton™s form
5 z2 ’z 2 (z ’ 1) 13 9 z 2 (z ’ 1)2
3
5
p(z) = p1 f(z) = ’ 2z + +2 + ;
2 2 z+1 2(z + 1)2 27 4 (z + 1)2 (z ’ 2)
which, by additional partial fraction decompositions, equals
1 7 73 1 5 1 13 1
5
p1 f(z) = ’ + z + + + :
6 12 54 z + 1 9 (z + 1)2 27 z ’ 2
In Section 4 we will present an alternative method computing the interpolant avoiding the additional
partial fraction decompositions.


3. Cauchy“Vandermonde determinants

In this section we give a new short proof of the explicite formula of the Cauchy“Vandermonde
determinant [17,7,15] in terms of the nodes and poles. It will be derived as a simple consequence
of Proposition 4.

Proposition 5. For consistently ordered node and pole systems as in (11) and (12) that have no
common points
N N
— —
k; j=1 (ak ’ aj ) k; j=1 (ak ’ bj )
u1 ; : : : ; uN
det V = mult(AN ) (55)
k¿j k¿j

L1 ; : : : ; LN N N
k; j=1 (bk ’ bj ) k; j=1 (bk ’ aj )
— —
k¿j k¿j
G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222 215


with
N
mult(AN ) = k (ak )! (56)
k=1

where k (a) is deÿned by (10) and use is made of notations (16) and (17).

Proof. From (48) and (42) for k + 1 = N we get
u1 ; : : : ; uN ’1 ; uN
det V
L1 ; : : : ; LN ’1 ; L
r1 ’1 uN (z) =
N
u1 ; : : : ; uN ’1
det V
L1 ; : : : ; LN ’1
(bN ’ b1 )— · : : : · (bN ’ bN ’1 )—
(z ’ a1 ) · : : : · (z ’ aN ’1 )
= :
(z ’ b1 )— · : : : · (z ’ bN ’1 )— (z ’ bN )— (bN ’ a1 )— · : : : · (bN ’ aN ’1 )—
As a consequence,
N (aN )
d
u1 ; : : : ; uN ’1 ; uN u1 ; : : : ; uN ’1
r1 ’1 uN (z)|z=aN :
N
det V = det V
L1 ; : : : ; LN ’1 ; LN L1 ; : : : ; LN ’1 dz
By Leibniz™ rule
N ’1 —
N (aN )
(aN ’ aj )
d (z ’ a1 ) · : : : · (z ’ aN ’1 ) j=1
= N (aN )! :
N
dz (z ’ b1 )— · : : : · (z ’ bN ’1 )— (z ’ bN )— — (a ’ b )
N j
z=aN j=1

Hence, we have got a recursion for the determinants considered. Since det V ( u1 )= 1 (a1 )!·1=(a1 ’b1 )—
a1
an induction argument proves (55).


4. Solution of linear CV-systems

In this section we will present a new method solving the system of linear equations (9) recursively
where no additional partial fraction decomposition is needed. Its proof is based upon Proposition 3.

Proposition 6. Let k ∈ N and let the CV-systems (u1 ; : : : ; uk ) and (u1 ; : : : ; uk ; uk+1 ) correspond to
the pole systems
Bk = (b1 ; : : : ; bk ) = (ÿ0 ; : : : ; ÿ0 ; ÿ1 ; : : : ; ÿ1 ; : : : ; ÿq ; : : : ; ÿq )
n0 n1 nq

and Bk+1 = (b1 ; : : : ; bk ; bk+1 ); respectively; where it is assumed that Bk is consistenly ordered with
ÿ0 = ∞; ÿ1 ; : : : ; ÿq ∈ C pairwise distinct and n0 + n1 + · · · + nq = k. We set for r = 0; : : : ; q;
jr :=n0 + · · · + nr :
Let Ak = (a1 ; : : : ; ak ) ∈ Ck and Ak+1 = (a1 ; : : : ; ak ; ak+1 ) ∈ Ck+1 be arbitrary node systems with
2 :=ak+1 = a1 = : 1 :
216 G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 203“222


By Ak we denote the node system Ak = (a2 ; : : : ; ak+1 ). Given a function f deÿned and su ciently
often di erentiable at the multiple nodes of Ak+1 . Let
k
k k
p1 f =: c1; j (f)uj ∈ Uk interpolate f at Ak ;
j=1
k
k k
p2 f =: c2; j (f)uj ∈ Uk interpolate f at Ak ; and
j=1
k+1
k+1 k+1
p1 f =: c1; j (f)uj ∈ Uk+1 interpolate f at Ak+1 :
j=1

<<

. 48
( 83 .)



>>