Assignment 4

A Parameterized Vector Class and Array Class

Due Date: March 13, 2017

Required for submitting:

  • Grade Sheet Print this sheet and bring it to class the day the program is due.

  • Bring your UML diagram to class. Note: you've already handed in your very last hand-drawn UML diagram

Purpose:

  • The purpose of this exercise is to give you more practice with the first few items listed below along with time management discipline - on-time submission of homework; i.e. don't delay work on this assignment.

    1. templated classes

    2. templated functions

    3. overloading operators

    4. the concept of possibly implementing algorithms as classes

    5. the Modified Gram-Schmidt process for orthonormalizing a set of vectors

Resources:

  • Unix help This is an S&T help site for the basics of Unix.

The Concept:

  • In the last assignment I introduced the Gram-Schmidt process. I included this statement:

    • This will lead you down the path of discovery that theoretically sound mathematical algorithms can fail when applying a numerical method without consideration to detail (in particular, numerical representation and round-off error).

    • Perhaps, but perhaps not, you were wondering what that meant. Now you know. You have certainly (hopefully?) seen in your introductory course in numerical methods that small perturbations in a system's coefficient matrix can radically change the outcome of the computation of a solution. This brings the issue of round-off error to the fore (like right in your face) and makes you painfully aware of the consequences. The Gram-Schmidt process presented in class (that you coded for program #3) works. It is "theoretically" sound. But when you apply it to some situations, it isn't going to work. Those situations include: BigBadUgly . Check it out; run your program #3 code with this ugly matrix. Are the resulting vectors in the supposedly orthonormal set orthogonal to each other?

    • The (expected) result of the above computations is caused by the multiplicity of arithmetic operations and the propogation of round-off error. But it is also caused by, and can be controlled by, the order of those same operations. There is a really neat way to fix this problem in the GS process. The fundamental difference in the two methods is this: In the original method, we calculate a new vector for our orthogonal set at each step along the way from our original set of non-orthogonal vectors. We never change the remaining n - k + 1 vectors after the kth step. In the modified version of the GS process, we will use the last computed orthogonal vector to "update" the vectors remaining in the original non-orthogonal set. Thus:

    • From the original set S = {v1, v2, ... vn } we produce the final orthonormal set T = {u1, u2, ... un }. But along the way we also produce intermediate sets of vectors Wj = {ujj+1, ... ,ujn }. These are created by adjusting the remaining vectors in S using the newest addition to T.

      • To start, let u1 = v1 and then u1 = u1 / ( (u1,u1) )1/2. Continue by adjusting the remaining vectors in S: u1j = vj - (vj,u1)u1 for j = 2, 3,...,n.

      • Now, u2 = u12 / ( (u12,u12) )1/2 and u2j = u1j - (u1j,u2)u2 for j = 3, 4, ... ,n.

      • Continuing in this manner, we produce the orthonormal set we desired in the first place, but without the out-of-control loss of significance.

      • In general, once we have {u1, ... ,uk-1}, we set uk = uk-1k / ( (uk-1k,uk-1k) )1/2 and ukj = uk-1j - (uk-1j,uk)uk, for j = k+1, ... ,n.

Program Specifications:

  • You are to implement the modified Gram-Schmidt process. Your design here is not going to stray too far from that of the previous assignment. Perhaps the only change is going to be the way you calculate the new vectors. You'll probably also want to correct any belatedly realized errors in your previous code.

    • Again, I want you to have your program read in data from a file. The file to read in and operate on is the above posted file: BigBadUgly. Of course, don't hard code for this file!. You can assume that any file to be read in will be formatted as follows:

    1. first value is an int specifying the number of elements in each vector and the number of vectors in the file.

      1. the vectors will be listed in the file one vector to a row. example:

        1. 4 3 8 3 0 1 2 3 4 4 6 8 9 2 0 5 7

    2. the vector components may be float types

    • Make your program accept command-line arguments so that a user can specify the name of the file to be read from. Your program is to output the orthonormalized set in some readable format. It is also to output the inner product of each of these vectors with each other vector. A set of n vectors will then yield n2 real numbers. What should they be? Can you tell if your algorithm is working correctly?

Deliverables:

  1. Code: I will test that the code you submit does indeed compile and run. You are to submit your source code and makefile as usual. How to do this is explained in Submission procedure.

  2. makefile: Supply the makefile which compiles and builds your program as detailed above. I really suggest that you play around with and use the third of the makefiles I posted.

  3. Your gradesheet and UML (in class, of course).