Dr. Robert van de Geijn: Now we

arrive at the very important topic of Gram-Schmidt orthogonalization. This is also known as

the Gram-Schmidt process. It starts with a set of

linearly independent vectors, and it results in a set of

mutually orthonormal vectors that span the same space as

those original vectors did. So what about orthogonal

basis, or orthonormal basis? Here’s the problem statement. Using the case where you have

three vectors as an example, you start with three vectors. We would like to find three

vectors, q0 through q2 such that the span of those three vectors

is the same as the span of the three vectors with which we start. And how do we do that? Well, step one is to normalize a. How do we visualize that? So here we visualize these

three vectors, a0, a1, and a2. Now, they’re are a

little bit hard to see until we start rotating this picture. And what you notice is that a0 and a1

are in the plane that we color blue, and then a2 sticks out of the plane. So it’s not in the space

spanned by the vectors a0, a1. And we also notice that a0 and a1

are not perpendicular to each other. And it’s probably a

little bit harder to see whether a2 is

perpendicular to a0 and a1. We’ll have a better look at that later. Here we visualize the first step

of the Gram-Schmidt process. Let’s let this spin for a little bit,

until we get a good view of this. That’s probably good enough. We start with the

vector a0, we want to be a vector of length one in

the same direction as a0. So the thick black arrow here

is in the same direction as a0, but is now of length 1. So what is it that we just

did in our visualization. We took our vector a, and we made it of

length 1 by dividing it by its length. And then we called the result vector of that q0. Another way of looking at that is

that we first computed a scalar. Later we’re going to see that calling

that scalar rh0 0, 0, is convenient. And then we divided a0 by rho 0 , 0 ,

which is then equivalent to dividing a 0 by its length. The result of that is one vector, q0,

in the direction of a0 of length one. So if we do this for our

example, we feed in the vector 1, 1, 1, we compute its length,

which is the square root of three, and then we take that vector,

we divide it by its length, q3, and there are several different

ways in which we could write it. It’s going to turn out

that writing it like this is going to be quite

convenient later on. Or, of course, you can

multiply through and end up with this vector that’s a square root

of 3 over 3 for each of its components. Let’s see what we have to do

to compute q1 orthogonal to q0. In this step, we want to compute a

component of a1 perpendicular to q0, and then normalize

that to be of size one. So how does that work? Well, let’s let this picture

rotate into a little bit better– There, that should be good. What we have here is the vector

a1, which is of some length. The component of a1 in the

direction of the vector q0 is given by the inner

product of q0 with a1– That’s the length– times the

vector q0, which is of length 1. So that gives us this

dashed line right here. And then if we take that vector

and we subtract it off of a1, we get the vector perpendicular. This dashed vector plus that vector is

equal to a1, therefore if you take a1, you subtract out the component

in the direction of q0, you end up with a component

that’s perpendicular to q0, and that’s the component

of a1 perpendicular to q0. Now, if you take that

vector and you simply move it so that it’s

rooted at the origin, then we have a vector that is

perpendicular, or orthogonal to q0. All we then have to do is make

that vector of length one, and we have two vectors that are

mutually orthonormal, q0 and q1. And if you look at

this picture carefully, you will notice that this vector points

in the same direction as a1 perp. Now, if we let this

rotate, you will also notice that the space

spanned by a0 and a1 is the same space as is

spanned by q0 and q1. So what did that animation show us? Well, it showed us how to compute the

component of a perpendicular to q0. And how did we do that? We did that by taking a1, we

then computed the component of a1 in the direction of q0. And this is the formula for that. And we subtracted that

component in the direction of q0 from a1, leaving us with the

component of a1 perpendicular to q0. We’ll call that a1 perp. It will become convenient later

on to do this in two steps, but first is to compute the

inner product of q0 with a1, and the second one is then to subtract

off that multiple of q0 from a1 to compute a1 perp. Now let’s look and see how this works

with the specific example with which we started. This here is the vector q0. We take the inner product of the

vector with this new vector, 1, 2, 3. If we work it out, that turns out

to be 2 times the square root of 3, if I did this right. Once we have that scalar,

we then take the vector a1, we subtract off rho 0, 1 times q0. Now it’s convenient that this square

root of three times that square root of three is three, so that this simply

becomes minus 2 times the vector 1, 1, 1. And if you work through it, you end

up with this vector, minus 1, 0, 1. And that is the component of a1

perpendicular to the vector q0. So now we have two vectors, q0 and a1

perp that are orthogonal to each other. The problem is that a1

perp is not of length one. To fix that, what we do is

we take our vector a1 perp, and we divide it by its length,

and we call the result of that q1. We will again do this in two steps. The first is to compute

the length of a1 perp, and the second one is to

divide a1 perp by that length. If we do that with the

specific example we have, this was the vector that we computed

as the component of a1 perpendicular to q0. The length of that is square root of

two, and then if we take that vector and we divide it by

the square root of two, we can write that either

as this vector right here, or we can explicitly multiply through

to get the individual components.

Extremely wonderful explanation!