Printer Friendly

CONVERGENCE OF THE MULTIPLICATIVE SCHWARZ METHOD FOR SINGULARLY PERTURBED CONVECTION-DIFFUSION PROBLEMS DISCRETIZED ON A SHISHKIN MESH.

1. Introduction. It is well known that, due to the presence of boundary layers in the analytic solution, singularly perturbed convection-diffusion problems require special discretization techniques in order to guarantee the stability of a numerical method. A general overview can be found, e.g., in the survey article [22]. One widely accepted discretization technique in this context is given by upwind or central finite difference schemes on a Shishkin mesh as described, e.g., in [22, Section 5] or [6, 12, 14, 19]. In short, Shishkin meshes are formed by an overlapping union of piecewise uniform meshes, with their respective sizes and mesh transition (or interface) points adapted to the expected width of the layers in the solution.

The matrix in a linear algebraic system obtained from a Shishkin mesh discretization of a singularly perturbed convection-diffusion equation is nonsymmetric and often highly nonnormal and ill-conditioned. Standard iterative solvers like the (unpreconditioned) GMRES method converge very slowly when applied to such a system; see Figures 2.2-2.4 in this paper for examples. On the other hand, the Shishkin mesh discretization naturally leads to a decomposition of the domain, which suggests to solve the discretized problem by the multiplicative Schwarz method. This is the approach we explore in this paper for one-dimensional model problems.

We consider both upwind and central difference schemes on the Shishkin mesh. Using the algebraic structure of the iteration matrices, we derive bounds on the infinity norm of the error that are valid from the first step of the corresponding multiplicative Schwarz iteration. Thus, unlike asymptotic convergence results based on bounding the spectral radius of the iteration matrix, our results apply to the transient rather than the asymptotic behavior. For the upwind scheme we prove rapid convergence of the multiplicative Schwarz iteration for all relevant parameters in the problem. The analysis of the central difference scheme is more complicated, since some of the submatrices that occur in this case are not only nonsymmetric but also fail to be M-matrices. This reminds of the analysis in [1], which showed that in this case the difference scheme itself does not satisfy a discrete maximum principle. Nevertheless, we can prove the convergence of the multiplicative Schwarz method for problems discretized by central differences on a Shishkin mesh under the assumption that the number of discretization points in each of the local subdomains is even. If this assumption is not satisfied, then the method may diverge, which we also explain in our analysis.

The multiplicative Schwarz method as a solution technique, which we analyze here and which is often called the alternating Schwarz method (see [8] for a historical survey), is for the most part used as a preconditioner for Krylov subspace methods such as CG or GMRES. Many of the convergence results for multiplicative Schwarz have been presented in that context; see, e.g., the treatment in the books [5, 24] and many references therein. When the method is considered from an algebraic point of view, as we do here, it is commonly treated as a solution method; see, e.g., [2]. One of our goals in this paper is to bring an understanding on why this solution technique is so effective for solving problems arising from the Shishkin mesh discretizations. Moreover, the convergence bounds provided in this paper shed light on an apparent contradiction: if the continuous problem becomes more difficult (a smaller diffusion coefficient is chosen), then the convergence of the multiplicative Schwarz method for the discretized problem becomes faster.

Several authors have previously applied the alternating (or multiplicative) Schwarz method to the continuous problem based on the partitioning of the domain into overlapping subdomains and subsequently discretized by introducing uniform meshes on each subdomain; see, e.g., [6, 7, 15, 16, 17, 18, 19]. However, as clearly explained in [18], significant numerical problems including very slow convergence and accumulation of errors (up to the point of non-convergence of the numerical solution) can occur when layer-resolving mesh transition points are used in this setup. These problems are avoided in our approach since we first discretize and then apply the multiplicative Schwarz method to the linear algebraic system. To the best of our knowledge, this approach has not been studied in the literature so far.

The paper is organized as follows. Section 2 specifies the model problem and its Shishkin mesh discretization. In Section 3 we describe the multiplicative Schwarz method for the discretized problem. In Section 4 we present the convergence analysis of the multiplicative Schwarz method, first for the upwind scheme and then for the central difference scheme. Numerical examples are shown in Section 5, and a concluding discussion, which also puts our results into a broader context, is given in Section 6.

2. Model problem and its Shishkin mesh discretization. We consider a one-dimensional convection-diffusion model problem with constant coefficients and Dirichlet boundary conditions

(2.1) -[??]u"(x) + [alpha]u'(x) + [beta]u(x) = f(x) in (0,1), u(0) = [u.sub.0], u(1) = [u.sub.1],

where [alpha] [much greater than] [??] > 0 and [beta] [greater than or equal to] 0. We assume that the parameters of the problem, i.e., [??], [alpha], [beta], f(x), [u.sub.0], [u.sub.1], are chosen so that the solution u(x) has one boundary layer at x = 1.

A common approach for discretizing such a problem is to resolve the boundary layer using a finer mesh close to x = 1. Here we will focus on the Shishkin mesh discretization. This technique has been described in detail, for example, in the book [19] or in the survey article [22, Section 5]. We therefore only state the facts that are relevant for our analysis.

Suppose that an even integer N [greater than or equal to] 4 defining the number of intervals constituting the Shishkin mesh is given and suppose that

(2.2) [TAU] = 2/[alpha] ln N [less than or equal to] - 1/2.

The inequality in (2.2) means that

(2.3) [??] [less than or equal to] [alpha]/4 ln N,

which is a natural assumption since [alpha] [much greater than] [??] and the number of mesh points usually is not exponentially large relative to [??]. The mesh transition point 1 - [TAU] then will be close to x = 1 and the boundary layer will be contained in the (small) interval [1 - [TAU], 1].

The idea of the Shishkin mesh discretization of the interval [0,1] is to use the same number of equidistantly distributed mesh points in each of the subintervals [0,1 - [TAU]] and [1 - [TAU], 1]. Thus, if we denote

n [equivalent to] N/2, H [equivalent to] 1-[TAU]/n, h = [TAU]/n,

then the N + 1 mesh points of the Shishkin mesh are given by

[x.sub.i] = iH, i = 0,..., n, [x.sub.i] = 1 - (N - i)h, i = n + 1,..., N.

Here [x.sub.0] = 0 and [x.sub.N] = 1, so that the mesh consists of N - 1 interior mesh points, where the mesh point [x.sub.n] is exactly at the transition point 1 - [TAU]. The ratio between the mesh sizes in the two subdomains is

h/H = [TAU]/1 - [TAU] = [TAU] + O([[TAU].sup.2]),

which is usually much less than 1.

