COMPUTING ASSIGNMENT #4 Solution

Instruction

Upload a PDF file with two parts. Part one should include your typed report (your discussions, data and figures). Part two should list your code. You will receive a Crowdmark link for uploading your results.


Perturbation and eigenvalues

This computing assignment is about visualizing computed eigenvalues of some special matri-ces. In particular, we want to see how sensitive eigenvalues are with respect to perturbations in the matrices. The focus is on setting up and conducting the experiments, and observing the outcome without going too deep into the analysis.


1. Create perturbations.

a). Create an n n random matrix B by the Matlab command rand such that each entry is a number in the interval [ 1; 1].

b). Create an n n random orthonormal matrix Q by QR factorizing B. In your report, display such a random orthonormal matrix Q with n 10.

c). Set = 10 8. Generate 100 random orthonormal matrices Q1; Q2; :::; Q100 and multiply the matrices by . Store the resulted perturbations Q1; Q2; :::; Q100.






2. Jordan block and Limac¸on.

a). Create the following n n matrix J (Jordan super block) in Matlab by the command diag with n 50.
0 0
0
1

0
0 1
0
1
0

0
0
B




C
    • ......C
    • .......C
    • .....C
J =
0
0
0

0
1
C
B







B
0
0
0

1
0
C

0
0
0

0
0

B






C
@






A
b). Let A = 4J. Report the eigenvalues and condition number of A. Compute the eigenvalues of A + Qi for the 100 perturbations created in Question 1. Note that these eigenvalues may be complex numbers. Plot all the eigenvalues of the 100 matrices (i.e. A + Qi) on one plot by the command plot(eigenvalues, ’.’). Report the plot and your observations.

c). Let A = 4J + 4J2. Report the eigenvalues and condition number of A. Compute the eigen-values of A + Qi for the 100 perturbations created in Question 1. Note that these eigenvalues may be complex numbers. Plot all the eigenvalues of the 100 matrices (i.e. A + Qi) on one plot by the command plot(eigenvalues, ’.’). Report the plot and your observations.


1
MACM 316    COMPUTING ASSIGNMENT #4



3. Gauss-Seidel

a). Create the following n    n matrices S, U and L from the matrix J in Matlab with n    50.
0 0
0
1
0
0
0 1
0
1
2
1
0
0
0 1

0
1
0
0
0
0
C ;
S = B
2
1
0
0
0
0
C
J=B ..  ...  ...
. . .
. . .
..


..
...  ...
. . .
. . .
..

B
.
0
0
0
1
.
C
B
.
0
1
2
1
.
C

0




0


0




0

B






C
B






C
B
0
0
0
0
0
1
C
B
0
0
0
1
2
1
C
B






C
B






C
B






C
B






C
B
0
0
0
0
0
0
C
B
0
0
0
0
1
2
C
@






A
@






A
0 0
0
1
0
0
0 1
0
1
2
0
0
0
0 1

0
1
0
0
0
0
C ;
L = B
2
0
0
0
0
0
C
U=J=B ..  ...  ...
. . .
. . .
..


..
...  ...
. . .
. . .
..

B
.
0
0
0
1
.
C
B
.
0
1
2
0
.
C

0




0


0




0

B






C
B






C
B
0
0
0
0
0
1
C
B
0
0
0
1
2
0
C
B






C
B






C
B






C
B






C
B
0
0
0
0
0
0
C
B
0
0
0
0
1
2
C
@






A
@






A
b). Let A = L 1U. Compute the eigenvalues of A and plot the eigenvalues. Report the plot of the eigenvalues and condition number of A. There is a formula for the exact eigenvalues of A. It is known that the eigenvalues are real, and are all in the interval [0; 1]. What do you observe? Is = 0 an eigenvalue of the matrix A?

c). Compute the eigenvalues of A + Qi for the 100 perturbations created in Question 1. Note that these eigenvalues may be complex numbers. Plot all the eigenvalues of the 100 matrices (i.e. A + Qi) on one plot by the command plot(eigenvalues, ’.’). Report the plot and your observations.





























2
MACM 316    COMPUTING ASSIGNMENT #4



4. Polynomial.

a). Generate n equally spaced points r1; r2; :::; rn on the interval [ 2; 2] in Matlab with the command linspace. Find the polynomial p(z) = c0 + c1z + cn 1zn 1 + zn with r1; r2; :::; rn as its roots by the Matlab command poly.

b). Create the following n n matrix A, which is the companion matrix of the polynomial and can be computed by Matlab command compan.

0
1
0

n
0

0
0 1

B
cn  1
cn  2
c

3

c1
c0
C
A =

0.
1.


0.
.
0.
0.


B
..
..


..   ..
..
..
C

B








C

B
0
0


0

0
0
C

B








C

B
0
0


0

1
0
C

B








C

@








A
c). Compute the eigenvalues of A and compare the eigenvalues with r1; r2; :::; rn. Report the observations about eigenvalues and condition number of A. Compute the eigenvalues of A + Qi for the 100 perturbations created in Question 1. Note that these eigenvalues may be complex numbers. Plot all the eigenvalues of the 100 matrices (i.e. A + Qi) on one plot by the command plot(eigenvalues, ’.’). Report the plot and your observations.

d). Use the following Matlab code to great a matrix B where r = [r1; r2; r3; :::; rn] are the vector of values from c).

M = 2*rand(n) - 1;    [W,R] = qr(M);    B = W*diag(r)*W';


Compute the eigenvalues of B as well as those of B + Qi and B + (Qi + QTi ), for ten different random orthogonal matrices Qi from Question 1. The second perturbation is symmetric, so the eigenvalues will remain real. Do not plot your results in this case. Instead, report by how much the eigenvalues move under these perturbations. Compare the eigenvalues of A and B. Do they have the same eigenvalues? What do you believe to be the reason for obtaining different results with perturbations?




















3