Inner Products and Gram-Schmidt

Review of Norms and Inner Products

Let's recall what the situation is:  inspired by the standard norm,  we elevate its  basic properties into a definition.  This definition gives us the ability to  invent various concepts of  ª lengthº  of vectors,  which is the main purpose of norms.

DEFINITION:  A norm on a vector space  V is a  real valued function  ÷ç v÷ç  defined for all vectors  v  in V which has the following properties:  For all vectors u, v  in  V  and scalars  a, 
	(1)  ÷ç u ÷ç  ³  0  with equality if and only if  v = 0.
	(2)  ÷ç a u ÷ç  =  ½a ½ ÷ç u ÷ç.
	(3)  ÷ç u  +  v ÷ç  £  ÷ç u ÷ç  + ÷ç v ÷ç.
A vector space, together with a norm defined on it, is called a normed vector space.

The classical examples are the  standard  (a.k.a.  Euclidean )  norms:

EXAMPLE 1:  V  =  R3  and  
	÷ç(x1, x2, x3) ÷ç   = Sqrt [ x12 + x22+ x32 ]

EXAMPLE 2:  V  =  C2  and     __         __
	÷ç(z1, z2)÷ç  =   Sqrt [ z1 z1 + z2 z2 ] 

A non-standard example:

EXAMPLE 3:  V = R3  and
	÷ç(x1, x2, x3)÷ç  =  ½ x1 ½ + ½ x2 ½ + ½ x3 ½
	
Norms, by themselves, cannot give us a concept of  ªangle between vectorsº  which we need for ideas like  ª parallelº  and ªperpendicular  ( = orthogonal)º  vectors.  For this we need the concept of an ª inner productº, which is again completely inspired by the standard inner products on a vector space.  Here is the definition:

DEFINITION:  An inner product on a vector space V  is a scalar valued function  <u,v>  defined for all vectors  u, v  in  V  which has the following properties:  For all vectors  u, v, w  in  V  and scalars  a,    ____
	(1)  <u, v>  =  <v,u>    (if  scalars are the reals, ignore the conjugate)
	(2)  <u + v, w>  =  <u, w> + <v, w>
	(3)  <a.u, v>  =  a <u, v>
	(4)  <u, u >  ³  0  with equality if and only if u = 0.
A vector space, together with an inner product on it, is called an inner product space.
	
There are a number of laws that can be deduced from these properties,  e.g., that fact that 
<0, v> = 0  for any vector v.  See your text for a larger listing.  Some of the more important outcomes of the definition are as follows:
(1)  We  can deduce the  Cauchy-Schwarz Inequality:  For all vectors u, v  in   V,
			½<u, v>½2  £  <u, u>.<v, v>
(2)  We can define a norm, called the induced norm, in terms of the inner product:
			÷ç u ÷ç  =  Sqrt [ <u, u> ]
As you might expect,  the standard inner products induce the standard norms (check this).
(3)  Thanks to the  Cauchy-Schwarz inequality we can introduce the angle, t, between two vectors u  and  v  by the formula
			Cos [t]  =  <u, v>/ (÷ç u ÷ç . ÷ç v ÷ç).
In particular, two vectors are orthogonal iff  Cos [t]  = 0,   i.e.,  <u, v> = 0.
(4)  We can  calculate the projection p of the vector  u along the vector a according to the formula
			p = proja (u)  =  (<a, u> / <a, a>)  a
Thus we get that  u = p + (u - p)  is the sum of a vector parallel to a and a vector orthogonal to a.

	
The classical examples are the standard (a.k.a. Euclidean ) inner products:

EXAMPLE 4:  V  =  R3  and  
	<(x1, x2, x3) , (y1, y2, y3)>  =  (x1, x2, x3) .  (y1, y2, y3)  =  x1 y1 + x2 y2 + x3 y3

EXAMPLE 5:  V  =  C2  and                                   __          __
<(z1, z2) , (w1, w2)>  =  (z1, z2) .  (w1, w2)  =  z1 w1 + z2 w2]

A  non-standard  example:

EXAMPLE 6:  V  =  R3  and
	<(x1, x2, x3) , (y1, y2, y3)>   =  4 x1 y1 + 3 x2 y2 + 2 x3 y3
This gives rise to a non-standard norm, namely
	÷ç (x1, x2, x3) ÷ç   =  Sqrt [ 4 x12 + 3 x22 + 2 x32]

We'll see another non-standard example in the third section.

Here are two more definitions that are inspired by the inner product idea and have proved to be useful.  They are motivated by a desire to abstract the good properties of the standard basis e1, e2, ...., en  of  Rn  (or  Cn).

DEFINITION:  a set of vectors  v1, v2, ..., vn  is  an orthogonal set of vectors if 
<vi, vj>  =  0 for all  i ¹ j.   If, in addition, each vi is normal, i.e., has unit length, then we say that the set of vectors is an orthonormal set of vectors.

