REGULARIZATION METHODS AND FOR DIFFERENTIAL THEIR NUMERICAL EQUATIONS SOLUTION By Ping Lin B . Sc. (Mathematics), Nanjing University, Nanjing, P . R . C h i n a , 1984 M . Sc. ( A p p l i e d Mathematics), Nanjing University, Nanjing, P . R . C h i n a , 1987 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR OF P H I L O S O P H Y in T H E F A C U L T Y OF G R A D U A T E STUDIES INSTITUTE OF A P P L I E D MATHEMATICS D E P A R T M E N T OF MATHEMATICS We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH C O L U M B I A December 1995 Â© P i n g L i n , 1995 In presenting degree at the this thesis in University of freely available for reference copying of department partial fulfilment British Columbia, and study. of by his or her may be It publication of this thesis for financial gain shall not Department of HtxttiemJ-ics The University of British Columbia Vancouver, Canada Date DE-6 (2/88) T>ec-e^U-<- i"l , 19*1 ^ that the I further agree representatives. permission. requirements I agree this thesis for scholarly purposes or the is that an advanced Library shall make it permission for extensive granted by the understood be for that allowed without head of my copying or my written Abstract M a n y mathematical models arising i n science and engineering, including circuit and device simulation i n V L S I , constrained mechanical systems i n robotics and vehicle simulation, certain models i n early vision and incompressible fluid flow, lead to computationally challenging problems of differential equations w i t h constraints, and more particularly to high-index, semi-explicit differential-algebraic equations ( D A E s ) . T h e direct discretization of such models i n order to solve them numerically is t y p i c a l l y fraught w i t h difficulties. We thus need to reformulate the original problem into a better behaved problem before discretization. Index reduction w i t h stabilization is one class of reformulations i n the numerical solution of high index D A E s . Another class of reformulations is called regularization. T h e idea is to replace a D A E by a better behaved nearby system. This method reduces the size of the problem and avoids the derivatives of the algebraic constraints associated w i t h the D A E . It is more suitable for problems w i t h some sort of singularities i n which the constraint Jacobian does not have full rank. Unfortunately, this method often results i n very stiff systems, which accounts for its lack of popularity i n practice. In this thesis we develop a method which overcomes this difficulty through a combination of stabilization and regularization i n an iterative procedure. We call it the sequential regularization method ( S R M ) . Several variants of the S R M which work effectively for various circumstances are also developed. T h e S R M keeps the benefits of regularization methods and avoids the need for using a stiff solver for the regularized problem. Thus the method is an important improvement over usual regularization methods and can lead to improved numerical methods requiring only solutions to linear systems. T h e S R M also provides cheaper and more efficient methods than the n usual stabilization methods for some choices of parameters and stabilization m a t r i x . We propose the method first for linear index-2 D A E s . T h e n we extend the idea to nonlinear index-2 and index-3 problems. T h i s is especially useful i n applications such as constrained m u l t i b o d y systems which are of index-3. Theoretical analysis and numerical experiments show that the method is useful and efficient for problems w i t h or without singularities. W h i l e a significant body of knowledge about the theory and numerical methods for D A E s has been accumulated, almost none of it has been extended to partial differential-algebraic equations ( P D A E s ) . A s a first attempt we provide a comparative study between stabilization and regularization (or pseudo-compressibility) methods for D A E s and P D A E s , using the incompressible Navier-Stokes equations as an i n stance of P D A E s . Compared w i t h stabilization methods, we find that regularization methods can avoid imposing an artificial boundary condition for the pressure. T h i s is a feature for P D A E s not shared w i t h D A E s . T h e n we generalize the S R M to the nonstationary incompressible Navier-Stokes equations. Convergence is proved. A g a i n nonstiff time discretization can be applied to the S R M iterations. Other interesting properties associated w i t h discretization are discussed and demonstrated. T h e S R M idea is also applied to the problem of miscible displacement i n porous media i n reservoir simulation, specifically to the pressure-velocity equation. A d v a n tages over m i x e d finite element methods are discussed. E r r o r estimates are obtained and numerical experiments are presented. F i n a l l y we discuss the numerical solution of several singular perturbation problems which come from many applied areas and regularized problems. T h e problems we consider are nonlinear turning point problems, a linear elliptic turning point problem and a second-order hyperbolic problem. Some uniformly convergent schemes w i t h respect to the perturbation parameter are constructed and proved. A spurious solution phenomenon for the upwinding scheme is analyzed. iii Table of C o n t e n t s Abstract ii L i s t of Tables vii L i s t of F i g u r e s viii Acknowledgement 1 2 ix Introduction 1 1.1 Regularization for Differential-Algebraic Equations ( D A E s ) 1 1.2 Regularization for the Incompressible N a v i e r - Stokes equations . . . . 7 1.3 A P r o b l e m i n Reservoir Simulation 8 1.4 Regularization for Differential Equations without Constraints 10 1.5 Contribution of This Thesis 12 S e q u e n t i a l R e g u l a r i z a t i o n M e t h o d s for Differential A l g e b r a i c E q u a - tions 15 2.1 M o t i v a t i o n of the S R M for General H i g h Index D A E s 15 2.2 Linear Index-2 Problems 21 2.3 P r o b l e m Conditioning 23 2.4 Derivation of the S R M 27 2.5 Convergence Analysis of the S R M 30 2.6 Discretization and Implementation Issues 34 2.7 N u m e r i c a l Experiments 41 2.8 M o r e about the Proof of Theorem 2.1 46 iv 3 S R M for N o n l i n e a r P r o b l e m s 52 3.1. Nonlinear, Nonsingular Index-2 Problems 53 3.1.1 55 3.1.2 T h e case ct = 0 58 x 3.2 Nonlinear, Singular Index-2 Problems 62 3.3 S R M for Nonlinear Higher-index Problems 64 3.3.1 65 3.3.2 4 T h e case ct\ = 1 T h e case of nonsingular GB T h e case for constraint singularities 71 3.4 S R M for Constrained M u l t i b o d y Systems 72 3.5 N u m e r i c a l Experiments 75 S R M for the N o n s t a t i o n a r y Incompressible N a v i e r - S t o k e s E q u a t i o n s 83 4.1 D A E Methods for Navier-Stokes Equations 4.2 Preliminaries and the Properties of the Regularized Problems 4.3 Convergence of the S R M 94 4.3.1 T w o linear auxiliary problems 94 4.3.2 T h e error estimate of S R M 97 4.4 5 6 83 . . . . Discretization Issues and N u m e r i c a l Experiments 88 103 S R M for the S i m u l a t i o n of M i s c i b l e D i s p l a c e m e n t i n P o r o u s M e d i a l l 2 5.1 Introduction 112 5.2 S R M Formulation 113 5.3 Convergence Analysis 116 5.4 T h e Galerkin A p p r o x i m a t i o n and Its Error Estimates 120 5.5 N u m e r i c a l Experiments 122 N u m e r i c a l M e t h o d s of Some S i n g u l a r P e r t u r b a t i o n P r o b l e m s v 127 6.1 6.2 6.3 One Dimensional Quasilinear Turning Point Problems 128 6.1.1 A repulsive turning point problem 128 6.1.2 A n attractive turning point problem 133 Notes about Spurious Solutions of U p w i n d Schemes 139 6.2.1 Inadequacy of Yavneh's argument 139 6.2.2 Our explanation 141 A Linear Hyperbolic-Hyperbolic Singularly Perturbed Initial-Boundary Value P r o b l e m 7 145 6.3.1 Construction of asymptotic solution and its remainder estimate 147 6.3.2 Difference scheme and its uniform convergence 150 C o n c l u s i o n and Future W o r k 154 7.1 S u m m a r y and conclusions 154 7.2 Discussion of future work 157 Bibliography 160 vi'. L i s t of Tables 2.1 S R M errors for E x a m p l e 2.2 using the midpoint scheme 43 2.2 S R M errors for E x a m p l e 2.2 using the shooting-back technique 2.3 S R M errors for E x a m p l e 2.3 using backward Euler 44 2.4 S R M errors for E x a m p l e 2.3 using forward Euler 45 2.5 Errors near singularity using modified formula (2.42) 45 2.6 Errors for problem without singularity using modified formula (2.42) 45 3.1 Errors for E x a m p l e 3.3 using the explicit second order R u n g e - K u t t a . . . 44 scheme 76 3.2 E x a m p l e 3.4 - bounded y and singularity at t* = .5 78 3.3 E x a m p l e 3.5 - unbounded y and singularity at t* = .5 78 3.4 Errors for E x a m p l e 3.6 using S R M 80 3.5 Drifts of the S R M for the slider-crank problem 4.1 S R M errors for \x = 0.1 without upwinding 109 4.2 S R M errors for fj, = 0.001 w i t h upwinding 110 4.3 S R M errors for /i = 0.001 with a pretty large time step k = h = 0.1 4.4 S R M errors for \x = 0.1 w i t h a i = 0 Ill 5.1 N u m e r i c a l results for E x a m p l e 5.1 w i t h grid size = 4^ 126 5.2 N u m e r i c a l results for E x a m p l e 5.1 w i t h grid size = ^ 126 5.3 N u m e r i c a l results for E x a m p l e 5.2 126 vii (3.45)-(3.46) 81 . 110 L i s t of Figures 2.1 planar slider-crank: initial state i n solid line, subsequent states i n dotted lines 17 3.1 Two-link planar robotic system 79 3.2 Solution for slider-crank problem w i t h singularities 81 3.3 Acceleration of slider end 82 5.1 One element w i t h velocity on each edge and pressure at the center vm . 123 Acknowledgement I a m specially grateful to D r . U r i Ascher, my thesis supervisor, who contributed significantly to the development of this thesis. T h a t contribution ranged from fruitful suggestions and enlightening discussions to general guidelines and ideas about how to present the results. I a m also grateful to Drs. John Heywood, T i m Salcudean, M i c h a e l W a r d and B r i a n W e t t o n , members of m y supervisory committee, for their helpful comments and suggestions during this research and writing of the thesis. I would also like to thank the financial supports from K i l l a m pre-doctoral fellowship committee and from Department of Mathematics, University of B r i t i s h C o l u m b i a . Most of all, I wish to acknowledge the tolerance displayed by m y wife, Yuchun, and by m y daughter, Xueshu (Susan) during this work. This thesis work often dominated the evenings, weekends and summers which could have been used in activities of greater interest to them. ix Chapter 1 Introduction M a n y mathematical models arising i n science and engineering, including circuit and device simulation i n V L S I , constrained mechanical systems i n robotics and vehicle simulation, certain models i n early vision and incompressible fluid flow, lead to computationally challenging problems of differential equations w i t h constraints, and more particularly to high-index, semi-explicit differential-algebraic equations ( D A E s ) . T h e direct discretization of such models i n order to solve them numerically is typically fraught w i t h difficulties, and most methods proposed i n the literature seek to circumvent this by employing combinations of problem reformulation, regularization 1 and special discretization techniques. We w i l l consider the regularization of such mathematical models and the numerical solution of the resulting regularized formulations. These formulations are often singular perturbation problems because they typically depend on a small parameter which provides a measure of the closeness between the regularized and the original problems. We w i l l also apply our regularization method and idea to other relevant practical problems. 1.1 R e g u l a r i z a t i o n for D i f f e r e n t i a l - A l g e b r a i c E q u a t i o n s ( D A E s ) D A E s are special implicit ordinary differential equations ( O D E s ) ^ h e concept of regularization was introduced by Tikhonov (see [109]). Its idea is that one solves a better behaved nearby problem instead of solving the original problem to circumvent some sort of difficulties. See the next section for more details. 1 2 Chapter 1. Introduction where the partial Jacobian m a t r i x f (y,x,t) y arguments. Here x' = is singular for a l l relevant values of its A n extension to partial differential equations is considered in the next subsection. D A E s were motivated by applications like network analysis, circuit simulation and mechanical system simulation starting i n the 1970's. T h e y often arise as ordinary differential equations w i t h additional variables and (equality) algebraic constraints. A n extensive list of applications is given i n [92]. In the 1980's, D A E s have developed into a highly topical subject of computational and applied mathematics. Contributions devoted to D A E s have appeared i n various fields, such as applied mathematics, scientific computation, mechanical engineering, chemical engineering, system theory, etc. Frequently, other names have been assigned to D A E s , e.g. semistate equations, descriptor systems, singular systems. Gear ([51], 1971) proposed to handle D A E s numerically by backward differentiation formulas ( B D F ) . For a long time D A E s had been considered not to differ essentially from regular implicit O D E s i n general. O n l y since about 1980, because of computational results that could not be brought into line w i t h the above supposition (e.g. Sincovec et al [103], 1981), the mathematical and particularly the numerical community have started investigating D A E s more thoroughly. W i t h their famous paper, Gear, H s u and Petzold ([52], 1981) started a discussion on D A E s that w i l l surely be carried on for a while. T h e structure of D A E s is very much related to the concept of index, which is a measure of the amount of singularity of the system. There are several ways to define index. T h e most popular one is called differential index, which is defined as the m i n i m a l number of analytical differentiations i n t such that (1.1) can be transformed by algebraic manipulations into an explicit ordinary differential system (in the original unknowns) x' '= (f>(x,t) Chapter 1. Introduction 3 which i n t u r n is called the "underlying O D E ". There are several structural forms of D A E s which appear frequently i n applications (see [92]). T h e differential index of these structural forms can be found by differentiating their algebraic constraints w i t h respect to t (and substituting into the differential equations which complement the algebraic constraints). For instance, â€¢ Semi-explicit index-1 system x = f(x,y), (1.2a) 0 = g(x,y), (1.2b) f(x,y), (1.3a) g(x), (1.3b) x' = f{x,y), (1.4a) y' = k(x,y,z), (1.4b) 0 g(x), (1.4c) if g is invertible. y â€¢ Hessenberg index-2 system x' = 0 = if g f is invertible. x y â€¢ Hessenberg index-3 system if g f k x y z = is invertible. Mechanical multibody systems w i t h holonomic con- straints are examples.of Hessenberg index-3 D A E s . In [56] it is pointed out that higher index (> 2) D A E s , i n the natural function space formulations, lead to ill-posed 2 problems because they do not have the usual A problem is called ill-posed if it is not well-posed. A problem is called well-posed if it satisfies three conditions, i.e. the existence, uniqueness and stability of its solution. "Stability" means that the solution of the problem continuously depends on the "data", which may be initial data, boundary data, coefficients in the equation, values of the operator, etc.. Here high-index D A E s fail to satisfy a stability condition. 2 Chapter 1. Introduction 4 stability property of differential equations i n general. E x a m p l e 1.1 Consider (See [86]) x' = y,' (1.5a) 0 - x-p(t), (1.5b) where x(t) and y{t) are scalar functions and p(t) is a given function. This is a very simple index-2 DAE. The exact solution is x = p(t), y â€” p'(t). If we add a small perturbation 5smut, 8 << 1, to the right hand side of the second equation we have the exact solution x = p(t) + 8 sin uit, y = p'(t) + 8u> cos tot. Hence y â€” y = StocosLot could be very large if to 3> 1/8, i.e. the solution changes a lot under a small change in the right-hand side of the equation. â€¢ A numerical method which is directly applied to a complex, ill-posed problem may generally fail. Therefore, to solve D A E s , we have to stabilize such problems to bring about continuous dependence on the "data" (or stability). One such approach is to change the formulation of the problem but not its solution, e.g. i n E x a m p l e 1.1 we differentiate (1.5b) once and obtain x' = y (1.6a) 0 = y-p'{t), x ( 0 ) = p ( 0 ) . (1.6b) Now (1.6) is of index-1 and becomes a well-posed problem w i t h the same solution as (1.5). We can solve (1.6) instead of (1.5) and gain well-posedness. However, such a direct index reduction procedure may cause the well-known drift difficulty (see [29]), i.e. the approximate solution of (1.6) may be far from satisfying the constraint (1.5b). Chapter 1. Introduction 5 Hence, methods have been designed to prevent moving away from the constraints. Baumgarte's stabilization [17] and projection invariant methods (cf. [16]) are popular among such methods. Most of these approaches treat i n i t i a l value problems, and only a few apply to boundary value problems. See [29, 58] for various numerical methods for i n i t i a l value problems; [93, 7, 15] for boundary value problems; and [16, 9, 35] for a survey of various stabilization reformulations. Another approach consists i n adding some small perturbation terms (measured by a small positive parameter e) to the given D A E . T h e perturbed problem is close to the original problem (if e is small) and is well-posed. Such an approach is usually called regularization. This is a natural approach since the high-index D A E is i l l posed; indeed i n [43] a well-known Tikhonov regularization algorithm (see [109]) was applied to solve D A E s . However, such a method seems so general that it is not sufficiently related to the special structure of the D A E . There are two types of regularization methods which are probably more interesting for D A E researchers. One is called parameterization. One such possibility, the pencil regularization, was given independently by Boyarintsev [24] (or see his newer book [25] published i n English) and C a m p b e l l [32]. B u t the regularized problem is ensured to be well-posed only for constant coefficient cases. A further parameterization was proposed by M a r z [85]. Her regularization is aimed at obtaining well-posed index-1 D A E s instead of obtaining well-posed O D E s . Heuristically, it seems evident that the D A E is less changed i f it is transformed into an index-1 D A E rather than an O D E . M a r z ' s regularization was proved to be well-posed for usual structural forms of D A E s . W e refer to [59] for further results i n this direction. Another class of regularization uses the penalty idea (see [84, 91]). It originates from penalty methods for constrained optimization problems. Note that an algebraic equation i n a D A E can be viewed as a constraint. This method seems more natural for D A E s . References [68, 70, 69] used the penalty regularization and singular 6 Chapter 1. Introduction perturbation theory to determine the solutions of D A E s when the i n i t i a l or boundary values are given improperly (i.e. inconsistently). In Chapter 2 we w i l l mention these methods again w i t h a bit more detail and indicate that Maxz's regularization is actually a k i n d of penalty method. Because the regularization method requires fewer differentiations of the constraints it is perhaps more suitable for D A E s which have singularities, i.e. whose constraints do not have full rank, e.g. when the m a t r i x g f is singular at some isolated points x y in the index-2 system (1.3). These problems can be challenging for the methods that are usually employed and appear frequently i n simulation of constrained mechanical systems. To our knowledge, there has not been a paper i n the numerical analysis literature about this u n t i l the recent two preprints [11] and [94] (although a number of relevant papers appear i n the mechanical engineering literature). F r o m a practical point of view, a number of codes which work well and efficiently (at least i f the regularization parameter e is not too small) are available for numerically solving the regularized problems. W e also note that the regularization method requires less smoothness of the coefficients of the differential-algebraic problem than other stabilization methods. These are the advantages of-the regularization method. T h e dominant disadvantage i n the above regularization methods is that the parameter e must be small enough to maintain the accuracy of the numerical method we use for the regularized problem at an acceptable level. Hence, a stiff solver is necessary. T y p i c a l l y i n regularization methods, the parameter e must be chosen both "large enough" and "small enough": large so that the regularized problem would behave significantly better than the original, and small so that its solution w i l l not differ too much from that of the original problem. We w i l l present a class of new regularization methods, inspired by [19], which we call sequential regularization method ( S R M ) . T h e S R M can be viewed as a combination of the penalty method w i t h Baumgarte's stabilization i n an iterative procedure; Chapter 1. Introduction 7 see Â§2.4 or Â§3.1 for specific instances. It is applicable for D A E s w i t h constraint singularities. Moreover, the regularization parameter e i n the method is not necessarily small. Thus, a nonstiff solver can be used for solving the regularized problems. Some variants of the S R M are discussed for index-2 and index-3 D A E s w i t h the goal of simplifying the computations. We will apply the S R M to mechanical m u l t i b o d y systems as well. 1.2 R e g u l a r i z a t i o n for the Incompressible Navierâ€” Stokes equations As noted before, D A E s have become a highly topical subject of applied and numerical mathematics. However, there seems to be still a void i n the literature about partial differential equations w i t h constraints ( P D A E s ) . A typical instance of such problems is the well-known incompressible Navier-Stokes equations: Ui + (u â€¢ grad)u = divu = u\ dn = b , / ^ A u â€” gradp + f, 0, u| (1.7a) (1.7b) < = 0 = a, (1.7c) in a bounded two- or three-dimensional domain fi and 0 < t < T. Here u(x,Â£) represents the velocity of a viscous incompressible fluid, p(x, t) the pressure, f the prescribed external force, a(x) the prescribed initial velocity, and b(t) the prescribed boundary values. T h e system (1.7) can be seen as a partial differential equation w i t h constraint (1.7b) w i t h respect to the time variable t. Hence, we call it a P D A E . It is easily verified that it is of index-2 without singularities since the operator divgrad = A is invertible (under appropriate boundary conditions). A huge number of methods have been designed to solve the nonstationary incompressible Navier-Stokes equations (1.7). Direct discretizations include finite difference Chapter 1. Introduction 8 and finite volume techniques on staggered- grids (e.g. [65, 26, 66]), finite element methods using conformal and nonconformal elements (e.g. [54, 110, 63, 64]) and spectral methods (e.g. [33]). Another approach yielding many methods has involved some i n i t i a l reformulation and/or regularization of the equations, to be followed by a discretization of the (hopefully) simplified system of equations. Examples of such methods include pseudo-compressibility methods, projection and pressure-Poisson reformulations (e.g. [36, 55, 72, 97, 102, 117]). T h e two types of regularizations we mentioned i n Â§1.1 for D A E s were already proposed i n the Navier-Stokes context quite a while ago (cf. [108, 72]). We are interested i n the generalization of the S R M to this problem because the regularized problems can be made essentially nonstiff and then a more convenient difference scheme (e.g. an explicit scheme) i n time is possible. Moreover, the method retains the benefits of the penalty method. For example, computations for the velocity u and the pressure p are uncoupled and an artificial boundary condition for calculating the pressure p is not necessary. 1.3 A P r o b l e m in Reservoir Simulation T h e idea of the S R M can be applied to a reservoir-simulation problem â€” miscible displacement i n porous media. Miscible displacement is an enhanced oil-recovery process that has attracted considerable attention i n the petroleum industry. It involves injection of a solvent at certain wells i n a petroleum reservoir, w i t h the intention of displacing resident o i l to other wells for production. This oil may have been left behind after primary production by reservoir pressure and secondary production by waterflooding. T h e economics of the process can be precarious, because the chemicals it requires are expensive and the performance of the displacement is by no means guaranteed. C o m p l e x physical behavior i n the reservoir w i l l determine whether enough additional o i l is recovered Chapter 1. Introduction 9 to make the expense worthwhile. A numerical simulation of the complex process undoubtedly plays an important role. Mathematically, the process is described by a convection- dominated parabolic partial differential equation for each chemical component i n the system. B y summing up the component equations, one can obtain an equation that determines the pressure in the system; this nonlinear equation is elliptic or parabolic, according to whether the system is incompressible or compressible. Thus, i n this problem one encounters elliptic, parabolic, and near-hyperbolic equations w i t h complicated nonlinear behavior. For simplicity, we consider the miscible displacement of one incompressible fluid by another i n a porous reservoir ft C R 2 over a time period [0,T]. Let p ( x , i) and u ( x , t ) denote the pressure and Darcy velocity of the fluid mixture, and c(x, t) the concentration of the invading fluid. T h e n the mathematical model is a strongly coupled nonlinear system of partial differential equations (see [44, 82]): u = - a ( g r a d p - 7gradcf), divu = q(x,t), (x, t) G ft x [0, T], (x,<) â‚¬ ft x [ 0 , r ] , (1.8a) (1.8b) dc 4>â€” - div(D(u)gradc) + u â€¢ g r a d e = g(c), (x, t) â‚¬ ft x [0, T ] , (1.8c) w i t h the boundary conditions u n = 0, ( x , t ) â‚¬ T x [0,T], Â£ > ( u ) g r a d c â€¢ n = 0, (1.9a) (x, t) â‚¬ T x [0, T], (1.9b) xeft, (1.10) and i n i t i a l condition c(x,0) = co(x), where a = a ( x , c ) is the mobility of the fluid mixture, 7 = 7(x,c) and c?(x) are the gravity and vertical coordinate, q is the imposed external rates of flow, <Â£(x) is Chapter 1. Introduction 10 the porosity of the rock, D is the coefficient of molecular diffusion and mechanical dispersion of one fluid into the other, g = g(x, t,c) is a known linear function of c representing sources, and n is the exterior normal to the boundary V = <9fi. T h e pressure-velocity equation (1.8a)-(1.8b) is elliptic (after eliminating u). T h e concentration equation (1.8c) is parabolic, but normally convection- dominated. It is derived from the conservation of mass which involves the Darcy velocity of the fluid mixture, but the pressure variable does not appear i n i t . Thus a good approximation of the concentration equation requires accurate solution for the velocity variables. M i x e d finite element methods have been applied to the pressure-velocity equation, which can yield velocity solutions one order more accurate than those obtained using corresponding finite difference and usual finite element methods [40, 41, 42, 46, 47, 120]. However, the finite dimensional spaces for the velocity and pressure need to satisfy the Babuska-Brezzi condition, and the resulting linear system does not have a positive definite coefficient matrix. Moreover, the number of degrees of freedom i n the linear system doubles that of finite difference or finite element methods. W e are interested i n designing an S R M for the pressure-velocity equation since the S R M formulation can produce as accurate a velocity approximation as the m i x e d finite element methods, and can avoid the above-mentioned problems i n m i x e d finite element methods. 1.4 R e g u l a r i z a t i o n for Differential E q u a t i o n s w i t h o u t C o n s t r a i n t s Regularization methods are also used to treat differential equations without constraints when these equations have some sort of singularities or their solutions m a y have some sort of discontinuities. Examples are viscous solutions of hyperbolic conservation laws [76], shape from shading problems w i t h singularities [34] and transition Chapter 1. Introduction 11 phenomena i n semi-conductor device simulation [13]. A frequently considered problem is the following first-order partial differential equation du du a{u,x,t)â€” + y,bi(u,x,t)h c(u,x,t) = 0 at oxi (1-H) w i t h appropriate initial and boundary conditions. In general, (1.11) m a y have some k i n d of discontinuous solutions, e.g. a shock wave [76]. O r , i f we consider the steadystate case, (1.11) may have singularities, i.e. b{ may vanish at some points, as i n the shape from shading problem [34]. Some regularization techniques have been designed for solving (1.11). A popular one is du a(u, x , + du ed{u, x, t)Au + ^ bi{u, x,^)^~ + ( i x,t) = 0. 71 c u (1.12) T h e regularized problem often has a physical meaning by itself, e.g. a time-dependent advection-diffusion equation w i t h a small diffusion term. Another choice could be d^u du ., du ed(u,x,t)( â€” - Au) + a(u,x,t)â€” + ^k(u,x,t)â€” + c(u,x,t) = 0. i=l (1-13) 1 This has physical meanings as well, e.g. a traffic flow problem [118] or so-called overdamped vibration problems [104]. Thus the approximate resolution of (1.11) becomes that of the singular perturbation problem (1.12) or (1.13). Unlike the S R M , the regularization parameter e has to be small i n comparison w i t h the mesh size to ensure that the solution of the regularized problem be a good approximation of that of the original problem. It is well-known that there are difficulties i n solving these regularized problems numerically w i t h small e, e.g. the stability problem for the central difference scheme and the accuracy problem for the upwinding scheme i n a boundary layer region i n which the derivatives of the solution may be large (see [37, 61]). We w i l l consider some special cases of (1.12) or (1.13) and focus mainly on uniformly convergent methods. W e w i l l discuss spurious solutions of a simple upwinding scheme as well. Chapter 1. Introduction 1.5 12 Contribution of T h i s Thesis Our objectives are to propose and to investigate regularization methods for various differential equations w i t h or without constraints. Most attention is paid to ordinary and partial differential equations w i t h constraints ( D A E s and P D A E s ) . W e pro- pose and analyze a regularization method called the sequential regularization method ( S R M ) . A very important advantage of our regularization method ( S R M ) is that the problem after regularization need not be stiff. Hence explicit difference schemes can be used to avoid solving nonlinear systems and they make the computation much simpler. Improvements over stabilization methods and extra benefits for P D A E s are also achieved. In Chapter 2, the S R M is presented for linear index-2 D A E s w i t h or without constraint singularities. A complete theoretical analysis is performed for both cases. It is proved that the difference between the exact solution of a D A E and the corresponding iterate becomes 0(e ) s i n magnitude at the 5th iteration, at least away from the starting value of the independent variable t. Hence, the regularization parameter e need not be very small so the regularized problems are less stiff. B y some choice of parameters the regularized problems can be essentially nonstiff for any e. A s an example, a simple difference scheme for solving the regularized problems is investigated. Implementation techniques are discussed to get an approximation i n the whole region for boundary value problems and to economize storage for i n i t i a l value problems. N u m e r i c a l experiments support our theoretical results. N u m e r i c a l examples also show that usual stabilization methods do not work for problems w i t h constraint singularities. Most parts of this chapter are taken from the paper [11]. In Chapter 3, we extend the S R M to nonlinear problems and to D A E s w i t h index higher than 2. A g a i n , nonstiffness of the regularized problems is achieved. Rather Chapter 1. Introduction 13 than having one "winning" method, this is a class of methods from which a n u m ber of variants are singled out as being particularly effective methods i n certain circumstances of practical interest. In the case of no constraint singularity we prove convergence results. T h e method is also applied to constrained m u l t i b o d y systems. N u m e r i c a l experiments confirm our theoretical predictions and demonstrate the viability of the proposed methods. Most parts of this chapter are taken from the paper [12]In Chapter 4, we generalize the S R M to P D A E s , i n particular, to the nonstationary Navier-Stokes equations. T h e convergence rate 0(e ) s at the 5th iteration is again proved for this P D A E case i n appropriate norms. T h e S R M not only avoids the stiffness of the regularized problems which always occurs i n pseudo-compressibility methods but also avoids providing an unphysical pressure boundary condition which has to be imposed i n stabilization methods. Discretization and implementation issues of the S R M are considered as well. In particular, a simple explicit difference scheme is analyzed and its stability is proved under the usual step size condition (independent of the regularization parameter e) of explicit schemes. T h e stability result also indicates that the step size restriction can be relaxed as the viscosity becomes small. A numerical example is calculated to demonstrate these results. T h e S R M formulation is new i n the Navier-Stokes context and it performs well. Most parts of the chapter are taken from the paper [79]. In Chapter 5, we apply the idea of the S R M to the simulation of miscible displacement i n porous media. T h e problem is modeled by a nonlinear coupled system of two partial differential equations: the pressure-velocity equation and the concentration equation. O n l y the approximation of velocity is important for the approximation of concentration. T h e S R M idea is used for the pressure-velocity equation. A n 0(e ) s error estimate at the s t h S R M iteration is also proved. A Galerkin finite element Chapter 1. Introduction 14 method is used for the discretization of the S R M formulation. It is capable of producing as accurate a velocity approximation as the m i x e d finite element method. B u t unlike the m i x e d finite element m e t h o d i t s stiffness m a t r i x is symmetric positive definite and its finite element spaces need not satisfy the so-called Babuska-Brezzi condition. Most parts of this chapter are taken from the report [82]. Chapter 6 is devoted to numerical methods of some special cases of singular perturbation equations i n the form of (1.12) or (1.13). Sections Â§6.1 and Â§6.3 describe a collection of papers [79, 115, 107] which reflects the author's earlier research interests. We believe that, by considering these special cases, we make steps towards the general problems (1.12) or (1.13) which are undoubtedly very difficult. A l s o , these special cases have practical meaning i n themselves, hence, are worthwhile to be considered independently. In Â§6.1, we consider the one dimensional steady-state case of (1.12). Â§6.2 covers a special two-dimensional steady-state instance of (1.12) given i n [121] to show that upwind schemes may lead to spurious solutions even for problems w i t h very smooth solutions. We indicate that this is actually an ill-posed problem when e is small. Hence, it is not strange that a direct discretization to the problem fails. In Â§6.3, we consider the linear one dimensional time-dependent case of (1.13). In this case, derivatives of the reduced problem may be discontinuous along the characteristic curves. Finally, conclusions and possible future work are contained i n Chapter 7. Chapter 2 Sequential R e g u l a r i z a t i o n M e t h o d s for Differential A l g e b r a i c E q u a t i o n s 2.1 M o t i v a t i o n of the S R M for G e n e r a l H i g h Index D A E s T h e sequential regularization method ( S R M ) is motivated from the augmented L a grangian method applied to constrained m u l t i b o d y systems (index-3 D A E s i n general) by Bayo and Avello [19] and an earlier paper [20]. So we start this chapter by considering a mechanical system whose configuration is characterized by the generalized coordinates q. Let L be the system Lagrangian, defined by L = T-V, where T and V are the kinetic energy and the potential energy, respectively. Let Q represent non-conservative forces. Usually the Lagrangian coordinates are not independent, but rather are interrelated through certain constraint conditions. W h e n the connections between bodies are of holonomic type, these constraint conditions can be expressed mathematically i n the following form: = 0. (2.1) T h e n H a m i l t o n ' s principle leads to the Euler-Lagrange equations: where A is a vector function whose components are Lagrange multipliers. For general m u l t i b o d y systems, (2.2) becomes M(q)q" + $ [ A . = f(q, q') 15 (2.3) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations!6 w i t h common i n i t i a l conditions, where M is the mass m a t r i x and $ g is the Jacobian of the constraint equations. (2.3) and (2.1) form the Euler-Lagrange equations for a constrained m u l t i b o d y system. T h i s is an index-3 D A E i f $ g has full rank. We have indicated that direct discretization would not be good i n general for such a higher index D A E . One usual way to treat this problem is index reduction (to an index-1 D A E or an O D E ) . T h e most straightforward transformation of the D A E (2.3), (2.1) to an index-1 D A E involves replacing the constraint (2.1) w i t h its second derivative plus i n i t i a l conditions: _ <P*(q(t),t)_ dt 2 ' (2.4a) (2.4b) (cf. (1.6)). However, this causes well-known drift difficulties, i.e. the numerical solution of (2.3), (2.4) m a y drift away from the original constraints (2.1) as time proceeds. Hence we have to look for stabilized index reduction methods. A very popular method called Baumgarte's method proposed i n 1972 [17] is a generalization of (2.4). It replaces (2.4a) w i t h the equation $" + a$' + 6$ = 0, (2.5) where a and b are parameters chosen so that the roots of the p o l y n o m i a l <T(T) = T 2 + ar + b = 0, (2.6) are both negative, i.e. the initial value problem for the differential equation (2.5) for $ is asymptotically stable (see [16]). T h e system (2.5), (2.3) can be written i n the form " M ^ _$ 0 9 ' A The matrix 0 (2.8) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations!! Figure 2.1: planar slider-crank: initial state i n solid line, subsequent states i n dotted lines is nonsingular i f $ g has full row rank. Hence (2.7) can be integrated using standard numerical integrators. If $ is rank-deficient, we have a potential difficulty i n solving 9 (2.7). Baumgarte's method may not work then. T h e problem is called singular i f $ ? does not have full rank. E x a m p l e 2.1 Consider two linked bars (see Fig. 2.1). One end of one bar isfixedat the origin, allowing only rotational motion in the plane. The other end of the other bar slides on the x-axis. The equations of motion form a nonlinear index-3 DAE p' Mi/ = v = / â€” G X T g(p) = 0 where Xj,yi,<pi are the coordinates of the center of mass of the ith bar, and Chapter 2. Sequential Regularization Methods for Differential Algebraic Equationsl8 P= (x ,y 4> x ,y2,<h) T 1 u u 2 If the left bar is strictly shorter than the right bar, then the Jacobian matrix G of the constraint functions of this problem has full rank. The problem is nonsingular. If the length of these two bars are the same, for example, each with length 2 and mass 1, then we have M = diag{l, 1 , 1 / 3 , 1 , 1 , 1 / 3 } / = (0,-9.81,0,0, -9.81, 0 ) ( Xi â€” COS 0 1 t/i - sin0i \ x â€” 2xi â€” COS 02 9= 2 2/2 V - 2y! - sin 0 2 sin 0 i + 2 sin ( 1 0 sin0! 0 1 -cos0 -2 0 0 0 G - g = v 2 02 ) T V 0 0 0 0 0 0 0 1 0 sin</> -2 0 0 1 - c o s 02 0 2 cos 0 ! 0 0 2 cos 02 / i 2 Clearly, as the mechanism moves left through the point where both bars are upright ((f>i â€” I", 0 2 = the last row of G vanishes at this one point and a singularity is obtained. When arriving at this point with no momentum, this is actually a bifurcation point where two subsequent motion configurations are possible. We will consider only the case where the sliding bar continues to slide along the x-axis past the singularity, and note that the solution is smooth in the passage through the singularity. â€¢ In [19], Bayo and Avello proposed to solve the multibody system (2.3) using an augmented Lagrangian algorithm which is transplanted from the same method i n the optimization context [5]. Their idea is to derive a modified formulation by adding to the expression of Hamilton's principle three terms: Chapter 2. Sequential Regularization Methods for Differential Algebraic Equationsl9 â€¢ a fictitious potential v* = Y, \Â«k<4*l (2.9) â€¢ a set of Rayleigh dissipative forces G k = (2.10) -2a u u $' k k k k â€¢ a fictitious kinematic energy term T* = Y,\^t k (2-11) z where each a k is a very large real number (the penalty), and Lo and p k k represent the natural frequency and the damping ratio of the penalized system (mass, dashpot and spring) corresponding to the constraint = 0. T h e n we get a modified Euler- Lagrange equation Mq" + $ J a ( $ " + 2 f y i $ ' + 0 $ ) + $ J A * = f(q, q') (2.12) 2 or ( M + ^a$ )q" q + $ f A* = f(q, q') - $?a((**)'q' + (*Â«)' + 2 0 / / $ ' + 0 $ ) , 2 (2.13) where a, fl and p are diagonal matrices that contain the values of the penalties, the natural frequencies and the damping ratios of the fictitious penalty systems assigned to each constraint condition. Because A* is not given i n advance Bayo, Jalon and Serna [20] propose an iteration to solve (2.12) or (2.13) by comparing (2.12) w i t h (2.3): A : = A ; _ ! + a ( $ " + 2fy*$' + ft^U^, s = 1, 2, â€¢ â€¢ â€¢ (2.14) to get an approximation of A. In [19] the authors called the whole procedure an augmented Lagrangian algorithm and claimed that the algorithm works well, however without any theoretical analysis. Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations20 In fact, the algorithm would certainly not work i n general. In m u l t i b o d y motions q usually remains smooth even i n passage through singular positions. However, as indicated i n later sections, A may be unbounded at the singularity. So the iteration (2.14), as an approximate procedure to obtain A, is not appropriate i n some cases. Also, should not be included i n (2.12) i n the singular case because unbounded coefficients may appear i n i t . F r o m (2.14) the formulation corresponds to Baumgarte's formulation since when A* gets close to A * _ (2.14) gets close to Baumgarte's stabilization. : B u t Baumgarte's stabilization is not as good as some other stabilization techniques (see [8]). Moreover, i n [19] the authors indicated that the iteration (2.14) is applied u n t i l \\q" â€” q"_i\\ < 8, where 8 is a user-specified tolerance. This criterion is perhaps applied because they d i d not know the convergence rate of their iterative procedure. We do not recommend this criterion because it causes not only unnecessary extra iterations but also makes a storage-saving implementation difficult (cf. Â§2.6). Our a i m is to construct a method for general D A E s which not only avoids the above shortcomings, but for which we also do not have a Lagrangian and H a m i l t o n ' s principle. So another derivation of the algorithm is needed. In this and the next chapter, we propose a class of algorithms motivated by the augmented Lagrangian method for more general D A E s of order u, x (u) 0 = f(x,x',...,x - \t) = g(x,t). {,/ l - B(x,t)y, (2.15a) (2.15b) T h e D A E (2.15) has index u + 1 i f GB is nonsingular for a l H , 0 < t < tj, where G = g . W e are interested i n the cases v = 1 or 2. T h e Euler-Lagrange equations (2.3) x for mechanical systems w i t h holonomic constraints are i n this form w i t h u = 2. T h e algorithm is derived by combining a modified penalty idea (a k i n d of regularization) given i n [91] w i t h stabilization techniques such as Baumgarte's stabilization or the stabilization analyzed i n [8, 35] i n an iterative procedure. W e call the method the Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations21 sequential regularization method ( S R M ) (cf. [11, 12]). T h e method is applicable for more general higher index D A E s . More importantly, it works for both boundary and i n i t i a l value problems and is justified by a theoretical analysis. T h e number of iterations can be determined beforehand depending on the penalty parameter a = 1/e, the mesh size h and the order of the method used. Since we specify the iteration number i n advance we can design a procedure for the i n i t i a l value case to perform the iteration without the need to store a l l previous approximate values. T h e sequential regularization method is actually a functional iteration procedure i n which the difference between the exact solution of a D A E and the corresponding iterate becomes 0(e ) s i n magnitude at the 5th iteration, at least away from the starting value of the independent variable (which we shall call ' t i m e ' ) . Hence, unlike the usual regularization, the perturbation parameter e does not have to be chosen very small, so the regularized problems can be less stiff and/or more stable. Next we w i l l propose and analyze the S R M for the linear index-2 case w i t h singularities. N u m e r i c a l experiments are given to verify our theoretical results. Some simple difference schemes for the regularized problems and implementation issues for the S R M are also discussed. 2.2 L i n e a r Index-2 P r o b l e m s We first write down the linear index-2 problem: x A(t)x - B{t)y + q(t) (2.16a) (2* 16b) 0 where A(t), B(t) and G(t) are sufficiently smooth functions of t,0 < t < tj, A(t) Â£ R" lXni , B(t) e R * Â«, n xn G{t) â‚¬ R^ â„¢*, x subject to n â€” n boundary conditions x y and n < n . We consider the D A E (2.16) y x Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations22 B x{0) + B x{t ) = (3. o 1 (2.17) f These boundary conditions are assumed to be such that they yield a unique solution for the O D E (2.16a) on the manifold given by (2.16b). In particular, i f we were to replace (2.16b) by its differentiated form 0 = Gx' + G'x + r'= -^g(x,t), (2.18a) g(x(0), 0) = G(0)x(0) + r(0) = 0, (2.18b) and use (2.18a) i n (2.16a) to eliminate?/ and obtain n O D E s for x, then the boundary x value problem for x w i t h (2.17) and (2.18b) specified has a unique solution. In the i n i t i a l value case B\ = 0, this means that (2.17) and (2.18b) can be solved uniquely for x(0). W e w i l l give a more precise assumption i n L e m m a 2.1 below. T h e problem (2.16), (2.17) is of index-2 i f GB is nonsingular for all t. However, here we allow GB to be singular at some isolated points of t. For simplicity of exposition, let us say that there is one singular point Â£*,0 <t*<tf. and r(t) Â£ R . ny T h e inhomogeneities are q(t) Â£ R * 71 We are only interested i n the k i n d of singularities as i n E x a m p l e 2.1, where the solution x of (2.16), (2.17) passes through the singularity smoothly. Returning to E x a m p l e 2.1 (where B = M~ G ), l m a t r i x GM~ G l T we can verify that, although the T is singular at the singularity , the m a t r i x M~ G (GM~ G )~ G 1 T 1 T l is smooth for all t. Also, two types of singular constraints (i.e., w i t h vanishing rows or w i t h some rows linearly dependent at some points) mentioned i n [2] both have a similar property. Thus, for the linear model (2.16), we assume accordingly: A s s u m p t i o n 2.1 The matrix function P â€” B(GB)~ G 1 is smooth, or more precisely, P is continuous and P' is bounded near the singular point i * where we define P(U) = )im(B(GB)- G){t). 1 Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations2d Because we are only interested i n the case where (2.16) has a smooth solution for x (as is the case i n E x a m p l e 2.1), it is necessary to assume, i n view of (2.16b): A s s u m p t i o n 2.2 The inhomogeneity r{t) satisfies r Â£ S, where S = {w(t) Â£ R ny : Gz = w for a smooth function z{t). We note that Assumptions 2.1 and-2.2 are satisfied automatically i f GB is nonsingular for each t. O n the other hand, neither B(GB)~ l nor (GB)~ G 1 alone are smooth near a singularity i n general. We also indicate here that to formulate the S R M (see Â§2.4) we only need the continuity of P. T h e further requirement i n A s s u m p t i o n 2.1 on the derivative of P is needed for the regularity of the solution (cf. L e m m a 2.1 and (2.24)) and the stability proof for the regularized problems (cf. Â§2.5). T h i s requirement can be avoided i f we make a more general assumption about the regularity and stability of the original problem (cf. Â§3.1). We consider both initial and boundary value problems. In Â§2.3 we briefly discuss the conditioning of the problem (2.16) with singularities. In Â§2.4 we derive the sequential regularization method. In Â§2.5 we estimate the error of the S R M . In Â§2.6, we consider some discretization and implementation issues for both i n i t i a l and boundary value problems. Finally, i n Â§2.7 several numerical examples demonstrate our theoretical results. 2.3 Problem Conditioning Similarly to [15] and to the method of pseudo upper triangular decomposition ( P U T D ) described i n [2] (cf. Â§10.6; w i t h the difference that we do pivoting to interchange the row w i t h the singularity of the lowest order and the current row when a l l the Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations24 other rows vanish at some singular point), there exists a smooth m a t r i x function R(t) G R K - " Â» ) x * , which has full row rank and satisfies n RB = 0, for each i, 0 < t < t , f where R can be taken to have orthonormal rows. As i n [15, 16], define the new variable u = Rx, 0 < t <t . f â€¢ (2.19) T h e n , using (2.16b), the inverse transformation is given by x = Su- B{GB)~ r, (2.20) l where S = (/ - B(GB)- G)R 1 T = (I- P)R . T B y the assumptions at the beginning of this chapter, this transformation is welldefined. Differentiating (2.19) and using (2.16a) and (2.20) we obtain the essential underlying O D E ( E U O D E ) : u' = (RA + R')Su - (RA + R')B(GB)- r 1 + Rq. (2.21) Hence the underlying problem of (2.21) is v! = (RA + R')Su + / , (2.22a) B S(0)u(0) + 5i5(t/)w(</) = Pi. (2.22b) o We make A s s u m p t i o n 2.3 The boundary value problem (2.22) is stable, i.e. there exists a moderate-size constant K such that H < f f ( | | / | | + |)9i|), where \\u\\ = max {\u(t)\, 0 < t < tf}. t Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations25 Similarly to Theorem 2.2 of [15], we have L e m m a 2.1 Let the DAE (2.16) have smooth coefficients, and assume that Assumptions 2.1 and 2.2 hold. If the EUODE (2.21) with boundary conditions (2.22b) has a unique solution, then there exists a unique solution for the x of problem (2.16)(2.17) which is smooth. This implies the unique existence of a smooth By as well. Furthermore, if Assumption 2.3 holds then there is a constant K such that \\x\\<K{\\q\\ + \\B{GB)-*r\\ + < K(\\q\\ + \\B(GB)- r\\ l 1)91), + ||( B(G' B)- r) || + \3\). 1 J , J R e m a r k 2.1 For problem (2.16) without singularities, we can get \\x\\ <K{\\q\\ + \\r\\ + \(3\), Hz'H < K(\\q\\ + ||r|| + ||r'|| + |/?|) as in [15, 16]. â€¢ The difference between the situation here and i n the nonsingular case is that the perturbation inhomogeneities r yield reasonably bounded perturbations i n the solution x only i f they are (in general) from the subspace Range (G). F r o m (2.16a) and (2.20), we can write = -(GB)- G(x' x y -Ax- q),t e [0,Q U (U,t ], f (2.23) which could be unbounded at the singular point Â£* (whereas By is bounded). Note that G could be replaced i n (2.23) by any appropriate m a t r i x Q w i t h the same size as G, e.g. Q can be B . T Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations2d> R e m a r k 2.2 If B has full rank for each t, then (GB)~ G l Hence, (GB)~ G l = {B B)- B P. T l T is smooth. Hence, there exists a unique solution for the y of problem (2.16)-(2.17) which is smooth and can be expressed as (2.23) for each t. Furthermore, using Lemma 2.1, we have in this case \\y\\ < K(\\q\\ + \\B(GB)- r\\ l + | | ( 5 ( C 7 i ? ) - V ) ' | | + |/?|). (2.24) In the general case, however, we will have to consider By, rather than y alone, in the theorems of the next section. â€¢ A Baumgarte stabilization applied to (2.16) consists of eliminating y according to (2.18),(2.23), and stabilizing (see (2.30) below for the usual form). T h i s gives the ODE x'=(I- B{GB)- G){Ax l + q)- B(GB)- (G'x l + r') - e" B(GB)-\Gx 1 + r ) (2.25) where e > 0 is a parameter (cf. [17, 8]). If there are no singularities then it follows from the analysis i n [16] that i f Assumption 2.3 holds then the boundary value problem (2.25),(2.17),(2.18b) is also stable. In other words, the "initial value stabilization" works also for the boundary value case, because the new modes introduced by replacing (2.16b) w i t h (2.18a) are separable and decaying, i n agreement w i t h the additional initial conditions (2.18b). However, i n the singular case (2.25) may not work because the terms and B(GB)~ r' 1 B(GB)~ G' X are i n general unbounded. Therefore, we develop an iterative method i n the next section which builds up an approximation to By and x that avoids going through unbounded quantities. Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations27 2.4 D e r i v a t i o n of the S R M There are many discussions on regularization methods for D A E s . A direct regularization (cf. the pseudo-compressibility method i n the Navier-Stokes context [108, 72, 97]) is: x' = -ty' = A(t)x - B(t)y + q(t), " (2.26a) G(t)x + r(t). (2.26b) T h i s formulation is not popular because it requires conditions on A , B and G , for the purpose of stability of the system, and the existence of the first derivative of y, which is not necessarily true for the original problem (2.16) [86]. It m a y also change the properties of the original index-2 problem too much by j u m p i n g from index-2 to index-0 ( O D E ) . It seems evident that a regularization w i t h fewer changes of the original problem (e.g. from index-2 to index-1) might be better. T h e penalty method [84, 91, 68, 70] is such a method. It reads x' = tE~ y = l A(t)x - B(t)y + q(t), (2.27a) G{t)x + r(t), (2.27b) where E Â£ ~R, y v is chosen such that BEG has non-negative eigenvalues. Hence, the n Xn system obtained by substituting (2.27b) into (2.27a) is generally stable. For example, we can choose, relying on Assumption 2.1, E â€” (GB) -1 E = (GB) T (hence, BEG â€” P). could be a good choice i n some circumstances. If B = M~ G l T Also, for some positive definite m a t r i x M (as i n the case of mechanical systems) then it is possible to choose E = I. Advantages of these choices of E w i l l be discussed i n Chapter 3. For problems w i t h singularities, we suggest using E = (GB)' 1 to avoid a turning point problem. Another approach is parameterization [85, 59]: = A(t)x- B(t)y + q(t), (2.28a) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations28 0 = G{t)(x + ex') + r(t). (2.28b) Substituting (2.28a) to (2.28b), we get eGBy = Gx + r + eGAx. (2.29) This implies that parameterization can be seen as an instance of the penalty method w i t h E = (GB) . -1 Recently, [94] has reported a regularization for D A E s w i t h sin- gularities based on a formulation obtained by the trust-region method i n numerical optimization. A l l these regularizations require the regularization parameter e to be very small. Therefore a stiff solver is needed to solve the regularized problem. In this section, we derive a new regularization method which is called the sequential regularization method [11]. T h e S R M is an iterative procedure which combines the popular Baumgarte stabilization or other stabilizations with a modified penalty method. One purpose for doing so is that the regularized problems of the S R M can be non-stiff or at least less stiff. Hence, simple discrete schemes (e.g. explicit schemes) can be used. Other advantages of the method w i l l be discussed i n Chapter 3. T h e Baumgarte stabilization of (2.16) reads (cf. (2.5)) a ^g(x,t) + a g(x,t) = 0, g(x(0),0) = 0. 1 (2.30) 2 A p p l y i n g the idea of the penalty method to equations (2.16a) w i t h constraints (2.30), we obtain x' = y = A{t)xy + 0 B(t)y + q(t), (2.31a) x0( ><) + " 2 0 ( M ) ) dt (2.31b) x e where yo can be seen as an initial guess of the exact solution y of problem (2.16), e (2.17). If we take y = He then the solution of problem (2.31), (2.17) is exactly the 0 Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations29 same as that of problem (2.16), (2.17). If we take yo = 0 then (2.31) coincides w i t h the penalty method (2.27). Given any initial guess yo(t), the solution, say {a;i, y i } , of (2.31), (2.17) is an approximation of the exact solution {x , y } of (2.16), (2.17). Using e e this solution y\ as a new initial guess, we re-solve problem (2.31), (2.17). W e expect that the solution obtained is a better approximation of the exact solution. Repeating the procedure, we invent the following iterative algorithm for solving (2.16): For 5 = 1 , 2 , . . . , solve the ODE problem xj = Ax -By s s + q (2.32) where y = y . - i + ^E(cti^g(xâ€žt) + a g(x t)), s 2 (2.33) ai subject to the same boundary conditions (2.17). Note that yo(t) is a given i n i t i a l iterate and that e > 0 is the regularization parameter. We call this algorithm a sequential regularization method ( S R M ) . Note that x (t) s and y (t) are defined on the entire interval [0,tj] for each s. For the problem w i t h s singularities, the choice E = (GB) generates turning point regularized problems T which are complicated to solve and analyze. We thus choose E = (GB) -1 singular case. Noting that B(GB)~ G' for the may be unbounded at the singularity we then 1 choose cti = 0 to avoid this term. Also, i n practice we m u l t i p l y (2.33) by B and keep track only of the approximations By to the bounded function By, since y m a y be s unbounded at the singularity. We thus have an S R M variant for the singular case: For 5 = 1 , 2 , . . . , solve the ODE problem xj = Ax -By s s + q (2.34) where By = By -i + s s -BEg(x ,t), s (2.35) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations30 subject to the boundary conditions (2.17). If y is desired (at times other than at the singular point Â£*) then it can be easily retrieved from By i n a post-processing step. 2.5 Convergence A n a l y s i s of the S R M We first prove a l e m m a which w i l l be used to discuss the convergence of the S R M . L e m m a 2.2 Let u, v be the solution of v! = Sv' + 7U = B S{0)u(0) + BiS(tf)u(t ) o (RA + R')Su + Siv + / i , (2.36a) eS^u + eS v + / , (2.36b) 3 2 = '3 - 5 u ( 0 ) -S v(t ), f 4 5 v(0) = v , f 0 (2.36c) where all coefficients are bounded, 8 = 1 or S = e, 7 is a positive constant and Assumption 2.3 holds. Then, for e appropriately small or 7 appropriately large, we have the following stability inequality \\u\\ < ^ ( | | / i | | + | | / | | + |/9| + K I ) , 2 I H I < / i r ( Â£ | | / i | | + | | / | | + |)9| + |t;o|), 2 where K is a positive constant. P r o o f : Let v = (ui, â€¢ â€¢ â€¢ ,v ) . T ny F r o m (2.36b), we easily have \vi\ < -II^IIHull + -||S ||||'u|| + -H/2II + |u|, i = 1, â€¢ â€¢ â€¢ ,n . , 7 7 3 7 y 0 Hence, taking the m a x i m u m of the left hand side for 1 < i < n and choosing small y e or large 7 appropriately such that e\\S3\\ < 7, we get \\v\\< jT^Pz 7 - e S 3 H + i , I, â€¢ 7-e 63 g (2-37) Chapter 2. Sequential Regularization Methods for Differential Algebraic EquationsSl B y using A s s u m p t i o n 2.3, from (2.36a), there exists a positive constant K\ such that ^idl^llUHI + HAH ||u|| < +1/?| + | 5 | K 0 ) | + I S B I K M ) 4 < A-iail^H + iSsDiiuii + ii/iii + ^ i + ^^W) < A^edl^H ^(115x11 + |5 |)(||/ || + 7kol) + |g |)||g || B a ^IJH 6 I H I a ^4s7\\ + | K r N f ii , i f l . , . o M f > n +Ai(||/i||+|0|+|5 ||t, |). 4 Hence, by choosing smaller e or larger 7 such that A i e ^ l ^ | ^ ^ 5 ^ 2 o < 1, the stability inequality for u follows. Now the stability inequality for v follows from that for u and (2.37). â€¢ Now we estimate the error of the S R M (2.34), (2.35). D e f i n i t i o n 2.1 J is an integer such that y (0) = y (0), y (0) = y' (0),..., o e o e y< (0) = y( )(0), J) J where yo(t) is the initial guess of the SRM iteration (2.34), (2.35) and y (t) is the e exact solution of the original problem (2.16). Set J = â€” 1 if yo(0) 7^ 2/e(0). â€¢ For i n i t i a l value problems we may calculate y ^ ( 0 ) , i = 0 , 1 , . . . i n advance b y e using the O D E and its derivatives. For boundary value problems we have J = â€” 1 i n general since we don't know y (0) beforehand. e T h e o r e m 2.1 Let the DAE (2.16) have sufficiently smooth coefficients, and assume that Assumptions 2.1, 2.2 and 2.3 hold. Then, for the solution of iteration (2.34), (2.35), we have the following error estimates (for J defined in Definition 2.1): = 0(e ) + 0 ( e V ( ' A K x (t)-x (t) s s e By (t) - By (t) s = e 0(eÂ°) + J+ i/e ), 0(e p {t/e)e-^), J+1 a for 0 < t < tf and s > 1. Here p (r) = 0 if s < J + 1 ; otherwise (T) is a polynomial s Ps of degree s â€” J â€” 2 with generic positive coefficients and |p (0)| = \(By )( ^(0) â€” J+1 s (By )( ^(0)\. J e o Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations32 P r o o f : Let u = Rx s and w = Px . s s Similarly to (2.20), we have s x = Su + w . s s (2.38) s Furthermore, using (2.34) we obtain < = (RA + R')Su + (RA + R')w ew' + w = e(PA + P')Su + e(PA + P')w s s + s + Rq, s s s (2.39a) - eBy,_i (2.39b) B (t ), (2.40a) 'ePq-B(GB)~ r, 1 subject to B S(0)u (0) + BiSitrfiisitf) o s w (0) 3 = [3- B w (0)- = - B(0)(C?(0)5(0))- r(0). o s lWs f (2.40b) 1 J The iteration (2.35) for By becomes By, = By _ s + -(w + B(GB)- r). ] 1 (2.41) l s T h e proof proceeds along familiar lines of singular perturbation analysis. According to [111, 112] we can construct the asymptotic expansion of w and u sequentially s s for s = 1 , 2 , . . . , where we use L e m m a 2.2 to estimate the remainders. ing (2.41) and (2.38), we get the asymptotic expansion of By s Note that i n these expansions the first terms are exactly x e eventually yields the proof of the theorem. and x s and By . e T h e n , usrespectively. This process â€¢ To provide a better understanding about the sequential regularization method we give i n Â§2.8 a detailed proof for the initial value case with no layers, s < J + 1. In that proof, the construction of the asymptotic expansion is directly for x and By. Moreover, the construction method we apply is somewhat different from [111, 112] and more relevant to the concept of D A E s . Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations33 Next, we consider the S R M (2.32), (2.33). For the i n i t i a l value problem w i t h E = I and B = G T , this corresponds to A l g o r i t h m (2.13), (2.14) of [19] for constrained mechanical systems (although they do it for the corresponding index-3 case) derived by a penalty-augmented Lagrangian formulation. Bayo and A v e l l o have noted that under repetitive singular conditions this algorithm m a y lead to unstable behavior. For our index-2 case (2.16) w i t h singularity, it appears to be impossible to choose a m a t r i x E such that problem (2.32),(2.33) is always stable, even i f we assume B = G . T A numerical example i n Â§2.7 w i l l verify such instability phenomena even for the case of one singular point. However, for the case where constraints are without singularities, (2.33) (multiplied by B) m a y have a benefit over (2.35). T h a t is, (2.33) yields an O D E problem for x which is essentially not a stiff problem. Take E = (GB)~ l s as before and rewrite (2.33) as By s = Bys-! + ^BE{a ^g{xâ€ž,t) + a g(x ,t)). l 2 s (2.42) T h e n we give the following error estimation for (2.32), (2.42): T h e o r e m 2.2 Let the DAE (2.16) have sufficiently smooth coefficients, and assume that G has full rank and that Assumptions 2.1, 2.2 and 2.3 hold. Then for the solution of the iteration procedure (2.32), (2.42) with a\ ^ 0, we have the following error estimates: x - x = 0(e ), s s By e - By = 0{e ) s s e for 0 < t < tf and s = 1 , 2 , . . . . Note that no boundary layer terms appear here even for J = â€” 1 (See Definition 2.1)1 P r o o f : Denote u = Rx and v = Gx . Hence s s s s x = Su + Fv , s s s (2.43) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations34 where S = (I - P)R T and F = B(GB)~ = PG (GG )~ 1 T T are both sufficiently 1 smooth. F r o m (2.32),(2.42), we get u' = (RA + R')Su + (RA + R')Fv + Rq, s (e + a )v' + a v x a 2 s s = s e(G' + GA)Su + e(G' + GA)Fv s s + eGBy s + tGq - a r' - a r, X x w i t h the corresponding boundary conditions, and By = 5 y _ ! + -BiGBY^a^v. s + r)' + a (v + r)). 2 s s Repeating the procedure of the proof of Theorem 2.1 and using L e m m a 2.2 again to estimate the remainder of the asymptotic expansion, we obtain u - u = 0(e ), v -v = 0(e ), = 0(e ), s e s e By -By s e s s s where u = Rx , v = Gx = â€”r. Hence, using (2.43) and x = Su + Fv , we obtain e e e e e e e x - x = S(u - u ) + F(v - v ) = 0(e ). s s e s e s e â€¢ R e m a r k 2.3 For the problem (2.32), (2.33) where GB is nonsingular, we have x -x s = 0(e ), s e This estimate also holds for E = (GB) . T 2.6 y -y s = 0(e ). s e â€¢ D i s c r e t i z a t i o n a n d I m p l e m e n t a t i o n Issues T h e S R M iteration yields a sequence of O D E problems which are to be solved numerically. We only consider the most difficult case, i.e. (2.34), (2.35) w i t h singularities. 2 Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations35 Inserting (2.35) into (2.34), the O D E problem to be solved at the 5th iteration is written as the singular-singularly-perturbed problem (see [112, 89]) ex' + BE(Gx + r) = eAx, - e ( Â£ y _ i - q), (2.44a) B x {0) +B x (t ) = (3 , G ( 0 ) x ( 0 ) + r ( 0 ) = 0. (2.44b) s o s s 1 s f s s We consider finite difference (or collocation) discretizations of (2.44) on a mesh 7T : 0 = t < t < ... < t 0 x = t N hi = t{ â€” U-i, f h = m a x hi l<i<N and denote by x*, y* the corresponding approximations of x (ti), y (ti), respectively. s s We now have essentially two small, positive parameters to choose: e and h. W e assume that h is chosen small enough so that the E U O D E problem (2.22) m a y be considered as nonstiff and that the problem's coefficients are sufficiently smooth. In the B V P case the situation is the familiar one, much like the iterative solution of a nonlinear boundary value O D E using quasilinearization (see, e.g., [14]). Each of the linear boundary value O D E s (2.44) is discretized on a mesh n using, say, a symmetric finite difference scheme or some other method. We expect, as h â€”> 0, convergence to the solution of ( 2.44) and our theory then applies for the entire numerical algorithm. As an example, we give here a detailed analysis of the convergence of the backward Euler difference scheme for (2.44). A similar discussion and results can easily apply to the forward Euler difference scheme. The results for general higher order collocation schemes have been described i n [11]. Now we write the backward Euler scheme of (2.44) as follows: e X l ~ h U + MGi \ B + n) x Bx s 0 0 + B s lX N = ^\-e{B - {U)-q^ (2.45a) = (3, G x + r = 0, (2.45b) iy9 X s 0 Biyl = BiVs-iiU) + -B Ei{GiX 0 s % t 0 + n), (2.46) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations36 where we represent the value / ( Â£ ; ) of a given function / at mesh point t{ by M u l t i p l y i n g (2.45) by R{ and P , respectively, and denoting t u\ = R , w\ = Pix\ s lX t (then x* = SiU* + w since (2.38) holds), we have s { ^rf^ = RiAiSiu'i + wt) + t ^ ^ i S ^ u U + < ) + c^rhiSi-iuU + ' = CRMS*! w -e(5,-2/ _i(*,-) - ) - BiEin, s Bo(S u' 0 a 0 i q i , (2.47a) + wU) % = 1, â€¢ â€¢ â€¢ , A , qi + w ) + B^SNU'N 0 + wU) + R + w ) = 8, w = -B E r s = P x (t ). s N 0 0 0 (2.47b) (2.47c) e 0 0 0 A t first, we consider the stability of the following difference scheme corresponding to (2.47): rh _ Ui - Ui-1 r> A C L/ Ui = : KiAibiUi 1 Ri ~ R{-\ : hi . Lw 2 t = UiAiWi h{ + v -> U>,-_i i - i + fi, _ *Wj â€” e 1- W{ = ePiAibiUi hi + e (2.48a) Pj - Pj-x : i>i_iu _i hi t p. _ p. eP A w + e z t 1 8 - -! + g , i = 1, â€¢ â€¢ â€¢ , A , 1 t Wi (2.48b) { I hi BSu 0 0 + BXSNUN 0 = 8I = 3 - B w 0 0 - B\w , N w = B. 0 2 (2.48c) Using the discrete m a x i m u m principle for the difference operator L\, i.e. z > 0 and L z 0 2 { > 0 z > 0,Vi, t (2.49) we easily get max \WJ\ < M(\3 \ + m a x \LowA). i<i<Â» Defining \\z\\i â€” maxi<j<; \ZJ\ and using (2.48b), we have 2 HI.-^McCiHii + lHIO + ^ l + IMIi (2.50) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations^! or \\w\\i < M(e\\u\\i + \3 \ + \\g\\i). (2.51) 2 Here M stands for a generic constant independent of i, e and h. O n the other hand, L\u{ is a one-step difference operator of (2.22a) â€” the underlying problem of (2.21). Using A s s u m p t i o n 2.3 and Theorem 5.38 of [14], we obtain H o o < Ki{\Pi\ + m a x \L \), l<j<iV (2.52) h lUj where ||^||oo = rnax <j<iv \ZJ\ and K\ = K + 0(h). Here K is the stability constant 0 defined i n A s s u m p t i o n 2.3. Using (2.48a) and (2.48c) we have WuWcc^ M(\\w\\ + \p \ + \p\ + \\f\\ ). N 2 (2.53) N T h e n , using (2.51), yields Hoo < M(\\f\\ + \\g\\ + \\3\ + \fo\) IIHU < M(e\\f\\ N (2.54a) N + \\g\\ + \\P\ + \(3 \). N N (2.54b) 2 We thus obtain the stability inequalities (2.54) for the difference scheme (2.48) or (2.47). Now we discuss the convergence of (2.47). Using (2.54) , we have the estimates: K(*,-)-<lloo < M(||r || H(i,-)-Â«>, l|oo < M(\\T \\ ? u + ||r || v) (2.55a) + \\T \\ ), (2.55b) w i V U i W N N where r " and T-" are local truncation errors for the difference scheme (2.47) and they can be w r i t t e n as r- T? = ^{<(e!) + i ? " ( e - ) [ 5 ( ^ - i ) ^ ^ - i ) + ^(^-i)] + m(ti)(Su = e / i , - K ( ^ ) + P (ni )[5(t _ ) (< -_i) + ; (t _ )] + P'(t )(Su a + w y^t)} (2.56a) s ,, ! i t s + w )'(rif)}, s 1 Ua 1 U 8 < 1 (2.56b) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations38 where Â£f,?7f Â£ ( t , _ i , t ) , / ^ = 1,2,3. To bound the truncation error, we need the t derivative estimates of u and w . F r o m the asymptotic expansions of u and iu ( cf. s s s s Theorem 2.1) u s = u + eu i + e (u w s = w + e(w i + w ) + e (w + w ) H 2 e e s2 + S )H (2.57a) s 2 (2.57b) 2 e where u = Rx , w = Px e s e e a sl s2 s2 , u j and w j are functions of regular expansions, u j and s s s wâ€žj are boundary layer functions whose basic forms are p(t/e) exp(â€”t/e) (where p is some polynomial) and u j = w j = 0 for j < s ( since S R M iteration cancels out the s s lower terms of regular expansions). We can expect that K | , K | , K | <M. (2.58) But K | = 0(e-> exp(-t/ ) < _ Me ' otherwise . M C M i f X 6 (2.59) Therefore |r-|| = 0(*),l|r-||= W ^ I C(ftJ if Â« < * . = Â« . - * > otherwise . ( 2 . 6 0 ) F r o m (2.55), we thus have lk(*,-)-".loo < Mh . (2.61a) |^.(*t) - < l | o o < \ . otherwise (2.61b) Mft i.e. x,(*,-) - x'i = S(ti)(u {ti) - <) + (w (ti) - w'i) = 0(h). a a (2.62) However, we can not generally get a good approximation for By i n the whole region e if e is not very small compared with hi since i n this case we generally have Bivi = B y - (U) + = Biy^t^ + ^BiEiiGiX^ = B (ti) i t iye 1 -B E {Gix' +r ) i i i i + r^ + ^w'i-Wsiti)) + 0(e + exp(-U/e)) + 0{h/e). (2.63) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations39 Fortunately, we can get 0(h) accuracy locally, i.e. i n a smooth region or away from the layer region, say for ti <t<tj. Indeed, considering an equidistant mesh 0 for simplicity, from (2.47b), we have L>A = e wt e where Aw s { A w Â° - ^ A + w l = l P A,-(5,-AÂ«? + Aw?) + / ' " ^ " ' ( f l - i A t z ? + AwU) + 0 ( 7 f ) , i = w (ti) â€” wÂ°, A m - = u (ti) â€” u\ and we note that s s (2.64) = 0(th) for io < i < N. Using the discrete m a x i m u m principle for L\ i n Â£,â€¢â€ž. < t < tj on the barrier function Zi = [Aw" | A J i o + m a x |<J-| Â± Aw? t Â°' 1 i <i<N l 1 1 1 0 where <5;(= 0(h)) is the right-hand side of (2.64) and A = h/(e + h), and using (2.61), we get Zi > 0 or \Aw*\ < | A < | A ' - " Â° + max \Si\ < For e = h , 1+5 M(hX- + eh). io (2.65) - 1 < 5 < 1, A ' 1 Taking i i such that - 1 ' = 0 exp(-(i exp(-(Â«,- - z )/i ) = 5 0 -U^/h ' ) 1 5 1 exp(-(Â«,- < Mh 1+S t^/h -*). 1 - = Me when h is sufficiently small, we get A'-*' < e x p ( - ( t 0 - UA/h ' ) < Me for i > i 1 8 il u i.e. \Awf | < Mth, Vz > z'i, and any e satisfying e = h , 1+5 - 1 < <5 < 1. C o m b i n i n g this w i t h (2.61b), we obtain |Atu?| < Meh, Vz > ti. (2.66) T h e n , using (2.63) and (2.66), we have the local error estimate \Biyl - B (U)\ lVe < M(h + e ), for i, < i < N. s (2.67) Chapter 2. Sequential Regularization Methods for Differential Algebraic EquationsAO T h i s means we can get good approximation i n a region which is away from the i n i t i a l layer. Once an accurate S R M solution, say {x*, B(t{)y*}, has been determined outside the i n i t i a l layer it may be possible to obtain an accurate solution everywhere by applying a few S R M iterations numerically solving (2.44a) ( changing BEG to â€”BEG) subject to the terminal value x{t ) = x* ,f and choosing By satisfying B(tf)y (tf) 0 0 (2.68) N = B(tj)y* . This procedure is feasible proN vided that the terminal value problem (2.44a),(2.68) is well-conditioned (which holds if the t e r m i n a l value problem for the E U O D E (2.22a) is well-conditioned). For the I V P case, where (2.44b) reduces to x(0) = x given, (2.69) we may, of course, proceed i n the same way as for the B V P case. B u t now a few things are easier. Firstly, for this case we can calculate By (0) and then choose Byo to be e exact at t = 0. In fact, as indicated earlier we can also do this for higher derivatives of By at the i n i t i a l value by repeated differentiation of (2.16). Such a preparation of the i n i t i a l iterate Byo allows removing the layer error terms (or the condition t{ 3> e) in the error estimates (2.61). Secondly, one may use a more convenient difference scheme to integrate the I V P (2.44a),(2.69). If the E U O D E is sufficiently nonstiff to warrant use of a nonstiff integration method then this can be an attractive possibility here. that â€”hi/e Note, though, must be i n the absolute stability region of the method (see (2.39b)). Thus, an explicit R u n g e - K u t t a method of order p, for instance, m a y necessitate (at least) p S R M iterations i n order for the error i n the estimates of Theorem 2.1 to be of the same order as the error i n the numerical approximation. Chapter 2. Sequential Regularization Methods for Differential Algebraic EquationsAl T h e most important difference between the I V P and B V P cases is that the iterative method described here does not appear to be necessarily optimal or even natural i n the I V P context, certainly not from the storage requirement point of view: Note that the entire approximation of Â£>y -i on [0,t/] needs to be stored. T h e situation here s is similar to that encountered w i t h other functional iteration methods like waveform methods. However, this difficulty can be resolved by rearranging the computation, assuming that the number of the S R M iterations, m , is chosen i n advance. Thus, at each time step z, 1 < i < N, we calculate sequentially the quantities xj, Byj,x , By ,..., 2 2 a;â„¢, By* To do this using a one-step scheme, say, we need only the corresponding quantities locally, over the mesh subinterval [Â£,-_!,Â£;), and ByÂ®. For the latter we m a y use, for instance, yf = y (0), i.e. Byf = B(i,-)yo, 0 < i < N. T h e storage requirements are e now independent of N and other typical I V P techniques such as local error control may be applied as well. 2.7 Numerical Experiments We now present a few very simple examples to demonstrate our claims i n the previous sections. Throughout this section we use a constant step size h and set tf = 1. To make life difficult we choose h so that there is an i such that i ; = i * (if there is a singularity). In the implementation we monitor the size of the pivot i n a Gauss elimination procedure for GB and slightly perturb ti away from t* when needed. A t a given time t, we use 'ex' to denote the m a x i m u m over a l l components of the error i n x while 'ey' denotes the m a x i m u m over all components of the error i n By . s s 'drift' denotes the m a x i m u m residual i n the algebraic equations. We first look at a boundary value problem. Similarly, Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations^! E x a m p l e 2.2 Consider the DAE (2.16) with - - ( - . ' : ) â€¢ â€¢ - ( . : . ) â€¢ - ( - : â€¢ ) G ( 1 â€” 2* = 1 - 2t) , r = - ( 1 - 2*)(e * + smt)' _ subject to xi(l) + x (0) = 1 / e . 2 The exact solution is x = ( e s'mt), y = _ i e ^4 singularity is located at t = 1/2, e where y becomes infinite while By stays bounded. We start computing with the iterate e e y (t) = 0. o In Table 2.1 we list errors when using the midpoint scheme = 4- *iLj-flpJ_ t By' , a where x ._ = ^'~ s x,+ L 1 % 2 = By'-* J ~ 2 i + M +e- B _ E _,(G,_LX-_ +r _,) 1 1 2 l 2 i V l * 2 1 2 i 2 (but no such relation is necessary for y ). s 7 We apply this scheme with h{ = h = .01 for various values of e. /Â£ is indicated in [11] that this scheme has 2nd order accuracy in ex and in ey, except for the case t <Â§C h when the error's order in By drops to 1. This is evident in the error column for t = 1.0. Note also the 0(e) improvement per SRM iteration when this term dominates the error (i.e. when e 3> h ). s 2 We note that the approximation for By at points within the initial layer is not accurate. To get a better approximation within the initial layer ( i.e. near the initial point t = 0), we solve a terminal value problem (2.44 ) (changing BEG to a â€”BEG), (2.68), as described in Â§2.6. Then we apply the SRM for the given problem with the improved values for Byo. In Table 2.2 we list the computed results after 3 iterations. They are obviously much better than the comparable ones in Table 2.1. â€¢ Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations43 e le-1 iteration 1 2 3 le-2 1 2 3 le-3 1 2 3 error at â€”) ex ey drift ex ey drift ex ey drift ex ey drift ex ey drift ex ey drift ex ey drift ex ey drift ex ey drift t=.Ul .38e-l .96 .87e-2 .92e-2 .91 .90e-2 .94e-2 .87 .86e-2 .38e-2 .67 .65e-2 .45e-2 .45 .44e-2 .30e-2 .30 .29e-2 .13e-2 .17 .17e-2 .30e-3 .30e-l .30e-3 .65e-4 .70e-2 .69e-4 t=.l .35e-l .40 .49e-l .37e-l .96e-2 .32e-l .19e-l .20 .16e-l .60e-2 .30e-2 .80e-2 .10e-3 .32e-3 .15e-4 .55e-5 .18e-2 .17e-5 .58e-3 .47e-2 .79e-3 .71e-4 .17e-l :51e-4 .15e-3 .33e-l .lle-3 t = .3 .56e-l .14 .51e-l .89e-2 .14 .61e-2 .12e-l .30e-l .43e-2 .53e-2 .40e-2 .38e-2 .88e-4 .70e-4 .14e-4 .52e-5 .26e-4 .26e-5 .52e-3 .41e-3 .38e-3 .75e-5 ,34e-4 .20e-5 .70e-5 .12e-3 .21e-5 t=.5 .52e-l .34e-l .0 .65e-2 .34e-l .0 .63e-2 .43e-l .0 .44e-2 .48e-2 .0 .77e-4 .44e-4 .0 .59e-5 .18e-4 .0 .45e-3 .49e-3 .0 .72e-5 .13e-4 .0 .70e-5 .14e-4 .0 t=1.0 .39e-l .66e-l .61e-l .72e-2 .65e-2 .72e-2 .15e-2 .85e-3 .74e-3 .38e-2 .62e-2 .55e-2 .64e-4 .23e-4 .68e-4 .lle-4 .67e-5 .56e-5 .39e-3 .62e-3 .54e-3 .12e-4 .54e-5 .65e-5 .12e-4 .56e-5 .59e-5 Table 2.1: S R Merrors for E x a m p l e 2.2 using the m i dpoint scheme Next we consider i n i t i a l value problems. E x a m p l e 2.3 Consider the same DAE as for Example 2.2 with the same exact solution but with initial values Xi(Q) = 1, x (0) â€” 0 specified. From these initial conditions 2 we can calculate y(0) = 1 in advance, and we choose the initial guess yo(t) = 1. Tables 2.3 and 2.4 display error results for e = .1 and h = .001 using the backward Euler and the forward Euler schemes, respectively. As explained in Â§2.6 we calculate all iterates at each step before proceeding to the next. These tables show a significant improvement with each SRM iteration and no strong initial layer effect, as predicted by theory. Chapter 2. Sequential Regularization Methods for Differential Algebraic EquationsAA e le-1 5e-2 le-2 le-3 error at â€”â€¢) ex ey ex ey ex ey ex ey t=.l .54e-2 .45e-2 .58e-3 .18e-2 .49e-4 .85e-4 .42e-4 .46e-4 t=.01 .62e-2 .48e-2 .76e-3 .22e-2 .57e-4 .10e-3 .49e-4 .56e-4 t = .3 .39e-2 .44e-2 .32e-3 .10e-2 .35e-4 .52e-4 .31e-4 .30e-4 t=.5 .28e-2 .54e-2 .17e-3 .50e-3 .26e-4 .32e-4 .23e-4 .19e-4 Table 2.2: S R M errors for Example 2.2 using the shooting-back technique iteration I 2 3 error at â€”> ex ey drift ex ey drift ex ey drift t=.001 .2(Je-5 .20e-2 .15e-5 .20e-5 .20e-2 .15e-5 .20e-5 .20e-2 .15e-5 t=.l .72e-2 .12 .60e-2 .51e-2 .68e-l .42e-2 .35e-2 .32e-l .29e-2 t = .3 .37e-l .15 .16e-l .13e-l .45e-2 .58e-2 .23e-2 .26e-l .12e-2 t=.5 .63e-l .12 .76e-4 .10e-l .20e-l .14e-4 .16e-2 .10e-l .10e-5 t=1.0 .11 .59e-l .15 .25e-2 .80e-2 .67e-2 .76e-3 .37e-2 .12e-2 Table 2.3: S R M errors for Example 2.3 using backward Euler E x a m p l e 2.4 Here we investigate the use of the modified formula (2.42) instead of (2.35). First, we solve the previous example numerically using (2-42). In Table 2.5 we record error values at the singularity point t = .5 after 3 SRM iterations, starting with yo(t) = 1 and using as before e = .1 and h â€” .001 (cf. Tables 2.5). From these results it is clear that the SRM with (2.42) does not work well when a.\ 7^ 0: large errors in By are obtained near the singularity and these adversely affect the accuracy in x as well. However, the comparison changes when there is no singularity in the constraints: We now replace the algebraic constraint in Example 2.3 by i + %2 â€” e x - t â€” t sm =0 leaving everything else the same (including the singularity in B). In Table 2.6 we record maximum errors in x and By over all mesh points (denote those 'exg' and Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations^ iteration 1 error at â€”) t=.u(Jl ex .50e-6 .20e-2ey drift .50e-6 ex .50e-6 .20e-2 ey drift .50e-6 ex .50e-6 .20e-2 ey drift .50e-6 2 3 t=.l .71e-2 .12 .60e-2 .51e-2 .68e-l .42e-2 .35e-2 .32e-l .29e-2 t = .3 .36e-l .15 .16e-l .12e-l .41e-2 .58e-2 .43e-2 .26e-l .12e-2 t=.5 .63e-l .12 .76e-4 .10e-l .20e-l .14e-4 .18e-2 .97e-2 .lle-5 t=1.0 .11 .60e-l .15 .44e-2 .70e-2 .67e-2 .98e-3 .46e-2 .12e-2 Table 2.4: S R M errors for E x a m p l e 2.3 using forward Euler (0,1 ) ex ey .16e-2 . 10e-l .18e-2 . 96e-2 ( a i , a ) -> method backward Euler forward Euler 2 (M) ex ey .80e-3 .20e+l .25e-2 .18e+l ex .15 .64 (1,1) ey .37e+3 .15e+4 Table 2.5: Errors near singularity using modified formula (2.42) 'eyg', respectively) for the starting iterates yo(t) = 1 and yo(t) â€” 0 (the latter does not agree with the exact y (0)). e yo = 1 = 0 ( a i , a ) -> method backward Euler forward Euler backward Euler forward Euler 2 (o, 1) exg eyg .46e-2 .44e-l .45e-2 .44e-l .22e-l .97 .22e-l .97 (h, 1) exg eyg .45e-2 .43e-l .44e-2 .43e-l .22e-l .94 .94 .22e-l (1, exg .22e-3 .19e-3 .12e-3 .19e-3 1) eyg .28e-3 .23e-3 .75e-3 .75e-3 Table 2.6: Errors for problem without singularity using modified formula (2.42) The modified method (corresponding to ( a i , a ) = (1,1) in Table 2.6 is seen to 2 work better for problems without singularities. The above calculations a l l agree w i t h our theoretical results described i n Â§2.5 and Â§2.6. Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations4Q 2.8 M o r e about the P r o o f of T h e o r e m 2.1 To provide a better understanding about the sequential regularization method we now give a detailed proof of Theorem 2.1 for the initial value case w i t h no layers, s < J + l. J is some positive integer defined i n Definition 2.1. In this proof, the construction of the asymptotic expansion is directly for x and By. Moreover, the construction method we apply is somewhat different from [111, 112] and more relevant to the concept of DAEs. T h e same idea is applied to prove the convergence of the S R M for Navier- Stokes equations i n Chapter 4. For s > J + l , additional initial layer expansions have to be developed. However, the construction of these layer expansions is precisely the same as i n [111, 112] and so it is omitted here. In case that (2.17) are i n i t i a l conditions (i.e. B\ = 0) our assumptions i m p l y that (2.17) together w i t h (2.18b) specify x(0), say x(0) = x (2.70) A t first, consider the case s = 1 of (2.34),(2.35): ex[ + B(GB)~ (Gxi +r) = eAx - eBy + eq, l w i t h the i n i t i a l conditions (2.70). x 0 This is a singular-singularly-perturbed problem (see [112, 89]). Let x\ = x + exn H 10 + ex s ls H Comparing the coefficients of like powers of e, we thus have B(GBY Gx l w B{GB)- Gx l xl B{GB)- Gx l u = -B(GB)~ r (2.71a) = -x' = - z i , - . ! + Axu-i, l 10 + Ax -By 10 0 + q, 2 < i < s + 1, where (2.71a) satisfies (2.70) and (2.71b) and (2.71c) satisfy homogeneous conditions corresponding to (2.70). (2.71b) (2.71c) initial Now, (2.71a) has infinitely many solutions i n Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations^! general. To realize the construction, we should choose x\o to satisfy (2.71a) and to ensure that the solution of (2.71b) exists. We choose x w to be the solution x of e problem (2.16)-(2.17), i.e. x[ = Ax 0 - By + g, 10 0 = Gx l0 (2.72a) e + r, (2.72b) Â£ *io(0) = 8. (2.72c) o So xw â€” x and (2.71b) has the following form e B(GB)- Gx = B(y -y ). 1 11 e (2.73) 0 Now we choose i n and a corresponding j/oi to satisfy x' = Ax - By (2.74a) = GB{y -y ), (2.74b) n n Gx n e B x {0) o 01 n 0 = 0. (2.74c) N o t i n g that By â€” â€”x' + Ax + q is smooth, we have GB(y e e e â€” yo) Â£ <S\ Hence, e using L e m m a 2.1, there exists a smooth solution x n of (2.74), and xn satisfies (2.73). Indeed, using (2.74b) and Definition 2.1, we have G(0)a;n(0) = 0, so s ( 0 ) = 0. A n d , n from (2.74b) again, {GB)- Gx = y- x n e y , for each t Â£ [0,Q U {U,t }. 0 f That is, B(GB)~ Gx 1 11 = B{y - y ),t Â£ [0,U) U (U,t ]. e 0 f (2.75) Taking the l i m i t of (2.75) at Â£*, we thus get that Xu satisfies (2.73) for each t Â£ [0, tj\. Moreover, from Definition 2.1, we have yoi(0) = y' (0) = â€¢â€¢â€¢ = y o r ( 0 ) = 0, s < J + 1. 1} ol Chapter 2. Sequential Regularization Methods for Differential Algebraic EquationsA8 Also we note that .Byoi is smooth. Generally, supposing we have got X i , - _ i , i ? y o i - i and yo,-i(0) = y _ ( 0 ) = - - - = y S n Oj + 1 ) 1 (0) =0 for i > 2, we choose xu, yo; satisfying x' = Axu - By , u Gxu = oi (GB)y i-i, 0 B xu(0) = 0. o B y the same argument as before, we obtain that xu satisfies (2.71c) for 2 < i < s + 1, and yoi(0) = y' (0) = â€¢â€¢â€¢ = y S r Â° ( 0 ) = 0, s < J + 1. oi Also, Byoi is smooth. Next we denote the asymptotic solution xu+i = xio + ex i i H he x s l s +e s + 1 a;i i s + and ^ls+l = X i â€” Xls+l- Then tz' ls+1 + Pzis+i = eAz +e ls+1 s + 2 (-x' l s + 1 + Axi i), s + *i +i(0) = 0s Let u i s + i = Rzi i and w\ i = Pzi i. s+ s+ s+ 2 l s + Hence, we have (cf. (2.38)) . i = Su i ls+ + W i ls+ and u' u+1 = (RA + R')Su ls+1 + {RA + R')w ls+1 + 0{e ), s+1 Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations49 ew' = e{PA + P')Su +w l3+1 + e(PA + P')w ls+1 la+1 u (0) = 0, w (0) ls+1 Using L e m m a 2.2, we get w i ia+ = 0. la+1 = 0(e ) and u i s+2 z la+1 = 0(e ), i.e. s+1 is+ = + 0{e ), s+2 la+1 0(e ). s+1 Therefore, xj = x Noting x 1 0 + e.T + : - - + Â£ x + O(e s 1 0 11 l s e l = 0{t). e T h e n , by using (2.35),(2.76),(2.71),(2.72a) (2.77) and (2.74a), i t follows that Byi = By + -^B{GB)-\G 0 Vl (2.76) = x , we thus obtain x -x B ). 5 + 1 = By + \{Px = Bye + eByoi + '-' + t^Byos-i 0 + B(GB)- r + ePx + --- + e Px 1 w + r) Xl s 11 + O(e + )) s ls 1 + O^) or By - By = 0(e). x (2.79) e Now we look at the second iteration s = 2 of (2.34), (2.35): ex' + B(GB)~ (Gx + r) = eAx - tBy + eq, 1 2 2 2 x w i t h i n i t i a l conditions (2.70). Let x =x 2 + ex + e x 2 20 21 22 H . N o t i n g that (2.78) gives us a series expansion for By we obtain, x B{GB)~ Gx o = -B(GB)~ r, B{GBY Gx = -x' + Ax = -x' _ + Ax - l 2 l 21 B{GB)~ Gx l 2i (2.80a) l 20 2l 20 x - By + q, (2.80b) e 2i X - By 0l U 2< i < s + 1 (2.80c) Chapter 2. Sequential Regularization Methods for Differential Algebraic EquationsbO A g a i n , (2.80a) satisfies initial conditions (2.70) and (2.80b) and (2.80c) satisfy the corresponding homogeneous ones. A s the case of s = 1, we choose X Q = x . W e thus 2 e have B{GB)- Gx = 0. 1 2l T h e n Â£21 is constructed to satisfy x' = Ax i â€” Byu, 21 (2.81a) 2 Gx = 0, 2l (2.81b) Â£0x21(0) = 0. (2.81c) Obviously x i = 0 since (2.81) is uniquely solvable for x 2 by L e m m a 2.1. In general, 2i similarly to the case of s = 1, we choose x i satisfying. 2 x' = Ax 2l Gx (2.82a) u = - ( G f l ) ( y , - i - yu-i), 2l (2.82b) 0 B x (0) 0 - By , 2l 2l = 0. (2.82c) for 2 < i < s + 1. B y applying L e m m a 2.2 and the same argument as i n the case of s = 1 we get x = x + tx 2 e +ex 22 + â€¢â€¢â€¢ + e x e = 0(e ). 2 2l s + 0(e ) (2.83) s+1 2s or x -x 2 (2.84) 2 T h e n , using (2.35),(2.80),(2.81a),(2.82a), (2.83) and (2.78), we conclude By 2 = = By^ -B{GB)-\Gx -rr) l 2 By + 5 y 2 J e e + --- + e - 5 y _ + 0 ( e ) s 1 2 1 s l s 1 (2.85) or By - By = 0{e ) 2 2 e (2.86) Chapter 2. Sequential Regularization Methods for Differential Algebraic Equations^! We can repeat this procedure, and, by induction, complete the proof for s < J + l. â€¢ Chapter 3 S R M for N o n l i n e a r P r o b l e m s In the previous chapter we derived the sequential regularization method and gave a detailed continuous and discrete analysis for linear index-2 D A E s . T h e method relates to a combination of stabilization and penalty-like methods. In this chapter we extend the method to nonlinear index-2 and index-3 problems (u = 1 and v â€” 2 i n (2.15)), including constrained m u l t i b o d y systems. A number of variants are proposed, and particularly effective methods are singled out i n certain circumstances. A l l results obtained here are certainly applicable to the linear case. T h e chapter is organized as follows: In Â§3.1 we consider problems without constraint singularities. T w o S R M variants are discussed. One variant involving ^ (corresponding to (2.32), (2.33)) leads to nonstiff problems. Taking E = I is particularly attractive. T h e other variant, corresponding to (2.32), (2.33) w i t h a\ = 0, does not involve ^ . T h e choice E = possible (otherwise one can choose E = (GB) ), T makes the computation particularly simple. Problems w i t h constraint singularities are considered i n Â§3.2. T h e S R M corresponding to (2.34), (2.35) is proposed for such problems. T h i s variant works well i n practice, but our proofs to date extend only to the linear case. In Â§3.3 we analyze and discuss various methods for index-3 problems. A number of S R M variants are possible, combining regularization w i t h Baumgarte's stabilization or w i t h invariant stabilization [8]. O f particular interest, i n case of no constraint singularity, are the methods (3.47) and (3.33)â€”(3.35) which corresponds to invariant 52 Chapter 3. SRM for Nonlinear Problems stabilization. 53 T h e choice E = I leads to particularly simple iterations. A corre- sponding convergence result is given i n Theorem 3.3. In case of a possible constraint singularity, the S R M (3.41) is recommended. These methods are reformulated i n Â§3.4 for the special case of m u l t i b o d y systems w i t h holonomic constraints. T h e "winning" methods are (3.44)-(3.45) w i t h E = I for the nonsingular case and (3.46)-(3.47) for the case where the constraint Jacobian may have isolated rank deficiencies. In Â§3.5 we report the results of numerical experiments confirming our theoretical predictions and demonstrating the effectiveness of the proposed methods. 3.1 N o n l i n e a r , N o n s i n g u l a r Index-2 P r o b l e m s T h e nonlinear index-2 D A E (y â€” 1 i n (2.15)) reads: x' = 0 = f(x,t)-B(x,t)y, (3.1a) g(x,t), (3.1b) where / , B and g are sufficiently smooth functions of (x,t) G Râ„¢* x [0, Â£/], and y GR . nv W e consider this D A E subject to n â€” n boundary conditions x y b(x(0),x(t )) = 8. (3.2) f These boundary conditions are assumed to yield a unique and bounded solution for 1 the O D E (3.1a) on the manifold given by (3.1b). Concretely, i f we were to replace (3.1b) by its differentiated form (denoting G = |^) 0 1 = Gx' + g {= f ) (3.3a) flf(x(0),0) (3.3b) d t f = 0 locally unique, or isolated solution in a sufficiently large neighborhood would suffice. 54 Chapter 3. SRM for Nonlinear Problems and use (3.3a) i n (3.1a) to eliminate y and obtain n O D E s for x, then the boundary x value problem for x w i t h (3.2) and (3.3b) specified has a unique solution. In the i n i t i a l value case (i.e., when b is independent of x(tj)), this means that (3.2) and (3.3b) can be solved uniquely for x(0). In this section, we consider the case where GB is nonsingular. Generalizing the idea i n Â§2.4, we have the following S R M formulation for the nonlinear index-2 D A E s (3.1), (3.2): for s = 1 , 2 , . . . , x' = f(xâ€žt) s -B(x ,t)y , a (3.4) a where y = y -i + ^E(x ,t)(a -^g(x ,t) s a s 1 a + ot g(x ,t)), 2 subject to the boundary conditions (3.2) and (3.3b). (3.5) a Note that yo(t) is a given i n i t i a l iterate which we assume is sufficiently smooth and bounded and that e > 0 is the regularization parameter. T h e regularization matrix E is nonsingular and has a uniformly bounded condition number; possible choices are E = I, E = (GB) -1 others (e.g. E = (GB) , T and cf. [11, 94]). W e note that if we take y = y then x\ = x , 0 where x and y are the solution of (3.1). If we take y = 0, then one S R M iteration 0 is the usual penalty method (cf. [84, 91, 69]). A s customary for the penalty method, we assume: A s s u m p t i o n 3.1 The problem (3.4), (3.5),(3.2),(3.3b) has a unique solution and the solution is bounded if y -\ s is bounded. A s s u m p t i o n 3.1 is generally true for i n i t i a l value problems. For general boundary value problems, we expect that it would hold for most practical cases since (3.4) (with (3.5) plugged in) may be seen as a perturbed problem of (3.1) according to the proof of Theorem 3.1 (see below), where the perturbation and its first derivative are both small i f e is small. Chapter 3. SRM for Nonlinear Problems 55 To analyze the S R M , we assume the following perturbation inequality: For 0 < t<t , f \\x{t) - x{t)\\ < M max (\8(T)\ + \8'(T)\), (3.6a) 0<T<i f \W)-y{t)\\ < M max (\8(T)\ + |<T(T)|), (3.6b) 0<r<i / where || â€¢ || is some l p norm (say, the m a x i m u m norm), and x and y satisfy the following perturbed version of (3.1): x' = f(x,t)-B(x,t)y, (3.7a) 0 = g(x,t) + 8(t) ' (3.7b) w i t h the same boundary conditions as (3.2). For initial value problems, (3.6) has been proved i n [58], pp. 478-481. It is actually the definition of the perturbation index introduced i n [58]. Furthermore, (3.6) also holds for boundary value problems if we impose some boundedness conditions on the corresponding Green's function (cf. [14]). The case ct\ ^ 0 i n (3.5) is sufficiently different from the case oc\ = 0 to warrant a separate treatment. 3.1.1 T h e case a i = 1 Now we estimate the error of the sequential regularization method (3.4)-(3.5). We prove a theorem which says that the error after s S R M iterations is 0(c ) s (i.e., each iteration improves the error by 0(e)) everywhere i n t. This result coincides w i t h that of the linear case. T h e o r e m 3.1 Let all functions in the DAE (3.1) be sufficiently smooth and the above assumptions hold. Then, for the solution of iteration (3.4), (3.5) with Qi ^ 0, we have Chapter 3. SRM for Nonlinear Problems 56 the following error estimates: x (t)-x (t) = 0(e ), y.(t)-y (t) = 0(e ), s e e s s for 0 < t < tj and s > 1. P r o o f : Let v = g(x ,t). s T h e n , from (3.4), s v' = G(x , t)x' + g (x , s s s t t) = G(x ,t)f(x , s s t) - G(x ,t)B(x , s s t)y s s + g (x ,t). t s Using (3.5), we thus have (e(GBE)~ 1 + I)v' + a v s = e(GBE)~\Gf vâ€ž(0) = 0. s 2 + g ) - tE^y,^, t (3.8a) (3.8b) Therefore it is not difficult to get v s = g(x ,t) = 0(e), s v' = g(x ,t)' s s = 0(e), (3.9) if y _ i is bounded (which implies that x is bounded from A s s u m p t i o n 3.1). s s For s = 1, we have x'i = f(xi,t)-B(x ,t)y 1 g(x t) = 0(e), u 1 g(x t)'= 0(e) u since yo is chosen to be bounded. F r o m assumption (3.6), we immediately get X! - x = 0 ( e ) , j / i - y = 0(e). e (3.10) e T h e n it is easy to see that j / i is bounded. So for s = 2, we obtain x' 2 = f(x2,t)-B(x ,t)y 2 g(x ,t) 2 = 0(e), 2 g'(x ,t) 2 = 0(e) Chapter 3. SRM for Nonlinear Problems 57 B y using assumption (3.6) again, this yields x â€” x = 0(c). 2 e Hence it can be verified, by substituting (3.3a),(3.la) for the exact solution, that the right hand side of (3.8a) becomes 0(e ). So, from (3.8), we can get 2 g(x ,t) = 0(e ), g'(x ,t) = 0(e ). â€¢ 2 2 2 2 A p p l y i n g assumption (3.6), it follows that x - x = 0(e ), y -y = 0(e ). 2 2 e 2 (3.11) 2 e T h i s also gives the boundedness of y . 2 We can repeat this procedure, and, by induction, conclude the results of the theorem. â€¢ F r o m (3.8) it is clear that there is no stiffness here, so we can choose e > 0 very small, so small i n fact that one S R M iteration would suffice for any desired accuracy, and discretize the regularized O D E , possibly using a nonstiff method like explicit R u n g e - K u t t a . T h i s gives a modified penalty method [/ + e- BEG}x' = f - B y x 0 e~ BE(g + a g) 1 t (3.12) 2 where B,E,g etc, all depend on x , w i t h the subscript 5 = 1 suppressed. For the choice E = (GB)~\ let P = BEG = B(GB)~ G be the associated l projection m a t r i x . M u l t i p l y i n g (3.12) by *_ P and by I â€” P, respectively, and then t adding together, we have x' = f - rrr^Byo - -J-L-^BiGBr^Gf + 9 t + a g) 2 Thus the iteration obtained is similar to Baumgarte's stabilization x' = f - B(GB)~ [Gf 1 + 9 i + a g] 2 (3.13) Chapter 3. SRM for Nonlinear Problems 58 In fact, the single S R M iteration tends to (3.13) i n this case when e â€”> 0. Indeed, the parameter cx is the usual Baumgarte parameter, and choosing cx > 0 obviously 2 2 makes equation (3.8a) asymptotically stable for the drift v . A s indicated i n [12], for s both of these methods we can apply post-stabilization instead, i.e. take a 2 = 0 but stabilize after each discretization step [8, 9]. For reasons of computational expense, it may be better to choose E = / i n (3.12). T h e iteration obtained is simple, although a possibly large m a t r i x (with a special structure) must be "inverted". E x a m p l e 3.1 The choice of E = I is utilized in Chapter 4 (see also [80]) for the time-dependent, incompressible Navier-Stokes equations governing fluid flow. The advantage gained is that no treatment of pressure boundary conditions is needed, unlike methods based on Baumgarte-type stabilizations which lead to the pressure-Poisson equation. â€¢ 3.1.2 T h e case a = 0 x For this case the drift equation (3.8) is clearly stiff for 0 < e <C 1. A s i n Â§2.5, we denote J such that yo(O) = y (0), y' (0) = y' (0),y (0) { J) e o e 0 = y( )(0), J (3.14) where J = â€”1 i f yo(0) ^ y (0), then we can prove the same result as Theorem 3.1 e for s < J + 1. Note that we may choose y 0 satisfying (3.14) for some m > 0 by expressing y i n terms of x at t = 0 for initial â€¢ value problems. B u t this starting procedure generally does not work for boundary value problems. Hence we state and prove the theorem for initial value problems and comment on the boundary value case following the proof. 59 Chapter 3. SRM for Nonlinear Problems T h e o r e m 3.2 Let the assumptions of Theorem 3.1 plus (3.14) hold. In addition, suppose that the matrix function E(x,t) has been chosen so that GBE is positive definite. Then, for the solution of iteration (3.4),(3.5) with ot\ = 0, we have the following error estimates: x (t)-x (t) = 0(e ), y (t)-y (t) = 0(e ), s e s for 1 < s < J + 1 andO <t e s s <t . f P r o o f : W e derive the result for the case s < J + 1 = 2. Following the proof, we w i l l comment on additional generalizations. The key is again the basic drift equation (3.8), which we rewrite here as ev' + (GBE)v s s v (0) 3 = e{Gf + g -GBy _ ), (3.15a) = 0. (3.15b) t s 1 where quantities are evaluated as before, at ( x , t ) , unless otherwise noted. s For 5 = 1, given the boundedness of yo we obtain as before >h - 0(e) To obtain a similar result for v[, however, a different procedure from that of T h e o r e m 3.1 is needed. Note that at t = 0, the condition yo(0) â€” y(0) implies (Gf + g -GBy )\ t o t=o =0 Hence from (3.15a), ui(0) = 0. Differentiating (3.15a) w i t h respect to t and using v\ = 0(e), we get ev" + (GBE)v[ = 0(e), and this yields vi = 0(e) v[(0) = 0 Chapter 3. SRM for Nonlinear Problems 60 F r o m assumption (3.6) we then get (3.10). Subtracting (3.1a) from (3.4) and using (3.10) gives also x[ = x' + 0(e) and boundedness of y[ is obtained from a differentiation of (3.5). For s = 2, given the boundedness of y i (by (3.10)) and j/i(0) = 2/(0), we get as for s = 1 v = 0(e), v' = 0(e) 2 2 and hence also x â€” x + 0(e) 2 T h i s yields that the right hand side of (3.15a) is 0(e ), so 2 v = 0(e ) 2 2 Now comes the delicate part. To obtain an 0(e ) estimate also for v' , so that the 2 2 estimate (3.6) can be used to complete the proof, we differentiate the drift equation again, obtaining tv' ' + (GBE)v' = 0(e ) + e(Gf + g 2 2 2 t GBy,)' and v' (0) = 0 obtained as for the 5 = 1 case. We are then left to show that 2 F(x , t) := (Gf + g - GB )' 2 t yi = 0(e) (3.16) For this purpose we must estimate v" first. Using the condition y' (0) = y'(0), and o also xi(0) = x(0), x[(0) = x'(0) (obtained from (3.4)), we can obtain (Gf(x t) u +g (x ,t) t 1 - GB(x ,t)y )'\t=o = 0 1 Hence v"(0) = 0 from (3.15a) once differentiated. now obtain precisely as when estimating v[ above, vÂ» = 0(e) 0 Differentiating (3.15a) twice we Chapter 3. SRM for Nonlinear Problems 61 T h e boundedness of a l l needed quantities can also be obtained i n the same way as before. F i n a l l y , we note v[ = Gx[+g (x t) t = Gf(x t) u u + g (xi,t) t GB(x t) u yi Ready to show (3.16), we now write F(x , t) = [(Gf(x ,t)-Gf(x t))+(g (x ,t)-g (x t)) 2 2 u t 2 t + (GB(x t)-GB(x , u O u r previous estimates allow the conclusion that x u 2 = x\ + 0 ( e ) , x 2 2 t)) -v[}' yi = x[ + 0 ( e ) , hence we can finally conclude the estimate (3.16) and obtain the result of the theorem for 5 = 2. T h e proof proceeds i n a similar manner for larger J. estimate Generally, one needs the = 0 ( e ) , 1 < j < J + 1, and this necessitates (3.14). â€¢ R e m a r k 3.1 The convergence result holds for all s (i.e. also for s > J + l , assuming sufficient smoothness) away from an initial layer of size 0(e) in t. This is so because E is chosen so that we can express the solution for small e as a smooth outer solution which is bounded in terms of the right hand side as before, plus an initial layer of width 0 ( e ) . Conditions (3.14) then ensure that the layer error is bounded by 0 ( e J + 1 ) for the first J + l iterations. â€¢ R e m a r k 3.2 For boundary value problems, there is no obvious technique to ensure J > â€” 1. For a given J, the results of Theorem 3.2 and Remark 3.1 can be extended as in Chapter 2. This requires a different proof technique, though. Basically, an asymptotic expansion for x s solution x , y. and y s is constructed, where the first term is the exact This latter proof technique follows more along traditional singular perturbation lines (see [112, 89, 69]), and is not as close to Theorem 3.1 and to DAE concepts. â€¢ Chapter 3. Taking a SRM for Nonlinear Problems 2 62 = I without loss of generality, we obtain the iteration x'â€ž = f - Bys-, - e-'BEgixs, t) (3.17) T h i s is a singular, singularly perturbed problem (so e should not be taken extremely small compared to machine precision even if a stiff solver is being used). If GB is positive definite then we may choose E â€” I, and this yields a very simple iteration i n (3.17) which avoids the inversion necessary in stabilization methods like Baumgarte's. However, i f an explicit discretization method of order p is contemplated then approximately p S R M iterations like (3.17) are needed, because one must choose e = 0(h), where h is the step size. 3.2 N o n l i n e a r , Singular Index-2 P r o b l e m s In this section we consider the nonlinear index-2 problem (3.1) w i t h an isolated singular point t*, i.e. GB is singular at t*. For simplicity, we assume that B and g are independent of t. Denote P(x) â€” B(GB)~ G. 1 Motivated by constrained m u l t i b o d y systems (see E x a m p l e 2.1), we assume P(x) to be differentiable i n t, but f^-(x) may be unbounded. For this reason, we consider only the case a\ = 0 i n this section (cf. Chapter 2 for the linear case). In the drift equation (3.8) we then have essentially the singularly perturbed operator ev' + GBEv E = (GB) T to consider. T h e choices of E = / or yield a turning point problem (i.e., at least one of eigenvalues of the ma- trix GBE vanishes at the point Â£*), which complicates the analysis, even i n the linear case , and degrades the numerical performance as well i n our experience. Therefore, we choose E = (GB)~ . l In the sequel we will be careful to evaluate the effect of E only when its singularity l i m i t is well-defined, as e.g. i n P(x). A direct generalization of the linear case i n Chapter 2 would give the S R M formulation (3.4), (3.5) where instead of updating y (because y may be unbounded at 63 Chapter 3. SRM for Nonlinear Problems t*) we update By by B{x )y s s = Bix^y,-! + -B{x ){G{x )B{x ))l 1 s s s g{x ). (3.18) s However, (3.18) needs to be modified, since we may have RangeB(x ) ^ s RangeB(x -\). s So we use the projection P(x ) to move from RangeB(x -\) to RangeB(x ). T h e n we s s s consider the following S R M formulation for singular problems: x' s B(x )y s s = f(xâ€žt)-B(x,)y , = P{x )B{x -i)y,- (3.19a) a B t + - B(x )(G(x )B{x ))- g(x ), l X e s s s s (3.19b) where x satisfies the boundary condition (3.2). s If the assumptions given at the beginning of Â§3.1 and i n Theorem 3.2 remain valid, then the result of Theorem 3.2 still holds. Unfortunately, for the singular problem, assumption (3.6) may not be true i n general. To see this, consider one iteration, i.e. 5 = 1. T h e accuracy for the approximation of x depends on the extent that the bound (3.6a) holds. N u m e r i c a l experiments show that we can get a good approximation of x near the singularity. B u t the situation for By is worse, and the bound (3.6b) often does not hold. Indeed, assume for the moment that we have a good, smooth approximation of Sciy xs â€”â€¢ x^ i.e. (3.7) holds w i t h 8,8' = 0 ( e ) , and B(x)y is defined by (3.19b) for some B ( x _ i ) y _ i . F r o m (3.7) we have s s B(x)y = P(x)f{x,t) + ri,' where n = B(x)(G(x)B(x))~ 8'. 1 (3.20) It is not difficult to find that the exact B(x)y from (3.1) satisfies B(x)y = P(x)f(x,t). (3.21) Yet, even i f n is small, B(x)y may not be a good approximation of By because | ^ may be unbounded at the singular point so that P(x) is not a good approximation of P(x). Chapter 3. SRM for Nonlinear Problems 64 g(x) = â€” cosa?i â€” cosx ., and G = B = s i n X\ s\nxism.x \ E x a m p l e 3.2 In (3.1) let x = (xi,x ), T ( 2 2 2 2 j . sin X i sin Â£ 2 sin x / Clearly, at a singular point x = (0,7r), the value of P depends on the direction from 2 2 which it is approached. Thus, |^ is unbounded, even though P is a differentiable function oft. Further letting f = ( s i n x â€” s i n x i ) - 1 2 (sin Â£2 2 sin 2 2 â€” sinxi) r ; and given the initial conditions Â£ i ( 0 ) = â€” 7 r / 2 , Â£2(0) = n/2, the exact solution is T x(t) = (t â€” ir/2 t + ir/2) 1 , y = (sinx â€” sinXi)~ 2 Thus, as t crosses t* = n/2, y(t) becomes unbounded, but By = (sin x 2 â€” sin X i ) - 1 ( sin x, s i n x 2 ) T remains bounded. However, it is easy to perturb x(t) slightly and smoothly in such a way that the perturbed By becomes unbounded near t = t*, still satisfying (3.7) with a small 5. â€¢ Note that for the linear model problem (see Chapter 2), P = P(t) is independent of x. Hence we do not have the above difficulty i n the linear case. For the nonlinear problem, the accuracy near the singular point is reduced and it no longer behaves like 0 ( e ) for more than one iteration. However, we do expect 0(e ) accuracy away from s s the singular point, assuming that no bifurcation or impasse point is encountered by the approximate solution . 3.3 S R M for N o n l i n e a r H i g h e r - i n d e x P r o b l e m s We now generalize the S R M to the more general problem (2.15). In particular, we consider the index-3 problem (y â€” 2). T h e Euler-Lagrange equations for m u l t i b o d y systems w i t h holonomic constraints yield a practical instance of the problem. T h e Chapter 3. SRM for Nonlinear Problems 65 S R M formulations presented i n this section are easy to generalize for more general problems (2.15) (index u + 1). The index-3 problem reads: x". = f(x,x',t)~ B(x,t)y, (3.22a) 0 ' = g(x,t), (3.22b) w i t h given 2(n â€” n ) boundary conditions, x y b(x(0),x(t ),x'(0),x'(t )) f = 0. f (3.23) T h e meaning of G, B and the stabilization m a t r i x E below remain the same as i n the index-2 problems considered i n previous sections. 3.3.1 T h e case of nonsingular GB We first use the idea from previous sections, v i z . a combination of Baumgarte's stabilization w i t h a modified penalty method, to derive the S R M for the nonlinear index-3 problem (3.22). T h e n we apply a better stabilization [8] to generate a new S R M which is expected to have better constraint stability. Finally, we seek variants which avoid evaluation of complicated terms i n the second derivative of the constraints. First consider, instead of (3.22b), the Baumgarte's stabilization d d 2 dJ2 ( ^ ai 9 x,t + dt ^ ' a2 9 X,t ) 9( > ) + ot3 x t = 0(x(O),O) = O, !<7(*(0),0) Â°>. = 0, (3.24a) (3.24b) where ctj,j = 1,2,3 are chosen so that the roots of the polynomial 3 a(r) = Y, 3 ~ a r3 3 i=i are all negative. Following the procedure of previous sections, we can write down an S R M for (3.22): for s = 1, 2 , . . . and y given, 0 x': = f(x ,x' ,t)-B(x ,t)y , s s s s (3.25) 66 Chapter 3. SRM for Nonlinear Problems where x satisfies boundary conditions (3.23) and (3.24b) and y is given by s s y = Vs-i + -E(x ,t)(a â€”g{x ,t) e s s 1 + a â€”-g(x ,t) + a 2 s a g(x ,t)). 3 s It is not difficult to repeat the approach of Â§3.1 for the present case. (3.26) Under assumptions similar to the index-2 case, i.e. (3.6) w i t h a change to include 6~"(r) at the right hand side (cf. [58]) and Assumption 3.1 w i t h the addition that the derivative of the solution is also bounded, we readily obtain extensions of Theorems 3.1 and 3.2 for the cases Â« i ^ 0 and a = 0 (with a ^ 0), respectively. We do not x 2 allow Â« ! = a = 0 since i n this case equations (3.25),(3.26) have different asymptotic 2 properties. Note that the S R M (3.25),(3.26) with Qi = 0 avoids computing g ; xx however, the iteration obtained now calls for solving problems which become stiff when e gets small, and to avoid g xx one should use a non-stiff discretization method. T h i s formulation w i t h E = I and a.\ ^ 0 is the same as that proposed i n [20, 19] using the augmented Lagrangian method. Another way to generalize the S R M to higher index problems is based on invariant stabilization. Its advantages over Baumgarte's stabilization have been discussed i n [8, 9]. We thus prefer the way based on this stabilization. Theoretical evidence is also mentioned i n Remark 3.4. W e first describe this new stabilization. B y two direct differentiations of the constraints (3.22b), we can eliminate y and get an O D E f(x,x',t), (3.27) for which the original constraint (3.22b) together w i t h its first derivative give an invariant. T h e idea of the method is to reformulate the higher index D A E (3.22) as a first order O D E (cf. (3.27)): (3.28) w i t h an invariant 0 = h(z,t), (3.29) Chapter 3. 67 SRM for Nonlinear Problems where and to consider the stabilization families z' = f(z,t)- F(z,t)h(z,t), (3.31) 7 where F = DE for some appropriate matrix functions D and E such that E and HD are nonsingular and H = h . The O D E (3.31) coincides w i t h Baumgarte's z stabilization for the index-2 problem (3.1) with D = B and E = E = (HD) . One -1 choice for D is D = H , T but others w i l l be mentioned below. Note that (3.31) has the same solution as the original problem (3.22) for any parameter value 7. A l t h o u g h the method has better constraint stabilization, both the evaluation of / and that of H involve g xx which may be complicated to calculate i n practice. Next, we present an S R M method based on invariant stabilization which avoids the computation of / . In fact, we can avoid g altogether using the new stabilization. xx If we do not eliminate y by differentiations, f(z,t) i n the stabilization (3.31) becomes ^ = ( , ( M ) - V 0 Â» ) - < 3 ' 3 2 ) Since y is not known i n advance, we use an iterative S R M procedure to calculate y as in [20, 11]. T h e solutions of the iterative procedure no longer satisfy (3.22) precisely. Hence the iterative procedure has to be a regularization procedure and the parameter i n (3.31) is changed to 7 = ^ to emphasize that it must be chosen sufficiently large. These lead to the following S R M formulation (for simplicity of notation, we only consider the special case where B and g are independent of t): < = ( ) Z2s ZlS = ( % , \ f{z ,t) - B(z )y,-i Z f ( ( a u ) - -F(z )h(z ), I e s s (3.33) Chapter 3. SRM for Nonlinear Problems 68 where z satisfies boundary conditions (3.23), (3.24b) and h = (g(zi), G(zi)z ) . Thus T s 2 the Jacobian of h is H = ( ^ ^ \ L(z) I , where L = ) ' G( ) Zl z?q (zx). ^ 2 i / xx V We choose D and E so that F = B ( E \0 ' Â°) = ( I ) \ Â° ) BE ) BE 0 (3.34) v ; where, as i n Â§3.1, E is chosen such that GBE has non-negative eigenvalues. U p d a t i n g y by y = y -\ + -E(z )G(z )z s s ls ls (3.35) 2s implies that the second part of the original index-3 system holds exactly, i.e. 2s = f( *;t) - z B(z )y . z ls s Next we analyze the convergence of (3.33)â€”(3.35). A g a i n we assume that the solutions of (3.33), (3.23), (3.24b) exist uniquely and are bounded if y _ i is bounded s (see A s s u m p t i o n 3.1 ). Assumption (3.6) changes slightly: W e first rewrite the system (3.22) as z[ = z, . z' = f(z,t)-B( )y, (3.36b) 0 = g( ). (3.36c) 2 (3.36a) 2 Zl Zl T h e n we assume the following perturbation bound, \\z(t) - z(t)\\ < M m a x (|<y(r)| + \S'(r)\ + + I W I + IWI), (3.37a) U S T S l f \\y(t) - y(t)\\ < M max (\S(T)\ + \S'(r)\ + \S"(r)\ + \0(r)\ + \9'(r)\), (3.37b) 69 Chapter 3. SRM for Nonlinear Problems where z and y satisfy a perturbed problem of (3.36), z[ = z + 0(t), (3.38a) z' 2 = f(z,t)-B( )y, 0 = 2 (3.38b) Zl flfO)+ (3.38c) w i t h the same boundary conditions (3.23). A g a i n , for initial value problems, (3.37) can be easily proved by following the technique presented i n [58], and this can be extended for boundary value problems as well. = Similarly to the proof of Theorem 3.1, let h(z ) s I, where v s = g(z ), is \w J F r o m (3.33), we get the drift equations (cf. (3.15)) s w â€” G(z\ )z . s s 2s ev' s tv" s = -GBE(z )v = -GBE(z )v' s s + ew s (3.39a) s - LBE{z )v s s s + t[Lz 2s + Gf(z ) - GB(z )y . ] s s s 1 (3.39b) w i t h the i n i t i a l conditions v (0) = 0, w (0) = 0. A p p l y i n g (3.39a) and then (3.39b) s for s = 1, we obtain s = 0(e), wi = 0(e). v, = 0(e ), 2 T h e n (3.39a) further yields v[ = 0(e) Comparing (3.38) w i t h (3.33)-(3.35), we have to bound S= v 0= u -e~ BEvi l and their derivatives appearing i n (3.37). We already-have that 8 = 0(e ), 8' = 0(e), '9 = 2 0(e) T h e procedure that follows continues to be similar to the one employed i n the proof of T h e o r e m 3.2, so we only sketch it here for s â€” 1. F r o m (3.39a) we obtain v[(0) = 0. Using the condition yo(0) = y(0) gives [Lz 21 + Gf(z )-GB(z )y ]\t=o l 1 o = 0 Chapter 3. SRM for Nonlinear Problems 70 so, from (3.39b), also w[(0) = 0. Differentiating (3.39b) we get tw'l + GBE(z )w' l = 0(e), l ioi(0) = 0 hence w[ = 0 ( e ) . Differentiating (3.39a) we next have eo'l + GBE(z )v[ 1 = 0(e ), v[(0) = 0 2 so v[ = 0 ( e ) . This implies 2 8' = O(e), 8" = O(e) We can now use (3.37) and obtain the desired conclusion for 5 = 1, z l z + 0(e), = y i = y + 0(e), where {z,y} is the exact solution of the index-3 problem. Then, continuing to follow the proof procedure of Theorem 3.2, we obtain: T h e o r e m 3.3 Let all functions in the DAE (3.22) be sufficiently smooth and assume the above assumptions (particularly (3.37)) hold. Assume in addition that yo satisfies (3.14)- Then, for the solution of iteration (3.33)-(3.35), the following error estimates hold: z (t)-z (t) = 0(e ), (3.40a) y (t)-y (t) = 0(e ) (3.40b) s s forl<s<J e e s s + l. R e m a r k 3.3 Extensions of this theorem to the boundary value case and to s > J + 1 away from an initial layer are possible, similarly to the extensions for Theorem 3.2 contained in Remarks 3.1 and 3.2. â€¢ 71 Chapter 3. SRM for Nonlinear Problems R e m a r k 3.4 We note that, unlike Proposition 2.2 of [8], we do not assume \\H(z)f(z)\\ <^\\h(z)\\ 2 2 to discuss the stability and accuracy of the constraints. Also, from (3.39), we see the difference of the constraint stability or accuracy between SRM formulations based on Baumgarte's stabilization and the new stabilization. For the former, we only have v[ = G(z )z' n = G(z )z n u = Wi 21 So if we obtain w\ = 0(e) then v = 0(te). This can be much worse than what we x get from (3.39a). â€¢ 3.3.2 T h e case for constraint singularities For the singular case GB may be singular at some isolated point t* as described i n the previous sections. T h e situation here is similar to that for index-2 problems. A n examination of the drift equations (3.39) suggests that here, too, the choice E â€” (GB) -1 is preferable to E = I or E â€” (GB) . T T h e iteration for y is modified as s well. S t i l l assuming for simplicity that g and B do not depend explicitly on t, this gives, i n place of (3.33)â€”(3.35) the iteration z' u = z - -B(GB)- g(z ) (3.41a) 4s = f(*â€žt)-y. (3.41b) Vs = l 1 2s s P{z )y -i s s + ^P(z )z s (3.41c) 2s Also, as indicated i n Â§3.2 for index-2 problems, we cannot expect 0(e ) approxis mation near the singular point any more. B u t we do expect that (3.40) holds away from the singular point, because the singularity is i n the constraint and the drift manifold is asymptotically stable (following our stabilization). A numerical example Chapter 3. SRM for Nonlinear Problems 72 i n Â§3.5 w i l l show that we do get improved results by using S R M iterations for the singular problem. 3.4 S R M for C o n s t r a i n e d M u l t i b o d y Systems Constrained m u l t i b o d y systems provide an important family of applications of the form (3.22) and (3.1). We consider the system q' = v (3.42a) M(q)v' = f(q,v)-G(q) X (3.42b) 0 = g(q) (3.42c) T where q and v are the vectors of generalized coordinates and velocities, respectively; M is the mass m a t r i x which is symmetric positive definite; f(q, v) is the vector of external forces (other than constraint forces); g(q) is the vector of (holonomic) constraints; A is the vector of Lagrange multipliers; and G(q) = j^g. For notational simplicity, we have suppressed any explicit dependence of M , / or g on the time t. We first consider the problem without singularities. Corresponding to (3.22) i n Â§3.3, we have B = M~ G , l r so GB = GM~ G . l T Other quantities like h and H retain their meaning from the previous section. In some applications it is particularly important-to avoid terms involving g , xx since its computation is somewhat complicated and may also easily result i n mistakes and rugged terms. So [9] suggests post-stabilization using the stabilization m a t r i x F = M~ G (GM~ G )~ 1 T 1 T 1 ^ Q J j ( - ) 3 4 3 twice, instead of involving H, at the end of each time step or as needed. T h e y find that this F performs very well i n many applications. However, while this stabilization avoids the g xx term m F, g xx is still involved i n obtaining / , although only through Chapter 3. SRM for Nonlinear Problems 73 matrix-vector multiplications (see (3.27)). The S R M formulation (3.33)â€”(3.35) en- ables us to avoid the computation of / i n the absence of constraint singularities. For the m u l t i b o d y system (3.42) we write the iteration as follows: For s = 1, 2 , . . . , find {q , v } s by s q' = v - -BE(q )g(q ) v' = M- f(q ,v )-B{q )X - -^BEG(q )v s s (3.44a) l s s s (3.44b) 1 s s s s 1 s s T h e n update A by A = A _j + s s -EG{q )v . s It is easy to see that i n this S R M formulation the g Moreover, since GM~ G l T s term is avoided com- xx pletely. (3.45) l is positive definite, we can choose E = I i n (3.44),(3.45), obtaining a method for which Theorem 3.3 applies, which avoids computing (GM~ G )~ . 1 T 1 A l t h o u g h it requires an iterative procedure, a small number of iterations (p if an explicit discretization method of order p is used) typically provide sufficient accuracy. N u m e r i c a l experiments will show the 0(e ) s error estimate. Next we consider the singular problem, i.e. w i t h the m a t r i x GM G _1 T being sin- gular at some isolated point t*, 0 < t* < tj. A typical example of singular m u l t i b o d y systems is the two-link slider-crank problem (see E x a m p l e 2.1 and Figure 2.1) consisting of two linked bars of equal length, w i t h one end of one bar fixed at the origin, allowing only rotational motion i n the plane, w i t h the other end of the other bar sliding along the x-axis. Various formulations of the equations of motion for this problem appear, e.g., i n [60, 19, 11, 12, 94]. In our calculations we have used the formulation i n E x a m p l e 2.1 (see [11]), to make sure that the problem is not accidentally too easy. It consists of 6 O D E s and 5 constraints, w i t h the last row of the Jacobian m a t r i x G vanishing when the mechanism moves left through the point where both bars are upright ( 0 i = f, 02 = ^f, where Â£ ; , y ; , 0 ; are the coordinates of the center of mass of the ith bar). Chapter 3. SRM for Nonlinear Problems 74 T h e last row of G vanishes at this point and a singularity is obtained. We note that the solution is smooth i n the passage through the singularity w i t h a nonzero velocity. W h e n we attempt to integrate this system using a stabilization method like [8] which ignores the singularity, the results are unpredictable, depending on how close to the singular time point the integration process gets when attempting to cross it. In fact, radically different results may be obtained upon changing the value of the error tolerance. (Similar observations are made i n [94].) In some instances a general purpose O D E code would simply be unable to "penetrate the singularity" and yield a solution which, after hovering around the upright (singular) position for a while, turns back towards the initial position (solid line i n Figure 2.1). Such a pattern of motion may well look deceptively plausible. Methods which do not impose the constraints on the position level (e.g. methods consisting of differentiating the constraints once and solving the resulting index-2 problem numerically, or of projecting only on the velocity-level constraint manifold) perform particularly poorly (cf. numerical results i n [94]). T h i s is easy to explain: T h e position-level constraint corresponds to ensuring that the two bars have equal length. If this is not strictly imposed i n the process of numerical solution, inevitable numerical errors due to discretization may yield a model where the lengths are not close enough to being equal, and this leads to the lock-up phenomena described e.g. in [60], which have a vastly different solution profile. W e now wish to generalize the S R M to problem (3.42) w i t h singularities since we have seen its success for the linear index-2 case. F r o m the two-link slider crank problem, we find that, although GM~ G l and M~ G (GM~ G )~ g 1 T 1 T 1 T is singular at t*, P(q) = 1 T 1 T 1 are smooth functions of t for the exact solution or func- tions q satisfying the constraints, while M~ G \GM~ G )-\ l and the derivative M~ G (GM~ G )~ G 7 l T M~ G (GM~ G )~ G 1 T 1 T 1 g are not. Also, as indicated i n [11], A is no longer smooth, while BX is since we assume the solution q to be sufficiently smooth. We only include Chapter 3. SRM for Nonlinear Problems 75 (3.46a) (3.46b) X = P(q )X s s s + 1 (3.47) -P(q )v s s A s we indicated i n Â§3.2, we do not expect 0(e ) accuracy near the singular point. s However, we do expect that the S R M iteration would improve the accuracy and that we still expect to get 0(e ) accuracy away from the singular point. N u m e r i c a l s experiments i n Â§3.5 w i l l show such improvements. 3.5 Numerical Experiments We now present a few examples to demonstrate our claims i n the previous sections. Throughout this section we use a constant step size h. To make life difficult we choose h when we can so that there is an i such that t{ = t*, namely, there is a mesh point hitting the singularity point t*, for singular test problems. A t a given time t, we use 'ex' to denote the m a x i m u m over all components of the error i n x . Similarly, 'drift' s denotes the m a x i m u m residual i n the algebraic equations. E x a m p l e 3.3 Consider the DAE (2.16), (2.17) with f 9 Xl x<1 e 0. subject to a?i(0) = 1, Â£2(0) The exact solution is x e singularities. sin *). 2 2^ = (e -t s'mt), y e = e*. This is a problem without 76 Chapter 3. SRM for Nonlinear Problems Using an explicit second order Runge-Kutta method with h = 0.001 we test various choices of E and a (always taking a = 1) of the SRM formulation in Â§3.1. We list x 2 the computational results in Table 3.1. Observe that, for*ct\ / 0, the SRM works well methods Â«i = 1 E = I ai = 1 ' E = (GB) OL\ = 1 E = (GB)Baumgarte e le-8 iteration le-8 1 le-8 1 5e-3 1 1 T 1 ai = 0 E â€” I 2 3 4 Cii = 0 E = (GBf 5e-3 1 2 3 4 5e-3 Â«i = 0 E = (GB)' 1 1 2 3 4 error at â€”)â€¢ ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift ex drift t=.l .lle-7 .79e-8 .lle-7 .78e-8 .lle-7 .80e-8 .45e-6 .40e-6 .60e-2 .54e-2 .lle-3 .96e-4 .32e-5 .29e-5 .26e-6 .13e-6 .70e-2 .64e-2 .22e-3 .20e-3 .lle-4 .10e-4 .85e-6 .75e-6 .51e-2 .46e-2 .35e-4 .30e-4 .86e-6 .77e-6 .26e-6 .26e-7 t=.5 .94e-7 .56e-7 .92e-7 .53e-7 .95e-7 .58e-7 .16e-6 .70e-7 .lle-1 .80e-2 .26e-3 .20e-3 .65e-5 .47e-5 .23e-6 .51e-7 .12e-l .13e-l .65e-3 .49e-3 .16e-4 .10e-4 .91e-7 .77e-6 .66e-2 .49e-2 .lle-3 .79e-4 .23e-5 .17e-5 .18e-6 .31e-7 t=1.0 .19e-6 .14e-6 .18e-6 .14e-6 .19e-6 .15e-6' .35e-6 .29e-6 .lle-1 .13e-l .22e-3 .27e-3 .46e-5 .54e-5 .28e-6 .12e-6 .13e-l .15e-l .31e-3 .29e-3 .69e-5 .52e-5 .29e-6 .14e-6 .10e-l .12e-l .21e-3 .24e-3 .47e-5 .53e-5 .26e-6 .13e-6 Table 3.1: Errors for E x a m p l e 3.3 using the explicit second order R u n g e - K u t t a scheme for various choices of E. Its error is as good as Baumgarte's method whose parameter corresponds to the a 2 of the SRM. For ai = 0, we see that the error improves at a rate of about 0(e) for various choices of E, including E = I. (Observe the errors att = 1; the error situation near t = .1 is different because of an initial layer.) Such an error 77 Chapter 3. SRM for Nonlinear Problems improvement continues until the accuracy of the second order explicit Runge-Kutta method, i.e. 0(h ), is reached. â€¢ 2 T h e next two examples are problems with singularities. In the index-2 case of the Baumgarte stabilization the worst term is B(GB)~ g for the type of the singularities 1 t i n this paper. To show what happens when the Baumgarte method does not work well, we choose nonautonomous problems (i.e. g / 0) as index-2 singular examples. t E x a m p l e 3.4 Consider the nonlinear DAE (2.16) with \2t + (t> - Â±)e* J 9 = \{xl + \x ) 2 xl-(t- -f-(e-\f) l subject to the initial condition X i ( 0 ) = â€” |, Â£2(0) = â€” | . The exact solution is x e at t* = | . = (t â€” | , t â€” |), 2 y e = e*. A singularity is located Using this example we test the SRM formulations of Â§3.2. We list the computational results in Table 3.2, where we take h = e = 0.001 for the case of a,\ = 0, and h = 0.001, e = 1 0 - 1 0 for the case of Â« i 7^ 0, and use the explicit second order Runge-Kutta scheme to easily see the iteration improvement (Ij stands for results of the jth iteration). From Table 3.2, we see the error's deterioration for the Baumgarte method and the SRM with a.i ^ 0. The SRM with a.\ = 0 performs better in the singular case. â€¢ Next we t r y an example i n which y is unbounded at the singularity. E x a m p l e 3.5 Consider the nonlinear DAE (3.1) with ^ g = ^ - z i + x - s i n ( < ) - ( l + 2*)j 2 x\-\- #i (#2 â€” sin(t) â€” 1 + 2t), ^ ^ 0 j Chapter 3. SRM for Nonlinear Problems methods ai = 1 error at â€”â€¢) ex drift ex a i = 0 (11) drift ex a i = 0 (12) drift ex a i = 0 (13) drift ex a i = 0 (14) drift Baumgarte ex drift t=.l .39e-6 .24e-6 .46e-3 .24e-3 .81e-6 .24e-6 .23e-6 .90e-9 .23e-6 .47e-ll .43e-6 .24e-6 78 t = .5 .12e-3 .10e-7 .43e-4 .18e-8 .41e-5 .15e-10 .34e-6 .78e-13 .36e-6 .10e-12 .34e-3 .61e-7 t = .3 .13e-5 .16e-6 .32e-3 .89e-4 .lle-5 .30e-6 .26e-6 .lle-8 .26e-6 .33e-ll .45e-6 .16e-6 t = .7 .14e-3 .39e-6 .49e-3 .20e-3 .29e-5 .13e-5 .29e-6 .35e-8 .27e-6 .29e-ll .39e-3 .24e-6 t = 1.0 .V6e-4 .75e-6 .20e-2 .22e-2 .68e-5 .76e-5 .29e-6 .18e-7 .29e-6 .28e-10 .21e-3 .75e-6 Table 3.2 E x a m p l e 3.4 - boun ded y and singularity at t* = .5 subject to the initial condition xi(0) = 1, Â£2(0) = 0. The exact solution is x e = ( 1 â€” 2t, s'mt), y e = â€” c o s Â£ / ( l â€” 2t). Taking the same parameters and using the same method as before, we get the results listed in Table 3.3. Clearly, the SRM with ct\ = 0 performs well for this situation, while methods SRM ( = 0) (13) Baumgarte a i error at â€”> ex drift ex drift t=.l .40e-6 .25e-8 .49e-7 .39e-7 t = .3 .25e-6 .76e-9 .15e-6 .59e-7 t = .5 .14e-6 .16e-15 .93e+l .52e+13 t = .7 .46e-7 .28e-9 NaN NaN t = 1.0 .60e-7 .40e-9 NaN NaN Table 3.3: E x a m p l e 3.5 - unbounded y and singularity at t* = .5 Baumgarte method blows up upon hitting the singularity. â€¢ Our next example tests the formulation (3.33)-(3.35) or (3.44)-(3.45) for index-3 problems. E x a m p l e 3.6 This example is made up from Example 2 in [9] (see Figure 3.1), which describes a two-link planar robotic system. We.use the notation of (1.11). Let 79 Chapter 3. SRM for Nonlinear Problems (*i> yi) fa, y?) Figure 3.1: Two-link planar robotic system q= (#1, 8 ) and T 2 + m (l\ + / / 3 + kl c ) m (l /3 + hl c /2) 2 2 2 2 2 2 2 2 2 M = \ m (lH3 + hl c l2) 2 2 m l\j3 2 2 ) where li = l = 1, m\ = m = 3 and c = cos 6 . The constraint equation is 2 2 2 2 g{q) = h sin 0i' + l sm(8 + 8 ) = 0. 2 t 2 We choose the force term (Ii cos 9i + l cos(^! + #2)) cos t â€” 3 sin t 2 f = l cos(#! + O2) c o s 2 t-+ (1 â€” | 2) sin Â£ c which yields the exact solution 8^ = s'mt, 8 = â€” 2 s i n t and A = cost. Because M is 2 (symmetric) positive definite and B = M~ G l (3.44)~(3-45)- T -we can take E = I in the SRM formula Again we use the second- order explicit Runge-Kutta scheme, and set h = 0.001, e = 0.005. The results are listed in Table 3.4, where eq and ev stand for maximum errors in q and v = q', resp., and pdrift and vdrift stand for drifts at the Chapter 3. SRM for Nonlinear Problems 80 position and velocity level, resp. We see that the accuracy is improved significantly by the first two iterations. The third iteration is unnecessary here, because the error is already dominated by the Runge-Kutta discretization error. Qualitatively similar results are obtained for E = (GB) T and E = (GB)' . 1 E = I we neither form nor invert GM~ G , X More interestingly, though, for so a particularly inexpensive iteration T is obtained. methods E = 1 e 5e-3 iteration 1 2 3 error at â€”>â€¢ eq ev pdrift vdrift eq ev pdrift vdrift eq ev pdrift vdrift t=.l .41e-4 .75e-2 .22e-4 .49e-2 .13e-6 .19e-5 .42e-9 .91e-7 .10e-6 .86e-6 .96e-ll .10e-8 t=.5 .66e-3 .74e-2 .28e-4 .41e-2 .66e-6 .81e-6 .13e-7 .21e-5 .58e-6 .10e-5 .60e-9 .99e-7 t=1.0 .26e-2 .69e-2 .'22e-4 .27e-2 .36e-6 .20e-4 .17e-6 .21e-4 .12e-5 .16e-5 .48e-8 .59e-6 Table 3.4: Errors for E x a m p l e 3.6 using S R M (3.45)-(3.46) â€¢ Next we solve for the dynamics of the slider-crank mechanism described i n E x a m ple 2.1. this is a nonlinear index-3 D A E w i t h isolated, "smooth" singularities. E x a m p l e 3.7 We take h = e = 0.0001 and use the explicit second order Runge- Kutta method again. Singularities are located at (<f>i,<f>2) = (f>^f) (i-e-, each time the periodic solution passes this point). Corresponding to the case shown in [94], we choose </>i(0) = -f and </>i(0) = 0 and compute 7 6i = </>!- y , 0 = cf> + - , 2 2 9[ and 9' . Using the formulation (3.47), (3-46), we calculate until t = 70 without any 2 difficulty (see Figure 3.2). 81 Chapter 3. SRM for Nonlinear Problems 0 10 20 30 40 50 60 70 Figure 3.2: Solution for slider-crank problem w i t h singularities We also list the drift improvement as a function of the SRM iteration in Table 3.5. iteration number I 2 position drift at t=30 .669e-8 .730e-ll velocity drift at t = 30 .b71e-4 .731e-7 Table 3.5: Drifts of the S R M for the slider-crank problem // we use the SRM formulations considered in Â§Â§5.5 and 3.4 for problems withour singularities, or one of the usual stabilization methods with strict tolerances, the results become wildly different from the correct solution after several periods. Next we calculate the acceleration of the slider end in the horizontal direction under the initial data (j>i(0) â€” \ and (p[(0) = 2\/2. The same problem was discussed in [19]. The result shown in [19] is not perfect since the maximum and minimum values in each period appear to differ. Our result looks better (see Figure 3.3). â€¢ Chapter 3. SRM for Nonlinear Problems Figure 3.3: Acceleration of slider end Chapter 4 S R M for the N o n s t a t i o n a r y Incompressible N a v i e r - S t o k e s E q u a t i o n s 4.1 D A E M e t h o d s for Navier-Stokes E q u a t i o n s W h i l e a significant body of knowledge about the theory and numerical methods for D A E s has been accumulated, not much has been extended to partial differentialalgebraic equations ( P D A E s ) . T h e incompressible Navier-Stokes equations form, i n fact, an example of a P D A E : to recall, these equations read u + (u â€¢ grad)u = jiAu â€” gradp + f, (4.1a) divu = 0, (4.1b) = b , u| t u\ da t = 0 = a, (4.1c) i n a bounded two- or three-dimensional domain f i and the time interval 0 < t < T. Here u(x, t) represents the velocity of a viscous incompressible fluid, p(x, t) the pressure, f the prescribed external force, a(x) the prescribed initial velocity, and b(t) the prescribed velocity boundary values. T h e system (4.1) can be seen as a partial differential equation w i t h constraint (4.1b) w i t h respect to the time variable t. C o m paring w i t h the D A E form (3.1) p corresponds to y, the g r a d operator corresponds to the m a t r i x B and the div operator corresponds to the Jacobian m a t r i x G. It is easily verified that (4.1) has index-2 since the operator d i u g r a d = A (corresponding to the m a t r i x GB) is invertible (under appropriate boundary conditions). Indeed, the pressure-Poisson reformulation of (4.1) (see, e.g., [55]) corresponds to a direct index reduction of the P D A E , i.e. a differentiation of the constraint w i t h respect to t followed by substitution of u* from the momentum equations. 83 Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 84 In this chapter we propose and analyze a sequential regularization method ( S R M ) for solving the incompressible Navier-Stokes equations. T h e method is defined as follows: w i t h po(x,t) an initial guess, for s = 1,2, â€¢ â€¢ â€¢ , solve the problem e(u ) s t - g r a d ( a i ( ^ u u ) i + a divu ) + e(u â€¢ g r a d ) u = epAu - egradp _! + ef, (4.2a) u | a n = b, u | (4.2b) s s s - s s s s s p 2 s = a, t = 0 ps-i - ^(a (divu ) 1 s t + a divu ). 2 s (4.2c) This method is an extension of the S R M which was proposed and analyzed i n previous chapters for ordinary D A E s , especially for the index-2 D A E s (3.4), (3.5). Here we can take E = I even for ct\ = 0 because (4.1) corresponds to (3.1) w i t h B = G. T It is indicated i n Â§3.1 that i f we take a.\ ^ 0 then certain restrictions on choosing the i n i t i a l iterate (cf. ( 3.14)) do not apply and, more importantly, the equation for x s is essentially not stiff i f the original problem is not stiff. Hence, a non-stiff time integrator can be used for any regularization parameter e. For the Navier-Stokes application (4.2) we therefore choose ot.\ > 0 so that we can still take e to be very small even when we use an explicit time discretization. So one S R M iteration is often good enough. However, we should not ignore the choice ct\ = 0 because Â§3.1 also indicates that w i t h this choice the computation can be particularly simple. For (4.2), when a.\ > 0, although we use explicit time discretization, a symmetric positive definite system relevant to the discretization of the operator / + ^-grad div still needs to be inverted. If we take a.\ = 0, then we do not need to solve any system to obtain the discrete solution. In this case, (4.2) is not stiff only for relatively large e. So more than one S R M iterations are required generally. In the sequel, the convergence proof Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 85 and discretization stability analysis i n Â§4.3 and Â§4.4 are mainly for the case of cti > 0. T h e discussion for the case of a\ = 0 can essentially be carried out i n a similar way. We w i l l remark on this case i n Â§4.3 and Â§4.4 and provide a numerical verification i n Â§4.4. T h e importance of the treatment of the incompressibility constraint has long been recognized i n the Navier-Stokes context. A classical approach is the projec- tion method of [36], where one has to solve a Poisson equation for the pressure p w i t h the zero Neumann boundary conditions which is, however, non-physical. R e cently, a re-interpretation of the projection method i n the context of the so-called pressure stabilization methods, or more generally, "pseudo - compressibility methods" has been given i n [97]. Some convergence estimates for the pressure can be obtained (cf. [101, 96]). In his review paper [97], Rannacher lists some well known examples of "pseudo-compressibility methods" (which are actually regularization methods): divu + ept = 0 , i n ft x [0, T ) , p\t=o = Po, (artificial compressibility) divu + ep = 0, i n ft x [0, T ) , divu â€” eAp = 0 , i n ft x [0, T ) , (penalty method) f^|an = Po (pressure stabilization). If we generalize Baumgarte's stabilization to this P D A E example (4.1), we get u + (u â€¢ grad)u t = (divu) + j divu = t pAu â€” gradp + f, 0. (4.3a) (4.3b) E l i m i n a t i n g u from (4.3), we obtain an equation for p: t â€”Ap + jdivu â€” div{(u â€¢ grad)u â€” pAu â€” f} = 0. We then find that this stabilization can be seen as a k i n d of pressure stabilization w i t h 7 = e . A l t h o u g h it works, since we do not have a singularity here, it still sets - 1 up a non-physical boundary condition for the Poisson equation for p. Also, i n this formulation, equations for u and p are not uncoupled. Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 86 In the S R M formulation (4.2) we do not need to set up boundary conditions for p. So it should be more natural than various pressure-Poisson formulations. T h i s method relates to the idea of penalty methods but, unlike them, the regularized problems are not stiff for cti > 0 or less stiff for ct â€” 0 since we can choose e to be relatively x large. Hence, more convenient (nonstiff) methods can be used for time integration, and nonlinear terms can be treated easily. We w i l l indicate i n Â§4.4 that e has little to do w i t h the stability of the discretization there, i.e. the stability restriction is satisfied for a wide range of e for Â« i > 0. We also indicate there that, i n the case of small viscosity, the usual time step restrictions for the explicit schemes can be loosened. A similar procedure following [5] (Uzawa's iterative algorithm ) i n the framework of o p t i m i z a t i o n theory and economics has actually appeared i n the Navier-Stokes context for the stationary Stokes equations (i.e. without the nonlinear term and the time-dependent term i n (4.1)) w i t h c*i = 0 using the augmented Lagrangian idea, see Fortin and Glowinski [50]. (Also see [54] for a related discussion.) in their procedure, e p = e _ 1 _ 1 i n (4.2c) is replaced by a parameter p. Note that, T h e y prove that is approximately optimal. For the nonlinear case, they combine Uzawa's algorithm w i t h a linearization iteration. They claim convergence but find it hard to analyze the convergence rate because their analysis depends on the spectrum of an operator which is non-symmetric i n the nonlinear case. For the nonstationary case (4.1), the augmented Lagrangian method cannot be applied directly. Therefore, [50] first discretizes (4.1a) w i t h respect to the time t (an implicit scheme is used). T h e n the problem becomes a stationary one i n each time step. Hence, Uzawa's algorithm can be applied and converges i n each time step. So, for the nonstationary case, their iterative procedure is, i n essence, to provide a method to solve the time-discretized problem. Thus, their iterative procedure has little to do w i t h time-discretization, or i n other words, they still do time-discretization directly for the problem (4.1). Consequently an implicit scheme is always appropriate because of the constraints Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 87 (4.1b), and a linearization is always needed to treat the nonlinear case. These properties are not shared by our method. We w i l l prove that the convergence results of the S R M i n the previous chapter still hold for the P D A E case (4.2). Hence, the solution sequence of (4.2) converges to the solution of (4.1) w i t h the error estimate of 0(e ) s about 0(e). after the s t h iteration. Therefore, roughly speaking, the rate is W e prove the convergence results using the method of asymptotic ex- pansions which is independent of the optimization theory and is also applicable to the steady-state case. In addition, when the finite element method is used, the difficulty of constructing test functions i n a divergence-free space to decouple the u,p system can be avoided by using the formulation of the S R M . We indicate here that, as many others do, we include the viscosity parameter u in the error estimates. So the estimates could deteriorate when u is very small. T h i s is because we have an unresolved technical difficulty, associated w i t h our inability to obtain an appropriate upper bound for the nonlinear term and w i t h the weaker elliptic operator /J,AU (which is dissipative) as p â€”>â€¢ 0. In the S R M formulation, a supplementary dissipative term â€” ci2graddivu s is introduced without perturbing the solution. A s indicated i n [50] for the stationary case, the relative advantage of such methods may therefore become more apparent for small values of the viscosity. T h e chapter is organized as follows: In Â§4.2 we define some preliminaries and discuss regularity properties of the solution of (4.2). T h e convergence of the S R M for Navier-Stokes equations is proved i n Â§4.3. Finally, i n Â§4.4 a simple difference scheme is discussed and some numerical experiments are presented. These numerical experiments are only exploratory i n nature. To summarize, our objective i n this chapter is to present a method for the nonstationary Navier-Stokes equations from the viewpoint of D A E regularization, and to provide a way to apply a D A E method to P D A E s . It appears that such a formulation is new i n the Navier-Stokes context and it is worthwhile because: Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 88 â€¢ Since e need not be very small, the regularized problems i n the sequence (4.2) are more stable/less stiff. So more convenient difference schemes, e.g. explicit schemes i n time, can be used under theoretical assurance. If we take cxi > 0, this is also true for small e. â€¢ T h e problem of additional boundary conditions, which arises i n the pressurePoisson formulation and projection methods, does not arise here. F i n i t e element methods can be used easily and the elements do not have to conform to the incompressibility condition to separate the variables u and p. 4.2 P r e l i m i n a r i e s and the P r o p e r t i e s of the R e g u l a r i z e d P r o b l e m s Before we begin our analysis, we'first describe some notation and assumptions. A s usual, we use L ( H ) , or more simply L , to denote the space of functions which are P p pth-power integrable i n f i , and as its norm, where u = â€¢ â€¢ â€¢, i t ) . We denote the inner product i n L by (-, â€¢) and 2 n let || â€¢ || = || â€¢ | | . CÂ°Â° is the space of functions continuously differentiable any number 2 of times i n $7, and CÂ£Â° consists of those members of CÂ°Â° with compact support i n $7. H m is the completion i n the norm U H m = ( E \\D u\\')*. a 0<|a|<m We w i l l consider the boundary conditions to be homogeneous, i.e. b = 0 i n (4.1c), to simplify the analysis. Nevertheless, through the inclusion of a general forcing term, the results may be generalized to the case of nonhomogeneous boundary values. W e are interested i n the case that (4.1) has a unique solution and the solution belongs to H , where the arbitrary constant which the pressure p is up to is determined by 2 (4.4) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 89 Hence, some basic compatibility condition is assumed (cf. [63]): (4.5) a|an = 0, diva. = 0. Furthermore, we assume sup ||f || < M \\a\\ 2 < Mi u (4.6) H *6[0,T] where M i is a positive constant. We take po i n (4.2) satisfying (4.4). Hence, it is easy to see that p satisfies (4.4) s for all s. For simplicity, we only consider the two-dimensional case. We can treat the threedimensional case i n the same way, possibly with some more assumptions. Throughout the chapter M represents a generic constant which may depend on p as we have explained i n the introduction. We will also allow M to depend on the finite timeinterval T since we are not going to discuss very long time behavior i n this chapter. A t first, we write down some inequalities: â€¢ Poincare inequality: u|| < 7||grad u||, More generally (see [87]), for u Â£ if u | n = 0. (4.7) H (fl) l â€¢ Young's inequality: abc < -a p p + -b q q + -c r r (4.9) if a, 6, c > 0, p, q, r > 1 and ^i + i + i = l. p g r â€¢ Holder's inequality: (4.10) if p, q, r > 1 and ^ip +g Ir + i = l. Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 90 â€¢ Sobolev's inequality i n two-dimensional space: ||u|| <7*H*||gradu||*, (4.11) 4 where = 2 i f ft = R . 2 7 l Suppose that w stands for the difference of two solutions of the S R M (4.2). T h e n w satisfies the homogeneous problem (4.27) (see next section). Hence, using the estimate in L e m m a 4.2, uniqueness of the solution of the S R M (4.2) is easy to consider. T h e existence can be analyzed by following the standard existence argument for NavierStokes equations (e.g. [108, 62]) and that of penalized Navier-Stokes equations (e.g. [28]). Hence we assume the existence of the solution of the S R M and concentrate on the proof of the convergence of the method. Before we do so, we derive the following regularity results of the solution. L e m m a 4.1 For the solution { u , p } of (4-2) there exists a constant to such that s s when e < e we have the following estimates 0 KIIHI + [ (^r\\( s)t\\w Jo e < M[\H\w T dlvu z + [ T + ^T\\divu \\ t + ||(u ) || + | | A u | | + \\p \\ ) dt 2 2 s L s ul t 2 2 s a ( l l / l l + l l g r a d ^ U ) dt}. 2 Hi (4.12) 2 P r o o f : For simplicity of notation we denote u as v here. T h e proof for the case s a i = 0 is just the same as that i n [28]. So we only consider the case a > 0. Hence, x without loss of generality, we take Â« i = 1 and a = ot. We then write (4.2) as 2 \ t â€” -grad((diuv)i + adivv) + (v â€¢ g r a d ) v = JUAV - g r a d p _ i + f, (4.13a) v|an = 0, v | (4.13b) s i = 0 = a, p = ps-i â€”-((divv)t + adivv). s (4.13c) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 91 The proof follows the ideas i n [28]. M u l t i p l y i n g (4.13a) by v and integrating w i t h respect to the space variables on the domain 0 , we get - â€” llvll H -||dzuv|| -\ 2 2 lldzuvll + jullgrad vII 2 â€¢ grad)v, v) - ( g r a d p = -((v < f ll^vll + 2 le s 2 _i,v) + (f,v) ^||v|| ||gradv|| 2 2 la + ^||v|| + ^llgradp^H + %|| , 2 2 lj 2 n p where we use â€” ((v â€¢ grad)v, v) = |((rfiuv)v, v). Then let c = m i n ( " , ^ ) and Y = ||v|| + ^||rfzuv||. Using Poincare's inequality (4.7), we obtain 2 2 Â±Y + cY + \{u - ^F)||grad v|| < l(\\f|| + Hgradp^|| ). 2 at l (4.14) 2 2 a u Note that Y(0) = ||a||. Write (4.14) as 2 Â±(H at - ^Y) a - ^ | | g r a d v | | ( > - â€”Y) la a 3 > - ^ ( U g r a d p ^ ||2 + ||f||2). ua A p p l y i n g a standard technique for solving linear differential equations and taking e appropriately small ( < eo) so that ^ _ 1H (0) > Â£ and ?11Z f (||ff + llgradp,.!^ dt < T a Y pa Jo aa Jo I 4 we get P-â€” a n<)>7 4 Vt6[0,T]. (4.15) T h e n , using the same technique and (4.14), we have Y < ||a|| exp(-ct) + M e x p ( - c t ) / < M[||a|| + f (||f|| + llgradp.^H ) dz]. 2 (||f || + ||gradp _i|| )exp(cz) dz 2 2 s Jo 2 2 (4.16) 2 Jo Thus, (4.12) holds for ||u||. Integrating (4.14) directly and using (4.15) yields 2 f Jo ||gradu|| dz < M[||a|| + /* (||f|| + Ugradp^|| ) dz]. 2 2 2 Jo 2 (4.17) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 92 To prove other estimates for (4.12) we define the operator A w = â€” - g r a d ( ( d i u w ) + adiww) â€” pAw = g, t where w satisfies w | g n = 0 and w | = a. Let < = u q= (4-18) ((divw)t + adiww). T h e n we have (noting diww\ o = 0) t= â€”pAw + g r a d g = g, divw = â€”e Jo (4.19a) qexp(â€”a(t â€” z)) dz (4.19b) This is a general nonhomogeneous Stokes problem. Using the results described i n [28] (or cf. [108]), we get || A w | | + ||gradq|| < M[||g|| + e /* ||grad || exp(-a(< - z)) dz). Jo ? (4.20) A p p l y i n g Gronwall inequality, it is easy to obtain ||gradg|| < M(||g|| + e f ||grad || dz) Jo (4.21) g and /* ||grad || dz<M Jo 2 ? f ||g|| dz = M f* | | A w | | dz. Jo Jo 2 2 (4.22) It thus follows that | A w | | < M(||g|| + e f ||g|| dz) = M(\\Aw\\ + t T Jo Jo | | A w | | dz), (4.23) and then /" ||Aw|| Jo dz<M 2 f ||g|| dz = M f Jo Jo 2 | | A w | | dz. 2 (4.24) F r o m (4.19b) and (4.22), we thus have 1 f /' ||graddww|| dz = f ||gradg|| dz < M f ~7iJO Jo Jo l 2 2 | | A w | | dz. 2 (4.25) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 93 Then f 1 l / ||grad(>'uw) || dz < M [ e Jo Jo \\Aw\\ dz 2 (4.26) 2 t 2 follows from (4.18). Now taking the scalar product of (4.13a) w i t h Av, we have â€” \\(divv) \\ + â€” ^-\\divv\\ + -4-||grad vll 2 + | | A v | | 2e 2edt" 2 dt" 2 llv ; 2 t 11 11 & 11 11 2 11 = -((v â€¢ grad)v, A v ) - (gradp,_i, A v ) + (f, A v ) . Note that i i i â€” ((v â€¢ grad)v, A v ) < ||v||||grad v | | | | A v | | < 7* ||v|| = ||grad v | | | | A v | | 2 | | A v | | 4 4 < ^ ( | | A v | | + | | A v | | ) + jL(|| || ||gradv|| )||gradv|| 2 2 2 2 2 v < <S[||Av|| + M | | A v | | 2 2 2 + M e ( f 2 \\Av\\ dz) } + -^(||v|| ||grad v|| )||grad v||, 2 2 Jo 2 loo' 2 2 3 where we use (4.23) for the last inequality. Recall that we have estimates for | | v | | and /0* ||grad V|| dz. Therefore, taking 8(1 + M ) < | , it is not difficult to obtain 2 2 ||gradv|| + - / e Jo < \\(divv) \\ dz + 2 t Jo | | A v | | dz 2 M[||grada|| + /* (||f || + Hgradp^|| ) dz + e f 2 2 2 2 Jo Jo Taking e such that M e < 1, we then get (4.12) for / * | | A v | | 2 0 2 \\Av\\ dz] 2 dz and ||gradv||. N o t i n g (4.25), (4.26), from (4.2c), (4.12) also holds for /0* ||gradps||2 dz. A p p l y i n g the inequality (4.8) and noting that p satisfies (4.4), yields the bound for JQ \\p \\ dz. 2 s s Hence, from (4.2c) we can obtain (4.12) for J \\divv\\ dz and then / J ||(diuv)*|| dz. f 2 2 0 We thus complete the proof. â€¢ F r o m this l e m m a , we see that if we choose po such that J*Q ||gradpo||2 dz is bounded then, by induction, all terms i n the left of (4.12) are bounded for any given s. 2 Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 94 4.3 Convergence of the S R M In this section, we estimate the error of the S R M (4.2) i n the solution of (4.1) by using the asymptotic expansion technique as i n the proof of Theorem 2.1 of Chapter 2 (see Â§2.8). Note that, i n the Navier Stokes context, the asymptotic expansion method was used i n [54] to obtain a more precise estimate for a penalty method for the stationary Stokes equations and i n [108] to calculate a slightly compressible steady-state flow. We w i l l m a i n l y consider the case cx\ > 0. Hence, we take a.\ = 1 and a 2 convenience. = ex for T h e result for a\ = 0 w i l l be described i n Remark 4.3. A t first we discuss a couple of linear auxiliary problems. T h e n we go to the proof. 4.3.1 T w o linear a u x i l i a r y problems We discuss two linear problems i n this section. One is ew< â€” grad(rfiuw)i â€” agraddivw + e(w â€¢ g r a d ) U +e(V â€¢ grad)w â€” epAw â€” egradg + ef, (4.27a) w| (4.27b) 9 a = 0, w | i = 0 = 0, where U , V and q are given functions. T h e other is w t + ( V â€¢ grad)w + (w â€¢ g r a d ) V = pAw â€” gradp + / , (4.28a) (divw) + adivw = g, (4.28b) w | a = 0, w | (4.28c) t 9 t = 0 = a, where V , g and a are given functions, a satisfies the compatibility conditions (4.5) and g satisfies (4.4). Now we show some properties of these two problems which w i l l be used later i n the proof of the convergence of S R M . L e m m a 4.2 For the solution of problem (4-27), z ' / U and V satisfy II â€¢ l l + f T H 1 Jo I I â€¢ H H * dt < M , (4.29) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 95 then we have the following estimate e\\w\\ + | | d i v w | | < M e / * (||f || + || || ) ds, Jo 2 2 2 2 ? e||gradw|| 2 + / * (e||w,|| + ||divwÂ«|| ) ds < Me f (||f|| + | | | | ) ds. Jo Jo 2 2 2 2 g (4.30a) (4.30b) P r o o f : M u l t i p l y i n g (4.27a) by w and then integrating on the domain ft yields 1 d 1 d 2 <ft" " Â£ W 2 + 2<ft " * d W W " 2 + W W a divw 2 + e^l|gradw|| 2 = â€”e((w â€¢ g r a d ) U , w ) â€” e((V â€¢ g r a d ) w , w ) + e(q, divw) + e(f, w ) < e||gradU||||w|| + | | | A W | | | | w | | < e 2 i 2 7 l - + e(q, divw) + e(f, w ) (using (4.10)) 1 ( | | g r a d U | | + - | | d i u V | | ) | | w | | | | g r a d w | | + e(q,divw) + e ( f , w ) (using (4.11)) 1 < 2 Â£ 1 | | g r a d w | | + ^ ( | | g r a d U | | + - | | ^ w | | ) | | w | | + e(q, divw) + e(f, w ) , 2 e A i 2 2 where we have used â€” e((V â€¢ g r a d ) w , w ) = ^((divV)w, w). Therefore, we have ^(e||w|| 2 + \\divw\\ ) - C ( i ) ( e | | w | | + \\divw\\ ) < < - e / j | | g r a d w | | - ( a + C(t))\\divw\\ + 2e(q, divw) + 2e(f, w ) - e ^ | | g r a d w | | + e ^/f_,, | | w | |M2+, _4 7- | | f, i||2 +, e. -! | ' - < 2 2 2 2 2 2 2 7i/2Z 2 Â£ l l r 2 112 \i a e^||f|| + ei|| || ,. 2 (4.31) 2 ji g a where J T T I I ^niN2 C7(t) = 7l - ^ (n| i| g r a d U | | +, -n| j|, ^. . V ||) 1 N o t i n g that w | t = 0 = 0 and divw\ t=0 = 0, we thus get (4.30a). Now, m u l t i p l y i n g (4.27) by w , then integrating with respect to x over ft, we get t e | | w | | + H ^ u w i l l + ^J \\ â„¢\? 2 2 div t t + e/"^l|gradw|| 2 = e((w â€¢ g r a d ) U , w ) + e((V â€¢ g r a d ) w , w ) + e(q, divw ) + e(f, w ) . t t t t (4.32) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 96 We use the inequalities listed i n the previous section to estimate the right-hand side of (4.32) and have the following: e((w-grad)U,Wi) < ^ | | w | | + M e ( | | g r a d w | | + ||w|| ), e((V â€¢ grad)w, w ) < -||w || + Mesup |V| ||gradw|| , . 4 n c(f,wÂ«) < |||wÂ«|| + Me||f|| , e(q,divw ) < -\\divw \\ t t 2 2 2 t 2 2 2 t 2 a + Me||g|| , 2 2 t where the bounds of s u p | U | and s u p | V | can be obtained by using the inequality n n sup | â€¢ | < M\\A â€¢ || a (see, e.g. [119]). T h e n , similarly to the procedure for obtaining (4.30a), we obtain (4.30b). â€¢ Next we consider problem (4.28). L e m m a 4.3 There exists a solution for problem (4-28). Moreover, for the solution of (4-28), we have the following estimate: rT W if So" ||f l| 2 dt and J T 0 / ( H w H k + Hw.ll Hfirll^i dt are bounded. IHI + Jo 2 + \\p\\ ) dt<M (4.33) 2 m P r o o f : F i r s t , we can solve divw from (4.28b) (noting that divw\ t=Q = 0): divw ~ gi, (4.34) gi = exp(â€”at) / gexp(as)ds Jo (4.35) where satisfies (4.4) since g does. B y applying Corollary 2.4 i n [54, p.23], the problem divw = pi, (4.36a) w\ 0 (4.36b) da = Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 97 has many solutions. We pick one and denote i t as w . T h e n w := w â€” w p p satisfies the linearized Navier-Stokes equations i n the form of (4.28a) w i t h a proper force t e r m (denoted by f) and divw = 0, w|an = 0 and w | B y noting that divw \ p t=0 < = 0 = a- w\ . p t=0 = gi\t=o = 0, the basic compatibility conditions like (4.5) for w are satisfied. F r o m (4.35) and the assumption for g, J* (U^iH^i T 0 + ||(<?i)<||) dt is 2 bounded. Hence, based on the estimates for the solution of (4.36) (see [1] a n d [54]), it is not difficult to get IK||HI + Thus JQ ||f|| 2 dt is bounded. [ (||(w ),|| + \\w \\ ) dt < M. Jo 2 T 2 p p n2 (4.37) Simulating the regularity argument of [62] or [63] (multiplying the linearized Navier-Stokes equations by w , w and P A w where P is t a projection operator (cf. [62]), respectively), we can obtain ||w|| i H + [ Jo T + llwiH 2 + \\p\\w) dt < M. (4.38) Therefore, (4.33) follows from (4.37) and (4.38). Using the estimate (4.38) and following a global existence argument (e.g. [62] or [108]), the existence of the solution for w can be obtained. We thus have the results of the l e m m a . â€¢ R e m a r k 4.1 The uniqueness of the solution of (4-28) follows from the standard argument for Navier-Stokes equations (cf. [108]). â€¢ 4.3.2 T h e error estimate of S R M In this section we prove the convergence of iteration (4.2) based on the same procedure described i n the proof of Theorem 2.1 of Chapter 2 (see Â§2.8) . We describe our results in the following theorem. Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 98 T h e o r e m 4.1 Let u and p be the solution of problem (4-1), a n d u s and p s be the solution of problem (4-2) at the sth iteration. Then there exists a constant eo such that when e < e we have the following error estimates for all t Â£ [0, T]: 0 ||u-u,|| i H (/ Jo \\p - \\ 2 Pa dt)* < Me , (4.39a) < Me% (4.39b) s where T is any given finite number and s = 1,2, â€¢ â€¢ â€¢. P r o o f : A t first, consider the case s = 1 of (4.2). Let Ui = uio + e u H he u H m n lm Comparing the coefficients of like powers of e, we thus have grad((<fo'uuio)t + adivu ) = 0, grad((efo'uun) + adivuu) = [u )t + (u + gradpo - f, w t -pAu w (4.40a) w w â€¢ grad)ui 0 (4.40b) i - l grad((dzuui,-) + adivu ) t u -pAuu-i = (ui,-_i) + E ( i i ' grad)ui,-_i_j , 2 < i < m + 1, u t (4.40c) where (4.40a) satisfies (4.2b) and (4.40b) and (4.40c) satisfy the homogeneous i n i t i a l and boundary conditions corresponding to (4.2b). Now (4.40a) has infinitely many solutions i n general. W e should choose Ui not only to satisfy (4.40a) but also to 0 ensure that the solution of (4.40b) exists. A choice of Uio is the exact solution u of (4.1), i.e. (uio)t + (uio â€¢ g r a d ) u (div\i ) w t = ^ A u i o - gradp + f, 1 0 + adivuio = 0, uiolsn = 0, u 1 0 | < = 0 = a. (4.41a) (4.41b) (4.41c) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 99 Note that divu \ = diva. = 0 and p is taken to satisfy (4.4). So u w t=0 1 0 = u and (4.40b) has the form grad((divu ) n + adivu ) t n â€” grad(p - ?)â€¢ (4.42) 0 Now we choose U n and a corresponding p\\ to satisfy (un)i + (uio â€¢ grad)un + (un â€¢ grad)uio = ^ A u - gradpu, (4.43a) (diuunjt + adivuw = p â€” p, (4.43b) unlsn = 0, u n | (4.43c) n 0 = 0. t = 0 A g a i n we have divun\ -o = 0 and let pn satisfy (4.4). According to L e m m a 4.3, Un t and pn exist . Generally, supposing we have Ui;_i, pu-i for i > 2, choose Ui;, pu satisfying (uii)i + (mo â€¢ grad)uii + ( u - â€¢ g r a d ) u u 10 i-l = uAu - u gradp - ^ ( u j j â€¢ grad)ui,_i_ , (4.44a) (divuu) + adivuu = â€”pu-i, (4.44b) ui.-lan = 0, u i , - | (4.44c) lt J t t = 0 = 0, where we note that divuu\ =o = 0 and pu satisfies (4.4). A p p l y i n g L e m m a 4.3, all t uu and pu, i = 0,1, â€¢ â€¢ â€¢, exist and satisfy (4.33). Next we estimate the remainder of the asymptotic expansion after the (m + l ) t h power of e. Denote ui m = uio + e u n + â€¢ â€¢ â€¢ + e ui m + 1 m + i (4.45) (vii also satisfies (4.33)) and m Wim = U i - U i . (4.46) m Then W i m satisfies e ( w ) - grad(dwwi ) l m t m t - agraddivw lm Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 100 +e(w â€¢ grad)uj + e ( u im Xm â€¢ grad)w i m = epAw lm - m+1 e m + 2 {(ui m + 1 )i + [(ui,- â€¢ g r a d ) u i i _ , - ] - , u A u i m + m + i}, (4.47a) t=0 wi | m 9 n = 0, w i | m Using regularity we have for Uu, i i i ||w || = 0 ( e lm m + 1 = 0. t = 0 (4.47b) and U i (see (4.12)) and L e m m a 4.2 , we obtain m ) and | | g r a d w | | = 0 ( e lm m + 1 ) . Therefore = uio + c u + â€¢ â€¢ â€¢ + e u + 0(e ). m U l u (4.48) m+1 l m in the H - n o r m for the spatial variables. Noting U i = u , we thus obtain 1 0 - u = 0(e). U l (4.49) Furthermore, according to L e m m a 4.2, we have ||^w l m | | = 0(e m + l), (f ||(dtt;w )t|| dt)* = 0 ( e T 2 lm m + l). Jo T h e n , by using (4.2c),(4.48),(4.41b), (4.43b), (4.44b) and the estimates for divw lm and ( & w l m ) ( , it follows that Pi = P + mi + â€¢ â€¢ â€¢ + e > i m + 0 ( e m + ") (4.50) or Pi -p= 0(e). (4.51) in the sense of the L - n o r m for both spatial and time variables, i.e. ( J 2 T 0 || â€¢ | | 2 dt)*. Now we look at the second iteration s â€” 2 of (4.2). Let u = u 2 2 0 + eu i H he u m 2 2 m H . N o t i n g that (4.50) gives us a series expansion for pi we obtain grad((cfem )t + adivu o) 20 2 = 0, (4.52a) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 101 grad((divu ) 21 = (u )t + (u o â€¢ grad)u + adivu ) t 21 2 20 -pAu + 20 20 (4.52b) gradp-f, i-l grad((divu ) 2i t + adivu ) = (u ,--i)t + J2( ^J â€”pAu i-i - gradpi,_i,2 < i < m + 1. 2t 2 U 2 " grad)u _i 2i (4.52c) A g a i n , (4.52a) is combined with the initial and boundary conditions (4.2b), and (4.52b) and (4.52c) are combined with the corresponding homogeneous ones. A s i n the case of s = 1, we again choose u o = u. We thus have 2 grad((fifo"uu i)t + adivu ) 2 â€” 0. 2i (4.53) T h e n u i is constructed to satisfy 2 (u i)i 2 + (u â€¢ grad)u i + (u â€¢ grad)u = ^^ 2i - gradp , u 2 20 21 (divvL2i)t + adivu 20 21 â€” 0, 21 (4.54b) u i | n = 0, u i|*=o = 0. 2 Obviously u 2i 9 (4.54a) (4.54c) 2 = 0 and p i = 0 is the solution of (4.54) and (4.4). 2 In general, similarly to the case of s = 1, we choose u;,p - to satisfy 2 24 (u ,-)t + (u â€¢ grad)u + (u â€¢ grad)u = 2 20 2j 2i 20 (4.55a) i-l - gradp ; - X!( 2J ' g pAu u r a d 2 2l (divu ) 2l t + adivu i = ) 2t-i-j, u -p i-i, 2 (4.55c) 2 u i|3n = 0, u '| o = 0 28 2 (4.55b) (4.55d) i= for 2 < i < m + 1, where p [ satisfies (4.4). B y the same procedure as for s = 1 2 we obtain error equations similar to (4.47) with the addition of a remainder term grad(pi â€” pirn) i n the right-hand side, where pi stands for the asymptotic expansion m (4.50) of pi. A p p l y i n g L e m m a 4.2 again, we get u =u 2 2 0 + eu + â€¢â€¢â€¢+ e u + 0(e ). m+1 m 2 1 2 m (4.56) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 102 N o t i n g u i = 0, 2 (4.57) u -u = 0(e ). 2 2 T h e n , using (4.2b),(4.56),(4.54b) and (4.55c), we conclude P2 = P + ep2i + â€¢â€¢â€¢ + e>2m + 0(e m + 2 (4.58) ) or p -p=0(e ). (4.59) 2 2 since p i = 0. 2 We can repeat this procedure, and, by induction for s (choosing m larger than s), conclude the results of the theorem. â€¢ R e m a r k 4.2 Corresponding to Theorem 2.1, we expect that the error estimates (4-39) also hold for the SRM (4-2) with cxi = 0, at least, away from t â€” 0. â€¢ R e m a r k 4.3 In Theorem 4-1, we find that the result for p is in a weaker norm lo II " l | dt. 2 This is because we have difficulty in estimating the first order time- derivative of the right-hand side of(4-47), or concretely, the term In [63] (Corollary 2.1) it is shown that / ||(ui i) || T 0 2 m+ tt / IKuim+i )Â«|| T 2 0 ds. ds may be unbounded ast â€”> 0 if we only assume the local compatibility conditions (4-5). In the case that this integral is bounded for 0 < t < T, we can get (4.60) Otherwise, we only can expect that (4-60) holds away from t = 0 by following the argument in [63]. â€¢ R e m a r k 4.4 Multiplying (4-27) by Aw, where A is the operator defined by (4-18), and following the later steps of the proof of Lemma 4-1, we can get Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 103 1 f f (\\grad(divw) \\ Jo T + a||gradrfz'uw|| ) dt 2 2 t <M / (||f|| Jo T 2 + ||gradg|| )^. 2 Using this result to estimate the remainders of the asymptotic solutions in the proof of Theorem J^.l, we obtain rT (/ Jo Wv-Psfm dt)* <Me . (4.61) s â€¢ 4.4 D i s c r e t i z a t i o n Issues a n d N u m e r i c a l E x p e r i m e n t s In previous sections, we have proposed the S R M and performed some basic analysis on i t . T h e S R M yields a sequence of P D E s which are to be solved numerically. T h e problem at the 5 t h iteration can be written as: e(u ) s t - g r a d ( a ( ^ ' u u ) + a divu ) = epAu + er , 1 s s 0,u | = dn 2 s + e(u â€¢ g r a d ) u s s s (4.62a) s s u\ i < = 0 = a, (4.62b) where r (t) is the known inhomogeneity s r = - g r a d p _ x + f. s (4.63) s A variational formulation of (4.62) gives: F i n d u G HQ such that s e-^-(u , 4>) + ^-^-(divUs, div<f>) + s +e/^(gradu ,grad0) + = a , s u | s i = o a (divu , 2 s divcf>) b(u , u , <f>) = e(r , 0), V0 â‚¬ HQ, (4.64a) s s s divu \ s t=o = 0, (4.64b) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 104 where the trilinear form v,w). 6(u,v,w) = (.(u â€¢ grad) F r o m (4.64) we see that the finite element method i n the spatial variables, combined w i t h time discretizations, can be easily adopted. Note that we do not need to construct divergence-free test functions to separate the variables u and p. Nevertheless, i n this section, we are not going to discuss finite element methods further. Some discussions on using the S R M with the finite element method w i l l be given i n the next chapter for a problem i n reservoir simulations. Some numerical experiments are also given there. Here we only consider a very simple first-order difference scheme (forward Euler scheme i n the time direction) i n two dimensional space, as an initial attempt towards the discretization of the sequential regularization method for the P D A E . Concretely, we consider a rectangular domain such that an equidistant mesh can be used. Let (u,v) stand for the approximation of u , and let k,h ,h T s x y denote step sizes i n time and spatial direction, respectively. W i t h o u t loss of generality, we assume that h = h = h and that the domain is a unit square. Thus, mesh points x y can be expressed as Xi = ih, i = 0,1, â€¢ â€¢ â€¢, / ; yj â€” jh,j = 0 , 1 , , â€¢ â€¢ â€¢, J ; t = rafc, n = 0,1, â€¢ â€¢ â€¢, N, N = [T/k]. n The difference scheme reads: (4.65a) + + l{'U'x (x y yy)i u (X2{Ux y + Uyy) (4.65b) u\an = 0, v\ n = 0, d (4.65c) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 105 where u Ui = h ity and My can be defined accordingly and the definitions for v are similar. Obviously, this is a first-order scheme explicit i n time, where the nonlinear term is discretized somewhat arbitrarily. T h e scheme is easy to implement. Next we discuss its stability. For simplicity, we analyze the linear case (corresponding to the Stokes equations) first, and consider the full nonlinear equations (4.65) i n Remark 4.7 below. W e write the linear case of (4.65) as follows : euj â€” cci(u + Vy )i = a (u xx ev{ - ai(u xy X + Uy )i = y u\aa = 0, u | n = 0, 9 2 + U y ) + e/i(u xx + Uyy) + xx X (4.66a) CV2(U y + Uyy) + Cp(V + Vyy) + &T y , X (4.66b) XX u\t=o = a , v\ u t=0 = a. (4.66c) v Here we take a.i â€” 1 and a = a. T h e result for the case of a.\ = 0 w i l l be given i n 2 Remark 4.6. The following theorem gives the stability estimate for (4.66) i n the sense of the discrete L - n o r m : 2 t'=0 j=0 where w h = (tOj,j), i = 0,1, â€¢ â€¢ â€¢ , / . â€” 1, i = 0,1, â€¢ â€¢ â€¢ , J â€” 1. T h e o r e m 4.2 Let u anc? v be the solution of (4-66) and A = e(||u|| + \\v\\l) + \\u + vy\\l + ep(\\u \\ + \\uy\\ + \\v \\ 2 2 s x 2 h 2 h x + \\v \\ ). 2 h y (4.68) Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 106 If f r < 1 â€” > where c is any constant in (0,1), then c A + kJ^ \\(u + v )i\\l<Me maxJ\\r \\ + \\r \\l) 2 g s u â€ž v h (4.69) U<vl <vi n n=U - - where M is a generic constant dependent on p and c. Proof: W e first write down the following identities and inequalities: â€¢ some difference identities [75]: (#)* = <ft/>* + (<fÂ»p)i = (4.70a) < M Â£ V , Wi + feEfy, (4.70b) 2M>i = (Wi-kfay, c . (4.70 4>4> (4.70d) = xx (dHf>i) - (<fe) , 2 s where the translation operator E (p(x,y,t) = (f>(x + ih,y,t). l x â€¢ an difference inequality [75]: Wx|U<2|HU (4-71) â€¢ a discrete version of the Poincare inequality (cf. [66]): U\\l<U4l + Uv\\l (4-72) if <p satisfies homogeneous boundary conditions. M u l t i p l y i n g (4.66a) by au-\-bui and (4.66b) by av + bv^ and adding, then summing for a l l ( i , j ) , i = 1, â€” 1, j = 1, â€¢ â€¢ â€¢, J â€” 1 where we use the difference identities (4.70) (omitting lots of tedious algebraic manipulations), we obtain Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 107 (\\ \\l + \\ \\l)i + o ( Â« 6 + a)(\\u + ea u v s +e(b - aA:)(||M^||^ + 2 2 h x + h + \\uy\\ + \\v \\ 2 x 2 2 h -epb(\\u \\ \\vi\\ ) + aa\\u + v \\ +eu.a(\\u \\ + \\uy\\ + x vy\\l)i + v 2 h x \\ugi\H 2 2 v 2 h s xi h \\vy\\ )i + (b - ^(ba + a)k)\\(u + Vy)i\\ - ^epbk(\\u \\ + 2 h 2 h h + \\v \\ 2 xi < Me{\\r \\ + \\r \\ ) + \epa(\\u\\ + \\v\\ ) + ^eb5(\\ \\ u + 2 h 2 2 h 2 h Ui h + \\Vyi\\ ) 2 h h + |H| ), 2 h where 5 > 0 can be chosen less than c/b. A p p l y i n g (4.71) and (4.72), we get h\{\\u \\ 2 xi + \\u \\ + \\v- \\ 2 h yi 2 h xi + \\VyiWl) < 4 ( | | n | | + \\vi\\l) 2 h i and + \Ml < \\U \\1 S + \\Uy\\ 2 + \\V4 2 + \\Vy\\l, respectively. T h e n we can choose a and b such that k 1 1 b- ak - pâ€” - -bS > 0, b - -(ba + a)k > 0 n 2 2 2 and obtain {A)i + depA + \\(u + x Vy)i\\l < Me(\\r \\ 2 u + \\r \\ ), 2 h v where d is a constant independent of k, h, e and /J,. F r o m this inequality, it is not difficult to see that (4.69) holds. â€¢ Remark 4 . 5 From (4-69) of Theorem 4-2, we find that the value of e will not affect the stability of the difference scheme. This means that the forward Euler scheme in the time direction works for any value of e. Also, the time step restriction k < (1 â€” c)h /u. 2 is actually loosened in the case of small viscosity (or large Reynolds number) which people are often interested in. This implies that the explicit scheme (4-66) to which an appropriate discretization of the nonlinear term (see the next remark) is added works very well. It enables us not only to avoid the complicated iteration procedure for nonlinear equations but also to choose the time step fairly widely in the case of small viscosity. â€¢ Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 108 R e m a r k 4.6 We have mentioned before that sometimes we may like to take a.\ = 0 to avoid solving any algebraic system. Following the same procedure as the proof of Theorem 4-2, we can get the stability condition for the case of cx\ = 0. k < meh , where m is a positive constant independent of e,h and p. 2 That is, We thus see that the stability of (4-66) with a.\ = 0 depends on the parameter e. This coincides with our experience with stiff problems discretized by explicit schemes. Fortunately, using the SRM, we do not need to take e very small. So the time step restriction is not much worse than the usual one corresponding to an explicit scheme applied to a non-stiff problem. â€¢ R e m a r k 4.7 For the nonlinear case (4-65), when the viscosity p is not small, we expect similar results since the nonlinear term can be dominated by the viscous term. When the viscosity is small, however, the scheme (4-65) is unstable. Although numerical computations indicate that we do get better stability if we increase a , i.e. some 2 kind of dissipation effect is obtained (we must note that such dissipation becomes small when the incompressibility condition is close to being satisfied), we suggest using spatial discretizations with better stability properties, e.g. upwinding schemes (cf. [102]), in the case of small viscosity. â€¢ R e m a r k 4.8 Applying corresponding difference identities for a nonuniform mesh (see e.g. [106]), the results of Theorem 4-2 may be generalized to difference schemes (4-66) on a nonuniform mesh. Hence, the difference scheme may be used for problems defined on more general domains. â€¢ Next we explain our theoretical results by calculating the solution of an artificial example. E x a m p l e 4.1 Consider the Navier-Stokes equations (4-1) with the exact solution Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 109 u = (u,v) T u = v = P = 5 0 Â£ ( l - x ) j / ( l - y ) ( l - 2 y ) [ l + exp(-t)], 2 2 -50y (l-y) x(l-x)(l-2a;)[l+exp(-t)], 2 2 [ - x ( |+ 2 ) - y ( | - 2 ) + ^][l + e x H ) ] 2 P As indicated in Â§2.6 of Chapter 2, to carry out the SRM iterations, we do not need to store the entire approximation of p -i s on [0,T] for calculating u . Assuming s that the number of the SRM iterations is chosen in advance, we can rearrange the computational order to make the storage requirements independent of N, where N represents the number of the mesh lines in the t direction. We first use constant steps k = 0.01 and h = 0.1. At a given time t, we use ' e u ' to denote the absolute discrete L -error in u 2 while ep' denotes the absolute discrete L -error in p . Table l s 2 s 4-1 summarizes the computational results of the difference scheme (4-65) with Q i = Q 2 = 1 and viscosity f.i = 0.1. e 5e-l iteration 1 2 3 le-3 1 error at â€”â€¢ eu ep eu ep eu ep eu ep t = k 4.65e-3 2.49e-l 2.16e-3 1.80e-l 2.15e-3 1.80e-l 2.14e-3 1.80e-l t = 1.0 2.69e-l 1.96e-l 2.53e-2 9.28e-2 1.77e-2 8.81e-2 1.73e-2 8.78e-2 t = 2.0 1.55e-l 1.57e-l 3.12e-2 7.37e-2 2.28e-2 6.69e-2 2.21e-2 6.61e-2 t = 3.0 1.31e-l 1.36e-l 3.18e-2 6.74e-2 2.48e-2 6.10e-2 2.41e-2 6.01e-2 t = 4.0 1.15e-l 1.25e-l 3.12e-2 6.48e-2 2.55e-2 5.91e-2 2.48e-2 5.82e-2 t = 5.0 l.U8e-l 1.21e-l 3.06e-2 6.35e-2 2.57e-2 5.83e-2 2.50e-2 5.75e-2 Table 4.1: S R M errors for p = 0.1 without upwinding We notice that the errors improve as the iteration proceeds until e reaches the s discretization accuracy 0(h), where s is the number of iterations. For small viscosity, say p = 0.001, the difference scheme (4-65) does not work. The errors blow up around t = 1. When we increase a , say to 50, we do get pretty 2 good results around t = 1; however, the errors still blow up at a later time. This Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 110 suggests that the scheme is not stable for small viscosity p. So we next discretize the nonlinear term using the upwinding scheme given in [102]. For the case of small viscosity, e.g. p = 0.001, we get good results (see Table \.2). e 5e~I iteration 1 2 3 1 le-3 error at â€”}â€¢ eu ep eu ep eu ep eu ep t =k 4.bbe-3 2.58e-l 2.16e-3 1.84e-l 2.14e-3 1.83e-l 2.14e-3 1.83e-l t = 1.0 2.26e-I 1.06e-l 7.74e-2 8.81e-2 7.69e-2 8.78e-2 7.69e-2 8.78e-2 t = 2.0 2.50e-l 6.67e-2 8.78e-2 6.22e-2 8.71e-2 6.21e-2 8.72e-2 6.21e-2 t = 3.0 2.29e-l 5.45e-2 9.13e-2 5.39e-2 9.06e-2 5.39e-2 9.07e-2 5.39e-2 t = 4.0 2.13e-l 5.12e-2 9.34e-2 5.11e-2 9.29e-2 5.11e-2 9.29e-2 5.11e-2 t = 5.0 2.03e-l 5.04e-2 9.53e-2 5.02e-2 9.48e-2 5.01e-2 9.49e-2 5.01e-2 Table 4.2: S R M errors for p = 0.001 w i t h upwinding Recall that according to Remark 4-5, in the case of small viscosity, the time step size can be increased to some extent without adverse stability effects. To demonstrate this, we take k = h = 0.1, and p = 0.001. The numerical results in Table 4-3 support our claim. e Ie-3 iteration 1 error at â€”5â€¢ eu ep t =k 2.18e-2 1.83e-l t = 1.0 8.61e-2 8.83e-2 t = 2.0 9.43e-2 6.26e-2 t = 3.0 9.70e-2 5.42e-2 t = 4.0 9.86e-2 5.13e-2 t = 5.0 9.99e-2 5.03e-2 Table 4.3: S R M errors for p = 0.001 w i t h a pretty large time step k = h = 0.1 Although we use explicit schemes for SRM (4-2) with a\ > 0, we still have to solve a banded symmetric positive definite system. An alternative is to take cti = 0 to avoid solving any algebraic systems. Table 4-4 shows the computational results of the difference scheme (4-65) with cx = 0 and a x 2 â€” 1. We take viscosity p = 0.1, h = 0.1 and k = 0.0005. Good results are obtained except for the pressure near t = 0 (cf. Remark 4-4) â€¢ Chapter 4. SRM for the Nonstationary Incompressible Navier-Stokes Equations 111 e 5e-l iteration 2 error at -> eu ep t = k 5.b4e-3 2.92e-0 t = 1.0 3.57e-2 9.70e-2 Table 4.4: S R M errors for p t = 2.0 2.94e-2 7.03e-2 t = 3.0 2.7Ie-2 6.17e-2 0.1 w i t h = 0 t = 4.0 2.62e-2 5.87e-2 t = 5.0 2.60e-2 5.77e-2 Chapter 5 S R M for the S i m u l a t i o n of M i s c i b l e D i s p l a c e m e n t i n Porous M e d i a 5.1 Introduction As explained i n Chapter 1, miscible displacement occurs i n the tertiary oil-recovery process which can enhance hydrocarbon recovery i n the petroleum reservoir. Numerical simulation plays an important role for this process because solvents (or chemicals) are expensive and experiments are hardly possible. Mathematically, misci- ble displacement i n porous media is modeled by a nonlinear coupled system of the pressure-velocity equation and the concentration equation w i t h appropriate boundary and initial conditions. The pressure-velocity equation is elliptic, while the concentration equation is parabolic, but normally convection-dominated. A c c u r a c y for velocity approximation is important to obtain a good approximation for concentration since the concentration equation only includes the velocity variable. M i x e d finite element methods for the pressure-velocity equation have been applied for this purpose [40, 41, 42, 46, 47, 120]. We are interested i n applying the idea of the S R M to this equation since it has benefits over mixed finite element methods. T h e S R M formulation for the pressure-velocity equation is a direct application of the sequential regularization method for time-dependent problems (see previous chapters). T h e velocity variable is involved i n the linear systems only and the pressure variable is obtained by substitutions (without solving any linear systems) at each iteration level. We notice that the same formulation can also be obtained from the augmented Lagrangian method (originated from Uzawa's algorithm) [50, 31]. U n l i k e 112 Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 113 the augmented Lagrangian method using spectral analysis to discuss the convergence rate for discretized problems, we use asymptotic, methods directly for the differential problems. T h e asymptotic method is easier to use for more general and more complicated problems than spectral analysis because the latter is scarcely possible for non-symmetric operators. We will later prove that our iterative schemes can improve the error to 0 ( e ) at the 5 t h iteration level, where e is a small positive number. In s other words, the convergence rate of our iterative procedure is about 0 ( e ) . Theoretical convergence analysis and numerical experiments show that the number of iterations is extremely small, usually 2. T h e organization of this chapter is as follows. In Â§5.2, we describe our S R M iteration for the time-discretized problem (the differential problem i n spatial variables) and its advantages. In Â§5.3, we show its convergence . T h e n i n Â§5.4 we give a fully-discretized scheme using the Galerkin finite element method for the problem formulation where the S R M is used for the pressure-velocity equation. Finally, i n Â§5.5, we present numerical examples to demonstrate the effectiveness and accuracy of our method. 5.2 S R M Formulation To recall, we again write down the model problem. Consider the miscible displacement of one incompressible fluid by another i n a porous reservoir (7 C R over a time period 2 [0, T ] . Let p(x,t) and u(x,t) denote the pressure and Darcy velocity of the fluid mixture, and let c be the concentration of the invading fluid. T h e n the mathematical model is a coupled nonlinear system of partial differential equations u = â€”a(gradp â€” 7 g r a d d ) , (x,t) 6 Q x [0,T], divu = q(x,t), [0,T], (x,t)eilx dc <f>a-- div(D(u)gradc) + u â€¢ g r a d e = g(c), (5.1a) (5.1b) (x,t) <G tt x [0,T], (5.1c) Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 114 w i t h the boundary conditions u n = 0, ( x , i ) G T x [0,T], D ( u ) g r a d c - n = 0, (x,t) (5.2a) G T x [0,T], (5.2b) and the i n i t i a l condition c(x, 0) = c ( x ) , 0 x G ft, (5.3) where a = a ( x , c) is the mobility of the fluid mixture (we w i l l later denote it as a(c)), 7 = 7(x,c) and <i(x) are the gravity and vertical coordinate (we w i l l later denote 7 as 7(c)), q is the imposed external rates of flow, </>(x) is the porosity of the rock, D is the coefficient of molecular diffusion and mechanical dispersion of one fluid into the other, g = g ( x , t, c) is a known linear function of c representing sources, and n is the exterior normal to the boundary F = <9ft. We assume that the mobility is bounded below and above by positive constants 0 < m 0 < a(c) < M 0, c and its gradient is bounded above by a positive constant. For existence of p, we assume that the mean value of q is zero and for uniqueness we suppose p has mean value zero. In recent years much attention has been devoted to the numerical simulation of this problem. In this chapter we are interested i n solving the velocity-pressure equation (5.1a)-(5.1b) using the idea of the S R M for the time-discretized problem. T h e method considered herein is a direct application of the sequential regularization method (see previous chapters but without the sense of regularization) and is closely related to the augmented Lagrangian method [50, 31] (without the augmented L a grangian framework). We w i l l analyze the method using the technique presented i n previous chapters, i n particular Chapter 3. These analyses give the convergence of the iterative procedure and its convergence rate at the same time. Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 115 After a time discretization, we obtain the following system for u and p at the current time step: (x, t) â‚¬ ft x [0, T], u = -a(c)(gradp - 7(c)gradd), divu = <?(x, t), where c ijeftx (x, (5.4a) [0, T], (5.4b) is an approximation of c assumed to be known. Taking e to be a small positive number, we replace the system (5.1a), (5.1b), (5.2a) by the following iterative method: for s = 1, 2, â€¢ â€¢ â€¢, find {u ,p } such that s a(c)~ u 1 s s grad(divu s â€” q) = -(gradp _x - 7(c)grado0, 8 u s n = 0, (x, t) G ft x [0, T ] , (5.5a) ( x , i ) â‚¬ r x [0,T], (5.5b) and p = s - ^(divu - q), a (x,t) G ft x [0,T], (5.6) where the i n i t i a l guess po is required to satisfy the zero mean value property: / podx â€” 0. Thus;p has mean value zero from (5.6) and (5.5b). We note that, by taking po = 0, \ each iteration is a k i n d of penalty method. s ' ti T h i s iterative procedure has the following salient features: 1. We solve a small system (5.5) for the velocity u , and obtain the pressure p from (5.6) directly. We w i l l show that the accuracy of such a method is 0(e ) s at the 5th iteration level. Note that the system (5.5) is well-posed since, unlike the usual penalty method, we need not take e very small. Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 116 2. T h e velocity-pressure equation was recently solved by the m i x e d finite element method [40, 41, 42, 46, 47, 120], i n which the discrete spaces for u and p need to satisfy the Babuska-Brezzi condition, and the resulting linear system has a nonpositive definite coefficient matrix. In our method, u and p are obtained from equations (5.5) and (5.6) separately, and compatibility conditions between the discrete spaces of u and p are not needed. Moreover, system (5.5) leads to a symmetric positive definite coefficient matrix. 3. W h e n the standard finite element method [38, 39, 44, 45, 48, 98, 99] is applied for the pressure equation, the velocity needs to be obtained by finite differencing the pressure variable, which gives less accuracy. Note that the accuracy of the approximate velocity is important, since the concentration equation involves the velocity only. T h e velocity i n our method is obtained directly, without finite differencing. 4. T h e discrete version of our S R M formulation (5.5)-(5.6) gives the same accuracy for the velocity as the m i x e d method and requires the solution of wellconditioned linear systems like Galerkin methods. Note that our numerical experiments w i l l show that a few (much less t h a n . 10) iterations are usually enough for our iterative procedure. 5.3 Convergence A n a l y s i s Before we begin our analysis, we first describe some notation to be used throughout the rest of the paper. A s i n Chapter 4, we use L (fl), p or simply L , to denote the p space of functions whose pth power is integrable i n f i , w i t h the norm Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 117 where u = p = 2. H m â€¢ â€¢ â€¢, u â€ž ) . W e w i l l omit the subscript p i n the n o r m notation when is the closure of C Â£ Â° ( 0 ) i n the norm H H - = ll^ll Â£ \0<|o;|<m â€¢ 2 / In addition, we define the divergence space H(div) = { w Â£ L (fl) 2 2 : divw Â£ L (fl)} 2 w i t h the following norm: |u|| (^)-(||u|| + ||^u|| )". 2 2 H We shall denote by (-, â€¢) and (â€¢, â€¢) the inner products i n Cl and on V, respectively. For a normed linear space B w i t h norm || â€¢ \\B and a sufficiently regular function g : [a, (3] â€”> B, we define \g\\i^([ ,p];B) a = ( / \\g{-,t)\\ Bdt)? \\9(;t)\\B<lt)* 2 a and n d ||flf||Loo( ^] B) = \\g\\L~(\a,l3];B) = TCT ; sup \\g(-,t)\\ . B a<t<(3 If [a, (3] = [0, T ] , we simplify the notation as ||<7||i,2(fl) and ||S'||L (B)J OO respectively. W e shall also denote generic constants by M and K , which may be different at different occurrences. Before stating our convergence theorem, we first give a lemma. L e m m a 5.1 There exists a unique solution {u,p} to the problem u = -a(c)(gradp - f ) , (x, t) Â£ ft x [0, T ] , (5.7a) divu = q, (x,t) Â£ tt x [0,T], (5.7b) u - n = 0, (x,t) Â£ T x [0,T], (5.7c) where p and q have mean value zero. Furthermore, there exits a constant Mi such that the following estimates hold: | | u | | ( ^ ) + \\p\\m < Mi[\\q\\ + ||f ||H(Â«Kâ€ž)], H Vt Â£ [0,T]. (5.8) Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 118 Proof: Substituting (5.7a) into (5.7b) and (5.7c) we see that p satisfies a Poisson equation w i t h N e u m a n n boundary condition â€” div(agradp) = q â€” div(af), P = at â€¢ n aâ€” d i n ft, on 1. f P an N o t i n g the zero mean value of p and using the standard results for the Poisson equation, we obtain the uniqueness and existence of p and the estimate \\p\\ < M [\\q\\ + ||f ||H(Â«Kâ€ž) + ||f ' n | | - i m H / 2 ( r ) ]â€¢ A n application of the trace inequality [54] (p.28) ||f â€¢ n | | - i / 2 H ( R ) < ||f\\H(div), Vf G H(div) leads to the inequality (5.8) for p. T h e n the existence, uniqueness and the estimate (5.8) for u follow directly. â€¢ We are now ready to describe our convergence theorem and prove it using a similar technique as Chapter 3. T h e o r e m 5.1 Let { u , p } be the solution of system (5.4a), (5.4b), and (5.2a) and {xisiPs} the solution of (5.5)-(5.6). Then we have ||u - u | | ( Â« H + a H \\p-Ps\W < ( M 1 M i Â£ )1bo â€¢5 = 1,2,---. Here M i is from Lemma 5.1 and we assume M\e < | . Proof: W e first consider the case s = 1 of (5.5)-(5.6). W r i t e (5.5a) and (5.6) as a ( c ) U i + gradpx = ^(cjgradd _ 1 div^ - q = e(p 0 p ). x (5.9) Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 119 T h e n subtracting equations (5.4a) and (5.4b), we have a ( c ) ( u i - u) + g r a d ( p i - p) = 0 (5.10a) div(ui â€” u) = e(p (5.10b) _ 1 pi). 0 Using L e m m a 5.1, we obtain ||ui - u\\ + \\p! -p\\ H{div) < Mit\\po -Pi\\. i H (5.11) W r i t i n g p â€” pi = po â€” p + p â€” pi, we immediately have 0 ||ui + Ibi -U||H(AÂ«) -P\\H> < \\Po ~P\\- l e (- ) 5 12 Now we look at the second iteration s = 2. A t first, we can get equations similar to (5.10a) and (5.10b): a ( c ) ( u - u) + g r a d ( p - p) = 0 (5.13a) div(u â€” u) = e(pi - p ). (5.13b) _ 1 2 2 2 2 A p p l y i n g L e m m a 5.1 again, we have ||u - u|| (rf,-â€ž) + ||P2 - p\\m < MitWpi - pad H 2 <M e(\\p -p\\ 1 1 + \\p -p\\). (5.14) 2 N o t i n g M\t < 1 and using the estimate of ||pi â€” p|| (see (5.12)), yield ||u 2 u|| (AÂ») + H ||P2 - p\\m < ( ) \\Po M 1 2 Mie ~ P\\- (- ) 5 15 We can repeat this procedure, and by induction, conclude the results of the theorem. â€¢ F r o m Theorem 5.1 we see that the convergence rate of our iterative scheme (5.5)(5.6) is about 0(e). This implies that the number of iterations needed to achieve a prescribed accuracy is very small. T h e fast convergence of our method makes it dramatically different from penalty-like methods. Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 120 5.4 T h e G a l e r k i n A p p r o x i m a t i o n a n d Its E r r o r E s t i m a t e s In this section, we approximate the velocity-pressure iterative scheme (5.5) and the concentration equation (5.1c) by using the standard Galerkin method. W e only provide a brief description about this approximation. More details are i n [82]. Let W = {w Â£ H(div) : w â€¢ n = 0 on T}. T h e variational form of (5.5) can be written into the following: find u : [0, T] â€”> W such that s ( a ( c ) u , w) Hâ€”(divu , divw) _1 s s = (p -i Hâ€”q, divw) + (7(c)grad<i, w), s Vw Â£ W . (5.16) T h e weak form of the concentration equation (5.1c) reads: find c : [0,T] â€”> H ( f i ) 1 such that (</Â»^,^) + ( D ( u ) g r a d , g r a d z ) + ( u - grade, z) = (g(c),z), J C (c(x, 0), z) = (co(x),z), Vz e ff^ft), (5.17) Vz Â£ H\n). (5.18) For h > 0 and an integer k > 0, with respect to the velocity-pressure equation, u we introduce finite element spaces W / i C W and Yh = {y : y = divw for w Â£ W ^ } associated w i t h a quasi-regular subdivision of ft into triangles or rectangles of diameter less than h . Similarly, we denote by Zh C i / ( f t ) the finite-dimensional space for 1 u the concentration equation w i t h grid size h and approximation index /. Assume that c the following approximation properties hold: inf | | w - w \ \ < Kh \\w\\ k i, inf \\div(w - w )\\ < i^^* (||w|| *+i + \\divw\\ k+i), inf w e W , k +1 h u H + (5.19) +1 h H H* - z \\ < Kh \\z\\ , , l +1 h c H +l z e H\n), H w â‚¬ W , (5.20) (5.21) zhÂ£Zh where K is a constant. T h e space W^, can be taken to be the vector part of the Raviart-Thomas [100] space of index fc, or Brezzi-Douglas-Marini [30] space of index k + 1. Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 121 G i v e n a partition of [0,T], 0 = t < ti < â€¢â€¢â€¢ < Â£jv = T , we denote J 0 [t ,t ],At n n+1 = t n n - Â£ , and At = m a x { A t } . Let {p ,u ,c } n+1 n n n n = and { P , U , C } be n n n n {p, u , c} and its approximation at time level t . We define our approximation scheme n at time t (n = 0 , 1 , 2 , â€¢ â€¢ â€¢) by the following. n S t e p 1: G i v e n C , find { U â€ž , P } Â£ ~Wh x ^ n a s n follows. Take the i n i t i a l guess P = 0. For s â€” 1, 2, â€¢ â€¢ â€¢ , iteratively obtain t j Â£ ~W and P , Â£ 0 s h such that ( a ( C ) t j , w ) + - ( d i u t j , divw) _ 1 n s s = ( P _ ! + i , divw) + (j(C )gradd, s g n P = Ps-x - - (div\J s Let U r a e w), Vw Â£ W , (5.22a) f c - q). s (5.22b) = U and P = P for some integer s. s n Step 2: W h e n U C s n is known, find Câ€ž+i Â£ Zh such that â€” C {(f> l -,z) + ( D ( U ) g r a d C i , g r a d z ) + ( U â€¢ g r a d C i , z) n+ n = (g(C ),z), n + \/zeZ . n+1 n n + (5.23) h Note that i n step 1 of the scheme, the initial guess could be more efficiently taken as Po = P -i for n > 1 and P = 0 for n = 0. Our numerical experiments w i l l show n 0 that the number of iterations can be generally taken to be s â€” 2 for the range of perturbation parameter e = 1 0 - 3 to 1 0 - 5 . T h e following error estimates of the above approximation are proved i n [82]. T h e o r e m 5.2 Let {p, u,c} be the solution to Problem (5.1c)-(5.1b), and { P , U , C } the solution to the scheme (5.22)-(5.23) with s iterations at each time step. Then there exists a constant K, for At sufficiently small, such that the following error estimates hold at time step t m || P m â€” Pm || + \\Um ~~ U \\H(div) m ( m = 0,1,2, â€¢ â€¢ â€¢ , N): + \\C m ~ C \\ m Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 122 < K [t + /i' s s + ^ + 1 ||c|| oo L ( [ 0 ) t m ] ; (ll IU~([0,t ];H*+i) + + 1 h + + 1 ) l + 1 c m L m â€”1 ( A i | | c â€ž + i â€” c +i iii) ^ 1 \\c \\ 2 t ||diuu|| oo [ U n ^ ( 0 i t m L m m ] . i+i H ) + (5.24) ].H*+i)) + At(||u || ,2 i I ( [ 0 ] t m ] . 2 L ) + ||Ctt|| 2 [o,t ] L3))], L ( m i 2 n n=0 < K [e s s + ^ + 1 + h \\c\\ oo^ ]. i+i) + h \\c \\ 2([ j . i+i) l c L tm t c (IMU~([0,t ];H*+i) + m + l +1 H L 0 m] H (5.25) ll<fr'wu|| oo( ,t ];tf*+3)) + A < ( | | U t | | 2 ( [ , t ] ; L a ) L [0 ra L 0 m + ||Câ€ž\\ 2([ ,t ];Z2))] â€¢ L 0 m T h i s theorem tells us that for sufficiently small perturbation parameter e, the error estimates for the velocity, pressure and concentration are o p t i m a l . 5.5 Numerical Experiments In this section, we present some numerical examples to show how well our iterative scheme performs, and how the parameter e affects the number of iterations needed and accuracy required. For simplicity, we w i l l just consider the pressure-velocity equation, since the concentration equation has been analyzed previously [40, 41, 42, 45, 46, 47, 48, 98, 99, 120]. Consider the elliptic problem with Neumann boundary condition u = â€”a(gradp â€” f), divu = g(x), u â€¢ n = 0, x G ft, x G ft, x G T, where ft is a square and V its boundary. More general domains ft w i l l not present technical problems. The approximation scheme takes the form: F i n d I P G W^,, for s = 1, 2, â€¢ â€¢ â€¢ , ( a ^ U , w) + \{divU% divw) = {P ' 3 3 ps = -i pa 1 + \q, divw) + (f, w), Vw G W , (5.26) _ k(divW -q). f c (5.27) Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 123 Figure 5.1: One element w i t h velocity on each edge and pressure at the center P a r t i t i o n the domain ft into a set of squares of side length h. We take the space Wh to be the vector part of the Raviart-Thomas [100] space of index 0. Thus W f c = [V Â®V ) x x 0 (V Â®Vi), 0 where Vk is the set of one variable polynomials of order less than or equal to k. Consequently, the approximate pressure P s lies i n the space of piecewise constants. Partitioning the domain into triangles or rectangles or applying higher order approximation polynomials can be treated analogously. Let [/* denote the constant value of the flux i n the positive x or y-direction on the edge a , a = L , R , B , T (representing left, right, bottom, and top, respectively), of each element. See Figure 5.1. Consider w to be the basis function (1 â€” ,x,0) (on the standard reference square). A p p l y i n g the trapezoidal rule to (5.26) we have Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 124 a ^ h - 2 ^ h eh qL + qR + qr + QB p -x S (5.28) 4e where q is the value of q at the middle point of edge a. Similarly, letting w = a (x, 0), (0, 1 â€” y), (0, y), and simplifying we have the following linear system for each element. eh ai U -2{U -Ut 2 l s R ps-i = -2th thWU s + W R-U + s L = 2th L p -i s B + eh f , (5.29b) 2 R U^-U ) B QL + qR + S (5.29c 2 U}-U ) + s R + eh f , L At B l B qR + qr + qs S -2th 2 s T QL + QR + qr + qs p -i l th aT U^ U -U ) At th a U -2{U -U B , S R = 2th 2 + s L + qr + qs At + (5.29c) th f , 2 B + 2(U -Ui + U}- U ) S S R ps-i + B 9 L + qR + qr + qs + ch f . (5.29d) 2 T At Note that equation (5.27) has the discrete version on each element: 1 U -U S P = P s-1 s R + U$- U q + qR + qr + q S L B L (5.30) B eL h 4 J y F r o m equations (5.29) we can easily form the element stiffness m a t r i x . J Then assembling a l l the element matrices and taking into account the boundary condition we obtain the stiffness matrix. T h e force vector can be obtained i n an analogous way. A l l velocity and pressure errors are measured for iterates { U , . P } against the S exact solution under the LÂ°Â° norm, i.e. 11U - Ulloo ^ S u ||P -p||oo S \p\< S Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 125 T h e i n i t i a l guesses are always chosen to be zero, so all. errors are 1.00 before the iterative procedure starts. E x a m p l e 5.1 Let the velocity u and the pressure p satisfy (x = (x; y) ) T divu = 7T [cos(7ra;) + cos(7ry)], u gradp â€” ^ u â€¢n= o, xe , x Â£ ft, X Â£ ft, r, where ft = [0,1] x [0,1], and T = 9ft. The true solutions for the velocity u and the pressure p are given by sin(7ra;) \ u= sin(Try) J ' p â€” â€”(cos(7rx) + cos(7ry) + x â€” y). 7T The pressure p and externalflowrate q = divu are chosen in such a way that they both have mean value zero. E x a m p l e 5.2 Let the velocity u and the pressure p satisfy the nonhomogeneous problem divu = ab (e 3 - e ), by â€”x u = â€”a gradp â€” u - n = #, x Â£ ft, bx , X Â£ ft, xÂ£T, where ft = [0.5,1] x [0.5,1], F = <9ft, a = 0.05, and b â€” 10. The function g is chosen such that the true solutions for the velocity u and the pressure p are given by be 2 u = â€”a b (e hx bx -b e 2 - by e ) by +x - v Chapter 5. SRM for the Simulation of Miscible Displacement in Porous Media 126 e= lfr velocity pressure l.UU l.UU 1.14E-2 9.71E-3 2.69E-4 4.00E-5 1.29E-4 1.25E-4 1.28E-4 1.26E-4 1 iteration 0 1 2 3 4 e = lO"* velocity pressure l.UU l.UU 1.53E-3 8.67E-4 1.29E-4 1.25E-4 1.28E-4 1.26E-4 - e = 10velocity pressure l.UU l.UU 2.69E-4 4.08E-5 1.28E-4 1.26E-4 J - - Table 5.1: N u m e r i c a l results for E x a m p l e 5.1 w i t h grid size = ^ e = 1(T velocity pressure l.UU l.UU 1.42E-4 1.16E-4 1.28E-4 1.26E-4 4 iteration 0 1 2 e = 10-" velocity pressure l.UU l.UU 1.29E-4 1.25E-4 1.28E-4 1.26E-4 e = 10~ velocity pressure l.UU l.UU 1.29E-4 1.26E-4 b Table 5.2: Numerical results for E x a m p l e 5.1 w i t h grid size = ^ For E x a m p l e 5.1, the results with (uniform) grid size are shown i n Tables 5.1 and 5.2. T h e results of E x a m p l e 5.2 w i t h (uniform) grid size ^ and ^ are shown i n Tables 5.3. More examples and results can be found i n [82]. F r o m Tables 5.1 through 5.3 we conclude that our iterative method performs as well as the theory predicts. In particular, it can achieve the same accuracy as m i x e d finite element methods (at least for velocity), while the linear systems to be solved are symmetric and positive definite. Also, the computational work of our method is m u c h smaller than that of mixed methods, since the number of iterations required is usually very small. e = 10~ iteration U 1 2 3 grid size = ^ velocity pressure l.UU l.UU 1.18E-3 5.85E-3 1.02E-3 5.42E-3 grid size = Â± velocity pressure l.UU 1.00 3.23E-4 1.61E-3 2.00E-4 1.24E-3 Table 5.3: Numerical results for E x a m p l e 5.2 Chapter 6 N u m e r i c a l M e t h o d s of Some Singular P e r t u r b a t i o n P r o b l e m s In this chapter, we discuss the numerical solutions of some singular perturbation problems which are all special cases of the regularizations (1.12) and (1.13), and have practical meanings i n themselves as we indicated i n Â§1.4. In Â§Â§6.1 and 6.3 we w i l l construct and analyze uniformly convergent methods for these singular perturbation problems. So we first describe the definition of the method ( cf. [90]). D e f i n i t i o n 6.1 Ifu is the solution of a singular perturbation problem with a parameter e and u is an approximation obtained using a uniformly convergent method, then h there exist two constants eo and h independent of e and h such that when 0 < e < eo Q and 0 < h < ho we have an inequality of the form \\u-u \\ h < Ch , (6.1) p or in a weaker version (cf. [79]) \\u-u \\ h <C(h p + e ), r (6.2) where C > 0, p > 0 and r > 0 are independent of e and of the mesh width h, and || â€¢ || is some appropriate norm. â€¢ We use M to represent generic (in the sense of 0 ( 1 ) ) positive constants independent of e and of the mesh w i d t h h. Some of these constants w i l l also be denoted by mo, m i , m2, M and M i , etc. 0 127 Chapter 6. Numerical Methods of Some Singular Perturbation Problems 6.1 128 O n e D i m e n s i o n a l Quasilinear T u r n i n g P o i n t P r o b l e m s In this section, we consider the following two-point boundary value problem w i t h Dirichlet data at the endpoint: â€” eu" â€” b(x,u)u' + c(x,u) = 0, i Â£ / = [ - l , l ] , Â« ( - l ) = E/_, u(l) = [/+, where e (6.3a) (6.3b) 1 usually and b(x,u) may be zero at some isolated points. Such prob- lems are usually called turning point problems. Constructing uniformly convergent methods for problem (6.3) is generally very hard. W e w i l l consider a simpler case i n which we know the point, say x*, at which b(x, u(x)) = 0 and b (x, u) ^ 0 for a l l u i n x the vicinity of the solution. There are two types of turning point problems. T h e y are called repulsive and attractive turning point problems corresponding to the negative and positive sign of j^b(x,u(x))\ *, respectively. x=x T h e rest of the section is devoted to the two types of turning point problems and is actually a summary of two papers [79, 115] written by the author and his collaborator. We assume that the problem which we consider (in the form of (6.3)) has a unique solution. We also assume that the coefficients of problem (6.3) are sufficiently smooth (usually C (I x R ) is enough). 2 6.1.1 A repulsive t u r n i n g point p r o b l e m In this section, we assume c (x,u) > c > 0 on [ - l , l ] x R u (6.4) 0 Hence, a m a x i m u m principle holds for (6.3). B y constructing a barrier function it is not difficult to get max -1<X<1 lul < r, (6.5) v ' Chapter 6. Numerical Methods of Some Singular Perturbation Problems where r = max_ < < \c(x,0)\/c + max(\U-\, \U \). 1 a; 1 Q + 129 Furthermore we make the fol- lowing assumptions 6(0, u) = 0 A ( 0 , u) < 0 . for \u\ < r, b(x,u)^0 (6.6a) for | u | < r and x / 0. (6.6b) According the condition (6.6) there exists a small positive number 8 such that b (x,u) < â€”bo < 0 for \x\ < 8 x b(x,u)>b_ >0 for b(x,u) < -b for<J<x<l, 1 x < 0 - 1 < x < -8 (6.7a) (6.7b) (6.7c) where 8, bo, 6-i and bi are positive constants independent of e. We first give the bounds on the derivatives of the solution which is useful i n the proof of uniform convergence: \u^(x)\ < M ( l + e - e x p ( - m ( x + l ) / e ) i 0 |Â«^| < M \u^(x)\ < M ( l + e - e x p ( - m ( l - x)/e) i 0 for a; G [-1,<J], (6.8a) for \x\ < 8, (6.8b) for x G [5,1], (6.8c) where 8 is sufficiently small. (6.8a) and (6.8c) are a direct application of the result for problems without turning points which is derived by [113] and [77] independently. (6.8b) is proved in [79] by examining the Newton's sequence. This result means that the repulsive turning point problem does not have any interior layers. Next we consider how the solution v(x) of the reduced problem: b(x,v)v'- c(x,v) = 0 , - 1 < x < 1, (6.9a) c(0,u(0)) = 0. (6.9b) approaches the solution u(x). A s i n [21] (Remark 2.11), applying (6.8b) and results i n [83], we have \u(x) - v(x)\ < M ( e + e x p ( - m ( x + l ) / e ) ) 0 for x G [â€”1, â€”5], (6.10a) Chapter 6. Numerical Methods of Some Singular Perturbation Problems \u(x) - v(x)\ < Me \u(x) - v(x)\ < M ( e + e x p ( - m ( l - x)/e)) 0 130 for x 6 [-6,6], (6.10b) for x e [8,1], (6.10c) Now we start to construct an almost uniformly convergent algorithm. In the construction, we combine the initial-value technique [67] (a modification is given i n [81]) w i t h the idea i n [23]. W e want to indicate here that [67, 81, 23] are a l l for problems without turning points. We first rewrite (6.3) as eu"+{f(x,u))'u(-l) g(x,u) = 0, x â‚¬ / = [-1,1], = Â£/_, u(l) = U+, (6.11a) (6.11b) where f(x,u) â€” J b(x,s)ds and g(x,u) = c(x, u) â€” f (x, u). Integrating (6.11a), we u 0 x get eu' + f(x,u) = [ g(t,u(t))dt Jo X + K for - 1 < x < 1, (6.12) where the integration constant is K = eu'(0). Let E(x)= f g{t,u(t))dt. Jo X T h e n problem (6.3) is reduced to the following equivalent nonlinear i n i t i a l value problems: eu' + f{x,u ) = E(x) + K, -1 < x < 0, (6.13a) m(-l) = U-; (6.13b) l l and eu' + f{x, u ) = E(x) + K, 0 < x < 1, (6.14a) u (l) = U+. (6.14b) 2 2 2 Chapter 6. Numerical Methods of Some Singular Perturbation Problems 131 Replacing E(x) by E(x)= f g(t,v{t))dt, Jo where v{t) is the solution of the reduced problem (6.9), and neglecting K i n (6.13a) and (6.14a), we obtain the approximate problems: ey[ + f{x, ) = yi yi(-i) E{x),-l<x<0, = (6.15a) tf-; (6.15b) and ey' + f{x,y ) 2 = E(x),0<x<l, (6.16a) y (l) = U+. (6.16b) 2 2 It is proved i n [79] that \ (x) - y (x)\ < Me for 0 < | x | < 1 and * = 1,2. Ui (6.17) t F i n a l l y we consider the numerical solution of (6.15) and (6.16). Note that by using the change of variable x = â€”x the numerical method for problem (6.15) w i l l follow from that for problem (6.16), so we proceed considering only problem (6.16). For convenience we write (6.16) as ey â€” m\xy = â€”xe(x,y ), 0 < x < 1, y (l) = U+, 2 2 2 (6.18a) 2 '. â€¢ (6.18b) where e(x,y) = d(x,y) + m y. In the expression d(x,y) = (f(x,y) + E(x))/x is x bounded and m j is a positive constant to be determined below. O n the interval [0,1], introduce an arbitrary mesh {xi,i = 1,2, â€¢ â€¢ â€¢ , 7Y, w i t h XN = 1}. Integrating problem (6.18) on the subinterval [ 2 ; , x ; i ] , and replacing function + Chapter 6. Numerical Methods of Some Singular Perturbation Problems 132 e(x,y (x)) by e ( x ; , y ( ^ t + i ) ) > suggests a difference scheme: 2 +1 2 S/2,.- = yV = 2 _ 1 1 k e x (6.19a) m <7 , i = l , 2 , . - - - , i V - 1, . + where k{ = e x p ( â€” | m e ( x 1 + C ~ i) ( i+i>y!*,i+i)/ ii iV2,i+l k 2 _ (6.19b) â€” x )). According to the idea of [23], we can choose 2 + 1 a suitable mesh _ J 1 + (e/m) l n ( l - A T - 1 ) ^ ( 1 - e ) ) , i = N - N u - XJ_I) = h, [ Xi,maxi(xi â€¢ â€¢ â€¢, A , x N = N l 1- h t i = 1, â€¢ â€¢ â€¢ , N - N - 1, 2 x (6.20) where h = e\ l n e | / m and hi = 1/iVj. We have the following error estimate (see [79]): t T h e o r e m 6.1 Let y (xi) and y 2 be the solutions of problems (6.18) and (6.19), 2i respectively, i = 1, â€¢ â€¢ â€¢ , N. Under the mesh (6.20), taking â„¢-i > -fu(x,u) = -b(x,u), then we have max \u (xi) - UoA < Mh, (6.211 2 Ki<N where h = 1 V ' " ~ A V ' max(hi,h ). 2 A p p l y i n g the same method, we can also get a numerical solution y ,i xi â€” â€” A , â€¢ â€¢ â€¢ , â€” 1, of problem (6.15) such that _ max_ \ ( ) i Let yi f y\ = I u(0) Xi - y \ < Mh. for l h u = -N, for i = 0 I y$ for i = ti (6.22) (6.23) l,---,N be an approximation of the solution u(x) of problem (6.3), where v(0) can be solved from c(0,u(0)) = 0. A p p l y i n g (6.17), (6.10b) , (6.21) and (6.22), we have _ m a x \u( ) - y f | < M(h + e). N Xi (6.24) Chapter 6. Numerical Methods of Some Singular Perturbation Problems 133 Therefore, the numerical method we propose is an almost uniformly convergent method. In [79], a technique is given to modify the method to achieve uniform convergence. A numerical example is also given i n [79]. 6.1.2 A n attractive t u r n i n g point p r o b l e m In this section, we shall extend the results from [114] and [78]. We make the following assumptions: Moreover, we shall assume that e is sufficiently small. Note that, unlike the previous section, the m a x i m u m principle may not hold since we do not assume (6.4) here. T h e corresponding reduced problem has a discontinuous solution consisting of two smooth curves, u + and u _ , which satisfy: bi(x,uÂ±)u' â€” ci(x,uÂ±) Â± = 0, u Â± ( Â± l ) = UÂ±. denote the m a x i m u m norm i n C(I). To consider uniformly convergent methods, we shall estimate the solution u(x) and its derivatives and the quantities: vÂ± = (u â€” uÂ±)^ \x), k for k = 0,1,2 and x Â£ IÂ±, where /_ = [ - l , 0 ] , J + = [0,1]. We collect these estimates i n the following theorem. T h e o r e m 6.2 \(xv (x))'\ Â± < M(pV{x)\ xG Chapter 6. Numerical Methods of Some Singular Perturbation Problems \{xvÂ±{x))"\ e|u"(x)| < Mip+.p^Vix)), < M(e+y(x)), e\u"'(x)\ < 134 x â‚¬ / Â± , x e I, M(p + iT V(x)), xel, l where V(x) = e x p ( - â€” | x | ) , t 1 with an positive constant mo independent of e. â€¢ ' F r o m the estimates we see that the attractive turning point problem has an interior layer but no boundary layers. This theorem is built on several lemmas whose proofs are very technical. To show how technical these proofs are we prove one l e m m a below. We refer to [115] for complete details. L e m m a 6.1 |w(x)| < M. P r o o f : Let J |x|, " l g xe i\[-p,fi\. *e[-p,p}. + f, We can easily verify that p G C {I), l m a x ( | x | , p) > p{x) > - m a x ( | x | , p). (6.25) Next, consider the following Riccati initial value problem P(a) := col + xKa + M p{x) + ec? = 0, (6.26) a(0) = 0. (6.27) 0 It has a uniformly bounded solution. Indeed, by applying Newton's method to (6.26), (6.27) (cf.[88] or [79]), with the initial guess: oo(x) = - r ^ p ( t ) e x p ( - ^ ( x - f))dt, Jo e Ze 2 Chapter 6. Numerical Methods of Some Singular Perturbation Problems 135 the conditions of the N e w t o n - K a n t o r o v i c h theorem are satisfied since: ||ao(x)||oo < M, ll^'M" !! <M^ 1 ||Ol - Â«o||oo < Mp, \\P"(a)\\ < 2. Here, || â€¢ || is the operator norm corresponding to || - | | o o - Hence, there exists a solution a(x) to (6.26), (6.27), such that ||a - ao||oo < Mu, thus a is bounded uniformly i n e. Furthermore, we have xct(x) < 0 for x e I. (6.28) Indeed, because of the m a x i m u m principle and ea' + xKa = -Mop(x) - to? < 0, a(0) = 0, a(x) < 0 for x > 0 and a(x) > 0 for x < 0. Let <p(x) â€” e x p [ / (t) dt]. Jo a It holds that 0 < m < ip(x) < M , ip'(x) = a(x)ip(x) = 0(1). 0 (6.29) Note that <p is a solution to the following equation: e<p" + xKip' + M p(x)tp = 0. 0 Let us now consider an auxiliary problem: eu" + xbi(x, u(x))u' â€” c(x, u) = 0, (6.30) u ( - l ) = U-, u(l) = U+, (6.31) Chapter 6. Numerical Methods of Some Singular Perturbation Problems 136 and let us make the transformation u(x) = z(x)ip(x). T h e n z(x) satisfies : ez" + [2ect(x) + xb^x, u(x))]z' - c(x, z) = 0, *<-Â» = Â£r (6.32) = %rv y ' (6 33) where c(x,z) = â€”[e(p"(x)-\-xbi(x,u(x))(p'(x)](f(x)~ z-\-(p(x)~ c(x,z(p(x)) x 1 â€” M p(x)z â€” x[bi(x, u(x)) â€” b*]a(x)z + ip(x)~ c(x, zip(x)). 1 0 Choosing M sufficiently large and using (6.25) and (6.28) we have 0 c (x,z) z = M p(x) â€” xa(x)(b(x, u(x)) â€” &*) + c (x, z<p(x)) > m m a x ( | x | , p). 0 u 2 Hence, the problem (6.32), (6.33) satisfies the m a x i m u m principle and therefore has a unique solution z , such that w ,)l< _i)l w + W i ) l + ^ - Q ^ L < M . This shows that (6.30), (6.31) has a unique solution which is equal to u . T h e n (6.29) t completes the proof. â€¢ T h e numerical method is closely related to that from [114]. T h e same special non-equidistant mesh I is used. It has the following mesh points: h 2i Xi = X(ti), ti = -1 + â€”, i = 0(l)n, n = 2no, no G N , where [u{t):=^ *G[0,ao] v 7r(i) := S(t - a ) + \u"(a ){t - a ) 3 X(t) = 2 0 0 +u>'(a )(t - a ) + u(a ), 0 I -X(-t), 0 0 0 t G [a ,1] 0 *e[-i,0] Chapter 6. Numerical Methods of Some Singular Perturbation Problems a 0 137 is an arbitrary parameter from (0,1), i 5 is determined from 7r(l) = 1, S O that A G C (IÂ±) and A G C (I), and the parameter 2 l f3 is chosen from ( 0 , 7 ( 1 â€” a ) ~ ] . It may look as i f A is artificial, but its part a; is a _1 2 0 suitable rational approximation to the logarithmic function representing the inverse of the interior layer function V(x) for x > 0. T h e n TT is just a smooth extension of u. Let hi = Xi - x^, i = l(l)n, 1 hi = -(hi + h ), i+1 and let w denote a mesh function on I \ { â€” 1,1}, which w i l l be identified w i t h the h R n _ 1 h -vector: w = [u>i,iu , â€¢ â€¢ â€¢ , ^ n - i ] , h T 2 (wi := wf). Moreover, let us introduce the following standard finite-difference operators: D'Â±Wi D"wi = = Â±(w - iÂ±1 Wi)/hi, - Wi)/hi + (w i i+ Wi)/h ]/hi. i+1 We shall use the following discrete L - n o r m : 1 71-1 i=l For all this cf. [114]. Finally, the constants M w i l l now be independent of I as well. h Before discretizing the problem (6.3), as i n the previous section, we rewrite (6.3a) in the following conservation form: Tu:=-eu"-'f{x,u) f + g(x,u) = 0, x G / , (6.34) Chapter 6. Numerical Methods of Some Singular Perturbation Problems 138 where f+(x,u), x e 1+ g+{x,u), x e /+ pu fÂ±(x,u) = / xb (x,s)ds, 1 J uÂ± (x) gÂ±(x,u) = c(x, u) â€” xbi(x, uÂ±(x))u' (x) + / Â± (xbi(x,s)) ds x J uÂ± (x) = I c(x,u) â€” xci(x,uÂ±(x))-{- (xbi(x,s)) ds. x Ju4-!x) T h e n the discrete problem corresponding to (6.34), (6.3b) is given by: T wi = 0, i = l ( l ) n - 1, (6.35) h where rph \ Tllwu [ Tfttfi, i = l(l)n i = n + l{l)n 0 0 TÂ±Wi = -eD"wi - DÂ±fÂ±(xi,Wi) and where w 0 and w n + - I gÂ±(xi,Wi), should be replaced by U- and U+ respectively. T h e discretiza- tion is a generalization of that for the m i l d l y nonlinear case considered i n [114] and [78]. Let us introduce the following assumption i n addition to i) â€” iv): v) g (x,u) u = (xbi(x,u)) x -f c (x,u) u > g* > 0, x Â£ /, u G R. T h e following error estimate is proved i n [115]. T h e o r e m 6.3 The discrete problem (6.35) has a unique solution w h estimate holds: \\w h - u | | * < M-[u fc n + exp(-n)], where u h = [u(xi), u(x ),.. 2 â€¢ A numerical example is given i n [115]. â€¢, u ( x â€ž _ i ) ] . T and the following Chapter 6. Numerical Methods of Some Singular Perturbation Problems 6.2 139 N o t e s about Spurious Solutions of U p w i n d Schemes 6.2.1 Inadequacy of Y a v n e h ' s argument First order upwind schemes have been found by several researchers to yield spurious solutions. Such behavior has been attributed to the excessive artificial viscosity introduced by the numerical scheme, to multiple solutions of the nonlinear set of algebraic equations that is obtained from the discretization, and to poor resolution by grids that are too coarse (cf. [121, 27]). A simple example i n [61] also shows that an u p w i n d scheme may lead to a spurious solution near a boundary layer. Yavneh i n his P h . D . thesis [121] (also see [27]) claimed that the spurious solution may occur even i n cases where none of the above apply, and that such behavior is seen to occur even i n the linear scalar advection-diffusion equation, despite the fact that the truncation-error tends to zero w i t h the mesh-size throughout the entire domain, the solution being smooth everywhere. However, his proof is incomplete. Yavneh considers a linear advection-diffusion equation â€”eAu + u (a,9) = Ui -^rue = 0, r , (6.36a) 2 u(b,6) = u (6.36b) 0 over the circular disk 0 < # < 2 7 r , 0 < a < r < 6 . Here 1 Au = u rr 1 + -u + -^uee r is the Laplacian i n polar coordinates and e > 0. T h e unique solution (the uniqueness comes from the m a x i m u m principle) is _ Marco-'] a In order to see what might go wrong w i t h the numerical solution of this problem, we rewrite the equation i n Cartesian coordinates Lu = -eAu â€”-u x + â€”r^-â€”-u y = 0, (6.37a) Chapter 6. Numerical Methods of Some Singular Perturbation Problems u\ 2 x where A u = u xx + + y 2 = a = m, = u, u\ 2 2 x +y (6.37b) 0 =b 140 u. yy A s is well known, discretization of this equation by central finite differences loses its stability when e is small compared to the product of the mesh-size and the absolute value of either coefficient of the first derivatives i n the equation. A common practice is to retain stability by increasing the absolute values of the coefficients of the discretized second derivatives. A particular method of this type is the first order upwind difference scheme. This sort of discretization gives a second-order central difference scheme to the following equation: -c\u - eu xx 2 V yy x + y â€žu + x z u = 0 X y x + y l (6.38) 1 w i t h the same boundary conditions as (6.37b),where h\y\ e i = e h\x\ + Wt 2o Iâ€”oT> 2 = e + 2 2(x + y) Â£ 2(x 2 + y) 2 We plot the relationship of these continuous and discrete equations as follows: Problem (6.37) <â€” t Problem (6.38) Upwind scheme (first order) II <â€” Corresponding central scheme Yavneh considers the case e < h/2r ( e > h/2r is not interesting since i n this case the central difference scheme is stable) and shows that the difference between the solutions of problems (6.37) and (6.38) has a lower positive 0 ( 1 ) bound throughout the domain except near the boundaries as the mesh-size tends to zero. Based on this result, he then claims that the first order upwind scheme yields a spurious solution of problem (6.37). F r o m the above diagram, we see that the argument is incomplete since we do not know i f the central difference scheme is a good approximation for problem (6.38). T h e proof of this fact is not that obvious since we no longer know i f Chapter 6. Numerical Methods of Some Singular Perturbation Problems 141 the solution of (6.38) is smooth. (6.38) is a partial turning point problem whose layer property could be complicated. 6.2.2 O u r explanation In this section, we show that the stability constant of problem (6.36) depends on e. T h e smaller the parameter e, the closer the problem is to being ill-posed. Hence, we can expect that any direct discretization (of course, including u p w i n d schemes) on the problem would be unstable when e is sufficiently small . Therefore, it is not strange that the first order upwind scheme fails for this problem. Let's consider (6.36) w i t h a forcing term f(x, y). Suppose that u(x, y) is a solution of the problem, i.e. Lu = f(x,y) (6.39) and u satisfies boundary conditions (6.36b). We construct u*(x, y) = u(x, y) + ( r - a ){b - r ) , 2 2 2 (6.40) 2 which satisfies the boundary conditions and Lu* = f(x, y) + e(12(x + y ) - 4 ( a + b )). 2 2 2 (6.41) 2 In other words, i f we make a small perturbation e(12(x + y ) â€” 4 ( a + 6 )) to the 2 2 2 2 right-hand side of the equation, the solution changes a lot (by ( r â€” a )(b â€” r ) ) . 2 2 2 2 T h a t means the problem (6.39),(6.36b) is not well-posed as e is small. T h e n we may not expect its approximation (direct discretization) to be stable. Indeed we can prove that any difference scheme w i l l not be stable (as e is small). Suppose we have a discretization (consistent w i t h order h ) r LhUh = f(x,y), B u h h = 0 (discrete B C ) also L u* = f(x, y) + e(12(z + y ) - 4 ( a + b )) 2 h h 2 2 2 Chapter 6. Numerical Methods of Some Singular Perturbation Problems 142 B u* = 0 h h Then L (u h - u%) = e(12(x + y ) - 4 ( a 4- b )) 2 h B (u h 2 2 2 - u* ) = .0 h h If (Lh,,Bh) is stable, or more precisely, i f the coefficient m a t r i x Ah of the linear algebraic system corresponding to the discretization satisfies Halloo < M , (6.42) where M is a generic positive constant independent of e and h, we get = Uh â€” u 0(h ) r u* -u* = 0(h ) r h u -u* h = 0(e) h Hence u-u* = 0(e + h ) r This is a contradiction since u â€” u* = ( r â€” a )(b â€” r ). So (Lh,Bh) can not be stable. 2 2 2 2 In fact, we can show Claim 1 J-j-r). \K \\>0( X (6-43) max(e, h ) T P r o o f : If e > h and WA^W^ = 0(l/e ), r s U u* -u* k h - S < 1, then ('^)<0(e - ), 1 U = 5 0 < 0(e ~ ), 1 5 u - u\ = h 0(e ' ). 1 5 Chapter 6. Numerical Methods of Some Singular Perturbation Problems 143 Therefore uâ€” u 0(e l-8\ can be arbitrarily small. This is a contradiction i n (6.40). So we must at least have IIA^Hoo = 0(l/e). O n the other hand, i f e < h , we can prove that r II Vlloo > 0(1). Thus (6.43) is proved. â€¢ For the first order upwind scheme, we actually can prove Claim 2 A- \\ (6.44) = 0{'max(e, h)' 1 h Before we prove this claim, we first write down the scheme a n d then prove a discrete m a x i m u m principle. T h e scheme is "t,J-"t-l,J Uj lJ-UjJ + h-xi -e + 1,J x i+y j 2 "â€¢â€¢,.) U J - U X, > - 1 J yj xj+yj _2 1 + xj+y* + u Xi h-xi u yj ,7 -1,7 ~2 ..2 1 -.2 ""<J hyj â€” l U 2 x e x 1y h i-i â€”1 "F h:iâ€”\) ; + IJ + x +y? h-xi 2 y.i h-xi 2(^3:2 j-ui,j-l ^ 2^yi h'yjâ€”1) (forx > 0,y > 0) (forx > 0,y < 0) u (forx < 0, y > 0) u (fonc < 0, y < 0) (6.45) 0. L e m m a 6.2 TVie difference scheme (6-45) has a discrete maximum principle, that is, LhUh > 0 and â€¢u^lr^ > 0 ==> > 0, where Th represents all the mesh points on the boundaries x +y 2 2 = a and x +y 2 P r o o f : Suppose that u > 0 is not true. T h e n there exists an interior point h of the domain such that u st < 0. Furthermore we can choose u S j t 2 = b. 2 2 (x ,y ) such that u s Sft t = Chapter 6. Numerical Methods of Some Singular Perturbation Problems 144 m i n ; j Uij and at least at one adjacent point u j of u ,t the rigorous inequality Uij > 8 s u t holds. Hence (for simplicity, we only consider x > 0,y > 0 case), St Â«5,t-Â«g,t Lh h\ < u u ,tâ€”U ,t s ^ h \{h y hy -i yt t +h u, - u t Â« j , | - " a , l ^ h xa xs s + y* ^ 5 Us,tâ€”Us,t s h -i xs t x Stt u s hxa X s>t - uj _ s + 2 S T h i s is a contradiction to LhUh > 0, which completes the proof. â€¢ Now we prove Claim 2. P r o o f : We construct the barrier function _ 2 _ 2 x Wh - \u \ + Wi \ + Mi y -7â€”TV 0 m ^ (6.46) \LhUh\, x max(e,n) Â« , j where h = max(h , h ), while h = max; h { h = maxj h j. T h e n it is easy to verify x y x x y y y that L (w h Â± u ) > 0, to/j Â± u \r > 0 h fc h h when M i is sufficiently large. Using the discrete m a x i m u m principle we obtain w Â±u > h 0. h We thus have . . . i b -x -y = \u \ + \ui\ + Mi â€”pâ€” m a x \ L u \ . max{6,n) h3 2 \uh\ <w h 2 0 2 h h This means \A~ \U l h <M â€”max(e a) l (6.47) : So (6.44) follows from (6.47) and Claim 1. â€¢ . Hence, the first order upwind scheme for problem (6.39),(6.36b) is not convergent when e is small compared w i t h mesh-size h. O f course, i t produces a spurious solution in general. For Yavneh's example (f(x, y) = 0 i n (6.39)), numerical calculation verifies the appearance of the spurious solution. F r o m the result of Claim 2 we expect that a Chapter 6. Numerical Methods of Some Singular Perturbation Problems 145 good second-order scheme would converge i f t is smaller than h but much larger than h . N u m e r i c a l calculation i n [121] verifies this too. 2 Note that, i n polar coordinates, the first order upwind scheme converges since its truncation error has a factor e (because the derivatives of u w i t h respect to 9 are all zero). In Cartesian coordinates, no such behavior exists. 6.3 A Linear Hyperbolic-Hyperbolic Singularly Perturbed Initial-Boundary Value P r o b l e m Previous to this work, we discussed several singularly perturbed problems of hyperbolic type i n joint papers [105, 106], constructed some difference schemes according to the properties of the problems, established discrete energy inequalities for the solutions of difference problems, and, based on the inequalities, proved that the difference schemes are uniformly convergent i n the sense of the discrete energy n o r m . B u t i n those papers the equations considered d i d not include a first derivative term w i t h respect to the space variable x. Here we discuss a more complete initial-boundary value problem: Lu c = e(u - u ) + a(x,t)u + b(x,t)u + c(x,t)u tt xx t x = f{x,t), (x,t) G G = {0 < x < /, 0 < t < T} u(s, 0) = <f>(x), u (x, 0) = ip(x), (0 < x < I) t u(0,t) = 0, u(l,t) = 0, (0 < t < T) where a(x,t),b(x,t),c(x,t), (6.48a) (6.48b) (6.48c) f(x,t),(/)(x) and ip(x) are sufficiently smooth functions and a(x,t) > a > 0 for all (x,t) G G. Moreover, b(x, t), f(x, t), 4>(x) and if>(x) satisfy 0 the following compatibility conditions: C I : (f)(0) = 0, V ( 0 ) = 0, (f)(1) = 0, rj>(l) = 0; C 2 : 4>"(0) = 0, 6(0,0)^(0) = / ( 0 , 0 ) , </>"(0 = 0, 6(/,0)^(/) = / ( / , 0 ) . Chapter 6. Numerical Methods of Some Singular Perturbation Problems 146 T h e subcharacteristics of the reduced operator Low â€” a(x, t)w + b(x, i)w + c{x, t)w t x (6.49) are timelike (cf.[53]) w i t h respect to the characteristic directions of equation (6.48a), that is, \b(x,t)\/a(x,t) < 1 for ( x , t ) G G. For simplicity we assume that b(x,t) >bo>0. (6.50) Hence, (6.50) becomes b(x,t) < a(x,t) for (x,t)'e G. (6.51) T h e reduced problem of (6.48) is LOUQ = u (x,0) = <f>(x), o f(x,t), (6.52a) u ( 0 , f ) = 0, (6.52b) o where LQ is defined as (6.49). Therefore, the solution of problem (6.48) has boundary layer at t = 0 and x â€” 1. T h e reduced problem (6.52) is a first order hyperbolic initial-boundary problem i n a semi-bounded region D = {(x,t), x > 0, t > 0}. According to [22], under the conditions Cl and C 2 , the first partial derivatives of the solution Uo(x, t) of (6.52) are continuous, but the second derivatives are discontinuous along the characteristic line. In order to construct the asymptotic solution, it is necessary that uo(x,t) G C (D). 2 We w i l l give a method to overcome the difficulty without additional c o m p a t i b i l i t y conditions. This section is a summary of the joint paper [107]. In what follows we first give an energy estimate of the solution of problem (6.48). T h e n , the asymptotic solution is constructed under the compatibility conditions C l and C2 and uniform validity is proved i n the sense of the energy norm. Thirdly, an exponentially fitted difference scheme for problem (6.48) is proposed and a discrete energy inequality is established. Chapter 6. Numerical Methods of Some Singular Perturbation Problems 147 Finally, we show that the discrete problem is uniformly convergent i n the sense of discrete energy norm. 6.3.1 C o n s t r u c t i o n of a s y m p t o t i c solution and its r e m a i n d e r estimate We first give the following energy inequality which w i l l be used i n estimating the remainder of the asymptotic expansion. L e m m a 6.3 Let u(x,t) be the solution of (6:48), and let the conditions we described previously be satisfied. Then as e is sufficiently small, we have Â«|| + e\\u \\ + e\\u \\ < MK(G, e) t (6.53) x where P r o o f : M u l t i p l y i n g equation (6.48a) by 2ea~ u l t + Â« , then integrating the obtained equation i n the region G = { ( x , s ) | 0 < x < I, 0 < s < Â£ } , and performing the t standard argument for the energy method, we thus have (6.53). â€¢ Next we construct the asymptotic solution. A s we indicated before, under the compatibility conditions Cl and C 2 , the solution belongs to C (D), 1 but not C (D). 2 Uo(x,t) of the reduced problem In order to realize the iterative procedure of the asymptotic solution, the continuity of the second derivatives of uo(x,t) is needed. However, this usually gives rise to the increase of the compatibility conditions. In this section, we construct the asymptotic solution under the conditions Cl and C2 without adding other ones. B y making some transformations on (6.52) so the i n i t i a l and boundary conditions become homogeneous and the right-hand function becomes equal to zero i n the neighborhood of t = 0, we obtain a problem i n which a l l compati b i l i t y conditions we need are satisfied. T h e n based on the transformed problem, an Chapter 6. Numerical Methods of Some Singular Perturbation Problems 148 approximate problem for (6.48) is constructed and the solution of its reduced problem belongs to C (D). 2 Now T h e n an asymptotic expansion can be constructed. we deal w i t h problem (6.52). Let Uo(x,t) = Wo(x,t) + (f>(x), noting that <f>(0) = 0, then L wo = F(x,t), 0 w {x,0) = 0, w (0,t) = 0, (6.54) o 0 where operator LQ is defined as (6.49) and F(x,t) = f(x,t) â€” Lo4>- Introduce a function u:(y) G CÂ°Â° satisfying 1 o Â«><Â»M) w i (s > 1) and 0 < u(y) < 1. Defining F = u)(t/5)F(x,t), we have nM)-F ^) = ( i - . ( > ^ ) = { f ( Therefore, F(x,t) and F(x,t) 1}. Replacing F(x,t) 0 = 0 ) | Â° have difference only i n the region {0 < t < 5, 0 < x < by F{x,t), Lw M problem (6.54) is changed into F(x,t) = u( -)(f{x,t)- L </>), t 0 w (x, 0) = 0, u> (0, t) = 0. o 0 P r o b l e m (6.55) for any S > 0 satisfies all compatibility conditions we need. (6.55a) (6.55b) Thus wo is sufficiently smooth. Transforming back, i.e. letting UQ = WQ + 4>, we obtain an approximate problem for (6.52) L uo 0 = /(M). = <f>(x) u (x,0) o , (6.56a) u (0,<) = 0, 0 where f( ,t) x = u( -)f(x,t) t + (l-co( -))L cf>. t 0 (6.56b) ^ / Chapter 6. Numerical Methods of Some Singular Perturbation Problems 149 Here Uo(x, t) is sufficiently smooth since WQ and <f> are. F r o m the appendix of [22], we have u -u 0 = 0(8). 0 (6.57) Now we can get an approximate problem of (6.48) Lu = t Â« ( 0 , x) = <p{x), u (0, x) = ip(x) f(x,t), , t (6.58a) u(0, t) = u(l, t) = 0. (6.58b) Using the energy inequality (6.53), we can get \\u - u\\ = 0(8*). (0 <t <T) (6.59) Note that problem (6.49) is the reduced problem of (6.58). Hence, the reduced problem of (6.58) has enough smoothness such that the usual procedure to construct the asymptotic expansion can be performed. For example, we can construct the asymptotic expansion of (6.58) i n the form of u(x,t) = u(x,t) + z, where u(x, t) = Â« ( x , t) + evj (x, r) + 4Â°(Â£, 0 + t), r = t/c, Â£ = (I - x)/e, 0) 0 } u is the solution of (6.49) and v^jV^ and v[ ^ satisfy the following equations 1 0 (vi% + a{x,0)(vi ) O) T T ( ^ ) ( x , 0 ) + (u ) (.T,0) O ) o T (v \ { 0 t b(l,t)(v \ { i vH\0,t) + 0 + u (l,t) o = 0, = 0, = tb(x), l i m vi 0) Tâ€”>-00 = = 0, l i m vH\U) <->oo = 0 0, Chapter 6. Numerical Methods of Some Singular Perturbation Problems 150 and (v[% + b(l,t)(v{\ = v[ (0,t) = 0, l i m v[ = 0, l) l) Â£-Â»oo respectively. Using the energy inequality (6.53) and estimating carefully, we have the following bound ||z|| = \\u(x,t) - u(x,t)\\ < M(5^ + + e8~ + e 8~ ). l 2 (6.60) 2 Denote the asymptotic expansion of problem (6.48) as (x,t) = u (x,t) + eviÂ°\x,r) + v$\{,t) + ev[ {C,t). l) Ul 0 2 A p p l y i n g (6.57),(6.59) and (6.60) and taking 8 = es, we finally obtain \\u(x,t)- (x,t)\\< Ul (6.61) MeK R e m a r k 6.1 If the coefficients, right-hand side and initial values of problem (6.4-8) satisfy enough compatibility conditions such that the solution u(x,t) Â£ C (G), then 3 we can construct the asymptotic solution without needing the function u(t/5). asymptotic solution is still Ui (replacing UQ by UQ in the equations for The and v$). Moreover, we have the following remainder estimate \u(x,t)- (x,t)\< Ul MeK (6.62) â€¢ 6.3.2 Difference scheme and its u n i f o r m convergence Taking uniform meshes i n the directions of x and t, we obtain a discrete region Gd = {(x{,tj), i â€” 0, â€¢ â€¢ â€¢ , N, j = 0, â€¢ â€¢ â€¢ , [T/k], Xi = ih, tj â€” jk], where h and k Chapter 6. Numerical Methods of Some Singular Perturbation Problems 151 are mesh sizes and Nh = I. Denoting u (x,i) as the approximate value of u(x,t), d we establish the difference scheme of problem (6.48) by using the exponential fitting idea: L{ ^u (x, t) = ( x , t, k)u$i(x, t) h d 7 l ( x , t, h)u (x, t) + a(x, t)uf d 7 2 xx +b(x, t)u (x, t) + c(x, t)u (x, t) = f(x, t), (x, t) Â£ G d d d u (x, 0) = cf>(x), u (x, k) - u (x, 0) = kxb( ), d d (6.63b) d x u (0,t) = u (l,t) = 0, d (6.63a) (6.63c) d where (X,t) 7 = (Xi,tj), = {u%, u | = (u$) h b(x,t)hexp(â€”b(x,t)h/e) 2 1 â€” exp(â€”b(x, t)h/e). ' u (a;,t) - u (x - h,t) rf s xS 1 â€” exp(â€”a(x, t)k/e) ' â€¢y (x,t,h) d d a(x, t)kexr)(â€”a(x,t)k/e) i(s,t,fc) u (x,t) u = rf h u (x,t) - u" (x,td ul(x,t) k u (x + h,t) - k) u (x,t) d d For this difference scheme we can establish the following discrete energy inequality. L e m m a 6.4 Let u (x,t) be the solution of (6.63) and let mesh sizes h and k satisfy d inequality b(x,t)h < a(x,t)k for all (x,t) G Gd- Then when e,h and k are sufficiently small we have \\A\l + Il7iÂ«rll2 + I I V l ^ 4 \ \ s < MK(h,fc,e), 2 where K(h,k,e) = ^ f c ^ ^ ^ : ^ -I- H-yxTx^H? H- II^Ti^^ll? -I- II^/O^TWM^II? -|2 j=lz = l N \v\\ . 2 h^2v(ih,sk) , i=i 2 s = 1,- â€¢ â€¢ , J, J â€” [T/k], p = k/e. (6.64) 152 Chapter 6. Numerical Methods of Some Singular Perturbation Problems P r o o f : Essentially, the proof is a simulation of the continuous case but m u c h more complicated because of the fitting factors 71 and 72. A sketch of the proof is i n [107]. â€¢ R e m a r k 6.2 Iffittingfactors are not used, then the condition b(x,t)h < a(x,t)k can be removed in the proof. â€¢ Next we prove the uniform convergence. We assume that enough compatibility conditions are satisfied so that the solution u(x, t) of problem (6.48) belongs to C (G). 3 Based on the asymptotic expansion we may assert that the following estimates | | ^ | < M(e- + 0 < * < 3, 0 < i < k (6.65) hold. For convenience we also assume c\k < h < c k, c i > 0, a(x,t)/b(x,t) > c > 0. 2 2 (6.66) Using derivative estimate (6.65), it is not difficult to verify L{ ' \u(x,t)-u (x,t)) h k = 0(^ + - ), d 2 e k 2 (u - u )\ d = 0, (u - u )\ = min( â€” ,k), d t=0 t=k {u - u% =0 = 0, (u - u% =l = 0. A p p l y i n g discrete energy inequality (6.64), yields \u-u%<M(- e + -). e 2 (6.67) O n the other hand, we can obtain 4 M ) ( f i i - Â«") = L{ > (u + e ^ h k) 0 0 ) + + - / /- x = 0(e + h + k + exp(â€”m â€”-â€”), (m > 0) 0 0 Chapter 6. Numerical Methods of Some Singular Perturbation Problems 153 and (Â«i - u )\ = 0(e), (uu-uDl^k d t=0 ( Â« i - u )\ d = 0(1), = 0(e"), ( u ! - u )\ = 0, d x=0 x=l where n is an arbitrary positive number. First making a change of variable such that the boundary value conditions become homogeneous, then using the discrete energy inequality (6.64), we have - u \\ < M ( ^ / m a x ( e , / 0 + k + e /h). d (6.68) n s Hence, from the remainder estimate (6.62) of the asymptotic solution u\, we obtain another error estimate | | M -U%< M ( ^ / m a x ( e , h) + k + e /h). (6.69) n C o m b i n i n g (6.67) w i t h (6.69) we achieve our uniformly convergent estimate. T h e o r e m 6.4 Supposing that (6.66) is satisfied and the solution of (6.^8) u(x,t) Â£ C (G). 3 Then the solution u (x,t) of the discrete problem (6.63) uniformly converges d to u(x,t) in the sense of the discrete energy norm, i.e. I l u - u ^ l . < Mh*, s = 0,1, (6.70) P r o o f : Using (6.69), (6.66) as e / < h and using (6.67), (6.66) as e / > h, we. 5 2 5 2 have (6.70) immediately. â€¢ R e m a r k 6.3 If we apply the remainder estimate (6.61) and corresponding procedure there we may discuss the uniform convergence under the compatibility conditions Cl and 0 2 only. â€¢ Chapter 7 C o n c l u s i o n and F u t u r e W o r k 7.1 S u m m a r y and conclusions T h e m a i n focus of the thesis is on constrained ordinary differential equations ( D A E s ) , constrained partial differential equations ( P D A E s ) , and their applications. A new class of methods for solving high index D A E s has been developed, which we call the Sequential Regularization Method or S R M for short. These methods offer significant advantages over some known solution techniques, such as regularization and stabilization methods, and are applied to the nonstationary Navier-Stokes equations governing incompressible fluid flow and to a mathematical model of reservoir simulation. H i g h index D A E s (index > 2) are usually difficult to discretize directly [29, 86]. We thus need to reformulate the original problem as a better behaved problem before discretization. Index reduction w i t h stabilization is a popular reformulation for the numerical solution of semi-explicit high index D A E s . Another class of reformulations is regularization, where the D A E is replaced by a better behaved nearby problem. Such a method reduces the size of the system to be solved and avoids the derivatives of the algebraic constraints associated w i t h the D A E problem. Regularization is particularly suitable for problems w i t h certain singularities where the constraint Jacobian does not have full rank. Unfortunately, this approach often yields very stiff problems, which accounts for its lack of popularity i n practice. T h e S R M is proposed to overcome this difficulty. It keeps the benefits of regularization methods and avoids the need to use stiff solvers for the regularized problems, because the regularization 154 Chapter 7. Conclusion and Future Work 155 parameter does not need to be very small. Thus, we obtain an important improvement over usual regularization methods which leads to easier numerical methods (explicit time discretization for regularized problems). The S R M also provides cheaper and more efficient alternatives to the usual stabilization methods for some choices of parameters and stabilization matrix. We first propose and analyze the method for linear index-2 D A E s . T h e n we extend it to nonlinear index-2 and index-3 D A E s . T h i s is especially useful i n applications such as constrained m u l t i b o d y systems which are of index-3. N u m e r i c a l experiments show that the method is useful and efficient for problems w i t h and without singularities. W h i l e a significant body of knowledge about the theory and numerical methods for D A E s has been accumulated, almost none has been extended to partial differentialalgebraic equations ( P D A E s ) . A s a first attempt we provide a comparative study between stabilization and regularization (or pseudo-compressibility) methods for D A E s and P D A E s , using the Navier-Stokes equations as an instance of P D A E s . C o m p a r e d w i t h stabilization methods, regularization methods can avoid imposing an artificial boundary condition for the pressure p. T h i s is a feature for P D A E s not shared w i t h DAEs. We generalize the S R M to the nonstationary incompressible Navier-Stokes equations. Similar to D A E s , explicit schemes i n the time direction can be used for the P D A E because of the reduced stiffness (taking the regularization parameter relatively large) or even essential nonstiffhess obtained for some choice of parameters. U n l i k e usual regularization methods, the time step restriction for the explicit scheme can be independent of the regularization parameter e. T h e time step restriction is further loosened for the case of small viscosity. A simple discretization (such as the forward E u l e r difference i n time and a first-order scheme i n space) is analyzed and implemented. N u m e r i c a l results support our theoretical results. T h e method works for both two- and three-dimensional problems. In recent years considerable attention has been devoted to numerical reservoir 156 Chapter 7. Conclusion and Future Work simulation, e.g. miscible displacement i n porous media. We have applied the S R M idea to the pressure-velocity equation in its 2-dimensional mathematical model equations. T h i s procedure is first analyzed at the differential level and then discretized by finite element methods. Theoretical analysis and numerical experiments show that this procedure converges at the rate of 0(e) per iteration, where e is a small positive number. T h e fast convergence rate makes our iterative method dramatically different from penalty methods . In addition, the perturbation parameter e does not have to be carefully chosen, unlike the case for other iterative methods. Indeed, our numerical experiments show that two iterations are usually enough for a variety of problems. Compared w i t h m i x e d finite element methods, the discrete version of our scheme can provide the same accurate approximations for velocity and pressure, which is crucial in reservoir problems since velocity is intimately involved i n the concentration equation. However, i n contrast to m i x e d finite element methods, our scheme requires only the solution of symmetric positive definite linear systems which have a smaller number of degrees of freedom corresponding to the velocity variable. Since our method completely decoupled the velocity and pressure variables, the so-called Babuska-Brezzi condition is not needed i n constructing the finite dimensional spaces for velocity and pressure. T h e method is easily applied to three-dimensional problems. Another topic of this thesis is singular perturbation problems, which come from many applied areas and regularized problems. We discuss numerical solutions of several singular perturbation problems. Uniformly convergent schemes w i t h respect to the perturbation parameter e are constructed and analyzed for nonlinear repulsive and attractive turning point problems and a second-order hyperbolic problem. We are the first to be able to construct uniformly convergent schemes for these problems. Also, an interesting spurious solution phenomenon from an upwinding scheme is analyzed for an elliptic turning point problem. We find that the spurious solution is caused by a m i l d instability of the problem (the constant for the stability inequality is of 0 ( ^ ) ) . Chapter 7. Conclusion and Future Work 157 This type of instability is not as serious as supersensitivity [73, 74]. It can be handled by using higher order upwinding schemes as long as their accuracy h <C e when e is r not too small. 7.2 D i s c u s s i o n of future work T h e results of this thesis can be extended i n a number of directions. Efficient s i m u l a t i o n of k i n e m a t i c chains w i t h closed loops T h e kinematic chain problem is an example of m u l t i b o d y systems, such as robot manipulators. Consider a chain consisting of n links. T h e numerical simulation of the problem is usually treated as two separate problems: (i) the forward dynamics problem for computing system accelerations, and ( n ) the numerical integration problem for advancing the state i n time. In recent years, many different algorithms have been proposed for solving the forward dynamics problem w i t h tree structure (without closed loops), ranging i n computational complexity from 0(n ) (e.g. the composite 3 rigid body method ( C R B M ) [116]) to 0{n) (e.g. the articulated-body method ( A B M ) [49]). However, it has never been possible to construct an 0(n) algorithm for the chain problem w i t h many closed loops. T h e S R M (plus explicit discretization) opens up a way to do this. According to the idea of the S R M , we can remove the extra constraints caused by closed loops and incorporate them into external force terms of the system. T h e reformulated problem has the same structure as that of the problem without closed loops. We thus expect to develop and test an 0(n) algorithm for closed-loop chains. F u l l y nonlinear D A E s Consider a fully nonlinear i n d e x - f D A E ^ f(t,x,x,---,x^ \y)? Chapter 7. Conclusion and Future Work 0 (i.e. = 158 g(t,x), where algebraic variables y appear nonlinearly together w i t h the differential variables x.) Some mechanical multibody systems are i n this form w i t h v = 2, e.g. the motion of a point mass on a parabolic orbit w i t h the forces of gravitation and Coulomb friction (see [4]). The S R M can be applied to this problem. For instance, corresponding to the index-2 problem (with v = 1) we have: for s = 1,2, â€¢ â€¢ â€¢, â€” fifi x s y s = siys)i x Vs-i + ^e(g(t,x )), s where the function e should be chosen such that the m a t r i x f e g y g x has positive eigen- values. Efficient s i m u l a t i o n of real fluid problems using S R M Because the computations for u and p are uncoupled and explicit time discretization can be used, we expect that the S R M incorporated w i t h a finite difference or finite element discretization would provide a cheap and efficient method for simulating more realistic fluid problems. For long time simulations, a reinitialization technique (e.g. projecting back to the divergence free space after a number of time steps) may be useful. A comparative study between the S R M and other methods would be interesting. S o l v i n g t h e system resulting from the discretization of t h e operator / + ^-graddzu T h i s operator comes from using S R M to solve the nonstationary Navier-Stokes equations w i t h cti ^ 0. T h e system is easily made to be banded symmetric positive definite. Hence a direct method can be used to solve it. A n interesting observation is that the usual iterative methods do not work well. T h i s is probably due to the lack of ellipticity of the system. Some research on solving this problem using m u l t i g r i d Chapter 7. Conclusion and Future Work 159 and domain decomposition techniques (at least for e not too small) is about to be completed by A r n o l d , Falk and W i n t h e r [3]. Based on a technique described i n [57], iterative methods (including multigrid) would be feasible under some pre-processing of the system (to increase the ellipticity). This was also suggested by W . Hackbusch in a private communication. Bibliography C . Amirouche and V . G i r a u l t , Decomposition of vector spaces and application to the Stokes problem i n arbitrary dimension, Czechoslovak M a t h e m a t i c a l J . 44(1994), N o . 119, pp. 109-140. F . Amirouche, Computational Methods in Multibody dynamics, P r e n t i c e - H a l l , 1992. D . N . A r n o l d , Private communication, 1995. M . A r n o l d , A perturbation analysis for the dynamical simulation of mechanical multibody systems, Preprint 94/24, Universitat Rostock, Fachbereich M a t h e matik, Germany, 1994. K . A r r o w , L . H u r w i c z and H . Uzawa, Studies in Nonlinear Programming, Stanford University Press, 1968. U . Ascher, On some difference schemes for singular singularly-perturbed boundary value problems, Numer. M a t h . 46 (1985), 1-30. U . Ascher, On numerical differential algebraic problems with application to semiconductor device simulation, S I A M J . Numer. A n a l . 26(1989), 517-538. U . Ascher, H . C h i n and S. Reich, Stabilization of DAEs and invariant manifolds, N u m e r . M a t h . 67 (1994), 131-149. U . Ascher, H . C h i n , L . Petzold and S. Reich, Stabilization of constrained mechanical systems with DAEs and invariant manifolds, Journal of Mechanics of Structures and Machines 23 (1995), 135-157. U . Ascher, J . Christiansen and R . D . Russell, Collocation software for boundary value ODEs, Trans. M a t h . Software 7(1981), 209-222. U . Ascher and P i n g L i n , Sequential regularization methods for higher index DAEs with constraint singularities: Linear index-2 case, S I A M J . Numer. A n a l . , to appear. U . Ascher and P i n g L i n , Sequential Regularization Methods for Nonlinear Higher Index DAEs, S I A M J . Sci. Comput., to appear. U . Ascher, P . A . M a r k o w i c h , P. Pietra, C . Schmeiser, A phase plane analysis of transonic solutions for the hydrodynamic semiconductor model, M a t h . Models & Methods i n A p p l i e d Sciences 1(1991), 347-376. 160 Bibliography 161 U . Ascher, R . Mattheij and R . Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equation, Prentice-Hall, 1988. U . Ascher and L . Petzold, Projected implicit Runge-Kutta methods for differential-algebraic equations, S I A M J . Numer. A n a l . 28 (1991), 1097-1120. U . Ascher and L . Petzold, Stability of Computational Methods for Constrained Dynamics Systems, S I A M J . Sci. Comput. 14 (1993), 95-120. J . Baumgarte, Stabilization of constraints and integrals of motion in dynamical systems, C o m p . M a t h . A p p l . M e c h . E n g . 1 (1972), 1-16. G . Bader and U . Ascher, A new basis implementation for a mixed order boundary value ODE solver, S I A M J . Scient. Stat. Comput. 8 (1987), 483-500. E . Bayo and A . Avello, Singularity-free augmented Lagrangian algorithms for constrained multibody dynamics, J . Nonlinear Dynamics 5 (1994), 209-231. E . Bayo, J . G . de Jalon and M . A . Serna, A modified Lagrangian formulation for the dynamic analysis of constrained mechanical systems, Computer Methods i n A p p l i e d Mechanics and Engineering 71(1988), 183-195. A . E . Berger, H . H a n and R . B . Kellogg, A priori estimates and analysis of a numerical method for a turning point problem, M a t h . C o m p . 42(1984, 465-491. L . E . Bobisud, The second initial-boundary value problem for a linear parabolic equation with a small parameter, M i c h . M a t h . J . 15(1969), 495-504. L P . Boglaev, On numerical integration of a singular- perturbed initial-value problem for ordinary differential equation, Z h . V y c h i s l . mat. i mat. fiziki ( C o m p . M a t h . & M a t h . Physics) 25(1985), 1009-1022. Y . Boyarintsev, Reguljarnyje i Singularnyje Sistemy Linejnych Obyknovennych Differencial'nych Uravnenij, Nauka (Sibirskoje otdelenije), Novosibirsk, 1980. Y . Boyarintsev, Methods of Solving Singular Systems of Ordinary Differential Equations, John W i l e y &s Sons, 1992 (originally published i n 1988 i n Russian). A . B r a n d t , Multigrid techniques: 1984 guide with applications to fluid dynamics, T h e W e i z m a n n Institute of Science, Rehovot, Israel, 1984. A . Brandt and I. Yavneh, Inadequacy of first order upwind difference schemes for some recirculationflows,J . C o m p . Phys. 93(1991), 128-143. B . Brefort, J . M . Ghidaglia and R . T e m a m , Attractors for the penalized NavierStokes equations, S I A M J . M a t h . A n a l . 19 (1988), 1-21. Bibliography 162 K . Brenan, S. C a m p b e l l and L . Petzold, The numerical solution of higher index differential/algebraic equations by implicit Runge-Kutta methods, S I A M J . N u m e r . A n a l . 26 (1989). F . B r e z z i , J . Douglas, J r . , and L . D . M a r i n i , Two families of mixedfiniteelements for second order elliptic problems, Numer. M a t h . , 47(1985), pp. 217-235. F . B r e z z i , and M . Fortin, Mixed and Hybrid Finite Element Methods, SpringerVerlag, New York, 1991. S.L. C a m p b e l l , Regularizations of linear time varying singular systems, A u t o m a t i c a 20(1984), 365-370. C . Canuto, M . Y . Hussaini, A . Quarteroni and T . A . Zang, Spectral Methods i n F l u i d Dynamics, Springer-Verlag, 1987. P. Carter, Computational methods for the shape from shading problem, P h . D thesis, University of B r i t i s h Columbia, 1993. H . S. C h i n , Stabilization methods for simulations of constrained multibody dynamics, P h . D thesis, University of B r i t i s h C o l u m b i a , 1995. A . J . C h o r i n , Numerical solution of the Navier-Stokes equations, M a t h . C o m p . 22 (1968), 745-762. E . P . Doolan, J . J . H . M i l l e r and W . H . A . Schilders, Uniform Numerical Methods for Problems with Initial and Boundary Layers, D u b l i n , Boole Press, 1980. J . Douglas, J r . , The numerical solution of miscible displacement in porous media, in: Computational Methods i n Nonlinear Mechanics ( J . T . Oden, E d . ) , Amsterdam, N o r t h H o l l a n d , 1980. J . Douglas, J r . , Simulation of miscible displacement in porous media by a modified method of characteristics procedure, i n : Lecture Notes i n M a t h . 912, SpringerVerlag, (1982). J . Douglas, J r . , R . E . E w i n g and M . F . Wheeler, The approximation of the pressure by a mixed method in the simulation of miscible displacement, R A I R O N u m e r . A n a l . 17(1983), pp. 17-33. J . Douglas, J r , R . E . E w i n g and M . F . Wheeler, A time-discretization procedure for a mixed finite element approximation of miscible displacement in porous media. R A I R O Numer. A n a l . 17(1983), pp. 249-265. R . C . D u r a n , On the approximation of miscible displacement in porous media by a method of characteristics combined with a mixed method, S I A M J . N u m e r . A n a l . 25(1988), pp. 989-1001. Bibliography 163 H . W . E n g l , M . Hanke and A . Neubauer, Tikhonov regularization of nonlinear differential-algebraic equations, Institutsbericht N r . 385, Johannes-KeplerUniversitat, Institut fur Mathematik, L i n z , 1989. R . E . E w i n g (Ed.), The Mathematics of Reservoir Simulation, S I A M P h i l a d e l phia, 1983. R . E . E w i n g and T . F . Russell, Efficient time-stepping methods for miscible displacement problems in porous media, S I A M J . Numer. A n a l . 19(1982), pp. 1-67. R . E . E w i n g , T . F . Russell and M . F . Wheeler, Simulation of miscible displacement using mixed methods and a modified method of characteristics, S P E 12241, 7th S P E Symposium on Reservoir Simulation, San Francisco, 1983. R . E . E w i n g , T . F . Russell and M . F . Wheeler, Convergence analysis of an approximation of miscible displacement in porous media by mixedfiniteelements and a modified method of characteristics, C o m p . M e t h . A p p l . M e c h . Engrg. 47(1984), pp. 73-92. R . E . E w i n g and M . F . Wheeler, Galerkin Methods for miscible displacement problems in porous media, S I A M J . Numer. A n a l . 17(1980), pp. 351-365. R . Featherstone, Robot Dynamics Algorithms, Kluwer A c a d e m i c Publishers, Norwell, M A , 1987. M . F o r t i n and R . Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Studies i n Mathematics and Its Applications 15, North-Holland, 1983. C . W . Gear, The simultaneous numerical solution of differential-algebraic equations, I E E E Trans. Circuit Theory, CT-18(1971), 89-95. C . W . Gear, H . H . Hsu and L . Petzold, Differential- algebraic equations revisited, Proc. O D E Meeting, Oberwolfach, Germany, 1981. R . Geel, Singular Perturbations of Hyperbolic Type, M a t h e m a t i c a l Center Tracts 98, A m s t e r d a m , 1978. V . G i r a u l t and P . A . Raviart, Finite Element Methods for Navier-Stokes Equations, Springer, Berlin-Heidelberg 1986. P . M . Gresho, Some current issues relevant to the incompressible Navier-Stokes equations, C o m p u t . Methods A p p l . Mech. Engrg. 87 (1987), 201-252. E . Griepentrog and R . M a r z , Differential-algebraic equations and their numerical treatment, Teubner Texte zur M a t h e m a t i k 88, Leipzig, 1986. Bibliography 164 W . Hackbusch, Multigrid Methods and Applications, Springer-Verlag, B e r l i n , H e i delberg 1985. E . Hairer and G . Wanner, Solving Ordinary Differential Equations II, SpringerVerlag, 1991. M . Hanke, Regularization of differential -algebraic equations revisited, Preprint N r . 92-19, Humboldt- U n i v . B e r l i n , Fachbereich M a t h e m a t i k , 1992. E . J . Haug, Computer-Aided Kinematics and Dynamics of Mechanical Systems Volume I: Basic Methods, A l l y n and Bacon, 1989. P . W . Hemker, A N u m e r i c a l Study of Stiff Two-point Boundary Problems, M a t h ematical Center Tracts 80, A m s t e r d a m 1977. J . G . Heywood, The Navier-Stokes equations: On the existence, regularity and decay of solutions, Indiana U n i v . M a t h . J . , 29 (1980), 639-681. J . G . Heywood and R . Rannacher, Finite element approximation of the nonstationary Navier-Stokes problem, I. Regularity of solutions and second-order error estimates for spatial discretization, S I A M J . Numer. A n a l . 19(1982), 275-311. J . G . Heywood and R . Rannacher, Finite element approximation of the nonstationary Navier-Stokes problem, IV: Error analysis for second-order time discretization, S I A M J . Numer. A n a l . 27 (1990), 353-384. C. Hirsch, A general analysis of two-dimensional convection schemes, V K I Lecture Series 1991-02 on Computational F l u i d Dynamics, V o n K a r m a n Institute, Brussels, B e l g i u m , 1991. T . Y . H o u and B . T . R . Wetton, Convergence of a finite difference scheme for the Navier-Stokes equations using vorticity boundary conditions, S I A M J . Numer. A n a l . , 29 (1992), 615-639. M . K . Kadalbajoo and Y . N . Reddy, Initial-value technique for a class of nonlinear singular perturbation problems, J . O p t i m . Theory and A p p l s . 53(1987), 395-406. L . Kalachev and R . O ' M a l l e y , J r . , The regularization of linear differentialalgebraic equations, S I A M J . M a t h . A n a l . , 1996, to appear. L . Kalachev and R . O ' M a l l e y , J r . , Regularization of nonlinear differentialalgebraic equations, S I A M J . M a t h . A n a l . 25 (1994), 615-629. L . Kalachev and R . O ' M a l l e y , J r . , Boundary value problems for differentialalgebraic equations, N u m . Func. A n a l . A p p l . 16 (1995), 363-378. Bibliography 165 [71] M . Knorrenschild, Differential/algebraic equations as stiff ordinary differential equations, S I A M J . Numer. A n a l . 29 (1992), no. 6, 1694-1715. [72] H . - O . Kreiss and J . Lorenz, Initial-Boundary Value Problems and the NavierStokes Equations, Pure and A p p l i e d Mathematics, V o l . 136, A c a d e m i c Press, 1989. [73] J . Laforgue and R . E . O ' M a l l e y , On the motion of viscous shocks and the supersensitivity of their steady-state limits, Methods and Applications of Analysis 2(1994), 465-487. [74] J . Y . Lee and M . J . W a r d , On the asymptotic and numerical analyses of exponentially ill-conditioned singularly perturbed boundary value problems, Studies i n A p p l i e d M a t h . 94 (1995), 271-326. [75] M . Lees, A priori estimates for the solutions of difference approximations to parabolic partial differential equations, Duke M a t h J . 27 (1960), 297-311. [76] R . J . LeVeque, Numerical Methods for Conservation Laws, Lectures i n M a t h e matics E T H Zurich, Birkhauser Verlag, Basel, 1990. [77] P . L i n , Numerical solutions of some singular perturbation problems, M . Sc. thesis, Nanjing University, Nanjing, C h i n a , 1987. (in Chinese) [78] P . L i n , Remarks on a mildly nonlinear turning point problem, A p p l i e d M a t h . Letters 6(1993), 29-32. [79] P. L i n , A numerical method for quasilinear singular perturbation problems with turning points, C o m p u t i n g 46(1991),155-164. [80] P. L i n , A sequential regularization method for time-dependent incompressible Navier-Stokes equations, S I A M J . Numer. A n a l . , to appear. [81] P. L i n and Y . Su, Numerical solution of quasilinear singularly perturbed ordinary differential equations without turning points, A p p l . M a t h . M e c h . (English E d . ) 10(1989). [82] P . L i n and D . Q . Yang, An iterative perturbation method for the pressure equation in the simulation of miscible displacement in porous media, S I A M J . S c i . C o m p u t . , submitted. [83] J . Lorenz, Combinations of initial and boundary value methods for a class of singular perturbation problems, In: P . W . Hemker and J . J . H . M i l l e r (eds.), N u merical Analysis of Singular Perturbation Problems, London: A c a d e m i c Press, 1979, 295-315. Bibliography 166 [84] P . Lotstedt, On a penalty function method for the simulation of mechanical systems subject to constraints, Royal Inst, of Tech. T R I T A - N A - 7 9 1 9 , Stockholm, 1979. [85] R . M a r z , On tractability with index 2, Preprint 109, H u m b o l d t - U n i v . B e r l i n , Sektion M a t h e m a t i k , 1986. [86] R . M a r z , Numerical methods for differential- algebraic equations, Part I: Characterizing DAEs, Preprint N r . 91-32/1, Humboldt-Universitat z u B e r l i n , 1991. [87] J . Necas, Les methodes directes en theorie des equations elliptiques, A c a d e m i a , Prague, 1967. [88] K . N i i j i m a , On the behavior of solutions of a singularly perturbed boundary value problem with a turning point, S I A M J . M a t h . A n a l . 9(1978), 298-311. [89] R . O ' M a l l e y , J r . , Singular Perturbation Methods for Ordinary Differential Equations, Springer, New York, 1991. [90] E . O ' R i o r d a n and M . Stynes, A globally uniformly convergent finite element method for a singularly perturbed elliptic problem in two dimensions, M a t h . C o m p . 57(1991), 47-62. [91] K . Park and J . C h i o u , Stabilization of computational procedures for constrained dynamical systems, J . of Guidance 11 (1988), 365-370. [92] L . R . Petzold, A brief history of numerical methods for differential-algebraic equations, Lecture notes i n the meeting of the 50th anniversary of the journal " Mathematics of Computations", 1993. [93] L . R . Petzold and P. Lotstedt, Numerical solution of nonlinear differential equations with algebraic constraints II: Practical implications, S I A M J . S c i . Stat. C o m p u t . 7(1986), 720-733. [94] L . R . Petzold, Yuhe R e n and T . M a l y , Numerical solution of differential-algebraic equations with ill-conditioned constraints, Technical Report 93-59, University of Minnesota, 1993 [95] P . Rabier and W . Rheinboldt, On the computation of impasse points of quasilinear differential algebraic equations, M a t h . C o m p . 62 (1994), no. 205, 133-154. [96] R . Rannacher, On Chorin's projection for the incompressible Navier-Stokes equations, In: R a u t m a n n , et al. (eds.): Navier-Stokes equations: Theory and numerical methods. Proc. Oberwolfach Conf., 19.-23.8.1991, Springer, Heidelberg 1992. [97] R . Rannacher, On the numerical solution of the incompressible Navier-Stokes equations, Z . angew. M a t h . M e c h . 73(1993), 203-216. Bibliography 167 [98] T . F . Russell, Finite elements with characteristic finite element method for a miscible displacement problem, S P E 10500, Proc. 6th S P E S y m p o s i u m on Reservoir Simulation, Dallas, 1982. [99] T . F . Russell, Time stepping along characteristics with incomplete iteration for a Galerkin approximation of miscible displacement in porous media, S I A M J . N u m e r . A n a l . 22 (1985), pp. 970-1003. [100] P . A . Raviart and J . M . Thomas, A mixed finite element method for second order elliptic problems, i n : I. Galligani and E . Magenes, Eds., M a t h e m a t i c a l Aspects of the F i n i t e Element M e t h o d , Lecture Notes i n Mathematics 606, Springer-Verlag, B e r l i n and New York, 1977, pp. 292-315. [101] J . Shen, On error estimates of projection methods for the Navier-Stokes equations: First order schemes, S I A M J . Numer. A n a l . 29 (1992), 57-77. [102] D . Sidilkover and U . M . Ascher, A multigrid solver for the steady state NavierStokes equations using the pressure-Poisson formulation, Technical Report 94-3, Dept. of Computer Science, University of B r i t i s h C o l u m b i a , 1994. [103] R . F . Sincovec, A . M . E r i s m a n , E . L . Y i p and M . A . E p t o n , Analysis of descriptor systems using numerical algorithms, I E E E Trans. A u t . C o n t r o l , AC-26(1981), 139-147. [104] D . R . S m i t h and J . T . Palmer, On the behavior of the solution of the telegraphist's equation for large absorption, A r c h . R a t . M e c h . A n a l . 39(1970), 146-157. [105] Y . S u and P. L i n , Numerical solution of singular perturbation problem for hyperbolic differential equation with characteristic boundaries, Proceedings of the B A I L V Conference, Shanghai, Boole Press, Dublin(1988), 20-24. [106] Y . S u and P . L i n , Uniform difference scheme for a singularly perturbed linear 2nd order hyperbolic problem with zero-th order reduced equation, A p p l i e d M a t h . M e c h . 11 (English Ed.)(1990), N o . 4. [107] Y . S u and P . L i n , An exponentially fitted difference scheme for the hyperbolichyperbolic singularly perturbed initial-boundary problem, A p p l i e d M a t h . M e c h . 12 (English Ed.)(1991), 237-245. [108] R . T e m a m , Navier-Stokes Equations, North-Holland, A m s t e r d a m , 1977. [109] A . N . Tikhonov and V . Y a . Arsenin, Methods for Solving Ill-posed Problems, Nauka, Moscow, 1979. [110] S. Turek, Tools for simulating nonstationary incompressibleflowvia discretely divergence-free finite element models, Preprint, Universitat Heidelberg, M a y 1992. Bibliography 168 [111] A . Vasil'eva and V . Butuzov, Asymptotic Expansion of Solutions of Singularly Perturbed Equations, Nauka, Moscow, 1973. [112] A . Vasil'eva and V . Butuzov, Singularly Perturbed Equations in the Critical Case, M R C Technical Summary Report # 2039, 1980. [113] R . Vulanovic, A uniform numerical method for quasilinear singular perturbation problems without turning points, C o m p u t i n g 41(1989), 97-106. [114] R . Vulanovic, On numerical solution of a mildly nonlinear turning point problem, R A I R O M a t h . M o d e l . Numer. A n a l . 24(1990), 765-784 . [115] R . Vulanovic and P . L i n , Numerical solution of quasilinear attractive turning point problems, Computers M a t h . A p p l i c . 23(1992), 75-82. [116] M . W . Walker and D . E . O r i n , Efficient dynamic computer simulation of robotic mechanisms, Journal of D y n a m i c Systems, Measurement, and Control 104 (1982), 205-211. [117] B . Wetton, Error analysis for Chorin's original fully discrete projection method and regularizations in space and time, Preprint, Institute of A p p l i e d M a t h , U n i versity of B r i t i s h C o l u m b i a , 1995. [118] G . B . W h i t h a m , Linear and Nonlinear Waves, Wiley, New York, 1974. [119] W . X i e , A sharp pointwise bound for functions with L -Laplacians and zero boundary values on arbitrary three-dimensional domains, Indiana University M a t h . J . 40 (1991), 1185-1192. 2 [120] D . Q . Yang, Mixed methods with dynamic finite element spaces for miscible displacement in porous media, J . C o m p u t . A p p l . M a t h . 30(1990), pp. 313-328. [121] I. Yavneh, Multigrid techniques for incompressible flows, P h . D . thesis, T h e W e i z m a n n Institute of Science, Israel, 1991.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Regularization methods for differential equations and...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Regularization methods for differential equations and their numerical solution Lin, Ping 1995
pdf
Page Metadata
Item Metadata
Title | Regularization methods for differential equations and their numerical solution |
Creator |
Lin, Ping |
Date Issued | 1995 |
Description | Many mathematical models arising in science and engineering, including circuit and device simulation in VLSI, constrained mechanical systems in robotics and vehicle simulation, certain models in early vision and incompressible fluid flow, lead to computationally challenging problems of differential equations with constraints, and more particularly to high-index, semi-explicit differential-algebraic equations (DAEs). The direct discretization of such models in order to solve them numerically is typically fraught with difficulties. We thus need to reformulate the original problem into a better behaved problem before discretization. Index reduction with stabilization is one class of reformulations in the numerical solution of high index DAEs. Another class of reformulations is called regularization. The idea is to replace a D A E by a better behaved nearby system. This method reduces the size of the problem and avoids the derivatives of the algebraic constraints associated with the D A E . It is more suitable for problems with some sort of singularities in which the constraint Jacobian does not have full rank. Unfortunately, this method often results in very stiff systems, which accounts for its lack of popularity in practice. In this thesis we develop a method which overcomes this difficulty through a combination of stabilization and regularization in an iterative procedure. We call it the sequential regularization method (SRM). Several variants of the S RM which work effectively for various circumstances are also developed. The S RM keeps the benefits of regularization methods and avoids the need for using a stiff solver for the regularized problem. Thus the method is an important improvement over usual regularization methods and can lead to improved numerical methods requiring only solutions to linear systems. The S RM also provides cheaper and more efficient methods than the usual stabilization methods for some choices of parameters and stabilization matrix. We propose the method first for linear index-2 DAEs. Then we extend the idea to nonlinear index-2 and index-3 problems. This is especially useful in applications such as constrained multibody systems which are of index-3. Theoretical analysis and numerical experiments show that the method is useful and efficient for problems with or without singularities. While a significant body of knowledge about the theory and numerical methods for DAEs has been accumulated, almost none of it has been extended to partial differential-algebraic equations (PDAEs). As a first attempt we provide a comparative study between stabilization and regularization (or pseudo-compressibility) methods for DAEs and PDAEs, using the incompressible Navier-Stokes equations as an instance of PDAEs. Compared with stabilization methods, we find that regularization methods can avoid imposing an artificial boundary condition for the pressure. This is a feature for PDAEs not shared with DAEs. Then we generalize the S R M to the nonstationary incompressible Navier-Stokes equations. Convergence is proved. Again nonstiff time discretization can be applied to the S RM iterations. Other interesting properties associated with discretization are discussed and demonstrated. The S RM idea is also applied to the problem of miscible displacement in porous media in reservoir simulation, specifically to the pressure-velocity equation. Advantages over mixed finite element methods are discussed. Error estimates are obtained and numerical experiments are presented. Finally we discuss the numerical solution of several singular perturbation problems which come from many applied areas and regularized problems. The problems we consider are nonlinear turning point problems, a linear elliptic turning point problem and a second-order hyperbolic problem. Some uniformly convergent schemes with respect to the perturbation parameter are constructed and proved. A spurious solution phenomenon for the upwinding scheme is analyzed. |
Extent | 7038853 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-02-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0079749 |
URI | http://hdl.handle.net/2429/4782 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1996-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1996-09118X.pdf [ 6.71MB ]
- Metadata
- JSON: 831-1.0079749.json
- JSON-LD: 831-1.0079749-ld.json
- RDF/XML (Pretty): 831-1.0079749-rdf.xml
- RDF/JSON: 831-1.0079749-rdf.json
- Turtle: 831-1.0079749-turtle.txt
- N-Triples: 831-1.0079749-rdf-ntriples.txt
- Original Record: 831-1.0079749-source.json
- Full Text
- 831-1.0079749-fulltext.txt
- Citation
- 831-1.0079749.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0079749/manifest