Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://srcc.msu.ru/nivc/english/about/home_pages/piskarev/obz1en.pdf Äàòà èçìåíåíèÿ: Thu Jun 5 17:53:19 2008 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 23:06:47 2012 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: m 87 jet

Journal of Mathematical Sciences, Vol. xxx, No. y, 2003

APPROXIMATION OF ABSTRACT DIFFERENTIAL EQUATIONS

Davide Guidetti, Bulent Karas¨ en, and Sergei Piskarev ¨ oz

UDC 517.988.8

1. Introduction This review pap er is devoted to the numerical analysis of abstract differential equations in Banach spaces. Most of the finite difference, finite element, and pro jection methods can b e considered from the p oint of view of general approximation schemes (see, e.g., [207, 210, 211] for such a representation). Results obtained for general approximation schemes make the formulation of concrete numerical methods easier and give an overview of methods which are suitable for different classes of problems. The qualitative theory of differential equations in Banach spaces is presented in many brilliant pap ers and b ooks. We can refer to the bibliography [218], which contains ab out 3000 references. Unfortunately, no b ooks or reviews on general approximation theory app ear for differential equations in abstract spaces during last 20 years. Any information on the sub ject can b e found in the original pap ers only. It seems that such a review is the first step towards describing a complete picture of discretization methods for abstract differential equations in Banach spaces. In Sec. 2 we describ e the general approximation scheme, different typ es of convergence of op erators, and the relation b etween the convergence and the approximation of sp ectra. Also, such a convergence analysis can b e used if one considers elliptic problems, i.e., the problems which do not dep end on time. Section 3 contains a complete picture of the theory of discretization of semigroups on Banach spaces. It summarizes Trotter­Kato and Lax­Richtmyer theorems from the general and common p oint of view and related problems. The approximation of ill-p osed problems is considered in Sec. 4, which is based on the theory of approximation of local C -semigroups. Since the backward Cauchy problem is very imp ortant in applications and admits a stochastic noise, we also consider approximation using a stochastic regularization. Such an approach was never considered in the literature b efore to the b est of our knowledge. In Sec. 5, we present discrete coercive inequalities for abstract parab olic equations in Cn ([0,T ]; En ),
Cn ([0,T ]; En ), Lpn ([0,T ]; En ), and Bn ([0,T ]; C (h )) spaces.

Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory. Vol. 113, Functional Analysis, 2002. 1072­3374/03/xxxy­0001 $ 27.00 c 2003 Plenum Publishing Corporation 1


The last section, Sec. 6 deals with semilinear problems. We consider approximations of Cauchy problems and also the problems with p eriodic solutions. The approach describ ed here is based on the theory of rotation of vector fields and the principle of compact approximation of op erators. 2. General Approximation Scheme Let B (E ) denote the Banach algebra of all linear b ounded op erators on a complex Banach space E . The set of all linear closed densely defined op erators on E will b e denoted by C (E ). We denote by (B ) the sp ectrum of the op erator B, by (B ) the resolvent set of B, by N (B ) the null space of B , and by R(B ) the range of B . Recall that B B (E ) is called a Fredholm op erator if R(B ) is closed, dim N (B ) < and codim R(B ) < , the index of B is defined as ind B = dim N (B ) - codim R(B ). The general approximation scheme [83­85, 187, 207, 210] can b e describ ed in the following way. Let En and E b e Banach spaces, and let {pn } b e a sequence of linear b ounded op erators pn : E En ,pn B (E, En ), n N = {1, 2, ··· }, with the following prop erty: pn x
E
n

x

E

as n for any x E.

Definition 2.1. A sequence of elements {xn },xn En ,n N, is said to b e P -convergent to x E iff xn - pn x
E
n

0 as n ; we write this as xn x.

Definition 2.2. A sequence of elements {xn },xn En ,n N, is said to b e P -compact if for any N N there exist N N and x E such that xn x, as n in N . Definition 2.3. A sequence of b ounded linear op erators Bn B (En ),n N, is said to b e PP -convergent to the b ounded linear op erator B B (E ) if for every x E and for every sequence {xn },xn En ,n N, such that xn x one has Bn xn Bx. We write this as Bn B. For general examples of notions of P -convergence, see [82, 187, 203, 211]. Remark 2.1. If we set En = E and pn = I for each n N, where I is the identity op erator on E , then Definition 2.1 leads to the traditional p ointwise convergence of b ounded linear op erators which is denoted by Bn B. Denote by E + the p ositive cone in a Banach lattice E. An op erator B is said to b e positive if for any x+ E + , it follows Bx+ E + ; we write 0 B.

