Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
_j
SEVEN
J
....
J
LINEAR
ALGEBRA
The solution
of
systems of simultaneous linear equations and the calculation of
the eigenvalues and eigenvectors
of
a matrix are two very important problems
that
arise in a wide variety of contexts.
As
a preliminary to the discussion of
these problems in the following chapters,
we
present some results from linear
algebra.
The
first section contains a review of material
on
vector spaces, matrices,
and
linear systems, wltich is taught
in
inost undergraduate linear algebra courses.
These results are summarized only. and no derivations are included. The remain-
ing sections discuss eigenvalues, canonical forms for matrices, vector and matrix
norms, and perturbation theorems for matrix
invers~s.
If
necessary, this chapter
can be skipped, and the results can
be
referred back to as they are needed in
Chapters 8 and
9.
For
notation, Section
7.1
and the norm notation
of
Section
7.3
should
be
skimmed.
7.1 Vector Spaces, Matrices, and Linear Systems
Roughly speaking a vector space V
is
a set of objects, called vectors, for which
operations
of
vector addition and scalar multiplication have been defined. A
vector space
V has a set of scalars associated with it,
and
in
this text, this set can
be
either the real numbers R or complex numbers C. The vector operations must
satisfy certain standard associative, commutative, and distributive rules, which
we will
not
list. A subset W of a vector space V is called a subspace
of
V if W is
a vector space using the vector operations inherited from
V.
For
a complete
development
of
the theory of vector spaces, see any undergraduate text on linear
algebra [for example, Anton (1984), chap. 3; Halmos (1958), chap. 1; Noble
(1969). chaps. 4 and
14;
Strang (1980), chap.
2].
Example
l.
V =
Rn,
the set of all n-tuples
(x
1
,
...
,
xn)
with real entries x;, and
R is the associated set of scalars .
2.
V =
en,
the set of all n-tuples with complex entries, and C is the set of
scalars.
3. V = the set
of
all polynomials of degree
:;;;
n, for some given n,
is
a vector
space. The scalars can be R or
C,
as desired for the application.
463
__
__]
!
i
[
I
I
!
I
I
...
j
464
LINEAR ALGEBRA
4. V = C[ a, b
],
the set of all continuous real valued [or complex valued]
functions
on
the interval [a, b
],
is
a vector space with scalar set equal to R [or C].
The example in (3)
is
a subspace
of
C[ a, b
].
Definition Let V be a vector space and let v
1
,
v
2
,
•••
,
vm
E
V.
1.
We
say that
vi>
...
,
vm
are linearly dependent if there
is
a set of
scalars a
1
,
•••
, am, with at least one nonzero scalar, for which
Since
at
least one scalar
is
nonzero, say
a;
=1=
0,
we
can solve for
We say that
v;
is
a linear combination of the vectors
v
1
,
•••
,
V;_
1
,
vi+!•
...
,
vm.
For
a set of vectors to be linearly
dependent, one
of
them must be a linear combination
of
the
remaining ones.
2.
We say v
1
,
•••
,
vm
are linearly independent if they are not depen-
dent. Equivalently, the only choice of scalars a
1
,
•..
, am for
which
is
the trivial choice a
1
= · · · = am =
0.
No V; can be written as
a combination of the remaining ones.
3. { u
1
,
•••
,
um}
is a basis for V
if
for every v E
V,
there
is
a
unique choice of scalars a
1
,
•.•
, am for which
Note that this implies
v
1
,
•••
,
um
are independent.
If
such a
finite basis exists,
we
say V
is
finite dimensional. Otherwise, it
is
called infinite dimensional.
Theorem 7.1
If
V
is
a:
vector space with a basis { v
1
,
...
,
vm
},
then every basis
for
V will contain exactly m vectors. The number m
is
called the
dimension of
V.
Example 1.
{1,
x, x
2
,
•••
,
xn}
is
a basis for the space V of polynomials
of
degree :$; n. Thus dimension V = n +
1.
2.
Rn
and
en
have the basis { e
1
,
...
, en), in which
e;=
(0,0,
...
,0,1,0,
...
,0)
(7.1.1)
VECTOR SPACES, MATRICES,
AND
LINEAR
SYSTEMS
465
with the 1 in position i. Dimension
R",
C" = n. This is called the standard basis
for
R"
and C", and the vectors in it are called unit vectors.
3. C[ a, b] is infinite dimensional.
Matrices and linear systems Matrices are rectangular arrays of real or complex
numbers,
and the general matrix of order m X n has the form
(7.1.2)
A matrix
of
order n
is
shorthand for a square matrix
of
order n X n. Matrices
will
be
denoted by capital letters, and their entries will normally be denoted by
lowercase letters, usually corresponding to the name
of
the matrix,
as
just given.
The following definitions give the
rommon operations on matrices.
Definition
1.
Let A and B have order m X n. The sum of A and B is the
matrix C
=A
+
B,
of order m X
n,
given
by
2. Let A have order m X n, and let a
be
a scalar. Then the scalar
multiple C
=
aA
is
of order m X n and is given by
C;j
=
aaij
3. Let A have order m X n and B have order n X
p.
Then the
product C
=
AB
is
of order m X p, and it is given by
n
C;j
= L
O;kbkj
k=l
4. Let A have order m X n. The transpose C =
AT
has order n X
m,
and
is
given by
The
conjugate transpose C
=A*
also has order n X
m,
and
The notation
z denotes the complex conjugate of the complex number
z, and z is real if and only if z = z. The conjugate transpose
A*
is
also
called the
adjoint of
A.
i
i
i
I
i
.I
466 LINEAR ALGEBRA
The following arithmetic properties of matrices can be shown without much
difficulty, and they are left
to
the reader.
(a)
A+
B = B
+A
(b)
(A
+B)+
C
=A
+
(B
+C)
(c)
A(B
+
C)=
AB
+
AC
(e)
(A
+
B)T
=AT+
BT
(d)
A(BC)
=
(AB)C
(7.1.3)
(f)
(AB)T
= BTAT
It
is
important for many applications
to
note that the matrices need not be
square for the preceding properties to hold.
The vector spaces
Rn
and
en
will usually be identified with the set of column
vectors of order
n X
1,
with real and complex entries, respectively. The linear
system
(7
.1.4)
can be written as
Ax
=
b,
with A
as
in (7.1.2), and
X = [
Xl'
...
' X
n]
T
The vector b is a given vector in
Rm,
and the solution x
is
an unknown vector in
Rn.
The use
of
matrix multiplication reduces the linear system (7.1.4)
to
the
simpler and more intuitive form
Ax
=
b.
We now introduce a
few
additional definitions for matrices, including some
special matrices.
Definition
l.
The zero matrix
of
order m X n has all entries equal to zero.
It
is
denoted by
omXn'
or more simply, by
0.
For
any matrix A of order
m X n,
A+
0 = 0 +
A.=A
2.
The identity
matrix
of order n
is
defined by
I=
[8ij],
i=j
i#-j
(7.1.5)
for
alll
~
i, j
~
n.
For
all matrices A of order m X n and B of order
n
Xp,
Al=A
JB = B
The notation
B;j
denotes the Kronecker delta function.
3.
Let A be a square matrix of order n.
If
there is a square matrix B
of order n for which
AB
=
BA
= I, then
we
say A is invertible, with
inverse B. The matrix B can be shown to be unique, and
we
denote the
inverse of
A by A
-l.
VECTOR SPACES, MATRICES,
AND
LINEAR SYSTEMS 467
4.
A matrix A
is
called symmetric if
AT=
A,
and it
is
called
Hermitian if
A*
=A.
The term symmetric is generally used only with
real matrices. The matrix
A
is
skew-symmetric if
AT=
-A.
Of
necessity, all matrices that are symmetric, Hermitian, or skew-symmet-
ric must also be square.
5. Let
A be an m X n matrix. The row rank of A is the number of
linearly independent rows in
A, regarded
as
elements of
Rn
or
en,
and
the column rank
is
the nuptber of linearly independent columns.
It
can
be
shown (Problem
4)
that these two numbers are aiways equal, and
this
is
called the rank of
A.
For
the definition and properties of the determinant of a square matrix A, see
any linear algebra text [for example, Anton (1984), chap.
2;
Noble (1969), chap.
7;
and Strang
(1980),
chap.
4].
We
summarize many
of
the results on matrix
inverses and the solvability of linear systems in the following theorem.
Theorem
7.2
Let A be a square matrix with elements from R (or C), and let the
vector space be
V =
Rn
(or
en).
Then the following are equivalent
statements.
1.
Ax
= b has a unique solution x E V for every b E
V.
2.
Ax
= b has a solution x E V for every b E
V.
3.
Ax
= 0 implies x =
0.
4.
A
-I
exists.
5.
Determinant {A)
=t=
0.
6.
Rank (A) = n.
Although no proof is given here, it is an excellent exercise to prove the
equivalence of some of these statements.
Use the concepts of linear independence
and basis, along with Theorem 7
.1. Also, use the decomposition
(7.1.6)
with
A*j
denoting column j in
A.
This says that the space
of
all vectors of the
form
Ax
is spanned by the columns of
A,
although they may be linearly
dependent.
Inner product vector spaces
One of the important reasons for reformulating
problems as equivalent linear algebra problems is
to
introduce some geometric
insight. Important
to
this process are the concepts
of
inner product and orthogo-
nality.
468 LINEAR ALGEBRA
Definition
1.
The inner product of two vectors
x,
y E
R"
is
defined by
n
(x,y)
=
LX;Y;=xTy=yTx
i=l
and for vectors x, y E C", define the inner product by
n
(x,y)=
LX;J;=y*x
i-1
Z.
The Euclidean norm of x in C" or
R"
is
defined by
(7.1.7)
The following results are fairly straightforward to prove, and they are left
to
the reader. Let V denote C"
orR".
1.
For
all
x,
y,
z E
V,
(x, y + z) = (x,
y)
+ (x, z ),
(x
+
y,
z)
=
(x,
z)
+
(y,
z)
2.
For
all
x,
y E
V,
(ax,
y) =
a(x,
y)
and for
V=
C", a E
C,
(x,
ay)
=
a(x,
y)
3. In
en,
(x,
y)
=
(y,
x);
and in
Rn,
(x,
y)
=
(y,
x).
4.
For
all x E
V,
(x, x)
~
0
and
(x,
x)
= 0 if and only if x =
0.
5.
For all
x,
y E
V,
l(x,
y)
1
2
~
(x,
x)(y,
y)
(7
.1.8)
This is called the Cauchy-Schwartz inequality, and it is proved in exactly the
same manner
as
(4.4.3) in Chapter
4.
Using the Euclidean norm,
we
can
write it as
(7.1.9)
6.
For
all
x,
y E
V,
(7.1.10)
This is the triangle inequality.
For
a geometric interpretation, see the earlier
comments in Section
4.1
of Chapter 4 for the norm
llflloo
on C[a,
b].
For
a
proof of
(7.1.10), see the derivation of (4.4.4) in Chapter 4.
VECTOR SPACES, MATRICES,
AND
LINEAR SYSTEMS 469
7.
For any square matrix A of order n, and for any x, y E C",
(Ax,
y)
=
(x,
A*y)
(7
.1.11)
The inner product
was
used to introduce the Euclidean length, but it
is
also
used to define a sense of angle, at least in spaces in which the scalar set
is
R.
Definition I. For
x,
y in
R",
the angle between x
andy
is defined by
Note that the argument
is
between
-1
and
1,
due to · the
Cauchy-Schwartz inequality (7.1.9). The preceding definition can
be
written implicitly
as
(7.1.12)
a familiar formula from the use of the dot product in R
2
and R
3
•
2. Two vectors x and y are orthogonal if and only if
(x,
y)
=
0.
This
is
motivated by (7.1.12).
If
{ x(l),
...
,
x<">}
is
a basis for C"
orR",
and if (x<il, x<j)) = 0 for all i
=I=
j,
1
::s;
i, j
::s;
n,'
then
we
say
{
x(l>,
..
.",
x<n>}
is
an orthogonal basis.
If
all basis vectors have
Euclidean length
1,
the basis
is
called orthonormal.
3. A square matrix U
is
called unitary if
U*U=
UU*
=I
If
the matrix U
is
real, it is usually called orthogonal, rather than
unitary. The rows for
colu.mns]
of an order n unitary matrix form an
orthonormal basis for
C", and similarly for orthogonal matrices
and
R".
E:mmp/e
I.
The angle between the vectors
x
='=
(1, 2, 3)
y = (3, 2, I)
is
given by
d=
ccis-
1
(
~~]
=
.775
radians
2.
The matrices
[
cos
8
sinO]
Ut=
-sin
8 cos 8
1]
.fi
are unitary, with the first being orthogonal.
j
!
I
!
I
470 LINEAR ALGEBRA
Yj
~~'-------1....-----'-----•
uW
Figure
7.1
Illustration
of
(7.1.15).
An orthonormal basis for a vector space
V =
Rn
or
en
is
desirable, since it
is
then easy to decompose an arbitrary vector into its components
in
the direction
of
the basis vectors. More precisely, let {
u(l>,
...
,
u<n>}
be an orthonormal basis
for
V,
and let x E
V.
Using the basis,
for some unique choice of coefficients
a
1
,
...
,
a".
To
find
aj,
form the inner
product of
x with u<j), and then
using the orthonormality properties of the basis. Thus
n
x = L (x,
uU>)uU>
j-1
(7~1.13)
{7.1.14)
This can
be
given a geometric interpretation, which is shown in Figure 7.1. Using
(7.1.13)
{7
.1.15)
Thus the coefficient
aj
is
just the length of the orthogonal projection of x onto
the axis determined by
uU>.
The formula (7.1.14)
is
a generalization of the
decomposition of
a vector x
u,sing
the standard basis ( e <
1
>,
...
, e
<"
> } , defined
earlier.
Example Let V
= R
2
,
and consider the orthonormal basis
u<l>=(~
{3)
2'
2
.u<2)
=
(-
{3
~)
2
'2
EIGENVALUES AND CANONICAL FORMS
FOR
MATRICES 471
Then
for
a given vector x =
(x
1
,
x
2
),
it
can
be
written as
x - a
u<
1
> + a
u<
2
>
- 1 2
For
example,
1
13
(
1
0) =
-u<
1
>-
-u<
2
>
' 2 2
7.2 Eigenvalues
and
Canonical Fonns for Matrices
The
number
A,
complex
or
real, is
an
eigenvalue
of
the square matrix A
if
there is
a
VeCtOr
X E
en,
X
-f=
0,
SUCh
that
Ax
=Ax
(7.2.1)
The
vector x is called
an
eigenvector corresponding
to
the eigenvalue
A.
From
Theorem
7.2, statements (3)
and
(5), A is
an
eigenvalue
of
A if
and
only
if
det(A-
AI)=
0
(7.2.2)
This
is called the characteristic equation for
A,
and
to analyze
it
we
introduce
the
function
·
If
A
has
order
n, then fA(A) will
be
a polynomial
of
degree exactly n, called the
characteristic polynomial
of
A.
To
prove
it
is a polynomial,
expand
the
determi-
nant
by
minors repeatedly to get
[
a
11
- A
a21
=
det
.
an1
=
(a
11
- A)(a
22
-
A)···
(ann-
A)
+ terms
of
degree
~
ri
- 2
+ terms
of
degree
~
n - 2
(7.2.3)