CONVERGENCE OF A CLASS OF RUNGE-KUTTA

BIT33(1993). 137-150.CONVERGENCE OF A CLASS OF RUNGE-KUTTAMETHODS FOR DIFFERENTIAL-ALGEBRAICSYSTEMS OF INDEX 2LAURENT JAYUniversit de Gen ve, D partement de math matiques, Rue du Li vre 2-4,Case postale 240, CH-1211 Gen ve 24, Switzerland.e-mail: jay@c#euge51.bitnet or: jay@uni2a.unioe.ch.Abstract.This paper deals with convergence results for a special class of Runge-Kutta (RK) methods as appliedto differential-algebraic equations (DAE's) of index 2 in Hessenberg form. The considered methods arestiffly accurate, with a singular RK matrix whose first row vanishes, but which possesses a nonsingularsubmatrix. Under certain hypotheses, global superconvergence tbr the differential components is shown,so that a conjecture related to the Lobano IliA schemes is proved. Extensions of the presented results toprojected RK methods are discussed. Some numerical examples in line with the theoretical results areincluded.Subject classifications: AMS(MOS): 65L06.Key words: Differential-algebraic, index 2, initial value problems, Runge-Kutta methods.1. Introduction.Differential-algebraic equations (DAE's) of index 2 arise in many applications,such as in mechanical modelling of constrained systems (see [4, pp. 6-7] or [5, pp.483-486 & 539-540]). Whereas optimal convergence results for Runge-Kutta (RK)methods with an invertible RK matrix are well-known (see I-4, Section 4] and [5,Section VI.7]), this paper is concerned only with RK methods having a singular RKmatrix.The main result of this article (Theorem 5.2 below) proves a conjecture (see [4, pp.18, 46 & 47] and 1-5,p. 515]) related to the Lobatto IliA processes which belong tothe class of methods considered in this paper (see Section 2). Its proof necessitatesseveral preliminary results which are collected in Section 3 (properties of the RKcoefficients), in Section 4 (existence, uniqueness of the numerical solution, andinfluence of perturbations), and in Section 5 (estimates of the local error andReceived June 1991.Revised May 1992.

138LAURENTJAYconvergence). Extensions of the previous results to projected RK methods arediscussed in Section 6. Finally, some numerical experiments are given in Section7 which illustrate the theoretical results. Let us mention that all the results presentedin this paper remain valid for some other types of DAE's (for further details see [4,pp. 5 & 30]).In this report, we consider the following system of DAE's given in an autonomousand semi-explicit formulation (or Hessenberg form)y' f(y,z),0 g(y),(1.1)y(xo) y o s N " ,z(xo) Zo e R"where the initial values (Yo,zo) are assumed to be consistent, i.e.,(1.2)O(Yo) O,(orf)(Yo, Zo) O.We suppose that f and 9 are sufficiently differentiable and that(1.3)(9yf )(Y,Z)is invertiblein a neighbourhood of the exact solution (index 2).2. The class of Runge-Kutta methods.One step of an s-stage Runge-Kutta (RK) method applied to (1.1) reads (see [3], [4,p. 30] or [5, p. 502])(2.1a)Yl Yo biki,z Zo ii 1bil,i 1where(2.1b)k l f ( Y , Z , ) ,0 g(Y3and the internal stages are given by(2.1c)r, yo o,,k,,j 1z , zo a,/,.j 1For a R K m e t h o d w e denote A : (ai,)i.,the R K matrix,b: (bl,.,b )r the weightvector,and c : (el.c,)r : A , the node vectorwhere : (I. 1)r. Let B(p),C(q), D(r) be the following simplifyin9assumptions which are related to the construction of such methodsB(p): i bic -t 1/kk 1,.,p;i 1C(q): a,,c -l 4 / kj li 1. s, k l,.,q;

CONVERGENCEOF A CLASSOF RUNGE-KUTTAD(r): bic k-1i aij bj(1 - ck)/kMETHODSj 1,., s,. . .139k 1,., r.i 1Throughout this paper we are only interested in R K methods with s 2 andcoefficients satisfying the hypothesesH l : a l j 0 f o r j 1. s;H2: the submatrix ,4: (ai )i. 2 is invertible;H3: bl a,i for i 1. s, i.e., the method is stiffly accurate.For these methods, the lj in (2.1) are not well-defined, but in order to define y and z 1,it is sufficient to solve the equivalent nonlinear system (4.2) below and to apply thefourth remark hereafter.REMARKS. The following results can be easily proven.1) The definition of c coincides with the condition C(1).2) H3 together with the condition B(1) leads to Cs 1. If in addition C(q) (resp. D(r))is satisfied then B(q) (resp. B(r 1)) holds.3) F r o m H t it follows that cl 0, Y1 Yo, g(Y0 g(Yo) 0, Z I zoin(2.1),and that A is singular.4) H3 implies that Yl Y , g(Yl) g(Y ) 0, and zl Zs in (2.1).A main advantage of methods verifying H1 and H3 is that the first stage of onestep is equal to the last stage of the previous step which coincides with the currentinitial value, so that it requires no supplementary computation. The most prominentexamples of such methods are given by collocation methods like the Lobatto IliAschemes whose coefficients c 0, c2,., c, 1 are the zeros of the polynomial ofdegree sds--2(2.2)dx - 2 ( x S - l ( x - 1)s-l)and which fulfil the conditions B(2s -- 2), C(s), and D(s - 2). Due to their symmetry,they are often used for the solution of boundary value problems (see [2]).3. Properties of Runge-Kutta coefficients.This section deals with relations of the RK coefficients appearing in the demonstration of Theorem 4.4.THEOREM 3.1. Suppose that the hypotheses H1, H 2 and H3 are satisfied togetherwith the condition D(r). For a f i x e d p \{0}, consider a multi-index v (vl . . . . . vp)satisfying vi 1 and let O. Iftvl : vi r then we have

140LAURENT JAYer ,c"(3.1)M, A1 e r - , C ' M I . . . M o A , 0where we have set(3.2)C : diag(e2,., cs),AI: (a21. a l)T,es 1: ( 0 , . . . , 0 , 1)r.The matrices Mi are of the form A* , C * or AC '*A-* and it is supposed thatM. cvG -1.REMARK. W i t h o u t loss of generality p r can be assumed.PROOF. In matrix notation, the simplifying assumption D(r) becomes(3.3a)ffTck-*A k(3.3b)/TTCk- t l(gTgT k) k-lb,k 1,.,r,k 1. rwhere if: (bz,., b )T, and H3 reads(3.4a)/ r e T 1A(3.4b)bl eT 1A1 a ,.Multiplying (3.3a) with .4- * and using/TTA - 1 e T 1 which follows from (3.4a), weobtain(3.5)f f r t k 1 e T , -- kF)Tdk-';k 1,.,r.Repeated application of (3.3a), (3.4a), and (3.5) to (3.1) shows that this expression isa linear combination of terms/ rCr, - *A1 with 1 7 - r. T h e y all vanish because of(3.6)ffTC A-*A, eT IA1 -- ?bTC -tA1 bl - bl 0which is a consequence of (3.5), (3.4b), and (3.3b).[]LEMMA 3.2. Suppose that the hypotheses H1, H2, and H3 hold. Then R(z), thestability function of the method, satisfies at(3.7)R( ) -e,T , A - - 1 A,.PROOF. R(z) is the numerical solution after one step of the m e t h o d applied to thetest equation(3.8)y' 2y,Yo 1,with z : h2. By using H3 we get R(z) y, Y e f ( I - zA)-* . The resultfollows from

141CONVERGENCE OF A CLASS OF RUNGE-KUTTA M E T H O D S . . .(3.9)(I - z A ) - 1( o(l -I - zA)-lzAl(I -1 -- z/l) -1)-A-1A1"4. Existence, uniqueness and influence of perturbations.This section is mainly devoted to the demonstration of Theorem 4.4, which is thefundamental result. We first investigate existence and uniqueness of the solution ofthe nonlinear system (2.1) where (Yo,z0) are replaced by approximate h-dependentstarting values ( , 0.THEOREM 4.1. Suppose that(4. la)g(q) O,(4. lb)(g,f)(t h () O(h),(4. lc)(gff )(y, z) is invertible in a neighbourhood of (q, 0,and that the RK coefficients verify the hypotheses H1 and H2. Then for h ho thereexists a locally unique solution to(4.2a)Yi q h aJ'(Yj, Zi)j l(4. 25)0 g(Y )//i 1, .,s""Jwith Z 1 : and which satisfies(4.3)Y - I? O(h),Z , - ( O(h).REMARKS.1) Y1 q, implied by H1, shows the necessity of(4.1a).2) The value of( in (4. lb) specifies the solution branch of(gyf)(y, z) 0 to which thenumerical solution is close.We omit the proof which can be obtained similarly as in [4, Theorem 4.1] or [5,Chapter VI, Theorem 7.1] covering the case of invertible RK matrix A. Our next result is concerned with the influence of perturbations to (4.2).THEOREM4.2. Let Yi, Zi be the solution of(4.2) and consider perturbed values , Zisatisfying

