Atkinson K. An Introduction to Numerical Analysis

i

I

. . I

482 LINEAR ALGEBRA

(0,1)

(1,

1)

(1,

0)

(-

1,-1)

S1

Figure

7.2

The unit sphere

SP

using vector norm

II·

llr

We now prove some results relating different norms.

We

begin with the

following result on the continuity of

N(x)

=

llxll,

as

a function of x.

Lemma Let

N(x)

be a norm on

en

(or Rn). Then

N(x)

is

a continuous

function of the components x

1

,

x

2

,

..•

, xn of

x.

Proof

We want to show that

i =

1,2,

...

, n

implies

N(x)=N(y)

Using the reverse triangle inequality (7.3.1),

IN(x)-

N(y)l::;

N(x-

y)

X,

y E

en

Recall from (7.1.1) the definition of the standard basis {

e<

1

l,

...

,

e<nl}

for

en.

Then

n

X - y = L

(X

j -

y)

e

(j)

j=l

n n

N(x-

y)

::;

L

!xj-

yj!N(

eUl)

::;

llx-

Ylloo

L

N(

eUl)

j-1

j=l

!N(x)-

N(y)l

s

cllx-

Ylloo

This completes the proof.

n

c = L

N(eUl)

j=l

(7.3.5)

•

Note that

it

also proves that for every vector norm

Non

en,

there

is

a c > 0

with

N(x)::;

cllxlloo

all X E

en

(7.3.6)

Just let y = 0 in (7.3.5). The following theorem proves the converse of this result.

VECTOR

AND

MATRIX NORMS 483

Theorem 7.7 (Equivalence

of

Norms) Let

Nand

M be norms on V

=en

or

Rn.

Then there are constants c

1

,

c

2

> 0 for which

allxE

V

(7.3.7)

Proof

It

is sufficient to consider the case in which N

is

arbitrary

and

M(x)

=

llxlloo·

Combining two such statements then leads

to

the general result.

Thus

we wish to show there are constants c

1

,

c

2

for which

(7.3.8)

or

equivalently,

allz

E S (7.3.9)

in

which

Sis

the set

of

all points z in

en

for which

l!zlloo

= 1.

The

upper

inequality

of

(7.3.9) follows immediately from (7.3.6).

Note

tllat

Sis

a closed

and

bounded set in

en,

and

N is a continuous

function on S.

It

is then a standard result

of

advanced calculus

that

N

attains its maximum

and

minimum on S

at

points

of

S,

that

is, there are

constants c

1

,

c

2

and

points z

1

,

z

2

in S for which

Clearly, c

1

,

c

2

~

0.

And

if c

1

= 0, tllen

N(z

1

)

= 0. But

then

z

1

= 0,

contrary

to the construction

of

S that requires

llz

1

lloo

=

1.

This proves

(7.3.9), completing the proof

of

the theorem. Note: This theorem does

not

generalize to infinite dimensional spaces. •

Many

numerical methods for problems involving linear systems

produce

a

sequence

of

vectors

{x<m>lm

~

0},

and

we want to speak

of

convergence

of

this

sequence

to

a vector x.

Definition A sequence

of

vectors {

x(l>,

x<

2

>,

...

,

x<m>,

• · ·

},

in

en

or

Rn

is said

to

converge to a vector x if and only

if

as m

~

oo

Note

that the choice

of

norm

is left unspecified.

For

finite

dimensional spaces,

it

doesn't matter which

norm

is used.

Let

M

and

N be two norms

on

en.

Then

from (7.3.7),

m~O

and

M(x

-

x<m>)

converges to zero

if

and

only

if

N(x

-

x<m>)

does

the same. Thus

x<m>

~

x with tile M

norm

if

and

only

if

it

converges with the

N norm. This is

an

important

result,

and

it

is

not

true

for infinite dimensional spaCes.

Matrix

nonns

The

set

of

all n X n matrices with complex entries

can

be

considered as equivalent

to

the vector space

en\

with a special multiplicative

484

LINEAR

ALGEBRA

operation added onto the vector space. Thus a matrix norm should satisfy the

usual three requirements

Nl-N3

of a vector norm. In addition,

we

also require

two other conditions.

Definition A matrix norm satisfies

N1-N3

and the following:

(N4)

IIABII

~

IIAIIIIBII.

(NS)

Usual,ly

the vector space

we

will be working with, V

=en

or

Rn,

will

have some vector norm, call it

Hxllv•

x E

V.

We

require that the matrix and vector norms be compatible:

allxE

V all A

Example Let A be n X n,

II

.

llv

=

II

.

lb-

Then for X E

en,

by using the Cauchy-Schwartz inequality (7.1.8). Then

{7.3.10)

F(A)

is

called the Frobenius norm of

A.

Property N5 is shown using (7.3.10)

directly. Properties

Nl-N3

are satisfied since

F(A)

is

just

the Euclidean norm on

en

2

•

It

remains to show N4. Using the Cauchy-Schwartz inequality,

=

F(A)F(B)

Thus

F(A)

is a matrix norm, compatible with the Euclidean norm.

Usually when given a vector space with a norm

II

·llv•

an associated matrix

norm

is

defined by

IIAxllv

IIAII

=

Supremum--

x,.o

Uxllv

(7.3.11)

VECTOR

AND

MATRIX NORMS 485

Table 7.1 Vector nonns and associated operator matrix norms

Vector Norm

n

llxlh

= L

!x;l

i-1

llxlb

= [

~

!x;l

2

]

112

J-1

llxlloo

=

Max

jx;l

lSi;S;n

Matrix Norm

n

I!Aih

=

M!U

L

!aiJi

lS]Sni=l

n

I!AIIoo

=

M!U

L

!a;JI

1St;S;n

j-l

It

is

ofien called the operator norm.

By

its definition, it satisfies N5:

X E

en

(7.3.12).

For

a matrix A, the operator norm induced by the vector norm

llxliP

will be

denoted by

IIAllr The most important cases are given

in

Table 7.1, and the

derivations are given later.

We

need the following definition in order to define

IIAII.2·

Definition Let A be an arbitrary matrix. The spectrum of A

is

the set of all

eigenvalues of

A,

and it is denoted by

a(A).

The spectral radius

is

the maximum size of these eigenvalues, and it is denoted

by

(7.3.13)

To show (7.3.11)

is

a norm in general,

we

begin

by

showing it

is

finite. Recall

from Theorem

7.7

that there are constants c

1

,

c

2

> 0 with

X E

en

Thus,

which proves

IIAII

is

finite.

At

this point it

is

interesting to note the geometric significance of

IIAII:

IIAxllv

II

( X )

II

IIAII

=

Supremum--

= Supremum A

--

= SupremumiiAzllv

x,.O

llxllv

x,.O

llxllv

v Uzll.=l

By

noting that the supremum doesn't change if

we

let

llzllv

~

1,

IIAII

= Supremumi!Azll

Uzfl,,sl

(7.3.14)

486 LINEAR ALGEBRA

Let

the unit ball with respect to

II

·

II

v· Then

IIAII

-=

SupremumiiAzll. = Supremumllwll.

zeB

weA(B)

with

A(

B)

the image of B

when

A

is

applied to it. Thus

IIAII

measures the effect

of

A on the unit ball, and if

IIAII

>

1,

then

IIAII

denotes the maximum stretching

of the ball

B under the action of A.

Proof Following

is

a proof that the operator norm

IIAII

is

a matrix norm.

1.

Clearly

IIAII

~

0,

and if A =

0,

then HAll= 0. Conversely, if

IIAII

= 0,

then

IJAxll.

= 0 for all

x.

Thus Ax = 0 for

all

x,

and this implies

A

=0.

2. Let a be any scalar. Then

llaAII

= SupremumllaAxllv = SupremumJaJIIAxJI. =

Jal

SupremumUAxllv

llxll,,:s;l

IJxllv:s;l

llxiJv:s;l

=

JaJIIAIJ

3. For any X E

en,

II(A

+ B)xllv =

IIAx

+

Bxllv

:$JJAxllv

+

JJBxJJv

since

II

·

llv

is

