CSCI 3656 Mid Term Test

To take the test, please answer each of the questions below, and when finished, input the results for each on the midterm entry on the usual results page. You need to input all questions in one sweep, then submit. It is fine to submit several times. I will use only the last submission.

YOU CANNOT SUBMIT USING THIS FORM.
THIS IS JUST TO SHOW YOU WHAT THE QUESTIONS ARE.
THERE IS NO SUBMIT BUTTON AT THE END!

Due Date: Thursday March 18th at midnight.

Rules: Open Book. Strictly no discussion with anyone in the class or outside of the class. Each student is showing what he or she can do on their own. The Honor Code applies.

For the problems requiring programming please write your own code, i.e. your own routines for solvers etc previously developed. Solutions done as a one-line MATLAB call would not be fair.

All numbers should be input with 5 digits of precision. No need for trailing zeroes - so 3.1000 can be input as 3.1. I use the notation x**y for x to the power y.

PIN:

Chapter 1

1. In a floating point number system the underflow level is the smallest positive number that perturbs the number 1 when added to it.
True False Dont Know
2. Using higher-precision arithmetic will make an ill-conditioned problem better conditioned.
True False Dont Know
3. Floating Point Numbers are uniformly distributed throughout their range
True False Dont Know
4. The mantissa in IEEE double precision arithmetic is exactly twice as long as the mantissa for single precision arithmetic.
True False Dont Know
5. In a 12-digit binary floating-point system with rounding to nearest, what is the value of emach:
2**-11 2**-12 1/2 2**-12 2**-14 Dont Know
6. Assume you are solving the quadratic equation ax**2 + bx + c = 0 with a = 1.22, b = 3.34 and c = 2.28 using normalized floating point arithmetic with beta = 10 and p = 3, and rounding to nearest. Assume that u*v*w is computed as (u*v)*w.
a) What is the computed value of the discriminant b**2 - 4ac:
b) What is the correct value of the discriminant in exact arithmetic:
c) What is the relative error in the computed value of the discriminant:

Chapter 2
7. If a matrix A is nonsingular then the number of solutions to A*x=b depends on the choice of RHS b.
True False Dont Know
8. If a triangular matrix has a zero entry on its diagonal then it must be singular.
True False Dont Know
9. The product of two upper triangular matrices is upper triangular.
True False Dont Know
10. The product of two symmetric matrices is symmetric.
True False Dont Know
11. The LU factorization, with row interchanges, PA = L*U, always exists for any matrix A, even if singular.
True False Dont Know
12. Gaussian elimination without pivoting fails only when the matrix is ill-conditioned or singular.
True False Dont Know
13. If x is any n-vector then the 1-norm ||x||1 <= the infinity norm, ||x||infinity.
True False Dont Know
14. If A is nonsingular then cond(A) = cond(1/A)
True False Dont Know
15. The multipliers in Gaussian Elimination with partial pivoting are bounded by 1 in magnitude, so that entries of the successive reduced matrices cannot grow in magnitude.
True False Dont Know
16. a) What is the condition number of the matrix: 
         A = 4  0  0
             0 -6  0
             0  0  2
in the 1-norm:
b) What is it in the infinity norm:
17. Suppose the n*n matrix A is perfectly well-conditioned so that cond(A) = 1 in the 1-norm. Each of the following would share this same property:
cA, c a non-zero constant: True False Dont Know
D*A, D nonsingular diagonal matrix: True False Dont Know
P*A, P a permutation matrix: True False Dont Know
B*A, B a nonsingular matrix: True False Dont Know
1/A: True False Dont Know
At, the transpose of A: True False Dont Know

Chapter 4

18. All the eigenvalues of a real matrix must be real:
True False Dont Know
19. A matrix A is singular if and only if 0 is an eigenvalue:
True False Dont Know
20. A matrix A that is both Hessenberg and Symmetric must be tridiagonal:
True False Dont Know
21. If two matrices have the same eigenvalues then they are similar.
True False Dont Know
22. Compute the largest root in magnitude of the polynomial 
        p(t) = t**4 - 10t**3 + 35t**2 - 50t + 24
by forming its 4*4 companion matrix C4 and using an eigenvalue solver to find the corresponding largest eigenvalue emax of C4. Power iteration will do fine. Also compute the corresponding eigenvector X of C4 and return its elements:
Largest Root emax:

Eigenvector X:
X[0] = , X[1] = ,
X[2] = , X[3] = .
23. Compute the second largest root in magnitude of the polynomial p(t) above by applying the deflation method to the 4*4 companion matrix C4 after determining its largest eigenvalue emax and eigenvector X in the previous problem. See section 4.5.4.

As discussed in 4.5.4 we want a matrix H to take the largest eigenvector X into a multiple of the unit vector e0 = (1 0 ... 0)t. As the matrix H, use the elementary elimination matrix M0 = M[k=0] from section 2.4.3. Here M0 is the identity matrix except in column 0 where it has the values -m1, -m2, ... -mn-1 below the diagonal, where mk = X[k]/X[0] for k = 1,,,n-1. Also remember from 2.4.3 that 1/M0 is the same matrix with the sign of the off-diagonal elements reversed. I have tried to shift everything from 1...n notation to 0...n-1 for convenience.

As discussed at 4.5.4, the matrix H*C4*1/H will then have the form: 

        H*C4*1/H =  lmax  .....
                      0     C3
where C3 is a 3*3 matrix, and therefore, by similarity, C3 has the same eigenvalues as C4 other than the largest one.
Thus we can find the second largest root of the polynomial as the largest eigenvalue of C3 by power iteration on C3 (and we could deflate further to get the remaining two eigenvalues if we wished as largest eigenvalues of 2*2 and 1*1 matrices C2 and C1).
Top diagonal element of C3 =
Second Largest Root =

Chapter 5

24. If an iterative method squares the error after every two iterations, what is the convergence rate:
Convergence Rate r =
25. A small residual ||f(x)|| in solving a system of nonlinear equations f(x) = 0, guarantees an accurate solution of the system.
True False Dont Know
26. a) What is the convergence rate for Newton's Method for finding the root x=2 of the function: 
        f(x) = (x-1)**2 (x-2)
Convergence Rate r =

b) What is the convergence rate for Newton's Method for finding the root x=2 of the function: 

        f(x) = (x-1) (x-2)**2
Convergence Rate r =
27. It is better to use the relative condition number than the absolute condition number in assessing the sensitivity of a root finding problem.
True False Dont Know
28. For solving an 100-dimensional system of nonlinear equations by Newton's Method, how many function evaluations (functions and/or derivatives) are required per iteration.
Number of function evaluations =
29. Write a routine based on Newton's Method to solve the system of nonlinear equations: 
        (x0 + 3)(x1**3 - 7) + 18 = 0
        sin(x1*exp(x0) - 1)      = 0
with starting point X = [-.5 1.4]. The exact answer is x* = [0 1] which allows you to verify that the code is working correctly.

At step k = 2, give the four elements of the 2*2 Jacobian J(x) in Algorithm 5.4. Note that since the algorithm starts with k = 0, this will be the third Jacobian that you compute.

J(x[k=2])[0,0] = J(x[k=2])[0,1] =
J(x[k=2])[1,0] = J(x[k=2])[1,1] =

Comments: