View of A boolean method in bivariate interpolation

(1)

MATI]trMATICA

_

REVUE D'ANALYSE ^NUMÉRIQUE ET DE TFIÉORIE Dtr L'APPROXIMATION

L'ANALYSE

NUMÉRIQUE

ET I,A TIIEORIE I}E

L'AI'PROXIN'IATION Tome

9,

No

L,

1980, PP.

36-&5

A ^BOOI]EAN ^METHOD IN BIVARIATE INTERPOI]ATION

by

F.J. DDÍ,VOS and

II.

^POSDORF

(Siegen, West Germany) (Bochum, West Gennany)

0.

Introduction

Boolean methods of nultivariate interpolation

rruefe introdu-

ced in the

fund.amental

papefs or con¡or¡ 14, 5]..It ^¡/as

^shown

of

commutative

projectors (in parti-

a

distributive lattice

^each^of'whose

arametric extensions

of

univariate

ii;ä #:!îI""å,1".'.,

J"","i

Í"ïå:Ti

^"

to

iog an va-

n formula

^have

the

same Boolean

(2)

36 ^F.J, DELVOS and H. POSDORF

2 ₃ A BOOLEAN METHOD IN B1VARIÄTE INTERPOLATION 37

1.

The Biermann

projector

I,et

S

:

_La,

_b) x lø, ål

^be

^a

^square^and.

let B(S)

denote a sutspace

of the

space

C(S) of

continuous functions

on S,

F'urthermore, let

{Ai 1<i<N}

Þ" ..set of N partial linear

operators

which

operate on

f ^e ^B(S)

^as^a

function of ø

such

that

Ai(f):ai(y) eB(s).

Similarly,

let

{Ai:t'i<N}

be

a

.set of N partial linear

operators

which

operate on

f ^e ^B(S)

^as^a

function of y

such

that

A:í(f):ai(x) _=B(S).

Nor'v consider

the finite

sequence

of natural

numbers

|<n,<nz<...

^<

and let

AL: {L;,'ir

^<

j < no}, | ^<

^k,

< K be a set of univariate

cardinal

functions,

r,vith respect to

i: {Aiil <i ³ n*}, | < h < I{,

1. e.

(1) A"(L;,"u):8;,r, l<i, j3no, l<h<I<.

Furthermote, we suppose

that

(2) (^i)c(Âi+r), l<h<K-1.

Similarly

let

A"¡: {Li,"u:l

^<

j S nn\, 7 < h ^< K be a set of

u.nivariate

cardinal functions with

respect to

A'i:

_{A,i

:I ^< ^,i 3 %*\, |

^<l?,

^< K,

i.e.

(3) Ai(Li,"o):8,.,r, 7 <i, j <no, I <

h,

<K,

and suppose

that

(4) (^í)C(Âí+r), l<k<K-l'

Thus

we

can construct

the

^set

{PLu:l<h<K}

of parametric projectors o',n,t ^< k ^< K,

associated

with the

sets

Âi and Aí, I ^<

^h'

^< ^K:

nþ

(5)

P',"u(f)

:DAi(f)Li,,u@), t ^<k ^< ^K.

Similarly

we construct

the

set

{P,u:1<k<K}

of parametric projectors pin, < h < K,

associated

with the sets

Âí

and Aí, I < h < K:

,þ

(6) Pi,þ(r):DAi(f)L'i,*o(v), ¹ ^<h ^< ^K.

It ^follows ^from ^the relations (1), ..., ⁽⁴⁾ ^that the projectors P|o

^anð'

Oio, t < h < I(, ^are

absorPtive, i.e.

Pi,Pi'¡ : P"¡PL,- PL;' | ^< i

^<

i ^< ^K' (7) P'i,P'i'¡:P'ljP'i'i- P'i't' | =i <j <K'

Finally

^we^assume

that the

sets

Aír, Aír

commute

on

B(S) ^:

(B) AiAiU):AîA't(f), 1<i' j3nu' /eB(s)'

Thus

it

follows

from (2), (4), (7), (7) that the projectors

P'n,,

" ', ^P''*,

Pi,,,

^.^.

.,

P'|,r, commute

and

generate

a distributive lattice (cf'

connoN

[4j).

Special" elements

of this lattices are product projectors

^PirP'1,¡,

1 < i, j < K:

P'-,P'; j(f

) :

ä É,

^Aí^A':,(^f⁾^Lí,,,(x)^Lü,,,^¡(v)^.

obviously, the product projectors enjoy the following

interpolation properties ^:

AíA'|,(PL P'Jj(.f))

: AiAhU)

(e)

\I <t I

^%i,

| 3l/rl 1 M¡, 7 < i, I

^SK).

