## Read an Excerpt

#### Applied Iterative Methods

**By Louis A. Hageman, David M. Young**

**Dover Publications, Inc.**

**Copyright © 1981 Louis A. Hageman and David M. Young**

All rights reserved.

ISBN: 978-0-486-15330-8

All rights reserved.

ISBN: 978-0-486-15330-8

CHAPTER 1

**Background on Linear Algebra and Related Topics**

1.1 INTRODUCTION

In this chapter we give some background material from linear algebra which will be helpful for our discussion of iterative methods. In **Sections 1.2–1.5**, we present a brief summary of basic matrix properties and principles which will be used in subsequent chapters. No proofs are given. It is assumed that the reader is already familiar with the general theory of matrices such as presented, for instance, in Noble and Daniel [1977] or in Faddeev and Faddeeva [1963, Chap. 1]. In **Sections 1.6** and **1.7**, we discuss the matrix problem which is obtained from a simple discretization of the generalized Dirichlet problem. The purpose of this example is to illustrate some of the matrix concepts presented in this chapter and to illustrate the formulations of matrix problems arising from the discretization of boundary- value problems.

**1.2 VECTORS AND MATRICES**

We let *EN* denote the set of all *N* × 1 column matrices, or vectors, whose components may be real or complex. A typical element *v* of *EN* is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-2.1)

To indicate that *vi, i* = 1, 2, ..., *N*, are the components of *v*, we write *v = (vi)*. A collection of vectors *v*(1), *v*(2), ..., *v(s)* is said to be *linearly dependent* if there exist real or complex numbers *c*1, *c*2, ..., *cs*, not all zero, such that

*c*1*v*(1) + *c*2*v*(2) + ··· + *csv(s)* = 0.

If this equality holds only when all the constants *c*1, ..., *cs* are zero, then the vectors *v*(1), ..., *v(s)* are said to be *linearly independent*. A *basis* for *EN* is a set of *N* linearly independent vectors of *EN*. Given such a basis, say, *v*(1), *v*(2), ..., *v(N)* then any vector *w* in *EN* can be expressed uniquely as a linear combination of basis vectors; i.e., there exists a unique set of numbers *c*1, *c*2, ..., *cN* such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-2.2)

The *transpose* of the vector *v* is denoted by *vT* and the *conjugate transpose* by *vH*. Given two vectors w and *v* of *EN*, the *inner product (w, v)* of the vector w with *v* is defined by

(*w, v*) [equivalent to] *w*H*v*. (1-2.3)

Similarly, *EN, N* denotes the set of all *N* × *N* square matrices whose elements may be real or complex. A typical element of *EN, N* is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-2.4)

or, equivalently, in abbreviated form by *A = (ai,j)* for 1 ≤ *i,j* ≤ *N*. We denote the *transpose* of the matrix *A* by *A*T and the *conjugate transpose* of *A* by *A*H. If the elements of *A* are real, then *A*H = *A*T. Normally, we shall deal only with real matrices. The matrix *A* is *symmetric* if *A* = *A*T.

The special *N* × *N* matrix *A = (ai, j)*, where *ai,i* = 1 and *ai,j* = 0 if *i* ≠ *j*, is called the *identity matrix* and is denoted by *I*. A matrix *A* in *EN,N* is *nonsingular* if there exists a matrix *H* such that *AH = HA = I*. If such an *H* exists, it is unique. The matrix *H* is called the *inverse* of *A* and is denoted by *A*-1.

A real matrix *A* in *EN,N* is *symmetric and positive definite* (SPD) if *A* is symmetric and if (*v, Av*) > 0 for any nonzero vector *v*. If A is SPD, then *A* is nonsingular. The matrix *LLT* is SPD for any real nonsingular matrix *L*. Also, if *A* is SPD, there exists a unique SPD matrix *J* such that *J*2 = *A*. The matrix *J* is called the *square root* of the SPD matrix *A* and is denoted by *A*1/2.

1.3 EIGENVALUES AND EIGENVECTORS

An *eigenvalue* of the *N* × *N* matrix *A* is a real or complex number λ which, for some nonzero vector *y*, satisfies the matrix equation

(*A* - λ*I*)*y* = 0. (1-2.1)

Any nonzero vector *y* which satisfies (**1-3.1**) is called an *eigenvector* of the matrix *A* corresponding to the eigenvalue λ.

In order for (**1-3.1**) to have a nontrivial solution vector *y*, the determinant of *A* - λ*I* (denoted by det (*A* - λ*I*)) must be zero. Hence, any eigenvalue λ must satisfy

det(*A* - λ*I*) = 0. (1-3.2)

Equation (**1-3.2**), which is called the *characteristic equation* of *A*, is a polynomial of degree *N* in λ. The eigenvalues of *A* are the *N* zeros of the polynomial (**1-3.2**).

A matrix *A* in *EN, N* has precisely *N* eigenvalues, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], some of which may be complex. The existence of at least one eigenvector corresponding to each eigenvalue λ*i* is assured since (**1-3.1**) with λ = λ*i* has a nontrivial solution. Eigenvectors corresponding to unequal eigenvalues are linearly independent. Thus, when all the eigenvalues of *A* are distinct, the set of eigenvectors for *A* includes a basis for the vector space *EN*. However, this is not always the case when some eigenvalues of *A* are repeated. In this book, we shall be concerned, for the most part, with those matrices whose eigenvalues are real and whose set of eigenvectors includes a basis for *EN*. Such eigenproperties are satisfied, for example, by the eigenvalues and eigenvectors of symmetric matrices.