Definition 2.4. A system {pn } is said to b e discrete order preserving if for all sequences {xn },xn En , and any element x E , the following implication holds: xn x implies x+ x+ . n 2


It is known [99] that {pn } preserves the order iff pn x+ - (pn x)+

E

n

0 as n for any x E.

In the case of unb ounded op erators, and, in general, we know infinitesimal generators are unb ounded, we consider the notion of compatibility. Definition 2.5. A sequence of closed linear op erators {An }, An C (En ), n N, is said to b e compatible with a closed linear op erator A C (E ) iff for each x D(A) there is a sequence {xn },xn D(An ) En ,n N, such that xn x and An xn Ax. We write this as (An ,A) are compatible. In practice, Banach spaces En are usually finite dimensional, although, in general, say, for the case of a closed op erator A, we have dim En and An
B (En )

as n .

2.1. Approximation of spectrum of linear operators. The most imp ortant role in approximations of equation Bx = y and approximations of sp ectra of an op erator B is played by the notions of stable and regular convergence. These notions are used in different areas of numerical analysis (see [10, 15, 81, 86­ 89, 207, 210, 212, 222]). Definition 2.6. A sequence of op erators {Bn },Bn B (En ),n N, is said to b e stably convergent to an
- op erator B B (E ) iff Bn B and Bn 1 B (En )

= O(1),n . We will write this as: Bn B stably.

Definition 2.7. A sequence of op erators {Bn },Bn B (En ), is called regularly convergent to the op erator B B (E ) iff Bn B and the following implication holds: xn
E
n

= O(1) & {Bn xn } is P -compact = {xn } is P -compact .

We write this as: Bn B regularly. Theorem 2.1 ([210]). For Bn B (En ) and B B (E ) the fol lowing conditions are equivalent: (i) Bn B regularly, Bn are Fredholm operators of index 0 and N (B ) = {0}; (ii) Bn B stably and R(B ) = E ; (iii) Bn B stably and regularly;
- (iv) if one of conditions (i)­(iii) holds, then there exist Bn 1 B (En ),B -1 - B (E ), and Bn 1 B -1

regularly and stably. This theorem admits an extension to the case of closed op erators B C (E ),Bn C (En ) [213]. Let C b e some op en connected set, and let B B (E ). For an isolated p oint (B ), the corresp onding maximal invariant space (or generalized eigenspace) will b e denoted by W (; B ) = P ()E , 1 where P () = (I - B )-1 d and is small enough so that there are no p oints of (B ) in 2i | -|= the disc { : | - | } different from . The isolated p oint (B ) is a Riesz point of B if 3


I - B is a Fredholm op erator of index zero and P () is of finite rank. Denote by W (, ; Bn ) =
|n -|<,n (Bn )

W (n ,Bn ), where n (Bn ) are taken from a -neighb orhood of . It is clear that

1 (In - Bn )-1 d . The following theorems state the 2i | -|= complete picture of the approximation of the sp ectrum. W (, ; Bn ) = Pn ()En , where Pn () = Theorem 2.2 ([82, 208, 209]). Assume that Ln () = I - Bn and L() = I - B are Fredholm operators of index zero for any and Ln () L() stably for any (B ) = . Then (i) for any 0 (B ) , there exists a sequence {n }, n (Bn ), n N, such that n 0 as n ; (ii) if for some sequence {n },n (Bn ), n N, one has n 0 as n , then 0 (B ); (iii) for any x W (0 ,B ), there exists a sequence {xn }, xn W (0 ,; Bn ), n N, such that xn x as n ; (iv) there exists n0 N such that dim W (0 ,; Bn ) dim W (0 ,B ) for any n n0 . Remark 2.2. The inequality in (iv) can b e strict for all n N as is shown in [207]. Theorem 2.3 ([210]). Assume that Ln () and L() are Fredholm operators of index zero for al l . Suppose that Ln () L() regularly for any and (B ) = . Then statements (i)­(iii) of Theorem 2.2 hold and also (iv) there exists n0 N such that dim W (0 ,; Bn ) = dim W (0 ,B ) for al l n n0 ; (v) any sequence {xn },xn W (0 ,; Bn ), n N, with xn of this sequence belongs to W (0 ,B ). Remark 2.3. Estimates of |n - 0 |, gap W (0 ,; Bn ), W (0 ,B ) ^ and |n - 0 | are given in [210],
E
n

= 1 is P -compact and any limit point

^ where n denotes the arithmetic mean (counting algebraic multiplicities) of the sp ectral values of Bn that contribute to W (0 ,; Bn ). For the notion of gap and its prop erties, see [105]. 2.2. Regions of convergence. Theorems 2.2 and 2.3 have b een generalized to the case of closed op erators in [213] by using the following notions introduced by Kato [105]. Definition 2.8. The region of stability s = s ({An }), An C (Bn ), is defined as the set of all C such that (An ) for almost all n and such that the sequence { (In - An )-1 }n s ({An }) and such that the sequence of op erators {(In - An )-1 }n op erator S () B (E ). 4
N

is b ounded.

The region of convergence c = c ({An }), An C (En ), is defined as the set of all C such that
N

is PP -convergent to some


It is clear that S (·) is a pseudo-resolvent, and S (·) is a resolvent of some op erator iff N (S ()) = {0} for some (cf. [105]). Definition 2.9. A sequence of op erators {Kn }, Kn C (En ), is called regularly compatible with an op erator K C (E ) if (Kn ,K ) are compatible and, for any b ounded sequence xn
E
n

= O(1) such that

xn D(Kn ) and {Kn xn } is P -compact, it follows that {xn } is P -compact, and the P -convergence of {xn } to some x and that of {Kn xn } to some y as n in N N imply that x D(K ) and Kx = y. Definition 2.10. The region of regularity r = r ({An },A), is defined as the set of all C such that (Kn ,K ), where Kn = In - An and K = I - A are regularly compatible. The relationships b etween these regions are given by the following statement. Proposition 2.1 ([213]). Suppose that c = and N (S ()) = {0} at least for one point c so that S () = (I - A)-1 . Then (An ,A) are compatible and c = s (A) = s r = r (A). It is shown in [213] that the conditions (An ,A) are compatible, I - An and I - A are Fredholm operators with index zero for any and (A) = imply (i)­(iv) of Theorem 2.2 when (A) and imply (i)­(iii) of Theorem 2.2 and (iv)­(v) of Theorem 2.3, when r . Definition 2.11. A Riesz p oint 0 (A) is said to b e strongly stable in Kato's sense if dim W (0 ,; Bn ) dim W (0 ,B ) for all n n0 . Theorem 2.4 ([213]). The Riesz point 0 (A) is strongly stable in Kato's sense iff 0 r (A). Investigations of approximation of sp ectra and typ es of convergence, but not those of general approximation scheme are given in [13, 40, 52, 130, 131, 142, 145]. 2.3. Convergence in Anselone's conditions. Throughout this subsection we assume that En = E and pn = I for all n N. Hence the symb ol P will b e omitted in the notation of this subsection. Let us recall that if Bn B compactly (see Definition 2.12), then for any = 0 we have I - Bn I - B regularly [207]. When Bn B compactly and B is a compact op erator, Anselone [10] has proved that (Bn - B )Bn 0, (Bn - B )B 0 as n . (2.1)
s

Considering an approximation of a weakly singular compact integral op erator, Ahues [4] has proved that these convergence prop erties (2.1) are sufficient to state that a Riesz p oint is strongly stable in Kato's sense. 5


Theorem 2.5 ([7]). Assume that B B (E ) is compact and that Bn B. If (Bn - B )Bn 0 as n ; then for any nonzero 0 (B ), assertions (i)­(iii) of Theorem 2.2 and assertions (iv)­(v) of Theorem 2.3 hold. Theorem 2.6 ([7]). Assume that Bn B and (2.1) holds. Then for any nonzero Riesz point 0 (B ), assertions (i)­(iii) of Theorem 2.2 and assertions (iv)­(v) of Theorem 2.3 hold. Corollary 2.1 ([5]). Assume that Bn B, I - Bn are Fredholm operators of index zero for {z :
k |z - 0 | }, and (Bn - B )Bn 0 as n for some k N. Then for any nonzero Riesz point

