The Gram-Schmidt Procedure

Names:

When you are finished, please 
	1) “Print” the lab to a pdf file.
	2) Submit it on Gradescope. One person can submit on behalf of the entire group. Make sure to label all problems to the correct pages, and include all group members on the submission.
	3) Email the .nb and .pdf file to npflueger@amherst.edu. CC all group members on the email.
	4) Please submit the lab by Wednesday next week (it is ok if it takes a few more days).

We discussed on Tuesday the notion of an orthonormal basis, and some of the reasons why these are especially convenient bases in many situations. This lab will explore a procedure that can be used to produce an orthonormal basis from a non - orthonormal basis, called the Gram - Schmidt procedure (this procedure is developed in more detail in section 6.3 of the text).  Mathematica can streamline the process by doing the messy arithmetic for us.
   
A basis for an inner product space is called orthonormal if any two different basis elements are orthogonal, and each basis element has norm (length) 1.

Syntax note: 
You can compute dot products in Mathematica using a period between two vectors, as in the cell below (hit shift-enter to try it, and make sure the answer is what you expect).

{1,2,3} . {4,5,6}

Gram-Schmidt using the dot product

The illustrate Gram-Schmidt, we first consider the case of (R^n), equipped with the dot product.

The basic idea is to take each vector in the given basis and subtract from it the parts that duplicate the previous vectors.  Please work through the following example that shows how to do the Gram-Schmidt procedure before doing the exercises.

Consider the basis { (({{({{1}, {0}})}, {1}})) , (({{({{1}, {1}})}, {0}})) , (({{({{2}, {1}})}, {2}})) } for (R^3).  (Take my word for it that this is a basis.)

Enter the 3 vectors into Mathematica:

v1={1,0,1};
v2={1,1,0};
v3={2,1,2};

Now we’ll create a new orthogonal basis {w1,w2,w3}. 

Recall the terminology: the projection of one vector onto another is defined by the following formula.
	(Subscript[proj, (OverVector[u])])(OverVector[v]) = (((OverVector[u]) ·(OverVector[v]))/((OverVector[u]) · (OverVector[u])))(OverVector[u])
The meaning of the projection is: it is the multiple of (OverVector[u]) that is closest to (OverVector[v]).

At each step, take the next vector in the given basis and subtract off the projections of that vector onto all previous vectors.

1) Start with v1 as the first vector w1.
2) Next take v2 and subtract off the projection of v2 onto w1 to obtain w2.
3) Then take v3 and subtract off the projections of v3 onto w1 and onto w2 to obtain w3.

The resulting set {w1,w2,w3} will be an orthogonal basis (but may not yet be orthonormal). Note that the dot product of two vectors may be computed using a period in Mathematica.

w1=v1

proj1=(v2.w1)/(w1.w1) *  w1;
w2=v2-proj1

proj1=(v3.w1)/(w1.w1) * w1;
proj2=(v3.w2)/(w2.w2) * w2;
w3=v3-proj1-proj2

Divide each vector by its length, so we get unit vectors, resulting in an orthonormal basis. Recall that length is equal to the square root of the dot product of a vector with itself.

u1=w1/Sqrt[ w1 . w1]
u2=w2/Sqrt[w2 . w2]
u3=w3/Sqrt[w3 . w3]

u1.u2       (* to check that u1 and u2 are orthogonal *)
u1.u3       (* to check that u1 and u3 are orthogonal *)
u2.u3       (* to check that u2 and u3 are orthogonal *)

The resulting orthonormal basis for (R^3) is {(({{(1/(Sqrt[2]))}, {0}, {(1/(Sqrt[2]))}})),(({{(1/(Sqrt[6]))}, {(Sqrt[(2/3)])}, {-(1/(Sqrt[6]))}})),(({{-(1/(Sqrt[3]))}, {(1/(Sqrt[3]))}, {(1/(Sqrt[3]))}}))}.

Exercise 1.  Apply the Gram-Schmidt procedure to the basis { (({{1}, {1}})) , (({{3}, {2}}))} to obtain an orthonormal basis for (R^2).  (If necessary, use the Simplify command to clean up messy results.)

Exercise 2.  Apply the Gram-Schmidt procedure to the basis { (({{({{0}, {3}})}, {4}})) , (({{({{-20}, {27}})}, {11}})) , (({{({{-14}, {-4}})}, {-2}})) } to obtain an orthonormal basis for (R^3).  Check that the vectors are indeed orthogonal by evaluating the dot products of each pair of vectors (so you’ll check 3 dot products).

Exercise 3.  Apply the Gram-Schmidt procedure to the basis { (({{({{1}, {0}})}, {({{0}, {-1}})}})) , (({{({{1}, {2}})}, {({{0}, {-1}})}})) , (({{({{3}, {1}})}, {({{1}, {-1}})}})) , (({{({{0}, {1}})}, {({{1}, {-1}})}})) } to obtain an orthonormal basis for (R^4).  Check that the vectors are indeed orthogonal by evaluating the dot products of each pair of vectors (so you’ll check 6 dot products).

Gram-Schmidt in other inner-product spaces

We now consider Gram-Schmidt in more general inner product spaces. The procedure is the same, except that the formula for projection should use whatever inner product we are interested in, rather than the dot product.
	(Subscript[proj, (OverVector[u])])(OverVector[v]) = ((⟨(OverVector[u]) ,(OverVector[v])⟩)/(⟨(OverVector[u]) , (OverVector[u])⟩))(OverVector[u])
For the next example, we will consider the space (Subscript[P, 3]) of polynomials of degree at most 3, with the following inner product.
	⟨p,q⟩ = (∫_0^1)p(x)q(x)dx
This inner product can be computed in Mathematica using the Integrate command, as in the following example.

p= x^3;
q = x^2;
Integrate[ p * q,{x,0,1}]

Therefore you can compute the projection of one polynomial onto another (with respect to this inner product) with syntax like the following.

projPQ = Integrate[p*q,{x,0,1}] / Integrate[p*p,{x,0,1}] * p // Simplify

Note 1: Although it’s not strictly necessary, I suggest that you add the “// Simplify” command to the end of each line in which you compute a polynomial (as above). This will help make the output more readable.

Note 2: You can save yourself some typing in the exercise below if you first define a “Projection” function that takes p and q as arguments and plugs them into the expression above. You may either look up how to define functions in Mathematica or call me over to ask about it.

Exercise 4.  Apply the Gram-Schmidt procedure to the standard basis {1, x, (x^2), (x^3)}, to obtain an orthonormal basis for  (Subscript[P, 3]), with respect to the inner product given above.