(3)

5 A BOOLEAN METHOD IN BIVARIATE INTERPOLATION 39

.)Õ F, J. DELVOS and H, POSDORF 4

DEFTNTTToN

L

^ThegenerøIized..B'iermønn

þrojector P* is

d.efined. as

tke Booleøtø sum

of

tke þrojectors

PL,Piu*r_,, 1 I r ^< ^K:

Px

:

Pi,nPi,K @ P:,^P';.o_, @

., . O

pL,r_rp,i," _@

pi,rpí,.

(,Note

that the

Roolean

súÍr of two

commuting projectors

A

and

B

^is

defined

by A

@

B : A + ^B - ^AB).

. -The

generalized, Bierø,t,ønn þrojector

P*,is locally

møxírnø|, sittce

it

is the

rnøximal elentent of tlte sublølt,ice generøted,by

P',,,pI*¡r_,, l<

r

<I{.

It

enjoys

the interpolation properties given in

rHÞoREM 7. ^þ-ov

/ ^e

^B(S),^the

function

^g

: _Poff)

interþol,øtes

f ⁱⁿ

the sense that

AiAi@):A'iAi _lÐ,

(1

3'i,3n". I

=

j

=,/Tt<+t-,.

I <r sK).

Proof

.

The

lattice

theoretical construction

of

Po yields

PL,Pirrr-,P,r: PL,Pí^r-,,1 < r ^< K.

Thus

the

interpolation properties

of the

Boolean sum

projector P*

follow immediately

from the

corresponding properties

of the-product

prôjectors

(see (e)).

Our

to

d.erive an

explicit

expression of the projector

Printermsof

sumsof

productprojectors PLrPi,r*r_,, 13r ^<

^R.

T,EMMA

l. For tke

generalized,

Bierntann þrojector Pu thc

_following

reþresentøtion

formulø is

^{aøl,id. :}

(10) o*:tî pL,+rp:,r-,Ð, _or,

p,l,x-,

Proof

. We will prove this

representation

formula for K: 3.

The general case

can be proved by induction ("f.

DÐr,vos-posDoRF _[3]).

Pu:

P'*^P'i,"@ P:,,P'i,@

PL"Pi,,:

: (Pi,,Pi,"+ P;,P'i,,-

P',,,Pi,,) @

P',,P|,:

:P;,P'ir" +

^Pi,,Pi,,

-

^P;,,

^Pi,+

^P:,"^P'r:,,

-

P',,,Lt'/,,

-

P",,P'1,,

+ ^P;,Pi,, : : P;,P'1"+

P:,"P',i" 1-

P:"P';,- P;,Pí, -

^P;,P'i',

THEoREM

2. Let.f =

^B(S),^{then the}general'ized' Biermønn 'ínterþolatnt

P*ff)

of

f

^has^the^followingreþresentat'ion

(no:0):

.Il-s s krll

"K-t

(11) P*(fl(x,y) :ÐD D Ð AiAiU)Lri(x,y),

r0 r=0 i:ttr1_l j =nyç_1_s*1

uhere L¿,¡(x,

y)

d'enote

the

cørd:ina.l,

functians aitlo resþect oJ ^Ai

^,4j¡

(n, J-lli ^1n,+r, /tK-r-.s+ 1s j 3ro-",0 <r < s < K- ¹⁾

^giaenby

(r2)

^L;,¡(x,

o) :ÐLl,,,nr@)L'i,,-¡b) -,i, r',,,,,(x)Li,,-,(!).

Proof. Taking into accoünt (5) and

(6)

the

representation formula (10) yields

R-l nt+l "R-t

p,(Í)(,r) :Ð Ð Ð oiAiu)Li,,+,1x)Li,"-,(!)-

K-l fr, nK-,

-D D ^D uAiff)L:,",1x)L!,,,*-,(!).