0 (B ), assertions (i)­(iii) of Theorem 2.2 and assertions (iv)­(v) of Theorem 2.3 hold. Theorem 2.7 ([7]). Assume that B is compact, Bn B , and Bn (Bn - B ) 0. Then 0 In - Bn 0 I - B regularly for any 0 = 0.
k Theorem 2.8 ([7]). Assume that B is compact, Bn B , and Bn (Bn - B ) 0 for some k N. Then

0 In - Bn 0 I - B regularly for any 0 = 0. Let r (B ) b e a sp ectral radius of op erator B B (E ). Theorem 2.9 ([18]). Let E be a Banach lattice. Let 0 (Bn ) and r (Bn ) r (B ) as n . The conclusion on the order of convergence of eigenvectors in Theorem 2.9 also is given in [17]. The application of Theorems 2.5­2.8 to the numerical solution of a mathematical model used in the jet printer industry is considered in [6, 118]. 2.4. Compact convergence of resolvents. We now consider the imp ortant class of op erators which have compact resolvents. We will use this prop erty of generator as an assumption in Sec. 6. In this case, it is natural to consider approximate op erators which "preserve" this prop erty. Definition 2.12. A sequence of op erators {Bn }, Bn B (En ), n N, converges compactly to an op erator B B (E ) if Bn B and the following compactness condition holds: xn
E
n

Bn ,B B (E ) be such that Bn B and

(Bn - B )+ 0 as n . Suppose that r (B ) is a Riesz point of (B ). Then r (Bn ) is a Riesz point of

= O(1) = {Bn xn } is P -compact.

Definition 2.13. The region of compact convergence of resolvents, cc = cc (An ,A), where An C (En ) and A C (E ) is defined as the set of all c (A) such that (In - An )-1 (I - A)-1 compactly. 6


Theorem 2.10. Assume that cc = . Then for any s the fol lowing implication holds: xn
E
n

= O(1) & (In - An )xn

E

n

= O(1) = {xn } is P -compact.

(2.2)

Conversely, if for some c (A) implication (2.2) holds, then cc = . Proof. Let (µIn - An )-1 (µI - A)-1 compactly for some µ cc . Then for xn (I - An )xn
E
n

E

n

= O(1) and

= O(1), from the Hilb ert identity (In - An )-1 - (µIn - An )-1 = (µ - )(In - An )-1 (µIn - An )-1 , (2.3)

we obtain xn = (µIn - An )-1 (In - An )xn - ( - µ)(µIn - An )-1 xn , and it follows that {xn } is P -compact. Conversely, let implication (2.2) hold for some 0 c (A). We show that 0 cc . Taking a b ounded sequence {yn }, n N, we obtain (0 In - An )-1 y to the sequence xn = (0 In - An )-1
nE
n

= O(1) for n N. Let us apply implication (2.2)

yn . It is easy to see that {xn } is P -compact. Hence 0 cc .

Corollary 2.2. Assume that cc = . Then cc = c (A). Proof. It is clear that cc c (A). To prove that cc c (A), let us consider the Hilb ert identity (2.3). Now let µ cc . Then µ cc c (A). Hence, for every c (A) and for any b ounded sequence {xn }, n N, the sequence {(In - An )-1 xn } is P -compact. Comparing Definitions 2.7, 2.8, and 2.13 with implication (2.2), we see that cc r . Theorem 2.11. Assume that cc = . Then r = C. Proof. Take any p oint 1 C. We have to show that (1 In - An ,1 I - A) are regularly compatible. Assume that xn
E
n

= O(1) and that {(1 In - An )xn } is P -compact. To show that {xn } is P -compact, we

