CLASSICALLY UNSTABLE APPROXIMATIONS

FOR LINEAR EVOLUTION EQUATIONS AND APPLICATIONS

A Dissertation

Submitted to the Graduate Faculty of the

Louisiana State University and Agriculture and Mechanical College

in partial fullfilment of the requirement for the degree of

Doctor of Philosophy

in

The Department of Mathematics

By Yu Zhuang

B.S. Zhejiang University, July 1990 M.S. Louisiana State University, December 1995

M.S. Louisiana State University, May 1998 August 2000

Acknowledgements

I would like to thank Professor Charles Delzell, Professor Guillermo Ferreyra, Professor John Hildebrant, Professor Bush Jones, Professor Frank Neubrander, and Professor Peter Wolenski for serving on my PhD committee and for the mathematical knowledge and wisdom they imparted to me when I was taking their courses. I would especially like to thank Professor Frank Neubrander for serving as my supervisor, for his interests in and pushing for this project, and for introducing me to the Banach space valued Laplace-Stieljes transform, a tool with which many proofs in this dissertation are built. I also would like to thank Professor Jerome Goldstein for bringing to my attention the work of Butzer, Dickmeis, Nessel, and Weis on stability-with-orders. Most particularly, I would like to thank my mother for taking my role of being father to my two-years old daughter for the two past years so that I had the time to finish this dissertation research.

Table of Contents

Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Notions of Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 An Unstable but Von-Neumann Stable Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.1 The Problem and Its Spatial Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 1.2.2 The Temporal Approximation Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.3 Numerical Testings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3 Outline of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 Spatial Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Stabilized Spatial Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Unstable Spatial Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3 Temporal Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48 3.1 Stabilized Temporal Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 Unstable Temporal Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.1 An Exponential Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2.2 Von-Neumann Stable Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.1 The Unstable but Von Neumann Stable Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.2 ADI-type Factorized Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3 A Domain Decomposition Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Abstract

Temporal discretization methods for evolutionary differential equations that factorize the resolvent into a product of easily computable operators have great numerical appeal. For instance, the alternating direction implicit (ADI) method of Peaceman-Rachford for 2-D parabolic problems greatly reduces the simulation time when compared with the Crank-Nicolson scheme. However, like many other factorized approximation methods that exhibit numerical stability, the ADI method is known to satisfy only the Von Neumann stability condition, a necessary condition that is usually surmised as sufficient in practical cases as pointed out by Lax and Richtmyer. Intensive efforts have been directed to understand the Von Neumann condition, e.g. by John, Lax and Richtmyer, Lax, Lax and Wendroof, and Strang. Their way of investigation is to find conditions under which the Von Neumann condition becomes sufficient for stability. In this dissertation, we found a factorized temporal approximation method and a well-posed problem for which the method is unstable but satisfies the Von Neumann stability condition. However, the method still exhibits excellent numerical stability even for large time step sizes.

Thus, to better understand the Von Neumann condition, we investigate the relation between stability and convergence in directions not covered by the Lax equivalence theorem which equates the stability with convergence for all initial values under some uniform consistency condition. To do that, we extend the Trotter-Kato theorem and the Chernoff product formula to possibly unstable “spatial” and “temporal” approximations and indicate how our results can be used for some unstable factorized approximation methods.

1 Introduction

In this dissertation we consider single step temporal approximation methods for the evolutionary system

