THE UN I V E R S I T Y OF M I C H I GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Mathematics Technical Report No. 2 STABLE MATCHING OF DIFFERENCE SCHEMES Melvyn Ciment ORA Project 027750 under contract with: OFFICE OF NAVAL RESEARCH DEPARTMENT OF THE NAVY CONTRACT NO. NO0014-67-A-0181-0023 WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1972 Approved for public release; distribution unlimited.

_:7 ic > < } X to

STABLE MATCHING OF DIFFERENCE SCHEMES* Melvyn Ciment Department of Mathematics University of Michigan Ann Arbor, Michigan 48104 ABS TRACT Approximations that result from the natural matching of two stable dissipative difference schemes across a coordinate line are shown to be stable. The basic idea is to reformulate the matching scheme consistent to an equivalent initial boundary value problem and verify the algebraic conditions for stability of such systems. An interesting comparison to the above result is the case of redefinition of a scheme at a single point. In particular, we show that some unstable perturbations do not upset the stability of the Lax-Wendroff scheme. This research was supported by 0. N. R. Contract No. NR044-377. This research was performed while the author was a Visiting Lecturer at Tel-Aviv University, Tel-Aviv, Israel. Reproduction in whole or in part is permitted for any purpose of the United States Government.

-1 -INTRODUCTION A local regridding procedure for finite difference approximations, referred to as a mesh refinement scheme, was analyzed by the author in [1], [2] for hyperbolic partial differential equations. For parabolic equations the mesh refinement technique has been analyzed by Osher [10], Varah [11] and Ciment and Sweet [3]. The basic idea in the mesh refinement technique is to employ one underlying finite difference scheme consistent to a given partial differential equation on what are essentially two different grid patterns. In the above works it has been shown how to relate a given difference scheme across neighboring uneven mesh points in a stable and computationally efficient manner. The mesh refinement technique was proposed to help in solving problems where the solution has large gradients, discontinuities, or generally what we call frontal effects in a localized region. In general, use of a mesh refinement scheme for problems with moving frontal effects will necessitate the following additional work: 1) Prediction of direction of frontal motion. 2) Interpolation and storage (regridding) of the pertinent variables and data in advance of the frontal effect. 3) Special treatment for solving the resulting algebraic equations when implicit schemes are used (as in the parabolic case).

-2 - Inspite of the above extra work, in cases where the frontal effect itself causes changes in the grid domain, the mesh refinement scheme can be very effective [4] Another approach for treating problems with frontal effects is what we call the matching scheme technique. Here the strategy is to leave the grid uniform, wherever at all possible, but to locally change the underlying finite difference shceme to suit the local phenomenon. The matching technique, in the case of moving frontal effects, would also need feature (1) above, but would not suffer from the other two drawbacks. Thus, it is to be expected that when applicable, the matching scheme technique should be computationally more efficient than the mesh refinement technique for moving frontal effects. In the future we hope to report on numerical experiments comparing both these techniques. This paper considers the L stability of an approximation to a pure 2 initial value problem which results from the natural matching of two difference schemes across a coordinate line. As in our treatment of mesh refinements [1], [2], stability is analyzed by reformulating the matching scheme as a difference approximation to an initial boundary value problem for a system of partial differential equations. General sufficient conditions for the stability of such hyperbolic systems have been given by Kreiss [6], [7], and Osher

-3 -[9]. Using analogous results for parabolic systems obtained by Varah [11], we verify that a large class of matched parabolic schemes are L2 stable. As an interesting comparison to the above result, we examine the case of redefinition of a difference scheme at a single point. In particular we show that even some unstable perturbations do not upset the stability of the Lax-Wendroff scheme. It is obvious from our presentation that our approach can be used to study the stability of a given dissipative difference scheme with a local perturbation or a discontinuity. I. Formulation of Problem. Consider the Cauchy problem for the following hyperbolic equation (1.1) u = Au + Bu + Cu; u(x, y, z, 0) = (x, y,z) x y z in the region -oo < x, y, z < oo, t > 0. For simplicity, we take u and qp scalar functions and A constant and B = C - 0. Observe that following Kreiss [6] and the author [1], our results will hold for A,B,C Lipschitz continuous diagonal matrices if the difference schemes are also diagonal. Consider a set of uniform mesh points (x., t ) where n x. = j Ax; j= 0, +1 +2...; t t; n = 0, 1, 2.* 3J - - n