An illustration of a Shishkin mesh and a plot of the (explicitly known) analytic solution of the problem (2.1) with [??] = 0.01, [alpha] = 1, [beta] = 0, f(x) = 1, and [u.sub.0] = [u.sub.1] = 0 are shown in Figure 2.1; cf. [22, Example 3.1]. Choosing, for example, N = 48 gives the mesh transition point 1 - [TAU] = 0.9226.

We consider two different finite difference schemes on the Shishkin mesh: upwind and central differences. Using the standard difference operators (see, e.g., [22, Section 4]), both schemes yield a linear algebraic system [Au.sup.N] = [f.sup.N] with the tridiagonal and nonsymmetric matrix

(2.4) [mathematical expression not reproducible]

For the upwind scheme, the entries of A are given by

(2.5) [mathematical expression not reproducible]

and for the central difference scheme by

(2.6) [mathematical expression not reproducible]

If [mathematical expression not reproducible] is the exact algebraic solution and u(x) is the solution of (2.1), then there exist constants [c.sub.1], [c.sub.2] > 0 such that

[mathematical expression not reproducible]

for the upwind scheme and

[mathematical expression not reproducible]

for the central difference scheme. Thus, the convergence of both schemes is [??]-uniform, and the central difference scheme is more accurate than the upwind scheme. As pointed out by Stynes [22, p. 470], the convergence proof for the central differences (originally due to Andreyev and Kopteva [1]) is complicated since the scheme does not satisfy a discrete maximum principle. We meet similar complications in our analysis in Section 4.2 below.

Both schemes lead to highly ill-conditioned matrices A. The main reason is the large difference between the mesh sizes H and h, which implies large differences between the moduli of the nonzero entries of A corresponding to each subdomain. Thus, A is poorly scaled. As shown by Roos [21], a simple diagonal scaling reduces the order of the condition number for the matrix from the upwind scheme from O([e.sup.-1][(N/ ln N).sup.2]) to O([N.sup.2]/ ln N). Although not shown by Roos, an analogous diagonal scaling appears to work well also for the central difference scheme; see Section 4.3 for the exact form of the scaling matrices. The first row in the following table provides a numerical illustration for [member of] = [10.sup.-8], [alpha] = 1, [beta] = 0 in (2.1), and N = 198.
                   upwind                upwind

matrix cond.       4.0500 x [10.sup.10]  2.9569 x [10.sup.3]
eigenvector cond.  1.5143 x [10.sup.17]  1.2297 x [10.sup.19]

                   scaled central        central scaled

matrix cond.       6.2323 x [10.sup.10]  2.9514 x [10.sup.3]
eigenvector cond.  4.1070 x [10.sup.3]   1.8682 x [10.sup.2]


The second row of the table displays the condition numbers of the eigenvector matrices from the decomposition A = [VDV.sup.-1] computed by [V,D]=eig(A) in MATLAB. We observe that the upwind scheme yields matrices with very ill-conditioned eigenvectors, i.e., highly nonnormal matrices. Apparently, the eigenvector conditioning is not much affected by the diagonal scaling.

As mentioned in the introduction, linear algebraic systems resulting from discretizations of convection-dominated convection-diffusion problems represent a challenge for iterative solvers. Figures 2.2-2.4 illustrate that this also holds for the Shishkin mesh discretization of the model problem (2.1). These figures show the relative true residual norms of the (unpreconditioned) GMRES method with zero initial vector applied to [Au.sup.N] = [f.sup.N] from the Shishkin mesh discretization of (2.1) with [alpha] = 1, [beta] = 0, f(x) = 1, [u.sub.0] = [u.sub.1] = 0, N = 198, and different values of [member of]. The GMRES convergence is virtually the same for both discretizations (upwind and central differences). Neither the scaling nor the eigenvector conditioning appears to have a significant effect on the performance of the iterative solver.

3. The multiplicative Schwarz method. Any Shishkin mesh discretization naturally leads to a decomposition of the given domain into overlapping subdomains. In our model problem the domain is the interval [0,1], and the overlapping subdomains are the intervals [0,1 - [TAU] + h] and [1 - [TAU] - H, 1]. The width of the overlap is H + h = 2/N, and the mesh transition point [x.sub.n] = 1 - [TAU] is the only mesh point in the overlap. We will now describe the multiplicative Schwarz method for solving the linear algebraic system [Au.sup.N] = [f.sup.N].

In short, the method uses restriction operators for constructing a multiplicative iteration matrix in which each factor corresponds to a local solve in one of the subdomains. In the notation established above, the restriction operators can be written as

[R.sub.1] [EQUIVALENT TO] [[I.sub.n] 0] and [R.sub.2] = [0 [I.sub.n]],

both of size n x (N - 1). The restrictions of the matrix A in (2.4) to the two subdomains are given by the two n x n matrices

[mathematical expression not reproducible] and [mathematical expression not reproducible]

where m [equivalent to] n - 1 and [e.sub.1], [e.sub.m] [member of] [R.sup.m]. In the following, the unit basis vectors [e.sub.j] are always considered to be of appropriate length, which for simplicity is sometimes not explicitly stated. Note that [A.sub.H],[A.sub.h] [member of] [R.sup.mxm] are tridiagonal Toeplitz matrices. The matrices corresponding to the solves on the two domains then are given by

(3.1) [mathematical expression not reproducible]

It is easy to see that [mathematical expression not reproducible], i.e., that these matrices are projections. Note also that since Pi is not symmetric, we have for the 2-norm, that [||I - [P.sub.i]||.sub.2] = [||[P.sub.i]||.sub.2] > 1; see, e.g., [23].

The multiplicative Schwarz method starting with the initial vector [x.sup.(0)] [member of] [R.sup.N-1] is defined by

(3.2) [x.sup.(k+1)] =T[x.sup.(k)]+v, k = 0, 1, 2 ,...,

where T = (I - [P.sub.2])(I - [P.sub.1]) or T = (I - [P.sub.1])(I - [P.sub.2]), and the vector v [member of] [R.sup.N-1] is defined to make the method consistent. For example, for the iteration matrix T = (I - [P.sub.2])(I - [P.sub.1]) the consistency condition [u.sup.N] = [Tu.sup.N] + v yields

v = (I - T)[u.sup.N] = ([P.sub.1] + [P.sub.2] - [P.sub.2][P.sub.1])[u.sup.N],

which is (easily) computable since

[mathematical expression not reproducible], i = 1,2.

The error of the multiplicative Schwarz iteration (3.2) is given by

