Lab 16: The Gram-Schmidt Process

In this lab you will use the python numpy module to perform the Gram-Schmidt process on a collection of vectors to find an orthonormal basis for their span. Recall that to import the NumPy module you use the command

>>> import numpy as np

Use the numpy array constructor for vectors:

>>> u=np.array([1,2,3])

This will allow you to use the built-in method to compute dot products. To compute the dot product of two vectors u and v, use the syntax u.dot(v) or v.dot(u).

Task 1

Write a function projection(u,v) that takes as input two vectors u and v of the same length n and computes the projection of v onto the subspace of \(\mathbb R^n\) spanned by u. Recall the formula for this projection is

\[\text{Proj}_{u}(v)=\frac{u\cdot v}{u\cdot u} u,\]

where · is the usual dot product.

>>> projection([1,0,-1],[1,2,3])
array([-1., -0., 1.])

>>> projection([1,2,0,-1],[2,3,4,5])
array([ 0.5,  1. ,  0. , -0.5])

Task 2

Write a function GramSchmidt(X) that takes as input a Python list X of vectors [v_1, v_2,... v_p] and returns a Python list of vectors [u_1, u_2,... u_q] which forms an orthogonal basis for the space spanned by the original vectors.

Here are a few more things you should be aware of:

  • You may assume the original vectors are the same length, however you should not assume the original vectors are linearly independent. Think about what this means for your vectors, will you need to keep all of them?

  • Convert the contents of each vector from int to float. This can be done by dividing each vector by 1.0 after it has been converted to a NumPy array.

  • Start the Gram-Schmidt algorithm with the first element of X and continue, in order, through the rest of the elements. Set u_1 = v_1, and then u_2 = v_2 - projection(u_1,v_2), etc. This will make sure your answers correspond with the autograder.

  • Round each of your vectors to two decimal places. (Use np.round(v, dec) to make things quicker)

>>> GramSchmidt([[1,0,-1],[1,2,3]])
[array([1., 0., -1.]), array([2., 2., 2.])]

>>> GramSchmidt([[1,0,-1,0],[1,2,3,4],[0,1,2,2]])
[array([1., 0., -1., 0.]), array([2., 2., 2., 4.])]

Task 3

Write a function Orthonormal(X) that takes as input a list X of vectors [v_1, v_2,... v_p] and returns a list of vectors [u_1, u_2,... u_q] which forms an orthonormal basis for the space spanned by the original vectors. Use the GramSchmidt function from the previous task to construct an orthogonal basis, then normalize each element to have norm 1.

>>> Orthonormal([[1,0,-1],[1,2,3]])
[array([ 0.70710678,  0.        , -0.70710678]),
array([0.57735027, 0.57735027, 0.57735027])]

>>> Orthonormal([[1,0,-1,0],[1,2,3,4],[0,1,2,2]])
[array([ 0.70710678,  0.        , -0.70710678,0]),
array([0.37796447, 0.37796447, 0.37796447, 0.75592895])]