11.3.3 Orthogonal bases (Gram-Schmidt Orthogonalization) Part 1

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.

One thought on “11.3.3 Orthogonal bases (Gram-Schmidt Orthogonalization) Part 1

Leave a Reply

Your email address will not be published. Required fields are marked *