take µ cc . Using (2.3) with = 1 , we obtain xn = (µIn - An )-1 (1 In - An )xn +(1 - µ)(µIn - An )-1 xn and, therefore, {xn } is P -compact. Assume now that xn x and (1 In - An )-1 xn y, as n in N N. Then x = (µI - A)-1 y - (1 - µ)(µI - A)-1 x, and it follows that x D(A)and (1 I - A)x = y . 3. Discretization of Semigroups Let us consider the following well-p osed Cauchy problem in the Banach space E with an op erator A C (E ) u (t) = Au(t), t [0, ), u(0) = u0 , 7 (3.1)


where the op erator A generates a C0 -semigroup exp(·A). It is well-known that this C0 -semigroup gives the solution of (3.1) by the formula u(t) = exp(tA)u0 for t 0. The theory of well-p osed problems and numerical analysis of these problems have b een develop ed extensively; see, e.g., [75, 88, 105, 161, 163, 200, 216]. Let us consider on the general discretization scheme for the semidiscrete approximation of the problem (3.1) in the Banach spaces En : un (t) = An un (t), t [0, ), un (0) = u0 n , (3.2)

with the op erators An C (En ) such that they generate C0 -semigroups which are compatible with the op erator A and u0 u0 . n 3.1. The simplest discretization schemes. We have the following version of Trotter­Kato's Theorem on the general approximation scheme. Theorem 3.1 ([203] (Theorem ABC)). The fol lowing conditions (A) and (B) are equivalent to condition (C). (A) Compatibility. There exists (A) n (An ) such that the resolvents converge: (In - An )-1 (I - A)-1 ; (B) Stability. There are some constants M 1 and , independent of n and that M exp(t) for t 0 and any n N; (C) Convergence. For any finite T > 0, one has max n whenever u0 u0 . n The analytic C0 -semigroup case is slightly different from the general case but has the same prop erty (A). Theorem 3.2 ([161]). Let operators A and An generate analytic C0 -semigroups. The fol lowing conditions (A) and (B1 ) are equivalent to condition (C1 ). (A) Compatibility. There exists (A) n (An ) such that the resolvents converge: (In - An )-1 (I - A)-1 ; (B1 ) Stability. There are some constants M2 1 and 2 such that (I - An )-1 8 M2 , Re > 2 ,n N; | - 2 |
t[0,T ]

exp(tAn )

exp(tAn )u0 - pn exp(tA)u0 0 as n


(C1 ) Convergence. For any finite µ > 0 and some 0 < <
(,µ)

, we have 2

max

exp(An )u0 - pn exp(A)u0 0 n

as n whenever u0 u0 . Here, (, µ) = {z ( ) : |z | µ} and ( ) = {z C : | arg z | }. n Definition 3.1. A linear op erator A : D(A) E E is said to have the positive off-diagonal (POD) property if Au, 0 whenever 0 Definition 3.2. An element e E 0 R such that -e x u D(A) and 0
+

E with u, = 0.

is said to b e an order-one in E if for every x E there exists
+

e. For e int E x
e

we can define the order-one norm by x e}.
E