Before discussing symmetric matrices and related matrices, we introduce some notations that will be used repeatedly in this and subsequent chapters.

The *spectral radius***S**(*A*) of the *N* × *N* matrix *A* is defined as the maximum of the moduli of the eigenvalues of *A*; i.e., if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the set of eigenvalues of *A*, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-3.3)

If the eigenvalues of *A* are real, we let *m(A) and M(A)* denote, respectively, the algebraically smallest and largest eigenvalues of *A*, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-3.4)

**Eigenproperties of Symmetric and Related Matrices**

Important eigenproperties of real symmetric matrices are summarized in the following theorem.

**Theorem 1-3.1.** If the *N* × *N* matrix *A* is real and symmetric, then

(1) the eigenvalues λ*i, i* = 1, ..., *N*, of *A* are real, and

(2) there exists *N* real eigenvectors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for *A* such that

**(a) Ay(i) = λiy(i), i = 1, ..., N,**

**(b) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]**

**(c) (y(i), y(j)) = 0 if i ≠ 0 and (y(i), y(j)) = i if i = j.**

When *A* is SPD, in addition to the eigenproperties given in **Theorem 1-3.1**, the eigenvalues of *A* are also positive. Since the matrix *A* is nonsingular if and only if no eigenvalue of *A* equals zero, it follows that a SPD matrix is also nonsingular.

Two matrices *A* and *B* are *similar* if *B = WAW*-1 for some nonsingular matrix *W*. Similar matrices have identical eigenvalues.

Except for (2c), the conclusions of **Theorem 1-3.1** also are valid for any real matrix *A* which is similar to a real symmetric matrix *C*.

For any real matrix *A* in *EN, N* and for any nonzero vector *v* in *EN* (real or complex), the *Rayleigh quotient* of *v* with respect to *A* is defined as the quotient of inner products *(v, Av)/(v, v)*. If *A* is symmetric, then for any nonzero vector *v* in *EN*

*m(A)* ≤ *(v, Av)/(v, v)* ≤ *M(A)*. (1-3.5)

Here *m(A)* and *M(A)* are defined by (**1-3.4**). Moreover, there exist nonzero vectors *w* and *z* such that

*(w, Aw)/(w, w) = m(A), (z, Az)/(z, z) = M(A)* (1-3.6)

and

*Aw = m(A)w, Az = M(A)z.* (1-3.7)

**Eigenproperties of Real Nonsymmetric Matrices**

The material in this subsection is used primarily in **Chapter 9**. Since the discussion is somewhat involved, many readers may wish to skip it on a first reading.

A real nonsymmetric matrix *A* may have complex eigenvalues. Since the coefficients of the characteristic polynomial (**1-3.2**) are real for this case, any complex eigenvalues of *A* must occur in complex conjugate pairs; i.e., if λ*i* is a complex eigenvalue of the real matrix *A*, then λ*k* = λ*i** is also an eigenvalue of *A*. Here, λ*i** denotes the complex conjugate of λ*i*. Moreover, if *y(i)* is an eigenvector corresponding to λ*i*, then *y(k) = y*(i)* is an eigenvector of *A* corresponding to λ*k* = λ*i**.

For an *N* × *N* nonsymmetric matrix *A*, it is not always possible to find a basis for *EN* from the set of eigenvectors of *A*. However, it is always possible to form a basis from the independent eigenvectors of *A* supplemented by other vectors (called principal vectors) which are associated with the eigenvalues and eigenvectors of *A*. Such a basis can best be described in terms of the Jordan canonical form associated with *A*. The following is a restatement of the results given in Noble and Daniel [1977].

A square matrix of order ≥ 1 that has the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-3.8)

is called a *Jordan block*. Note that the elements of *J* are zero except for those on the principal diagonal, which are all equal to λ, and those on the first superdiagonal, which are all equal to unity. Any matrix *A* can be reduced to a direct sum of Jordan blocks by a similarity transformation. More precisely, we have

**Theorem 1-3.2.** For any *N* × *N* matrix *A*, there exists a nonsingular matrix *V* such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1-3.9)

where each *Ji*, 1 ≤ *i* ≤ *k*, is a Jordan block whose constant diagonal element is an eigenvalue of *A*. The number of linearly independent eigenvectors of *A* is equal to the number *k* of Jordan blocks in (**1-3.9**).

The matrix J in (**1-3.9**) is called the *Jordan canonical form* of *A* and is unique up to a permutation of the diagonal submatrices. Let the column vectors of *V* be denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; i.e., *V* = [*v*(1), *v*(2), ..., *v(N)*]. Since *V* is nonsingular, the set of vectors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a basis for *EN*. For use in later chapters, we now examine the behavior of the matrix-vector products *Aiv(i), i* = 1, ..., *N*.

From the relation *AV = V* J and the form of J, it follows that the vectors *v(i)* separate, for each Jordan block *J*, into equations of the form

*Av(i)* = λ*iv(i)* + *viv*(*i* - 1), (1-3.10)

where λ*i* is an eigenvalue of *A* and *vi* is either 0 or 1, depending on J. If *vi* = 0, then *v(i)* is an eigenvector of *A*. When *v(i)* is an *eigenvector of A*, we have by (**1-3.10**) that

*Alv(i) = Al-1*(λ*iv(i))* = (λ*i*)*lv(i)*. (1-3.11)

*(Continues...)*

Excerpted fromApplied Iterative MethodsbyLouis A. Hageman, David M. Young. Copyright © 1981 Louis A. Hageman and David M. Young. Excerpted by permission of Dover Publications, Inc..

All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.

Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.