Note that the property of being an orthonormal or orthogonal set is a property of the whole set of vectors.  The standard example of an orthonormal set is (what else)  the standard basis   {e1, e2, ..., en}.  Here is an orthogonal set of vectors that is not standard (still using the standard inner product, however):  
	v1 = (1, 1, 0),  v2 = (1, -1, 0),  v3 = (0, 0, 1).
Notice that this set of vectors  is  not  orthonormal, since  the first two vectors don't have unit length.  This shortcoming is easy to fix up provided the vectors are all nonzero:  simply divide each vector by its length to obtain a unit length vector.  In this case we would obtain:
	u1 = (1/Sqrt [2]) (1, 1, 0),  u2 = (1/Sqrt [2]) (1, -1, 0),  u3 = (0, 0, 1).
	
Here is an important fact about orthogonal sets of nonzero vectors (notice that automatically includes any orthonormal set of vectors):

FACT:  Any orthogonal set of nonzero vectors is a linearly independent set.
Proof:  Suppose a linear combination of the orthogonal set v1, v2, ...vn of nonzero vectors added up to 0:
	c1 v1 + c2 v2 + ... + cn vn  = 0.
Take the inner product of both sides with the vector vi,  use the linearity property of inner products and obtain that
	0 = <vi, 0>  =  <vi, c1 v1 + c2 v2 + ... + cn vn>
	                    = c1 <vi, v1> + c2 <vi, v2> + ... + cn <vi, vn>
	                    = ci <vi, vi>
But  <vi, vi> = ÷ç vi ÷ç2  ¹ 0, since  vi is not  the zero vector.  Hence, we may divide by  
<vi, vi>  and obtain ci = 0.  This  is true for any index i, so the linear combination must be trivial.  Therefore,  the vectors  v1, v2, ...., vn  form a linearly independent set.  

What good are orthonormal sets?  Here is a nifty application:  suppose we are given a vector  u  in the vector space  V  along with a subspace  W.  The problem is to find the vector in  W  nearest to u.  If you use your 3-D intuition,  visualizing  V  as  R3 and W  as a plane in  R3  through the origin,  you will see that what we are really looking for is the projection  p of the vector  u  into the  subspace  W.  That is,  a vector  p in  W  such that  u - p  is orthogonal to all vectors in  W.   Now  if  u1, ..., un  is an orthonormal basis of W,  this projection is easy to find:

	p = projW (u)  =  <u1, u> u1 + <u2, u> u2 + ... + <un, u> un.

Check for yourself that  u - p is orthogonal to every ui.  Since  every vector in  W  is a combination of these ui's,  it follows that  u - p  is orthogonal to every vector in  W.  This  is exactly what we were looking for.

The Gram-Schmidt Algorithm

Here is the situation:  we have a subspace  W  of R3 given to us by way of a spanning set.
		
		W = lin{v1, v2, v3},

where v1 = {1, -1, 1},  v2 = {1, 2, 1},  v3 = {-1, -3,  0}.  How can we understand what the subspace looks like?

	For one thing, we can replace the spanning set by a basis of the space.   This tells us the fewest number of vectors of  W  needed to generate the other vectors of  W  as linear combinations.  Click on the next cells to determine pivot columns of the Row Echelon Form of  A = {v1, v2, v3}.

v1 = N[{1, -1, 1}]

v2 = N[{2, 2, 1}]

v3 = N[{4, 0, 3}]

a = Transpose[{v1,v2,v3}]

MatrixForm[RowReduce[a]]

Now we see that  v1 and v2 form a basis for W.   In fact, you can figure out a linear combination of v1 and v2 that give v3 from the Row Echelon Form.  See it?  Click on the next cell for a useful definition:

VectorPlot[v_,view_]:= Show[Graphics3D[Join[Map[Line[{{0,0,0},#}]&,v],
		{PointSize[0.02], Map[Point[#]&,v]}]],Axes->Automatic, 
		AxesLabel->{"x","y","z"},
		ViewPoint->view]

Now let's get a picture of the vectors v1, v2, v3.  Click the next cells:

VectorPlot[{v1,v2,v3},{5,-5,10}]

If you're not satisfied with the picture, move the point of your eyeball  {5, -5, 10}  around a bit  and reclick the previous cell to see it from different angles (don't use {0,0,0}).
	Rather than work with the basis v1, v2  of W, we would like to work with something like the standard basis  e1, e2. In other words,  we would rather work with an orthonormal basis of vectors.  Is this possible?  Yes !!  Let's use v1 for our first vector.  But this isn't quite right, since  v1 does not have unit length.  Rather,  let's replace  v1  by the vector 
u1 = v1 / ÷ç v1÷ç:

u1 = v1 / Sqrt[v1.v1]

Next, let's  replace v2  by a vector orthogonal to v1.  In fact, all we have to do is subtract the projection of v2 along u1 from the vector v2 to obtain a vector orthogonal to u1.   This won't be a unit length vector, so let's denote the result by u2'.  By the way, notice that in the following formula for a projection, we don't divide by  the factor  u1.u1.   Why so?

u2p = v2 - (u1.v2) u1

Now let's turn u2' into a unit vector u2 by normalizing it.

u2 = u2p/Sqrt[u2p.u2p]

Finally, let's see what these vectors look like:

VectorPlot[{u1,u2},{5,-5,10}]

If your'e not convinced that these vectors are orthogonal, you could adjust the viewpoint.  Or simply click on the next cell:

u1.u2

What we have now is an orthonormal basis of  W,  namely, the vectors  u1 and u2.  Consider the following problem:  what is the projection of  u  into  W,  where  u  is given by the next cell?   Now that we have an orthonormal basis of  W,  we can use the nice projection formula given in the previous section.  That is the next cell.  Click it, as well as the cells that verify the correctness of our calculations immediately following.

u = {2,1,1}

p = (u1.u)*u1 + (u2.u)*u2

(u-p).u1

(u-p).u2

O.K., now here's the basic goal of the Gram-Schmidt algorithm:  given a linearly independent set of vectors,  v1,  v2,  .... , vn,  we would like to replace these vectors by an orthonormal set of vectors u1,  u2,  .... , un,  such that for 1 £ i £ n,  the vectors  v1, v2, ...., vi  have exactly the same span as the vectors u1,  u2,  .... , ui.

Here's how it is done:  Given that we already have built orthonormal vectors  u1, u2, .... , ui-1  with the desired properties,  subtract the projections of vi in each of the directions  u1,  u2,  ....,  ui-1  from vi and then normalize the resulting vector ui' by dividing by its length to get the vector ui.   Continue in this way til done.
	Remember that the projection of a vector v in the direction of a unit vector u has the simple formula
				proju(v) = <u, v> u

Here are the Gram-Schmidt formulas:
		
		ui'  =  vi  -  <u1, vi>  u1 -  <u2, vi> u2 - ... - <ui-1, vi>  ui-1,
		
		ui  =  ui' /  Sqrt [<ui',  ui'>]

Now let's see how this works on our v1,  v2  (remember, we don't need v3).  Notice that for two vectors,  these formulas aren't really new.  We already did these calculations.

up1 = v1

u1 = up1 / Sqrt[up1 . up1]

up2 = v2 - (u1 . v2) u1

u2 = up2 / Sqrt[up2 . up2]

VectorPlot[{u1, u2},{-1,-5,10}]

Now  to see how this works on three or more vectors, do the following:  go back to the definition for v1, v2, v3  above and change the vector v3 slightly, so that the three are linearly independent.  Then click on the following cells (you may want to adjust perspective in the last cell):

up1 = v1

u1 = up1 / Sqrt[up1 . up1]

up2 = v2 - (u1 . v2) u1

u2 = up2 / Sqrt[up2 . up2]

up3 = v3 - (u1 . v3) u1 - (u2 . v3) u2

u3 = up3 / Sqrt[up3 . up3]

VectorPlot[{u1, u2, u3},{5,-5,10}]

Just for  fun, let's calculate the projection of our vector  u  from earlier cells  into the subspace spanned by the orthonormal set  u1, u2, u3.  What does this give you?

u

(u1.u)*u1 + (u2.u)*u2 + (u3.u)*u3

Non-Standard Inner Products

We are going to look at a problem that, on the face of it, has nothing to do with inner products or even vector spaces.  But analysis of the problem will illustrate why it is sometimes useful to develop ideas beyone the level of immediately obvious applications.  Sometimes, rather abstract ideas can have unexpected practical applications.

Suppose you work for a manufacturer of calculators, and are involved in the design of a new calculator.  The problem is this :  as one of the ªfeaturesº of this calculator, the designers decided that it would be nice to have a key which calculated a transcendental function.  For the sake of argument, we'll take the function to be  F[x] = Sin [ Exp [x]].  Of course, it would be more likely that the function would be something like  Exp[x]  or  Log[x], but  for purposes of our graphs, the differences I want to highlight for you show up better with this  F[x].   Let's suppose that our job is to come up with an adequate way of calculating  F[x], say with an error no worse than .1  (yes, I know the error is too large, but this will illustrate what's going on without getting too messy.)   Moreover, suppose that it will only be necessary to compute  F[x]  for values between  -1 and 1.  Now your job is to find a simple way to calculate values of this function  F[x], for  -1 £ x £ 1. 

Polynomials are a natural idea for approximating functions.  From a designer's point of view they are particularly attractive because they are so easy to implement.  Given the coefficients of a polynomial, it is easy to design a very efficient and compact algorithm for calculating values of the polynomial.  Such an algorithm, together with the coefficients of the polynomial, would fit nicely into a small ROM for the calculator, or could even be microcoded into the chip.

The first idea that ought to occur you comes from Calculus: what about Taylor series, say centered at 0, since our interval is centered about 0.  Mathematica has some nice functions for building polynomials.  Let's try it.  First, make a definition of the function  F[x] for Mathematica to work on.

F[x_] := N[Sin[Exp[x]]]

Now for the Taylor Series of F, say of degree 3

Series[F[x],{x,0,3}]

What's the weird stuff, O[x]?  It says that the leftover terms behave no worse than a constant times  x4, which is  O.K. by the Remainder Formula for Taylor Polynomials.  To get a sensible form without that last term, do this:

q = Normal[Series[F[x],{x,0,3}]]

Let's plot these functions:

Plot[{F[x], q}, {x, -1,1}]

Not too good...  Go to the previous cells for q and Plot, and change the 3 to a 4 and Enter.  Then try a 5.  Let's see what the error is.  It appears the worst error is at 1.  So...

N[Abs[F[1] - (q /. {x -> 1})]]

There is another way, which is the point of this experiment.  Let's adopt the point of view that our functions live in the inner product space C[-1,1] of continuous functions on the interval [-1, 1] with the integral type inner product.  Now let's try to find the function in the space of cubic (3rd degree) polynomials P3  that is closest to our F[x].  We will build the necessary tools by using definitions of inner products as in class.  In the following, we will assume that the independent variable in each function expression is x.

InProd[f_,g_] := NIntegrate[f g, {x, -1, 1}]

Norm[f_] := Sqrt[InProd[f,f]]

Now use the Gram-Schmidt algorithm to generate orthonormal polynomials p0, p1, p2, and p3   from the polynomials 1, x, x2, x3.  These polynomials are famous enough to have a name attached to them:  they are the Legendre polynomials.

p0 = 1

p0 = p0 / Norm[p0]

p1 = x - InProd[p0,x] p0

p1 = p1 / Norm[p1]

p2 = x^2 - InProd[p0,x^2] p0 - InProd[p1,x^2] p1

p2 = p2 / Norm[p2]

p3 = x^3 - InProd[p0,x^3] p0 - InProd[p1,x^3] p1
         - InProd[p2,x^3] p2

p3 = p3 / Norm[p3]

Finally, let's calculate the projection of our F into P2 and see how it does against F[x].

p = InProd[p0,F[x]]p0+InProd[p1,F[x]]p1+InProd[p2,F[x]]p2

Plot[{F[x],p},{x,-1,1}]

This  isn't so great.  Try adding an extra term so as to calculate the projection of F into P3.  Testing, for example, at the endpoints, in the following line confirms what the graph suggests.

Abs[F[1] - p /. {x -> 1}]

To summarize: what we have accomplished is to obtain a polynomial of degree 3 that does as nearly as good a job as the 5th degree Taylor polynomial in approximating F[x], at least as far as the worst error is concerned.  Could we do better with a third degree?  Actually, yes.  But we would have to use an even weirder inner product :  InProd[f_,g_] = 
NIntegrate[f g / Sqrt[1 - x^2], {x, -1, 1}].  The resulting orthonormal polynomials that would be generated from 1, x, x2, etc, are also famous enough to have a name: the Tschebychev polynomials.  But that's a story  for another course......

Exercises

(1)  For each of the following sets of vectors, produce an orthonormal set which spans the  
       same space as the original vectors:
       
       (a)  {(1,1,0), (1,0,1), (1,1,1)}
       (b)  {(0,1,1,1), (1,0,1,1), (1,1,2,2), (1,1,1,0)}
       (c)  {(1,0,1,2,-1),(3,-1,3,7,4),(0,0,0,0,0),(-1,3,2,4,7),(-2,5,6,7,9)}

(2)  Define the inner product f *g by f * g = Integrate [f(x) g(x), {x, 0, p}].  The set of 
       continuous functions with this inner product is an inner product space.
       
      (a)  Generate an othogonal basis for the span of the set of ªvectorsº
            {1, Exp[x], Exp [2 x], Exp [3 x]}  (Hint: use N to approximate constants.)
      (b)  Now try to generate an othogonal basis from the set of vectors
            {1, Sin [x], Sin [2 x], Sin [3 x]}.  Can you make any further predictions?
      (c)  Let f[x] = x, for -p / 2  £ x <  p/2.  Find the projection of f onto each of the vectors
            you obtained in (2b).    
                   The series  å [(f * Sin [n x]) Sin [n x] + (f * Cos [n x]) Cos [n x] ] is called the
            Fourier Series of a function f.  If f[x] = - f[-x] (as is here) then f * Cos [n x] = 0 "n.