-4 -On this grid represent two different difference approximations to (1.1), (with B= C = O) as P1 (1.2a) V n+l Q Vn z C(1) Vn j 1 j a j+a P2 n+l n n (1.2b) U = QU C U J J Z=-r a j+a a —= -r M G) ( a where C C (ib) with b A, and where r. a a x x positive integers. By the matching of Q and Q, we mean the difference Q defined by 3 Z. Z.~ cons is tent and p are i i approximation Q2 Z' j = 0, -1, 2, *.. Our main result is that Q is L stable if both Q and Q are stable 2 1 2 and dissipative. For simplicity of notation we have considered explicit schemes, but it will be obvious from our proof that the same result holds for analogous implicit schemes.

-5 -We treat this analytically by using an equivalent formulation as an initial boundary value problem. It is convenient to obtain this by reflecting and shifting the difference functions used on the left hand side. Defining n n W. U gives 3 -J+1 r n+l n W. = Qz C( (-b) Wn 3J 2 J aj+ = -p as an approximation to u( -(j - 1) Ax, (n + 1) At ). Since V. denotes an approximation to u(j Ax, nA t), near the interface the following overlapping identification of grid points is implied (see diagram) n n W = i. 2P 2 _j+X = x=0 (Case p2 =2, rl 1) We complete the reformulation of this matching scheme as an equivalent system of difference equations for an initial boundary value problem by introducing the matrix notation

nv V. 3 n w" Then the precise expression n+ (1. 3a) ZK 0 -6 -j = 0, + 1, +... n = 0, 12,. * of the matching scheme Q is 0 n Z.; Q 2 J Q2 j = 1, 2,.. n = 0, 1, 2.. with boundary conditions I 0 1 (1.3b) Zn = 0Z; 1,.., r- 1 -j 3+1;JO.. 1 0 where r - max [r1, p ]. If p2 + rl these boundary conditions identify some additional overlapping points, but this does not alter the algorithm. Now the matching scheme expressed in (1. 3a, b) appears as an approximation to the system (1.4) Zt = Z t 0 -A with compatibility condition U( O, t) = W(O, t).

-7 -Sufficient conditions for the L stability of dissipative difference 2 approximations to initial boundary value problems of the above type have been given by Kreiss [6], [7] and Osher [9]. Accordingly, because of the diagonal structure of our systems, to prove stability it suffices to show that there are no eigensolutions of (1. 3a, b) of the form ~n Xn E oo (1.5) Z. | j| < J ~J j=l J for \ 1, I X > 1, and furthermore, that x = 1 is not a generalized (approximate) eigenvalue in the sense of Kreiss [6]. In the following it is assumed that the reader is familiar with the paper of Kreiss [6] or Corollary 1 of [2]. Briefly stated for our case, these say that the eigensolutions of interest are those where gj are formed using the characteristic roots of (1.6) having absolute value less than one. Furthermore, as -> 1, those characteristic roots in the component of n Z. corresponding to the positive diagonal element of the leading matrix in 3 (1.4) must have a limiting absolute value strictly less than one. Theorem. Let Q and Q defined by (1.2) each be a stable and 1 ^2 consistent dissipative approximation to (1, 1). Then the matching of Q and Q as defined in (1.3a, b) is a stable approximation. 2i

-8 -Proof. To find all eigensolutions of the form (1.5) it is sufficient to find all characteristics roots T.i(), i.(X) such that P1 p () (1.6a) k = C) (b) T. Cy -a=-r (1.6b) = (-b) x ) a = -PZ with I Ti(X) < 1 and t| i() | < 1. For X + 1, X 1, dissipativity implies the separation of the roots property [1], [6], that is, counting multiplicities there are only rl linearly independent characteristic roots Ti (2 roots i.) such that Ti < 1 (I il < 1 ). Furthermore, strict inequality remains for either all T. or all E. roots as X -> 1 All admissible eigensolutions can be expressed in the form d Z f(j) T. 1 1 i=1 n n (1.7) z; Ixj 1, + 1 2 (j) i=1

