AMS WORDS

internat. 3. Math. & Nath. Sci.

VOL. 18 NO. (1995) 89-96

COMPUTABLE

ERROR

BOUNDS FOR COLLOCATION METHODS

89

A.H.AHMED

Department

^of

Mathematics

Ash-Sharq University Khartoum, Sudan

(Received August 12, 1992 and in revised form February 27, 1994)

ABSTRACT.

This paper deals with error bounds for numerical solutions of linear ordinary differentialequationsby globalorpiecewisepolynomialcollocationmethodswhich arebasedon consideration of theinvolveddifferential operator, relatedmatricesandthe residual. Itisshown that significant improvement may be obtained ifdirectbounds for theerror in the solution are considered. The practical implementation of thetheory is illustratedbyaselectionof numerical examples.

KEY

WORDSAND PHRASES:

1980AMS

SUBJECT

CLASSIFICATION:

1. INTRODUCTION

This paperis concerned with computable error bounds for the solution oflinear ordinary differential equations by global and piecewise polynomial collocation methods. Thiswork is motivatedbyanabstractapproachoferroranalysis^suchasdescribedforexample byKantorvich andAkilov 1,Chapter

XIV]

^andAnselone

[2,

Chapter

I].

Itextendspreviousworkinthisareaby Cruickshankand Wright

[3]

and considersdirect errorboundsonthesolutionandits derivatives ratherthanviatheerrorboundsonthehighestderivativesasdescribed in

[3].

Thebasic idea here is tomakeuse of thematrix involvedin thenumerical solutionofthe differentialequationincomputingerrorbounds. Therelationshipbetween various matrices and the inverse differential operator has beenconsideredby Wright

[4],

Gerrard andWright

[5]

^andAhmed and Wright

[6]. In

particularthesepapersare concernedwithasymptotic relationships^between inverse operatornormsand those ofmatrices relatedtothenumerical solution. The theory leads naturallytotheuseofmatrixnormsinboundingthe inverseoperatornorms. Then computation of the residual norm leadsimmediatelytocomputationoftheerrorbounds.

Theuseof theseideasin error estimation is discussed in

[7].

Theirpracticalimplementation inselection criteriaforadaptivecollocationalgorithmsis examinedin

[8].

Referencestoalternative

approaches

in collocationalgorithmsand erroranalysissuchasDelves

[9],

^DeBoorandSwartz

[10],

De Boor

[11]

^andRussell and Christiansen

[12]

may^befoundin

[7].

Detailedcomparisons withthealgorithmsof Ascher, Christiansen and Russell

(used

in the well known codeCOLSYS for solving boundaryvalue

problems) [13],

^ispresentedin

[8].

Throughoutthispaper^theanalysisand illustrative resultsuseinfinity norms,

though

^someof theideascould be extendedtoother norms. Theassumptionsabout the methodsandequationsare introducedwhenneeded,toemphasizetheirsignificance. The theoreticalbackgroundispresented only brieflyasit isreasonablywell known. The results are testedon aselection ofproblemsand comparisonsaremadewiththose in

[3].

The workpresentedinthispaperisbasedonAhmedthesis

[14].

90 A, H. AHYlED

2. ASSUMPTIONSAND NOTATION

Inorderto beable to treatboth global and piecewise polynomial collocation in a uniform manner wefollowverycloselytheassumptions andnotationsused in

[7].

We consider the linear ruth orderdifferentialequationof the form:

xt")(t)

+

,-o P’(t)xO)(t)

^"y(t)

⁽¹⁾

With m associatedhomogeneous boundaryconditions. Withoutloss ofgeneralityweassumethat theequation holds in

[-1,1].

Theequation maybewritten inoperator form:

(D’-

T)x y

(2)

where

D

denotesthe differential operator.

In (2)

wesupposethatxE

X

^andyC

Y

where

X

and

Y

are suitableBanachspaces. The operators

(D T)

and

D"

withthe associated conditions^areboth assumedtobe invertible. Theapproximatecollocation solution istakeninasubspace

X,,,

^{CX. To}

definethis,wefirstdefineasubspace

Y,,

^CY.

^Suppose

^theinterval[-J,

1]

^issubdividedbythebreak points-1

to

^<

t

^{< <}t,, 1.

In

each sub-intervalqcollocation pointsareused chosenas:

+k--((tk--tk_l) +(tk

+

t_))/2

^{j 1 q}

(3)

k 1,...,n

where

{’}+

^{j 1,...,q,are}given reference pointsin

(-1,1).

^Thespace

Y,,,

consists of functions whicharepolynomials ofdegree q 1 in each of the intervals

Jk- ^[t_t

^+,t-

^1],k

^{1 n. No}

assumptions regardingcontinuityatthe break pointsismade. The solutionspace

X,,

^{isthen taken}

as

(D’)-Y.

Theprojectionoperator

9,,,

is defined asthe operator whichgives^theinterpolantin

X,,,

basedonthecollocationpoints

{g}.

^Withtheseassumptionstheapproximatesolution

x,w

^satisfies:

(D" ,r)x, y (4)

In [6]

certain matrices

Q

were introducedand theirpropertiesexamined.

Here

weuse aspecialcase of this and denoteitby

Q,,,.

^{Thisis most}convenientlydefinedby consideringtherighthandside y and the solution^atthe collocationpoints. Then thereis amatrix

Q,,,

^{such that}

xt)= Q, wY ⁽⁵⁾

and this can beregardedas adefinitionof

Q. ^In

^{asimilarwaywedefinethe matrix}

Q.<)

by

x(r) Q.q,,

^{(r). r 1,2,...,m 1}

⁽⁶⁾

and the matrix

Q)by

x<,,,) Q,,,y

Thenunder suitable conditions it wasshownin

[6]

forr 0,1 m 1that t’)ll

IID’(D’- r)-ll

^{as n o,q fixed,and}

