On the Regularization and Stabilization ofApproximation Schemes for C0-SemigroupsSimone Flory, Frank Neubrander, and Yu ZhuangAbstract. Many temporal discretization methods for linear evolution equations con-verge uniformly on compact time intervals at the rate1nαonly for sufficiently smoothinitial data. It is shown that these methods can be regularized such that the new schemesconverge ‘in the average’ at the rate1nαfor all initial data. Examples given include theCrank-Nicholson scheme and the alternating direction implicit method.1 Introduction.In this paper, we will consider approximation schemes for abstract initial valueproblemsu(t)=Au(t),t≥ 0,u(0) = f ∈ D(A), (1.1)where A is the generator of a strongly continuous semigroup T (·)onaBanachspaceX with T (t)f≤Mewtf for all t ≥ 0andf ∈ X. In particular, the domainD(A) is a dense subset of X, there exist constants M, w such that R(λ, A):=(λI − A)−1is bounded andR(λ, A)n≤M(λ − w)nfor all λ>w.For simplicity, we will often assume that the spectrum σ(A) of A is strictly con-tained in the left half-plane; i.e., s(A):=sup{Reλ : λ ∈ σ(A)} < 0. For any initialvalue f ∈ D(A), the function u(·):=T (·)f ∈ C1([0, ∞),X) is the unique ‘classi-cal’ solution of (1.1) and, for f ∈ X, the function u(·):=T (·)f ∈ C([0, ∞),X)isthe unique ‘mild’ solution of (1.1); i.e., for any sequence fn∈ D(A)withfn→ f,the corresponding ‘classical’ solutions T (·)fnconverge uniformly on compact timeintervals to T (·)f , which is then a solution of the integral equationu(t)=f + At0u(s) ds, t ≥ 0.Since we will consider approximation schemes which do not necessarily convergeto T (t)f for all f ∈ X but only on D(A) or on a subset of D(A), the followingremark might be useful. In practice, the physically meaningful initial values f andinstantaneous states u(t) of the system described by the initial value problem (1.1)are always contained in D(A), and often even in a true subset (cone) D ⊂ D(A).2 Flory, Neubrander, ZhuangHowever, for the mathematical discussion of (1.1), it is convenient to enlarge D toa linear space (which is then the domain of a linear operator A) and to think ofthe states as points in a (complex) Banach space X, even if the imposed linearity,completeness, and complexity forces us to accept as elements of X some points(functions, vectors) not having direct significance as ‘classical’ states of the physicalsystem. Thus, the consideration of approximation schemes that converge for D ⊂D(A) and not necessarily on X is a meaningful enterprise as long as the schemesare numerically stable.In the study of approximations of the solutions of (1.1), the Chernoff ProductFormula and the Lax Equivalence Theorem are outstanding results on which muchof the theory is based. The basic idea behind these results is the Euler formula;i.e., let {V (t),t ∈ [0,δ]} be a family of linear operators on X with V (0) = I suchthat the consistency conditionV (t)f − ft→ Af, t → 0,f ∈ D ⊂ D(A) (1.2)holds. Then V (t)f ∼ (I + tA)f (t small), or V (tn)nf ∼ (I +tnA)nf ∼ etAf asn →∞. It was shown by Lax and Richtmyer in 1956 [L-R] and Chernoff in 1974[Ch] that these formal considerations are justifiable if the scheme is stable; i.e.,V (t)n≤Meωnt(1.3)for some ω ≥ 0andalln ∈ IN0,t ∈ [0,δ]. The purpose of this paper is to discusslinear (not necessarily bounded) approximation schemes that are consistent (sat-isfy (1.2)) but do not necessarily satisfy (1.3). Examples which will be discussedbelow are the Crank-Nicholson scheme,1the alternating direction implicit method(ADI method) of Peaceman and Rachford, the Lie-Trotter product formula, andthe Strang scheme. In many cases one can show that schemes which do not nec-essarily satisfy (1.3) are regularizable and/or stabilizable in the following sense.An approximation scheme {V (t),t ∈ [0,δ]} is called regularizable if there existsk ∈ IN0and a convergence rate g : IN → IR w i t h g(n) → 0asn →∞such thatV (tn)nf − T (t)f≤g(n)Akf (1.4)for all f ∈ D(Ak)andt ∈ [0,T].2If (1.4) holds, then we will show in Section 3 thatthere exists a convolution norm ||| · ||| on [0,T] and a regularized approximationscheme Vreg(·) such that|||Vreg(·n)nf − T (·)f||| ≤ g(n)f (1.5)1For a discussion of higher order rational approximations, see [F-N-Z].2Recall that we assume that s(A) < 0; in this case Akf is equivalent to the graphnorm f + Akf.Approximation Schemes for C0-Semigroups 3for all f ∈ X,andn ∈ IN. One should notice that the concept of regularization ismeaningful even for stable approximation schemes. For stable schemes, (1.4) andthe density of D(Ak)implythatV (tn)nf − T (t)f→0 (1.6)as n →∞for all f ∈ X, uniformly for t ∈ [0,T]. However, in the step from (1.4)to (1.6) one loses the rate of convergence g(n) for initial data f ∈ X\D(Ak). Incontrast, the rate of convergence is retained in (1.5) for all initial values f ∈ X.In order to obtain estimates of the form (1.4) it is sometimes necessary to stabilizethe approximation scheme first. A consistent approximation scheme {V (t),t ∈[0,δ]}⊂L(X) is called stabilizable if there exists {W (t),t ∈ [0,δ]}⊂L(X)andj, k ∈ IN s u c h t h a tW (tn)jV (tn)n−jf − T (t)f≤g(n)Akf (1.7)for all n ≥ j, f ∈ D(Ak), and t ∈ [0,T], where g(·) is as above. The outlineof the paper is as follows. In Section 2 we review the relation between stability,consistency and convergence and collect some of the known results about theCrank-Nicholson scheme, the ADI method, and the Lie-Trotter product formula.In Section 3 we discuss the regularization principle and stabilization techniqueoutlined above and present some applications.2 Remarks on Consistency and Stability.When an approximate solution of (1.1) is obtained by finite difference methods, thetime variable t assumes discrete values tn:= n∆t (n ∈ IN0), and correspondingly,one obtains a discrete sequence unof approximate states of the physical systemat time n∆t. Thus, single step temporal approximation methodsun= V (∆t)un−1approximate the solution at time n∆t by applying an operator V (∆t)totheap-proximate solution un−1at time (n − 1)∆t; i.e., un= V (∆t)nu0is an approxi-mation of the instantaneous solution u(n∆t) of (1.1), where u0is an approxima-tion of the initial value u(0) = f. In particular, if