Numerische Mathematik 9 by Springer-Verlag 1979
Numer. Math. 32, 167-181 (1979)
A o-Stability and Stiff Stability of Brown's Multistep Multiderivative Methods Rolf Jeltsch Mathematisches Institut, Ruhr-Universit~it Bochum, D-4630 Bochum, Germany (Fed. Rep.)
Summary. Brown [1] introduced k-step methods using I derivatives. Necessary and sufficient conditions for Ao-stability and stiff stability of these methods are given. These conditions are used to investigate for which k and l the methods are A0-stable. It is seen that for all k and I with k < 1.5 (l+ 1) the methods are Ao-stable and stiffly stable. This result is conservative and can be improved for l sufficiently large. For small k and l A0-stability has been determined numerically by implementing the necessary and sufficient condition.
Subject Classifications. AMS(MOS): 65L05; CR: 5.17. 1. Introduction We shall consider numerical methods for solving the initial value problem
y'(x)=f(x,y(x)),
y(a)=r/
which use the higher derivatives and
f~i)(x,y)=~---s
(1)
f(J)(x, y), which are defined by f(~
"~+ ~yyj 0 rcJ(x ,yj
1)(x,y) f (x, y),
y)= f(x,
y)
j = l , 2 .....
Let h > 0 be the stepsize, x,, =a+mh, and Yr, be approximations to the exact solution y(xm) of (1). Moreover, let f~)=f~J)(xm,y,,). The methods are of the form k
l
2 ~ i Y n + i -~i=0
~, h~a ftj-1)l-'jJn+k with
j=l
k
~[c~i[>0, i=0
l
~lfljl>0,
(2)
j=l
n-~0,1,2 ..... Here ~ and flj are constants. For convenience in notation we 0029-599X/79/0032/0167/$03.00
168
R. Jeltsch
introduce the natural convention that flo = -0~ k. We shall always assume that the coefficients a t, flJ satisfy ( - 1)J+ 1 fli>0, % :I:0,
j = 0 , 1 ..... 1
(3a)
fl~,0
(3b)
a o + ~ 1 + ... + ~k =0.
(3C)
A method of form (2) is said to have error order p if k
I
~i y(x + i h ) - ~ hJ ~ yO~(x + k h) = C. + ~ h" + I y~.+ ~(x) + O(hP + ~), i=0
j=l
Cp+ i ~0, for all sufficiently often differentiabte functions y(x). An important subclass of methods of form (2) satisfying (3) is obtained if one selects e~ and/~j such that the method has highest possible error order. These methods have been introduced by Brown [1] and in Jeltsch, Kratz [15] it was shown that
ei=(-1)k-l(ki)(k-i)-t , flj=(-1)J/j! ~
(--1) k-i
i=0,1 .... , k - 1
(k-i) J-~,
j = 0 , 1 .... ,1.
(4a)
(4b)
i=O
In [,15] it was shown that the methods given by (2) and (4) have the error order p = k + / - 1 and that there is no method of form (2) with a higher error order. We shall call the formula (2) with (4) Brown's (k, /)-method. It was discussed in [15] for which k and l Brown's (k, /)-method is stable and for which it is not. Since the method belongs to the class of k-step methods with l derivatives and p > 1 it converges if and only if it is stable (see e.g. Griepentrog [-8], Spijker [,,17]). Convergence is also shown for strongly stable methods in Brown [,1, 2]. Assuming strong stability an estimate for the global discretization error as well as the first term in the asymptotic error expansion are given in [1, 2]. In the present article we give necessary and sufficient conditions for the methods to be A0?stable. These conditions are then used to investigate for which k and l Brown's (k, /)-methods are A0-stable, see Fig. 1. For k and l small this has been done by implementing the criterias on the computer. It is proved that Brown's (k, /)-methods are A0-stable and stiffly stable if k < l . 5 (/+1). For any e < e ~ 3 . 5 9 1 1 2 1 4 8 it is A0-stable and stiffly stable for k < e ( l + l ) and / sufficiently large. Computer results suggest that l > 2 is already large enough. Moreover, these numerical results support the conjecture, that a zero-stable Brown's method is A0-stable and stiffly stable. Finally we would like to mention that Brown's (k, 1)-methods are the well known Backward Differentiation Methods BDM. In Liniger [-16] it has been shown that the BDM are Ao-stable and strongly stable for k__<5.
A0-Stability and Stiff Stability of Brown's Multistep Multiderivative Methods h
/
A o- stobthty Qnd strong stability in this region Ls due to Theorem 5 J
l
15
~0
k
= 15 (1.1)
t"/.:"" :-':: :::::
5 J .
:-..:.
: : . ~ . ~:, . .. .-+s+ +
+++
/ . . . . . . . . . . . . . . . . . . . | ...... jr . . . . . . . . . . . . . . | . . . . . . ~....+++ . . . . . . . . . . | ...... <~..+++
/
169
+++
f . . . . . . | . . . . . . ~,.+++ / ...... | ..... ~. +++++++ jr174 ..... ,~++++++++++++ 9 | .... ~,++++++++++++
j~r 0 ~ + + + s'~ 9 @++++++++
0 .... I .... 5
+++ ++++++++++++++++++++++++++ +++-I-+++++++
i ....
10
I .... I ....
15
20
+++
+++++
I .... I ....
25
30
++++++++
I ....
35
+++
I ....
40
++ ++++++++++++
I ....
L5
I ....
50
+++++
~. . . .
55
+
I ....
60 k
Fig. 1~ Diagram of (k, l) for which Brown's (k, /)-method is Ao-stable or not. 9 means method is Aostable; + means method is not Ao-stable since P(0 has a root of modulus exceeding 1; o corresponds to (~, l), see Def. 1; <~corresponds to (v~,l), see Def. 1
G e a r [-7] s h o w e d by p l o t t i n g the b o u n d a r y o f the r e g i o n o f a b s o l u t e s t a b i l i t y that the B D M are stiffly s t a b l e for k < 6 . It is well k n o w n , see C r y e r [4], C r e e d o n , M i l l e r [-3] t h a t the B D M are u n s t a b l e for k > 6 . I n t h e n e x t s e c t i o n we d e r i v e n e c e s s a r y a n d sufficient c o n d i t i o n s for A 0stability of m e t h o d s of f o r m (2) satisfying (3). I n Sect. 3 these c o n d i t i o n s are used to derive o u r m a i n results o n B r o w n ' s (k, / ) - m e t h o d s while the m o r e t e c h n i c a l proofs are p o s t p o n e d to the last section.
2. Necessary and Sufficient Conditions for A o-Stability A p p l y i n g the m e t h o d (2) to y' = 2 y leads to t h e r e c u r r e n c e r e l a t i o n k
1
~ cq y,+ i i=O
~flj(h2)Jy,,+k=O,
n = O , 1. . . . .
(5)
j=1
This is a l i n e a r h o m o g e n e o u s r e c u r r e n c e r e l a t i o n w i t h c o n s t a n t coefficients a n d thus its c h a r a c t e r i s t i c e q u a t i o n is r
p) = p ( ~ ) _/~ ~k r/(#) = O.
(6)
Here we h a v e used the a b r e v i a t i o n / ~ = h 2 a n d the p o l y n o m i a l s k
p(O = Y~ ~, ~',
1
~(~') = Y~/~i ~i
i=O
(7)
j=l
Let (~(#), i = 1, 2 . . . . , k be the k b r a n c h e s of the a l g e b r a i c f u n c t i o n {(/0 d e f i n e d b y
9 (~(~), ~) =0.
(8)
"['hen every s o l u t i o n of (5) c a n b e w r i t t e n in the f o r m k
Y. = ~* Hj(n) ~ ( # ) , j=l
(9)
170
R. Jeltsch
where Hi(n) are polynomials in n with constant coefficients whose degree is less than the multiplicity of (j(#) as a root of 4~((,/~). * in (9) indicates that the sum is only taken over those j for which the branch (i(#) is finite. Clearly ~j(0) are the roots of p((). A method is called stable or more precisely zero-stable if [(~(0)l < 1 for i = 1, 2, ..., k and if I(i(0)] = 1 then (~(0) is a simple root of p ((), see e.g. Henrici [9], Stetter [18, p. 206]. A method is convergent if it is stable and the error order p exceeds 0, Griepentrog [8], Spijker [17]. It is well known that for a convergent method there is exactly one branch of ~(#) which becomes 1 at /~=0. We call this branch the principal branch and denote it by (1(/~). Hence (1(0)=1 and (j(0) + 1 for j = 2, 3..... k. A method is called strongly stable if ]~i(0)t< 1,
i = 2 , 3 ..... k.
(10)
In the weakstability analysis of methods one is interested in the asymptotic behaviour of y, given by (9) as n tends to infinity and h is kept fix. Hence one is interested in the region of absolute stability A = {/~'[[~(/~)] < 1, i = 1,2,...,k}.
(11)
According to Cryer [5] a method is called Ao-stable if A contains the negative real axis, i.e. ( - ~ , 0 ) = A . Gear [7] introduced the concept of stiff stability which we shall use in the rigorous form given in Jeltsch [11-13]. Since ~1(0) is a simple root of p(~) the principal branch ~l(p) of the algebraic function if(#) is analytic in a neighborhood of/~ =0. Let f2 be the largest star region into which the principal branch has an analytic continuation. The set R = {#~f211~(#)[ < t~(#)1, i = 2 , 3 .... ,k} is called the region of relative stability. Let D, 0 and a be positive constants and define the sets R 1= { # e ~ l R e ~ < - D } , R2 = { # ~ C I R e # < - a ,
]Im/zl<0}
and R3 = {#eCltRe/~[
1. Then it is stiffly stable if and only if it is Ao-stable and strongly stable. This theorem follows immediately from Theorem 3 in Jeltsch [12, 13]. The above theorem is one important reason why we are interested in finding necessary and sufficient conditions for Ao-stability. In the following we shall derive such conditions for methods of form (2) which satisfy (3). However, these methods need not to be convergent. We introduce the standard transformation z-
~+1 ~-1'
z+l z-l'
~ =__
(12)
Ao-Stability and StiffStability of Brown's Multistep MultiderivativeMethods
17i
which maps the unit disk of the ~-plane onto the left half plane H = {zOI2[Re z < 0} of the z-plane. Accordingly we introduce T(z, p ) = ( z - 1)k (b {z + 1, #] \z- 1 ! = r ( z ) - p r l ( p ) ( z + 1)k =0,
(13)
[z+l\ k i r(z) = ( z - - 1)k p / - - ! = 2., al z . \z--l/ i=0
(14)
where
Assume that P ( 0 has a root ( = 1 of exact multiplicity m. Because of (3) one has m > 1. Clearly in most applications one will have m---1. Since the transformation (12) maps ( = 1 into z = oo the polynomial r(z) is of exact degree k - m . Let z(#) be the algebraic function defined by T ( z ( # ) , # ) = 0 and zi(#), i = 1, 2..... k, its branches. Clearly, a method is Ao-stable if Re zi(#) < 0 for all # e ( - oo, 0) and all i = t, 2,..., k. Deviding (13) by pt one finds immediately that z i ( o o ) = - I for i = 1 , 2 ..... k. It follows from (3) that # q ( p ) < 0 for all p e [ - o % 0 ) and therefore T(z,p) is a polynomial in z of exact degree k for any # e [ - 0o, 0). Hence zi(l0 is always finite for all p e [ - o% 0) and all i = 1,2 ..... k. The branches z~(p) can be defined such that these are continuous functions of # e [ - o o , 0 ) . Hence the method is Ao-stable if and only if none of the graphs z~(#) intersects the imaginary axis for # e ( - oo, 0). Hence we have shown the following Lemma 1. Assume a method of form (2) satisfies (3). Then the method is Aostable if and only if r ( i y ) - p t l ( l ~ ) ( i y + 1)k =I=0
(15)
for all p e ( - 09, 0) and all y e N . Clearly Lemma 1 is not a constructive criterion for Ao-stability since (t5) has to be tested for infinitely many pairs p and y. In order to formulate a constructive criterion for A0-stability we introduce the polynomials P(z): = _ y - 1 I m { r ( i y ) ( - i y +
1)k}
(16a)
and Q(z): = Re {r(i y ) ( - i y + 1)k},
(16b)
where r..=y 2. p(z) and Q(~) are real polynomials of degree k - 1 . Let z l , z 2.... ,z s be all real non negative roots of P(v). Theorem 2. Assume that a method of form (2) satisfies (3). Then the method is A0-stable if and only if the following two conditions hold. A~:
Q(O)=r(O)=(_l)kp(_l)>O
Az:
Q(rj)>0
for j = l , 2 , . . . , s .
Note that a convergent method always satisfies A v Clearly condition A z is satisfied if P(z) has no non negative roots at all. This gives the following
172
R, Jeltsch
Corollary 1. Assume that a method of form (2) satisfies (3). Then the conditions B1, B2 are sufficient for Ao-stability. Bl:
r ( 0 ) = ( - l ) k p ( - 1)>0 P(r):~0
B2:
for all ze[0, ~).
Remark. Condition B 1 is easily checked and condition B 2 can be checked in finitely many additions, subtractions, multiplications and divisions using the Sturm algorithm, see Werner [19, p. 132], Dickson [6, p. 83]. B 2 is trivially satisfied if all coefficients of P(z) have the same sign. Proof of Theorem 2. (15) is equivalent to r(iy)(iy+l)-k~pq(#),
# e ( - - oO,0), yelR.
(17)
From (3) follows that #q(#) is a polynomial which maps ( - o o , 0 ) onto ( - o % 0 ) . Hence by Lemma 1 and (17) a method is Ao-stable if and only if r(iy)(iy+l)-kr
O)
for all yetR.
(18)
But by (16) one has Q (y2) _ i y p(y2) = r(i y)( - i y + 1)k = r(i y)(i y + 1)- k(1 + y2)k.
(19)
Hence one has Ao-stability if and only if Q(yZ)-iyP(yZ)r
oo,0)
for all yelR.
(20)
(20) is now obviously equivalent to the conditions A 1 and A 2. [] We would like to recall that in Theorem 2 we did not assume that the method is stable or has an error order p > 1. The reason is that through slight modifications of the conditions A1, A z one obtains a criterion which gives A0stability and strong stability. Theorem 3. Assume a method of form (2) satisfies (3) and has an error order p > l . Then the method is Ao-stable and strongly stable if and only if the following three conditions hold. C~:
ao=r(O)=(-1)kp(-1)>O
C2:Q(zj)>0 C3:
for j = l , 2 , . . . , s
ak- 1 > 0 .
Proof ( I ) Necessity. Assume that the method is Ao-stable and strongly stable. Hence A 1 and A 2 hold. Since ( = - 1 is not a root of P ( 0 one has C r Strong stability together with p > l implies that ( = 1 is a simple root of P(0, that is m = l . As we have seen earlier this implies ak_14:0. However, since r(z) is a polynomial with all roots in the left hand plane H - we have that a o and a k_ 1 have the same sign. This implies C a. We have already seen that zi(#) is continuous for # e [ - oo, 0) for i = t, 2 .... , k. Since a k = 0 and a k_ 1 + 0 one of these
A0-Stability and Stiff Stability of Brown's Multistep Multiderivative Methods
173
roots z~(#), let us denote it by zl(#), will tend to infinity as # tends to 0- while the other ones remain finite. Hence lim
~0-
zi(#)=zi(O )
i=2, 3, ...,k
(21)
are the roots of r(z). Strong stability implies that Re z~(0)<0. Hence (15) has to hold for all # e ( - Qo,0] and all y e N . As in the proof of Theorem 2 this implies that
Q(y2)-iyP(y2)•(- oo,0]
for all yelR.
(22)
From (22) follows immediately C 2.
(II) Sufficiency. From C 1 and C 2 follows by Theorem I that the method is A ostable. C 3 ensures that p(~) has a simple root at ~= 1. Hence we find as in (I) that (21) holds. From C 1 and C 2 follows that (22) holds and hence Rez~(#)<0 for all # a ( - o 9 and i = 2 , 3 , . . . , k . In particular Rez~(O)1 to be stiffly stable. 2. Note that a convergent method always satisfies C 1 and C 3. Condition C 2 is satisfied if P(z) has no non negative root. This gives the Corollary 2. Assume a method of form (2) satisfies (3) and has p_>_1. Then the conditions D t - D 3 are sufficient for Ao-stability, strong stability and stiff stability. DI:
ao = r ( 0 ) > 0
DE:
P(z)+O
D3:
ak_ 1 > 0 .
for all re[0, oo)
As we shall see in the next section, Corollary 2 will be very powerful for the investigation of Brown's (k, /)-methods. For completeness we give the following result. Theorem 4. Assume a method of form (2) satisfies (3) and has an error order p~ 1. Then the method is A0-stable and zero-stable if and only if the conditions El-E4 hold. El:
ao =r(O)>O ,
E2:
Q(zj)>O
E3:
ak_ 1 > 0 ,
for j = l , 2 .... ,s,
E~: If Q(zi)=0 then z = _+iz)/2 is a simple root of
r(z).
The proof goes along the lines of the proofs of Theorems 2 and 3 and is therefore left to the reader.
174
R. Jeltsch
3. A o-Stability of Brown's (k, /)-Method In this section we shall investigate for which k and 1 Brown's (k, /)-method is A ostable. It is clear that if a method is unstable due to a root of P(0 which lies outside the unit circle then the method is also not Ao-stable. Hence from Jeltsch, Kratz [15] follows that to any fixed I Brown's (k, /)-method is not A0-stable for all k large enough. However, if we fix k then Brown's (k, /)-method becomes A ostable, strongly stable and stiffly stable for all I large enough. To show this let us first show that Brown's (k, /)-method satisfies (3). In [15] it was shown that the following relation holds
(k-i)J-'
(-1) k-l-' i=0 k
tl
tl - j - 1
= Y', t~ ~ E t21"-'fiL~-~ E fi-_~>0, t1= I
/2 = 1
j = 0 , 1 ..... l - 1 .
(23a)
t1-2
For j = l one finds through direct calculation ~ (-1) k-l-i
=1 >0.
(23b)
i=0
Using (23) in (4b) one finds that (3a) and (3b) hold. Note that we could have established (3a) and (3b) also from the fact that Brown's methods are Hermite interpolatory, see Theorem9 in [10]. The assumption (3c) is satisfied since Brown's methods have the error order p = k + l - 1 > 1. Theorem 5. Brown's (k, /)-method is A0-stable and strongly stable whenever
k<3(l+ 1).
(24)
Proof. We show this Using Corollary 2. From (24) and (4) one obtains r(z)= y~ ( - 1 ) k-'
(k--i)-'{(z+l)'(z--1)k-i-(z+t)q.
(25)
i=O
Hence
(k--i)-t{1--(--1)k-i}>O
ao= ~
(26)
i=0
and ak_ i =2 ~ (--1) k-l-~
(k-i)'-'
(27)
i=0
(26) implies that D t holds and (27) together with (23) show that D 3 holds. In the remaining part of the proof we shall show that D 2 holds whenever (24) is satisfied. From (25) and (16a) we find through an easy but tedious computation that
A0-Stability and Stiff Stability of Brown's Multistep Multiderivative Methods
P(~) =2 2 ( - i) k - l - j
175
(k-j)-Z(l + ~)J
j=O
k-j
9t = o ( 2 t + l ) ( Z - - 1 ) k -
l_~_zt4t (
--Z)',
(28)
with ~: = [ ( k - 1 -j)/2].
(29)
Here [a] denotes the largest integer not exceeding a. In order to show that P(r) has no non negative roots we have to distinguish the following cases I. l<7. Direct calculation on a TR440 in double precision (i.e. 81-84 bitmantissa) showed that all coefficients of P(z) are positive whenever k satisfies (24). Hence P ( t ) > 0 for all t~[0, oe) and hence D 2 is satisfied. II. l > 7. We split P(z) as follows 89
=S(z) + T(z),
(30)
where
s(~)= 2 ( - 1 ) k-x-j
(k-j)1-'(1 +~y(~- 1)k-l-j
(31)
j=O
and k3
T(z)- ~. ( - 1)k - l - )
(k-j)-z(1 + z y
j=O
t=l 2 t + l
(z--1)k-l-J-E'4t(--z)t'
(32)
where u is given by (29). We shall need the following two lemmata. Lemma 2. Let 1 8. Then one has S(r)>k(1 +z) k-2
for all ~e[0, ~).
(33)
Lemma 3. Let 3___k_<1.5 (/+1) and 1>8. Then one has
IT(z)l< 88
~'-2
for all ze[0, oo).
(34)
In order not to interrupt the idea of the proof we postpone the proofs to Sect. 4. For k = 1, 2 one has from (32) that T(z)=0. Hence by Lemma 2 and (30) one has P(r)>0 for all re[O, oo). Thus condition D 2 holds. In the following let k>3. F~om (30), (33) and (34) follows
~P(z) > S(z) - IT(z)[ > (z + 1)k- 2 {k- 88
- 1)(k- 2) 2 32-z}
for all ze[0, oo), 3___8. Hence P(z) has no non negative root if 3z> 9(k - X)(k- 2) 2 .
(35)
176
R. Jeltsch
Since the right hand side of (35) is monotonically increasing in k it is enough to show (35) for k = 1.5 (l+ 1). Hence it remains to show that 3t > 9 ( 3 l + 1)(3 l - 1)z.
(36)
However, it is easy to see that (36) holds for l > 8. Collecting the results from I and II we find that P ( z ) > 0 for all ze[0, ~ ) for i<_k<1.5 (l+1) and l = 1 , 2 , . . . . Hence D z is satisfied. [] Clearly in the proof of (24) we have made some conservative estimates. We can improve upon (24) if we consider the methods only for 1 large enough. Theorem 6. Let ~
q(~): = ~ e
",
(37)
~ ~ 3.59112148. Then Brown's (k, /)-method is A0-stable and strongly stable for all k with
k<~(t+ 1)
(38)
and I sufficiently large. The proof of Theorem 6 is based on Corollary 2. As we have already seen DI and D 3 are always satisfied. In order to show D z one splits P(z) as in (30) and gives a lower bound for S(z) and an upper bound for T(z). We shall omit the proofs of these bounds since they are rather technical and lengthy. For the complete proof of Theorem 6 and these bounds see [14]. As we shall see from Table 1 computer results suggest that for all ~ 2. Note that Theorem 6 gives zero-stability for ~<~1, k
Definition I. Let rq be such that the coefficients of P(z) are all positive for k<-z~ and at least one is negative for k = r c t + l . Let vt be such that D 2 holds for k 4 for l > 1. The numerical values for ~, vt, at and #t are given in Table 1.
A0-Stability and Stiff Stability of Brown's Multistep Multiderivative Methods
177
Table 1. Values of ~, v~, a t and #~ which are defined in Definition 1. Question marks stand for unknown numbers which exceed 49 l
1
2
3
4
5
6
7
8
9
10
11
~l vI ~l #l
4 6 6 7
6 10 10 11
9 14 14 15
12 18 18 19
16 22 23 24
20 27 28 29
24 31 33 34
29 36 39 40
35 42 45 46
40 48 ~ 53
45 ? ? 59
The c o m p u t a t i o n of rh has been done in double precision (i.e. 81-64 bitmantissa). We c o m p u t e d vl with a double precision p r o g r a m which used Sturm sequences, see e.g. [6], [19], to determine whether P(z) has a n o n negative root. a t has been found using T h e o r e m 3. Since Brown's m e t h o d s always satisfy C 1 and C 3 one only has to test C 2. This was done in the following way. A bisection algorithm based on Sturm sequences finds through a search a p p r o x i m a t i o n s tj to the nonnegative roots rj of P(z). In fact n u m b e r s lj, uj have been c o m p u t e d such that O 0 . N o example was found where Q(z) did change sign in one of these intervals [/j, uj]. Hence the p r o g r a m always gave either Ao-stability or showed that the m e t h o d was not Ao-stable. All c o m p u t a t i o n s have been done in double precision. Because of overflow this algorithm has only been used for k<49. T h e n u m b e r s #t have already been c o m p u t e d in [15] and are just listed for comparison. The numerical results are collected in Fig. 1. Note that in [15] it has been seen for l = 1, 2 .... ,11 that Brown's (k, /)-method is strongly stable for 1 < k < #1 - 1. It is surprising that for l < 4 one has vI =/~1 - 1, and that for l < 9 one has a I = #1 - 1. It is conjectured that a z= #l - 1 for all I. This means that for Brown's (k, /)-method one has the rare situation that strong stability implies Ao-stability and stiff stability.
4. Proof of Lemmata We shall need the following Lemma 4. Let ne{1, 3}. Let c~, be the unique positive root of q(ct) = -
1
(39)
n
where q(c~) is given by (37). Then to any c~< c~. there exists w.(c~) such that i
1 (k-i+l)
,<
(k-i)"
i=l,2,...,k-1
(40)
for l~w,(ct) and k
R. Jeltsch
178 Table 2
n
~.
~
w.(~)
1 3
3.59112148 1.65687525
3.3 1.5
7 8
Proof
(40) is equivalent to
f(i) =
(ikl) (k-i+l)-~
1 <-
(ki)(k_i)_ ,
for i = 1, 2, ..., k - 1
(41)
n
and we ask for which values of k and I is (41) satisfied. We replace the integer variable by a continuous variable s and determine the maximum of
f(s)=k-s+l \ k - s + l ] for
sEI=[1,k-1].
An easy calculation shows that maximum point is oe' ~-
f(s)
has exactly one maximum in I and the
k(k + 1) l+k+l"
Hence (41) is satisfied if f(s')< ,
k
k
gl(k):=f(s ) = ~ i -
1/n. Consider l
l
((k + 1)(/+ 1))
which is a monotonically increasing function in k. Hence (41) is established if
h(7'l):=gl(a(l+ l))=~
1 +7 1+
satisfies h(a, l) < -1.
(42)
n
Observe that 1
lira h(e,/) = c(e
~ = q (~).
(43)
l~oo
Clearly q(a) is monotonically increasing for ee(0, oo). Hence (39) has a unique positive solution e,. Let ~ < % therefore q(e)< i/n. From (43) follows that there
Ao-Stabilityand StiffStability of Brown's Multistep MultiderivativeMethods
179
exists w,(~) such that h(c~,/)< 1In for l > wn(~) and thus (40) holds. In order to be able to compute actually wn(c0 given n and ~, observe that for a fixed ~ the function h(~, l) is monotonically decreasing in I. Thus it is enough to verify that h(0~,wn(~))
Proof of Lemma 2. Let us write
k-1 S(r) = ~ si
i=0
where
\ ~ - z ] (1 - z)k- 1,
i = 0, 1, ..., k - 1.
(44)
I. Let ze[0, 1]. From (44) follows that s~>0. Hence
S(z)>Sk_i=k(l+z)k-l>k(l+z)k-2
for zs[0, 1].
II. Let ze(1, oo). From (40) with n = l , c~=3.3
ISol
for 1~8.
Moreover, si(-1) k- i - i > 0 . Hence /k\
1
1
s(~) >s~_l +s~_2 =k(1 +~)~- ~+ [2) g = r ( + ~)~- 2( 1 -~) =(l+z)k-2{~(2~-k+l)z+k+~}.
(45)
Clearly 2 ~ - k + 1 >_2~-4(l+ 1)+ 1 > 0
for 1>5
(46)
and all k with 1 < k < 4 ( l + 1). Hence from (46) and (45) follows
S(z)>k(l+z) k-2
for ze[1, oo).
Proof of Lemma3. Since l r
[] and I z l < l z + l l for zE[0, oo) one finds
from (32) that
[Z(.c)[ = k~3 ~=0
(~) ( k - j ) - ' ( l + z ) J ~u (2~t~j) (z + 1)k- i - J - 2'4'(Z + 1)' t=l
1
R. Jeltsch
180
For Te[0, oe) one has that (r + 1) l - t < 1 for all t > 1. Hence
< 89
2s= 89 +2) k-~
s=O
and thus lr(~)l<(r+l)k-2~j~o
(k-j)-z3 k-~
for zs[0, oo).
We apply (40) of Lemma 4 with n= 3, e = 1.5 <e3 and w3(e)= 8. Hence
IT(r)l<(.c+l)k-289
)
for re[0, oo)
and k > 3. This is obviously equivalent to (34).
[]
References t. Brown, R.L.: Multi-derivative numerical methods for the solution of stiff ordinary differential equations. Department of Computer Science, University of Illinois, Report UIUCDCS-R-74-672, 1974 2. Brown, R.L.: Some characteristics of implicit multistep multi-derivative integration formulas. SIAM J. Numer. Anal. 14, 982-993 (1977) 3. Creedon, D.M., Miller, J.J.: The stability properties of q-step backward difference schemes. BIT 15, 244-249 (1975) 4. Cryer, C.W.: On the instability of high order backward-difference multistep methods. BIT 12, 17-25 (1972) 5. Cryer, C.W.: A new class of highly-stable methods: Ao-stable methods. BIT 13, 153-159 (1973) 6. Dickson, L.E.: New first course in the theory of equations. New York-London: John Wiley, 1962 7. Gear, C.W.: The automatic integration of stiff ordinary differential equations. Information Processing 68, 187-193. Amsterdam: North Holland Publ. Co. 1969 8. Griepentrog, E.: Mehrschrittverfahren zur numerischen Integration yon gew6hnlichen Differentialgleichungssystemen und asymptotische Exaktheit. Wiss. Z., Humboldt-Univ. Berlin Math.Natur. Reihe 19, 637~553 (1970) 9. Henrici, P.: Discrete variable methods in ordinary differential equations. New York-London: J. Wiley & Sons 1962 10. Jeltsch, R.: Multistep multiderivative methods and Hermite-Birkhoff interpolation. Proceedings of the Fifth Manitoba Conference on numerical mathematics, Oct. 1-4, 1975, Congressus Numerantium XVI, Utititas Mathematica Publishing Intercoporated, Winnipeg (1976), 417-428 11. Jeltsch, R.: Stiff stability and its relation to A o- and A(0)-stability. SIAM J. Numer. Anal., 13, 8 17 (1976) 12. Jeltsch, R.: Stiff stability of multistep multiderivative methods. SIAM J. Numer. Anal., 14, 760772 (1977) 13. Jeltsch, R.: Corrigendum to "Stiff stability of multistep multiderivative methods", to appear in SIAM J. Numer. Anal. 16 (1979) 14. Jeltsch, R.: Ao-stability of Brown's multistep multiderivative methods. Proceedings of the 1977 Army numerical analysis and computers conference, 1977, 565-581 15. Jeltsch, R., Kratz, L.: On the stability properties of Brown's multistep muttiderivative methods. Numer. Math. 30, 25-38 (1978)
Ao-Stability and Stiff Stability of Brown's Multistep Multiderivative Methods
181
16. Liniger, W.: Zur Stabilit~it der numerischen Integrationsmethode t'fir Differentialgleichungen. Doctoral thesis, University of Lausanne, Switzerland (1957) 17. Spijker, M.N.: Convergence and stability of step-by-step methods for the numerical solution of initial-value problems. Numer. Math., 8, 161-177 (1966) 18. Stetter, H.J.: Analysis of Discretization methods for ordinary differential equations. BerlinHeidelberg-New York: Springer 1973 19. Werner, H.: Praktische Mathematik I. Berlin-Heidelberg-New York: Springer 1970
Received January 23/September 28, 1978