OOll .,, lID’(D" r)-ll

^{as n} ,n fixed, and in

[4]

^and

[5]

^that

O0’011

II:.,, ^II( T(D’)-’)II

^{as n} oo, q fixed, and as n--, n fixed.

(7)

COHPUTABLE ERROR BOUNDS FOR COLLOCATION NETHODS 91

Theseconditionsconcerned thelocationof thecollocationpointsandrequiredthe continuity of the coefficients

Pj(t)

ⁱⁿ

(1).

Inparticular, theglobal ^case(q %n 1)assumed that thepoints

{’}

were zeroofcertainorthogonalpolynomials.

Some further definitions and notations are needed before constructing the bounds. It is convenientheretodefinethe compact operatorsKand

K

^by

K

T(D")

^-1

K, D’-"

for r 1,2,...,m 1.

Wealso introduce theevaluationoperator

.q:Y R "’

^{togivea vector}consisting ofthe values of afunction atthecollocationpoints. Further an extension operator^qJ’.R"q

Y

canbe definedtogive afunctionwhosevaluesatthecollocationpointsagreewiththe components of the vector,withy theproperties

.q[I tIJ.qll

^1,

.qC,,q-.q

^and

(nqLIlnq- I.,,

9.q

.W.q.,

^{asdescribed in}

[4,5]. Operator

expressionsfor thematrices

Q.

^{can now beobtained. From}

(4)

-1

andapplying

.

^gives

-,.T) ,.y, (8)

and hence

Q.q .qCD"

In

asimilarwayweexpress

Q,,’,

^and

W,,,

in thefollowingoperatorforms

-1

and

(9)

(10) (11) TI-IE

ERROR

BOUNDS

Suppose

anapproximatesolution

x.q

of the differentialequation

(2)

has been found and

x.,

satisfies

(4).

^Lettheresidual

r,q

^{be defined}by

r,, ^(D" T)x,,

^y

and the errorby

Using

(2),

^wehave

(12)

(D" T)e,,q r,,,

^or

e,q ^(D" r)-lr,

q.

(14)

e.,ll

^"=

^(O" T)-II _r. (15)

Notethat

I1,’.11

^{canbeevaluatedatany pointwithoutdifficultysince}

x,,,

^isapiecewise polynomial.

Thus

r.ll

^maybe estimatedbyevaluationatasuitablyfinegridofpoints. Nowonce aboundon

W’- T)-ql

has beenobtained,

(15)

^{canbe usedto}bound

e.ll

^{To bound}

^W’- r)-ll

^directly

weneedtoextend thetheoryin

[3]

^{in the}following way. Ifwedenote the inverses

(D" -$,,,T)

^-I

and(I-

q,,rK)

^-1when restrictedtothesubspace

Y.,

^by

(D" -#hqT)-lY,

^and

(I- ,,rg)-’Y,,,

then the followingrelation canbe seen betweenthem.

It immediatelyfollows that

e,, x,,

^x.

⁽¹³⁾

92 A.H. AHMED

whichimplies

(I

,,qK) -

^I+(I

,,,K)-’Yq9,,,K

(D" #,,qT)

^-1

D"

+

(D" q,,,T)-tY,,,,,qK

(16)

(17)

(D" -9.,T)-’ _I111 ^(D’)

^{-t /}

^(O"- .,T)-’Y.q .g ⁽¹⁹⁾

Now (D" T)

-

^{canberelatedto(I}

^-.qK) -

^and(D"

^{-.,T) -1. By}

^{applyingAnselone}

^[2,

^page

^59]

tothe identity

(D" t)(D")-)(l

+K+...+K^a-+(I

^%K)

^-a)K

,

^I+

^{(0., I)K(I}

⁺

^,,.,K) - ^K

^d

weconclude that

(D"

T)^-t

I111 ^(D") -

⁺

^{(D’)-’ K}

^+...+

^{(D’)-’ K -’11 (D" .T)}

^-x

^K

6-II(%-l)g(1-*.g)-’gq

^{< d-1,2}

⁽²⁰⁾

Nowtoapplytheextendedprojection theory suggestedⁱⁿ

[3],

^define

W,,d

^by

W,, (D’)-y

+

(D Tx,,

By

definitionof

,q(D")-x,,D

^{isaboundedlinearprojectionfrom}

^X

^to

X,.

^Define

T,:X ^Y

^by

T. T(D’)-, ^".

^{Thenit can}easily be verifiedthat,

(o" r.)w.

^y,

(D" L)-’ ^(D’)

^-x+

(D’)-’T(I .T)-’, ⁽²¹⁾

and

(K K.q)-’ ^I

⁺

^K(I .,rK)y.q

Now byapplying Anselone

[2,

page

59]

^totheidentity

(D" T)-’ (D")-’

(I+

K

+ +

K

^a-’+

(I -KO,,,)-’Ka)(I

⁺

K(O., ^1)(I -Kc#.,)-’K ^a-’)

weconclude that

(D’)-’

+

(D’)

^-1

K

+...+

(D’)-’ K-’

+

(D" T.)-’ K"

(D" T)-’ I1":

₁

_A.

a

if

A.- II(%-I)K(I- .)-Kq

^{<1 d-}1,2,...

Nowifwerecallequation

(9)

Q,,, q),,(D"

^-x

anduse

q.tIJ.,qs., q., q.,rx., x.,, ,,,V. I.

^and_-1

.. .

^weget _-1

sothat

D’-.T)-’Y. _IIll . ^Q.

(22)

(23)

C0IPUTABLE ERROR BOUNDS FOR COI,LOCATION NETHOI)S 93

Ifwerecall

(11)

and usethesame idea weget(D T)

-

^<

-,,qT) Ynq I111 ^(D) % ^Q.q II. ⁽²⁴⁾

Again,if we recall

(21)

^{and usethesame ideaof}

(23),

we get

(D" T,,,)

^-t

I111 (D’)-’T, ^Q,

⁺

^(D’)-’ II.

²⁵⁾

Inasimilarway it canbeshown that

_{,.K) K}

K(I

_(,. Q,K) _I -

^d

_’]l ^K,q,Q,q

₊

_{(,. z,.ll}

^andhence

_{o.ll K"II (26)}

and

IIK(%-)(-K%)-KII IIKII ^II(*.-ZII +IIKII II(.-Z.II I1.%11 ^IIKq.

⁽²⁷⁾

Now if we denote the bounds in

(20)

by

QP

^{and use}

(18), (19), (23), (24)

^and

(26)

^we get

QPd

(D’)-’[[ 11K’II

⁺

*.11 ^I1Q.II *.Kd.’l[ ₍₂₈₎

,-o

-

and

-I +I

wp,,-ii (D’)-’ : ^K’

⁺

^(D) ,., ^Q." *.de"

i-o

and ifwedenotetheboundsin

(22)

by

Aa

^anduse

(21), (25),

and

(27)

^weget

i-o

-A

(29)

(3O)

zx. -II ^{K (* -r) K}

^/

^{r (*. -OK,.} ?. ^K I1

^{1 d 1,2,....}

Followingthearguments of

(28), (29)

^and

(30)

^andusing

(10)

insteadof

(9)

^{similarbounds forthe}

derivativesof thesolutionn be derived.

Nowin ordertocompute these boundsweneedtocompute bounds for

(,. II, *. ^II,

and

D -’T.

Boundsfortheprojectedtermscanbe

computed

using

Jacon

theorem

[15]

^whereas boundsfor theconstant tescan beevaluated directlyas described in

[3].

3.

NUMERICAL RESULTS

Wepresent herea selectionofnumericalexamples illustratinghowtheideas canbeapplied in practice and whatsortof results can beobtained. WeusezerosofTchebychev polynomialsas collocationpoints^andforthepiecewisecasewework withtwopointsonly. For comparisonwe includethe bounds derived in

[3]

^anddenote themby

Pa

^and

Aa.

^Wealso use theproblems used thereasbasictestproblems.Otherproblemshave beenconsidered, including higherorderequations.

/-4 A. H. AHN[’I)

Problem x"+c( +

t2)x

y x(__.l) 0

Problem2 x" ctr y x(+_l) 0

Problem3 2a

x"-(t

+5)

2x

^{y x(__l) 0}

2coc" 2tx

Problem4 x"+ y x(_l) 0

+3

(t

+3)

The parameter^tis included tovarythe stiffness of theproblem. Intable wepresent thevalues ofPd, WPd, QPd,

Ad

^and

^QAa

^{for theglobal} collocationmethod. In comparing these boundswe observe thefollowinginequalities:

Problem ct--.5 A <

QAI Po

^<

^WPo

^<

^QPo

ct .5,1

A:,

<

QA

<

WPt

^<

^QP

^<

Pt

Fromtheseinequalitiesand the results in the tableswe note:

(1)

^The extended projection bounds

(QAt,2,A1,2)

are much more accurate than the projection method bounds

(QPo, IPo,).

This confirmsexpectation based ontheexpressions for these boundsas

aPt

^and

ed

^{includetheprojectionnorm}

,q

which is notuniformly^bounded.

(2)

If we consider each projection method separately, we observe that

(with

^the extended projection

method)

in all problemsexceptproblem1,

QA1,2 <A,2.

^{Forthe usual}projection method inmostcases

QPo

and

WPx

^havenoimprovementsover

P0,

^while

QP

and

WPI

^are

better than

P. ^In

^general,if

^K I1<

^{1/2,it can}be seen thatWP_{a <}

P,t

andsuperiorityof bounds usingthe matrix

Q

becomes moreclear when

a., I1:11 W"-x) w.,

^{asjustifiedbythe}

theory.

(3)

^Ifwecomparebounds with small values of dwiththoseofhigher^valuesof dweobserve that thelatterare

always

better. This isobviouslyduetothe bounds derivedfor

(z-.,) r

as mentioned in

[3].

Resultsforthepiecewisecollocationmethod arepresentedintable 2. Alltheproblems therehave consistentlysatisfiedtheinequality

QAI,,

^<

QPo,1

^<

WPo, <ml,2

^<

P0.1"

Thisconfirmsthesuperiorityof bounds using the matrix

Q

and the improvement of

Pa

^by

^WP,

^as

expected bythetheory.

NOTE: The missing values in the tables are duetothe deltasnotbeing <1.

Problem2 ct .5 A <

QA Po

^<

WPo

^<

^QPo

a-

QA <At aPo

^<

WPo

^<

Po

ct .5,1

QA

<

QP

<A <

WP

^<

PI

Problem3 .-.5,1

QA

<A

<Po

^<

WPo ^<QPo

ct-.5,1

QA

<A <

P

^<

WPa

^<

^QP

Problem4 t-.5

QA

<A

ct-.5

QAz

<A <

QPI

^<

WP

^<

P,

COMPUTABLE ERROR BOUNDS FOR COLLOCATION METHODS 95

96 A.H. AHMED 4. CONCLUSION

Thenumerical results show thatimprovedcomputablebounds for the inverseof thedifferential operatorcanindeedbefound ifweconsiderthe differentialequationin theoriginal form,

(D"

T)x y, insteadofthetransformedone

(l -K)x y

Theintroductionofthe matrix

Q,,

^whosenorm as shownin

[6],

tendsto the normofthe inverse differential operatoris a mainfactor of the closeness of these bounds. The improvementis more obvious withthepiecewisecollocation method thanwiththeglobalcase. Within theglobal case there is much improvement with the extended projection method. This is clearly due to the involvementof the projectionnorm(whichis notuniformly

bounded)

^{in the}latter case. However in that case we havegot

WPd

^{boundswhich use (D}

)9,,, w,, [[,

^insteadof

@,, Q,, [[,

^as

alternatives. Despite the closeness of thesebounds,unfortunatelythe conditions ofapplicability (5,^d<1,A,^d<1),which weremajor problemswiththepreviousanalysis

[3],

have turnedout tobe the same.

An

alternative approachtodeal with suchproblems is tosplitthedifferential operatorin somedifferentway. Forexample

(D")

ⁱⁿ

(2)

maybereplaced by

a,,D"

+a,,

D

^+...+

aid

^where

al,a2 a,,are someconstantstobe chosentogivethehighestpossible applicability. This idea is justified bythe resultdescribedin

16]

^andmaybeinvestigatedinaseparate paper.

REFERENCES

[1] KANTORIVICH,

L. V. and AKILOV, G.

P.,

Functional ^Analysis in Normed

Spaces, Pergamon Press,

NewYork

(1964).

[2] ANSELONE,

P.

M.,

Collectively

Compact Operator

ApproximationTheory,Prentice-Hall, EnglewoodCliffs,NJ

(1971).

[3] CRUICKSHANK,

D. M. and

WRIGHT, K.,

Computable errorbounds for polynomial collocationmethods, SIAM J. Num.Anal. 15,134-151

(1978).

[4] WRIGHT,

K., Asymptotic properties of collocationmatrix norms 1- global polynomial approximation,

I.A.A.J. Num.

Axial, 4, 185-200

(1984).

[5] GERRARD,

C.and

WRIGHT, K.,

Asymptotic properties ofcollocation matrix norms 2:

piecewise polynomial approximation,

I.M.A.J. Num.

Anal, 4,363-373

(1984).

[6] AHMED,

A.and

WRIGHT, K.,

Further asymptoticpropertiesofcollocation matrixnorms, I.M.A.J. Num.Anal.5,235-241

(1985).

[7] AHMED,

A.and

WRIGHT, K.,

Errorestimationfor collocationsolutionof linearordinary differentialequations,

Comp. &

Maths. withAppl;,,Vol.128, No.5/6,1053-1059

(1986).

[8] WRIGHT, K., AHMED, A.

H. and

SELEMAN,

A.

H.,

Criteria for mesh selection in collocation algorithms forordinarydifferential boundaryvalueproblems, I.M.A.J. Nurrl, Anal. 11, 7-20

(1991).

[9] DELVES,

L.

M.,

inModern NumericalMethods for^OrdinaryDifferential Equal;i0ns

(Edited

by G.Hall andJ.M.

Watt),

Chap. 19, OxfordUniversity

Piess (1976).

[10] DE BOOR,

C. andB.

SWARTZ,

Collocation atGauss points, SIAM J. Num. Anal. 10, 582-606

(1973).

[11] ^DE

^BOOR

C.,

^Goodapproximation by splineswith variableknotsII.

In

proceedingofa conferenceonthe NumericalSolutionof Differential Equations

(Edited

by G. A.

Watson),

lecturenotesin Matheamtics 363,Springer,Berlin

(1974).

[12] RUSSELL, R.

D.and

CHRISTIANSEN,

.l., Adaptivemesh selectionstrategies

for

solving

boundary

valueproblems, SIAM J. Num. Anal, 15,59-80

(1978).

[13]

^U.

ASCHER, CHRISTIANSEN,

J.and

RUSSELL,

R.

D.,

COLSYS

A

Collocation forBoundary-ValueProblems. Codes forBoundaryValue Problems inOrdinary_ Differential Equations. gd.B.Childs etal., New York,

Spriner

Verlag,164-185

(1979).

14] ^{AHMED, A.,}

Collocationalogrithmsand erroranalysisforapproximatesolutionsof ordinary differentialequations,Ph.D.Thesis, Universityof Newcastle

Upon Tyne (1981).

[15] CHENEY,

E.

W.,

IntroductiontoApproximationTh.eory,McGraw-Hill,NewYork

(1960).

16] AHMED, A.,

Asymptotic propertiesof collocationprojection norms,Vol. 19,No._4,45-50, 1990Int. J.of

Comp.

and Math.withApplications.