/:1 i:1 j:l

Thus

rve obtain

K-l nr-Fl K-l n(-s (" \

p(Í)(,y):D

_t:0 _i:t\ll

D D D

s:/ i:,tff-l-s+l

,Aia:;(f)lÐri,",,()Li,.*-,U)l-

\r:/ )

- iì ^,:þ,,Ð ^,:;Ð; ,'AiA';(Í)(þ''""o' r;"'*-lv)):

K- l nt*l K-l nr-s / s \

: _Ð

t:0 i:n +l s:t j:l¡<-l -s+1

_. _D. D D _,, AiAí(f)lÐti,",,,(x)

\¿:t

Li,'*-,{r)J -

K-2 nttt K-l nr-s / s \

-D D D D AíAí(f)1.D.ri,,,1)L'i,,-,g)l:

7O ¿-or+t ^t:-r-¡1¡:rrrj-"+t \':/+l ^I

- il s _b-]

,:Þ' ^,AiAi(fl lÐri,,,,,() Li,,*-,(y) -

- /-r ¿-r I

t:O i-n¡+,l 5:7 ¡:r¡ç_1-"{1

- ,å,

^L't,,,(x)

L'i,.*-,(y)

s-0 /:0

DD ,"Ë.,,_._Þ' _,

^Ai

^Ai 0

{Ð rr,,,,., çx)L,i,,*_,u) -

i-nrll i-nç-t-s*l

- s' r| tfl

^,^-''n^t(x)

t;"'*'t _u)

^ì

l'

I(-l s

(4)

40 F, J. DELVOS and H. POSDORF

o 7 ^ABOOLEÄN METIIOD IN BIVARIATE INTERPOLATION ₄₁

IÍ: n,:2r.In ^this

^case^{we have}

^N :2K. An

application

of

^Theo-

rern

2

yields:

Thus the equalities (r1)

_.and

.(r2)

^gre

verified. we

now merely have

to

prove

that the Lr!(1:1r)

given

ià lizt are the d"sit"¿

"ärdinal

^functions.

Theorem ₁

yields

_for

f ₌

^B(S)

_AiAiff):AiAiP"ffi); ⁽¹ ^< i ^<?t,,, |

=

j <?tx+t_,,t <r <I{).

I,et

7@,

y). - ^Li,x@) Lí,,.*(y),

r

< _/t, r 3

^nu.

Then

Ã, ^AiA'i (i):à¿,¿87,r,(1 < o.r,, l <l<ftK+t-,, | <r <K).

I nus

Pt _U) :

Ln,t

rvhich implies

A:

Ai

_@k,ù

:

Aí

Ai e* ^(ñ) : Ai

A,;(,i)

:

^8¿,¿8,;¿.

this

proves

our

theorem.

We

considet

r.oy in

greater detail the_two cases. nt

: /

â"ttd, _%,

:2r.

. .!, n,: r,In ^this

^casõ^{we have}

N:1(. ei, ãïpii"rtion

ot Theorem 2 yields :

Pr(f)(*,r) :

Þ^ È ^or*,

Aío-, (f)L,+t,w-,(x, y),

s:0 /:0

with

s

Lr+t,N-s (*,

y) :Ðtl*r,;+t

(x)L'io-,,*-, (y)

- ,ù

_i:t1-l

.rir,r()Lk-,,w-¿(y).

Note

that

the well _knownbivariate

Taylor formula

and

the

Biermann form.ula.

^

(sraNcu [B]) ^are

^ortainea

^-ny ;p;"irli;'i'ö tîe

operators and cardinal

functions

ãs-follows :

(i) Taylor formula:

Aiff): D',-'f@',ù, A'i(Í): Di-r.f(x, yo), 1 < i < N.

Lí,n(x):(x- xòi-' l(i _ _t)

!

L'í,n(y):(y- !òi-'lU - \ ! (l'i<

h',

l 'å'N).

(ii)

Biermann formula:

¿i(f):Í(x¡, j), Ai (Í):.f(x, y,), 1 < i ^<

N.

L|u (x)

: n

^O

-

^x¡)^I^@¡

-

^x¡)

i+i

L(,n (y)

: \

^ro

-y¡)lU¿-y¡) withxr1x21...<

