Agoston M.K. Computer Graphics and Geometric Modelling: Mathematics

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

B.9 The Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 850

B.10 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 851

B.11 Extension Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855

B.12 Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859

Appendix C: Basic Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860

C.1 More on Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . 860

C.2 Inner Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862

C.3 Matrices of Linear Transformations . . . . . . . . . . . . . . . . . . . . . . . 865

C.4 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 870

C.5 The Dual Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873

C.6 The Tensor and Exterior Algebra . . . . . . . . . . . . . . . . . . . . . . . . . 875

Appendix D: Basic Calculus and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 889

D.1 Miscellaneous Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 889

D.2 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892

D.3 Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894

D.4 The Lebesgue Integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896

Appendix E: Basic Complex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898

E.1 Basic Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898

E.2 Analytic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899

E.3 Complex Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 902

E.4 More on Complex Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903

E.5 Miscellaneous Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905

Appendix F: A Bit of Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 907

F.1 The Condition Number of a Matrix . . . . . . . . . . . . . . . . . . . . . . . 907

F.2 Approximation and Numerical Integration . . . . . . . . . . . . . . . . . . 908

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Abstract Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Advanced Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Algebraic Curves and Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Algebraic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916

Algebraic Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916

Analytic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917

Complex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917

Conics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917

Cyclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917

Differential Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918

Differential Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918

Geodesics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

Geometric Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

Contents xiii

Offset Curves and Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920

Projective Geometry and Transformations . . . . . . . . . . . . . . . . . . . . . . . . . 920

Quadrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920

Real Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920

Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921

Bibliographic Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956

Index of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 959

xiv Contents

CHAPTER 1

Linear Algebra Topics

1.1 Introduction

This chapter assumes a basic knowledge and familiarity of linear algebra that is

roughly equivalent to what one would get from an introductory course in the subject.

See Appendix B and C for the necessary background material. In particular, we assume

the reader is familiar with the vector space structure of n-dimensional Euclidean

space R

and its dot product and associated distance function. The object of this

chapter is to discuss some important topics that may not have been emphasized or

even covered in an introductory linear algebra course. Those readers with a weak

background in abstract linear algebra and who have dealt with vectors mostly in the

context of analytic geometry or calculus topics in R

or R

will also get a ﬂavor of the

beauty of a coordinate-free approach to vectors. Proofs should not be skipped because

they provide more practice and insight into the geometry of vectors. The fact is that

a good understanding of (abstract) linear algebra and the ability to apply it is essen-

tial for solving many problems in computer graphics (and mathematics).

As in other places in this book we have tried to avoid generality for generality’s

sake. By and large, the reader can interpret everything in the context of subspaces of

; however, there are parts in this chapter where it was worthwhile to phrase the

discussion more generally. We sometimes talk about inner product spaces, rather than

just sticking to R

and its dot product, and talk about vector spaces over other ﬁelds,

the complex numbers C in particular. This was done in order to emphasize the general

nature of the aspect at hand, so that irrelevant details do not hide what is important.

Vector spaces over the complex numbers will be important in later chapters.

Geometry is concerned with lots of different types of spaces. This chapter is about

the simplest of these, namely, the linear ones, and some related topics. Hopefully,

much of the material that is covered is review except that we shall approach the

subject here, like in many other places, with a vector approach. Sections 1.2–1.5

review the deﬁnition and basic properties of k-dimensional planes in R

. We also look

at the abstract deﬁnition of angle and some important concepts related to ortho-

gonality, such as that of the orthogonal projection of a vector. Next, in Sections 1.6

and 1.7 we discuss the extremely important concepts of orientation and convexity.

Some basic results on the diagonalization of maps and matrices in Section 1.8 lead

to a discussion of bilinear maps and quadratic forms in Section 1.9. Section 1.10

describes a general version of the three-dimensional cross product. Finally, Section

1.11 deﬁnes the generalized inverse of a transformation and matrix along with several

applications.

1.2 Lines

Our ﬁrst goal in this chapter is to characterize linear subspaces of Euclidean space

and summarize some basic facts about them. There is not much to say about points,

the 0-dimensional linear subspaces, but the one-dimensional subspaces, namely,

“straight” lines, are a special case that is worth looking at separately.

First of all, let us consider lines in the plane. The usual deﬁnition of a line in this

case is as the set of solutions to a linear equation.

Deﬁnition. (The equation deﬁnition of a line in the plane) Any set L in R

of the form

(1.1)

where a, b, and c are ﬁxed real constants, is called a line. If a = 0, then the line is

called a horizontal line. If b = 0, then the line is called a vertical line. If b π 0, then

-a/b is called the slope of the line.

Although an equation deﬁnes a unique line, the equation itself is not uniquely

deﬁned by a line. One can multiply the equation for a line by any nonzero constant

and the resultant equation will still deﬁne the same line. See Exercise 1.2.1.

The particular form of the equation in our deﬁnition for a line is a good one from

a theoretical point of view, but for the sake of completeness we list several other well-

known forms that are often more convenient.

The slope-intercept form: The line with slope m and y-intercept (0,b) is deﬁned by

(1.2)

The point-slope form: The line through the point (x

) with slope m is deﬁned

(1.3)

The two-point form: The line through two distinct points (x

) and (x

) is

deﬁned by

(1.4)

Note that equations (1.2) and (1.3) above apply only to nonvertical lines.

When one wants to deﬁne lines in higher dimensions, then one can no longer use

a single equation and so we now give an alternative deﬁnition that works in all dimen-

xx-=

()

yy mxx-= -

()

ymxb=+.

x y ax by c a b,,,,,

()

{}

2 1 Linear Algebra Topics

sions. It is based on the intuitive geometric idea that a line is deﬁned by a point and

a direction.

Deﬁnition. (The point-direction-vector deﬁnition of a line) Any subset L of R

the form

(1.5a)

where p is a ﬁxed point and v is a ﬁxed nonzero vector in R

, is called a line (through

p). The vector v is called a direction vector for the line L. By considering the compo-

nents of a typical point x = p + tv in L separately, one gets equations

...

(1.5b)

that are called the parametric equations for the line.

In the case of the plane, it is easy to show that the two deﬁnitions of a line agree

(Exercise 1.2.2). The deﬁnition based on the equation in (1.1) is an implicit deﬁni-

tion, meaning that the object was deﬁned by an equation, whereas the deﬁnition using

(1.5a) is an explicit deﬁnition, meaning that the object was deﬁned in terms of a para-

meterization. We can think of t as a time parameter and that we are walking along

the line, being at the point p + tv at time t.

Note that the direction vector for a line is not unique. Any nonzero multiple of v

above would deﬁne the same line. Direction vectors are the analog of the slope of a

line in higher dimensions.

1.2.1. Example. To describe the line L containing the points p =(0,2,3) and q = (-2,1,-1).

Solution. The vector pq = (-2,-1,-4) is a direction vector for L and so parametric

equations for L are

1.2.2. Example. Suppose that the parametric equations for two lines L

and L

are:

(1.6)

Do the lines intersect?

Solution. We must solve the equations

=- +

12::xt xt=- =+

x p tv t

nn n

=+ Œ,,R

xptv

11 1

22 2

pv R+Œ

{}

tt ,

1.2 Lines 3

for s and t. The ﬁrst two equations imply that t =-1 and s = 0. Since these two values

also satisfy the third equation, the lines L

and L

intersect at the point (2,1,-2).

Note. A common mistake when trying to solve a problem like that in Example 1.2.2

is to use the same variable for both s and t. Just because lines intersect does not mean

that persons “walking” along the lines will get to the intersection point at the same

“time.”

Deﬁnition. Points are said to be collinear if they lie on the same line and non-

collinear, otherwise.

Deﬁnition. Let p, q Œ R

. The set

(1.7)

is called the segment from p to q and is denoted by [p,q]. The points of [p,q] are said

to lie between p and q.

Note that [p,q] = [q,p] (Exercise 1.2.5). A segment basically generalizes the notion

of a closed interval of the real line, which explains the notation, but the two concepts

are not quite the same when n = 1 (Exercise 1.2.6). The following proposition gives a

very useful alternative characterization of a segment.

1.2.3. Proposition. Let p, q Œ R

. Then

(1.8)

Proof. Let

In order to show that [p,q] = S we must prove the two inclusions [p,q] Õ S and

S Õ [p,q].

To prove that [p,q] Õ S, let x Œ [p,q]. Then x = p + tpq for some t with 0 £ t £ 1.

It follows that

so that x Œ S.

To prove that S Õ [p,q], let x Œ S. Since |px| + |xq| = |pq| = |px + xq|, the triangle

inequality implies that the vectors px and xq are linearly dependent. Assume without

loss of generality that px = txq. Then

px xq pq pq pq+= +- =tt1,

S x px xq pq=+=

{}

p q x R px xq pq,=

[]

Œ+=

{}

ppq+Œ

[]

{}

tt01,

212

-=+

+=-

-+ =-+

4 1 Linear Algebra Topics

In other words,

(1.9)

It is easy to show that the only solutions to (1.9) are 0 £ t. But the equation px = txq

can be rewritten as

which shows that x Œ [p,q] since 0 £ t/(1 + t) £ 1.

The next proposition proves another fairly innocuous looking fact. It also plays a

key role in the proofs of a number of future theorems.

1.2.4. Proposition. Let p be a point on a line L. If c > 0, then there are two and

only two points x on L that satisfy the equation |px| = c.

Proof. Let q be a point on L distinct from p. Then any point x on L has the form

x = p + spq and hence c = |px| = |s| |pq|. The only solutions to |s| = c/|pq| are s =±t,

where t = c/|pq|. In other words,

and the proposition is proved.

Finally,

Deﬁnition. Let p, v, q Œ R

. If v π 0, then the ray from p in direction v, denoted by

ray(p,v), is deﬁned by

