is obtained. With this technique, the resulting total number of cut-edges is equal to 441

and the standard deviation is 7.04. As is somewhat expected, the number of cut-edges has

decreased dramatically, while the standard deviation of the various sizes has increased.

b“gm

7‚£7

¢ $¨s

@7@

1 In the proof of Theorem 13.4, the following form of the Cauchy-Schwarz inequality was used:

& &

¥¦ ¦

¥

¥ ¥ ‚

¥

‚ ‚

£

$ $ # &

#B$ I$ #

¡ # $ 9$

#

¡

& ¤$ & ¤$

¢$

¡ ¡ ¡

(a) Prove that this result is a consequence of the standard Cauchy-Schwarz inequality. (b) Extend ¥

the result to the -inner product. (c) Assume that the ™s and ™s are the columns of two $

$

¤ H©§

6¨

matrix and . Rewrite the result in terms of these matrices.

¢&

2 Using Lemma 13.1, write explicitly the vector for the Multiplicative Schwarz procedure,

¦% e ¦%

in terms of the matrix and the ™s, when and then when .

$

¤ )d

¢

3 (a) Show that in the multiplicative Schwarz procedure, the residual vectors obtained

$ $

¤(

¦

at each step satisfy the recurrence,

& $8$ & $ ¤ ¤ ( & 8¦ 8

$

$

$

&

% F''" X ¦

for . (b) Consider the operator . Show that is a projector. (c)

$ $ $

$ $ ¤

¤

#

"

!

!

Is an orthogonal projector with respect to the -inner product? With respect to which inner

$1! ¤

product is it orthogonal?

&

4 The analysis of the Additive Schwarz procedure assumes that is “exact,” i.e., that linear $ ¤

& &

¢

systems are solved exactly, each time is applied. Assume that is replaced by

#$

$ ¤ $ ¤

¤ ¦ &

some approximation . (a) Is still a projector? (b) Show that if is Symmetric Positive $ $

$

$ % $

)23£

4

De¬nite, then so is . (c) Now make the assumption that . What becomes of

$ $

#

% 1)'

% 0( &

the result of Theorem 13.2?

5 In Element-By-Element (EBE) methods, the extreme cases of the Additive or the Multiplicative

Schwarz procedures are considered in which the subdomain partition corresponds to taking to $

5

be an element. The advantage here is that the matrices do not have to be assembled. Instead, they

are kept in unassembled form (see Chapter 2). Assume that Poisson™s equation is being solved.

—‘

—t

7 u pU¢ 7 p z7 yw— y w u

{ {˜p p { p

˜

“£§

¢

! hC §¤ !

¤ …S !

§

¥

¤ ¤

(a) What are the matrices ? (b) Are they SPD? (c) Write down the EBE preconditioning

$

¤

corresponding to the multiplicative Schwarz procedure, its multicolor version, and the additive

Schwarz procedure.

6 Theorem 13.1 was stated only for the multiplicative version of the Schwarz procedure. There is

a similar result for the additive Schwarz procedure. State this result and prove it.

7 Show that the matrix de¬ned by (13.37) is indeed a projector. Is it possible to formulate Schwarz

procedures in terms of projection processes as seen in Chapter 5?

8 It was stated at the end of the proof of Theorem 13.4 that if

¥ # ¤ © X ¨ § ¦# ¤ £ ¡¤B

¥¢¢

¢¢

&§

for any nonzero , then . (a) Prove this result without invoking the min-max

# ¡B $

¢ ¤

&

theory. (b) Prove a version of the min-max theorem with the -inner product, i.e., prove that the ¤

min-max theorem is valid for any inner product for which is self-adjoint. ¤

9 Consider the Laplacean of a graph as de¬ned in Section 13.6. Show that

‚

'

c$ (

#

$ #

¦#

"#! ©$

10 Consider a rectangular ¬nite difference mesh, with mesh size in the -direction and

'¦ %

&