J+¿

(l<i<h, l<,å<N)

\ _{_/1V}

I(-1 s ^2/+2

Po(fl@,y):

,4 Ð ,F*

_{:2(K-s) -}

D

_I

^A|

^A',j^(Í)L;,¡

^(*,

^y),

2K -2s (13)

with

tj

s

(14)

^L,,¡^(x,

_ù :ÐL'¡,"u+rt

@)Li,z¡r-ub)

-,Ð,

^Li,2¡(x)Li,21v-n U),

From

⁽¹³⁾

the

folloi,ving

formula can

^easily

be

derived:

(15) ^pou)@,r, :

Þ. D,^{our*uA'íto,¡(Í)L,r,+u,z1x-¡

^(x,

v) ¡

I ALv+.,tA'í6-,t-rU)

Ltv+r1,2(K-s)-r

(*' y) + -l

^AL,+,

A'íø-¡(Í)Lt +r,ztx_¡(x,

Y)

¡ -f

^AL,+t

A'lw-,\-, (f)Lr,+t,tt*-¡_, ^(x, !)\' we will now apply this formula to

reduced

Hermite

interpolation schemes

of type II

þ?oposed.

by r6r,r<Es [6]'

^F'or

^this

^purpose

let (S:

: _{[0, 1]} x [0,

^1])^:

AL¿-r(f): D';1Í(0, !), AL¡(Í): ^D';'Í(1,

^Y)

Aï¡-,(f): ^n,Í(x,0), Ai,ff): Di-, fl(*, t) ^0< ^í<K)'

the

corresponding cardinal

functions

^are

(16)

LL¡-,,"u _@)

: #,0 - ^*)o(ã(t- :-') ^t)

(17)

I-î¡,rn (x)

: (- l)i-t ¡'

_-',"0

(l -

^x)'

The

^functions

L'í:t,"n (y)

and

L'í¡,*(y)

are d.efined analogously.

F;; ^th" á;ii"otiä"'äf ihc

cardiäaf iunctions see pHrrrrrrps [7.]).

F'rom

(14),

_{' '}

.,

^{(17) we}now obtain the following

1HE9REM

3.

The reþresentation forntul,a

for

^the^red'uced'Herm'ite inter-

þolant P"(f)

of

f ^ís

^gíuen^bY^:

K-l s

P

u(fl @,y): Ð

^Ð,^{^}^{D

^;Di

^-t-""/ ( 1, 1 ) ⁽

-

^t^¡

^r-

^t

^{-' !'}

^L^{z, +}^t,,to^{-o -}^{r (}¹

- ^*'l -

^y)

+

!

Dr,Drc-r-y(1,

0)(-l)

L",+r21n-"¡-r(1

- ^{x, y)} ⁺ I D,nDx-t-y(0, 1)(-1¡o-t-"r2tt,z(r-s)-t(, l- ^y) + I Dr*Dx-r-y(O,

⁰⁾

L",+t,r(-")-t(, y)\,

l< j<h, 1<h.sI{)

(5)

42 ^F.J. DELVOS ônd t{. POSDORF

B

I

A BOOLEAN METIIOD IN BIVARIATE INTERPOLATION 43

witlt

An

application

of

Lemma

2 to

reduced

Hermite interpolation

yields THEoREM

4.

Let

/ ₌

B(S):C2K+2(S),

S: _{[0, 1]} x [0, 1]'

^Then^tloe

remøind,ev

P*(Í)

o"f tlte ^reduced'Herm'ite 'interþolant

P"(f) is

g'iuen by

"

Eu)@, ,lJW

^o?,"^"f

^(*,

^vo)

r

s

Lr,) r,"(,, ,¡-r(ø,

y) :

Ð

LL.t.t,zQ+tt(x)

L'ír,r-'¡

_{r,rto_nU)}

- -,Ð,

^LL,^+r,u(x)^Lís,^_,t^_^r,rv,^_rt(r)

2.

Rcrnaindel r,cpresentation,

rn this

sectiolr we

will

derive a

re'rainder

represe'tation

formula

for gerreralized Bicrmann projector

p,,

_anð.

_apply

_this

iã'n'iãïo

,"ao"ed Her-

urite

interpolation.

From

Lernma 1

wc

obtain the

follolvirg

reprcsentation formula of

p*:

(18) _P'. :

å

^(PL,*,

-

pi,,) p1,,,-,

with Pi,"- P'i,,:0

and

P',,rr,_r:1

wher.e

0

denotes

the

zero_projector and

I

denotes

the

identity-projector.

This

leads us to

+l ffi

DTD"rrc-'tr(x,,

!x-)+a#D',*Í@o'v) -

fi|

^,,*1(*

-

^1)/+t^yK-t(y

- ^1)*-' - )

:

-

Pz(t+tl D1,""'

-f(i,*l, ^yK-/)' H,,

^Q?

*

^t))t(z(K

-

^r))l

Proof

.

Using

the elror

estimates

of univariate Hermite

interpolation

(cf. oavis t2l) ^the

^theorem

is

proved' bv

K-l K-1

4: ^P'í*+ D FÇHw-¡-l-PrK- l, PbvltP'í6-'','

t:l r:O

which is

an immediate conseqllence

of

Lemma ^2.

TiÐI,rr,rA

2. For

th,e retnø,inder

uing

reþresentøt,ion

fonnulø

^'is^uþ_rojector o.f

Pr,

d.enoted.

by P*,

ttte fotlo-

ctl,id, :

LI< 1)

-

K I(_l

Ðo1,o,,,_, - _Ð p;,*rr,;o_, 3.

Concluding remarhs

In

a recent

papef

ryATKINS and LaNCaSrnn [9]. extend-ed the method

of

^red.uced

lteimite interpolation to fill up cerlain

^gaps

in the finite

element construction of recfangular elements'

It

^{is the}

topic of a

^forthco-

min

^he^e-íements^of

^this

extended Melkes

family

can

be

^etalized

Biermann interpolation' fn

^particular

this ^icit

construction

of the

corresponding cardinal functions.

by

proof. Taki'g into

account

the formula

(18)

th.r

lemma

is

proved

ä,o;*, -

^P;,)^Pü,,-,

* _ho,,, ^Pio-, Ð4'*,F'|',,-,:

K K

:Ðe,,*, -

^PL,)

Px,r_,+Ð(v,"- _H,,*r) P'l,u_,:

APPENDIX

: \

^{Pi,,

^r, -

^P',,,)^P'1,^r,

-, + D

K ^{^e^i,,

^*, -

^P'n,)^Pi,^*

-, : _As _an

instance we present

the

inter

interpolation lor K :2,

multiple

node consisting ^o

up to

and including

ft.

W

functional A'tA'i,0 : _Í(0,

: Ð(P:,,+, --

^PL,)

: _r

(6)

44 ^F,^J.DELVOS and lJ. POSDORF

10 1t ^A^BOOLEAN^METT{OD^]N^BIVARTATEINTERPOLATION 45

K-2

tll Biermann, ^O.,Über näherungsaeise Kwbøluren. ^REFERENCES i:[/.orats1n. math. Phys. lLt ^271-225

( 1e03).

l2lDavis, Pl., J., Interþolation and Aþþroxitnøtioø.Blaisdell Publishing Company, [on- don (1963).

[3] Delvos, ^F.J.,Posdo¡f, Ir,, ^N-th^ord'er^blending.In: ,,Constructive Theory of Func- tions of Several Va¡iables". Ecls. : W. Schempp, K. Zeller. Irecture Notes in Mathematics, 671, 53-64 ^(1577).

[4] ^G^o^r^d^on, W.J., Distributiae Lattices and the Aþþroxirnation of Mul'tiuøriate Functions.

Proc. Symp. Approximation with Special Emphasis on Spline ^Functions, (Madison, Wisc. 1969). Ed. : I.J. Schoenberg. Acaclemic Press, New-York, 1969,

pp.223-277.

tsl Gorclon, W. J., Blend,ing-Function Methods of Bi.uariate ønd Multiuariate Inlerþolation a.nd' Aþþrotrimøtion. SIAI|/,, J. ^Num.Anal., Vol. B, No' 1, 158-177 ^(1971)' [6] Melkes, ^F.,^Red,uced,Pieceuise Biuaviate Hermite Interþolation. Num. Math. l9' 326-

-s40 ^(1s72).

t7l ^P^hⁱ^{11i p s,}^G.M., Exþli'cit Forms for Cerlain Hermi'le Aþþroximations. BIT 13, 177 -180

(1s73).

tB]

Stancu,

^{D. D.,}Theyemøind,er of certøinlinear øþþroximationformuløsin twoua,r¿o,bles.

SIA1\[, J. Num. Anal., Ser. B 1, 137-163 (1964).

[9]

Watkins,

D. S.,

I,anc aster,

P', Sovne Farnil'ies

of

Finite ^Elemenls.J. ^Inst.

lVlaths Applics 19, 385-397 (1977).

Received 16, II. 1979.

K-l

Dr.

!'.

_J.^DETTVOS

Lehvslukl,

fitr

Matherrxa,t'ih

I

Uniuersity of Siegen

Höld.erlirstr. 3

D-5900 Siegen 21

West Germany

Dr.

II.

^POSDORF

Reohenzentrum Uniuersity of Bochum Universitätsstr. 150

D-4630 Bochum West Getmany

K-_4

Fig. 1

View of A boolean method in bivariate interpolation

_

L'ANALYSE

ET I,A TIIEORIE I}E

9,

L,

36-&5

A BOOI]EAN METHOD IN BIVARIATE INTERPOI]ATION

II.

0.

Boolean methods of nultivariate interpolation

ced in the

papefs or con¡or¡ 14, 5]..It ¡/as

of

projectors (in parti-

distributive lattice

of

ii;ä #:!îI""å,1".'.,

Í"ïå:Ti

to

n formula

the

The Biermann

I,et

:

b) x lø, ål

a

let B(S)

of the

C(S) of

on S,

{Ai 1<i<N}

Þ" ..set of N partial linear

which

f e B(S)

function of ø

that

Ai(f):ai(y) eB(s).

Similarly,

{Ai:t'i<N}

be

.set of N partial linear

which

f e B(S)

function of y

that

A:í(f):ai(x) =B(S).

the finite

of natural

|<n,<nz<...

AL: {L;,'ir

j < no}, | <

< K be a set of univariate

functions,

i: {Aiil <i 3 n*}, | < h < I{,

(1) A"(L;,"u):8;,r, l<i, j3no, l<h<I<.

that

(2) (^i)c(Âi+r), l<h<K-1.

Similarly

A"¡: {Li,"u:l

j S nn\, 7 < h < K be a set of

cardinal functions with

A'i:

:I < ,i 3 %*\, |

< K,

(3) Ai(Li,"o):8,.,r, 7 <i, j <no, I <

<K,

that

(4) (^í)C(Âí+r), l<k<K-l'

we

the

{PLu:l<h<K}

of parametric projectors o',n,t < k < K,

with the

Âi and Aí, I <

< K:

(5)

:DAi(f)Li,,u@), t <k < K.

Similarly

the

A ^BOOI]EAN ^METHOD IN BIVARIATE INTERPOI]ATION

papefs or con¡or¡ 14, 5]..It ^¡/as

_b) x lø, ål

^a

f ^e ^B(S)

f ^e ^B(S)

A:í(f):ai(x) _=B(S).

j < no}, | ^<

i: {Aiil <i ³ n*}, | < h < I{,

j S nn\, 7 < h ^< K be a set of

:I ^< ^,i 3 %*\, |

^< K,

of parametric projectors o',n,t ^< k ^< K,

Âi and Aí, I ^<

^< ^K:

:DAi(f)Li,,u@), t ^<k ^< ^K.

(6) Pi,þ(r):DAi(f)L'i,*o(v), ¹ ^<h ^< ^K.

It ^follows ^from ^the relations (1), ..., ⁽⁴⁾ ^that the projectors P|o

Oio, t < h < I(, ^are

Pi,Pi'¡ : P"¡PL,- PL;' | ^< i

i ^< ^K' (7) P'i,P'i'¡:P'ljP'i'i- P'i't' | =i <j <K'

" ', ^P''*,

PL,Piu*r_,, 1 I r ^< ^K:

B : A + ^B - ^AB).

/ ^e

: _Poff)

f ⁱⁿ

AiAi@):A'iAi _lÐ,

PL,Pirrr-,P,r: PL,Pí^r-,,1 < r ^< K.