a norm. Using the property (7.3.12),

This implies

II(A

+ B)xllv :SIIAiillxllv +

IIBJJIIxllv

II(A

+ B)xllv

:SIIAII

+

IIBII

llxllv

IIA

+

BIJ

::;;

IIAII

+

IIBII

4. For any X E

en,

use (7.3.12) to

get

II(AB)xllv = IIA(Bx)

llv

:SIIAIIIIBxiJv

:SIIAIIIIBIIIIxllv

IJABxiJv

:S

IIAIIIIBII

llxiJv

This implies·

IIABIJ

::;;

IJAIJIIBIJ

•

VECTOR

AND

MATRIX NORMS

487

We now comment more extensively on the results given in Table

7.1.

Example I. Use the vector norm

Then

II

llxll1

= L lxjl

j=l

xE

C

11

Changing the order of summation,

·we

can separate the summands,

Let

Then

and thus

II

IIAxlh

~

L

ixjl

L laijl

j~l

i=1

II

c = Max L

ia;·i

1:5}:511

i=1

1

IIAih

~

c

To

show this

is

an equality,

we

demonstrate an x for which

IIAxih

--=c

llxlh

{7.3.15)

Let

k be the column index

for

which the maximum in (7.3.15)

i~

attained. Let

x =

e<k>,

the

kth

unit vector. Then

Uxlh

= 1 and

This proves that for the vector norm

II

·

11

1

,

the operator norm

is

II

IIAih

=

~~

L laijl

1_]:5,11

i=1

{7

.3.16)

This is often called the column norm.

2.

For

C

11

with the norm

llxll""'

the operator norm

is

II

IIAIIco

=

M~

L laijl

1:5,1_11

j=l

{7.3.17)

488 LINEAR ALGEBRA

This

is

called the row norm of A. The proof of the formula

is

left

as

Problem

25,

although it is similar to that for

IIAih-

3. Use the norm

llxlh

on

en.

From (7.3.10), we conclude that

(7.3.18)

In general, these are not equal. For example, with A = /, the identity matrix, use

(7.3.10) and (7.3.11) to obtain

F(l}

=

{;

We prove

IIAib =

.jr"(A*A)

(7.3.19)

as stated earlier in Table 7.1. The matrix A* A

is

Hermitian and all of its

eigenvalues are nonnegative, as shown in the proof of Theorem 7.5. Let

it

have

the eigenvalues

counted according to their multiplicity, and let

u(l),

...

,

u<n>

be the correspond-

ing eigenvectors, arranged as an orthonormal basis for

en.

For a general X E

en,

Write x as

Then

and

I!Axll~

=(Ax,

Ax)=

(x,

A*Ax)

n

x = L

ajuU>

j=l

n n

A*

Ax

= " a .A*

AuU>

=

"'

a),

.uU>

L..J

L..Jj

j=l

n

~

A1

L la)

2

=

AIIIxll~

j=l

using (7.3.20) to calculate

llxlh-

Thus

(7.3.20)

VECTOR AND MATRIX NORMS

489

Equality follows by noting that if x =