\{ \begin{matrix}u′(t) = Au(t), t ≥ 0, \\ u(0) = f ∈D(A), \end{matrix}  (1.1)

where A is a spatial (i.e. independent of time), closed linear operator in a Banach space E, and D(A) denotes the domain of A. Single step temporal approximation methods of the form

u^{n+1} = V (Δt)u^{n}  (1.2)

approximate the solution at time (n+1)Δt by applying an operator V (Δt) to the approximate solution u^{n} at time n Δt, where the solution of equation (1.1) refers to a continuously differentiable function t ↦ u(t) ∈ D(A) which satisfies (1.1). For all approximation procedures, the final goal is “fast” convergence of the approximate solutions to the true solution.

The convergence of the approximate solutions computed by the method (1.2) depends not only on the operators V (Δt), but clearly on the operator A and the regularity of the initial values of the solutions as well. In this dissertation, we restrict ourselves to linear problems which are well-posed (see [9, 17, 28]) in the sense that

• the spatial operator A is densely defined in the Banach space E,

• for each initial value f ∈D(A), there exists a solution u of (1.1), and

• for each solution u of (1.1), for each t > 0, u(t) continuously depends on u(0).

The three conditions above implies (see also [9, 17, 28]) that there exists a strongly continuous family of bounded linear operators S := {S(t) : t ∈ [0, ∞)} which, for each t ≥ 0, maps the initial value f to u(t), the value of the solution at time t. We call this operator family S the C_{0}-semigroup generated by A. The emphases of this dissertation are

• to investigate approximation methods which are stable in senses weaker than the classical one (see below), but still strong enough to imply convergence for a large set of initial values, and

• to investigate “benefits” of weakened stability requirements with regard to the final goal of approximations — “fast” convergence.

Since these “benefits” are the major motivation of this dissertation research, we describe some of them in this introductory chapter.

Before we proceed, we would like to list some additional notations used in this dissertation. The range of an operator A is denoted by R(A), and D(A^{∞}) := ⋂_{n=1}^{∞}D(A^{n}). We denote by L(E) the set of bounded linear operators on a Banach space E. Here we call an operator L bounded if it is bounded on a dense subset of E, and we identify it with its unique bounded extension to E. We denote the everywhere defined (and hence bounded) resolvent of a closed linear operator A by R(λ,A) := (λ−A)^{−1}, and we denote by ρ(A) := {λ ∈ C : (λ − A)^{−1} ∈ L(E)} the resolvent set of A. The letters N, R and C, respectively, denote the set of positive integers, the set of real numbers, and the set of complex numbers. Moreover, N_{0} := N ∪ {0}, and R^{+} := [0, ∞).

1.1 Notions of Stability

It is well known that the convergence of the approximate solutions computed by the method (1.2) depends very much on the stability of the method, that is, the uniform normboundedness of the powers of the operators V (Δt). This dependence was first recognized in 1928 by Courant, Friedrichs and Lewy in their important paper [6], and later characterized (first by Lax in a seminar talk at New York University in January 1954) in the following theorem reformulated from a result in an 1956 paper of Lax and Richtmyer [17].

Theorem (Lax Equivalence Theorem) Let S be the C_{0}-semigroup generated by A. Assume that a strongly continuous one-parameter family of bounded linear operators V := {V (t) : t∈[0, δ]} with V (0) = I satisfies the uniform consistency condition

lim_{Δt→0} \frac{V(Δt)−I}{Δt}S(t)f = AS(t)f  (1.3)

uniformly for t in compact intervals for each f ∈D(A). Then the following statements are equivalent.

( i ) lim_{n→∞}V (t/n)^{n}f = S(t)f uniformly for t∈[0, T] for each T > 0 and f ∈E.

(i i) For any T > 0 and compact subset E_{C} ⊂ E, lim_{n→∞}V (t/n)^{n}f = S(t)f uniformly for (t, f)∈[0, T]×E_{C}.

(iii) The family of bounded operators V is stable in the sense that there exists an increasing positive function M(·) such that for any T > 0

∥V (t)^{n}∥ ≤ M(T)  (1.4)

for those (n, t)∈N×[0, δ] with nt∈[0, T].

Proof: (i)⇒(iii). Let T > 0. Since for each f ∈ E the map t ↦ V (t)f is continuous, we have that for each T > 0 sup{∥V (t)f∥ : t ∈ [0, T] ∩ [0, δ]} < ∞. Then by the uniform boundedness principle (see [38], pp. 201),

sup{∥V (t)∥ : t∈[0, T] ∩ [0, δ]} < ∞.  (1.5)

Now statement (i) menas that for each f ∈E, lim_{n→∞}V (t/n)^{n}f = S(t)f uniformly for t∈[0, T], then we obtain that sup_{t∈[0,T], \frac{t}{n} ≤δ} ∥V (t/n)^{n}f − S(t)f∥ < 1 for all n > N_{f} for some f-dependent integer N_{f} > 0, which implies that

sup_{n>N_{f} ,t∈[0,T], \frac{t}{n}≤δ} ∥V (t/n)^{n}f∥ < 1 + sup_{t∈[0,T]} ∥S(t)f∥.

Now for each f ∈E,

sup_{n∈N,t∈[0,T], \frac{t}{n}≤δ} ∥V (t/n)^{n}f∥ ≤ ( sup_{n>N_{f} ,t∈[0,T], \frac{t}{n}≤δ} + sup_{n≤N_{f} ,t∈[0,T], \frac{t}{n}≤δ} ) ∥V (t/n)^{n}f∥

≤ 1+ sup_{_{t∈[0,T]}, \frac{t}{n}≤δ}∥S(t)f∥ + sup_{_{n≤N_{f} ,t∈[0,T]}, \frac{t}{n}≤δ}∥V (t/n)^{n}f∥

≤ 1+ sup_{_{t∈[0,T]}, \frac{t}{n}≤δ}∥S(t)f∥ + sup_{_{n≤N_{f} ,t∈[0,T]}, \frac{t}{n}≤δ}∥V (t)∥^{n}∥f∥.

Then it follows from (1.5) and the C_{0}-semigroup properties of S that

sup_{(n,t)∈N×[0,T]} ∥V (t/n)^{n}f∥ < ∞.

By the uniform boundedness principle, sup_{(n,t)∈N×[0,T]} ∥V (t/n)^{n}∥ < ∞.

Now for each T ≥ 0, let S_{T} := {(n, t) ∈ N×[0, T] : t/n ≤ δ}, and define a positive function M : T ↦ M(T) = sup_{(n,t)∈S_{T}} ∥V (t/n)^{n}∥. Since S_{T} ⊂ S_{T′} for T < T′, the function M(·) is increasing. Let (n, t) ∈ N×[0, δ] with nt ∈ [0, T]. Then (n, nt) ∈ S_{T}. Thus, by the definition of the function M(·),

∥V (t)^{n}∥ = ∥V (nt/n)^{n}∥ ≤ M(T),

which is statement (ii).

(iii)⇒(ii). For f ∈D(A), T > 0, and (n, t)∈N×[0, δ] with t ≤ T,

\begin{aligned}∥V (t/n)^{n}f − S(t)f∥ & = & ∑_{i=1}^{n} ∥V (t/n)^{i−1}[V (t/n) − S(t/n)]S(\frac{n−i}{n}t)f∥ \\ & ≤ & ∑_{i=1}^{n} M(T)∥[V (t/n) − S(t/n)]S(\frac{n−i}{n}t)f∥, \end{aligned}

where the last inequality is due to the stability condition (1.4). Then, from the above inequality, we can further obtain

\begin{aligned}∥V(\frac{t}{n})^{n}f −S(t)f∥ & ≤ \frac{t}{n} ∑_{i=1}^{n}M(T)∥[(\frac{V( \frac{t}{n})−I}{t/n} −A)−(\frac{S( \frac{t}{n})−I}{t/n} −A)]S(\frac{n−i}{n}t)f∥ \\ & ≤ tM(T) sup_{1≤i≤n} ∥[(\frac{V( \frac{t}{n})−I}{t/n} −A)−(\frac{S( \frac{t}{n})−I}{t/n} −A)]S(\frac{n−i}{n}t)f∥ \\ & ≤ T M(T) sup_{1≤i≤n} ∥[(\frac{V( \frac{t}{n})−I}{t/n} −A)−(\frac{S( \frac{t}{n})−I}{t/n} −A)]S(\frac{n−i}{n}t)f∥. \end{aligned}  (1.6)

From the uniform consistency condition (1.3), it follows that

lim_{n→∞} sup_{1≤i≤n} ∥(\frac{V (t/n)−I}{t/n} −A) S(\frac{n−i}{n}t)f∥ = 0.  (1.7)

The C_{0}-semigroup S also satisfies the uniform consistency condition, since for each f ∈D(A) and T > 0,

∥\frac{S(Δt)−I}{Δt}S(t)f −AS(t)f∥ = ∥S(t) (\frac{S(Δt)−I}{Δt}f − Af) ∥
≤ sup_{t∈[0,T]} ∥S(t)∥ · ∥\frac{S(Δt)−I}{Δt}f − Af∥.

Then we have that lim_{n→∞} sup_{1≤i≤n} ∥(\frac{S(t/n)−I}{t/n} −A) S(\frac{n−i}{n}t)f∥ = 0, which, together with (1.7),

implies that lim_{n→∞} ∥[(\frac{V (t/n)−I}{t/n} −A) − (\frac{S(t/n)−I}{t/n} −A)] S(\frac{n−i}{n}t)f∥ = 0. We obtain from (1.6)

that for f ∈D(A),

lim_{n→∞} ∥V (t/n)^{n}f − S(t)f∥ = 0  (1.8)

uniformly for t∈[0, T].

For n ∈ N and t ∈ [0, δ], let L_{n}(t) = V (t/n)^{n} − S(t). Then, the uniform convergence in (1.8) implies that lim_{n→∞} L_{n}(t)f = 0 uniformly for t∈[0, T] for each f ∈D(A). And the stability condition (1.4) provides us the inequality ∥L_{n}(t)∥ ≤ 2M(T). Now, for a compact subset E_{C}, and ϵ > 0, there exist k = k(ϵ) elements f_{1}, f_{2}, ⋯, f_{k} ∈ E_{C} such that for any f ∈ E_{C}, there exists f_{i_{f}} ∈ {f_{1}, f_{2}, ⋯, f_{k}} with ∥f − f_{i_{f}} ∥ ≤ ϵ/8M(T). Since D(A) is dense in E,

there exist g_{1}, g_{2}, ⋯, g_{k} ∈D(A) such that sup_{1≤i≤k} ∥g_{i} − f_{i}∥ ≤ ϵ/8M(T). Since lim_{n→∞} L_{n}(t)f = 0

uniformly for t ∈ [0, T] for each f ∈ D(A), it follows that lim_{n→∞} sup_{1≤i≤k} ∥L_{n}(t)g_{i}∥ = 0 uniformly for t∈[0, T]. Then there exists N = N(ϵ) such that for n ≥ N, sup_{t∈[0,T]} sup_{1≤i≤k} ∥L_{n}(t)g_{i}∥ < ϵ/2. Now, for f ∈E_{C}, t∈[0, T], and n ≥ N(ϵ),

sup_{t∈[0,T]} ∥L_{n}(t)f∥ ≤ sup_{t∈[0,T]} [∥L_{n}(t)(f −f_{i_{f}})∥ + ∥L_{n}(t)(f_{i_{f}} −g_{i_{f}})∥ + ∥L_{n}(t)g_{i_{f}} ∥]
≤ sup_{t∈[0,T]} [∥L_{n}(t)∥ · (∥f −f_{i_{f}} ∥ + ∥f_{i_{f}} −g_{i_{f}} ∥) + sup_{1≤i≤k} ∥L_{n}(t)g_{i}∥]
≤ 2M(T)[ϵ/8M(T) + ϵ/8M(T)] + ϵ/2
= ϵ,

which proves statement (ii).

(ii)⇒(i). The implication is obvious.

Statement (iii) of the Lax equivalence theorem is the classical definition of stability for general time dependent problems. Now we give two characterizations of it.

Lemma 1.1 Let {V (t) : t ∈ [0, δ]} be a one-parameter family of bounded linear operators with V (0) = I. The following statements are equivalent.

( i ) There exists an increasing positive function M(t) such that ∥V (t)^{n}∥ ≤ M(nt) for all (n, t)∈N×[0, δ].

(i i) There exists an increasing positive function M(·) such that ∥V (t)^{n}∥ ≤ M(T) for any T > 0 and (n, t)∈N×[0, δ] with nt∈[0, T].

(iii) There exist δ-dependent positive constants G and ω such that for all t∈[0, δ],

∥V (t)^{n}∥ ≤ G e^{nωt}.  (1.9)

Proof: (i)⇒(ii): Let T > 0. For (n, t)∈N×[0, δ] with nt∈[0, T], statement (i) implies that ∥V (t)^{n}∥ ≤ M(nt). Since M(t) is an increasing function of t, it follows that M(nt) ≤ M(T).

(ii)⇒(iii): The inequality (1.9) obviously holds for t = 0. So, we proceed to prove (1.9) for the case t > 0.

Let T = 2δ, and let ω = \frac{2}{T} ln M(T). Then e^{0.5ωT} = M(T). It follows from statement (ii) that ∥V (t)^{[ \frac{T}{t} ]}∥ ≤ M(T) since [\frac{T}{t}]t ≤ T, where [\frac{T}{t}] denotes the largest integer less than \frac{T}{t}. But e^{0.5ωT} = M(T), so we have

∥V (t)^{[ \frac{T}{t} ]}∥ ≤ e^{0.5ωT} ≤ e^{[ \frac{T}{t} ]· \frac{0.5ωT}{T/t−1}} = e^{[ \frac{T}{t} ]· \frac{0.5ωT t}{T −t}} .

Since T = 2δ, we obtain from the above inequality that

∥V (t)^{[ \frac{2δ}{t}]}∥ ≤ e^{[ \frac{2δ}{t}]· \frac{ωδt}{2δ−t}} ≤ e^{[ \frac{2δ}{t}]· \frac{ωδt}{2δ−δ}} = e^{[ \frac{2δ}{t}]ωt},

where the second inequality holds because t ≤ δ. For notational simplicity, let N = N(δ, t) := [\frac{2δ}{t}]. Then the above inequality becomes

∥V (t)^{N}∥ ≤ e^{Nωt}.  (1.10)

Now, for any n∈N, there exist k, m∈N_{0} such that n = kN + m and m < N. Thus,

∥V (t)^{n}∥ = ∥V (t)^{kN+m}∥ ≤ ∥V (t)^{N}∥^{k} · ∥V (t)^{m}∥.  (1.11)

Since m < N = [\frac{2δ}{t}] < \frac{2δ}{t}, we obtain that mt ≤ 2δ. Then it follows from statement (ii) that ∥V (t)^{m}∥ ≤ M(2δ), which, together with (1.11), implies that

∥V (t)^{n}∥ ≤ M(2δ)∥V (t)^{N}∥^{k}.

Now, it follows from (1.10) that ∥V (t)^{n}∥ ≤ M(2δ)e^{kNωt} ≤ M(2δ)e^{nωt}. Setting G = M(2δ), we obtain statement (iii) from the above inequality.

(iii)⇒(i): Statement (i) follows by setting M(t) = G e^{ωt}.

Now with this lemma, we obtain the following theorm concerning the equivalence of the convergence and stability under a consistency condition weaker and much easier to check than the uniform consistency condition in the Lax equivalence theorem.

Theorem 1.1 Let S be the C_{0}-semigroup generated by A. Assume that a strongly continuous one-parameter family of bounded linear operators V := {V (t) : t∈[0, δ]} with V (0) = I satisfies the consistency condition

lim_{t→0} \frac{V(t)−I}{t}f = Af  (1.12)

for each f ∈D(A). Then the following statements are equivalent.

( i ) lim_{n→∞}V (t/n)^{n}f = S(t)f uniformly for t∈[0, T] for each T > 0 and f ∈E.

(i i) The family of bounded operators V is stable in the sense of (1.4).

Proof: (i)⇒(ii). In part (i)⇒(iii) of the proof of the Lax equivalence theorem, we did not use the uniform consistency condition at all, which means that the implication (i)⇒(ii) of this theorem also holds.

(ii)⇒(i). By Lemma 1.1, the stability of V implies its exponential stability. Then under the consistency condition (1.12), the implication in this direction follows from the Chernoff product formula [7] (also see Chapter 3).

In view of the equivalence of the stability of the method (1.2) and the convergence of the method for all initial values in the space E under the consistency condition (1.12), there are two possible ways to proceed without risking losing convergence while weakening stability. They are

• strengthening the consistency condition (1.12), and/or

• restricting the set of initial values for which the approximation methods will converge.

In this dissertation, we choose to restrict the set of initial values instead of trying to strengthen the consistency. Let us explain why such a restriction is both practically acceptable and mathematically appropriate.

It is usually the case in actual numerical computations or in the mathematical study of Cauchy problems modeled from evolutionary systems in sciences or engineering that the initial values of the problem are in the domain of A. It is well-known that when the initial value f is not in the domain of A, the meaning of the solution of the Cauchy problem (1.1) has to be interpreted in the temporally non-differential sense of mild solutions (see [9, 28]). Thus, if one is interested only in classical solutions, then one needs convergence only for initial values in D(A). This allows one to consider stability requirements which are possibly weaker than the one in the Lax equivalence theorem. For example, Butzer and Weis [4], and Butzer, Dickmeis and Nessel [5] have considered stability and convergence in this direction. They introduced a weakened notion of stability which they called stability-with-orders.

Definition 1.1 An approximation method {V (t) : t ∈ [0, δ]} of bounded linear operators with V (0) = I is said to be stable of order β ≥ 0 (or β-stable for short) if there exists an increasing positive function M(·) such that for all t∈(0, δ] and n∈N,

∥V^{n}(t)∥ ≤ t^{−β}M(nt).  (1.13)

With the introduction of this “stability with orders” condition, they showed that a β-stable approximation method V (t) converges for all initial values in a subset S ⊂D(A) if, for some α > β, V (t) is uniformly consistent of order α on the set S ⊂ E in the sense that for each T > 0 and f ∈S, there exists a constant C_{T,f} > 0 such that for all t∈[0, T] and Δt in a neighborhood of of 0, ∥V (Δt)S(t)f −S(t+Δt)f∥ ≤ C_{T,f} · (Δt)^{α+1}.

With the introduction of this notion of weaker stability, Butzer, Dickmeis, Nessel and Weis furthered the understanding of the relation between stability and convergence established in the Lax equivalence theorem. Besides the mathematical significance, weakening stability requirements also has practical computation benefits. A weaker stability requirement allows one to design more flexible approximation methods which might be advantageous in other aspects. One example is the alternating direction implicit (ADI) method

V_{ADI}(t) := (I − \frac{t}{2}A_{1})^{−1}(I − \frac{t}{2}A_{2})^{−1}(I + \frac{t}{2}A_{2})(I + \frac{t}{2}A_{1})  (1.14)

proposed by Peaceman and Rachford [29] for two dimensional parabolic problems where A is split into directional components A = A_{1} + A_{2} with D(A)⊂D(A_{i}) for i = 1, 2. The ADI method is an approximate factorization of the second order Crank-Nicolson method

V_{CN}(t) := (I − \frac{t}{2}A)^{−1}(I + \frac{t}{2}A),  (1.15)

where an approximation method V := {V (t) : t ∈ [0, δ]} is called to be of p-th order accurate if there exists a set D(A^{p})⊂E dense in E such that for each f ∈D, there exists a constant C > 0 such that for t in a neighborhood of of 0,

∥V (t)f − S(t)f∥ ≤ C · t^{p+1}.  (1.16)

The Crank-Nicolson method is well known to be of second order. This can be seen by expanded the solution S(t)f and the Crank-Nicolson approximation V_{CN}(t)f into Taylor series upto the third derivatives. The ADI method is an approximation to the Crank-Nicolson method, but it attains the same order of accuracy. The significance of the order of accuracy can be seen from the following proposition for methods that commute with the operator A. For more general results, see Lax’s [16] and Butzer and Weis’ [4].

Proposition 1.1 Let S be the C_{0}-semigroup generated by A satisfying the stability condition ∥S(t)∥ ≤ Me^{ωt} for some positive constants M, ω independent of t. Let V := {V (t) : t ∈ [0, δ]} with V (0) = I be a strongly continuous one-parameter family of bounded linear operators satisfying the stability condition ∥V (t)^{n}∥ ≤ Me^{ntω} for all n ∈ N and t ∈ [0, δ]. Suppose that V is of p-th order for the evolutionary system (1.1) on D(A^{p+1}). Then, for each f ∈D(A^{p+1}), there exists a positive constant C such that

\overline{lim}_{n→∞} \frac{∥V (t/n)^{n}f − S(t)f∥}{(t/n)^{p}} ≤ C

if for each t ≥ 0, V (t)Af = AV (t)f for all f ∈D(A^{p+1}).

Proof: Let f ∈D(A^{p+1}). Since V (t) and A commute for all t ≥ 0, it can be easily verified that V (t) and S(t) also commute. Then,

\begin{aligned}∥V (t/n)^{n}f − S(t)f∥ & = & ∥ ∑_{i=1}^{n} V (t/n)^{n−i}[V (t/n) − S(t/n)]S(t/n)^{i−1}f \\ & = & ∥ ∑_{i=1}^{n} V (t/n)^{n−i}S(t/n)^{i−1}[V (t/n) − S(t/n)]f∥, \end{aligned}

where the last equality is due to the commutativity of V (t) and S(t). Then the stability conditions of S and V imply that

\begin{aligned}∥V (t/n)^{n}f − S(t)f∥ & ≤ & ∥ ∑_{i=1}^{n} Me^{(n−i)ωt/n}Me^{(i−1)ωt/n}∥[V (t/n) − S(t/n)]f∥ \\ & ≤ & M^{2}e^{ωt} ∑_{i=1}^{n} ∥[V (t/n) − S(t/n)]f∥ \\ & ≤ & M^{2}e^{ωt} ∑_{i=1}^{n} C_{f}(t/n)^{p+1}, \end{aligned} (1.17)

where the last inequality is due to the p-th order accuracy of V, and C_{f} is a positive constant dependent upon f. Since ∑_{i=1}^{n} C_{f}(t/n)^{p+1} = tC_{f}(t/n)^{p}, it follows from (1.17) that

∥V (t/n)^{n}f − S(t)f∥ ≤ t C_{f}M^{2}e^{ωt}(t/n)^{p},

from which the conclusion of this proposition follows immediately.

While it retains the same order as that of the Crank-Nicolson method on D(A^{3}), the ADI method (1.14) reduces the computation of the 2-D operator (I−\frac{t}{2}A)^{−1} to that of two 1-D operators (I−\frac{t}{2}A_{1})^{−1} and (I−\frac{t}{2}A_{2})^{−1}, resulting in great computation reduction especially when A is not self-adjoint. And this computation reduction does not come at the expense of numerical instability, as exhibited by numerical errors as small as those of the stable (see Chapter 4) Crank-Nicolson method. However, when the two components A_{1} and A_{2} do not commute, it is unknown if the ADI method is stable or β-stable, even though in this case it still exhibits perfect numerical stability. It will be proven in Chapter 4 that when each component A_{i} with D(A) ⊂ D(A_{i}) satisfies the quasi-dissipative condition ⟨A_{i}f, f⟩ ≤ ω∥f∥^{2} for some constant ω and for all f ∈ D(A_{i}), the ADI method satisfies the Von Neumann stability condition

lim_{n→∞}^{n} \sqrt{∥V_{ADI}(t)^{n}f∥} ≤ e^{ω′ t}, for t∈[0, δ] and f ∈D(A)  (1.18)

for some constant ω′ > ω and an ω-dependent constant δ > 0. A more detailed definition and historical background of this here newly introduced notion of stability are given below.

Another example of approximation methods with weakened stability but significant computation benefits is a domain decomposition based factorized temporal approximation method introduced by the author in his computer science dissertation proposal [40]. This method is both computationally and communicationally efficient for large scale parallel computing on distributed memory architecture machines. It exhibits excellent numerical stability, and satisfies the Von Neumann stability under certain assumptions (see Chapter 4). However, it is unknown if this method is stable or β-stable.

The Von Neumann stability condition (1.18) is usually stated only for methods for spatially discretized problems (see [17, 16, 18, 32]) in finite dimensional spaces E_{h}; i.e. for

\{ \begin{matrix}u′_{h}(t) = A_{h}u_{h}(t), t ≥ 0 \\ u_{h}(0) = f_{h} ∈E_{h}, \end{matrix}  h∈(0, ϵ)  (1.19)

where {E_{h} : h ∈ (0, ϵ)} is a family of finite dimensional spaces approximating E in some sense, and {A_{h} : E_{h} → E_{h}, h∈(0, ϵ)} is a family of bounded linear operators approximating A is some sense. A temporal approximation method {V (t; A_{h}) : (t, h)∈[0, δ]×(0, ϵ)} for the spatially discrete problem (1.19) is said to satisfy the Von Neumann stability condition if the spectral radii r(V (t; A_{h})) := \overline{lim}_{n→∞}∥V (t; A_{h})^{n}∥^{1/n} of V (t; A_{h}) satisfy

r(V (t; A_{h})) ≤ e^{ωt} for all (t, h)∈[0, δ′]×(0, ϵ)  (1.20)

for some constants ω ≥ 0 and δ′ ∈(0, δ].

This spectral-radius based definition of Von Neumann stability is obviously extendible to an approximation method V (t; A) in a Banach space when the operators V (t; A)^{n} are bounded for all n large enough. However, the requirement that V (t; A)^{n} are bounded operators for sufficiently large n is too restrictive. Take the ADI method (1.14) for example. The ADI method V_{ADI}(t; A_{h}) for the spatially discrete problem (1.19) satisfies the Von Neumann stability condition (1.20) when A_{h,1} and A_{h,2} retain the quasi-dissipativity of A_{1} and A_{2}. But in general, the operators V_{ADI}(t; A)^{n} are not necessary bounded for n large enough (see Section 1.2). Thus, in order to deal with approximation methods in Banach spaces without recourse to spatial discretization, but still able to accommodate numerically perfectly stable methods like the ADI, we are not going to impose the boundedness restriction on the operator V (t; A)^{n} for sufficiently large n. Hence, we generalize the usual Von Neumann stability condition (1.20) to approximation methods in general Banach spaces in the following sense.

Definition 1.2 An approximation method {V (t):t∈[0, δ]} of linear operators V (t) defined on a set D ⊂ E is said to satisfy the Von Neumann stability condition on D if there exist constants ω ≥ 0 and δ′ ∈(0, δ] such that for all t∈[0, δ′] and f ∈D,

lim_{n→∞}^{n} \sqrt{∥V (t)^{n}f∥} ≤ e^{ω t}.  (1.21)

An approximation method V is said to satisfy the Von Neumann stability condition if V satisfies the Von Neumann stability condition on some dense subset of E.

It is obvious that this definition of the Von Neumann stability condition coincides with the spectral radius based definition when {V (t) : t ∈ [0, δ]} is a family of bounded operators. It is well known that stable methods consisting of bounded operators satisfy the Von Neumann stability condition in the sense that r(V (t)) ≤ e^{ωt} for some constant ω ≥ 0 for t in a neighborhood of 0 [17]. Now, with the characterizations given in Lemma 1.1, we have the following stronger result. The proof is obvious and thus omitted.

Corollary 1.1 Suppose that a temporal approximation method {V (t) : t ∈ [0, δ]} is stable in the classically sense of Lemma 1.1. Then there exists a constant ω ≥ 0 such that r (V (t)) ≤ e^{ωt} for all t∈[0, δ].

This corollary states that the Von Neumann stability condition is a necessary condition for stability. Since there has been no observed numerical “misfortune” of any Von Neumann stable approximation method in practical computations, it is surmised, as pointed out by Lax and Richtmyer in [17], that the Von Neumann stability condition (1.20) is also sufficient for stability. Intensive research has been carried out to find conditions under which the Von Neumann condition becomes sufficient for stability, e.g. by F. John [12], Lax and Richtmyer [17], Lax [16], Lax and Wendroff [18], and Strang [32]. However, to our knowledge the question if the Von Neumann stability condition (1.20) itself is sufficient for stability has remained open, until now.

1.2 An Unstable but Von-Neumann Stable Method

In this section we present an example in which a consistent factorized temporal approximation method satisfies the Von Neumann stability condition in both the usual sense (1.20) and the newly introduced sense (1.21), but is not stable in the classical sense (1.4) or in the stability-with-orders’ sense (1.13). This shows that the Von Neumann condition is not sufficient for stability. However, the method still exhibits excellent numerical stability as indicated by measured errors in Tables 1 and 2 (see Section 1.2.3), and the measured errors are even smaller than those of approximated solutions computed using the stable implicit method.

1.2.1 The Problem and Its Spatial Approximation

Let Ω = [0, π]. Let E denote the real Hilbert space E := {f ∈L^{2}(Ω) :f(0)=f(π)=0} with the L^{2} inner product. It is known that every function f in this space has a Fourier series expansion f = ∑_{k∈N} ⟨f, e_{k}⟩ e_{k}, where {e_{k}}_{k∈N} is an orthonormal basis consisting of the functions e_{k}(x) := \sqrt{\frac{2}{π}} sin(kx). Let A_{1} denote the differential operator A_{1}f = f′′(x) on the domain D(A_{1}) := {f ∈E : ∑_{k∈N} |k^{2} ⟨f, e_{k}⟩|^{2} < ∞}. It is easily verifiable that

A_{1}e_{k} = −k^{2}e_{k} for all k ∈N,  (1.22)

which implies that that A_{1} is dissipative and hence generates a contraction semigroup. Then the Hille-Yosida theorem implies that

∥(I − tA_{1})^{−1}∥ ≤ 1 for all t ≥ 0.  (1.23)

From the dissipativity of A_{1}, we also have that

∥(I + tA_{1})(I − tA_{1})^{−1}∥ ≤ 1 for all t ≥ 0,  (1.24)

since for all f ∈D(A),

∥(I + tA_{1})f∥^{2} = ∥f∥^{2} + 2tRe ⟨A_{1}f, f⟩ + t^{2}∥A_{1}f∥^{2}
≤ ∥f∥^{2} − 2tRe ⟨A_{1}f, f⟩ + t^{2}∥A_{1}f∥^{2}
= ∥(I − tA_{1})f∥^{2}.

Define an operator A_{2} by

A_{2}f := ∑_{k=1}^{∞} ⟨f, e_{k^{2}}⟩ e_{k}.  (1.25)

By the Parseval equation ∥ ∑ a_{k}e_{k}∥^{2} = ∑ |a_{k}|^{2} for all f = ∑_{k} a_{k}e_{k} ∈ E. Then, we have that ∥A_{2}f∥^{2} = ∑_{k=1}^{∞} | ⟨f, e_{k^{2}}⟩ |^{2} ≤ ∑_{k=1}^{∞} | ⟨f, e_{k}⟩ |^{2} = ∥f∥^{2}, which shows that ∥A_{2}∥ ≤ 1 and hence

∥I + tA_{2}∥ ≤ 1 + t.  (1.26)

Define an operator A on D(A_{1}) by Af := A_{1}f + A_{2}f. Then, A generates a C_{0}-semigroup since A_{1} generates a contraction semigroup and A_{2} is bounded (see Theorem I.6.4, [9]).

For n ∈ N, we choose the discrete space Ω_{n} := \{\frac{kπ}{n} : k = 0, 1, ⋯, n\}. Define, as a counterpart of E, a finite dimensional function space E_{n} on this discretized domain Ω_{n} by E_{n} := {f ∈L^{2}(Ω_{n}) : f(0) = f(π) = 0} , with the inner product defined as ⟨f, g⟩_{n} = \frac{π}{n} ∑_{k=1}^{n−1} f(\frac{kπ}{n}) g(\frac{kπ}{n}). Define a projection operator P_{n} : E → E_{n} by (P_{n}f)(x) = f(x) for f ∈ E and x∈Ω_{n}. With the discrete domain and function space in place, we will now discretize the two operators A_{1} and A_{2}. We first choose an orthonormal basis of E_{n}. For k = 1, 2, ⋯, n − 1, let e_{n,k} := P_{n}e_{k} = \sqrt{\frac{2}{π}} sin(kx) for x ∈ Ω_{n}. Then, ∥e_{n,k}∥ = 1 for k ∈ {1, 2, ⋯, n−1} since

∥e_{n,k}∥^{2} = \frac{π}{n} ∑_{x=1}^{n−1} \frac{2}{π} sin^{2}(kxπ/n)
= \frac{2}{n} ∑_{x=0}^{n−1} \frac{1−cos(2kxπ/n)}{2}
= 1 − \frac{1}{n} ∑_{x=0}^{n−1} cos(2kxπ/n)
= 1 − \frac{1}{n} Re ∑_{x=0}^{n−1} e^{i \frac{2kxπ}{n}}
= 1 − \frac{1}{n} Re\frac{1−e^{i \frac{2kπ}{n} ·n}}{1−e^{i \frac{2kπ}{n}}} = 1.

To see that

⟨e_{n,j}, e_{n,k}⟩ = 0 for j, k ∈{1, 2, ⋯, n−1}, j ≠k,  (1.27)

we first examine the case when j −k is an odd number. In this case j +k is also an odd number. Since 2 sin(α) · sin(β) = cos(α − β) + cos(α − β),

⟨e_{n,j}, e_{n,k}⟩ = \frac{2}{n} ∑_{x=1}^{n−1} sin(jxπ/n) sin(kxπ/n)
= \frac{1}{n} ∑_{x=1}^{n−1} [cos \frac{(j−k)xπ}{n} − cos \frac{(j+k)xπ}{n} ]
= \frac{1}{2n}∑_{x=1}^{n−1}[cos \frac{(j−k)xπ}{n} +cos \frac{(j−k)(n−x)π}{n} −cos \frac{(j+k)xπ}{n} −cos \frac{(j+k)(n−x)π}{n}]
= \frac{1}{2n}∑_{x=1}^{n−1}[cos \frac{(j−k)xπ}{n} −cos \frac{(j−k)xπ}{n} − cos \frac{(j+k)xπ}{n} + cos \frac{(j+k)xπ}{n}]
= 0.

Next, we examine the case when j −k is a non-zero even number. In this case j +k is a positive even number. So,

⟨e_{n,j}, e_{n,k}⟩ = \frac{2}{n} ∑_{x=0}^{n−1} sin(jxπ/n) sin(kxπ/n)
= \frac{1}{n} ∑_{x=0}^{n−1} [cos \frac{(j−k)xπ}{n} − cos \frac{(j+k)xπ}{n} ]
= \frac{1}{n} Re ∑_{x=0}^{n−1} [e^{i(j−k)xπ/n} − e^{i(j+k)xπ/n}]
= \frac{1}{n} Re [\frac{1−e^{i(j−k)π}}{1−e^{i \frac{(j−k)π}{n}}} − \frac{1−e^{i(j+k)π}}{1−e^{i \frac{(j+k)π}{n}}} ]
= 0.

Now on E_{n}, we use the commonly used central finite difference to discretize A_{1}, yielding

A_{n,1} := (\frac{n}{π})^{2} ( \begin{matrix}−2 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & −2 & 1 & ⋯ & 0 & 0 & 0 \\ · & · & · & ⋯ & · & · & · \\ 0 & 0 & 0 & ⋯ & 1 & −2 & 1 \\ 0 & 0 & 0 & ⋯ & 0 & 1 & −2 \end{matrix} ) .

It was observed in Hockney’s famous Fast Poisson Solver paper [10] that

A_{n,1}e_{n,k} = −a_{n,k} e_{n,k},  (1.28)

where a_{n,k} := \frac{2−2 cos \frac{kπ}{n}}{(π/n)^{2}} > 0. To see this equality, let v_{i}(i = 0, 1, ⋯, n−1) denote the i-th entry in the vector v := A_{n,1}e_{n,k}. By definition,

v_{i} = (n/π)^{2}\sqrt{2/π} [sin \frac{k(i−1)π}{n} − 2 sin \frac{kiπ}{n} + sin k(i + 1)πn] .

Notice that this equality also holds for i=1 and i=n−1 since sin \frac{k(1−1)π}{n} = sin \frac{k(n−1+1)π}{n} = 0. Then, we have that v_{i} = sin \frac{kiπ}{n} [2 cos(kπ/n)−2] = −a_{n,k} e_{n,k}. Since a_{n,k} > 0, A_{n,1} retains the dissipativity of A_{1}. From the dissipativity of A_{n,1}, we have that

∥(I − tA_{n,1})^{−1}∥ ≤ 1 and ∥(I −tA_{n,1})^{−1}(I +tA_{n,1})∥ ≤ 1  (1.29)

for all t ≥ 0. For the operator A_{2}, we use the discretization

A_{n,2} f := ∑_{k=1}^{k^{2}<n} ⟨f, e_{n,k^{2}}⟩ e_{n,k} for f ∈E_{n}.  (1.30)

Since {e_{n,k}}_{k=1}^{n−1} is an orthonormal basis of E_{n}, it follows that A_{n,2} is bounded by 1 and hence

∥I + tA_{2}∥ ≤ 1 + t.  (1.31)

1.2.2 The Temporal Approximation Method

Define temporal approximation methods V (t; A) and V (t; A_{n}) for n∈N by

\{ \begin{matrix}V (t; A) f & := & (I − \frac{t}{2}A_{1})^{−1}(I + tA_{2})(I + \frac{t}{2}A_{1})f, \\ V(t; A_{n})P_{n}f & := & (I − \frac{t}{2}A_{n,1})^{−1}(I +tA_{n,2})(I + \frac{t}{2}A_{n,1})P_{n}f. \end{matrix}  (1.32)

for f ∈D(A) and t∈[0, 1]. We shall show that

(a) V (t; A) is consistent for f ∈D(A) in the sense of (1.12);

(b) V (t; A)^{n} is unbounded for all (n, t)∈N×(0, 1];

(c) {V (t; A) : t∈[0, 1]} satisfies the Von Neumann stability condition (1.20) on D(A) for all t∈[0, 1]; (d) V (t; A_{n}) is not unconditionally stable, where the unconditional stability of the

temporal approximation method {V (t; A_{n}) : (n, t) ∈ N×[0, ∞)} means the existence of a constant δ ∈ [0, 1] and an increasing function M(·) on [0, ∞) such that for all n, k ∈N and t∈[0, δ],

∥V (t; A_{n})^{k}∥_{n} ≤ M(kt);

(e) {V (t; A_{n}) : t∈[0, 1], n∈N} satisfies the Von Neumann stability condition (1.20).

Proof: (a) For f ∈D(A),

V (t; A)f − f = (I − \frac{t}{2}A_{1})^{−1}(I +tA_{2})(I + \frac{t}{2}A_{1})f − f
= (I − \frac{t}{2}A_{1})^{−1}[(I +tA_{2})(I + \frac{t}{2}A_{1}) − (I − \frac{t}{2}A_{1})]f
= t(I − \frac{t}{2}A_{1})^{−1}[A + \frac{t}{2}A_{2}A_{1}]f.

Thus we have that

\frac{V (t;A)f−f}{t} −Af = [(I − \frac{t}{2}A_{1})^{−1}Af − Af] + \frac{t}{2}(I − \frac{t}{2}A_{1})^{−1}A_{2}A_{1}f.

Since A = A_{1}+A_{2} and A_{2} is bounded, it follows that D(A_{1}) = D(A). Then, for f ∈D(A), we have that A_{2}A_{1}f ∈ E. Since A_{1} generates a contraction semigroup, the Hille-Yosida theorem implies that ∥(I − \frac{t}{2}A_{1})^{−1}∥ ≤ 1 for all t ≥ 0. Thus,

∥\frac{t}{2}(I − \frac{t}{2}A_{1})^{−1}A_{2}A_{1}f∥ ≤ \frac{t}{2}∥A_{2}A_{1}f∥ → 0

as t → 0. And again since ∥(I − \frac{t}{2}A_{1})^{−1}∥ ≤ 1, we obtain that

∥(I − \frac{t}{2}A_{1})^{−1}g − g∥ = ∥(I − \frac{t}{2}A_{1})^{−1}[g − (I − \frac{t}{2}A_{1})g]∥
≤ ∥(I − \frac{t}{2}A_{1})^{−1}∥ · ∥\frac{t}{2}A_{1}g∥
≤ \frac{t}{2}∥A_{1}g∥ → 0

as t → 0 for all g ∈ D(A). The Banach’s Convergence Theorem (see H. H. Schaefer [30], Theorem III.4.5) implies that lim_{t→0} (I−\frac{t}{2}A_{1})^{−1}g = g for all g ∈E since D(A) is dense in E and (I−\frac{t}{2}A_{1})^{−1} is uniformly bounded. Replacing g by Af we obtain that lim_{t→0}(I−\frac{t}{2}A_{1})^{−1}Af − Af = 0. Therefore, lim_{t→0} \frac{V (t;A)f−f}{t} − Af = 0, which means that V (t; A) is consistent.

(b) For k ∈ N, V (t; A)e_{k^{2}} = (I − \frac{t}{2}A_{1})^{−1}(I + tA_{2})(I + \frac{t}{2}A_{1})e_{k^{2}} by definition (1.32) of the approximation method V. The equality (1.22) implies that

\{ \begin{matrix}(I + \frac{t}{2}A_{1})e_{k} & = & (1−\frac{t}{2}k^{2})e_{k}, \\ (I − \frac{t}{2}A_{1})^{−1}e_{k} & = & (1+\frac{t}{2}k^{2})^{−1}e_{k}. \end{matrix}  (1.33)

Thus we obtain that

V (t; A)e_{k^{2}} = (1−\frac{t}{2}k^{4})(I − \frac{t}{2}A_{1})^{−1}(I + tA_{2})e_{k^{2}}.  (1.34)

By the definition of A_{2}, (I + tA_{2})e_{k^{2}} = e_{k^{2}} + te_{k}. Hence it follows from (1.34) that

V (t; A)e_{k^{2}} = (1−\frac{t}{2}k^{4})(I − \frac{t}{2}A_{1})^{−1}(e_{k^{2}} + te_{k}).

Then, with (1.33) we obtain from the above equality that

\begin{aligned}V (t; A)e_{k^{2}} & = & (1−\frac{t}{2}k^{4})[_{\frac{1}{1+ \frac{t}{2} k^{4}}} e_{k^{2}} + _{\frac{t}{1+ \frac{t}{2} k^{2}}} e_{k}] \\ & = & \frac{1− \frac{t}{2} k^{4}}{1+ \frac{t}{2} k^{4}} e_{k^{2}} + \frac{t(1− \frac{t}{2} k^{4})}{1+ \frac{t}{2} k^{2}}e_{k}. \end{aligned}  (1.35)

Therefore,

∥V (t; A)e_{k^{2}}∥ ≥ ∥\frac{t(1−\frac{t}{2} k^{4})}{1+ \frac{t}{2} k^{2}}e_{k}∥ = |\frac{t(1−\frac{t}{2} k^{4})}{1+ \frac{t}{2} k^{2}}| → ∞

as k → ∞ for any t > 0. This shows that V (t; A) is unbounded for any t∈(0, ∞). Now, let k be an integer that is not a square of an integer. Then,

\begin{aligned}V (t; A)e_{k} & = & (I − \frac{t}{2}A_{1})^{−1}(I + tA_{2})(I + \frac{t}{2}A_{1})e_{k} \\ & = & (1 − \frac{t}{2}k^{2})(I − \frac{t}{2}A_{1})^{−1}(I + tA_{2})e_{k}, \end{aligned}  (1.36)

where the last “=” sign is due to (1.33). By definition, A_{2} e_{k} = ∑_{i} ⟨e_{k}, e_{i^{2}}⟩ e_{i} = 0. Then, it follows from (1.36) that V (t; A)e_{k} = (1 − \frac{t}{2}k^{2})(I − \frac{t}{2}A_{1})^{−1}e_{k} . With (1.33) we arrive at

V (t; A)e_{k} = \frac{1− \frac{t}{2} k^{2}}{1+ \frac{t}{2} k^{2}} e_{k}.  (1.37)

For each t ∈ (0, 1], let c_{1,k} := \frac{1− \frac{t}{2} k^{2}}{1+ \frac{t}{2} k^{2}} , c_{2,k} := \frac{1− \frac{t}{2} k^{4}}{1+ \frac{t}{2} k^{4}} , and b_{k} := \frac{t(1− \frac{t}{2} k^{4})}{1+ \frac{t}{2} k^{2}}. When k is not a square of an integer, it follows from (1.37) and (1.35) that

\{ \begin{matrix}V (t; A)^{n}e_{k} & = & cn_{1,k}e_{k}, for n∈N, \\ V (t; A)e_{k^{2}} & = & c_{2,k}e_{k^{2}} + b_{k}e_{k}. \end{matrix}  (1.38)

Now for n∈N_{0},

\begin{aligned}V (t; A)^{n+1}e_{k^{2}} & = & V (t; A)^{n}(c_{2,k}e_{k^{2}} + b_{k}e_{k}) \\ & = & c_{2,k}V (t; A)^{n}e_{k^{2}} + b_{k}cn_{1,k}e_{k}, \end{aligned}

from which we have

∑_{i=0}^{n} cn−i_{2,k} [V(t; A)^{i+1}−c_{2,k}V(t; A)^{i}] e_{k^{2}} = ∑_{i=0}^{n} cn−i_{2,k}b_{k}ci_{1,k}e_{k} = \frac{c_{2,k}^{n+1}−c_{1,k}^{n+1}}{c_{2,k}−c_{1,k}} b_{k}e_{k}.

But the leftmost side of the above equalities equals

cn+1_{2,k} ∑_{i=0}^{n}[\frac{V (t;A)^{i+1}}{c_{2,k}^{i+1}} − \frac{V (t;A)^{i}}{c_{2,k}^{i}} ] e_{k^{2}} = [V (t; A)^{n+1} − cn+1_{2,k}]e_{k^{2}}.

So,

V (t; A)^{n+1}e_{k^{2}} = cn+1_{2,k}e_{k^{2}} + \frac{c_{2,k}^{n+1} − c_{1,k}^{n+1}}{c_{2,k} − c_{1,k}} b_{k}e_{k},

from which we obtain ∥V (t; A)^{n+1}e_{k^{2}}∥ ≥ |\frac{c_{2,k}^{n+1}−c_{1,k}^{n+1}}{c_{2,k}−c_{1,k}} b_{k}|. Thus, to show that V (t; A)^{n} is not bounded for any n∈N, it suffices to show that

lim_{k→∞} |\frac{c_{2,k}^{n+1} − c_{1,k}^{n+1}}{c_{2,k} − c_{1,k}} b_{k}| = ∞.  (1.39)

We will show first that

lim_{k→∞} |\frac{c_{2,k}^{n+1} − c_{1,k}^{n+1}}{c_{2,k} − c_{1,k}} | = n+1.  (1.40)

Since \frac{a−1}{a+1} < \frac{b−1}{b+1} < 1 for b > a > 1, we have that |c_{1,k}| < |c_{2,k}| < 1. Obviously, lim_{k→∞} c_{1,k} = lim_{k→∞} c_{2,k} = −1. So, |c_{2,k}| > 0 when k is large enough, and thus

\{ \begin{matrix}0 < \frac{c_{1,k}}{c_{2,k}} < 1, & k large enough, \\ lim_{k→∞} \frac{c_{1,k}}{c_{2,k}} & = 1. \end{matrix}  (1.41)

Therefore, |\frac{c_{2,k}^{n+1}−c_{1,k}^{n+1}}{c_{2,k}−c_{1,k}} | = \frac{1−(c_{1,k}/c_{2,k})^{n+1}}{1−(c_{1,k}/c_{2,k})} = \frac{1−x_{k}^{n+1}}{1−x_{k}}, where x_{k} := c_{1,k}/c_{2,k}. Then, by L’Ho-

pital’s rule lim_{k→∞} |\frac{c_{2,k}^{n+1}−c_{1,k}^{n+1}}{c_{2,k}−c_{1,k}} | = lim_{k→∞} \frac{d(1−x_{k}^{n+1})}{dx_{k}}/\frac{d(1−x_{k})}{dx_{k}} = n+1, which proves (1.40). Obviously, lim_{k→∞} b_{k} = −∞. Then (1.39) follows immediately from (1.40).

(c) Denote W (t) := (I+tA_{2})(I+\frac{t}{2}A_{1})(I−\frac{t}{2}A_{1})^{−1}. Then ∥W (t)∥ ≤ 1+t by (1.24) and (1.26), and hence for (t, n)∈[0, 1]×N and f ∈D(A),

∥V (t; A)^{n+1}f∥ = ∥(I − \frac{t}{2}A_{1})^{−1}W(t)^{n}(I +tA_{2})(I + \frac{t}{2}A_{1})f∥
≤ ∥W(t)∥^{n} ∥(I − \frac{t}{2}A_{1})^{−1}∥ · ∥(I +tA_{2})∥ · ∥(I + \frac{t}{2}A_{1})f∥
≤ (1 + t)^{n+1}∥(I + \frac{t}{2}A_{1})f∥.

It follows that

lim_{n→∞} ∥V (t; A)^{n}f∥^{1/n} = lim_{n→∞}(1 + t) ∥(I + \frac{t}{2}A_{1})f∥^{1/n} = 1 + t,

which shows that the approximation method V satisfies the Von Neumann stability condition (1.21) on D(A).

(d) By definition, the spatially discrete method {V (t; A_{n}) : (t, n) ∈ [0, 1]×N} is called unconditionally stable if sup_{n∈N} ∥V (\frac{t}{m}; A_{n})^{m}∥_{n} ≤ M(t) for some positive increasing function M(·). An obvious necessary condition for unconditional stability is

sup_{n∈N} ∥V (\frac{t}{m}; A_{n})^{m} P_{n}f∥_{n} ≤ M(t) sup_{n∈N} ∥P_{n}f∥_{n}  (1.42)

for f ∈E. Thus, to show that V (t; A_{n}) is not unconditionally stable, it suffices to show that (1.42) does not hold.

Let k be a prime number and n := k^{2}+1. A calculation using (1.28) and (1.30) shows that

\{ \begin{matrix}V (t; A_{n})e_{n,k^{2}} & = & \frac{1− \frac{t}{2} a_{n,k^{2}}}{1+ \frac{t}{2} a_{n,k^{2}}} e_{n,k^{2}} + \frac{t(1− \frac{t}{2} a_{n,k^{2}})}{1+ \frac{t}{2} a_{n,k}}e_{n,k}, \\ V (t; A_{n})e_{n,k} & = & \frac{1− \frac{t}{2} a_{n,k}}{1+ \frac{t}{2} a_{n,k}} e_{n,k}, \end{matrix}  (1.43)

which has the exact the same form as (1.38). Observe that the coefficients before e_{n,k^{2}} and e_{n,k} have the same properties as those of c_{1,k}, c_{2,k} and b_{k} in (1.38), and that these properties of c_{1,k}, c_{2,k} and b_{k} are used in (c) to show the unboundedness of {∥V (t; A)^{m}e_{k^{2}} ∥_{n}}_{k=1}^{∞} for any fixed m∈N and t > 0. By exactly the same argument, we can show that the sequence {∥V (t; A_{n})^{m}e_{n,k^{2}}∥_{n}}_{k=1}^{∞} is unbounded for any fixed m ∈ N and t > 0. This shows that (1.42) does not hold.

(e) Define W_{n}(t) := (I +tA_{n,2})(I + \frac{t}{2}A_{n,1})(I − \frac{t}{2}A_{n,1})^{−1}. Then ∥W_{n}(t)∥_{n} ≤ 1 + t by (1.29) and (1.31), and for m∈N_{0} and (t, n)∈[0, δ]×N,

∥V (t; A_{n})^{m+1}f_{n}∥_{n} = ∥(I − \frac{t}{2}A_{n,1})^{−1}W_{n}(t)^{m}(I +tA_{n,2})(I + \frac{t}{2}A_{n,1})f_{n}∥_{n}
≤ ∥W_{n}(t)∥_{n}^{m} ∥(I − \frac{t}{2}A_{n,1})^{−1}∥_{n} · ∥(I +tA_{n,2})∥_{n} · ∥(I + \frac{t}{2}A_{n,1})f_{n}∥_{n}
≤ (1 + t)^{m+1}∥(I + \frac{t}{2}A_{1})f_{n}∥_{n},

where the last inequality is due to (1.29), (1.31) and the inequality ∥W_{n}(t)∥_{n} ≤ 1+t. Again, since the discrete matrix A_{n,1} is a bounded linear operator for each fixed n ∈ N, it follows that ∥V^{m}(t; A_{n})∥_{n} ≤ (1+t)^{m}∥I + \frac{t}{2}A_{n,1}∥_{n}. Therefore,

r(V (t; A_{n})) = lim_{m→∞}^{m} \sqrt{(1 + t)^{m}∥I + tA_{n,1}∥_{n}} = 1 + t.

This shows that V (t; A_{n}) satisfies the Von Neumann stability condition.

1.2.3 Numerical Testings

To examine the numerical stability of the classically unstable method given in (1.32), we choose an initial value condition for the problem with a known solution. The simulation time interval, the initial value condition, and the true solution of the example problem for the initial value condition are:

Time interval: [0, 1];
Initial value: u(0, x) = sin(2x)+sin(3x);
True solution: u(t, x) = e^{−4t}sin(2x)+e^{−9t}sin(3x).

We also choose three initial value errors for the testing problem. They are

\{ \begin{matrix}e_{1}(x) & = & 0, \\ e_{2}(x) & = & \frac{x(π−x)}{10^{5}} cos(nx), \\ e_{3}(x) & = & ∑_{k^{2}=1}^{k^{2}<n} \frac{sin(k^{2}x)}{10^{4}n}, \end{matrix}

where n = π/Δx is the spatial partition size. The second and third initial value errors contain very high frequency components. High frequency errors usually tend to be enlarged considerably for unstable methods like the explicit method, and we choose these two errors in order to see how they will affect the simulation errors for our unstable example method.

We solved the example problem with the three perturbed initial value conditions by the explicit method V (t)u^{n+1} = (I +tA)u^{n}, the implicit method V (t)u^{n+1} = (I −tA)^{−1}u^{n}, the factorized unstable method (1.32) which is listed as FAC in the tables, and the Crank-Nicolson method (1.15) which is listed as C-N in the tables. We have tested these methods

Table 1: Stability testing — Small spatial partition sizes

Δx  Δt Initial Err Explicit  Implicit  F A C  C-N
e_{1}(x)  2.47e − 01 4.06e − 02 3.04e − 03 3.04e − 03
π/16 1/5 e_{2}(x) 7.13e + 01 4.06e − 02 3.03e − 03 3.03e − 03
e_{3}(x)  1.31e + 00 4.06e − 02 3.04e − 03 3.03e − 03
e_{1}(x)  6.70e − 03 9.32e − 03 7.24e − 04 7.24e − 04
π/16 1/20 e_{2}(x) 5.48e + 07 9.32e − 03 7.24e − 04 7.24e − 04
e_{3}(x)  1.77e + 01 9.32e − 03 7.29e − 04 7.29e − 04
e_{1}(x)  2.01e − 03 4.18e − 03 9.45e − 04 9.45e − 04
π/16 1/50 e_{2}(x) 2.27e − 03 4.18e − 03 9.45e − 04 9.45e − 04
e_{3}(x)  2.00e − 03 4.18e − 03 9.49e − 04 9.49e − 04
Δx Δt Initial Err Explicit Implicit F A C C-N
e_{1}(x)  2.46e + 01 1.77e − 02 7.81e − 04 7.81e − 04
π/32 1/10 e_{2}(x) 2.87e + 11 1.77e − 02 7.88e − 04 7.88e − 04
e_{3}(x)  1.07e + 10 1.77e − 02 7.79e − 04 7.78e − 04
e_{1}(x)  3.76e + 34 1.78e − 03 2.32e − 04 2.32e − 04
π/32 1/100 e_{2}(x) 1.26e + 45 1.78e − 03 2.32e − 04 2.32e − 04
e_{3}(x)  1.96e + 37 1.78e − 03 2.34e − 04 2.34e − 04
e_{1}(x)  5.07e − 04 1.00e − 03 2.40e − 04 2.40e − 04
π/32 1/200 e_{2}(x) 1.94e + 01 1.00e − 03 2.40e − 04 2.40e − 04
e_{3}(x)  5.05e − 04 1.01e − 03 2.42e − 04 2.42e − 04

with different spatial mesh sizes Δx and time step size Δt, and the computed approximated solutions are compared with the true solution and the maximal errors are listed in the two tables.

For the four methods chosen, the explicit method is not stable, not unconditionally stable, and even not Von Neumann stable. The FAC is also not stable or unconditionally stable, but satisfies the Von Neumann stability condition as shown in the previous section. The implicit method is stable for all well-posed problems by the Widder’s theorem [2], and the Crank-Nicolson is stable for quasi-dissipative problems (see Section 2 of Chapter 4) like the example problem given in the previous section.

The test results show that the explicit method is obviously unstable. It has huge numerical errors when time step sizes Δt are large relative to the spatial mesh size Δx. The unstable method FAC exhibits much smaller numerical errors than does the explicit method, even smaller than the errors produced by the always-stable implicit method. Only when compared with the stable Crank-Nicolson method, the FAC method shows slightly larger numerical errors for the cases of simultaneously large Δt and small Δx when the initial value has high frequency errors. The Crank-Nicolson method is a second order method while the FAC method is only first order. The first order accuracy of the FAC method is due to the first order approximation of the semigroup e^{tA_{2}} by the explicit method (I+tA_{2}) — the second factor in the FAC method (1.32). And even in the worst tested case for the FAC

Table 2: Stability testing — Large spatial partition sizes

Δx  Δt  Initial Err Explicit Implicit F A C  C-N
e_{1}(x)  ∞  3.91e-03 6.45e-05 6.45e-05
π/4096 1/40  e_{2}(x)  ∞  3.91e-03 8.28e-05 8.28e-05
e_{3}(x)  ∞  3.91e-03 4.33e-04 6.47e-05
e_{1}(x)  ∞  3.77e-04 6.31e-07 6.31e-07
π/4096 1/400  e_{2}(x)  ∞  3.77e-04 2.25e-05 2.25e-05
e_{3}(x)  ∞  3.77e-04 4.04e-06 8.69e-07
e_{1}(x)  ∞  3.76e-05 8.27e-09 8.27e-09
π/4096 1/4000  e_{2}(x)  ∞  3.76e-05 9.81e-09 9.81e-09
e_{3}(x)  ∞  3.76e-05 2.85e-08 2.85e-08
Δx  Δt  Initial Err Explicit Implicit F A C  C-N
e_{1}(x)  ∞  1.92e-03 1.61e-05 1.61e-05
π/8192 1/80  e_{2}(x)  ∞  1.92e-03 3.56e-05 3.56e-05
e_{3}(x)  ∞  1.92e-03 3.46e-04 1.63e-05
e_{1}(x)  ∞  1.88e-04 1.58e-07 1.58e-07
π/8192 1/800  e_{2}(x)  ∞  1.88e-04 2.25e-05 2.25e-05
e_{3}(x)  ∞  1.88e-04 2.96e-06 3.66e-07
e_{1}(x)  ∞  1.88e-05 2.10e-09 2.10e-09
π/8192 1/8000  e_{2}(x)  ∞  1.88e-05 3.69e-09 3.69e-09
e_{3}(x)  ∞  1.88e-05 1.29e-08 1.29e-08

method, when compared with the Crank-Nicolson the errors are still close to those of the C-N method. So it is unclear if these larger errors of the FAC method is caused by the unstability or the first order accuracy.

1.3 Outline of the Dissertation

As mentioned in the beginning of this chapter, the purpose of this dissertation is to study weakened stability conditions and their effects on or benefits to the convergence of approximation methods. Thus, the dissertation is presented in a way toward revealing the convergence properties and possible “benefits” of Von Neumann stable methods like the one presented in Section 1.2. Before addressing convergence of Von Neumann stable approximation methods in Chapter 3, we need to accumulate sufficient preparatory results in Chapter 2. In Chapter 4, the convergence results established in Chapter 3 are applied to the example in Section 1.2, and to two practically useful temporal approximation methods.

2 Spatial Approximations

2.1 Introduction

For an evolutionary system many of its spatial properties are closely related to its temporal properties. For instance, a property of the system at a spatial point will affect the properties of the system at the neighboring spatial points as time progresses. Such tempo-spatial interactions are also true with approximation procedures of an evolutionary system. For instance, an approximation of the operator A (which is a purely spatial approximation involving no time at all) clearly will affect the stability of a temporal approximation method of the spatially approximated system.

A numerical simulation of an evolutionary system consists of spatial and temporal approximations. Because of the influence of spatial approximations on the temporal approximations, we shall examine spatial approximations in this chapter.

A spatial approximation of the evolutionary system (1.1) involves the approximation of the operator A by a sequence of operators A_{n}, which converges in some sense to A. Thus, with spatial approximation we obtain a sequence of problems

\{ \begin{matrix}u′(t) = A_{n}u(t), t ≥ 0, \\ u(0) = f ∈D(A_{n})⊂E. \end{matrix}  (2.1)

In order that the approximating problems converge to the original problem in the sense that the true solutions u_{n}(t) of (2.1) converge to the true solution u(t) of the original problem (1.1) uniformly on compact time intervals for a sufficiently large set of initial values, some stability condition is usually enforced on the approximations in addition to the condition of the strong convergence of A_{n} to A. An important sufficient condition for the convergence of spatial approximations is stated in the following result (see J. A. Goldstein [9], pp. 44) derived from the Trotter-Kato theorem [13, 26, 36].

Theorem Let A_{n}(n∈N_{0}) defined on D(A_{n})⊃D(A_{0}) generate C_{0}-semigroups S_{n} satisfying the “stability condition”

∥S_{n}(t)∥ ≤ Me^{ωt}, t ≥ 0,  (2.2)

for positive constants M, ω independent of n, t. Assume that for each f ∈D(A_{0}), lim_{n→∞} A_{n}f = A_{0}f. Then lim_{n→∞} S_{n}(t)f = S_{0}(t)f for each f ∈ E, where the limit is uniform for t in compact intervals of [0, ∞).

The stability condition (2.2) not only assures the strong convergence of the semigroups, but also suffices to absorb small initial value errors. In fact, for any f ∈E and any sequence {f_{n}}⊂E with lim_{n→∞} f_{n} = f, the inequality

∥S_{n}(t)f_{n} − S(t)f∥ ≤ ∥S_{n}(t)(f_{n} − f)∥ + ∥S_{n}(t)f − S(t)f∥

implies that lim_{n→∞} S_{n}(t)f_{n} = f when ∥S_{n}(t)∥ is uniformly bounded on any compact interval of t. It may happen that the spatial approximations are such that the semigroup sequence is not stable even though the approximating operators converge. The following is such an example.

Example 2.1 Let Y = {f ∈ L^{2}([0, 1], C) : f(0) = f(1) = 0}. Let E be the product Banach space given by E = {(f, g) : f, g ∈ Y, ∥(f, g)∥ := max(∥f∥_{Y} , ∥g∥_{Y}) < ∞}. Define an operator A by A(f, g)(x) := (if′′(x), ig′′(x)) , or, in matrix form

A [ \begin{matrix}f \\ g \end{matrix} ](x) = [ \begin{matrix}\frac{id^{2}}{dx^{2}} & 0 \\ 0 & \frac{id^{2}}{dx^{2}} \end{matrix} ] [\begin{matrix}f(x) \\ g(x) \end{matrix}] .

Since the Schrödinger operator A_{s}:= \frac{id^{2}}{dx^{2}} generates a strongly continuous isometric group S_{s}(t) on Y, the operator A generates a C_{0}-semigroup on S(t) := \binom{S_{s}(t) 0}{0 S_{s}(t)} on E. For each n ∈ N, define an operator A_{n} on D(A) by

A_{n} := A + \binom{0 B_{n}}{0 0} ,

where B_{n}f := nπ ⟨f, e_{n}⟩ e_{n} with e_{n} representing the function x↦\sqrt{2} sin(nπx). Then,

( i ) each A_{n} generates a C_{0}-semigroup S_{n},

(i i) the operators A_{n} converge strongly to A on D(A), but

(iii) ∥S_{n}(t)∥ ≥ nt.

Proof: ( i ) Define P_{n} := \binom{0 B_{n}}{0 0}. Since A generates a C_{0}-semigroup and P_{n} is bounded for each n∈N, it follows that A_{n} = A + P_{n} generates a C_{0}-semigroup (see [9], pp. 40).

(ii) Let u = (f, g) ∈ D(A). Then

∥A_{n}u − Au∥ = ∥\binom{0 B_{n}}{0 0} \binom{f}{g}∥
= nπ∥ ⟨g, e_{n}⟩ e_{n}∥_{Y}
= (nπ)^{−1}∥ ⟨g′′, e_{n}⟩ e_{n}∥_{Y}
≤ (nπ)^{−1}∥g′′∥_{Y} ∥e_{n}∥_{Y}^{2} .

Since u ∈ D(A), it follows that g′′ ∈ L^{2}[0, 1] by the definition of A. Since ∥e_{n}∥_{Y} = 1 we obtain that lim_{n→∞} ∥A_{n}u − Au∥ = 0.

(iii) To prove the inequality we will derive an expression for the semigroup S_{n}. For f ∈D(A_{s})⊂Y,

B_{n}A_{s}f = B_{n}if′′ = − iB_{n} ∑_{k=1}^{∞} k^{2}π^{2} ⟨f, e_{k}⟩ e_{k}
= −i ∑_{k=1}^{∞} k^{2}π^{2} ⟨f, e_{k}⟩ B_{n}e_{k}
= −i(nπ)^{3} ⟨f, e_{n}⟩ e_{n}.

On the other hand, A_{s}B_{n}f = A_{s}nπ ⟨f, e_{n}⟩ e_{n} = i nπ ⟨f, e_{n}⟩ e′′_{n} = −i(nπ)^{3} ⟨f, e_{n}⟩ e_{n}, which shows that

A_{s}B_{n}f = B_{n}A_{s}f for all f ∈D(A_{s}).  (2.3)

Now, for u = (f, g)∈D(A) we have that f, g ∈D(A_{s}). Then,

AP_{n}u = \binom{A_{s}}{A_{s}} \binom{0 B_{n}}{0 0} \binom{f}{g} = \binom{A_{s}B_{n}g}{0} = \binom{B_{n}A_{s}g}{0} = \binom{0 B_{n}}{0 0} \binom{A_{s}f}{A_{s}g} = P_{n}Au.  (2.4)

Let t ≥ 0. Then, P_{n}(I − tA)^{−1} = (I − tA)^{−1}P_{n} since for all u∈E,

\begin{aligned}(I −tA)^{−1}P_{n}u−P_{n}(I −tA)^{−1}u & = (I −tA)^{−1}[P_{n}(I −tA)−(I −tA)P_{n}](I −tA)^{−1}u \\ & = (I − tA)^{−1}[tP_{n}A − tAP_{n}](I − tA)^{−1}u = 0. \end{aligned}

It then follows that

\begin{aligned}P_{n}S(t) & = & P_{n}lim_{k→∞} (I − \frac{t}{k}A)^{−k} \\ & = & lim_{k→∞} (I − \frac{t}{k}A)^{−k}P_{n} \\ & = & S(t)P_{n} \end{aligned}  (2.5)

for all t ≥ 0. Similarly, with (2.3) we can show that

B_{n}S_{s}(t) = S_{s}(t)B_{n} for all t ≥ 0.  (2.6)

By Trotter’s product formula [37] we have that S_{n}(t) = lim_{k→∞} [e^{\frac{t}{k} P_{n}}S(\frac{t}{k})]^{k} . Since P_{n}^{2} = 0, it follows that e^{tP_{n}} = I + tP_{n} for all t ≥ 0. Thus,

\begin{aligned}S_{n}(t) & = & lim_{k→∞} [(I + \frac{t}{k}P_{n})S(\frac{t}{k})]^{k} \\ & = & lim_{k→∞} (I + \frac{t}{k}P_{n})^{k}S(\frac{t}{k})^{k}, \end{aligned}

where the last equality is due to (2.5). Then we obtain

S_{n}(t) = e^{tP_{n}}S(t) = (I + tP_{n})S(t) = \binom{I tB_{n}}{0 I} S(t).

Now let f_{n}(x) := (nπ)^{−1}e_{n} and let u_{n} := \binom{0}{f_{n}}. Then

∥S_{n}(t)u_{n}∥ = ∥e^{tP_{n}}S(t)u_{n}∥
= ∥ \binom{I tB_{n}}{0 I} \binom{S_{s}(t) 0}{0 S_{s}(t)} \binom{0}{f_{n}} ∥
= ∥ \binom{tB_{n}S_{s}(t)f_{n}}{S_{s}(t)f_{n}} ∥
= max{∥tB_{n}S_{s}(t)f_{n}∥_{Y} , ∥S_{s}(t)f_{n}∥_{Y} }
= max{∥tS_{s}(t)B_{n}f_{n}∥_{Y} , ∥S_{s}(t)f_{n}∥_{Y} },

where the last equality is due to (2.6). It follows from Stone’s theorem (see e.g. [9], pp. 32) that S_{s}(t) is a unitary operator for all t ≥ 0. Thus,

∥S_{n}(t)u_{n}∥ = max{∥tB_{n}f_{n}∥_{Y} , ∥f_{n}∥_{Y} }
= max{tnπ| ⟨f_{n}, e_{n}⟩ |, (nπ)^{−1}∥e_{n}∥_{Y} }
= max{t, (nπ)^{−1}}.

Since ∥nπu_{n}∥ = 1, we obtain that

\begin{aligned}∥S_{n}(t)∥ & ≥ & ∥S_{n}(t)(nπu_{n})∥ & = & nπ∥S_{n}(t)u_{n}∥ \\ & = & nπ max\{t, (nπ)^{−1}\} & ≥ & nπt. \end{aligned}

Although the spatial approximation given in the example above is unstable, it is stabilizable in the following sense. The implications of the stabilizability of S_{n} with respect to convergence will be described in the next section.

Example 2.2 The semigroup sequence {S_{n}} in Example 2.1 is stabilizable in the sense that there exists a sequence of bounded operators {W_{n}} such that

(a) ∥W_{n}S_{n}(t)∥ ≤ Me^{ωt} for some constants M, ω independent of n, t, and

(b) lim_{n→∞} W_{n}f = f for all f ∈ E.

Proof: For n ∈ N define operators W_{n} by W_{n}(f, g) := ((I − \frac{1}{nπ} \frac{d^{2}}{dx^{2}} )^{−1}f, g) . Then, ∥W_{n}S_{n}(t)∥ = ∥W_{n}e^{tP_{n}}S(t)∥ ≤ ∥W_{n}e^{tP_{n}}∥, where the last inequality holds because ∥S(t)∥ = 1. Now we will show that ∥W_{n}e^{tP_{n}}∥ ≤ e^{t} for all t ≥ 0 and n∈N.

(a) We introduce the notation Q_{n}f := (I − \frac{1}{nπ} \frac{d^{2}}{dx^{2}} )^{−1}f. Then W_{n}\binom{f}{g} = \binom{Q_{n} 0}{0 I}\binom{f}{g}. For (f, g) ∈ E,

∥W_{n}e^{tP_{n}} \binom{f}{g} ∥ = ∥W_{n} \binom{I tB_{n}}{0 I} \binom{f}{g} ∥
= ∥W_{n} \binom{f}{g} + W_{n} \binom{0 tB_{n}}{0 0} \binom{f}{g} ∥
≤ ∥W_{n} \binom{f}{g}∥+∥\binom{Q_{n} 0}{0 I}\binom{0 tB_{n}}{0 0}\binom{f}{g}∥
= ∥W_{n} \binom{f}{g}∥ + t∥ \binom{Q_{n}B_{n}g}{0} ∥.

By definition, B_{n}g = nπ ⟨g, e_{n}⟩ e_{n}. Since ∥W_{n}∥ ≤ 1, it follows that

∥W_{n}e^{tP_{n}}(f, g)∥ ≤ ∥(f, g)∥ + tnπ|⟨g, e_{n}⟩| · ∥(Q_{n}e_{n}, 0)∥.

An easy calculation shows that Q_{n}e_{n} = \frac{e_{n}}{1+nπ} for all n∈N. Then from the above inequality we obtain ∥W_{n}e^{tP_{n}}(f, g)∥ ≤ e^{t} for t ≥ 0 for all n∈N since

∥W_{n}e^{tP_{n}}(f, g)∥ ≤ ∥(f, g)∥ + \frac{tnπ}{1+nπ} |⟨g, e_{n}⟩| · ∥(e_{n}, 0)∥
< ∥(f, g)∥ + t|⟨g, e_{n}⟩|
≤ ∥(f, g)∥ + t∥g∥_{Y}
≤ (1 + t)∥(f, g)∥
≤ e^{t}∥(f, g)∥.

(b) For f ∈D(A_{s}),

lim_{n→∞} ∥Q_{n}f −f∥ = lim_{n→∞} ∥(I − \frac{1}{nπ} \frac{d^{2}}{d x^{2}} )^{−1}f − f∥
= lim_{n→∞} ∥(I − \frac{1}{nπ} \frac{d^{2}}{d x^{2}} )^{−1} \frac{1}{nπ} \frac{d^{2}}{d x^{2}} f∥
= lim_{n→∞} \frac{1}{nπ} ∥(I − \frac{1}{nπ} \frac{d^{2}}{d x^{2}} )^{−1}A_{s}f∥
≤ lim_{n→∞} \frac{1}{nπ} ∥A_{s}f∥ = 0,

(2.7)

where the inequality sign “≤” holds since ∥(I − \frac{1}{nπ} \frac{d^{2}}{d x^{2}} )^{−1}∥ ≤ 1. Since W_{n} = \binom{Q_{n} 0}{0 I}, it follows from (2.7) that lim_{n→∞} W_{n}u = u for all u ∈ D(A). Since ∥W_{n}∥ ≤ 1 for all n ∈ N and D(A) is dense in E, statement (b) follows from Theorem III.4.5 in H. H. Schaefer’s [30].

One purpose of this chapter is to weaken the stability condition (2.2) to be able to accommodate unstable but stabilizable spatial approximations like the one in the example. In the next section we will investigate the convergence properties of unstable spatial approximations which can be stabilized in the sense of Example 2.2.

One tool we use to establish convergence theorems in this thesis is the Laplace-Stieljes transform and its approximation theory. In the following we collect some definitions and known approximation results for the Laplace-Stieljes transform.

Definition 2.1 Let Lip_{ω} denote the Banach space of Lipschitz continuous functions

Lip_{ω}:={v:[0, ∞)→E:v(0)=0, and ∥v∥_{Lip_{ω}} <∞},

where ∥v∥_{Lip_{ω}}:=sup\{\frac{∥v(t)−v(t′)∥}{| ∫_{t′}^{t} e^{ωτ} dτ|} : t, t′ ∈[0, ∞)\}. For v ∈ Lip_{ω}, the Laplace-Stieljes transform

of v is defined as (L_{s}v)(λ) := ∫_{0}^{∞} e^{−λt}dv(t) for all complex numbers λ with real parts satisfying Reλ > ω.

Remark 2.1 It is not difficult to verify that for any locally integrable function u : [0, ∞) → E satisfying ∥u(t)∥ ≤ Me^{ωt} for some constants M, ω ≥ 0, the antiderivative v : t↦∫_{0}^{t} u(s)ds is in Lip_{ω} and (L_{s}v)(λ) = ∫_{0}^{∞} e^{−λt}u(t)dt = λ ∫_{0}^{∞} e^{−λt}v(t)dt.

The following theorem for approximations of Laplace-Stieljes transforms is taken from Bäumer and Neubrander’s paper [2].

Theorem 2.1 Let M > 0, f_{n} ∈ Lip_{ω} with ∥f_{n}∥_{Lip_{ω}} ≤ M and r_{n} = L_{s}f_{n} for all n ∈ N_{0}. The following are equivalent. ( i ) lim_{n→∞} r_{n}(λ) = r_{0}(λ) for all λ∈(ω, ∞). (i i) lim_{n→∞} f_{n}(t) = f_{0}(t) uniformly on compact subsets of [0, ∞).

2.2 Stabilized Spatial Approximations

One important result in the convergence theory for spatial approximations is the following theorem originally due to Trotter (see [13, 26, 36]).

Theorem (Trotter-Kato) Let A be a generator of a C_{0}-semigroup S with ∥S(t)∥ ≤ Me^{ωt} (M, ω >0, and t≥0). For n∈N, let A_{n} with D(A_{n}) ⊃ D(A) be generators of C_{0}-semigroups S_{n}(t). If the semigroups S_{n} (n∈N) satisfy the stability condition

∥S_{n}(t)∥ ≤ Me^{ωt},  (2.8)

then the following statements are equivalent.

( i ) lim_{n→∞} R(λ, A_{n})f = R(λ, A)f for all λ > ω and f ∈ D, where D is a total subset of E.

(i i) For f ∈ E, lim_{n→∞} S_{n}(t)f = S(t)f uniformly for t in compact intervals of [0, ∞).

An important assumption of the Trotter-Kato theorem is the stability condition (2.8) — the uniform boundedness of the semigroups. This condition implies another important but less conspicuous condition: a non-empty intersection of resolvent sets which contains a complex right half plane. In this section we modify the Trotter-Kato theorem by requiring only a stabilizability condition that does not imply a non-empty intersection of resolvent sets, and a weaker strong convergence of the resolvents, namely, stabilized strong convergence.

Theorem 2.2 Suppose that A generates a C_{0}-semigroup S with ∥S(t)∥ ≤ Me^{ωt} (M, ω >0, and t ≥ 0). For n ∈ N, let W_{n} ∈ L(E) and A_{n} with D(A_{n}) ⊃ D(A) be generators of C_{0}-semigroups S_{n}(t). If

(a) lim_{n→∞} W_{n}f = f for all f ∈ E,

(b) For all f ∈D(A), W_{n}f ∈D(A) and W_{n}A_{n}f = A_{n}W_{n}f for f ∈ D(A), and

(c) ∥W_{n}S_{n}(t)∥ ≤ Me^{ωt},

then the following statements are equivalent.

( i ) lim_{n→∞} R_{n}(λ)f = R(λ, A)f for all λ > ω and f ∈ D, where D is a total subset of E, and R_{n}(λ)f := ∫_{0}^{∞} e^{−λt}W_{n}S_{n}(t)f dt for λ > ω and f ∈ E.

(i i) For all f ∈E, lim_{n→∞} W_{n}S_{n}(t)f = S(t)f uniformly for t in compact intervals of [0, ∞).

Remark 2.2 It is possible that the intersection of the resolvent sets of the operators A_{n} is empty. But since A_{n} is a generator of a C_{0}-semigroup for each n ∈ N, there exists ω_{n} > 0 such that R(λ, A_{n}) exists for all λ > ω_{n}. Hence, R_{n}(λ) is an analytic continuation of W_{n}R(λ, A_{n}) from (ω_{n}, ∞) to (ω, ∞).

Proof of Theorem 2.2: (i)⟹(ii): By condition (c) and the definition of R_{n}(λ), a simple calculation shows that ∥R_{n}(λ)∥ ≤ M(λ − ω)^{−1} for all λ > ω. Then it follows from Banach’s Convergence Theorem that statement (i) is equivalent to

lim_{n→∞} R_{n}(λ)f = R(λ, A)f  (2.9)

for all f ∈ E.

Condition (c) implies that the function t↦∫_{0}^{t} W_{n}S_{n}(τ)fdτ is in Lip_{ω} (see Definition 2.1) and ∥ ∫_{0}^{t} W_{n}S_{n}(τ)fdτ∥_{Lip_{ω}} ≤ M for all f ∈ E. By Remark 2.1 and the definition of R_{n}, the Laplace-Stieljes transform of ∫_{0}^{t} W_{n}S_{n}(τ)f dτ is R_{n}(λ)f. Since the Laplace-Stieljes transform of ∫_{0}^{t} S(τ)f dτ is R(λ, A)f, it follows from (2.9) and Theorem 2.1 that

lim_{n→∞} ∫_{0}^{t} W_{n}S_{n}(t)f dt = ∫_{0}^{t} S(t)f dt  (2.10)

for all f ∈ E.

Let f ∈E and λ > ω. By condition (c) and Remark 2.1,

\begin{aligned}R_{n}(λ)f & = & λ ∫_{0}^{∞} e^{−λt} (∫_{0}^{t} W_{n}S_{n}(τ)f dτ) dt \\ & = & λ ∫_{0}^{∞} e^{−λt}W_{n} (∫_{0}^{t} S_{n}(τ)f dτ) dt. \end{aligned}  (2.11)

Since ∫_{0}^{t} S_{n}(τ)f dτ ∈D(A_{n}), the commutativity condition (b) implies that W_{n} ∫_{0}^{t} S_{n}(τ)f dτ ∈ D(A_{n}). Then it follows from (2.11) that R_{n}(λ)f ∈ D(A_{n}). Thus, by the closedness of A_{n} and the commutativity condition (b),

\begin{aligned}A_{n}R_{n}(λ)f & = & λ ∫_{0}^{∞} e^{−λt}A_{n}W_{n} (∫_{0}^{t} S_{n}(τ)f dτ) dt \\ & = & λ ∫_{0}^{∞} e^{−λt}W_{n} (A_{n} ∫_{0}^{t} S_{n}(τ)f dτ) dt \\ & = & λ ∫_{0}^{∞} e^{−λt}W_{n} (S_{n}(t)f − f) dt \\ & = & λR_{n}(λ)f − W_{n}f. \end{aligned}  (2.12)

Since AR(λ)f = λR(λ, A)f−f, equation (2.9), condition (a) and equality (2.12) imply that for all f ∈ E,

lim_{n→∞} A_{n}R_{n}(λ)f = AR(λ, A)f.  (2.13)

For f ∈ E, let V_{n}(t)f := A_{n} ∫_{0}^{t} W_{n}S_{n}(τ)fdτ = W_{n}S_{n}(t)f − W_{n}f. Then, condition (c) implies that

∥V_{n}(t)∥ ≤ Me^{ωt} + M.  (2.14)

Now for f ∈ E,

\begin{aligned}∥W_{n}S_{n}(t)f − S(t)f∥ & ≤ & ∥W_{n}[S_{n}(t)f − f] − [S(t)f − f]∥ + ∥W_{n}f − f∥ \\ & = & ∥V_{n}(t)f − A ∫_{0}^{t} S(τ)f dτ∥ + ∥W_{n}f − f∥ \end{aligned}

Since ∥W_{n}f −f∥ → 0 by condition (a), to show lim_{n→∞}∥W_{n}S_{n}(t)f − S(t)f∥ = 0 it suffices to show that

lim_{n→∞} V_{n}(t)f = ∫_{0}^{t} AS(τ)f dτ  (2.15)

for all f ∈ D(A) (due to (2.14) and Banach’s Convergence Theorem.

For f ∈D(A), let g = (λ − A)f for some λ > ω. Then,

∥V_{n}(t)f − ∫_{0}^{t} AS(τ)f dτ∥ ≤ ∥ ∫_{0}^{t} W_{n}A_{n}S_{n}(τ)[R(λ, A) − R_{n}(λ)]gdτ∥
+ ∥ ∫_{0}^{t} W_{n}S_{n}(τ)[A_{n}R_{n}(λ) − AR(λ,A)]gdτ∥
+ ∥ ∫_{0}^{t}[W_{n}S_{n}(τ) − S(τ)]AR(λ, A)gdτ∥.

Denote the three terms on the right hand side of the above inequality by I_{1}, I_{2} and I_{3} respectively. Then lim_{n→∞} I_{1} = 0 by (2.14) and (2.9), lim_{n→∞} I_{2} = 0 by (2.13) and condition (c), and lim_{n→∞} I_{3} = 0 by (2.10). Therefore, (2.15) holds for all f ∈ D(A).

(ii)⟹(i): It is well known that R(λ, A)f = ∫_{0}^{∞} e^{−λt}S(t)fdt for λ > ω and f ∈ E. Then with statement (ii) and the stability condition (c), statement (i) follows from the dominated convergence theorem.

The commutativity condition (b) in Theorem 2.2 is a severe restriction on the stabilizing operators W_{n}. The stabilizers W_{n} given in Example 2.2 do not commute with the semigroups they stabilize, so the theorem is not applicable. But if we choose the stabilizers W_{n} to be W_{n} = \binom{Q_{n} 0}{0 Q_{n}}, where Q_{n} = (I − \frac{1}{nπ} \frac{d^{2}}{dx^{2}} )^{−1}, then it is verifiable that W_{n} and A_{n} commute. Thus in this case, the unstable semigroup sequence {S_{n}} converges strongly to S under the stabilization of these new stabilizers.

2.3 Unstable Spatial Approximations

In this section we will derive several results with the commutativity condition removed. To establish these convergence result for stabilized semigroups, we need to modify the stabilizability condition accordingly.

Theorem 2.3 Suppose that A generates a C_{0}-semigroup S with ∥S(t)∥ ≤ Me^{ωt} (M, ω > 0 and t ≥ 0). For n ∈ N, let W_{n} ∈ L(E) and A_{n} be the generators of C_{0}-semigroups S_{n}. Assume that

(a) f_{o} ∈ D:=∩_{n=1}^{∞}D(A_{n}) ∩ D(A),

(b) lim_{n→∞} W_{n}f = f for all f ∈ D(A), and

(c) ∥W_{n}S_{n}(t)A_{n}f∥ ≤ M_{f}e^{ω_{f} t} for all f ∈ D(A_{n}) and for f-dependent constants M_{f} > 0, ω_{f} ≥ ω.

Then for each f ∈ D, the integrals R_{n}(λ)f := ∫_{0}^{∞} e^{−λt}W_{n}S_{n}(t)f dt and R_{n}(λ)A_{n}f := ∫_{0}^{∞} e^{−λt}W_{n}S_{n}(t)A_{n}f dt exist for all λ > ω_{f} and n ∈ N; and the following statements are equivalent.

( i ) lim_{n→∞} R_{n}(λ)f_{o} = R(λ, A)f_{o} for all λ > ω_{f_{o}}.

(i i) lim_{n→∞} W_{n}S_{n}(t)f_{o} = S(t)f_{o} uniformly for t in compact intervals of [0, ∞).

Proof: Since each operator A_{n} generates a C_{0}-semigroup S_{n} for n∈N, it follows that for f ∈D

S_{n}(t)f = f + ∫_{0}^{t} S_{n}(τ)A_{n}fdτ.

From the boundedness of W_{n} we obtain that

W_{n}S_{n}(t)f = W_{n}f + ∫_{0}^{t} W_{n}S_{n}(τ)A_{n}fdτ.

Conditions (b) and (c) imply that

∥W_{n}S_{n}(t)f∥ ≤ sup_{n∈N} ∥W_{n}f∥ + M_{f} ∫_{0}^{t} e^{ω_{f} τ} dτ = G_{f}e^{ω_{f} t},

for some constant G_{f}. Thus the integrals R_{n}(λ)f are well defined for all λ>ω_{f} and n∈N. Due to condition (c), the integral R_{n}(λ)A_{n}f exists for f ∈D, λ>ω_{f}, and n∈N. Thus, for each f ∈D the integrals R_{n}(λ)(λ−A_{n})f also exist for all λ>ω_{f} and n∈N.

Now, for f ∈D, λ>ω_{f}, and n∈N,

λR_{n}(λ)f = λ ∫_{0}^{∞} e^{−λt}W_{n}S_{n}(t)fdt
= λ ∫_{0}^{∞} e^{−λt}W_{n}[f + ∫_{0}^{t} S_{n}(τ)A_{n}fdτ]dt
= W_{n}f + λ ∫_{0}^{∞} e^{−λt} ∫_{0}^{t} W_{n}S_{n}(τ)A_{n}f dτ dt
= W_{n}f + ∫_{0}^{∞} e^{−λt}W_{n}S_{n}(t)A_{n}f dt
= W_{n}f + R_{n}(λ)A_{n}f,

which is equivalent to

R_{n}(λ)(λ−A_{n})f = W_{n}f  (2.16)

for f ∈ D(A_{n}), λ > ω_{f} and n ∈ N. Since R(λ, A)(λ−A)f = f for all f ∈ D(A) and λ > ω, and since lim_{n→∞} W_{n}f = f for f ∈ D(A), it follows that statement (i) is equivalent to

(i′)  lim_{n→∞} R_{n}(λ)A_{n}f_{o} = R(λ, A)Af_{o}

for all λ > ω_{f_{o}}.

Let W_{0} := I, S_{0}(t) := S(t) and A_{0} := A. Then, R_{0}(λ) = R(λ, A), and for all n ∈ N_{0} and f ∈ D(A_{n}), W_{n}S_{n}(t)f − W_{n}f = ∫_{0}^{t} W_{n}A_{n}S_{n}(τ)fdτ since A_{n} generates the C_{0}-semigroup S_{n}. Since lim_{n→∞} W_{n}f = f for all f ∈ D(A), it follows that statement (ii) is equivalent to

(ii′)  lim_{n→∞} ∫_{0}^{t} W_{n}A_{n}S_{n}(τ)f_{o}dτ = ∫_{0}^{t} AS(τ)f_{o}dτ.

For n ∈ N_{0}, let v_{n}(t) := ∫_{0}^{t} W_{n}A_{n}S_{n}(τ)f_{o}dτ = ∫_{0}^{t} W_{n}S_{n}(τ)A_{n}f_{o}dτ. An easy calculation shows that the Laplace-Stieljes transform of v_{n} is

(L_{s}v_{n}) (λ) = R_{n}(λ)A_{n}f_{o},

for all n∈N_{0}. By condition (c), v_{n} ∈Lip_{ω} and sup_{n∈N} ∥v_{n}∥_{Lip_{ω}} ≤M_{f_{o}}. It then follows from Theorem 2.1 that statements (i′) and (ii′) are equivalent.

Theorem 2.3 relates the strong convergence of stabilized “resolvents” to that of the stabilized semigroups. It is common that the strong convergence of generators, rather than resolvents, is given. The following is a result relating the strong convergence of generators to that of their stabilized semigroups.

Corollary 2.1 Suppose that A generates a C_{0}-semigroup S with ∥S(t)∥ ≤ Me^{ωt} (M, ω, t > 0). For n ∈ N, let W_{n} ∈ L(E) and A_{n} with D(A_{n}) ⊃ D(A) be generators of C_{0}-semigroups S_{n}. If

(a) lim_{n→∞} W_{n}f = f for all f ∈ D(A), (b) ∥W_{n}S_{n}(t)∥ ≤ Me^{ωt}, and

(c) lim_{n→∞} A_{n}f = Af for all f ∈D(A^{∞}),

then, for all f ∈E, lim_{n→∞}W_{n}S_{n}(t)f = S(t)f uniformly for t in compact intervals of [0, ∞).

Proof: Condition (c) implies that for f ∈ D(A^{∞}), there exists an f-dependent positive constant M_{f} such that ∥A_{n}f∥ ≤ M_{f} for all n∈N. Then,

\begin{aligned}∥W_{n}S_{n}(t)A_{n}f∥ & ≤ & ∥W_{n}S_{n}(t)∥ · ∥A_{n}f∥ \\ & ≤ & Me^{ωt}∥A_{n}f∥ \\ & ≤ & M_{f}Me^{ωt}. \end{aligned}  (2.17)

Now, for f ∈ D(A^{∞}), λ > ω, and n ∈ N, let R_{n}(λ)f := ∫_{0}^{∞} e^{−λt}W_{n}S_{n}(t)f dt and g := R(λ, A)f. Then

∥R_{n}(λ)f −R(λ, A)f∥ = ∥[R_{n}(λ)(λ−A)g − g∥
= ∥ [R_{n}(λ)(λ−A) − I] g∥
= ∥ [R_{n}(λ)(λ−A_{n}) + R_{n}(λ)(A_{n}−A) − I] g∥.

Obviously, g = R(λ, A)f ∈D(A^{∞})⊂D(A). Then (2.16) implies that

R_{n}(λ)(λ − A_{n})g = W_{n}g.

Therefore,

\begin{aligned}∥R_{n}(λ)f −R(λ,A)f∥ & = & ∥ [W_{n} + R_{n}(λ)(A_{n} − A) − I] g∥ \\ & ≤ & ∥(W_{n}−I)g∥+∥R_{n}(λ)(A_{n}−A)g∥. \end{aligned}  (2.18)

Using the definition of R_{n}(λ) and condition (b), an easy calculation shows that ∥R_{n}(λ)∥ ≤ M(λ − ω)^{−1}. This, together with (2.18), implies

∥R_{n}(λ)f− R(λ, A)f∥ ≤ ∥(W_{n}− I)g∥ + \frac{M}{λ−ω} ∥(A_{n}−A)g∥.  (2.19)

Since g ∈D(A^{∞}), it follows from condition (c) that lim_{n→∞}(A_{n}−A)g = 0. And since (W_{n}−I)g →0 by condition (a), it follows from (2.19) that R_{n}(λ)f converges to R(λ, A)f. Then, we obtain from (2.17) and Theorem 2.3 that for all f ∈D(A^{∞}),

lim_{n→∞} W_{n}S_{n}(t)f = S(t)f  (2.20)

uniformly for t in compact intervals of [0, ∞). By Theorem 2.7 in Pazy’s [28], D(A^{∞}) is dense in E and hence total in E. Thus we obtain from Banach’s Convergence Theorem the convergence in (2.20) for all f ∈E uniformly for t in compact intervals of [0, ∞).

Now, with the above corollary, we re-examine the problem discussed in Examples 2.1 and 2.2 from the viewpoint of convergence.

Example 2.3 Using Corollary 2.1, statement (i) in Example 2.1, and statements (a) and (b) in Example 2.2, we obtain that the unstable sequence of semigroups {S_{n}} converges strongly to S under stabilization of {W_{n}}, namely, lim_{n→∞}W_{n}S_{n}(t)f = S(t)f for all f ∈ E. The stabilizability condition (a) proven in Example 2.2 further implies that for any f ∈ E and any sequence {f_{n}} convergent to f, the limit

lim_{n→∞} W_{n}S_{n}(t)f_{n} = S(t)f

holds uniformly for t in compact intervals, due to the following inequalities

\begin{aligned}∥W_{n}S_{n}(t)f_{n} − S(t)f∥ & ≤ & ∥W_{n}S_{n}(t)(f_{n} − f)∥ + ∥W_{n}S_{n}(t)f − S(t)f∥ \\ & ≤ & ∥W_{n}S_{n}(t)∥ · ∥f_{n} − f∥ + ∥W_{n}S_{n}(t)f − S(t)f∥. \end{aligned}

It is evident from the proof of Theorem 2.3 that we can weaken the C_{0}-semigroup assumption for S since the uniform norm-boundedness ∥S(t)∥ ≤ Me^{ωt} is not used at all. And we can also relinquish the C_{0}-semigroup assumption for the approximating operator families S_{n} because we only require an initial value dependent uniform boundedness condition, not uniform norm-boundedness. In the following theorem, we will weaken the assumptions of Theorem 2.3 and generalize it, in the case of W_{n} = I, to families of linear, possibly unbounded, and even unclosed operators.

Theorem 2.4 Let {A_{n}}_{n=0}^{∞} be a sequence of linear operators. Let f ∈∩_{n=0}^{∞}D(A_{n}^{∞}). For each n∈N_{0}, let {S_{n}(t) : t ≥ 0} be a one parameter family of linear operators with S_{n}(0) = I and ∩_{t≥0}D(S_{n}(t))⊃ D for all n∈N. Suppose that

(a) the function t ↦ S_{n}(t)f is differentiable for all t ≥ 0 and \frac{d S_{n}(t)f}{dt} = S_{n}(t)A_{n}f for n∈N_{0}, and

(b) there exist constants M, ω ≥0 such that ∥S_{n}(t)A_{n}f∥ ≤ Me^{ωt} for all t ≥ 0 and n∈N_{0}.

Then the following statements are equivalent.

( i ) lim_{n→∞}R_{n}(λ)f =R_{0}(λ)f for all λ>ω, where R_{n}(λ)f:=∫_{0}^{∞}e^{−λt}S_{n}(t)fdt for λ > ω.

(i i) lim_{n→∞} S_{n}(t)f = S_{0}(t)f uniformly for t in compact intervals of [0, ∞).

Proof: Condition (a) implies that

S_{n}(t)f − f = ∫_{0}^{t} S_{n}(τ)A_{n}fdτ for n∈N_{0}.  (2.21)

Then, condition (b) implies that

∥S_{n}(t)f∥ ≤ ∥f∥ + M_{f} ∫_{0}^{t} e^{ωτ} dτ = ∥f∥ + ω^{−1}M_{f} (e^{ωt} − 1) .

Then R_{n}(λ)f is well defined for λ>ω, and n∈N_{0}.

Equation (2.21), condition (b) and Remark 2.1 imply that for each n∈N_{0}, the function t ↦ (S_{n}(t)f −f) has a Laplace-Stieljes transform and its Laplace-Stieljes transform satisfies

[L_{s}(S_{n}(·)f −f)](λ) = λ ∫_{0}^{∞} e^{−λt} ∫_{0}^{t} S_{n}(τ)A_{n}fdτdt
= λ ∫_{0}^{∞} e^{−λt}(S_{n}(t)f − f)dt
= λR_{n}(λ)f − f.

for all λ > ω. Then, statement (i) is equivalent to

(i′)  lim_{n→∞}[L_{s}(S_{n}(·)f −f)](λ) = [L_{s}(S_{0}(·)f −f)](λ)f for λ>ω.

With conditions (a) and (b), a straightforward calculation using (2.21) shows that the Lip_{ω} norm of S_{n}(·)f −f as defined in Definition 2.1 satisfies

∥S_{n}(·)f∥_{Lip_{ω}} ≤ M

for all n∈N_{0}. Then, by Theorem 2.1, (i′) is equivalent to

lim_{n→∞} S_{n}(t)f −f = S_{0}(t)f −f

uniformly for t in compact intervals, which is obviously equivalent to (ii).

Without the C_{0}-semigroup assumption for the operator family S, Theorem 2.4 aims at ill-posed problems (as opposed to well-posed problems where the spatial operator A generates a C_{0}-semigroup). We would like to mention that in this dissertation we are not going further toward that direction. Like Theorem 2.3, the main contribution of Theorem 2.4, at least in this dissertation, is to serve as a bridge to the study of other approximation methods. Because A is not required to be a C_{0}-semigroup, and because of the flexibility of allowing unstable or even unbounded spatial approximation methods, we are able to unify stable temporal approximation methods with a general class of possibly unstable but Von-Neumann stable methods in the next chapter. This is done by bridging the temporal methods to the true solution with a sequence of spatially approximating problems, which are constructed from the approximating temporal methods and have only initial value dependent uniform boundedness.

3 Temporal Approximations

One practically useful convergence theorem for temporal approximation methods is the following result originally due to Chernoff (see [28], pp. 90).

Theorem (Chernoff Product Formula) Suppose that A is the generator of a C_{0}- semigroup S with ∥S(t)∥ ≤ Me^{ωt} for all t ≥ 0 for some constants M, ω > 0. Let {V (t) : t ∈ [0, ∞]} be a temporal approximation method which is consistent on D(A) and satisfies ∥V (t)^{n}∥ ≤ Me^{nωt} for all (n, t)∈N×[0, δ]. Then, for each f ∈ E, lim_{n→∞} V (\frac{t}{n})^{n}f = S(t)f uniformly for t in compact interval [0, T] for any T > 0.

In this chapter, we will generalize Chernoff’s product formula to (i) stabilized temporal approximation methods, and (ii) to Von Neumann stable temporal approximations.

3.1 Stabilized Temporal Approximations

As an application of Corollary 2.1, we extend in this section the Chernoff product formula to possibly unstable, but stabilizable approximation methods.

Theorem 3.1 Suppose that A generates a C_{0}-semigroup S with ∥S(t)∥ ≤ Me^{ωt} for all t ≥ 0 and some constants M, ω ≥ 0 independent of t. Let {V (t) : t ∈ [0, δ]} and {W (t) : t ∈ [0, δ]} be two strongly continuous families of bounded linear operators on E satisfying V (0) = W (0) = I, lim_{t→0} \frac{V (t)f−f}{t} = Af for all f ∈D(A^{∞}), and

∥W (t)V (t)^{k−1}∥ ≤ Me^{ωtk}  (3.1)

for all (k, t) ∈ N_{0}×[0, δ]. Then, for any f ∈ E, lim_{n→∞} W (\frac{t}{n})V (\frac{t}{n})^{n−1}f = S(t)f uniformly for t in compact intervals.

Lemma 3.1 Let W (t), V (t) be as in Theorem 3.1. Define A_{s}f := \frac{V (s)−I}{s} f for all s ∈ (0, T], f ∈ E. Then for any ω_{o} > ω, there exist s_{o} > 0 such that ∥W (s)e^{tA_{s}}∥ < Me^{ω_{o}(t+s)} whenever s∈(0, s_{o}).

Proof: By definition, A_{s} is bounded. Thus, e^{tA_{s}}f = lim_{m→∞} (I + \frac{t}{m}A_{s})^{m} f for all f ∈ E, and therefore

∥W (s)e^{tA_{s}}f∥ = lim_{m→∞} ∥W (s) (I + \frac{t}{m}A_{s})^{m} f∥
= lim_{m→∞} ∥W (s) (I + \frac{t}{m} \frac{V (s)−I}{s} )^{m} f∥
= lim_{m→∞} ∥W (s) (\frac{ms−t}{ms} + \frac{t}{ms}V (s))^{m} f∥
= lim_{m→∞} ∥W (s)[λ_{m} + μ_{m}V (s)]^{m}f∥,

(3.2)

where λ_{m} := \frac{ms−t}{ms} and μ_{m} := 1 − λ_{m} = \frac{t}{ms}. Since λ_{m} > 0 for m large, it follows that

∥W (s) (λ_{m} + μ_{m}V (s))^{m} f∥ = ∥ ∑_{i=0}^{m} \binom{m}{i} λ_{m}^{m−i}μ_{m}^{i}W (s)V (s)^{i}f∥
≤ ∑_{i=0}^{m} \binom{m}{i} λ_{m}^{m−i}μ_{m}^{i}Me^{ω(1+i)s}∥f∥
= Me^{ωs} (λ_{m} + μ_{m}e^{ωs})^{m} ∥f∥.

It follows from (3.2) that ∥W (s)e^{tA_{s}}∥ ≤ Me^{ωs} lim_{m→∞} (1 + μ_{m}(e^{ωs}−1))^{m} by noticing that λ_{m} = 1 − μ_{m}. For ω_{o} > ω there exists s_{o} > 0 such that e^{ωs} − 1 ≤ ω_{o}s for all s ∈ (0, s_{o}]. Then ∥W (s)e^{tA_{s}}∥ ≤ Me^{ωs} lim_{m→∞} (1 + μ_{m}ω_{o}s)^{m}. Replacing μ_{m} by \frac{t}{ms}, we obtain

∥W (s)e^{tA_{s}}∥ = Me^{ωs} lim_{m→∞} (1 + \frac{ω_{o}t}{m})^{m} ≤ Me^{ω_{o}(s+t)},

which proves the lemma.

The following lemma extends an estimate due to Chernoff [7]. The proof is a modification of Chernoff’s original proof for his estimate.

Lemma 3.2 Let W, L ∈ L(E). Suppose there exist constants M, l ≥ 1 such that for all f ∈ E, ∥W L^{n}∥ ≤ Ml^{n+1} for all n ≥ 0. Then

∥W e^{n(L−I)}f −W L^{n}f∥ ≤ M\sqrt{n}l^{n}e^{(l^{2}−1)n/2}∥ · ∥Lf − f∥

for each f ∈ E and n ∈ N.

Proof: Let f ∈E. Clearly, for n∈N,

∥W e^{n(L−I)}f −W L^{n}f∥ ≤ e^{−n} ∑_{k=0}^{∞} \frac{n^{k}}{k!} ∥W L^{k}f −W L^{n}f∥.  (3.3)

Now for k ≥ n,

∥W L^{k}f − W L^{n}f∥ ≤ ∑_{i=n+1}^{k} ∥W L^{i}f − W L^{i−1}f∥
≤ ∑_{i=n+1}^{k} ∥W L^{i−1}∥ · ∥Lf − f∥
≤ ∑_{i=n+1}^{k} Ml^{i−1}∥Lf − f∥
≤ Ml^{k} ∑_{i=n+1}^{k} ∥Lf − f∥
≤ Ml^{k}|k − n| · ∥Lf − f∥
≤ Ml^{k+n}|k − n| · ∥Lf − f∥.

Similarly, we can prove that ∥W L^{k}f − W L^{n}f∥ ≤ Ml^{k+n}|k − n| · ∥Lf − f∥ for k < n. It follows from (3.3) that

∥e^{n(L−I)}f − L^{n}f∥ ≤ e^{−n} ∑_{k=0}^{∞} \frac{n^{k}}{k!} M l^{k+n}|k−n| · ∥Lf −f∥
≤ \frac{M l^{n}}{e^{n}} ∥Lf −f∥ ∑_{k=0}^{∞} \frac{n^{k}}{k!} |n − k|l^{k}
= \frac{M l^{n}}{e^{n}} ∥Lf −f∥ ∑_{k=0}^{∞} \frac{(\sqrt{n}l)^{k}}{\sqrt{k!}} \frac{(\sqrt{n})^{k}(n−k)}{\sqrt{k!}}.

Then by Schwartz inequality for inner products,

\begin{aligned}∥e^{n(L−I)}f − L^{n}f∥ & ≤ & \frac{M l^{n}}{e^{n}} ∥Lf −f∥ \{∑_{k=0}^{∞} \frac{(nl^{2})^{k}}{k!} \}^{1/2}\{∑_{k=0}^{∞} \frac{n^{k}}{k!} (n−k)^{2}\}^{1/2} \\ & = & \frac{M l^{n}}{e^{n}} ∥Lf −f∥e^{nl^{2}/2} \{∑_{k=0}^{∞} \frac{n^{k}}{k!} (n^{2}−2nk+k^{2})\}^{1/2} . \end{aligned}

But the summation ∑_{k=0}^{∞} \frac{n^{k}}{k!} (n^{2}−2nk+k^{2}) can be simplified into

∑_{k=0}^{∞} \frac{n^{k}}{k!} (n^{2}−2nk+k^{2}) = n^{2}e^{n} − 2n ∑_{k=1}^{∞} \frac{n^{k}}{(k−1)!} + ∑_{k=1}^{∞} \frac{kn^{k}}{(k−1)!}
= n^{2}e^{n} − 2n^{2}e^{n} + ∑_{k=0}^{∞} \frac{(k+1)n^{k+1}}{k!}
= −n^{2}e^{n} + n ∑_{k=0}^{∞} \frac{(k+1)n^{k}}{k!}
= −n^{2}e^{n} + n(ne^{n} + e^{n}) = ne^{n}.

Thus,

\begin{aligned}∥e^{n(L−I)}f − L^{n}f∥ & ≤ & \frac{M l^{n}}{e^{n}} ∥Lf −f∥e^{nl^{2}/2}(ne^{n})^{1/2} \\ & = & M\sqrt{n} l^{n}e^{(l^{2}−1)n/2}∥Lf −f∥. \end{aligned}

Lemma 3.3 Let W (t), V (t) and A_{s} be as in Lemma 3.1. Then, for any T > 0 and f ∈ E,

lim_{n→∞} ∥W (t/n)V^{n}(t/n)f − W (t/n)e^{tA_{t/n}}f∥ = 0  (3.4)

uniformly for t∈(0, T].

Proof: By the condition (3.1) and Lemma 3.1, ∥W(t/n)V^{n}(t/n)f − W(t/n)e^{tA_{t/n}}f∥ is exponentially bounded. Since D(A^{∞}) is dense in E it suffices to show that (3.4) holds for f ∈D(A^{∞}) by Banach’s Convergence Theorem.

For s∈(0, T], ∥W (s)V^{n}(s)∥ ≤ Ml^{n}, where l = e^{ωs} ≥1. Then, by Lemma 3.2,

\begin{aligned}∥W (s)V^{n}(s)f − W (s)e^{n(V (s)−I)}f∥ & ≤ M\sqrt{n}l^{n}e^{(l^{2}−1)n/2}∥V (s)f − f∥ \\ & = M\sqrt{n}e^{nωs}e^{(e^{2ωs}−1)n/2}∥V (s)f − f∥. \end{aligned}

By setting s = \frac{t}{n} and noticing that e^{n(V ( \frac{t}{n})−I)}f = e^{tA_{t/n}}f, we obtain

∥W (\frac{t}{n})V^{n}(\frac{t}{n})f − W (\frac{t}{n})e^{tA_{t/n}}f∥ ≤ M\sqrt{n}e^{ωt}e^{(e^{2ωt/n}−1)n/2}∥V (\frac{t}{n})f − f∥.

For any ω_{o} > ω, there exists n_{o} (dependent on T) such that for all t ∈ (0, T], e^{2ωt/n} − 1 < 2ω_{o}t/n for all n > n_{o}. So, for all n > n_{o},

\begin{aligned}∥W (\frac{t}{n})V^{n}(\frac{t}{n})f − W (\frac{t}{n})e^{tA_{t/n}}f∥ & ≤ & M\sqrt{n}e^{ωt}e^{ω_{o}t}∥V (\frac{t}{n})f − f∥ \\ & ≤ & M \frac{t}{\sqrt{n}}e^{2ω_{o}t} \frac{∥V (t/n)f−f∥}{t/n}. \end{aligned}

Since lim_{n→∞} \frac{∥V (t/n)f−f∥}{t/n} = Af for f ∈ ∩_{k=1}^{∞}D(A^{k}), it follows that

lim_{n→∞} ∥W (t/n)V^{n}(t/n)f − W (t/n)e^{tA_{t/n}}f∥ = 0

uniformly for t ∈ (0, T].

Proof of Theorem 3.1: For f ∈ E,

∥W (\frac{t}{n})V^{n−1}(\frac{t}{n})f − S(t)f∥ ≤ ∥W (\frac{t}{n})V^{n−1}(\frac{t}{n})f − W (\frac{t}{n})V^{n}(\frac{t}{n})f∥
+ ∥W (\frac{t}{n})V^{n}(\frac{t}{n})f − W (\frac{t}{n})e^{tA_{t/n}}f∥
+ ∥W (\frac{t}{n})e^{tA_{t/n}}f − S(t)f∥.

Let I_{1}, I_{2} and I_{3} denote the three components in the right hand side of the above inequality. We already know that I_{2} →0 as n→∞ uniformly for t∈[0, T] (by Lemma 3.3).

For I_{1} we have that

\begin{aligned}I_{1} & = & ∥W (\frac{t}{n})V^{n−1}(\frac{t}{n})\{V (\frac{t}{n})f − f\}∥ \\ & ≤ & Me^{ωt}∥V (\frac{t}{n})f − f∥. \end{aligned}

where the last inequality is due to the stability assumption (3.1). Since V (0) = I, the strong continuity of V implies that I_{1} → 0 uniformly for t ∈ [0, T] as n → ∞.

It remains to be shown that I_{3} → 0. By the definition of A_{s}, lim_{s→0}A_{s}f = V′(0)f = Af for f ∈∩_{k=1}^{∞}D(A^{k}). By Lemma 3.1, there exist ω_{o}, M_{o} >0 such that ∥W (s)e^{tA_{s}}∥ ≤ M_{o}e^{tω_{o}}. Since W is a strongly continuous family of bounded linear operators and W(0) = I, W(s) converges strongly to the identity operator I as s → 0. Then, by Corollary 2.1, I_{3} → 0 uniformly for t ∈ [0, T] as n → ∞.

3.2 Unstable Temporal Approximations

3.2.1 An Exponential Formula

In this subsection, we will generalize an exponential formula for semigroups generated by bounded linear operators [23, 24, 39] to one-parameter families of linear (possibly unbounded and even not closed) operators.

Lemma 3.4 Let A be a linear operator and f ∈D(A^{∞}). Suppose that there exists constants M > 0 and ω ≥ 1 such that

∥A^{n}f∥ ≤ Mω^{n} for all n∈N,  (3.5)

Let t ↦ e^{tA}f : [0, ∞) → E be defined by e^{tA}f := ∑_{n=0}^{∞} \frac{t^{n}A^{n}}{n!} f. Then,

( i ) e^{tA}f is well-defined, entire, and \frac{d}{dt}e^{tA}f = e^{tA}Af = ∑_{n=0}^{∞} \frac{t^{n}A^{n}}{n!} Af;

(i i) (L_{s}e^{tA}f)(λ) = ∫_{0}^{∞} e^{−λt}e^{tA}Af dt for all f ∈D(A^{∞}) and λ > ω;

(iii) for any T > 0, e^{tA}f = lim_{n→∞}(I + \frac{t}{n}A)^{n}f uniformly for t∈[0, T].

Proof: (i) It is obvious that the series ∑_{n=0}^{∞} \frac{t^{n}A^{n}}{n!} f is uniformly convergent for all t ∈ C. Thus e^{tA}f is well-defined, entire, and

\begin{aligned}\frac{d}{dt}e^{tA}f & = & ∑_{n=0}^{∞} \frac{d}{dt} \frac{t^{n}A^{n}}{n!} f \\ & = & ∑_{n=0}^{∞} \frac{t^{n}A^{n}}{n!} Af = e^{tA}Af. \end{aligned}

(ii) It is easily verifiable that condition (3.5) implies that ∥e^{tA}f∥ ≤ Me^{ωt} and ∥e^{tA}Af∥ ≤ ωMe^{ωt} for t ≥ 0. Then, by statement (i) of this lemma and Remark 2.1, the map t↦e^{tA}f has Laplace-Stieljes transform for λ > ω given by

L_{s}(e^{tA}f)(λ) = ∫_{0}^{∞} e^{−λt}e^{tA}Af dt.

To prove statement (iii) of the lemma above, we need the following lemma which extends an estimate due to Chernoff [7].

Lemma 3.5 Let L be a linear operator defined on D(L) ⊂ E. Suppose that there exists a constant l ≥ 1 such that for each f ∈D(L^{∞}), there exists an f-dependent constant M_{f} such that

∥L^{n+1}f − L^{n}f∥ ≤ M_{f} l^{n}

for all n ≥ 0. Then, for each t ≥ 0, the operator e^{t(L−I)} : f ↦∑_{n=0}^{∞} \frac{t^{n}(L−I)^{n}}{n!} f is well-defined on D(L^{∞}), and ∥e^{n(L−I)}f − L^{n}f∥ ≤ M_{f} \sqrt{n} l^{n}e^{(l^{2}−1)n/2} for f ∈D(L^{∞}) and n∈N_{0}.

Proof: For f ∈D(L^{∞}) and n∈N,

∥(L − I)^{n}f∥ = ∥(L − I)^{n−1}(L − I)f∥
= ∥ ∑_{i=0}^{n−1} \binom{n−1}{i} (−1)^{n−i}L^{i}(L − I)f∥
≤ ∑_{i=0}^{n−1} \binom{n−1}{i} ∥L^{i}(L − I)f∥
≤ ∑_{i=0}^{n−1} \binom{n−1}{i} M_{f} l^{i}
= M_{f}(1 + l)^{n−1}.

Then, by Lemma 3.4, e^{t(L−I)}f is well-defined for all t > 0 and f ∈D(L^{∞}).

It is well known that the series ∑_{k=0}^{∞} \frac{t^{k}}{k!} is absolutely convergent to e^{t}. Therefore the series ∑_{k=0}^{∞} \frac{t^{k}}{k!} L^{k}f converges to e^{tL}f by the convergence theorem for the Cauchy product e^{t}e^{t(L−I)}f. Thus, we have that e^{n(L−I)}f = e^{−n}∑_{k=0}^{∞} \frac{n^{k}}{k!} L^{k}f for all f ∈ D(L^{∞}), which implies that

∥e^{n(L−I)}f − L^{n}f∥ = e^{−n} ∥∑_{k=0}^{∞} \frac{n^{k}}{k!} (L^{k} − L^{n})f∥ .  (3.6)

Now, for k ≥ n and f ∈ D(L^{∞}),

∥L^{k}f − L^{n}f∥ ≤ ∑_{i=n+1}^{k} ∥L^{i}f − L^{i−1}f∥
≤ ∑_{i=n+1}^{k} M_{f}l^{i}
≤ M_{f}l^{k+n}|k − n|.

Similarly we can prove that ∥L^{k}f − L^{n}f∥ ≤ M_{f}l^{k+n}|k − n| for k < n. It then follows from (3.6) that

∥e^{n(L−I)}f − L^{n}f∥ ≤ e^{−n} ∑_{k=0}^{∞} \frac{n^{k}}{k!} ∥L^{k}f − L^{n}f∥
≤ M_{f}e^{−n}l^{n} ∑_{k=0}^{∞} \frac{n^{k}}{k!} |n − k|l^{k}
= M_{f}e^{−n}l^{n} ∑_{k=0}^{∞} \frac{(\sqrt{n}l)^{k}}{\sqrt{k!}} \frac{(\sqrt{n})^{k}(n−k)}{\sqrt{k!}}.

Then, by Schwartz inequality for inner products,

\begin{aligned}∥e^{n(L−I)}f − L^{n}f∥ & ≤ & \frac{M_{f} l^{n}}{e^{n}} \{∑_{k=0}^{∞} \frac{(nl^{2})^{k}}{k!} \}^{1/2}\{∑_{k=0}^{∞} \frac{n^{k}}{k!} (n−k)^{2}\}^{1/2} \\ & = & \frac{M_{f} l^{n}}{e^{n}} e^{nl^{2}/2} \{∑_{k=0}^{∞} \frac{n^{k}}{k!} (n^{2}−2nk+k^{2})\}^{1/2} . \end{aligned}

But,

∑_{k=0}^{∞} \frac{n^{k}}{k!} (n^{2}−2nk+k^{2}) = n^{2}e^{n} − 2n ∑_{k=1}^{∞} \frac{n^{k}}{(k−1)!} + ∑_{k=1}^{∞} \frac{kn^{k}}{(k−1)!}
= n^{2}e^{n} − 2n^{2}e^{n} + ∑_{k=0}^{∞} \frac{(k+1)n^{k+1}}{k!}
= −n^{2}e^{n} + n ∑_{k=0}^{∞} \frac{(k+1)n^{k}}{k!}
= −n^{2}e^{n} + n(ne^{n} + e^{n}) = ne^{n}.

Thus,

\begin{aligned}∥e^{n(L−I)}f − L^{n}f∥ & ≤ & \frac{M_{f} l^{n}}{e^{n}} e^{nl^{2}/2}(ne^{n})^{1/2} \\ & = & M_{f} \sqrt{n} l^{n}e^{(l^{2}−1)n/2}. \end{aligned}

Proof of Lemma 3.4: (iii) For t = 0, the limit in statement (iii) holds trivially.

For s > 0, let L_{s} := I +sA. Then for f ∈D(A^{∞}),

∥L_{s}^{n+1}f − L_{s}^{n}f∥ = ∥L_{s}^{n}(L_{s}f − f)∥
= s∥(I + sA)^{n}Af∥
= s∥ ∑_{k=0}^{n} \binom{n}{k} s^{k}A^{k}Af∥
≤ s ∑_{k=0}^{n} \binom{n}{k} s^{k}M_{f}ω^{k+1}
= s ωM_{f}(1 + sω)^{n}
≤ G_{f}e^{nωs},

where G_{f} = sωM_{f}. It follows from Lemma 3.5 that

∥e^{n(L_{s}−I)}f − L_{s}^{n}f∥ ≤ G_{f} \sqrt{n}e^{nωs}e^{(e^{2ωs}−1)n/2} for f ∈D(L^{∞}).

Replacing L_{s} by I + sA and G_{f} by sωM_{f}, we obtain

∥e^{n s A}f − (I + sA)^{n}f∥ ≤ sωM_{f} \sqrt{n}e^{nωs}e^{(e^{2ωs}−1)n/2}.

Setting s = \frac{t}{n} in the above inequality yields ∥e^{tA}f − (I + \frac{t}{n}A)^{n}f∥ ≤ \frac{t}{\sqrt{n}}M_{f}e^{ωt}e^{(e^{2ωt/n}−1)n/2}.

For t∈[0, T], there exists N_{T} > 0 such that e^{2ωt/n} ≤ 1+ \frac{4ωt}{n} for all n>N_{T}. Then

\begin{aligned}∥e^{tA}f − (I + \frac{t}{n}A)^{n}f∥ & ≤ & \frac{t}{\sqrt{n}}M_{f}e^{ωt}e^{(1+4ωt/n−1)n/2} \\ & ≤ & \frac{t}{\sqrt{n}}M_{f}e^{3ωt}, \end{aligned}

which implies that lim_{n→∞}(I + \frac{t}{n}A)^{n}f = e^{tA}f.

3.2.2 Von-Neumann Stable Temporal Approximations In this section, we extend the Chernoff product formula to possibly unstable approximation methods.

Theorem 3.2 Suppose that A generates a C_{0}-semigroup S. Let V := {V (t) : t ∈ [0, δ]} be a family of linear operators satisfying D(A) ⊂ D(V (t)^{∞}) for all t ∈ [0, δ]. Suppose that the map t ↦ V (t)f is continuous for all f ∈ D(A). If there exists a constant ω ≥ 0 such that

(a) for all f ∈ D(A), t ∈ [0, δ] and n ∈ N, ∥V^{n+1}(t)f − V^{n}(t)f∥ ≤ tM_{f}e^{nωt} for some f-dependent positive number M_{f}, and

(b) there exists a family {W (t) : t ∈ [0, δ]} of operators defined on D(A^{2}) such that for each f ∈ D(A^{2}) the map t ↦ W (t)f is continuous, W (0)f = 0, and ∥V^{n+1}(t)f − V^{n}(t)f − t V^{n}(t)Af∥ ≤ t e^{nωt}∥W (t)f∥ for all t∈[0, δ] and n∈N,

then lim_{n→∞}V (\frac{t}{n})^{n}f = S(t)f for each f ∈D(A), uniformly for t in compact interval [0, T] for any T > 0.

Before proceeding to prove Theorem 3.2, we first discuss connections of this theorem to the Chernoff product formula and to the Von Neumann stability condition.

Remark 3.1 If a temporal approximation method V is consistent on D(A), and stable in the classical sense that

∥V (t)^{n}∥ ≤ Me^{nωt}, for all (t, n)∈[0, δ]×N  (3.7)

for some positive constant M, ω independent of n and t, then conditions (a) and (b) of Theorem 3.2 hold. Hence, Theorem 3.2 is a generalization of the Chernoff product approximation formula.

Proof of Remark 3.1: For f ∈D(A), t∈[0, δ) and n∈N,

\begin{aligned}∥V (t)^{n+1}f − V (t)^{n}f∥ & ≤ & ∥V (t)^{n}∥ · ∥V (t)f − f∥ \\ & ≤ & Me^{nωt}∥t · \frac{V (t)f−f}{t} ∥. \end{aligned}  (3.8)

Since V is consistent on D(A), it follows that the limit lim_{t→0} \frac{V (t)f−f}{t} exists and hence ∥\frac{V (t)f−f}{t} ∥ is bounded on (0, δ). Without loss of generality, we assume that sup_{t∈(0,δ)}∥\frac{V (t)f−f}{t} ∥ ≤

\frac{M_{f}}{M}. Then it follows from (3.8) that ∥V^{n+1}(t)f − V^{n}(t)f∥ ≤ tM_{f}e^{nωt}, which is condition (a) of Theorem 3.2.

For f ∈ D(A^{2}), t∈[0, δ) and n∈N,

\begin{aligned}∥V (t)^{n+1}f − V (t)^{n}f − tV (t)^{n}Af∥ & ≤ & ∥V (t)^{n}∥ · ∥V (t)f − f − tAf∥ \\ & ≤ & Me^{nωt}∥t · \frac{V (t)f−f}{t} − tAf∥ \\ & = & tMe^{nωt}∥\frac{V (t)f−f}{t} − Af∥. \end{aligned}  (3.9)

For t∈[0, δ], define a family W(t) of operators on D(A) by

W (t)f := \{ \begin{matrix}M (\frac{V (t)−I}{t} f − Af) & for t > 0, \\ 0 & for t = 0. \end{matrix}

Then, from (3.9) we obtain that

∥V (t)^{n+1}f − V (t)^{n}f − tV (t)^{n}Af∥ ≤ te^{nωt}∥W (t)f∥

for f ∈D(A^{2}). It is obvious that the function t↦W (t)f is continuous for t∈(0, δ] for each f ∈ D(A). Since V is consistent on D(A), it follows that for each f ∈ D(A), the function t↦W (t)f is continuous at t = 0. This shows that V also satisfies condition (b) of Theorem 3.2

Remark 3.2 Condition (a) of Theorem 3.2 implies that V satisfies the Von Neumann stability condition (1.21) on D(A), namely, for all f ∈D(A),

lim_{n→∞} (∥V (t)^{n}f∥)^{1/n} ≤ e^{ωt}.  (3.10)

Proof: Let f ∈D(A). The telescoping equality V (t)^{n}f =∑_{k=0}^{n−1} [V (t)^{k+1}f −V (t)^{k}f]+f yields that ∥V (t)^{n}f∥ ≤ ∑_{k=0}^{n−1} ∥V (t)^{k+1}f − V (t)^{k}f∥ + ∥f∥. Then, condition (a) of Theorem 3.2 implies that

∥V (t)^{n}f∥ ≤ ∑_{k=0}^{n−1} tM_{f}e^{kωt} + ∥f∥
≤ ntM_{f}e^{nωt} + ∥f∥
≤ e^{nt}M_{f}e^{nωt} + ∥f∥
≤ (M_{f} + ∥f∥)e^{n(ω+1)t},

from which (3.10) follows immediately.

Similarly, we can show that the spatially discretized temporal approximation method V (t; A_{h}) also satisfies the Von Neumann stability condition (1.20) when condition (a) of Theorem 3.2 is preserved for the method V (t; A_{h}). Namely, the following remark holds.

Remark 3.3 If a spatially discretized temporal approximation method {V (t, A_{h}) : E_{h} → E_{h} : t∈[0, δ], h∈(0, ε)} satisfies

∥V (t; A_{h})^{n+1}f_{h} − V (t; A_{h})^{n}f_{h}∥ ≤ tM_{f_{h}}e^{nωt}  (3.11)

for all (t, h) ∈ [0, δ]×(0, ε) and n ∈ N. Then the Von Neumann stability condition (1.20) holds for the approximation method {V (t; A_{h}) : (t, h)∈[0, δ]×(0, ε)}.

Now, we accumulate two lemmas for the proof of Theorem 3.2.

Lemma 3.6 Let V (t) be as in Theorem 3.2. Let T > 0. For each s ∈ (0, T], define A_{s}f := \frac{V (s)−I}{s} f for f ∈D(A). Then condition (a) of Theorem 3.2 implies the following.

( i ) For f ∈ D(A),

lim_{n→∞} ∥V^{n}(t/n)f − e^{tA_{t/n}}f∥ = 0  (3.12)

uniformly for t∈(0, T].

(i i) For f ∈ D(A) and t ≥ 0, the function t ↦ e^{tA_{s}}A_{s}f := ∑ k = 0^{∞} \frac{t^{k}A_{s}^{k}}{k!} A_{s}f is well defined, and for any ω_{o} > ω there exist s_{o} ∈ (0, T] such that for each s ∈ (0, s_{o}), ∥e^{tA_{s}}A_{s}f∥ < M_{f}e^{ω_{o}t} for all f ∈D(A) and t ≥ 0.

(iii) For f ∈D(A) and t ≥ 0, the function t↦e^{tA_{s}}f := ∑_{k=0}^{∞} \frac{t^{k}A_{s}^{k}}{k!} f is well defined, and for any ω_{o} >ω there exist s_{o} ∈(0, T] such that for each s∈(0, s_{o}), ∥e^{tA_{s}}f∥ < (∥f∥+ \frac{M_{f}}{ω_{o}})e^{ω_{o}t} for all f ∈D(A) and t ≥ 0.

(iv) For any ω_{o} > ω there exist s_{o} ∈ (0, T] such that for each s ∈ (0, s_{o}) the integrals R_{s}(λ)g := ∫_{0}^{∞} e^{−λt}e^{tA_{s}}g dt exist for all g ∈ D(A) ∪ A_{s}(D(A)) and λ > ω_{o}, and the equality R_{s}(λ)(λ−A_{s})f =f holds for all λ>ω_{o} and f ∈D(A).

Proof: (i) For t = 0, (3.12) is obviously true. For t∈(0, T], condition (a) of Theorem 3.2 implies that

\begin{aligned}∥V^{n}(s)f − V^{n−1}(s)f∥ & ≤ & sM_{f}e^{nsω} \\ & = & G_{s,f} l^{n}, \end{aligned}

where G_{s,f} = sM_{f} and l = e^{sω} ≥1. Then, by Lemma 3.5,

\begin{aligned}∥V^{n}(s)f − e^{n[V (s)−I]}f∥ & ≤ G_{s,f} \sqrt{n}l^{n}e^{(l^{2}−1)n/2} \\ & = sM_{f} \sqrt{n}e^{nsω}e^{(e^{2sω}−1)n/2}. \end{aligned}  (3.13)

By definition of A_{s}, e^{n[V(s)−I]}f = e^{nsA_{s}}f. Thus taking s=t/n, we have that e^{n[V (t/n)−I]}f = e^{tA_{t/n}}. Then it follows from (3.13) that

∥V (\frac{t}{n})^{n} f − e^{tA_{t/n}}f∥ ≤ M_{f} \frac{t}{\sqrt{n}}e^{ωt}e^{(e^{2ωt/n}−1)n/2}.

For any ω_{o} > ω, there exists n_{o} (dependent on T) such that e^{2ωt/n} − 1 < 2ω_{o}t/n for all n > n_{o}. So for all n > n_{o},

\begin{aligned}∥V^{n}(\frac{t}{n})f − e^{tA_{t/n}}f∥ & ≤ & M_{f} \frac{t}{\sqrt{n}} e^{ωt}e^{ω_{o}t} \\ & = & M_{f} \frac{t}{\sqrt{n}}e^{ωt}e^{ω_{o}t}, \end{aligned}

from which statement (i) follows.

(ii) For f ∈ D(A) and n ∈ N,

∥A_{s}^{n}A_{s}f∥ = ∥ (\frac{V (s)−I}{s} )^{n} (\frac{V (s)−I}{s} ) f∥
= s^{−n}∥ ∑_{i=0}^{n} \binom{n}{i} (−1)^{n−i}V^{i}(s)\frac{V (s)−I}{s} f∥
≤ s^{−n} ∑_{i=0}^{n} \binom{n}{i} M_{f}e^{iωs}
= M_{f} (\frac{1+e^{ωs}}{s} )^{n} ,

where the last inequality is due to condition (a) of Theorem 3.2. Then, by Lemma 3.4, e^{tA_{s}}A_{s}f is well-defined for f ∈ D(A) and t ≥ 0.

Statement (iii) of Lemma 3.4 implies that

\begin{aligned}∥e^{tA_{s}}A_{s}f∥ & = & ∥ lim_{m→∞} (I + \frac{t}{m}A_{s})^{m} A_{s}f∥ \\ & = & lim_{m→∞} ∥[λ_{m} + μ_{m}V (s)]^{m}A_{s}f∥, \end{aligned}  (3.14)

where λ_{m} = \frac{ms−t}{ms} and μ_{m} = 1 − λ_{m} = \frac{t}{ms}. Since

∥ (λ_{m} + μ_{m}V (s))^{m} A_{s}f∥ = ∥ ∑_{i=0}^{m} \binom{m}{i} λ_{m}^{m−i}μ_{m}^{i}V^{i}(s)\frac{V (s)−I}{s} f∥
≤ ∑_{i=0}^{m} \binom{m}{i} λ_{m}^{m−i}μ_{m}^{i}M_{f}e^{iωs}
= M_{f} (λ_{m} + μ_{m}e^{ωs})^{m} ,

it follows from (3.14) that ∥e^{tA_{s}}A_{s}f∥ ≤ M_{f} lim_{m→∞} [1 + μ_{m}(e^{ωs} − 1)]^{m} by noticing that λ_{m} = 1 − μ_{m}. For ω_{o} > ω, there exists s_{o} > 0 such that e^{ωs} − 1 ≤ ω_{o}s for all s ∈ (0, s_{o}]. Then,

∥e^{tA_{s}}A_{s}f∥ ≤ M_{f} lim_{m→∞} (1 + μ_{m}ω_{o}s)^{m}
= M_{f} lim_{m→∞} (1 + \frac{ω_{o}t}{m})^{m}
≤ M_{f}e^{ω_{o}t}.

(iii) By an argument similar to that in the proof of statement (i), we can show that e^{tA_{s}}f is well defined for f ∈ D(A) and t ≥ 0. Now, by statement (i) of Lemma 3.4, e^{tA_{s}}f = f + ∫_{0}^{t} e^{τA_{s}}A_{s}f dτ. Then by (i),

∥e^{tA_{s}}f∥ ≤ ∥f∥ + ∫_{0}^{t} M_{f}e^{ω_{o}τ} dτ ≤ (∥f∥ + \frac{M_{f}}{ω_{o}})e^{ω_{o}τ} .

(iv) By the two estimates established in statements (ii) and (iii) for e^{tA_{s}}f and e^{tA_{s}}A_{s}f, the integrals R_{s}(λ)g = ∫_{0}^{∞} e^{−λt}e^{tA_{s}}g dt exist for all s∈(0, s_{o}), λ>ω_{o} and g ∈D(A)∪A_{s}(D(A)).

By statement (i) of Lemma 3.4, we have that e^{tA_{s}}f−f = ∫_{0}^{t} e^{τA_{s}}A_{s}fdτ. Then it follows from Remark 2.1 that for s∈(0, s_{o}), λ>ω_{o} and f ∈D(A),

\begin{aligned}[L_{s}(e^{·A_{s}}f −f)](λ) & = & ∫_{0}^{∞} e^{−λt}e^{tA_{s}}A_{s}f dt \\ & = & R_{s}(λ)A_{s}f. \end{aligned}  (3.15)

On the other hand, with the estimate established for ∥e^{tA_{s}}f∥ in statement (iii), integrating by parts we obtain

[L_{s}(e^{·A_{s}}f −f)](λ) = ∫_{0}^{∞} e^{−λt}d(e^{tA_{s}}f −f)
= λ ∫_{0}^{∞} e^{−λt}(e^{tA_{s}}f −f)dt
= −f + λR_{s}(λ)f,

which, together with (3.15), implies that

R_{s}(λ)(λ−A_{s})f = f.

Lemma 3.7 Let A_{s} be as defined in Lemma 3.6. Then condition (b) of Theorem 3.2 implies that for any ω_{o} > ω, there exist s_{o} ∈ (0, T] such that for s ∈ (0, s_{o}) and f ∈ D(A^{2}), e^{tA_{s}}(A_{s} −A)f is well-defined and ∥e^{tA_{s}}(A_{s} − A)f∥ ≤ e^{ω_{o}t}∥W (s)f∥ for t ≥ 0, and lim_{s→0} R_{s}(λ)(A_{s} − A)f = 0.

Proof: For f ∈ D(A^{2}) and n ∈ N,

∥A_{s}^{n}(A_{s}−A)f∥ = ∥ (\frac{V (s)−I}{s} )^{n} (\frac{V (s)−I}{s} − A) f∥
= s^{−n}∥ ∑_{i=0}^{n} \binom{n}{i} (−1)^{n−i}V^{i}(s) (\frac{V (s)−I}{s} − A) f∥
≤ s^{−n} ∑_{i=0}^{n} \binom{n}{i} e^{iωs}∥W (s)f∥
= (\frac{1+e^{ωs}}{s} )^{n} ∥W (s)f∥,

where the last inequality is due to condition (b) of Theorem 3.2. Then, by Lemma 3.4, e^{tA_{s}}(A_{s}−A)f is well-defined for f ∈D(A) and t ≥ 0.

Statement (iii) of Lemma 3.4 implies that

\begin{aligned}∥e^{tA_{s}}(A_{s}−A)f∥ & = & ∥ lim_{m→∞} (I + \frac{t}{m}A_{s})^{m} (A_{s}−A)f∥ \\ & = & lim_{m→∞} ∥[λ_{m} + μ_{m}V (s)]^{m}(A_{s}−A)f∥, \end{aligned}  (3.16)

where λ_{m} = \frac{ms−t}{ms} and μ_{m} = 1 − λ_{m} = \frac{t}{ms}. Since

∥ (λ_{m} + μ_{m}V (s))^{m} A_{s}f∥ = ∥ ∑_{i=0}^{m} \binom{m}{i} λ_{m}^{m−i}μ_{m}^{i}V^{i}(s) (\frac{V (s)−I}{s} − A) f∥
≤ ∑_{i=0}^{m} \binom{m}{i} λ_{m}^{m−i}μ_{m}^{i}e^{iωs}∥W (s)f∥
= (λ_{m} + μ_{m}e^{ωs})^{m} ∥W (s)f∥,

it follows from (3.16) that ∥e^{tA_{s}}(A_{s}−A)f∥ ≤ lim_{m→∞} [1 + μ_{m}(e^{ωs} − 1)]^{m} ∥W (s)f∥ by noticing that λ_{m} = 1 − μ_{m}. For ω_{o} > ω, there exists s_{o} > 0 such that e^{ωs} − 1 ≤ ω_{o}s for all s ∈ (0, s_{o}]. Then,

∥e^{tA_{s}}(A_{s}−A)f∥ ≤ lim_{m→∞} (1 + μ_{m}ω_{o}s)^{m} ∥W (s)f∥
= lim_{m→∞} (1 + \frac{ω_{o}t}{m})^{m} ∥W (s)f∥
≤ e^{ω_{o}t}∥W (s)f∥.

With the exponential bound established above for e^{tA_{s}}(A_{s} −A)f, it follows that the integrals R_{s}(λ)(A_{s} − A)f exist for all f ∈D(A^{2}) and s∈(0, s_{o}), and

∥R_{s}(λ)(A_{s} − A)f∥ ≤ ∫_{0}^{∞} e^{−λt}∥e^{tA_{s}}(A_{s} − A)f∥dt
≤ ∫_{0}^{∞} e^{−λt}e^{ω_{o}t}∥W (s)f∥dt
= (λ−ω_{o})^{−1}∥W (s)f∥.

Since W is strongly continuous and W (0)g = 0 for g ∈D(A), we have that lim_{s→0} R_{s}(λ)(A_{s}− A)f = 0.

Proof of Theorem 3.2: For f ∈ D(A),

\begin{aligned}∥V^{n}(\frac{t}{n})f − S(t)f∥ & ≤ & ∥V^{n}(\frac{t}{n})f − e^{tA_{t/n}}f∥ \\ & + & ∥e^{tA_{t/n}}f − S(t)f∥. \end{aligned}  (3.17)

Since lim_{n→∞} ∥V^{n}(\frac{t}{n})f − e^{tA_{t/n}}f∥ = 0 by Lemma 3.6, it remains to be shown that

lim_{n→∞} e^{tA_{t/n}}f = S(t)f.  (3.18)

Let R_{s} and ω_{o} be as in Lemma 3.6. For f ∈D(A) and λ>ω_{o}, we obtain from statement (iv) of Lemma 3.6 that R(λ, A)f = R_{s}(λ)(λ−A_{s})R(λ, A)f. Then,

\begin{aligned}R_{s}(λ)f − R(λ, A)f & = & R_{s}(λ)f − R_{s}(λ)(λ−A_{s})R(λ, A)f \\ & = & R_{s}(λ)[(λ−A)−(λ−A_{s})]R(λ, A)f \\ & = & R_{s}(λ)(A_{s} − A)R(λ, A)f, \end{aligned}  (3.19)

Since f ∈ D(A) implies that R(λ, A)f ∈ D(A^{2}), it follows from Lemma 3.7 and (3.19) that lim_{n→∞}R_{s}(λ)f = R(λ, A)f for all λ > ω_{o}. Then, with the boundedness condition for e^{tA_{s}}A_{s}f proven in statement (ii) of Lemma 3.6, it follows from Theorem 2.4 and statement (i) of Lemma 3.4 that lim_{s→0} e^{tA_{s}}f = S(t)f uniformly for t ∈ [0, T] for all f ∈ D(A), from which statement (3.18) follows.

One well-accepted meaning of stability for convergent methods that is also implied by definition (1.4) is that when the initial value has a small error, the approximated solution has a small error too. However, approximation methods satisfying only conditions (i) and (ii) of Theorem 3.2 may not necessarily be stable in this sense, but are stable in a sense very close to this.

Theorem 3.3 Suppose that condition (a) of Theorem 3.2 is strengthened to the following. There exists a constant M >0 such that for all f ∈D(A),t∈[0, δ] and n∈N,

∥V^{n+1}(t)f − V^{n}(t)f∥ ≤ tMe^{nωt}(∥f∥+∥Af∥).  (3.20)

Then for each f ∈D(A) and each sequence {f_{n}}⊂D(A) with

lim_{n→∞}∥f_{n}−f∥ + ∥A(f_{n}−f)∥ = 0,  (3.21)

lim_{n→∞}V (\frac{t}{n})^{n}f_{n} = S(t)f uniformly for t in compact interval [0, T] for any T > 0.

Proof: For f ∈ D(A), Theorem 3.2 implies that lim_{n→∞}V (\frac{t}{n})^{n}f = S(t)f uniformly for t∈[0, T]. It then suffices to show that for any sequence {f_{n}} satisfying (3.21),

lim_{n→∞}V (\frac{t}{n})^{n} (f_{n}−f) = 0  (3.22)

uniformly for t∈[0, T].

For f ∈ D(A) and a sequence {f_{n}} satisfying (3.21), we have that

\begin{aligned}∥V (\frac{t}{n})^{n}(f_{n}−f)∥ & = & ∥ ∑_{k=1}^{n} [V(\frac{t}{n})^{k}(f_{n}−f)−V(\frac{t}{n})^{k−1}(f_{n}−f)] + (f_{n}−f)∥ \\ & ≤ & ∥f_{n}−f∥ + ∑_{k=1}^{n} ∥V (\frac{t}{n})^{k}(f_{n}−f) − V (\frac{t}{n})^{k−1}(f_{n}−f)∥., \end{aligned}

It then follows from (3.20) that

∥V (\frac{t}{n})^{n}(f_{n}−f)∥ ≤ ∥f_{n}−f∥ + ∑_{k=1}^{n} \frac{t}{n}Me^{kωt/n} [∥f_{n}−f∥ + ∥A(f_{n}−f)∥]
≤ ∥f_{n}−f∥ + ∑_{k=1}^{n} \frac{t}{n}Me^{ωt} [∥f_{n}−f∥ + ∥A(f_{n}−f)∥]
= ∥f_{n}−f∥ + tMe^{ωt} [∥f_{n}−f∥ + ∥A(f_{n}−f)∥]
≤ (1+tMe^{ωt}) [∥f_{n}−f∥ + ∥A(f_{n}−f)∥] ,

Then statement (3.22) follows from (3.21).

4 Applications

In this chapter, we apply Theorem 3.3 to the unstable but Von-Neumann stable temporal approximation method given in Chapter 1, an ADI type factorized temporal discretization method, and a domain decomposition based factorized temporal approximation method.

4.1 The Unstable but Von Neumann Stable Method

In Section 1.2, we have considered the evolutionary system

\{ \begin{matrix}u′(t) = Au(t), t ≥ 0, \\ u(0) = f ∈D(A), \end{matrix}

on the Hilbert space E := {f ∈ L^{2}[0, π] : f(0) = f(π) = 0} with A + A_{1} + A_{2}, where A_{1}f = f′′, A_{2}f = ∑_{k=1}^{∞} ⟨f, e_{k^{2}}⟩ e_{k}. We also investigated the temporal approximation method

V (t)f := (I − \frac{t}{2}A_{1})^{−1}(I + tA_{2})(I + \frac{t}{2}A_{1})f,

and showed that it is unstable in the classical sense but satisfies the Von Neumann stability condition (1.21). Now as an application of Theorem 3.3, we shall prove that this temporal discretization method satisfies the following statement.

Statement 4.1 For f ∈D(A), and any sequence {f_{n}}_{n=1}^{∞} ⊂D(A) with

lim_{n→∞} ∥f_{n}−f∥ + ∥f′′_{n}−f′′∥ = 0,

lim_{n→∞} V (\frac{t}{n})^{n}f_{n} = S(t)f uniformly for t ∈ [0, T] for any T ≥ 0, where S is the semigroup generated by A.

Proof: Since A_{2} is bounded, D(A) = D(A_{1}). Thus D(A)⊂D(V (t)^{∞}). Since A_{1} generates a contraction semigroup and A_{2} is bounded, it follows immediately that the map t↦V (t)f is continuous for all f ∈D(A).

The three inequalities (1.23), (1.24) and (1.26) are combined into

\{ \begin{matrix}∥(I − \frac{t}{2}A_{1})^{−1}∥ ≤ 1, \\ ∥(I + \frac{t}{2}A_{1})(I − \frac{t}{2}A_{1})^{−1}∥ ≤ 1, \\ ∥I + tA_{2}∥ ≤ 1 + t. \end{matrix}  (4.1)

For t ≥ 0, denote Y (t) := (I +tA_{2})(I + \frac{t}{2}A_{1})(I − \frac{t}{2}A_{1})^{−1}, that is,

V (t) = (I − \frac{t}{2}A_{1})^{−1}Y (t)(I − \frac{t}{2}A_{1}).

Then (4.1) implies that ∥Y (t)∥ ≤ 1 + t. Now for f ∈D(A) and n∈N,

∥V (t)^{n+1}f −V (t)^{n}f∥ = ∥V (t)^{n} [V (t) − I] f∥
= ∥(I−\frac{t}{2}A_{1})^{−1}Y(t)^{n} [(I+tA_{2})(I + \frac{t}{2}A_{1})−(I−\frac{t}{2}A_{1})] f∥
= t∥(I − \frac{t}{2}A_{1})^{−1}Y (t)^{n} [(I + \frac{t}{2}A_{2})A − \frac{t}{2}A_{2}^{2}] f∥
≤ t∥Y (t)^{n} [(I + \frac{t}{2}A_{2})A − \frac{t}{2}A_{2}^{2}] f∥,

where the last inequality is du to (4.1). From the inequality ∥Y (t)∥ ≤ 1 + t we have that

∥V (t)^{n+1}f − V (t)^{n}f∥ ≤ t(1 + t)^{n}∥ [(I + \frac{t}{2}A_{2})A − \frac{t}{2}A_{2}^{2}] f∥
≤ t e^{nt} [∥(I + \frac{t}{2}A_{2})Af∥ + ∥\frac{t}{2}A_{2}^{2}f∥]
≤ t e^{nt} [(1+ \frac{t}{2})∥Af∥ + \frac{t}{2}∥f∥]
≤ t e^{nt} [e^{t}∥Af∥ + e^{t}∥f∥]
≤ t e^{2nt} [∥Af∥ + ∥f∥] .

Now, for f ∈D(A^{2}) and n∈N,

∥V(t)^{n+1}f −V(t)^{n}f −tV(t)^{n}Af∥ = ∥V (t)^{n} [V (t)−I −tA] f∥
= ∥(I−\frac{t}{2}A_{1})^{−1}Y(t)^{n}[(I+tA_{2})(I+\frac{t}{2}A_{1})−(I−\frac{t}{2}A_{1})(I−tA)]f∥
= t∥(I − \frac{t}{2}A_{1})^{−1}Y (t)^{n}[\frac{t}{2}A^{2} − \frac{t}{2}A_{2}^{2}]f∥
≤ t(1 + t)^{n}∥\frac{t}{2}(A^{2}−A_{2}^{2})f∥
≤ t e^{2nt}∥\frac{t}{2}(A^{2}−A_{2}^{2})f∥.

Set W (t) := \frac{t}{2}(A^{2}−A_{2}^{2}). Obviously, the map t ↦ W (t)f is continuous and W (0)f = 0 for all f ∈D(A^{2}). Then, by Theorem 3.3, lim_{n→∞} V (\frac{t}{n})^{n} f_{n} = S(t)f uniformly for t∈[0, T] for T ≥ 0.

4.2 ADI-type Factorized Methods

In this section, we use Theorem 3.3 to exmaine the convergence of the popular ADI-type temporal approximation methods for quasi-dissipative operators in a Hilbert space.

Lemma 4.1 Let E be a Hilbert space with inner product ⟨·, ·⟩. Let A be a C_{0}-semigroup generator on E satisfying the quasi-dissipative conditon

Re ⟨Af, f⟩ ≤ ω∥f∥^{2},  (4.2)

for some constant ω ≥ 0. Then the Crank-Nicolson method V(t)=(I − \frac{t}{2}A)^{−1}(I + \frac{t}{2}A) satisfies the stability condition

∥V (t)∥ ≤ e^{2ωt} for all t∈[0, \frac{1}{ω}].  (4.3)

Proof: Since A generates a C_{0}-semigroup, it follows that (I−tA)^{−1} ∈L(E) for t∈[0, \frac{1}{ω}). Since (I − \frac{t}{2}A)^{−1} and (I + \frac{t}{2}A) commute on D(A) for t∈[0, \frac{1}{ω}], it follows that the stability conclusion (4.3) is equivalent to that ∥(I + \frac{t}{2}A)(I − \frac{t}{2}A)^{−1}g∥ ≤ e^{2ωt}∥g∥ for all g ∈ E. Replacing (I − \frac{t}{2}A)^{−1}g by f, this is equivalent to

∥(I + \frac{t}{2}A)f∥ ≤ e^{2ωt}∥(I − \frac{t}{2}A)f∥ for t∈[0, \frac{1}{ω}], f ∈D(A).  (4.4)

Squaring the left hand side of the above inequality, we obtain

\begin{aligned}∥(I + \frac{t}{2}A)f∥^{2} & = & ∥(1 + \frac{ωt}{2})f + \frac{t}{2}(A − ω)f∥^{2} \\ & = & (1+ \frac{ωt}{2})^{2}∥f∥^{2} + t(1+ \frac{ωt}{2}) Re ⟨(A−ω)f, f⟩ + \frac{t^{2}}{4} ∥(A−ω)f∥^{2}. \end{aligned}

Squaring the right hand side of inequality (4.4), we obtain

\begin{aligned}e^{4ωt}∥(I − \frac{t}{2}A)f∥^{2} & = e^{4ωt}∥(1− \frac{ωt}{2})I − \frac{t}{2}(A−ω)f∥^{2} \\ & = e^{4ωt} [(1−\frac{ωt}{2})^{2}∥f∥^{2}−t(1−\frac{ωt}{2})Re ⟨(A−ω)f, f⟩+ \frac{t^{2}∥(A−ω)f∥^{2}}{4} ] . \end{aligned}

Therefore, (4.4) holds as long as

t[(1+\frac{ωt}{2})+(1−\frac{ωt}{2})e^{4ωt}]Re ⟨(A−ω)f, f⟩ ≤ [(1−\frac{ωt}{2})^{2}e^{4ωt}−(1+\frac{ωt}{2})^{2}] ∥f∥^{2}  (4.5)

for all t ∈ [0, \frac{1}{ω}] and f ∈ D(A). Since t[(1+ \frac{ωt}{2}) + (1− \frac{ωt}{2})e^{4ωt}] > 0 for all t ∈ [0, \frac{1}{ω}], and Re ⟨(A−ω)f, f⟩ ≤ 0 by the quasi-dissipativity assumption, it follows that (4.5) holds if (1− \frac{ωt}{2})^{2}e^{4ωt} − (1+ \frac{ωt}{2})^{2} ≥ 0 for t∈[0, \frac{1}{ω}], which is obviously equivalent to

(1− \frac{ωt}{2})e^{2ωt} − (1+ \frac{ωt}{2}) ≥ 0 for t∈[0, \frac{1}{ω}],  (4.6)

Let h(t) := (1− \frac{t}{2})e^{2t} − (1+ \frac{t}{2}) for t ∈ [0, 1]. Obviously h is differentiable on [0, 1] and h′(t) = (\frac{3}{2} − t)e^{2t} − \frac{1}{2}. Since h′(t) ≥ (1 − t)e^{2t} ≥ 0 for t∈[0, 1], it follows that the function t ↦ h(t) is increasing on [0, 1]. Again since h(0) = 0, it follows that h(t) ≥ 0 for t ∈ [0, 1]. Therefore, h(ωt) ≥ 0 for t∈[0, \frac{1}{ω}], which is exactly (4.6).

Theorem 4.1 Suppose that A = A_{1} +A_{2} with D(A) ⊂ D(A_{1})∩D(A_{2}) generates a C_{0}- semigroup S, and there exists a constant ω ≥ 0 such that

Re⟨A_{i}f, f⟩ ≤ ω∥f∥^{2} for all f ∈D(A)  (4.7)

for i = 1, 2. Let \{V (t) : t ∈ [0, \frac{1}{ω}] be a family of linear operators given by

V (t) = (I − \frac{t}{2}A_{1})^{−1} (I − \frac{t}{2}A_{2})^{−1} (I + \frac{t}{2}A_{2}) (I + \frac{t}{2}A_{1}) .

Then, for f ∈ D(A) and {f_{n}}_{n=1}^{∞} ⊂ D(A) with lim_{n→∞} ∥f −f_{n}∥ + ∥A(f −f_{n})∥ = 0, the limit lim_{n→∞}V^{n}(\frac{t}{n})f_{n} = S(t)f exists uniformly for t in compact subsets of [0, ∞), where S is the C_{0}-semigroup generated by A.

Proof: By the Lumer-Phillips theorem, condition (4.7) implies that ∥(λ−ω)(λ−A_{i})^{−1}∥ ≤ 1 for λ > ω for i = 1, 2. This is equivalent to ∥(I −tA_{i})^{−1}∥ ≤ (1−ωt)^{−1} for t ∈ [0, \frac{1}{ω}) and i = 1, 2. Since (1 − ωt)^{−1} ≤ e^{2ωt} for t∈[0, \frac{1}{2ω}], we obtain that

∥(I − \frac{t}{2}A_{i})^{−1}∥ ≤ e^{ωt}  (4.8)

for t∈[0, \frac{1}{ω}] and i = 1, 2. For t∈[0, \frac{1}{ω}], let

Y (t) := (I − \frac{t}{2}A_{2})^{−1}(I + \frac{t}{2}A_{2})(I + \frac{t}{2}A_{1})(I − \frac{t}{2}A_{1})^{−1}.

By Lemma 4.1, the quasi-dissipativity condition (4.7) implies that

∥Y (t)∥ ≤ e^{4ωt}  (4.9)

for t∈[0, \frac{1}{ω}] and i = 1, 2.

Let t∈[0, \frac{1}{ω}]. Then D(A)⊂D(V (t)^{∞}) and the map t↦V (t)f is continuous for f ∈D(A). For f ∈D(A) and n∈N,

\begin{aligned}∥V (t)^{n+1}f − V (t)^{n}f∥ & = & t∥V^{n}(t)(I − \frac{t}{2}A_{1})^{−1}(I − \frac{t}{2}A_{2})^{−1}Af∥ \\ & = & t∥(I − \frac{t}{2}A_{1})^{−1}Y (t)^{n}(I − \frac{t}{2}A_{2})^{−1}Af∥. \end{aligned}

Then, by (4.8) and (4.9),

\begin{aligned}∥V (t)^{n+1}f − V (t)^{n}f∥ & ≤ & t∥Af∥ e^{ωt}(e^{4ωt})^{n}e^{ωt} \\ & ≤ & t∥Af∥ e^{6ωnt}. \end{aligned}

Now for f ∈D(A^{2}) and n∈N,

∥V(t)^{n+1}f −V(t)^{n}f −tV(t)^{n}Af∥ = t∥V^{n}(t) [(I − \frac{t}{2}A_{1})^{−1}(I − \frac{t}{2}A_{2})^{−1} − I] Af∥
= t∥(I−\frac{t}{2}A_{1})^{−1}Y(t)^{n} [(I−\frac{t}{2}A_{2})^{−1}−(I−\frac{t}{2}A_{1})]Af∥
≤ t e^{ωt}(e^{4ωt})^{n}∥ [(I − \frac{t}{2}A_{2})^{−1} − (I − \frac{t}{2}A_{1})] Af∥
≤ t e^{6ωnt}∥ [(I − \frac{t}{2}A_{2})^{−1} − (I − \frac{t}{2}A_{1})] Af∥.

Let W (t) = (I−\frac{t}{2}A_{2})^{−1}−(I−\frac{t}{2}A_{1}) for t∈[0, \frac{1}{ω}]. Clearly, the map t↦W (t)f is continuous and W (0)f = 0 for all f ∈D(A_{1}). Since D(A) ⊂ D(A_{1})∩D(A_{2}), it follows that Af ∈D(A_{1}) for all f ∈D(A^{2}), and hence the map t↦W (t)Af is continuous and W (0)Af = 0 for f ∈D(A^{2}). Then by Theorem 3.3, for any sequence {f_{n}}_{n=1}^{∞} ⊂D(A) with lim_{n→∞} ∥f−f_{n}∥+∥A(f−f_{n})∥ = 0, the limit lim_{n→∞}V (\frac{t}{n})^{n} f_{n} = S(t)f exists uniformly for t in compact subsets of [0, ∞).

4.3 A Domain Decomposition Method

In this section, we use Theorem 3.3 to analyze the convergence of an operator splitting based domain decomposition method (see [40, 41]). A description of the method is given below.

We consider the homogeneous initial-boundary value problem

\{ \begin{matrix}\frac{∂}{∂t}u(t, x, y) & = Au(t, x, y) & t ≥ 0, & (x, y)∈Ω, \\ u(t, x, y) & = 0 & t ≥ 0, & (x, y)∈∂Ω, \\ u(0, x, y) & = f(x, y) & f ∈D(A), & (x, y)∈Ω \end{matrix}  (4.10)

where A is a closed self-adjoint linear operator in the Hilbert space

L_{0}^{2}(Ω) = {f ∈L^{2}(Ω) : f(x, y) = 0 for (x, y)∈∂Ω} ,

and Ω is a two dimensional rectangular domain. Suppose that A satisfy the quasi-dissipative condition

Re ⟨Af, f⟩ < ω ⟨f, f⟩ .  (4.11)

where ⟨·, ·⟩ denotes the L^{2} inner product. We define a bilinear form ⟨·, ·⟩_{E} from D(A)× D(A) → L_{0}^{2}(Ω) by

⟨f, g⟩_{E} := 2ω ⟨f, g⟩ − ⟨f, Ag⟩ .  (4.12)

Since A is self-adjoint and quasi-dissipative with the L^{2} inner product, it is easy to verify that ⟨·, ·⟩_{E} is an inner product. Define a new space

E := \{f ∈D(A) : ∥f∥_{E} := \sqrt{⟨f, f⟩_{E}} < ∞\}.

Using the closedness of A, it is verifiable that E is a Hilbert space.

The domain Ω is divided into p open subdomains Ω_{1}, Ω_{2}, ·, Ω_{p} (e.g. as in Figure 1), where these subdomains do not contain any part of the interface boundary and thus are disjoint. And the interface boundaries are defined as the set of points which are on the boundary of the subdomains and are in the interior of Ω. We denote the interface boundaries by B. Then the complement of the interface boundary is B^{c} = Ω_{1} ∪ Ω_{2} ∪ ⋯ ∪ Ω_{p}, and then Ω = B^{c} ∪ B.

Ω_{1}  Ω_{2}  ⋯  Ω_{p−1}  Ω_{p}

Figure 1

We discretize the domain Ω uniformly in each dimension with mesh size h = max(h_{x}, h_{y}), obtaining a discrete grid

Ω_{h} = {(x_{i}, y_{j}) : i = 0, 1, ⋯, m, and j = 0, 1, ⋯, n},

where x_{i−1} and x_{i} are neighboring coordinates in the x-dimension, and y_{j−1} and y_{j} are neighboring coordinates in the y-dimension with (x_{0}, y_{j}), (x_{m}, y_{j}), (x_{i}, y_{0}), (x_{i}, y_{n}) on the boundary ∂Ω. We define a finite dimensional function space E_{h} on the discrete domain by

E_{h} = {f ∈L^{2}(Ω_{h}) : f(x, y) = 0 for (x, y)∈∂Ω∩Ω_{h}} .

Let A_{h} be the discrete spatial approximation of A. If A_{h} retains the self-adjointness and the quasi-dissipative condition

Re ⟨A_{h}f, f⟩ < ω ⟨f, f⟩ ,  (4.13)

with respect to the finite dimensional L^{2} inner product

⟨f, g⟩ := \frac{l w}{mn} ∑_{i=1}^{m−1} ∑_{j=1}^{n−1} f(x_{i}, y_{j})g(x_{i}, y_{j}),

where l and w respectively are the length (|x_{0}−x_{m}|) and width (|y_{0}−y_{n}|) of the rectangular domain Ω, then E_{h} is a Hilbert space under the inner product

⟨f, g⟩_{h} := 2ω ⟨f, g⟩ − ⟨f, A_{h}g⟩ .  (4.14)

With both the decomposition and discretization of the domain Ω ready, we define the decomposition of the discrete domain Ω_{h} simply by inheriting the decomposition of the original domain:

\{ \begin{matrix}Ω_{h,i} = Ω_{h} ∩ Ω_{i} & for i = 1, 2, ⋯, p, \\ B_{h} = Ω_{h} ∩ B. \end{matrix}

Then our domain decomposition algorithm for computing the solution u_{h}^{n+1} at the (n+1)-th time step from the current n-th time step is as follows.

1. Compute u_{h}^{n+1} at B_{h} using an explicit scheme. These computed data provide the interface boundary conditions.

2. Compute u_{h}^{n+1} on the subdomains B_{h}^{c} using any unconditional stable scheme with the interface boundary conditions computed at step 1.

3. Throw away the interface boundary condition computed at step 1, bring back u^{n} on B_{h}, and then implicitly recompute u_{h}^{n+1} on B_{h}.

There are several choices for the explicit operator in step 1, for the implicit subdomain solvers in step 2, and for the implicit replacement operator in step 3. For the convenience of discussion, we choose the explicit scheme in step 1, and the implicit scheme in both steps 2 and 3.

We first introduce some notations for the representation of our algorithm. Define two operators A_{h,1} :=χ_{B_{h}} A_{h}, A_{h,2} :=χ_{B_{h}^{c}} A_{h}, where χ_{S} is the characteristic matrix for a subset S of Ω_{h} defined by

(χ_{S} u_{h}) (x) = \{ \begin{matrix}u_{h}(x), & x ∈ S, \\ 0, & x ∉ S. \end{matrix}

Thus χ_{S} is a diagonal matrix that has 1 at the positions corresponding to the grid points in the subset S and 0 everywhere else. The two matrices A_{h,1} and A_{h,2} are hence “restrictions” of A_{h} on B_{h} and B_{h}^{c} respectively. They form a splitting of matrix A_{h}, namely, A_{h} = A_{h,1} + A_{h,2}. It is easy to see that the matrices A_{h,1} and A_{h,2} have several rows whose entries are all zero. For the matrix A_{h,1}, the non-zero rows correspond to the grid points on the interface boundary, and the non-zero rows of the matrix A_{h,2} correspond to the grid points on the subdomains. If we order the grid points in such a way that the grid points on the interface boundaries are listed before the grid points in the subdomains Ω_{B_{h}^{c}} as in the ordering u_{h} = (u_{B_{h}} u_{B_{h}^{c}})^{T}, then with any spatial approximation method, the matrix A_{h} has the form A_{h} = \binom{D_{1} U_{1}}{L_{2} D_{2}}, where

A_{h,1} = \binom{D_{1} U_{1}}{0 0} and A_{h,2} = \binom{0 0}{L_{2} D_{2}} .  (4.15)

We first establish some properties about these two component matrices.

Lemma 4.2 If the matrix A_{h} is symmetric and satisfies the quasi-dissipative condition (4.13) for each h ∈ (0, 1), then for all h ∈ (0, 1), the component matrices A_{h,1} and A_{h,2} satisfy the quasi-dissipative condition Re ⟨A_{h,i}f, f⟩_{h} ≤ ω ⟨f, f⟩_{h}, with respect to the inner product given by (4.14).

Proof: We prove only the quasi-dissipativity of A_{h,1}. The proof for A_{h,2} is exactly the same and thus omitted.

Let f ∈E_{h}. By definition,

⟨A_{h,1}f, f⟩_{h} = 2ω ⟨A_{h,1}f, f⟩ − ⟨A_{h,1}f, A_{h}f⟩ .  (4.16)

Since A_{h,1} =χ_{B_{h}} A_{h}, we have that

⟨A_{h,1}f, A_{h}f⟩ = ⟨χ_{B_{h}} A_{h}f, A_{h}f⟩ = ⟨χ_{B_{h}} A_{h}f, χ_{B_{h}} A_{h}f⟩ = ⟨A_{h,1}f, A_{h,1}f⟩ .

Then from (4.16), we obtain that

\begin{aligned}Re ⟨A_{h,1}f, f⟩_{h} & = & 2ωRe ⟨A_{h,1}f, f⟩ − ⟨A_{h,1}f, A_{h,1}f⟩ \\ & = & ω(⟨A_{h,1}f, f⟩ + ⟨f, A_{h,1}f⟩) − ⟨A_{h,1}f, A_{h,1}f⟩ \\ & = & ω^{2} ⟨f, f⟩ − ⟨(ω − A_{h,1})f, (ω − A_{h,1})f⟩ \\ & ≤ & ω^{2} ⟨f, f⟩ . \end{aligned}  (4.17)

The quasi-dissipative condition (4.13) is obviously equivalent to 0 < ω ⟨f, f⟩ − ⟨A_{h}f, f⟩, which implies that ω ⟨f, f⟩<2ω ⟨f, f⟩−⟨A_{h}f, f⟩. But the right hand side is exactly ⟨f, f⟩_{h}. Then from (4.17), we have that Re ⟨A_{h,1}f, f⟩_{h} < ω ⟨f, f⟩_{h}.

Lemma 4.3 Suppose A_{h} satisfies the quasi-dissipative condition (4.13) for all h ∈ (0, 1). Then for all t∈[0, \frac{1}{8ω}], h∈(0, 1) and f ∈E_{h},

∥ χ_{B_{h}} (I −tA_{h,1})^{−1}f∥_{h}^{2} ≤ e^{4ωt}∥ χ_{B_{h}} f∥_{h}^{2} + (e^{4ωt}−1)∥ χ_{B_{h}^{c}} f∥_{h}^{2}.  (4.18)
∥ χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}f∥_{h}^{2} ≤ e^{4ωt}∥ χ_{B_{h}^{c}} f∥_{h}^{2} + (e^{4ωt}−1)∥ χ_{B_{h}} f∥_{h}^{2}.  (4.19)

Proof: We will prove only (4.18). The proof for (4.19) is the same and thus omitted.

Inequality (4.18) is obviously equivalent to

∥ χ_{B_{h}} g∥_{h}^{2} ≤ e^{4ωt}∥ χ_{B_{h}} (I −tA_{h,1})g∥_{h}^{2} + (e^{4ωt}−1)∥ χ_{B_{h}^{c}} (I −tA_{h,1})g∥_{h}^{2}  (4.20)

for all g ∈E_{h}. Since χ_{B_{h}^{c}}A_{h,1} =0 and χ_{B_{h}}A_{h,1} =A_{h,1}, the above inequality is equivalent to

∥ χ_{B_{h}} g∥_{h}^{2} ≤ e^{4ωt}∥ χ_{B_{h}} g − tA_{h,1}g∥_{h}^{2} + (e^{4ωt}−1)∥ χ_{B_{h}^{c}} g∥_{h}^{2}.  (4.21)

The right hand side of the above inequality is equal to

e^{4ωt} [∥ χ_{B_{h}} g∥_{h}^{2} − 2t Re ⟨A_{h,1}g, g⟩_{h} + t^{2}∥A_{h,1}g∥_{h}^{2}] + (e^{4ωt} − 1)∥ χ_{B_{h}^{c}} g∥_{h}^{2}.

Thus inequality (4.21) is equivalent to

0 ≤ (e^{4ωt} − 1) [∥ χ_{B_{h}} g∥_{h}^{2} + ∥ χ_{B_{h}^{c}} g∥_{h}^{2}] + e^{4ωt} [t^{2}∥A_{h,1}g∥_{h}^{2} − 2t Re ⟨A_{h,1}g, g⟩_{h}] .

But ∥ χ_{B_{h}} g∥_{h}^{2} + ∥ χ_{B_{h}^{c}} g∥_{h}^{2} = ∥g∥_{h}^{2}, the inequality above is again equivalent to

2t e^{4ωt} ⟨A_{h,1}g, g⟩_{h} ≤ (e^{4ωt} − 1)∥g∥_{h}^{2} + e^{4ωt}t^{2}∥A_{h,1}g∥_{h}^{2}.

Since e^{4ωt}t^{2}∥A_{h,1}g∥_{h}^{2} ≥ 0, the above inequality holds if

e^{4ωt}Re ⟨A_{h,1}g, g⟩_{h} ≤ \frac{e^{4ωt}−1}{2t}∥g∥_{h}^{2}.  (4.22)

So to show (4.18), it suffices to show that the inequality (4.22) holds for all g ∈ E_{h} and t∈[0, \frac{1}{2ω_{0}} ].

Lemma 4.2 states that for all g ∈ E_{h}, Re ⟨A_{h,1}g, g⟩_{h} ≤ ω ⟨g, g⟩_{h}, which, by multipying both sides by e^{4ωt}, is equivalent to

e^{4ωt}Re ⟨A_{h,1}g, g⟩_{h} ≤ e^{4ωt}ω ⟨g, g⟩_{h}  (4.23)

for all t ≥ 0. Since e^{4ωt} < 2 for t ∈ [0, \frac{1}{8ω}], it follows from (4.23) that e^{4ωt}Re ⟨A_{h,1}g, g⟩_{h} < 2ω ⟨g, g⟩_{h} for t ∈ [0, \frac{1}{8ω}]. But 2ω < \frac{e^{4ωt}−1}{2t}, then (4.22) follows immediately from the above inequality.

With the domain decomposition based matrix splitting given, the domain decomposition method is representable by (see [41] for its derivation)

u_{h}^{n+1} = (I −ΔtA_{h,1})^{−1}[χ_{B_{h}} + χ_{B_{h}^{c}} (I −ΔtA_{h,2})^{−1}(I +ΔtA_{h,1})] u_{h}^{n}.  (4.24)

Theorem 4.2 Let V(t, h) denote the error amplification matrix of method (4.24) for (t, h)∈ [0, 1]×(0, 1), namely,

V (t, h) = (I −tA_{h,1})^{−1}[χ_{B_{h}} + χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}(I +tA_{h,1})] .

Suppose that for each h∈(0, 1), A_{h} is self adjoint with respect to the finite dimensional L^{2} space inner product and satisfies the quasi-dissipative condition (4.13) with ω = 0.^{1} For each h ∈ (0, 1), let E_{h} be the Hilbert space with inner product (4.14). If for each h ∈ (0, 1), there exists a projection operators P_{h} : E → E_{h} such that for each f ∈D(A),

\{ \begin{matrix}sup_{h∈(0,1)} ∥P_{h}f∥_{h} ≤ M∥f∥_{E}, \\ sup_{h∈(0,1)} ∥A_{h}P_{h}f∥_{h} ≤ M(f) for some M(f) > 0, \end{matrix}  (4.25)

and

lim_{h→0} ∥A_{h}P_{h}f − P_{h}Af∥_{h} = 0.  (4.26)

then the limit

lim_{{h → 0 \atop n→∞}} ∥V(\frac{t}{n}, h)^{n}P_{h}f − P_{h}S(t)f∥_{h} = 0

holds uniformly for t in compact intervals, where S(t) is the semigroup generated by A.

1The case of ω > 0 can be proven similarly but with more messy calculations. The two lemmas Lemma 4.2 and Lemma 4.3 are sufficient for establishing estimates for the proof of the case ω > 0.

To prove this theorm, we need the following estimates. Lemma 4.4 The following inequalities hold for t∈[0, \frac{1}{2ω_{0}} ], h∈(0, ε) and f ∈E_{h}. ( i ) ∥V(t, h)^{n}f∥_{h} ≤ ∥(I −tA_{h,1})f∥_{h} for n∈N; (i i) ∥V(t, h)^{n+1}f − V(t, h)^{n}f∥_{h} ≤ t∥A_{h}f∥_{h} for n∈N; (iii) ∥V(t, h)^{n+1}f −V(t, h)^{n}f −tV (t, h)^{n}A_{h}f∥_{h} ≤ t^{2}∥A_{h}^{2}f∥_{h} for n∈N. Proof: (i) Let Ṽ (t, h) = (I −tA_{h,1}) V (t) (I −tA_{h,1})^{−1}, namely,

Ṽ =χ_{B_{h}} (I−tA_{h,1})^{−1}+ χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}(I+tA_{h,1})(I−tA_{h,1})^{−1}.  (4.27)

Then ∥Ṽ f∥_{h}^{2} = ∥χ_{B_{h}}(I−tA_{h,1})^{−1}f∥_{h}^{2} + ∥χ_{B_{h}^{c}}(I−tA_{h,2})^{−1}(I+tA_{h,1})(I−tA_{h,1})^{−1}f∥_{h}^{2}. It follows from (4.18) and (4.19) that

∥Ṽ f∥_{h}^{2} ≤ ∥χ_{B_{h}} f∥_{h}^{2} + ∥χ_{B_{h}^{c}} (I+tA_{h,1})(I−tA_{h,1})^{−1}f∥_{h}^{2} .  (4.28)

A straightforward calculations using the matrix form (4.15) of A_{h,1} and A_{h,2} reveals that

\{ \begin{matrix}χ_{B_{h}^{c}} (I +tA_{h,1})f =χ_{B_{h}^{c}} f, \\ χ_{B_{h}^{c}} (I −tA_{h,1})^{−1}f =χ_{B_{h}^{c}} f, \\ χ_{B_{h}^{c}} (I+tA_{h,1})(I−tA_{h,1})^{−1}f =χ_{B_{h}^{c}} f. \end{matrix}  (4.29)

for all f ∈E_{h}. Then it follows from (4.28) that

\begin{aligned}∥Ṽ f∥_{h}^{2} & ≤ & ∥χ_{B_{h}} f∥_{h}^{2} + ∥χ_{B_{h}^{c}} f∥_{h}^{2} \\ & = & ∥f∥_{h}^{2}. \end{aligned}  (4.30)

Now for f ∈E_{h},

\begin{aligned}∥V(t, h)^{n}f∥_{h} & = & ∥(I −tA_{h,1})^{−1} Ṽ^{n} (I −tA_{h,1})f∥_{h} \\ & ≤ & ∥(I −tA_{h,1})^{−1}∥ · ∥Ṽ ∥^{n} · ∥(I −tA_{h,1})f∥_{h} \\ & ≤ & ∥(I −tA_{h,1})^{−1}∥ · ∥(I −tA_{h,1})f∥_{h}, \end{aligned}  (4.31)

where the last inequality is due to (4.30). By Lemma 4.2, A_{h,1} is dissipative since ω = 0. Hence ∥(I −tA_{h,1})^{−1}∥_{h} ≤ 1. Then from (4.31) we obtain

∥V(t, h)^{n}f∥_{h} ≤ ∥(I −tA_{h,1})f∥_{h}.

(ii) For f ∈E_{h},

\begin{aligned}∥V(t, h)^{n+1}f −V(t, h)^{n}f∥_{h} & = & ∥V(t, h)^{n}[V(t, h)f − f]∥_{h} \\ & = & ∥(I −tA_{h,1})^{−1} Ṽ^{n} (I −tA_{h,1})[V(t, h)f − f]∥_{h} \\ & ≤ & ∥(I −tA_{h,1})[V(t, h)f − f]∥_{h}, \end{aligned}  (4.32)

where the last inequality is due to the (4.30) and the inequality ∥(I−tA_{h,1})^{−1}∥_{h} ≤ 1 implied by the dissipativity of A_{h,1}. And

\begin{aligned}(I −tA_{h,1})[V(t, h)f − f] & = & (I −tA_{h,1})V(t, h)f − (I −tA_{h,1})f \\ & = & [χ_{B_{h}}+χ_{B_{h}^{c}} (I−tA_{h,2})^{−1}(I+tA_{h,1})]f −(I−tA_{h,1})f \\ & = & χ_{B_{h}^{c}} [(I −tA_{h,2})^{−1}(I +tA_{h,1}) − I] f + tA_{h,1}f \\ & = & χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}tA_{h}f + tA_{h,1}f \\ & = & [χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}+ χ_{B_{h}}]tA_{h}f. \end{aligned}  (4.33)

Then it follows from (4.32) that

∥V(t, h)^{n+1}f −V(t, h)^{n}f∥_{h}^{2} ≤ ∥ χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}tA_{h}f∥_{h}^{2} + ∥ χ_{B_{h}} tA_{h}f∥_{h}^{2}
≤ ∥ χ_{B_{h}^{c}} tA_{h}f∥_{h}^{2} + ∥ χ_{B_{h}} tA_{h}f∥_{h}^{2}
= ∥tA_{h}f∥_{h}^{2},

where the second inequality is due to (4.19). (iii) For f ∈E_{h},

\begin{matrix}∥V (t, h)^{n+1}f − V (t, h)^{n}f − tV (t, h)^{n}A_{h}f∥_{h} \\ = ∥V (t, h)^{n}[V (t, h)f − f − tA_{h}f]∥_{h} \\ = ∥(I −tA_{h,1})^{−1}Ṽ^{n}(I −tA_{h,1})[V (t, h)f − f − tA_{h}f]∥_{h} \\ ≤ ∥(I −tA_{h,1})[V (t, h)f − f − tA_{h}f]∥_{h}. \end{matrix}  (4.34)

And from (4.33) we have that

(I −tA_{h,1})[V(t, h)f −f −tA_{h}f] = [χ_{B_{h}^{c}}(I −tA_{h,2})^{−1}+χ_{B_{h}}] tA_{h}f −(I −tA_{h,1})tA_{h}f
= [χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}− χ_{B_{h}^{c}} +tA_{h,1}]tA_{h}f
= [χ_{B_{h}^{c}} {(I −tA_{h,2})^{−1}−I} + tA_{h,1}]tA_{h}f
= [χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}tA_{h,2} + tA_{h,1}]tA_{h}f
= [χ_{B_{h}^{c}} (I −tA_{h,2})^{−1} χ_{B_{h}^{c}} + χ_{B_{h}}]t^{2}A_{h}^{2}f,

which, together with (4.34), implies that ∥V (t, h)^{n+1}f − V (t, h)^{n}f − tV (t, h)^{n}A_{h}f∥_{h}^{2} ≤ ∥ χ_{B_{h}^{c}} (I −tA_{h,2})^{−1}t^{2}A_{h,2}A_{h}f∥_{h}^{2} + ∥ χ_{B_{h}} t^{2}A_{h}^{2}f∥_{h}^{2} ≤ ∥ χ_{B_{h}^{c}} t^{2}A_{h,2}A_{h}f∥_{h}^{2} + ∥ χ_{B_{h}} t^{2}A_{h}^{2}f∥_{h}^{2} = ∥ χ_{B_{h}^{c}} t^{2}A_{h}^{2}f∥_{h}^{2} + ∥ χ_{B_{h}} t^{2}A_{h}^{2}f∥_{h}^{2}

= ∥t^{2}A_{h}^{2}f∥_{h}^{2},

where the second inequality is due to (4.19). Proof of Theorem 4.2: Define a product space

E = {{f_{h}} : h∈(0, δ), f_{h} ∈E_{h}, |||{f_{h}}||| = sup_{h∈(0,1)} ∥f_{h}∥_{h} < ∞} ,

and define an operator A on E by A{f_{h}} = {A_{h}f_{h}}. Since D(A_{h}) = E_{h}, the domain of A is obviously D(A) = {{f_{h}}∈E : sup_{h∈(0,1)} ∥A_{h}f_{h}∥_{h} < ∞} . It is easy to verify that A is closed. And since A_{h} = A_{h,1} + A_{h,2} and A_{h,1}, A_{h,2} are dissipative, so is the operator A. Then A generates a C_{0}-semigroup S. Again define two operators A_{1} and A_{2} on D(A) by

A_{1}{f_{h}} := {A_{h,1}f_{h}}, A_{2}{f_{h}} := {A_{h,2}f_{h}}.

Then similarly we can show that A_{1} and A_{2} generate C_{0}-semigroups S_{1} and S_{2} respectively. It is easy to verify that for t > 0,

\{ \begin{matrix}(I − tA_{1})^{−1} = \{(I − tA_{h,1})^{−1}\} , \\ (I − tA_{2})^{−1} = \{(I − tA_{h,2})^{−1}\} . \end{matrix}  (4.35)

Now, we define a temporal method to approximate the semigroup S. For t∈[0, 1], define W (t) by W (t){f_{h}} = {V (t, h)f_{h}} for t∈[0, 1]. It is easily verifiable that for each t∈[0, 1], W (t) is linear and

W (t)f = (I − tA_{1})^{−1}[W_{1} + W_{2}(I − tA_{2})^{−1}U(t)]f  (4.36)

for f ∈D(A), where

\{ \begin{matrix}W_{1} & = & \{χ_{B_{h}}\}, \\ W_{2} & = & \{χ_{B_{h}^{c}}\}, \\ U(t) & = & \{(I +tA_{h,1})\}. \end{matrix}  (4.37)

To see that D(A) ⊂ D(W (t)^{∞}) for all t∈[0, 1], let f = {f_{h}}∈D(A). Then by statement (i) of Lemma 4.4, for any k ∈N and t∈[0, 1],

∥V (t, h)^{k}f_{h}∥_{h} ≤ ∥(I − tA_{h,1})f_{h}∥_{h}
≤ ∥f_{h}∥_{h} + t∥ χ_{B_{h}} A_{h}f_{h}∥_{h}
≤ ∥f_{h}∥_{h} + t∥A_{h}f_{h}∥_{h}.

Since {f_{h}}∈D(A), we have that sup_{h∈(0,1)}{∥f_{h}∥_{h}, ∥A_{h}f_{h}∥_{h}} < ∞, so

|||W (t)^{k}f||| = sup_{h∈(0,1)} ∥V (t, h)^{k}f_{h}∥_{h}
≤ sup_{h∈(0,1)}{∥f_{h}∥_{h} + t∥A_{h}f_{h}∥_{h}}
< ∞,

which means that f ∈D(W (t)^{∞}).

Next, we shall show that for each f ∈D(A), W (t)f is continuous in t. Since A_{1} and A_{2} are dissipative, it follows that for f ∈E, the maps t ↦ (I−tA_{1})^{−1}f and t ↦ (I−tA_{2})^{−1}f are continuous. Since W_{1} and W_{2} are bounded operators on E, to show that W (t)f is continuous in t for f ∈ D(A), it suffices to show that t ↦ U(t)f is continuous for f ∈ D(A). Now let f = {f_{h}} ∈ D(A), and let t, t′ ∈ [0, 1]. Then, |||U(t)f − U(t′)f||| = ||| {(t − t′)A_{h,1}f_{h}} ||| ≤ (t − t′)|||Af|||, from which it follows that t ↦ U(t)f is continuous for each f ∈D(A).

For f ∈D(A), by definition of ||| · ||| we have that

|||W (t)^{n+1}f − W^{n}(t)f||| = sup_{h∈(0,1)} ∥V (t, h)^{n+1}f_{h} − V (t, h)^{n}f_{h}∥_{h}
≤ sup_{h∈(0,1)} ∥t A_{h}f_{h}∥_{h}
= t|||Af|||,

where the inequality above is due to Lemma 4.4. And for f ∈ D(A^{2}), we can also obtain the following immediately from Lemma 4.4.

|||W (t)^{n+1}f − W (t)^{n}f − tW (t)^{n}Af||| ≤ t^{2}|||A^{2}f|||.

Then it follows from Theorem 3.2 that for f ∈D(A),

lim_{n→∞} W (\frac{t}{n})^{n}f = S(t)f  (4.38)

uniformly in compact intervals. Let f ∈ D(A). Then (4.25) implies that {P_{h}f} ∈ D(A). It is easy to see that S(t) = {e^{tA_{h}}}. Then we obtain from (4.38) that

lim_{n→∞} sup_{h∈(0,1)} ∥V (t/n, h)^{n}P_{h}f − e^{tA_{h}}P_{h}f∥_{h} = 0  (4.39)

uniformly for t in compact intervals for each f ∈ D(A). Since A_{h} is dissipative for each h ∈ (0, 1), the semigroups {e^{tA_{h}}}_{h∈(0,1)} are uniformly norm-bounded by 1. Since e^{tA_{h}} = (e^{\frac{t}{n} A_{h}})^{n}, the assumption (4.26) and the spatially discrete version of the Chernoff’s product formula (see [28], pp 96) imply that for f ∈D(A),

lim_{h→0} ∥e^{tA_{h}}P_{h}f − P_{h}S(t)f∥_{h} = 0  (4.40)

uniformly for t in compact intervals. Then, with (4.39) and (4.40), the conclusion of this theorem follows from the inequality

∥V(\frac{t}{n}, h)^{n}P_{h}f −S(t)f∥_{h} ≤ sup_{h∈(0,1)} ∥V(\frac{t}{n}, h)^{n}P_{h}f −e^{tA_{h}}P_{h}f∥_{h} + ∥e^{tA_{h}}P_{h}f −S(t)f∥_{h}.

References

[1] G. Arendt, Ch. Batty, M. Hieber and F. Neubrander, Vector-Valued Laplace Transforms and Cauchy Problems. Accepted for publication in the series Monographs in Mathematics by Birkhaeuser Verlag.

[2] B. Bäumer and F. Neubrander, Laplace transform methods for evolution equations, Conferenze del Seminario di Mathematica dell’ Universitá Bari 259 (1994), pp. 27-60.

[3] K. Black, Polynomial collocation using a domain decomposition solution to parabolic PDE’s via the penalty method and explicit/implicit time marching, J. Sci. Comput., 7 (1992), no. 4, pp. 313-338.

[4] P. Butzer and R. Weis, On the Lax equivalence theorem equipped with orders, J. Approx. Theory, 19 (1977), No. 3, pp. 239-252.

[5] P. Butzer, W. Dickmeis and R. Nessel, Lax-type theorems with orders in connection with inhomogeneous evolution equations in Banach spaces. Linear Spaces and Approximation (Proc. Conf. Math. Res. Inst. Oberwolffach, 1997), pp. 531-546. Lecture Notes in Biomath., 21, Springer, Berlin-New York, 1978.

[6] R. Courant, K. Friedrichs and H. Lewy, Über die partiellen Differenzialgleichungen der mathematischen Physik, Math. Ann., Vol. 100, 1928, pp. 32-74.

[7] P. Chernoff, Note on product formulas for operator semigroups, J. Funct. Anal. 2 (1968), pp. 238-242.

[8] E. Du Fort and S. Frankel, Stability conditions in the numerical treatment of parabolic differential equations, Math. Tables and Other Aids to Computation, 7 (1953), pp. 135-152.

[9] J. A. Goldstein, Semigroups of Linear Operators and Applications. Oxford University Press 1985.

[10] R. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM, 12 (1965), pp. 95-113.

[11] , The potential calculation and some applications, Meth. in Comput. Phys., 9 (1970), pp. 135-211.

[12] F. John, On integration of parabolic equations by difference methods, Comm. Pure Appl. Math. 5 (1952), pp. 155-211.

[13] T. Kato, Remarks on pseudo-resolvents and infinitesimal generators of semigroups, Proc. Japan Acad. 35(1959), pp. 195-211.

[14] T.G. Kurtz, Extensions of Trotter’s operator semigroup approximation theorems, J. Funct. Anal. 3 (1969), pp. 354-375.

[15] , A general theorem on the convergence of operator semigroups, Trans. Amer. Math. Soc. 148 (1970), pp. 49-58.

[16] P. D. Lax, On the stability of difference approximations to solutions of hyperbolic equations with variable coefficients, Comm. Pure Appl. Math., Vol. 14 (1961), pp. 497-520.

[17] P. Lax and R. Richtmyer, Survey of stability of linear finite difference equations. Comm. Pure Appl. Math., Vol. 9 (1956), pp. 267-293.

[18] P. Lax and B. Wendroff, Systems of conservation laws, Comm. Pure Appl. Math., Vol. 13 (1960), pp. 217-237.

[19] , On the stability of difference schemes, Comm. Pure Appl. Math., Vol. 15 (1962), pp. 363-371.

[20] G. Lumer and R. S. Phillips, Dissipative operators in a Banach space, Pac. J. Math. 11 (1961), pp. 679-698.

[21] T. Mathew, P. Polyakov, G. Russo, and J. Wang, Domain decomposition operator splittings for the solution of parabolic equations. SIAM J. Sci. Comput. Vol. 19, No. 3, pp. 912-932, May 1998.

[22] J. Von Neumann and R. Richtmyer, A method for the numerical calculation of hydrodynamic shocks, J. Appl. Physics, 21 (1950), pp. 232-237.

[23] M. Nagumo, Einige analytische Untersuchugen in linearen metrischen Ringen, Jap. J. Math. 13 (1936), pp. 61-80.

[24] D. S. Nathan, One-parameter groups of transformations in abstract vector spaces, Duke Math. J. 1 (1935), pp. 518-526.

[25] F. Neubrander and Y. Zhuang, Stabilized approximation for evolution equations, Preprint.

[26] J. Neveu, Théorie des semi-groupes de Markov, Univ. Calif. Publ. Statistics, 2 (1958), pp. 319-394.

[27] G.-Z. Ouyang, S.-Y. Zhu and Z.-F. Chin, Mathematical Analysis, Vol. 2, 4th printing, Shanghai Press of Science and Technology 1985.

[28] A. Pazy, Semigroups of Linear Operators and Applications to Partial Differential Equations. Springer-Verlag 1983.

[29] D. W. Peaceman and J. H. H. Rachford, The numerical solution of parabolic and elliptic differential equations, J. SIAM, 3 (1955), pp. 28-41.

[30] H. H. Schaefer, Topological Vector Spaces. 4th printing, Springer 1980.

[31] G. Strang, Accurate partial difference methods I: Linear Cauchy problems, Arch. Rational Mech. Anal., 12 (1963), pp. 392-402.

[32] , Wiener-Hopf difference equations, J. Math. Mech., Vol. 13 (1964), No. 1, pp. 85-96 [33] , Accurate partial difference methods II: Non-linear problems, Numer. Math., 6

(1964), pp. 37-46.

[34] , On the construction and comparison of difference schemes, SIAM J. Numer. Anal., Vol. 5, No. 3, September 1968, pp. 506-517.

[35] X. Sun and Y. Zhuang, A high-order direct solver for helmholtz equations with neumann boundary conditions. NASA ICASE Technical Report No. 97-11, NASA Langley Research Center Hampton, VA 23681-0001, 1997.

[36] H. F. Trotter, Approximation of semigroups of operators, Pac. J. Math. 8(1958), pp. 887-919.

[37] H. F. Trotter, On the product of semi-groups of operators, Proc. Amer. Math. Soc., 10 (1959), pp. 545–551.

[38] D.-X. Xia, Z.-R. Wu, S.-Z. Yan and W.-C. Shu, Real Variables and Functional Analysis, Vol. 2, 2nd printing, 2nd ed., Higher Education Press Beijing, 1986

[39] K. Yosida, On the group embedded in the metrical complete ring, Japan J. Math. 13 (1936), pp. 7-26.

[40] Y. Zhuang, PhD dissertation proposal, Department of Computer Science, Louisiana State University Baton Rouge, July 1999.

[41] Y. Zhuang and X. Sun, A parallel domain decomposition method for parabolic equations, preprint.

Vita

The author was born on March 7, 1968, in Hanzhou, China. After obtaining his high school diploma in 1986, he entered Zhejiang University in September of the same year, where he started his career training as a mathematician. After writing a thesis on extrapolation based approximation methods, he graduated with a degree of Bachelor of Science in applied mathematics in July 1990. He was assigned to Yonggu Rubber Factory as an official employee in August 1990 and during the winter of 1990 and 1991, he took a leave from Yonggu and worked as an un-official employee for Shanghai Wu-Song Electric Equipement Company as a software engineer until the Spring of 1992 when he returned to Yonggu. After working as an information analyst in Yonggu for a few months, he left for the United States and entered the graduate program in the Department of Mathematics of Louisiana State University in the Fall of 1992. In December 1995, he received a master of science degree from the Department of Mathematics at Louisiana State University. During the summers of 1997 and 1998, he went to Los Alamos National Laboratory and worked in the Scientific Computing group (CIC-19) of CIC division. In May 1998 he received a master of science degree from the Department of Computer Science of Louisiana State University. In August, 2000, the degree of Doctor of Philosophy in mathematics will be conferred.