CSCI 3656 Mid Term Test With Results

To take the test, please answer each of the questions below, and then click the Submit button at the end. Unfortunately it is not possible to save your results half way through. You need to complete all questions, then submit. It is fine to submit several times. I will use only the last submission.

Due Date: Friday March 20th at 3PM

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

FALSE. The underflow level is the smallest positive normalized number. See section 1.3.3.
2. Using higher-precision arithmetic will make an ill-conditioned problem better conditioned.
True False Dont Know

FALSE. Even in infinite-precision, e.g. exact, computation an ill-conditioned problem is ill-conditioned. See section 1.2.6
3. Floating Point Numbers are uniformly distributed throughout their range
True False Dont Know

FALSE. See Figure 1.3 in the book.
4. The mantissa in IEEE double precision arithmetic is exactly twice as long as the mantissa for single precision arithmetic.
True False Dont Know

FALSE. See Table 1.1.
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

Case 2. See Section 1.3.5 in the book. emach = 1/2 beta**(1-p) = 1/2 2**(1-12) = 2**-12
Note, if normalized numbers are used you would only need 11 digits to store the mantissa since its first digit is 1. However by the definition given in Section 1.3.5, this is still a 12-digit system.
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:

Since p=3 we only have 3 digits of precision total. For example 11.1556 will be stored as 11.2. Using this we see that: 

a) b**2 = 3.34*3.34 = 11.2; 4ac = (4*a)*c = 4.88*2.28 = 11.1
   discr = b**2 - 4ac = 11.2 - 11.1 = 0.1
b) discr = b**2 - 4ac = 11.1556 - 11.1264 = .0292
c) relative error = error/exact = (0.1 - .0292)/.0292 = 2.4246575

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

FALSE. A*x=b has exactly one solution, x = 1/A*b.
8. If a triangular matrix has a zero entry on its diagonal then it must be singular.
True False Dont Know

FALSE. The answer would be TRUE if the question had been about upper triangular matrices. The diagonal elements of an upper or lower triangular matrix are its eigenvalues, so the matrix has a zero evalue and is therefore singular by definition. However we have defined a triangular matrix (section 2.4.2) as one which can be converted to upper or lower triangular form by permuting rows or columns. This includes even 2x2 matrices such as: 

0 1
1 0
which becomes the diagonal identity matrix (clearly upper triangular) if you permute its columns. This matrix has evalues +1 and -1 and is therefore nonsingular despite having all zeros on the diagonal!
9. The product of two upper triangular matrices is upper triangular.
True False Dont Know

TRUE.
Suppose U, V upper triangular so U[i,j] = 0 if i>j. V[i,j] = 0 if i>j.
So (U*V)[i,j] = sum U[i,k]V[k,j] has sum running only over i<=k<=j.
If i>j then this range is empty so the sum is zero.
Therefore (U*V)[i,j] is 0 for i>j and thus U*V is upper triangular.
10. The product of two symmetric matrices is symmetric.
True False Dont Know

FALSE. Easily shown with 2*2 counter examples. (The result is true if the symmetric matrices commute: AB = BA).
11. The LU factorization, with row interchanges, PA = L*U, always exists for any matrix A, even if singular.
True False Dont Know

TRUE. See section 2.4.5 which explains this.
12. Gaussian elimination without pivoting fails only when the matrix is ill-conditioned or singular.
True False Dont Know

FALSE. It fails if a zero occurs on the diagonal - yet the matrix may be fine, since a zero on the diagonal does not require it to be either ill-conditioned or singular.
13. If x is any n-vector then the 1-norm ||x||1 <= the infinity norm, ||x||infinity.
True False Dont Know

FALSE. The 1 -norm = sum |x[i]| which is >= max |x[i]| = infinity norm.
14. If A is nonsingular then cond(A) = cond(1/A)
True False Dont Know

TRUE. cond(A) = ||A|||1/A|| so cond(A) = cond(1/A).
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

FALSE. While the multipliers are bounded by 1, it is not true that elements cannot grow. See pg 76 which points out they can double - you might subtract -6 from a 6 to get 12 for example.
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:

See section 2.3.2. Since A and 1/A are diagonal the row and columns sums are the same - just the diagonal element, and so the 1-norm and infinity norm are the same. The maximum diagonal elt of A is 6 and of 1/A is 1/2 and so ||A|| = 6 and ||1/A|| = 1/2 leading to cond(A) = ||A||||1/A|| = 3.
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

See section 2.3.3.
a) TRUE. cond(cA) = cond(A) so unchanged.
a) FALSE. cond(DA) can be quite different . Consider A=I and D= (10,0,..). Clearly D*A is singular so its cond cannot be 1!
c) TRUE. ||P*A|| <= ||P||||A|| = ||A| since ||P|| = 1.
||1/(P*A)|| = ||1/A * 1/P|| <= ||1/A||||1/P|| = ||1/A| since 1/P = P. so true for P*A.
d) FALSE. Not true for B*A since D*A is a special case.
e) TRUE. since 1/(1/A) = A. f) FALSE. It is not true that ||At| = ||A||. For example: 

A = 0 1  has 1-norm 5, whereas its transpose  At = 0 2   has 1-norm 4
    2 3                                            1 3
This should lead to easy counterexamples. For example, the inverses of these are: 
1/A = -3/2 1/2  with 1-norm 2, and  1/At = -3/2  1   has 1-norm 2.5
        1    0                              1/2  0
So cond(A) = 5*2 = 10 but cond(At) = 4*2.5 = 10! So instead of finding FALSE we find TRUE. I tried other 2x2 cases and get the same! It may actually be TRUE for 2x2. However I refuse to believe it is true for n*n. If someone can prove it is then of course I'll change that! I'm leaving on Spring Break and cannot nail this down or I'll miss my flight.

Chapter 4

18. All the eigenvalues of a real matrix must be real:
True False Dont Know

FALSE. 

Consider [ 0 1
          -1 0]
which has two imaginary evalies i and -i.
19. A matrix A is singular if and only if 0 is an eigenvalue:
True False Dont Know

TRUE. By definition.
20. A matrix A that is both Hessenberg and Symmetric must be tridiagonal:
True False Dont Know

TRUE. Hessenberg means zero below first subdiagonal. By symmetry must be zero above first supdiagonal. Hence tridiagonal.
21. If two matrices have the same eigenvalues then they are similar.
True False Dont Know

FALSE. See example 4.9 for a counter example.
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] = .

Here is a complete sample computation with detailed printout illustrating this.
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 =

Here is a complete sample computation with detailed printout illustrating this.

Chapter 5

24. If an iterative method squares the error after every two iterations, what is the convergence rate:
Convergence Rate r =

sqrt(2) = 1.41459.... - since two iterations gives the square of this, or 2.
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

FALSE. We have seen many examples where residual is small, but error is large - e.g. the Hilbert matrix problem.
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 =

a) Convergence rate is quadratic (r=2) since this is Newton's Method for a root of multiplicity 1. b) Convergence rate is linear (r=1) since this root has multiplicity 2. See end of section 5.5.3.
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

FALSE. As discussed frequently, since the answer for root finding is 0, the relative error is not defined so we are forced to use absolute error.
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 =

Answer = 10,100. Therre will be 100 functions f(x1,,,,x100) to be evaluated and there will be 10,000 partial derivatives d/dxi*d/dxj. This gives a total of 10,100 functions. Actually since the Jacobian is symmetric we really can get away with evalating only n*(n-1)/2 = 4950 derivatives so a better answer is 5,050 functions need to be evaluated.
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] =

Here is a complete sample computation with detailed printout illustrating this.


Comments: