A-Stable linear multistep methods for Volterra Integro-Differential Equations

Numer. Math. 27, 85--94 (t976) 9 by Springer-Verlag t 976

A-Stable Linear Multistep Methods for Volterra Integro-Differential Equations. J. Matthys Received September 12, 1975

Summary. A class of linear algorithms for Volterra Integro-Differential Equations is studied. The concept of the associated canonical fraction is extended to this class and leads to an algebraic criterion for A-stability. 1. Introduction The present paper is concerned with the numerical solution of Volterra integrodifferential equations (VIDE) by a linear algorithm, consisting of a linear multistep (LMS) formula, coupled with a "reducible" linear quadrature (LQ) formula, as defined in Section 2. From the stability point of view, as well as for the order of the truncation error, these algorithms are shown to be equivalent to a composite LMS formula. As a consequence, some recent results due to Brunner and Lambert [t] can be simplified, unified and completed. Section 3 is concerned with scalar VIDEs. A definition of A-stability is proposed, which appears as a more natural extension of Dahlquist's concept [2] to VIDEs than the one proposed in [1 ]. As for usual LMS formulas, a canonical fraction [3, 4] is defined, leading to an algebraic criterion for A-stability in a straightforward way. Finally it is proved that there exist no A-stable methods of an order larger than two. In Section 4 this approach is extended to systems of VIDEs. The class of algorithms remaining A-stable for general systems is seen to be very restricted. 2. Definitions and Notations

Consider the following VIDE: y ' (x) = F (x, y (x), z (x)),

(t)

z(x) =fK(x, t, y(t)) dt

(2)

o

in the interval O~_x
k

Z oqy._i=h ~fl, F(x._~, y._i,z._i)

n>k

(3)

86

J. Matthys

where h is a constant stepsize, y, is an approximation to y(x,,), x,,=nh, n = 0 , ~.... N, N h = a , while the successive values z, are obtained by the LQ formula

z,,=h~?,~,i K(x,~, x~, yi)

n ~n o

(4)

~0

where ~ = max (n, n o+ k - - 1). Some starting procedure is assumed to have been applied to provide a sufficient number of initial values, with a sufficient accuracy, to the algorithm defined by the relations (3) and (4) and denoted or a;/~). The LMS formula (3) will be denoted .~ (0, a) and is characterized b y the two polynomials k i=O

i=O

which obviously can be normalized so as to make O(~) a monic polynomial. Suppose now that, for all K(x, t, y) not depending on x, and for all n >=no-kk, z. can be written as a linear combination of z._1, z._, . . . . z._ k, K., K._ 1. . . . . K._ h ( K i = K ( x i , Yi)), with coefficients which are independent of n. The resulting relation can then be written as

~.-~iz,,_i=h Efii Kn_i

i=o

n~no+k

i~o

