стр. 35 |

a

Figure 10.3: De nition of the normal vector to a plane.

Up to this point the plane was de ned by the vectors a and b (or equivalently by the

^

orthonormal unit vectors ^ and b?). However, a plane can also be de ned by the unit

a

vector n that is perpendicular to the plane, see gure (10.3). In fact, the unit vectors ^,

^ a

^? and n form a complete orthonormal basis of the three-dimensional space. According

b ^

aa ^ ^? ^ ^

to equation (10.13) this implies that ^^T +b?bT + nnT = I. With (10.18) this implies that

the projection operator P can also be written as

P = I n nT :

^^ (10.19)

;

Problem e: Give an alternative derivation of this result. Hint, let the operator in equa-

tion (10.19) act on an arbitrary vector v.

10.3 The Householder transformation

Linear systems of equations can be solved in a systematic way by sweeping columns of the

matrix that de nes the system of equations. As an example consider the system

x + y + 3z = 5

+ 2z = 1 (10.20)

;x

2x + y + 2z = 5

10.3. THE HOUSEHOLDER TRANSFORMATION 109

This system of equations will be written here also as:

0 1

B 113 5

1C

j

@ A

02 (10.21)

;1 j

212 5

j

This is nothing but a compressed notation of the equations (10.20), the matrix shown

in (10.21) is called the augmented matrix because the matrix de ning the left hand side

of (10.20) is augmented with the right hand side of (10.20). The linear equations can

be solved by adding the rst row to the second row and subtracting the rst row twice

from the third row, the resulting system of equations is then represented by the following

augmented matrix: 0 1

113 5

B0 1 5 6C

j

@ A (10.22)

j

0 ;1 ;4 j ;5

Note that in the rst column all elements below the rst elements are equal to zero. By

adding the second row to the third row we can also make all elements below the second

element in the second column equal to zero:

0 1

B1 1 3 5

6C

j

@0 1 5 A (10.23)

j

001 1

j

The system is now in upper-triangular form, this is a di erent way of saying that all matrix

elements below the diagonal vanish. This is convenient because the system can now be

solved by backsubstitution. To see how this works note that the augmented matrix (10.23)

is a shorthand notation for the following system of equations:

x + y + 3z = 5

y + 5z = 6 (10.24)

z=1

The value of z follows from the last equation, given this value of z the value of y follows

from the middle equations, given y and z the value of x follows from the top equation.

Problem a: Show that the solution of the linear equations is given by x = y = z = 1.

For small systems of linear equations this process for solving linear equations can be

carried out by hand. For large systems of equations this process must be carried out on a

computer. This is only possible when one has a systematic and e cient way of carrying

out this sweeping process. Suppose we have an N N matrix A:

0 1

a11 a12 a1N

B a2N C

A=B C

a21 a22

B C

.. C : (10.25)

B .. .. ...

@ .A

. .

aN1 aN2 aNN

CHAPTER 10. LINEAR ALGEBRA

110

We want to nd an operator Q such that when A is multiplied with Q all elements in the

rst column are zero except the element above or on the diagonal, i.e. we want to nd Q

such that: 00 0 1

B a0 a12 a1N 0

11 0

a02N C

QA = B .. .. . . .. C :

B a22 C (10.26)

B. . . .C

@ A

0 aN2 aNN

0 0

This problem can be formulated slightly di erently, suppose we denote the rst columns

of A by the vector u: 0 1

a11

B a21 C

uB C

B C

.. C : (10.27)

B

@ .A

aN1

The operator Q that we want to nd maps this vector to a new vector which only has a

nonzero component in the rst element:

00 1

B a0

11 C0

Qu = B .. C=a ^

B C 11 e1 (10.28)

B. C

@ A

0

where ^1 is the unit vector in the x1 -direction:

e

01

B1C

стр. 35 |