= inf { 0 : -e

An ordered Banach space E is called an order-one space if there exists e int E + such that · Now we can state a version of the Trotter­Kato theorem for p ositive semigroups.

=·

e

.

Theorem 3.3 ([169]). Let the operators An and A from (3.1) and (3.2) be compatible, let E, En be
+ order-one spaces, and let en D(An ) int En . Assume that the operators An have the POD property and

An en

0 for sufficiently large n. Then exp(tAn ) exp(tA) uniformly in t [0,T ].

We can assume without loss of generality that conditions (A) and (B) hold for the corresp onding semigroup case if any discretization processes in time are considered. If we denote by Tn (·) a family 1 (Tn (n ) - In ) B (En ) and Tn (t) = Tn (n )kn , where of discrete semigroups as in [105], i.e., An = n t , as n 0,n , then one obtains the following assertion. kn = n Theorem 3.4 ([203] (Theorem ABC-discr.)). The fol lowing conditions (A) and (B ) are equivalent to condition (C ). (A) Compatibility. There exists (A) n (An ) such that the resolvents converge: (In - An )-1 (I - A)-1 ; (B ) Stability. There are some constants M1 1 and 1 such that Tn (t) M1 exp(1 t) for t R+ = [0, ),n N; (C ) Convergence. For any finite T > 0 one has maxt whenever u0 u0 . n 9
[0,T ]

Tn (t)u0 - pn exp(tA)u0 0 as n , n


Theorem 3.5 ([203]). Assume that conditions (A) and (B) of Theorem 3.1 hold. Then the implicit difference scheme U n (t + n ) - U n (t) = An U n (t + ), U n (0) = u0 , n n is stable, i.e. (In - n An )-k
n

(3.3)

M1 e1 t ,t = kn n R+ , and gives an approximation of the solution

of problem (3.1), i.e., U n (t) (In - n An )-kn u0 exp(tA)u0 P -converges uniformly with respect to n n t = kn n [0,T ] as u0 u0 ,n ,kn ,n 0. n Here, in Theorem 3.5, An = An (In - n An )-1 , and, therefore, (In - n An )-kn = (In + n An )kn . Theorem 3.6 ([203]). Assume that conditions (A) and (B) of the Theorem 3.1 hold and condition n A2 = O(1) n is fulfil led. Then the difference scheme Un (t + n ) - Un (t) = An Un (t), Un (0) = u0 , n n is stable, i.e., (In + n An )k as n ,kn ,n 0. Theorem 3.7 ([161]). Assume that conditions (A) and (B1 ) of Theorem 3.2 hold and condition n An 1/(M +2),n N (3.6)
n

(3.4)

(3.5)

Met ,t = kn n R+ , and gives an approximation of the solution of

problem (3.1), i.e., Un (t) (In + n An )kn u0 u(t) P -converges uniformly with respect to t = kn n [0,T ] n

is fulfil led. Then the difference scheme (3.5) is stable and gives an approximation of the solution of problem (3.1), i.e., Un (t) (In + n An )kn u0 u(t) discretely P -converge uniformly with respect to n t = kn n [0,T ] as u0 u0 , n , kn , n 0. n Let us introduce the following conditions: (B1 ) Stability. There are constants M and such that exp(tAn ) M e t , An exp(tAn ) M t e , t R+ . t

(B1 ) Stability. There are constants M , , and > 0 such that (In - n An )-k M e
kn

, kn An (In - n An )-k M e

kn

, 0 < n < ,n,k N.

Proposition 3.1 ([183]). Conditions (B1 ), (B1 ), and (B1 ) are equivalent. Theorem 3.8. Conditions (A) and (B1 ) are equivalent to condition (C1 ). 10


Theorem 3.9 ([164]). Let the assumptions of Theorem 3.7 and (3.4) be satisfied. Then tAn (In + n An )kn tA exp(tA) uniformly in t = kn n [0,T ]. (3.7)

Conversely, if (In + n An )kn exp(tA) uniformly in t = kn n [0,T ] and (3.7) is satisfied, then condition (C1 ) holds. Theorem 3.10 ([164]). Let condition (B1 ) hold. Then exp(tAn ) - (In - n An )-k If, moreover, the stability condition (3.6) holds, then exp(tAn ) - (In + n An )k
n n

c

n t e. t

c

n t e, t n t e An xn , t

(exp(tAn ) - (In + n An )kn )xn An (exp(tAn ) - (In + n An )kn )xn

cn et An xn , c t = kn n .

In the case of analytic C0 -semigroups for the forward scheme, as we saw, the stability condition n An < 1/(M +2) cannot b e improved even in Hilb ert spaces for self-adjoint op erators. In the case of almost p eriodic C0 -semigroups and the forward scheme for differential equations of first order in time (3.1), one obtains necessary and sufficient stability condition
n

An < 1 [163]. It was discovered that the stability condition

of the forward scheme like (3.5) for the p ositive C0 -semigroups also can b e written in the form n An < 1; see [168]. Stability of difference schemes under some sp ectral conditions were obtained in [26]. The stability of difference schemes for differential equations in Hilb ert spaces in the energy norm are investigated in [179, 180], where schemes with weights were also considered. Semidiscrete approximations are studied also in [180]. 3.2. Rational approximation. Let us denote by Pp (z ) an element of the set of all real p olynomials of Pp (z ) degree no greater than p and by p,q the set of all rational functions rp,q (z ) = and Pq (0) = 1. Then Pq (z ) a Pad´ (p, q )-approximation for e-z is defined as an element Rp,q (z ) p,q such that e |e-z - Rp,q (z )| = O(|z |p
+q +1

) as |z | 0.

It is well known that a Pad´ approximation for e-z exists, is unique and is represented by the formula e Rp,q (z ) = Pp,q (z )/Qp,q (z ), where
p

Pp,q (z ) =
j =0

(p + q - j )!p!(-z )j , Qp,q (z ) = (p + q )!j !(p - j )!

q

(p + q - j )!q !z j (p + q )!j !(q - j )!.
j =0

11


In [174, 175], details of the location of p oles and the order of convergence of rational approximations in different regions are given. Definition 3.3. A rational approximation rp,q (·) p,q for e-z is said to b e (a) A-acceptable if |rp,q (z )| < 1 for Re(z ) > 0; (b) A( )-acceptable if |rp,q (z )| < 1 for z ( ) = {z : - < arg(z ) < , z = 0}. It is well known that Rq,q (z ),Rq
-1,q

(z ), and Rq

-2,q

(z ) are A-acceptable. But for q 3 and p = q - 3,

the Pad´ functions are not A-acceptable. e Theorem 3.11 ([175]). For any q 2 and p 0, the Pad´ approximation of e-z has no poles in the e sector S
p,q -1

= z : | arg(z )| < cos

q-p-2 p+q

;

in particular, for p q p +4 al l poles lie in the left half-plane. Since r (·) p,q is an approximation of e-z , it is natural to construct the op erator-function r (n An )k which can b e considered as an approximation of exp(tAn ) for t = kn . For simplicity, we assume in this section that exp(tAn ) M, t R+ . Theorem 3.12 ([44]). Let condition (B) be satisfied. There is a constant C depending on r such that if r is A-acceptable, then r (n An )k CM k for n > 0,k N. Remark 3.1. The term k in Theorem 3.12 cannot b e removed in general; moreover, there are examples [55, 97], which show that the inequality r (n An )k c k, k N, holds. We say that r (·)
p,q

is accurate of order 1 d p + q if |e-z - r (z )| = O(|z |d+1 ) as |z | 0.

Theorem 3.13 ([44]). Let condition (B) be satisfied. Then there is a constant C depending on r such that, if r is A-acceptable and accurate of order d, then r (n An )k u0 - exp(tAn )u0 CM n n
d n

Ad+1 u0 for n > 0,k N,u0 D(Ad+1 ). n n n n

Theorem 3.14 ([44]). Let condition (B1 ) be satisfied. Then there is a constant C depending on r , such that if r is A-acceptable and accurate of order d, then r (n An )k u0 - exp(tAn )u0 CM n n 12
d n

Ad u0 for n > 0,k N,u0 D(Ad ). nn n n


Theorem 3.15 ([162, 185]). Let condition (B1 ) be satisfied. Then there is a constant C depending on r , such that if r is A-acceptable and accurate of order d with |r ()| < 1 or condition (3.6) is satisfied, then r (n An )k u0 - exp(tAn )u0 CM n n t
n d-



A u0 for n > 0, 0 d, t = kn ,k N. nn

In [54, 152, 154], the analogs of Theorems 3.13­3.15 were proved for multistep methods. Let us recall that constant M2 in condition (B1 ), which defines , 0 < < , by M2 sin < 1 [110] 2 is such that (In - An )-1 M for any (/2+ ). | - | (3.8)

Theorem 3.16 ([55, 150]). Let condition (B1 ) be satisfied. Then there is a constant C depending on r , such that if r is A( )-acceptable, accurate of order d, and (/2 - , /2] for from condition (3.8), then r (n An )k CM for n > 0,k N, and r (n An )k - exp(tAn ) - k exp(-
-b n - - akn (-An )-b ) CM (kn d + kn 1/b ), t = kn n ,

where = r () and a, b are some positive constants. It is p ossible to show [151] that
k j =1

r (

n,j

An ) is a stable approximation for exp(
n,j

k j =1 n,j

A) with

a variable stepsize, but under condition 0 < c n,i /

C < , i, j N.

3.3. Richardson's extrapolation method. Let us consider schemes (3.3) and (3.5) which have the
order of convergence O(n ) and denote Unn (kn ) = Un (t)u0 and U n (kn ) = U n (t)u0 ,t = kn n . The following n n n

approach to the limit is valid. Theorem 3.17 ([167]). Assume that condition (B) is satisfied. Then for V n (t) = 2U n (kn ) - U one has
2 V n (t) - un (t) n Met t2 A3 u0 , t = kn n . nn If, in addition, scheme (3.5) is stable, then for Vn (t) = 2Unn (kn ) -Unn (2kn ),t = kn n , 2 Vn (t) - un (t) n Met t2 A3 u0 , t = kn n . nn /2 n n /2 n

(2kn ),

Let us consider the Crank­Nicolson scheme ~ ~ ~ ~ Un (kn + n )+ Un (kn ) ~ Un (kn + n ) - Un (kn ) = An , Un (0) = In , k N0 , n 2 (3.9) 13


Theorem 3.18 ([167]). Assume that condition (B) is satisfied and that scheme (3.9) is stable. Then 4 ~ /2 1 ~ n (t) = Unn (2kn ) - Unn (kn ) satisfies 3 3
4 n (t) - un (t) cn et t2 A6 u0 , t = kn n . nn In general, we set Vnn (t) = Rp,q (n An )kn u0 , t = kn n . n

Theorem 3.19 ([167]). Assume that condition (B) is satisfied, p = q and the scheme which corresponds 1 22q /2 Vnn (t)+ 2q Vnn (t), to Vnn is stable. Then for n (t) = - 2q 2 -1 2 -1 n (t) - un (t) c
2q +2 t e n

t3/2 2q A n n

+3 0 un

+ t3

2q -3 n

A4q n

+2 0 un

, t = kn n .

Theorem 3.20 ([167]). Assume that condition (B1 ) is satisfied, p = q and n An const. Then for 1 22q /2 Vnn (t)+ 2q Vnn (t), 0 2q and n (t) = - 2q 2 -1 2 -1 n (t) - un (t) c
2q +2 n et 2q +2-



t

A u0 , t = kn n . nn

3.4. Lax-type equivalence theorems with orders. The Lax equivalence theorem on the convergence of the solution of the approximation problem to the solution of the given well-p osed Cauchy problem states that the stability of the method is necessary and sufficient for the convergence provided it is compatible. Recently, Lax's theorem with orders, which make it p ossible to consider "unstable" approximations, was obtained. Definition 3.4. C0 -semigroups exp(tAn ) and exp(tA) are said to b e compatible of order O((n )) on a linear manifold U E with resp ect to the semigroup exp(·A) if exp(tA)U D(A) and there is a constant C such that (An pn - pn A)exp(tA)x Cn (n )et |x|U for any x U , where |· | denotes the seminorm on U . Definition 3.5. C0 -semigroups exp(tAn ) is said to b e stable of order O(Mn en t ) if there are constants Mn and n such that exp(tAn ) Mn en t for any t R+ . The following is a slight modification of [47­50] and [66­68], which was proved in [164]. 14 (3.11) (3.10)


Theorem 3.21. Let a C0 -semigroup exp(·An ) be compatible of order O((n )) on a linear manifold U E with respect to a semigroup exp(·A), exp(tA)U U , and let | exp(tA)x|U M |x|U . The fol lowing assertions are equivalent: Cn (exp(tAn )pn - pn exp(tA)) x 2Mn en t K t(n ),x; E, U ; 2 Mx , x E, n t (ii) exp(tAn )pn - pn exp(tA) x Mn e Cn t(n )|x|U , t = kn n [0,T ],x U ; 2 (iii) exp(tAn ) Mn en t , (An pn - pn A)exp(tA)x Cn n (n )et |x|U for any x U ,t R+ , (i) where Mx is a constant depending only on x and K (t, x; E, U ) = inf
y U

x-y

E

+t|y |U

is Peetre functional.

Definition 3.6. A family of discrete semigroups {Un (kn n )} is said to b e compatible of order O((n )) on a linear manifold U E with resp ect to the semigroup exp(·A) if U = E and (Un (n )pn - pn exp(n A)) exp(tA)x Cn (n )|x|U for any x U . (3.12)

Theorem 3.22. Let exp(tAn )Un Un , let condition (B) hold, and let | exp(tAn )x|Un C