and we say that the L Q formula (4) is reducible to the LMS method &a(~, i~), where ~(r and 8(r are polynomials similar to (5) with coefficients ~i and fl~ respectively. The following results concerning reducible L Q formulae were derived in [6]. Lemma 1. Let the sequence .... s_1, s o, s1. . . . be defined b y the equations

~(~)/~(~')- s o + s~r sj=O i
s ~ - ~ + ...

~) iff

7,,~=s,_~+ ~ls,,~.+i Ci~

n >=no

(6)

where Cii=O for i =>n0q-~ and arbitrary for 0 =
(r+ t) ~=o~n,~i'=n "+1 for no ~ n ~-----no-l-k-- 4, 0 ~ r ~ p - - t.

A-Stable LMS Methods for Volterra Integro-Differential Equations

87

As an example, we derive the L Q formula which reduces to the second order backwards differentiation formula [7]:

~(0=r162

~(~)=3~.

This gives ~(r162

i_~o3i + l - 1 ~ - i = 2 8 1 :26 ~ , ~+---~-3 3 - + 9 ~- +-2-7r + "'"

Since p = k = 2, we can choose n o =0. Applying Lemma 2 the 2 • 2 matrix (7 is found to be (7=

26

3J

and the ~.,i are given by (6) as

~

3n-/+l-

1

2~i
~n'i~] 3n t l-T--3;-

i = o, t

Other examples are, of course, methods I and II in [t]. An algorithm tit'(O, e ; / ' ) for which the LQ formula (4) is reducible to some .W (~, ~) will be denoted ~r (Q, e; ~, ~). 3. A-Stable Methods for Scalar Equations

3.1. De/inition and Comments Our stability analysis will be based on the linear test equation s

y' (x) = (~ + ~,) y (x) - ~ J

y (t) dt

(7)

the use of which has been justified in [t]. All solutions y (x) of (7), as well as their x

integrals z ( x ) = fy(t) dr, tend to zero for x tending to infinity, ift Re 2 < 0 and d

Re # < 0. It is therefore natural to extend Dahlquist's A-stability definition [2] as follows: Definition 1. A method dr' (~, a; F) for scalar VIDEs is called A-stable iff its solution y~, z, converges to zero for n tending to infinity, when it is applied, with a fixed stepsize, to any equation (7) for which Re 2 < 0 and Re/t < 0. This definition slightly deviates from the one proposed by Brunner and Lambert [t ] by the fact that they take a priori/z = ~* so as to make the coefficients in (7) real. This allows an easy graphical representation of the stability regions, since the parameter space is only two-dimensional, whereas the parameter space of Definition t has four dimensions. In this sense, the definition of Brunner and Lambert seems rather to be the generalization of A (0) stability in ODE theory [8]. In [1] the convergence of zn is automatically achieved when the stability regions are defined in terms of the stability polynomial.

J. Matthys

88

The rest of this section will be devoted to the derivation of an algebraic criterion for the A-stability of methods ~ ' (~, a; ~, 8).

3.2. Characteristic Equation The application of ~ (Q, a; ~, ~) to the linear test Equation (7) yields: k

k

7, ~, y._~ = h 7, ~, [(~ +~) y._~-- ~ z._,], i=0

i=0

Z ?q z,_, = h Z fil Y,-,

i~O

i=0

which can be written as a two-dimensional recurrence equation K

Z A~ ~._~= o

i~O

(8)

where K = m a x (k, k), ~.= [y., z.] T and

[~,--h~,(~+~,) h,~,%1. ~ = f l ~ = O for i > h and ~i=fi~=O for i > k The convergence of these equations has been studied, e.g. in [9]. If M(~) is defined as x

M(~) = Z A~ U -~, i=o

one has:

Condition 1. ~ ( ~ , ~;~,~) is A-stable iff all the roots of the characteristic equation det M(~)=~lk-~l (e(~) ~(~)--h (1+/~) ~(~) (~(~)+h2tl~a(~)5(~)) = 0

(9)

lie inside the unit circle for all 2 and # with negative real parts.

3.3. Remarks 3.3A. The irrelevant factor r

will be omitted in the following.

3.3.2. It is always assumed that 0(~) and a(~) (~(~) and ~(~)) are mutually prime. However it is possible for ~(~) and a(~) to have common zeros. If such a zero lies on or outside the unit circle, the method is, of course, not A-stable. 3.3.3- In the special case ~ (~) -- O(~); ff (r ~ a (~), the characteristic equation (9) degenerates into

(0 (~)- h~(~)) (e (0-- h ~ ( 0 ) = 0 and Condition t reduces to the requirement that all the roots of e(~)--qa(~)=O lie inside the unit circle for all q with negative real part. ~.~.4. If h tends to zero, (8) reduces to h

7,~q y._~=0; i=0

7, ~ z.,.,= 0. i-O

(~o)

A-Stable LMS Methods for Volterra Integro-Differential Equations

89

In analogy with It0~, p. 33, it is therefore natural to define zero-stability as follows: Definition 2. ~ ( 0 , a; ~,5) is said to be zero-stable, iff both -~(0, a) and .~(~, 5) are zero-stable.

3.4. Canonical Fraction Condition 1 is now transformed, in order to obtain a criterion in terms of positive real analytic functions. As in [3, 4], a change of variables is performed by the bilinear transformation

~=(z+t)/(z-l)

(11)

which yields the new polynomials r (z), s (z), ? (z), ~ (z), defined by expressions of the form [z+t~

r(z) = (z- ~)k 0 / ~--=7}" Furthermore, denoting h ~ by v and h/t by -- w, the foliowing equivalent condition is obtained.

Condition 2. "-s

a; ~, 5) is A-stable iff all the roots of r (z) ? (z) - ( v - w) s (z) ~ (z) - v w s (z) ~ (z) = o

(t 2)

lie in the left half plane Re z < 0 for all values of v having negative real part, and all values of w having positive real part. Thus, for (12) the following implication is valid: (Re v < 0 ) ^ ( R e w > 0 ) =~ R e z < 0 which is logically equivalent to ( R e w > 0 ) A ( R e z > 0 ) =~ R e v > 0 and this can alternatively be written as (Rew_~0) A ( R e z > 0 ) ~ R e v ~ 0 by a reasoning similar to the one given in [4] Section 3.I. This proves the following theorem: Theorem 1. Jr' (0, a; ~, 5) is A-stable iff the canonical fraction r (z) ~ (z) + w s (z) ~ (z) v = s (z) ~ (z) + w s (z) ~ (z)

(l 3)

is a positive real bivariable analytic function. In the degenerate case (~0), we are reduced to the theory of [2] or ~3] giving: Theorem 2. ,It'(0, a; 0, a) is A-stable iff Z(z)=r(z)/s(z) analytic function.

is a positive real

3.5. A-Stability Criterion It is clear that v and t/v are simultaneously positive real analytic functions. Since 1 t + w iT(z)

7--

z(z)+w

(t4)

90

J. Matthys

with Y (z)= ~ (z)]~ (z), Theorem 5 of Oono and Koga [t 1] can be applied on (t 4) to obtain the following characterization:

Criterion. , ~ (q, a; ~, ~) is A-stable iff the following conditions are satisfied: 1. Z (z) is positive real.

09

2. Y (z) is positive real.

(t6)

3. For all real eo

F(-ja,)

z (jco) + ~ (jo~) z (-j~o) + 2 =>21~(/o) Z (io~)- I I.

07)

Corollary 1. A necessary condition for the A-stability of dr' (9, a; ~, 8) is that both .~ (9, a) and .~e (3, a) be A-stable. Corollary 2. If Z(z) (Y(z)) is an odd positive real function, ~ ( ~ , a; ~,~) is A-stable iff F (z) (Z (z)) is equally odd positive real and

t __>Z(jo~) Y(j~o)

for all real a~.

(18)

3.6. Remarks 3.5.1. In the degenerate case (t 0), the conditions (t 5) and (16) are equivalent; the right-hand member of (17) vanishes, whereas the left-hand member is always nonnegative. Hence we are reduced to Theorem 2. 3.5.2. The definition of Brunner and Lambert [1] leads to the following modified condition:

Condition& all(Q, a; ~,~) is A-stable in the sense of Brunner and Lambert iff all the roots of r (z) ~ (z) - 2 ~ ~ (z) s (z) + ( ~ + o~) s (z) ~ (z) = o

lie in the left hand plane Re z < 0 for all real ~o and all real negative ~. Theorem 3. Any combination of two A-stable methods .~e (~, a) and .LP(~, 8) for which ~ (r and a (r have no common zeros on the unit circle, is A-stable in the sense of Brunner and Lambert.

Proo]. Since s (~, a) and .~e (~, ~) are A-stable, both Z (z) and F (z) are positive real analytic functions. Now suppose, for some real r o and some real negative ~0, the characteristic equation to have a zero z0 with nonnegative real part. Since Z (z) and Y (z) are positive real, and since ? (z) and s (z) have no common zeros on the imaginary axis, ? (Zo) and s (Zo) are nonzero. Therefore the following equality would be valid: Z (Zo) - 2 ~o + ( ~ + o~o*)F (z0) = o. However the real part of the left member is strictly positive; hence the initial hypothesis is false and for all real to and all real negative ct the characteristic equation has only zeros in the left half plane Re z < 0. Q.E.D. 3.6.3. Suppose Z (z) to be an odd positive real analytic function. By Corollary 2, (z) is then equally odd positive real. Therefore, both fractions can be written as

H (~' + ~ ) ( z ~ + ~ ) ...

A-Stable LMS Methods for Volterra Integro-Differential Equations

91

with 0 ~o~'1 < a h < co'2... and where the degrees of numerator and denominator differ by one unity. If ?'co1 is a pole of Z, it cannot be a pole of Y, since in that case (z*+o~) divides as well s(z) as ~(z), corresponding to a common zero on the unit circle for a (r and ~(r As pointed out in Section 3.%2. this is contradictory to the requirements of A-stability. The poles of the product Z Y have thus multiplicity one at most. In the neighbourhood of such a pole, Z (?'co) Y(l'eo) varies from - - ~ to + ~ , which is clearly incompatible with condition (t8). Hence all the poles of Z Y must vanish through simplification with a corresponding zero, leaving for the simplified function

Z(z) Y(z)=Az~+B

A>O, I > B ~ 0 .

If Z has a zero at infinity, A must be zero. Moreover, if both methods .~ (~, a) and .LP(~, ~) are consistent, B can only be 1. This way we have proved the following theorem. Theorem 4. If .oqe(0,a) is a consistent A-stable algorithm, corresponding to an odd canonical fraction, the only A-stable method for VIDEs, combining a consistent algorithm with s (9, a), is Jr' (Q, a; Q, a). 3.5.4. Theorem S. The maximal order of an A-stable method d/(~, a; ~,a) is two.

Proo/. By Corollary t, a necessary condition for A-stability is, that both .s (q, a) and .o~f(~,~) be A-stable. Hence, .o.r a) and .SP(~,~) have order 2 at most [2] and so has ~s162 (~, a; ~, ~) by the definition of the order [t]. On the other hand, if .Sf(~, a) is A-stable of order 2, we can derive an LQ formula, reducible to .5~a(p, a) with the same order (Lemmata I and 2). H e n c e ~ ( ~ , a; Q, a) is A-stable and of order 2, by Theorem 2 and the order definition respectively. Q.E.D. 3.7. Examples 3.7.t. Since the trapezoidal rule is a consistent A-stable algorithm corresponding to an odd canonical fraction (ZT= 2[z), Theorem 4 applies and the only Astable method for VIDEs involving the trapezoidal rule is the trivial combination of this algorithm with itself. As a result, the combinations of the trapezoidal and the backward Euler rules, which are A-stable in the sense of Brunner and Lambert [1 ], cannot be A-stable in the sense of Definition t. 3.7.2. As an example of a nontrivial A-stable method consider q(~) = r 202. 1 o"~" 301 z 99 ~) = 4 ~ - r + 402'

q (r = r 1 6 2 (r = 0.7525 r

0.005 -b 0.2525

which yields

2(z+ t.ot) Z(z)--- z*+1.ot z + t ' z*-bz-t- t .01 F(z)= 2(z+ t)

92

J. Matthys

Both methods have order 2, the canonical fractions are obviously positive real and the condition on the imaginary axis gives 0.0t eo4+0.02030t r > [0.000t co8+ 0.00040602 to~+ 0.000010130601 oJ4 + 0.000108120601 co2+ 0.00040401 ]~/2 which is satisfied for all real co.

4. A-stable Methods for Systems of VIDEs 4.1. Definition Suppose now that y and z in the Equations (t) (2) denote d • t vectors, while F and K denote d • 1 vector valued functions, and apply again the classical arguments of weak stability to this case. We are then brought to study the matrix test equation x y' (x) = A y (x) + B f y (t) d t (t9) 0

which is equivalent to

where ~ = [yr zT]T. Now all solutions ~ tend to zero as x tends to infinity, iff all the eigenvalues of N have negative real part [t 2]. It is therefore natural to define A-stability for systems of VIDEs as follows: Definition 3. A method .~(~, a ; / ' ) for systems of VIDEs is called A-stable iff its solution y~, z~ converges to zero for n tending to infinity, when it is applied, with a fixed stepsize, to any Equation (t9) for which all the eigenvalues of N have strictly negative real parts.

4.2. Characteristic Equation If the L Q formula (4) is reducible to some .W(~, if), the appfication of J / ( e , a; ~,~) to (19) yields a recurrence relation of dimension 2d, similar to (8), where the A i become

Ai

I,- h a [ - h & Id

- h

B] Zd]

with a corresponding matrix M(~) of dimension 2d. The characteristic equation now becomes, after the bilinear transformation

(tt):

det [r (z) Y(z) I d - h ~ (z) s (z) A - - h z s (z) ~ (z) B] = 0

(20)

and we have the following condition for systems of VIDEs:

Condition 4..At(Q, a; ~,~) is A-stable iff all the roots of the characteristic equation (20) lie in the left half plane Re z < 0 for all A and B such that all the eigenvalues of N have strictly negative real parts. 4.3. Remarks 4.3.1. If ~(~) -----0(~) and ~(~) ---=-a(~), M(~) reduces to 0 (~) l~.a--h a(~) N and Condition 3 to Theorem 2.

A-Stable LMS Methods for Volterra Integro-Differential Equations

93

4.3.2. If h tends to zero, Remark 3.3.4. remains valid.

4.4. A Necessary Condition toy A-stability In particular, if A and B can be diagonalized by the same transformation, we are reduced to the scalar case. Therefore the criterion derived in section 3 is a necessary condition. We now go one step further. Define two d • d matrices U and V as follows: U=T 1 A 1 TI'I;

Ax=diag:t~ ~)

Re 2!x}<0

i-----t... d,

V = T ~ Az T~ 1;

A~ = d i a g 2!~)

Re 2!s~< 0

i = t ... d

and put

A=U+V;

B=--UV.

The eigenvalues of N are then :t!il ( i = 4 . . . d , / ' = 1, 2). Hence the following condition is necessary. act [Z (z) X-- h U-- (X-- Y (z) h U) h V] has no zeros in Re z ~ 0. We already know that Y (z) is a positive real function; therefore {1-- ~7(z) h U) is nonsingular in Re z =>0 and the necessary condition can equivalently be written as:

( x - ?(z) h nl) -1 Czc~} z - h a l ) - h a, As r-,

(24)

must be nonsingulax everywhere in Re z ~ 0. If Y ( z ) ~ t]Z(z) we are immediately reduced to Theorem 2 and the only condition is Z(z) positive real. However, if ~ t / z and unless A~=2sl, it is always possible to choose T = T { t T, in such a way that matrix (2t) becomes singular for any given value of z, in particular for values in the right half plane. Hence a necessary condition for A-stability is Y (z)=--t/Z (z). Since this condition is also sufficient we have proved the following theorem: Theorem 6. The necessary and sufficient conditions for an algorithm, consisthag of an LMS method .oq'(Q,a) and a reducible LQ formula, and used for the numerical solution of general systems of VIDEs, to be A-stable, are that ~ (~, g) is A-stable and that the LQ formula is reducible to s a).

4.5. Comments 4.5.4. The reasoning of Section 4.4. remains valid if the range of the eigenvalues is restricted to a region smaller than Re 2 < 0. As a result, Theorem 6 remains true if the word A-stable is replaced b y D-stable, A (~)-stable, stiffly stable, or any other weaker form of stability (except zero-stability). 4.5.2. Obviously Theorem 5 remains true. 4.5.3. Unlike for ODEs, the class of A-stable algorithms for systems of VIDEs is more restricted than for a single equation. This is due to the fact that the scalar case yields trivially A~=2~ L

94

J, Matthys 8. Conclusion

I n view of 4.5.t. t h e s t a b i l i t y t h e o r y of linear algorithms for systems of V I D E s , based on a reducible L Q formula, reduces to t h e degenerate case of m e t h o d s of t h e t y p e ~ ' ( Q , a ; Q, a) a n d t h e form of s t a b i l i t y is t h a t of the LMS m e t h o d s a). F o r systems which degenerate to a n u m b e r of uncoupled scalar equations, a larger class of algorithms is acceptable, which t h e n h a v e to satisfy, in t h e case of A - s t a b i l i t y , Criterion 3.5. Acknowledgment. The author wishes to thank Dr. Y. Genin and Dr. Y. K a m p for m a n y valuable discussions and interesting suggestions throughout this work, and Prof. Dr. G. G. Dahlquist for his thorough reviewing and helpful comments. References t. Brunner, H., Lambert, J . D . : Stability of Numerical Methods for Volterra Integro-Differential Equations. Computing 12, 75-89 (1974) 2. Dahlquist, G. G.: A Special Stability Problem for Linear Multistep Methods. B I T 3, 27-43 (1963) 3. Genin, Y. : A New Approach to the Synthesis of Stiffly Stable Linear Multistep Formulas. I E E E Trans. Circ. Th. CT20, 352-360 (1973) 4. Genin, Y. : An Algebraic Approach to A-Stable Linear Multistep Multiderivative Integration Formulas. B I T 14, 382-406 (1974) 5. Linz, P. : Linear Multistep Methods for Volterra Integro-Differential Equations. J. ACM 16, 295-30t (t969) 6. Matthys, J. : A Class of Linear Multistep Methods for Volterra Integro-Differential Equations. MBLE Research Lab. Rep. 278, t974 7. Gear, C. W. : Numerical Integration of Stiff Ordinary Differential Equations. Univ. of Illinois, Urbana, Rep. 221, 1967 8. Widlund, O. B. : A Note on Unconditionally Stable Linear Multistep Methods. B I T 7, 65-70 (1967) 9. Sloate, H. M., Bickart, T. A. : A Stable Composite Multistep Methods. J. ACM 20, 7-26 (t973) 10. Lambert, J . D . : Computational Methods in Ordinary Differential Equations. London: J. Wiley and Sons t973 1 t. Oono, u Koga, T. : Synthesis of a Variable-Parameter One-Port. I E E E Trans. Circ. Th. CT10, 2t3-227 (t963) 12. Gantmacher, F. R. : Matrizenrechnung I. Berlin: VEB Deutscher Verlag der Wissenschaften 1958 J. Matthys MBLE Research Laboratory Avenue Van Becelaere, 2 B-t t 70 Brussels (Belgium)