Professor Dave here, I want to teach you the Gram-Schmidt Process.
In the previous tutorial, we learned all about orthogonal vectors, and how we can generate
from these a set of orthonormal vectors, by taking each vector and dividing it by its length.
This makes each vector’s length equal to 1, and since they were already orthogonal,
the new vectors become orthonormal.
But what if we start with a set of vectors that are not already orthogonal?
Furthermore, how do we go about making an orthonormal basis for a vector space given
any set of vectors that form a basis?
To do this, we need to learn something called the Gram-Schmidt process, so let’s take
a look at this now.
To see how this works, let’s examine the vectors v1 to vn, which serve as a basis for
the vector space V. Our only requirement for these vectors is that they form a basis, we
are no longer assuming any orthogonality between them.
The Gram-Schmidt Process takes these vectors and forms a new, orthogonal set of basis vectors,
which we will label u1 to un.
The process goes as follows.
First, start by setting the first new vector u1 equal to the first basis vector v1.
For the second step, take the second vector v2 and subtract from it the inner product
between v2 and u1, divided by the length of u1 squared, times the vector u1.
So all together, that looks like this.
Then the third step will be to take the vector v3 and subtract a similar term, the only difference
is that now we take the inner product between v3 and u1 in the numerator, and then we also
subtract another term, which is the inner product between v3 and u2, divided by the
length of u2 squared, times u2.
At this point you may notice a pattern emerging.
For each new vector, we must subtract an additional term that involves the inner product of the
current v vector with each previously found u vector, so we will need one more such term
for each vector.
The reason we need to do this is that we are subtracting off any part of the v vector that
is not orthogonal to the new vectors we have found, leaving only the orthogonal part.
To make things a little more succinct, each of these new vectors after the first one can
be put into summation notation as follows: uk equals vk minus the sum over i from 1 to
(k – 1) of the inner product between vk and ui, divided by the length of ui squared,
times ui.
If this notation is unfamiliar go back and check out some of my tutorials on sums, otherwise
we can quickly see how the orthogonal basis we just wrote can be derived from this expression.
Some useful tips to help remember how this looks include noting that the only v vector
that appears in the formula has the same number as the u that is being found.
Also, every other u vector that has already been found will show up in a specific term
in the remaining v vectors.
Another helpful feature is that u1 has one term in its formula, u2 has two, u3 three,
and so on.
For ordinary real vectors, what we mean by inner product is simply the vector dot product.
And recall that the length of a vector is simply the square root of its dot product
with itself.
So just considering this case, we can rewrite these terms with dot products.
This might all look a bit overwhelming at first glance, but let’s look at an example
and take it step by step.
Consider the basis vectors for R3: v1 = (1, -1, 1), v2 = (1, 0, 1), and v3 = (1, 1, 2).
We always start by setting our first vector u1 equal to the first basis vector, so u1
equals (1, -1, 1).
Now we get to step two where we take our second vector, v2, and subtract v2 dot u1 divided
by u1 dot u1, times u1.
Well v2 dot u1 will be (1 times 1) + (0 times 1) + (1 times 1) or simply 2.
Then, u1 dot u1 will be (1 times 1) + (-1 times -1) + (1 times 1), or 3.
So u2 equals (1, 0, 1) – two thirds times (1, -1, 1).
Simplifying this expression, we get u2 equals (1/3, 2/3, 1/3).
Finally for the third vector, u3, we will take v3 minus (v3 dot u1) over (u1 dot u1)
times u1, minus (v3 dot u2) over (u2 dot u2) times u2.
Now simplifying, v3 dot u1 is (1 times 1) + (1 times -1) + (2 times 1) which is 2.
We already know that u1 dot u1 is 3, so let’s just use that.
Then v3 dot u2 is (1 times 1/3) + (1 times 2/3) + (2 times 1/3) which equals 5/3.
And then u2 dot u2 is (1/3 times 1/3) + (2/3 times 2/3) + (1/3 times 1/3) which becomes
1/9 + 4/9 + 1/9.
This is 6/9, which simplifies to 2/3.
Plugging in all these dot products we get u3 equals (1, 1, 2) minus two thirds times
(1, -1, 1) minus five thirds over two thirds, which simplifies to five halves, times (1/3,
2/3, 1/3).
Lastly, going through the vector addition, we end up with u3 = (-1/2, 0, 1/2).
These three vectors form an orthogonal basis.
Now, if we wanted an orthonormal basis, as we know, we would take each of these resultant
vectors and do what we have already learned, dividing each vector by its length, thus creating
a new set of vectors of length one.
And since they are already orthogonal, these vectors will be orthonormal.
To be thorough, let’s go ahead and do this for the three vectors we just found, u1 = (1,
-1, 1), u2 = (1/3, 2/3, 1/3), and u3 = (-1/2, 0, 1/2).
We know that u1 dot u1 equals 3, so the length of u1 is root 3.
We also saw that u2 dot u2 was 2/3, so the length of u2 is root (2/3).
We must still calculate u3 dot u3, which ends up being (-1/2 times -1/2) + (0 times 0) +
(1/2 times 1/2), which equals 1/2.
So the length of u3 is root (1/2).
Now taking u1 and dividing by its length we get (1/root 3, -1/root 3, 1/root 3).
Taking u2 and dividing by its length we get (1/root 6, 2/root 6, 1/root 6).
Finally, dividing u3 by its length we get (- root 2/2, 0, root 2/2).
These are the orthonormal basis vectors we obtain from our original basis, thanks to
the Gram-Schmidt Process.
Being able to generate an orthonormal basis is a useful tool, as the bases themselves
can be very helpful for certain calculations.
This process also works for different kinds of vector spaces, such as ones involving functions,
it just changes how we compute the inner product.
Now that we’ve gone over the process of finding an orthonormal basis from any existing
basis vectors, let’s check comprehension.