to COMP 205 Homework 3 Feb 02, 1998, Due: Feb 11, 1998

Problems

1. (15 points) Given a vector , show that

   

   and

   

2. (15 points) Given matrices, and , let be operator norms, as defined in the class. Prove the following properties :
   1. , if is the operator norm induced by the vector norm .
   2. .
   3. .
   4. .
3. Programming Assignment (40 points) Implement Gaussian elimination with back-substitution for solving linear systems. Use two versions of the algorithm: with partial pivoting and complete pivoting. Test each of your routines on a number of randomly generated matrices of various sizes up to 30 or so, and check that your answer is correct by verifying that

   

   is of order unity. Compare your answers for partial and complete pivoting. Does R depend on n, the order of the matrix. You are recommended to use the 2-norm. To compute the 2-norm of make use of routines to compute the Singular Value decomposition (as available on the WWW page). Remember that the 2-norm corresponds to the largest singular value.

   As test matrices, your trials should include some well-conditioned problems as well as ill-conditioned ones. To generate a well-conditioned matrix, let be a permutation matrix, and add a small random number to each entry. To generate an ill-conditioned matrix, let be a random lower triangular matrix with tiny diagonal entries and moderate subdiagonal entries. Let be a similar upper triangular matrix, and let .

   Also try both solvers on the following class of matrices for n = 1 up to 60 (in double precision). Shown here is the case for n = 5 and the others are similar:

   

   Your solutions should consist of a well-documented program listing, an explanation of random matrices you generated, and a table of the following 7 columns: Example number, dimension, condition number of the matrix , R for partial pivoting, the run time for your routine, R for complete pivoting, the run time for complete pivoting. To compute accurate timings from Unix run each routine with each particular matrix about times and use clock() routine (man 3 clock) to obtain the total time and divide that by .

Code provided

In directory /afs/cs.unc.edu/home/dm/public_html/UNC/COMP205/Program/HW3, (also accessible from the Comp205 WWW homepage), you will find code, along with sample makefile and application code, for the following routines:

• dsvdcmp() --- a C routine for performing SVD on a given matrix A and returning its singular value decomposition . The vector w returned by this routine is the diagonal of the W matrix above and holds the singular values (unsorted) for the matrix A.

  Originally from Numerical Recipes in C, it has been modified to work with 0-indexed arrays and matrices, rather than the 1-indexed convention held over from FORTRAN.

• unif_rand_dbl() --- a C/C++ routine, derived from the NumRec rand3() routine, for producing uniformly distributed random values in the range .

• randint() -- a C++ routine derived from the above for producing uniform random integers in the range for user-given n.

Most of the above code is in C---for novitiates, the application program shows how simple it is to link C-routines into a C++ program.

It may be a good idea to build a small class library of matrix and vector routines to use in this assignment and possible future assignments. However, do not spend too much time in the design and implementation of that library. For numerical work in C++, it is important to make class constructors simple and efficient, and to use inline functions for direct access to data members which will be used frequently in computation (such as matrix elements). In this way, C++ code can be made that runs with little efficiency loss over comparable C or FORTRAN code, while allowing the organizational benefits of OOP.

• About this document ...