-9 -Here each distinct T. solves (1.6a) with multiplicity m. and f.(j) 1 1 1 is a polynomial of degree m.-, and each distinct p. solves (1. 6b) with multiplicity i.-1, and h.(j) is a polynomial of degree.- 1, and 1 1 1 d1 d2 i 1 i 2 i=l 1 i=l 1 Substitute Z. into the boundary conditions and find dl d -j j+d (1.8a) Z f (-j) T. + h h.(j + 1) 0 i=-1 i=l * j = O, 1,, dI d2 1 ~ ~+l _j (1.8b) Z f.(j +1) T + + h.(-j) = 0 1=1 1i=1 1 Now order the equations of group (a) from r - 1 to 0 and those group (b) from 0 to r to obtain d d ticj, ~~ ~~ -1 j-1 Z fOj) T + z h (-j +1) [K i *i i i i=1 i=1 vanishing at the 2r consecutive integers j = -r + 1, *., -1, 0, *.-, Despite the shift of indices, the set of difference functions r - 1. ' of r. fi(J) d U i(- + 1) [ 1 J i.l il

-10 -form a fundamental set for the linear homogeneous difference equation whose characteristic polynomial is d d 1 m m 2 1 -l i p(x) = I (X- T) (X - I i=l i=l Observe that p(x) is of degree rl + p2 and the linear combinations (1.8) vanish at 2r consecutive points. Since r + 2 < 2r, for a non-trivial: 2 solution this can only occur (See Theorem 5.3 [5]), if there are repeated d d d -1 d2 roots. Now the {Ti} and {[i } are separately sets of distinct i=1 i=l -1 roots by definition. Thus it must be for some i and m that T. = m 1 m This in turn implies that 1 = T. which implies that | T. | = | = 1, 1 1T 1 "m This establishes stability, since as remarked above all the roots of one group must be strictly less than one in absolute value even as - 1 We note that the same matching of two difference schemes with different mesh spacings is easily seen to be stable for the case r = p2 = 1 when Ax /Ax = 1/N, and N is a positive integer. 1 2 II. Parabolic Case. Recent results obtained by Varah [11] allow a similar analysis for the analogous matching scheme for second-order parabolic equations in one space dimension. For the case of matching diagonal parabolic difference

-11 -schemes, our above analysis remains valid and indicates that there are no eigenvalues X greater than one in modulus. Varah's sufficient condition can be expressed in the form that the determinant of essentially system (1.8) vanish of the order > 0(4X - 1 ) as - 1 We found this hard to verify in general. However, if p =r = r =2, after some simple operations the determinant in question is of Vandermonde form det SY = det{ (Ti -j+4 j j+4 2) 1 ' ~ 2 j =0, 1, 2, 3 (T -1) (T1-2) (T -1)(1-T 1)(22-1 )(T2-1). Varah shows that the separation of the roots for parabolic schemes is such that as -> 1 say, T1 = 1+ O( tI - 1) then T | < p < 1 say, = 1 + ( 1 ) then | P < 1. Only the first term in the expression for the determinant can vanish while all others are bounded away from zero. The first term gives the desired estimate. Thus, most of the well known schemes can be matched in a stable manner.

-12 -III. Local Redefinition of a Difference Scheme Consider the one dimensional case (1. 1) with the Lax-Wendroff =. W~n scheme [8] used at all points except x = 0. Then W. denotes an approximation to u(j Ax, na t) and is given by n+l n b-b n 2 n b+b n W = Q(b) W ( b ) + (- b) W + ( ) W 2 Jj-1 j 2 J+ A t for j = + 1,; n= 1, 2 *.. Here b = A - must be restricted by b | < 1 for stability of the pure initial value problem. We consider a simple case of locally redefining our scheme by some 3-point approximation which is also consistent to (1. 1) denoted by (3. 1) ~(3.1) ~ + = C-I W L4 + OWOa1 + a W n 0,2, 1, 2, Introducing a reflection of our problem, we express this locally perturbed scheme as the system of difference equations Q(b) 0 j = 1, 2, n+ _ (3.2a) Z Zn J J L 0 Q(-b) n = 0, 1, 2, with boundary conditions. * * ~

-13 -n+ 1 n (3. 2b) Z = a. Z i — 1 i=-l (1 - b - ) (1 +b- aO) where by consistency ac = 2 0 and ca = 2 u (x, t) jax = x Here Z. = A Z(x, t) = V Lv Lu(-x, t) nAt = t Now one needs to consider all eigensolutions of the form (1.5) for \ f 1, X i >.1. The separation of the roots property allows us to express these in the form 3J ~j = 1,, 2,. (3.3) Z = X z.J =2 n = 0, 1, 2 Z where IT1 < 1 (3.4) x = Q Observing that 2 concludes that T2. T2 I < 1 are the characteristic roots of [(i+1 b] i i = 1, 2. satisfies the reflected difference equation of T, one can be expressed as the reciprocal of the separated

-14 - T root, i. e. the inadmissible T root that is outside the unit circle. Thus, by product of the roots rule -1 b- 1 T1 b + 1 Substitution of (3.3) into (3.a, b) using this last relationship yields Substitution of (3. 3) into (3. 2a, b) using this last relationship yields - _ b. r b - 1 /1 \ j3^ c ~O L- bb - 1 '2 The table below lists the results of our stability analysis of the locally perturbed Lax-Wendroff scheme for several local redefinitions. The instabilities of (4) are apparent by the geometrical arguments of C.F.-L. For case (1), (3.5) implies X =. Cases (2) and (3) are more interesting since the perturbation schemes are separately unstable. However, for (2) we find that X = (1 + b ) < 1 and for (3) a short calculation using (3. 5) and (3. 4) gives I | 1 22 (1 - -b ) Since b l < 1 this guarantees stability. For the locally perturbed scheme, we have been unable to find any general result comparable to our above theorem on matching schemes.

-15 -aO Perturbation Scheme (3. 1) Redefined Scheme (3. Za, b) (1) 0 stable stable (2) 1 unstable unle ss b =0(Ax) stable 2 (3) 1-b /2 always unstable stable (4) 1-b stable for 1 > b > 0 stable unstable for b < 0 unstable

-16 -Bibliography [1] M. Ciment, Stable Difference Schemes with Uneven Mesh Spacings. A. E. C. Research and Development Report No. NYO-1480-100, New York University, June, 1968 (Ph. D. Thesis). [2] M. Ciment, "Stable Difference Schemes with Uneven Mesh Spacings" Math. of Comp. V. 25, No. 114 April, 1971, pp. 219-227. [3] M. Ciment and R. A. Sweet, "Mesh Refinements for Parabolic Equations", (To appear). [4] M. Ciment and R'. B. Guenther, "Numerical Solution of a Free Boundary Value Problem for Parabolic Equations", (To appear). [5] P. Henrici, Discrete Variable Methods in Ordinary Differential Equations, John Wiley, Publishers, New York (1962). [6] H.. Kreiss, Difference Approximations for Initial-Boundary Value Problems for Hyperbolic Differential Equations, Proc. Adv. Sympos. Numerical Solution of Partial Differential Equations (Madison, Wis. 1965), Wiley, New York, 1966 pp. 141-166 [7] H. 0. Kreiss, "Stability Theory for Difference Approximations of Mixed Initial Boundary Value Problems. I", Math. Comp., V. 22, 1968, pp. 703-714. [8] P. D. Lax, "Numerical Solution of Partial Differential Equations" Amer. Math. Monthly, Vol. 72, No. 2, Part II (1965) 74-84.

-17 -[9] S. Osher, "Systems of Difference Equations with General Homogeneous Boundary Conditions", Trans. Amer. Math. Soc. V. 137, 1969, pp. 177-201. [10] S. Osher, "Mesh Refinements for the Heat Equations", SIAM J. Num. Anal. 7 (June, 1970), pp. 199-205. [11] J. Varah, "Stability of Difference Approximations to the Mixed Initial Boundary Value Problem for Parabolic Systems", SIAM J. Num. Anal., 8 (1971), pp. 598-615

Unclassified < < \ 1 ( II.; tI k I. I I, I^ -* *W~ t2 CUMUNT CG. " ^ Dt..' i1. Oi lk,. INA 1 IN, AC tlVITY (t'orPi)fritJ.,itoir)..,i. 1iLi-'OII.L. CU I T Y CC A.,',,.A i. IC;<, Department of Mathematics Unclassified University of Michigan 26. GROUP Ann Arbor, Michigan 48103 j3 REPORT TITLE Stable Matching of Difference Schemes 4. 4, TII V I NOTES (i'ypo o raperi and lizclusive dates) Technical Report, January 1972, 5. AU THOR(S) (First name, middle initial, last name) Melvyn Ciment i6. REPORT DATE 17a. TOTAL NO. OF PAGES 76. NO. OF REFS il January, 1972 18 11 8a. CONTRACT OR GRANT NO. 9a. ORIGINATOR'S REPORT NUMBER(S) N00014-67-A-0181-0023 b. PROJECT NO. Technical Report No. 2 NR 044-377 c. - 9b. OTHER REPORT NO(S) (Any other numbers that may be assigned this report) d. 10. DISTRIBUTION STATEMENT Approved for public release; distribution unlimited. II. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Mathematics Program Office of Naval Research _______________________Arlington, Virginia 22217 13. ABSTRACT Approximations that' result from the natural matching of two stable dissipative difference schemes across a coordinate line are shown to be stable. The basic ideas is to reformulate the matching scheme consistent to an equivalent initial boundary value problem and verify the algebraic conditions for stability of such systems. An interesting comparison to the above result is the case of redefinition of a scheme at a single point. In particular, we show that some unstable perturbations do not upset the stability of the Lax-Wendroff scheme... fi~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~f I*I..:~~~~~;;;R~~~f&= ~~~~i~~sllLY351.;i~~~~~~.~~;i~~~ t~~il i~~CL~~~S~iiii-~~~~~~~~3~~Q;.;; ~ ~ D F,FORM N;. -'- "', J / 1 NO V C0 5 i 0 0 S/N 0101-807-6801 (PAGE ) Unclassified Security Classification

Unclassified: -_ -- St.cuTrry Clas sific. io:. ~ 4.~ ~. I I.~s. ~ i<N K A o. >s t\ i, { L.< iA '. KEY -WOii,'S _ --, q 0 L lC W T i 0 '.L v, ' ' Hyperbolic differential equations Mesh refinement Finite Differences Lax-Wendroff scheme \ ~ I 11 [I t. li I.i 1' 'N ~ i t_-.;i_ ', --- - I -,= Iown=.,!:""'. '.,~:, "~"7B3 (BACK) NO(PAGE 2) (PAGE' 2) Unclas s ified Security Classification

UNIVERSITY OF MICHIGAN 111113 90111111111111111111115 02828 5461 3 9015 02828 5461