u(l>,

then

llxll

2

= 1

and

I!Axll~

=

(x,

A*Ax)

=

(u(l>,

A

1

u(l>)

= A

1

This proves

(7j.19),

since A

1

= ra(A* A).

It

can

be

shown that

AA*

and A* A

have the same nonzero eigenvalues (see Problem 19); thus, ra(AA*) = ra{A*

A),

an

alternative formula for (7.3.19).

It

also proves

IIA!b

=

IIA*II2

(7.3.21)

This is not true for the previous matrix norms.

It

can

be

shown fairly easily that if A is Hermitian, then

{7.3.22)

This is left as Problem 27.

Example Consider the matrix

Then.

IIAih

= 6

IIAib

=

h5

+ f221

~

5.46

IIAII""

= 7

As

an

illustration

of

the inequality (7.3.23)

of

the following theorem,

5 +

v'33

rAA)

=

2

~

5.37

<!!Alb

Theorem 7.8 Let A

be

an

arbitrary square matrix. Then for

any

operator matrix

norm,

{7.3.23)

Moreover,

if

f > 0 is given, then there

is

an

operator matrix norm,

denoted here by

11·11.,

for which

(7.3.24)

Proof

To

prove (7.3.23), let

II

·

II

be

any matrix

norm

with

an

associated

compatible vector norm

II

·

llu·

Let A

be

the eigenvalue

in

o(A)

for which

and

let x be an associated eigenvector,

llxllv

= 1. Then

which proves (7.3.23).

I

490 LINEAR ALGEBRA

The proof of (7.3.24) is a nontrivial construction, and a proof

is

given

in Isaacson and Keller (1966, p. 12).

•

The

following corollary

is

an easy,

but

important, consequence of Theo-

rem 7.8.

Corollary

For

a square matrix

A,

r.,(A) < 1 if and only if

IIAII

< 1 for some

operator matrix norm.

•

Tiris

result can be used to prove Theorem 7.9 in the next section,

but

we

prefer

to use the

Jordan

canonical form, given in Theorem 7.6. The results (7.3.22) and

Theorem 7.8 show that

r.,(A) is almost a matrix· norm, and this result is used in

analyzing the rates of convergence for some

of

the iteration methods given in

Chapter 8 for solving linear systems of equations.

7.4 Convergence

and

Perturbation Theorems

The

following results are the theoretical framework from which

we

later construct

error analyses for numerical methods for linear systems

of

equations.

Theorem 7.9 Let A be a square matrix of order n. Then Am converges to the

zero matrix

as

m

-+

co

if and only if r.,(A) <

1.

Proof

We use Theorem

7.6

as a fundamental tool. Let J be the Jordan

canonical form for

A,

p-

1

AP

= J

Then

(7 .4.1)

and

Am-+ 0 if and only if

1m·:.....

0.

Recall from (7.2.27) and (7.2.28) that

J

can

be

written as

J=D+N

in which

contains the eigenvalues

of

J (and

A),

and

N is a matrix for which

N"=O

By

examining the structure

of

D and N, we have

DN

= ND.

Then

CONVERGENCE AND PERTURBATION THEOREMS 491

and using

Nj

= 0 for j;;:: n,

(7 .4.2)

Notice that the powers

of

D satisfy

m-j;;::m-n-+oo

as

m-+oo

(7.4.3)

We need the following limits:

For

any

positive c < 1

and

any r

;;::

0,

(7 .4.4)

m-+

oo

This can be proved using L'Hospital's rule from elementary calculus.

In (7.4.2), there are a fixed number

of

terms, n + 1, regardless

of

the

size

of

m,

and we can consider the convergence

of

Jm by considering

each

of

the individual terms. Assuming ra(A) < 1, we know that all

1-h;l

< 1, i = 1,

...

,

n.

And

for any matrix norm

Using the row norm, we have that the preceding is bounded

by

which converges to zero as m

-+

oo,

using (7.4.3) and (7.4.4), for 0

:$;

j :$;

n. This proves half

of

the theorem, namely that if ra(A) <

1,

then

Jm

and

Am, from (7.4.1), converge to zero as

m-+

oo.

Suppose that ra(A);;::

1.

Then let A

be

an

eigenvalue

of

A for which

i.hl

;;::

1, and let x

be

an

associated eigenvector,

x-=!=

0.

Then

and clearly this does

not

converge to zero as m

-+

oo.

Thus it is

not

possible that

Am-+

0,

as that would

implyAmx-+

0. This completes the

proof. •

Theorem 7.10 (Geometric Series) Let A

be

a square matrix.

If

ra(A) <

1,

then

(I-

A)-

1

exists, and it can be expressed as a convergent series,

( )

-1

2

I-A

=l+A+A

+···+Am+···

(7 .4.5)

Conversely, if the series

in

(7.4.5) is convergent, then ra(A) <

1.

Proof Assume ra(A) <

1.

We show the existence

of

(I-

A)-

1

by

proving the

equivalent statement

{3)

of

Theorem 7.2. Assume

(I-

A)x

= 0

Atkinson K. An Introduction to Numerical Analysis

Подождите немного. Документ загружается.