If p π q, then the ray from p through q, denoted by [pq >, is deﬁned by

1.3 Angles

The intuitive notion of the angle between two vectors is something that one picks up

early, probably while studying Euclidean geometry in high school. In this section we

show that there is a very simple rigorous deﬁnition of this that is also very easy to

compute. Everything we do here holds for an arbitrary real vector space with an inner

product, but, for the sake of concreteness, we restrict the discussion to Euclidean

space with its standard dot product.

pq p pq>

()

[

=,ray .

ray t tpv p v,

()

=+ £

{}

xp pq xp pq=+ =-tor t

xp pq=+

tt+=+11

ttxq xq xq xq+= +.

1.2 Lines 5

Deﬁnition. Let u, v Œ R

. Deﬁne the angle q between the vectors u and v, denoted by

–(u,v), as follows: If either u or v is the zero vector, then q is zero; otherwise, q is that

real number such that

Note the purely formal aspect of this deﬁnition and that we need the Cauchy-

Schwarz inequality to insure that the absolute value of the quotient in (a) is not bigger

than 1 (otherwise there would be no such angle). The motivation behind the deﬁni-

tion is the law of cosines from Euclidean geometry shown in Figure 1.1. To see this,

substitute |p|, |q|, and |p + q| for a, b, and c, respectively, and simplify the result.

Now if |u| = 1, then

which one will recognize as the length of the base of the right triangle with hypotenuse

v and base in the direction of u. See Figure 1.2. This means that we can give the fol-

lowing useful interpretation of the dot product:

Deﬁnition. Let u, v Œ R

. If the angle between the two vectors u and v is p/2, then

they are said to be perpendicular and we shall write u ^ v. If the angle between them

is 0 or p, they are said to be parallel and we shall write u || v.

uv v n u∑

()

= is the signed length of “the orthogonal projection of on whenever ”.1

uv v∑= cos q,

cos qqp=

∑

££

,.and 0

6 1 Linear Algebra Topics

|u| = 1

u·v = |v| cos q

|v| cos q

|v|

Figure 1.2. Interpreting the dot product.

+ b

– 2ab cos θ = c

Figure 1.1. The law of cosines.

Deﬁnition. Two vectors u and v in an arbitrary vector space with inner product •

are said to be orthogonal if u•v = 0.

1.3.1. Theorem. Let u, v Œ R

(1) u ^ v if and only if u and v are orthogonal.

(2) u || v if and only if u and v are linearly dependent.

Proof. Most of the theorem follows easily from the deﬁnitions. Use the Cauchy-

Schwarz inequality to prove (2).

Although the words “orthogonal” and “perpendicular” have different connota-

tions, Theorem 1.3.1 shows that they mean the same thing and we have an extremely

easy test for this property, namely, we only need to check that a dot product is zero.

Checking whether two vectors are parallel is slightly more complicated. We must

check if one is a multiple of the other.

Finally, note that if u = (u

,...,u

) is a unit vector, then u

= u•e

= cos q

, where

is the angle between u and e

. This justiﬁes the following terminology:

Deﬁnition. If v is a nonzero vector, then the ith component of the unit vector

is called the ith direction cosine of v.

1.4 Inner Product Spaces: Orthonormal Bases

This section deals with some very important concepts associated with arbitrary vector

spaces with an inner product. We shall use the dot notation for the inner product. The

reader may, for the sake of concreteness, mentally replace every phrase “vector space”

with the phrase “vector subspace of R

or C

,” but should realize that everything we

do here holds in the general setting.

Probably the single most important aspect of inner product spaces is the existence

of a particularly nice type of basis.

Deﬁnition. If v

, v

,..., v

are vectors in an inner product space, we say that they

are mutually orthogonal if v

• v

= 0 for i π j. A set of vectors is said to be a mutually

orthogonal set if it is empty or its vectors are mutually orthogonal.

Deﬁnition. Let V be an inner product space and let B be a basis for V. If B is a

mutually orthogonal set of vectors, then B is called an orthogonal basis for V. If, in

addition, the vectors of B are all unit vectors, then B is called an orthonormal basis.

In the special case where V consists of only the zero vector, it is convenient to call the

empty set an orthonormal basis for V.

Orthonormal bases are often very useful because they can greatly simplify com-

putations. For example, if we wanted to express a vector v in terms of a basis v

, v

..., v

, then we would normally have to solve the linear equations

vv v v=+++aa a

nn11 22

...

1.4 Inner Product Spaces: Orthonormal Bases 7

for the coefﬁcients a

. On the other hand, if we have an orthonormal basis, then it is

easy to check that a

= v • v

and there is nothing to solve. Our ﬁrst order of business

therefore is to describe an algorithm, the Gram-Schmidt algorithm, which converts an

arbitrary basis into an orthonormal one.

The Gram-Schmidt algorithm is an algorithm that actually can be applied to any

collection of vectors and will produce an orthonormal basis for the space spanned by

these vectors. We shall illustrate how this process works in the case of two and three

vectors.

Let v

and v

be two nonzero vectors. Then u

= (1/|v

|)v

is a unit vector. We want

to ﬁnd a unit vector u

that is orthogonal to u

and so that u

and u

span the same

space as v

and v

. Consider Figure 1.3. If we could ﬁnd the orthogonal vector w, then

all we would have to do is make w have unit length to get u

(assuming that w is not

zero). But w can easily be computed from the “orthogonal projection” v of v

on u

and we pointed out in Section 1.3 that v could be found using the dot product. The

following equations now summarize how one can compute the orthonormal basis u

and u

(1.10)

where

To see that these computations really do produce orthogonal vectors it sufﬁces to show

that the dot product of the vectors w and u

is zero. But

Next, suppose that we want to construct an orthonormal basis for the space

spanned by three vectors v

, v

, and v

. See Figure 1.4(a). First, apply the construc-

wu v v uu u

vu vuuu

∑= - ∑

()

[]

∑

=∑- ∑

()

∑

()

122111

21 2111

wv v

vvuu

=∑

()

211

8 1 Linear Algebra Topics

Figure 1.3. A simple orthogonal projection.