142LAURENT JAY(4.4a) fl h aijf( ,2j) h61(4,4b)0 g( ) 01j li 1,.,swith Z1 : . In addition to the assumptions of Theorem 4.1, suppose that(4.5)0-rt--O(h),2 - ( O(h),3i O(h),Oi O(h2).Then we have for h ho the estimates(4.6a)II - Y II - C(ll - rttl h 2 II - (11 h 11611 II011),(4.6b)112 - Z, It h ( h I1 - rttl h II( - ll h 11611 HOII)where 6 (31 . . . . . 6,) r,116I1 max II6 tl and similarly for O.REMARKS.1) The conditions (4.5) ensure that all terms O(-) in the p r o o f below are small.2) The terms containing - ( will be c o m p u t e d in detail. This will be justified in thedemonstration of T h e o r e m 4.4.3) We introduce the notation Art -- rt, A( - (,Y (Y1,--., Ys)T,A Y Y - Y,, ilAIql maxi IlAY/ll and similarly for the z-component. Overa multiple-vector a tilde ' ' indicates the removal of its first subvector, e.g., " (Y2. y )r.PROOF. H1 implies that Y1 -- rt and 1 ] 0 h61. Therefore we haveAY1 Art h61,(4.7)AZ A(which proves the statement (4.6) for i 1. Hence from (4.2b) and (4.4b) we deducethatgr(rt)Art O(h IIArtll h IIb [t II0 ll).(4.8)F o r i 2, by subtracting (4.2) from (4.4) we obtain by linearization(4.9a)AYi Art h i aiJfr(YJ,ZJ)AY h aljf ( ,Z )AZ ij lj l hfi O(h NAYII2 h ItAYI[ " tIAZII h IIAZtI2),(4.9b)0 gr(Y/)AY/ Oi O(HAY/[]2) It can be noticed that if fzz 0 ( f linear in z) the expression O(h IIAZII2) in (4.9a)disappears, but O(h IIAY[I " IIAZII) remains. Therefore we retain all terms permittingto analyse easily this situation (see the first remark after T h e o r e m 4.4). By usingtensor notation, (4.9) can be rewritten with the help of (4.7) as

CONVERGENCE(4.10a)OF A CLASSOF RUNGE-KUTTAMETHODS. . .143AY ls- Aq h(A I.){fr}AY A (fz(q, 0hA0 (sl I,,){fz}haZ hS O(h IIA 'II 2 h IIAYII IIAZII h IIAZll 2 h IIAnlI h 2 I1, 1t),(4.10b)0 {O ,}AY O O(IIA?II 2)where(4.11a){fy): blockdiag(L(Y2, Z2) . f (Y , Zs)),(4.lib){f } : blockdiag (fz(Yz, Z2),., f (Y , Zs)),(4.1 lc)(gy} : blockdiag (gy(Yz),., gy(Y )).Insertion of the expression (4.10a) into (4.10b) yields(4.12)- {gr}(/l I,){f }hk2 {gr}( s l A / h(/l I,){J }AY A1 (fz(q, 0hA0 h ) i f O(tla?ll 2 h IIA?It" tlAZtt h ttAZtt 2 h llA #tl h 2 lt,hlt).In view of (4.3) we have(4.13)gr(Yi)aufz(Ys, ZS) au(grf )(rl, 0 O(h),thus the left matrix of (4.12) can be written as(4.14){gy}(/ @ I,,){f:} /T (gyf )(r#,0 O(h)and is invertible by H2 and (4. lc) ifh is sufficiently small. Hence from (4.12), and bythe use of (4.8) for (4.15'), we get(4.15) hAZ -({gr}(A I,){f:})- l{gy}x (l,-t At/ h(/l I,){fy}AY / l l (fz(##,0hA0 O(IIA II 2 h tlA?II IIAZtl h tlA tl 2 h IIAnll h IIA II2 h2 II 11t h tl3"II I1#II)(4.15') -({gr)(A I,,){f:})- ' {gr}(/T, @ (f (q, 0hA0) O(h tta?tl h IIA2112 h tlAnll h ItAffll 2 h If,51t ll0N).(4.15) inserted into (4.10a) leads to(4.16)A - P.7(l -x A / h(,4 I,){fr}AY A (f ( /,0hA0) O(tlA?II 2 h tlA?II" tlAZII h tlA2tl 2 h IIAr#ll h IIA(tl 2 h 2 I1, II h IID"ll IIOII),with the following definitions