[e.sup.(k + 1) = [u.sup.N] - [x.sup.(k + 1) = (T[u.sup.N] + v) - (T[x.sup.(k)] + v) = T[e.sup.(k)], k = 0,1, 2,...,

and hence [e.sup.(k+1)] = [T.sup.k+1][e.sup.(0)] by induction. For any consistent norm || * ||, we therefore have

(3.3) ||[e.sup.(k+1)]|| [less than or equal to] ||[T.sup.k+1]|| ||[e.sup.(0)]|| [less than or equal to] [||T||.sup.k+1] ||[e.sup.(0)]||.

Our main goal in the following is the derivation of quantitative convergence bounds, where we consider both T = (I - [P.sub.2])(I - [P.sub.1]) and T = (I - [P.sub.1])(I - [P.sub.2]).

We point out that the analysis of the multiplicative Schwarz method in the following sections uses the unscaled linear algebraic system with A as in (2.4) having the entries (2.5) or (2.6). In Section 4.3 we explain why this analysis also applies to suitably scaled linear algebraic systems and in particular to the scaling suggested by Roos in [21].

4. Convergence bounds for the multiplicative Schwarz method. We start with a closer look at the structure of the iteration matrix T. Note that the matrices [P.sub.i] from (3.1) satisfy

[mathematical expression not reproducible]

and

[mathematical expression not reproducible]

where [e.sub.1], [e.sub.n] [member of] [R.sup.n]. We now denote

(4.1) [mathematical expression not reproducible]

where [mathematical expression not reproducible] [member of] [R.sup.m] for i = 1,2, and [[pi].sup.(1)] and [[pi].sup.(2)] are scalars. Then

[mathematical expression not reproducible]

which gives

[mathematical expression not reproducible]

and

[mathematical expression not reproducible]

where [e.sub.n+1], [e.sub.n-1] [member of] [R.sup.N-1]. Thus, both iteration matrices have rank one, and we can apply the following observation.

PROPOSITION 4.1. Let T be a square matrix of rank one, i.e., T = [uv.sup.T] for some vectors u, v. Then [T.sup.2] = [rho]T, with [rho] = [v.sup.T]u, and consequently [T.sup.k+1] = [[rho].sup.k]T for k [greater than or equal to] 0.

Proof. The proof follows by direct computation. []

COROLLARY 4.2. In the notation established above, let T = (I - [P.sub.2])(I - [P.sub.1]) or T = (I - [P.sub.1])(I - [P.sub.2]). Then for any k [greater than or equal to] 0 we have

(4.4) [mathematical expression not reproducible]

Proof. Applying Proposition 4.1 to either (4.2) or (4.3) produces the desired result. []

Equation (4.4) shows, in particular, that ||[T.sup.k+1]|| = [|[rho]|.sup.k]||T|| holds for any matrix norm || * ||. In order to obtain a convergence bound for the multiplicative Schwarz method we will bound |[rho]| and [||T||.sub.[infinity]]. The following lemma will be essential in our derivations.

LEMMA 4.3. In the notation established above,

[mathematical expression not reproducible]

Proof From (4.1) we know that [p.sup.(1)], [p.sup.(2)], [[pi].sup.(1)], and [[pi].sup.(2)] solve the systems

[mathematical expression not reproducible]

Hence the expressions for [p.sup.(1)], [p.sup.(2)], [[pi].sup.(1)], and [[pi].sup.(2)] can be obtained using Schur complements. []

Combining (4.4) and Lemma 4.3 gives

(4.5) [mathematical expression not reproducible]

In order to bound |[rho]| we thus need to bound certain entries of inverses of the tridiagonal Toeplitz matrices [A.sub.H] and [A.sub.h]. In the following lemma we show that this is straightforward in the case of an M-matrix. As we will see later in Lemma 4.5 and Lemma 4.8, the matrix [A.sub.h] is an M-matrix for both the upwind and the central difference scheme. However, while [A.sub.H] is an M-matrix for the upwind scheme, it is not an M-matrix in the most common situation for the central difference scheme. We then have to use a different technique for bounding the entry [mathematical expression not reproducible]; see Section 4.2.

Recall that a nonsingular matrix B = [[b.sub.i,j]] is called an M-matrix when [b.sub.i,i] > 0 for all i, [b.sub.i,j] [less than or equal to] 0 for alli [not equal to] j, and [B.sup.-1] [greater than or equal to] 0 (elementwise).

LEMMA 4.4. Let B be an i x i tridiagonal Toeplitz matrix,

[mathematical expression not reproducible]

with a > 0 and b, c < 0. Moreover, let B be diagonally dominant, i.e., a [greater than or equal to] |b| + |c|. Then B is an M-matrix with [B.sup.-1] > 0 (elementwise),

(4.6) [mathematical expression not reproducible]

and the entries of [B.sup.-1] decay along the columns away from the diagonal. In particular,

[([B.sup.-1]).sub.1,1] > [([B.sup.-1]).sub.i1] for 1 < i [less than or equal to] l,

[([B.sup.-1]).sub.l,l] > [([B.sup.-1]).sub.i,l]. for 1 [less than or equal to] i < l.

Proof The matrix B is an M-matrix since its entries satisfy the sign condition and B is irreducibly diagonally dominant; see, e.g., [4, Theorem 6.2.3, Condition M35] or [10, Criterion 4.3.10]. The elementwise nonnegativity of the inverse, [B.sup.-1] > 0, follows since the M-matrix B is irreducible; see, e.g., [4, Theorem 6.2.7] or [10, Theorem 4.3.11].

Since B is a tridiagonal Toeplitz matrix, its (1,1) and (I, I) minors are equal. Therefore, the classical formula [B.sup.-1] = [(det(B)).sup.-1]adj(B) implies that ([B.sup.-1])1 1 = [([B.sup.-1]).sub.l,l]. Moreover, since a [greater than or equal to] |b| + |c|, we can apply [20, Lemma 2.1, equation (2.8)] to obtain

[mathematical expression not reproducible]

Finally, the bounds on the entries of [B.sup.-1] are special cases of [20, Theorem 3.11], where it was shown that

[mathematical expression not reproducible] for i [greater than or equal to] j and [mathematical expression not reproducible] for i [less than or equal to] j,

with some [TAU], [omega] [member of] (0,1). (They can be expressed explicitly using the entries of B.) []

In the next two subsections we separately treat the upwind and the central difference schemes.

4.1. Bounds for the upwind scheme. Using Lemma 4.4 we can prove the following result for the upwind scheme.

LEMMA 4.5. For the upwind scheme both matrices [A.sub.H] and [A.sub.h] satisfy the assumptions of Lemma 4.4, and the related quantities from Lemma 4.3 satisfy

[mathematical expression not reproducible]

Proof. It is easy to see from (2.5) that both matrices [A.sub.H] and [A.sub.h] resulting from the upwind scheme satisfy the assumptions of Lemma 4.4. Thus, from (4.6) we have

[mathematical expression not reproducible] and [mathematical expression not reproducible]

Moreover, a > 0 and b, c < 0 as well as a + b + c = [beta] [greater than or equal to] 0, so that

[mathematical expression not reproducible]

Using these inequalities and the fact that the entries of [mathematical expression not reproducible] decay along a column away from the diagonal yields

[mathematical expression not reproducible]

Using the decay of the entries of [mathematical expression not reproducible] and

[mathematical expression not reproducible]

which follows from (4.6), as well as the definitions of the entries in (2.5), we obtain

[mathematical expression not reproducible] []

We can now state our main result of this subsection.

THEOREM 4.6. For the upwind scheme we have

(4.7) [mathematical expression not reproducible]

and

[mathematical expression not reproducible]

Thus, the error of the multiplicative Schwarz method (3.2) satisfies

[mathematical expression not reproducible]

Proof. For the bound on |[rho]| we apply Lemma 4.5 to the expression [mathematical expression not reproducible] from (4.4). From (4.2) and (4.3) we respectively see that

[mathematical expression not reproducible] and [mathematical expression not reproducible]

Thus, using Lemma 4.5,

[mathematical expression not reproducible]

Using these bounds and (4.4) in the first inequality in (3.3) yields the convergence bound for the multiplicative Schwarz method. []

Suppose that [member of] < [alpha]H, which is a reasonable assumption in our context. Then

[mathematical expression not reproducible]

This expression shows that the convergence of the multiplicative Schwarz method will be very rapid in case of the upwind scheme and a strong convection-dominance. Numerical examples are shown in Section 5.

Note that since 2/N = H + h [less than or equal to] 2H, we have 1/N [less than or equal to] H and hence

(4.8) [mathematical expression not reproducible]

Using the expression on the right-hand of (4.8) in Theorem 4.6 would give (slightly) weaker convergence bounds for the multiplicative Schwarz method. However, the right-hand side of (4.8) represents a more convenient bound on the convergence factor which directly depends on the parameters [member of], [alpha], and N of our problem.

4.2. Bounds for the central difference scheme. We will now consider the discretization by the central difference scheme, i.e., the matrix A with the entries given by (2.6). It turns out that the analysis for this scheme is more complicated than for the upwind scheme since, as mentioned earlier, the matrix [A.sub.H] need not be an M-matrix. Moreover, as we will see below, the multiplicative Schwarz method may not converge when the parameter m is odd.

The following result about the entries a, b, and c of A will be frequently used below. LEMMA 4.7. For the central difference scheme we have

(4.9) a > 0, c, b < 0, - (c + b) = |c| + |b| = a - [beta] [less than or equal to] a, and [mathematical expression not reproducible] < 1.

Proof. The inequalities a > 0 and c < 0 are obvious from (2.6). From (2.2)-(2.3) and N [greater than or equal to] 4 we have that

(4.10) [alpha]h = 2[member of] 2 ln N/N < 2[member of],

and thus

b = [alpha]h - 2[member of]/h(H + h) < 0.

Moreover, -(c + b) = a - [beta] [less than or equal to] a, which yields

[mathematical expression not reproducible] []

We next consider the matrix [A.sub.h] from the central difference scheme.

LEMMA 4.8. The matrix [A.sub.h] from the central difference scheme satisfies the assumptions of Lemma 4.4, and for the corresponding quantities from Lemma 4.3 we have

[mathematical expression not reproducible]

Proof. The inequalities [a.sub.h] > 0 and [c.sub.h] < 0 are obvious from (2.6) and using (4.10) we get

[mathematical expression not reproducible]

Since also

[mathematical expression not reproducible]

the matrix [A.sub.h] satisfies the assumptions of Lemma 4.4. Thus, in particular, [mathematical expression not reproducible]. Using also (4.9) gives

[mathematical expression not reproducible]

Finally, since the entries of [mathematical expression not reproducible] decay along a column away from the diagonal, we obtain [mathematical expression not reproducible]. []

We now concentrate on bounding the quantities from Lemma 4.3 related to the matrix [A.sub.H] for the central difference scheme. We will distinguish the three cases [alpha]H < 2[member of], [alpha]H = 2.sub.[??], and [alpha]H > 2[member of] or, equivalently, the cases that the entry

[mathematical expression not reproducible]

of [A.sub.H] is negative, zero, or positive. It is clear from (4.5) that the sign of [b.sub.H] is important for the value |[rho]|.

A simple computation shows that [b.sub.H] [less than or equal to] 0 if and only if

[??] [greater than or equal to] [alpha]/N + 2 ln N

If [??] [much less than] [alpha] [approximately equal to] 1, then this condition means that [??](N + 2 ln N) = 0(1), which is an unrealistic assumption on the discretization parameter N. Nevertheless, we include the case [b.sub.H] [less than or equal to] 0 for completeness.

We first assume that

(4.11) [alpha]H < 2[member of],

which means that [b.sub.H] < 0.

LEMMA 4.9. If [alpha]H < 2[member of], then the matrix [A.sub.H] from the central difference scheme satisfies the assumptions of Lemma 4.4, and we have

[mathematical expression not reproducible]

Proof The inequalities [a.sub.H] > 0 and [c.sub.H] < 0 are obvious from (2.6), and [b.sub.H] < 0 holds because of (4.11). Moreover,

|[c.sub.H]| + |[b.sub.H]| = [alpha]/2H + [member of]/[H.sup.2] +[member of]/[H.sup.2] - [alpha]/2H = 2[member of]/[H.sup.2] [less than or equal to] [a.sub.H],

so that the matrix [A.sub.H] satisfies the assumptions of Lemma 4.4. In particular,

[mathematical expression not reproducible]

Using (4.9) we obtain

[mathematical expression not reproducible]

Moreover, using that the entries of [mathematical expression not reproducible] decay along a column away from the diagonal as well as

[mathematical expression not reproducible]

which follows from (4.6), we see that

[mathematical expression not reproducible]

where we used h < H and h + H = 2/N. []

Next we consider the (very) special case

(4.12) [alpha]H = 2[member of],

which means that [b.sub.H] = 0.

LEMMA 4.10. If [alpha]H = 2[member of], then the matrix [A.sub.H] from the central difference scheme is nonsingular, and we have |[[pi].sup.(1)]| < 1 and [p.sup.(1)] = 0.

Proof. If [b.sub.H] = 0, then [A.sub.H] is lower triangular and nonsingular since [a.sub.H] > 0. Using the definitions of [p.sup.(1)] and [[pi].sup.(1)] from Lemma 4.3 and the last inequality in (4.9) we obtain

[mathematical expression not reproducible] []

The third case we consider is

(4.13) [alpha]H > 2[member of],

which means that [b.sub.H] > 0. This is the most common situation from a practical point of view, but now AH does not satisfy the assumptions of Lemma 4.4. We therefore need a different approach for bounding the quantities from Lemma 4.3 and in particular the entries of the vector [mathematical expression not reproducible]. Note that because of (4.13) we have

[mathematical expression not reproducible]

LEMMA 4.11. If [alpha]H > 2[member of], then the matrix [A.sub.H] from the central difference scheme is a nonsingular tridiagonal Toeplitz matrix with the entries [a.sub.H],[b.sub.H] > 0, and [c.sub.H] < 0. Moreover,

(4.14) [mathematical expression not reproducible]

where the second inequality in (4.14) is an equality if [beta] = 0. If m = N/2 - 1 is even, then

(4.15) [mathematical expression not reproducible]

and

(4.16) [mathematical expression not reproducible]

Proof The inequalities [a.sub.H] > 0 and [c.sub.H] < 0 are obvious from (2.6), and [b.sub.H] > 0 holds because of (4.13).

In order to see that [A.sub.H] is nonsingular, note that eigenvalues of the tridiagonal Toeplitz matrix [A.sub.H] are given by

[mathematical expression not reproducible]

Since [b.sub.H][c.sub.H] < 0, the number [mathematical expression not reproducible] is purely imaginary, and hence all eigenvalues are nonzero.

Adapting [25, Theorem 2] to our notation (and formulating this result in terms of columns instead of rows) shows that the entries of the vector [mathematical expression not reproducible] can be written as

[mathematical expression not reproducible]

where

(4.17) [[theta].sub.i] = [a.sub.H][[theta].sub.i-1] - [b.sub.H][c.sub.H][[theta].sub.i-2], [[theta].sub.0] = 1, [[theta].sub.1] = [a.sub.H].

Since [b.sub.H][c.sub.H] < 0 and [a.sub.H] > 0, we have [[theta].sub.i] > 0 for all i [greater than or equal to] 0 and [[xi].sub.i] [not equal to] 0. Since [b.sub.H] > 0, [[xi].sub.i] changes sign like [(-1).sup.m-i] , and [[xi].sub.m] > 0. Consequently, the first inequality in (4.14) holds.

If we define the sequence of positive numbers

[mathematical expression not reproducible]

then

(4.18) [mathematical expression not reproducible]

We will prove by induction that

(4.19) [mathematical expression not reproducible]

for all i [greater than or equal to] 1, with equality if [beta] = 0. For i = 1 we have

[mathematical expression not reproducible]

with equality if [beta] = 0. Using the recurrence (4.17), the inequality [a.sub.H] [greater than or equal to] -([c.sub.H] + [b.sub.H]), which is an equality if [beta] = 0, and the induction hypothesis, we obtain

[mathematical expression not reproducible]

again with equality if [beta] = 0.

Combining (4.18) and (4.19) yields

(4.20) [mathematical expression not reproducible]

showing the second inequality in (4.14), which is an equality if [beta] = 0.

Now let m be even. Using (4.19) we obtain

(4.21) [mathematical expression not reproducible]

which contains the first inequality in (4.16). Using (4.20) and (4.21) we obtain

[mathematical expression not reproducible]

which shows (4.15). Let us write

[mathematical expression not reproducible]

Using (4.13) we have 0 < v < 1, and by induction it can be easily shown that the inequality 1 - [(1-v).sup.m] < mv holds for every integer m [greater than or equal to] 2. Thus,

[mathematical expression not reproducible]

which proves the second inequality in (4.16). []

Using Lemma 4.11 and the assumption that m is even, we can bound the quantities from Lemma 4.3 related to the matrix AH from the central difference scheme as follows.

LEMMA 4.12. If (4.13) holds and ifm = N/2 - 1 is even, then

[mathematical expression not reproducible]

(Proof. From (4.9) we know that c < 0, and from Lemma 4.11 we know that [b.sub.H] > 0 and [mathematical expression not reproducible]. Therefore,

[mathematical expression not reproducible]

where we have used (4.9). Thus, using also (4.16), we obtain

[mathematical expression not reproducible]

Finally, (4.15) implies that [mathematical expression not reproducible] []

We can now formulate an analogue of Theorem 4.6 for the central difference scheme. THEOREM 4.13. For the central difference scheme we have

(4.22) [mathematical expression not reproducible]

If [alpha] H [less than or equal to] 2[member of], we have

[||(I - [P.sub.2])(I - [P.sub.1])||.sub.[infinity]] [less than or equal to] 1, ||(I - [P.sub.1])(I - [P.sub.2])||.sub.[INFINITY]] [less than or equal to] 1,

and if [alpha]H > 2[member of], we have

[||(I - [P.sub.2])(I - [P.sub.1])||.sub.[infinity]] < 2, [||(I - [P.sub.1])(I - [P.sub.2])||.sub.[INFINITY]] < 2.

Thus, the error of the multiplicative Schwarz method (3.2) for both iteration matrices satisfies

[mathematical expression not reproducible]

Proof. From (4.4) we know that [mathematical expression not reproducible], and hence the bounds on |[rho]| follow from |[mathematical expression not reproducible]| [less than or equal to] 1 (Lemma 4.8), and Lemmas 4.9-4.10 for the case [alpha]H [less than or equal to] 2[member of], as well as Lemma 4.12 for the case [alpha]H > 2[member of].

For the first iteration matrix we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE]

and for the second iteration matrix we have

[mathematical expression not reproducible]

The bounds on these matrices now follow from the Lemmas 4.8, 4.9, 4.10, 4.12, and the error bound for the multiplicative Schwarz method follows from (3.3) and (4.4). []

As in the discussion of Theorem 4.6 we could use 1/N [less than or equal to] H and m = N/2 - 1, and thus obtain

[mathematical expression not reproducible]

where the right-hand side again represents a bound on the convergence factor that directly depends of the parameters of our problem.

Because of the factor 2m [approximately equal to] N, the error bound for the central differences discretization can be significantly larger than for the upwind scheme. Thus, we expect that the multiplicative Schwarz method for the central differences discretization converges slower than for the upwind scheme, at least when [alpha]H > 2[member of]. An example with [member of] = [10.sup.-4] and N = 198, leading to |[rho]| = 8.3 x [10.sup.-1] and a very slow convergence of the multiplicative Schwarz method is shown in Section 5. In this case, the bound (4.22) is even greater than one. It should be noted, however, that in a strongly convection-dominated case the situation [member of][N.sup.2] = 0(1) is rather unrealistic.

Finally, let us discuss the situation when (4.13) holds, so that -1 < [b.sub.H]/[c2H] < 0 but m is odd. In this case the multiplicative Schwarz method does not converge for all parameter choices, and we will now give an intuitive explanation for this fact. For simplicity, let [beta] = 0. Then (4.19) yields

[mathematical expression not reproducible]

The essential inequality in (4.21) then fails to hold, and we may have [mathematical expression not reproducible] > 1. Using the exact expression for [rho] in (4.5), it is then easy to find parameters for which |[rho]| > 1, and for which the multiplicative Schwarz method indeed diverges. Note that even if m is odd, it holds for sufficiently large values of m that |[rho]| < 1, and the multiplicative Schwarz method converges to the discrete solution. However, in this case we cannot expect the convergence to be as fast as in the case of even values of m.

These problems with odd m correspond to the situation when equation (2.1) is discretized using central differences on a uniform mesh. Consider, for example, the discrete solution of the problem (2.1) with [alpha] = 1, [beta] = 0, f(x) = 1, and [u.sub.0] = [u.sub.1] = 0, which can be found in [22, Section 4]. If the number of interior points of the uniform mesh is even, then the discrete solution oscillates but with an amplitude bounded by one, so that some important information about the analytic solution is still preserved in the discrete solution. If the number of inner points is odd, the discrete solution is highly oscillating (cf. [22, Figure 4.1]), and therefore it does not provide much useful information about the analytic solution.

In our case of the Shishkin mesh, the multiplicative Schwarz method solves discrete problems on the coarse mesh and the fine mesh in an alternating way, and it combines the solutions of the two subproblems. If m is odd and the discrete solution on the coarse mesh is highly oscillating, then this solution is essentially useless, and the multiplicative Schwarz may fail to improve the approximation to the discrete solution.

4.3. Remarks on diagonally scaled linear algebraic systems. As mentioned in Section 2, the large difference between the mesh sizes H and h leads to highly ill-conditioned matrices A, both for the upwind and the central difference scheme. As shown by Roos [21] (for the upwind scheme), the ill-conditioning can be avoided by a simple diagonal scaling; cf. the numerical example in Section 2. In our notation, the linear algebraic system [Au.sup.N] = [f.sup.N] is multiplied from the left by the diagonal matrix

(4.23) [mathematical expression not reproducible]

where for the upwind scheme we choose

[d.sub.H] = H/[alpha], d = hH/2[member of], [d.sub.h] = [h.sup.2]/[member of],

and for the central difference scheme we choose

[mathematical expression not reproducible]

We will now explain the effect of a diagonal scaling with a matrix D as in (4.23) on our convergence analysis of the multiplicative Schwarz method.

Multiplying A from the left with D preserves the Toeplitz structure of the matrix as well as the M-matrix property of the submatrices (if it holds for the unscaled matrix). The derivations of all bounds in Sections 4.1 and 4.2 depend on these properties and on ratios between elements in the same row such as |b/a| and |[b.sub.H]/[c.sub.H]|; see in particular Lemma 4.5 for the upwind and Lemma 4.11 for the central difference scheme. The ratios, however, are invariant under any diagonal scaling of the form (4.23). Consequently, all convergence bounds in Theorems 4.6 and 4.13 hold for the multiplicative Schwarz method applied to DA[u.sup.N] = D[f.sup.N] for a diagonal matrix D as in (4.23) with any positive diagonal entries [d.sub.H], d, and [d.sub.h].

Note that, using a convenient scaling, one can also see the structure of the (scaled) matrices [A.sub.H] and [A.sub.h]. In particular, let [beta] = 0 and [member of] [much less than] [alpha]H. Then there is a scaling such that the scaled matrix [A.sub.h] is close to tridiag(-1, 2, -1). Another scaling can be found such that the scaled [A.sub.H] is close to tridiag( -1,1,0) for the upwind scheme and close to tridiag( -1,0,1) for the central difference scheme. The matrix (1/[mathematical expression not reproducible])tridiag(-1,0,1) [member of] [R.sup.m x m] is orthogonal when m is even, but it is singular when m is odd. This gives another intuitive explanation for the problems occurring when an odd value of m is chosen in the central difference scheme (also see our discussion of this point above).

In our experiments, the diagonal scaling had virtually no effect on the actual convergence of the Schwarz method (similar to the GMRES method; see Figures 2.2-2.4). In the following section we therefore present only results for the unscaled systems with A as in (2.4)-(2.6).

5. Numerical examples. We now illustrate the convergence behavior of the multiplicative Schwarz method applied to the Shishkin mesh discretization of the problem (2.1) with

[alpha] = 1, [beta] = 0, f(x) = 1, [u.sub.0] = [u.sub.1] = 0.

The analytic solution of this problem with e = 0.01 is shown in Figure 2.1.

We first consider N = 198, so that m = N/2 - 1 = 98 is even. Recall that the (unpreconditioned) GMRES method converges very slowly for both types of discretizations (upwind and central differences); see Figures 2.2-2.4.

For our experiments we computed [u.sup.N] = [A.sup.-1] [f.sup.N] using the backslash operator in MAT-LAB. (Applying iterative refinement in order to improve the numerical solution obtained in this way yields virtually the same results, so we do not consider iterative refinement here.) Using the solution obtained by MATLAB's backslash operator, we computed the error norms of the multiplicative Schwarz method by [mathematical expression not reproducible] with [x.sup.(k+1)] as in (3.2) (rather than using the update formula [e.sup.(k)] = T[e.sup.(k-1)]). Consequently, the computed error norms stagnate on the level of the maximal attainable accuracy of the method. On the other hand, an error bound of the form [|[rho]|.sup.k] for some |[rho]| < 1 becomes arbitrarily small for k [right arrow] [infinity].

We start with the upwind discretization. The left parts of Figures 5.1-5.5 show the error norms

[mathematical expression not reproducible]

for the iteration matrices T = (I - [P.sub.1])(I - [P.sub.2]) (solid) and T = (I - [P.sub.1])(I - [P.sub.2]) (dashed) as well as the corresponding upper bounds from Theorem 4.6, for increasing values of [member of]. We observe that the bounds are quite close to the actual errors. Moreover, in each case the error norm for the multiplicative Schwarz method with the iteration matrix T = (I - [P.sub.1])(I - [P.sub.2]) almost stagnates in the first step, as predicted by the bound in Theorem 4.6.

On the right parts of Figures 5.1-5.5 we display the error norms of the multiplicative Schwarz method and the corresponding convergence bounds from Theorem 4.13 for the central difference scheme. For our choice of parameters we have [alpha]H > 2[member of]. Note that the error norms are virtually the same for both iteration matrices. However, the bounds are not as tight as for the upwind scheme. For fixed N the bounds become weaker with increasing [??], i.e., decreasing convection-dominance. For our chosen parameters and [member of] = [10.sup.-4], giving [member of][N.sup.2] = 0(1), the convergence of the multiplicative Schwarz method becomes very slow, and the bound (4.22) fails to predict convergence at all. The values of |[rho]| and the corresponding bounds from Theorems 4.6 and 4.13 are shown in Table 5.1 for the case N = 198. We observe that the bounds on |[rho]| for the upwind scheme are tighter than for the central difference scheme.

We also run the experiments for a larger value of N, namely N = 10002, to further illustrate our results. We consider the special cases [member of][N.sup.2] [approximately equal to] 1 (Figure 5.4) and [member of]N [approximately equal to] 1 (Figure 5.5) which are mainly of theoretical interest. While the bound (4.7) for the upwind scheme is still tight and descriptive, the bound (4.22) for the central difference scheme does not predict convergence well. Note that the parameters used in Figure 5.5 yield [alpha]H [approximately equal to] 1.9959 x [10.sup.-4] < 2[member of], and hence the right part of Figure 5.5 shows error norms and the convergence bound corresponding to the case [alpha]H [less than or equal to] 2e in Theorem 4.13.

We conclude our numerical experiments by applying GMRES to the linear algebraic system preconditioned with multiplicative Schwarz, i.e., the linear algebraic system (6.1), in the case N = 198. The true (preconditioned) relative residual norms are shown in Figures 5.6-5.8. In all cases convergence is achieved in two iterations, which is explained in the next section. These figures are the counterparts to Figures 2.2-2.4, where GMRES makes little progress until iteration 198.

6. Concluding discussion. We studied the convergence of the multiplicative Schwarz method applied to upwind and central finite difference discretizations of one-dimensional singularly perturbed convection-diffusion model problems posed on a Shishkin mesh. The matrices that arise from the discretization are nonsymmetric and usually nonnormal as well as ill-conditioned, which leads to very slow convergence of standard iterative solvers like the (unpreconditioned) GMRES method.

In the simple one-dimensional case analyzed in this paper, the Shishkin mesh divides the discretized domain into two local subdomains where the solution presents a different characteristic nature. Therefore, a solution approach based on domain decomposition methods seemed only natural. For the upwind scheme, we proved rapid convergence of the multiplicative Schwarz method for all relevant problem parameters. The convergence for the central difference scheme is slower but still rapid when [N.sup.2][member of] < [alpha] and if N/2 - 1 is even.

Based on (3.2), it is clear that the multiplicative Schwarz method can be seen as a Richardson iteration for the system

(6.1) (I - T)x = v.

Furthermore, the iteration scheme (3.2) can be written in the form

[x.sup.(k +1)] = [x.sup.(k)] + (I - T)(x - [x.sup.(k)]),

so that the multiplicative Schwarz method as well as GMRES applied to (6.1) obtain their approximations from the Krylov subspace [K.sub.k](I - T,[r.sub.0]). Consequently, in terms of the residual norm, GMRES applied to (6.1) will always converge faster than the multiplicative Schwarz method. Moreover, if one applies GMRES to (6.1), then the multiplicative Schwarz method can be seen as a preconditioner for the GMRES method; see, e.g., [11] where this approach is taken. The preconditioner M such that [M.sup.-1]Ax = [M.sup.-1]b results in (6.1), can formally be written as M = A[(I - T).sup.-1]; see, e.g., [13, Lemma 2.3].

In general, if a matrix T satisfies r = rank(T), then for any initial residual [r.sub.0] we have

dim ([K.sub.k](I - T, [r.sub.0])) [less than or equal to] r + 1,

so that GMRES applied to the system (6.1) converges to the solution in at most r + 1 steps (in exact arithmetic). In the one-dimensional model problem studied in this paper we have a matrix T with r = 1. Thus, GMRES applied to (6.1) converges in (at most) two steps (see Figures 5.6-5.8) even if the multiplicative Schwarz iteration itself converges slowly or diverges, which may happen for the central difference scheme and m odd. In a generalization of the approach presented in this paper to two- or three-dimensional problems and hence more complicated Shishkin meshes with several transition points, one can possibly exploit a low rank structure of the iteration matrix as well.

It is important to point out that, typically, in practical implementations the local subdomain problems will not be solved exactly. In the case of inexact solves the bounds obtained in this paper and the exact termination of GMRES in r+1 steps will no longer hold. Nevertheless, the theory for the exact case presented here gives an indication of the behavior in the inexact case. This is a standard approach in the context of preconditioning. An example of this framework is given by the saddle-point preconditioners for which GMRES terminates in a few steps; see [3]. In the context of domain decomposition methods, in particular for Schwarz methods, the concept of inexact subdomain solves was investigated, e.g., in [2, Section 4]. See also [9], where a similar situation is described for algebraic optimized Schwarz methods.

Acknowledgments. We would like to thank the anonymous referees for valuable comments that helped improve the presentation of the results.

REFERENCES

[1] V. B. ANDREEV AND N. V. KOPTEVA, A study of difference schemes with the first derivative approximated by a central difference ratio, Comput. Math. Math. Phys., 36 (1996), pp. 1065-1078.

[2] M. BENZI, A. FROMMER, R. NABBEN, AND D. B. SZYLD, Algebraic theory of multiplicative Schwarz methods, Numer. Math., 89 (2001), pp. 605-639.

[3] M. BENZI AND A. J. WATHEN, Some preconditioning techniques for saddle point problems, in Model Order Reduction: Theory, Research Aspects and Applications, W. H. A. Schilders, H. A. van der Vorst, and J. Rommes, eds., vol. 13 of Math. Ind., Springer, Berlin, 2008, pp. 195-211.

[4] A. BERMAN AND R. J. PLEMMONS, Nonnegative Matrices in the Mathematical Sciences, 2nd ed., SIAM, Philadelphia, 1994.

[5] V. DOLEAN, P. JOLIVET, AND F. NATAF, An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation, SIAM, Philadelphia, 2015.

[6] P. A. FARRELL, A. F. HEGARTY, J. J. H. MILLER, E. O'RIORDAN, AND G. I. SHISHKIN, Robust Computational Techniques for Boundary Layers, Chapman & Hall, Boca Raton, 2000.

[7] P. A. FARRELL AND G. I. SHISHKIN, Schwartz methods for singularly perturbed convection-diffusion problems, in Analytical and Numerical Methods for Convection-Dominated and Singularly Perturbed Problems, L. G. Vulkov, J. J. H. Miller, and G. I. Shishkin, eds., Nova Science Publishers, Huntington, NY, 2000, pp. 33-42.

[8] M. J. GANDER, Schwarz methods over the course of time, Electron. Trans. Numer. Anal., 31 (2008), pp. 228-255. http://etna.ricam.oeaw.ac.at/vol.31.2008/pp228-255.dir/pp228-255.pdf

[9] M. J. GANDER, S. LOISEL, AND D. B. SZYLD, An optimal block iterative method and preconditioner for banded matrices with applications to PDEs on irregular domains, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 653-680.

[10] W. HACKBUSCH, Elliptic Differential Equations, Springer, Berlin, 2010.

[11] G. A. A. KAHOU, E. KAMGNIA, AND B. PHILIPPE, An explicit formulation of the multiplicative Schwarz preconditioner, Appl. Numer. Math., 57 (2007), pp. 1197-1213.

[12] N. KOPTEVA AND E. O'RIORDAN, Shishkin meshes in the numerical solution of singularly perturbed differential equations, Int. J. Numer. Anal. Model., 7 (2010), pp. 393-415.

[13] P. J. LANZKRON, D. J. ROSE, AND D. B. SZYLD, Convergence of nested classical iterative methods for linear systems, Numer. Math., 58 (1991), pp. 685-702.

[14] T. LINSS AND M. STYNES, Numerical methods on Shishkin meshes for linear convection-diffusion problems, Comput. Methods Appl. Mech. Engrg., 190 (2001), pp. 3527-3542.

[15] H. MACMULLEN, J. J. H. MILLER, E. O'RIORDAN, AND G. I. SHISHKIN, Schwarz iterative method for convection-diffusion problems with boundary layers, in Analytical and Numerical Methods for Convection-Dominated and Singularly Perturbed Problems, L. G. Vulkov, J. J. H. Miller, and G. I. Shishkin, eds., Nova Science Publishers, Huntington, NY, 2000, pp. 213-218.

[16]--, A second-order parameter-uniform overlapping Schwarz method for reaction-diffusion problems with boundary layers, J. Comput. Appl. Math., 130 (2001), pp. 231-244.

[17] H. MACMULLEN, E. O'RIORDAN, AND G. I. SHISHKIN, Schwarz methods for convection-diffusion problems, in Numerical Analysis and its Applications (Rousse, 2000), L. Vulkov, J. Wasniewski, and P. Yalamov, eds., vol. 1988 of Lecture Notes in Comput. Sci., Springer, Berlin, 2001, pp. 544-551.

[18]--, The convergence of classical Schwarz methods applied to convection-diffusion problems with regular boundary layers, Appl. Numer. Math., 43 (2002), pp. 297-313.

[19] J. J. H. MILLER, E. O'RIORDAN, AND G. I. SHISHKIN, Fitted Numerical Methods for Singular Perturbation Problems: Error Estimates in the Maximum Norm for Linear Problems in One and Two Dimensions, Revised Edition, World Scientific Publishing, Singapore, 2012.

[20] R. NABBEN, Two-sided bounds on the inverses of diagonally dominant tridiagonal matrices, Linear Algebra Appl., 287 (1999), pp. 289-305.

[21] H.-G. ROOS, A note on the conditioning of upwind schemes on Shishkin meshes, IMA J. Numer. Anal., 16 (1996), pp. 529-538.

[22] M. STYNES, Steady-state convection-diffusion problems, Acta Numer., 14 (2005), pp. 445-508.

[23] D. B. SZYLD, The many proofs of an identity on the norm of oblique projections, Numer. Algorithms, 42 (2006), pp. 309-323.

[24] A. TOSELLI AND O. WIDLUND, Domain Decomposition Methods--Algorithms and Theory, Springer, Berlin, 2005.

[25] R. A. USMANI, Inversion of Jacobi's tridiagonal matrix, Comput. Math. Appl., 27 (1994), pp. 59-66.

CARLOS ECHEVERRIA ([section]), JORG LIESEN ([section]), DANIEL B. SZYLD ([double dagger]), AND PETR TICHY ([dagger])

(*) Received January 12, 2017. Accepted January 22, 2018. Published online on February 22, 2018. Recommended by Ken Hayami. The work of C. Echeverria was partially supported by the Berlin Mathematical School and the Einstein Center for Mathematics Berlin. The work of D. B. Szyld was supported in part by the U.S. National Science Foundation under grant DMS-1418882 and by the Department of Energy grant DE-SC0016578. The work of P. Tichy was partially supported by the projects P201/13-06684S and 17-04150J of the Grant Agency of the Czech Republic.

([section]) Institute of Mathematics, TU Berlin, Stra[beta]e des 17. Juni 136, 10623 Berlin, Germany ({echeverria,liesen}@math.tu-berlin.de).

([double dagger]) Department of Mathematics, Temple University, Philadelphia, PA 19122-6094, USA (szyld@temple.edu).

([dagger]) Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic, and Institute of Computer Science, Academy of Science of the Czech Republic (ptichy@karlin.mff.cuni.cz).

DOI: 10.1553/etna_vol48s40
Table 5.1 Values of |[rho]| computed using (4.5) and the corresponding
bounds (4.7) and (4.22) for different [member of] and N = 198.

             upwind                                 central differences
[member of]  |[rho]| (4.5)       bound (4.7)        |[rho]| (4.5)

[10.sup.-8]  9.4 x [10.sup.-7]   9.9 x [10.sup.-7]  1 8 x [10.sup.-4]
[10.sup.-6]  9.4 x [10.sup.-5]   9.9 x [10.sup.-5]  1 8 x [10.sup.-2]
[10.sup.-4]  9.3 x [10.sup.-3]   9.8 x [10.sup.-3]  8.3 x [10.sup.-1]

             central differences
[member of]  bound (4.22)

[10.sup.-8]  3.9 x [10.sup.-4]
[10.sup.-6]  3.9 x [10.sup.-2]
[10.sup.-4]  3.8 x [10.sup.0]
COPYRIGHT 2018 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Echeverria, Carlos; Liesen, Jorg; Szyld, Daniel B.; Tichy, Petr
Publication:Electronic Transactions on Numerical Analysis
Article Type:Report
Date:Jan 1, 2018
Words:8934
Previous Article:QUADRATIC SPLINE WAVELETS WITH SHORT SUPPORT SATISFYING HOMOGENEOUS BOUNDARY CONDITIONS.
Next Article:ASYMPTOTIC CONSISTENT EXPONENTIAL-TYPE INTEGRATORS FOR KLEIN-GORDON-SCHRODINGER SYSTEMS FROM RELATIVISTIC TO NON-RELATIVISTIC REGIMES.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters