CARNEGIE MELLON UNIVERSITY



Carnegie mellon university

DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING

18-771 linear systems spring 2003

_ _

midterm examination

open textbook and course notes

Tuesday 25 February 2003

2:30 p.m. – 4:30 p.m.

ph a18C

_

OVERVIEW

This midterm examination (which constitutes thirty-five percent of your final grade) consists of five (5) problems and will be graded on the basis of three hundred fifty (350) points. You are to solve these problems in the blue books. Present your solutions in consecutive order and put a box around your answers.

The objective of this midterm examination is to test your understanding of state-space fundamentals and your ability to apply these concepts to solve engineering problems. Most of the tasks do not require extensive computation. Wherever appropriate, solutions based upon engineering insight will receive full credit.

The quality of your analysis, synthesis and evaluation is as important as your answers. Your reasoning must be precise and clear; your complete English sentences should convey what you are doing. Your grade will reflect both the clarity of your presentation and checking of your results.

A grading sheet appears on page 7. Letter your name on the cover of each blue book and the grading sheet. Submit the grading sheet along with your blue books.

_ _

PROLOGUE

For each problem, formulate a coherent plan to gain insight, generate straightforward algebraic expressions and extract the salient information required to accomplish the prescribed tasks. To alleviate the computational tedium, carry your algebraic computations to the point of addressing the issues and drawing engineering conclusions. To facilitate your algebraic computations, you are encouraged to define intermediate parameters and variables; e.g., g ( g1 + g2. You are not required to simplify algebraic expressions for the aesthetic objective of simplifying algebraic expressions.

PROBLEM I (90 POINTS)

DO ALL OF THE PARTS OF THIS PROBLEM WITHOUT A CALCULATOR.

In the system of linear algebraic equations

A x = b (1)

the coefficient matrix

[pic]

and the right-hand side input vector

[pic]

(A – 5 Points) Find the rank of A.

(B – 10 Points) List the pivot columns of A.

(C – 10 Points) State the solvability condition for the system of linear algebraic equations in (1).

(D – 10 Points) Find a basis for the null space of A.

(E – 10 Points) Find a basis for the column (range) space of A.

(F – 10 Points) Find the general solution of the system of linear algebraic equations in (1).

(G – 10 Points) Exhibit an LU decomposition of the coefficient matrix A in (1).

(H – 10 Points) Write MATLAB( code to compute numerically the LU decomposition of the coefficient matrix A in (1).

(I – 10 Points) Exhibit the structure of the singular value matrix ∑ in the economy size singular value decomposition of the coefficient matrix A in (1).

(J – 5 Points) Write MATLAB( code to apply Gaussian elimination to compute numerically the solution of the system of linear algebraic equations in (1).

PROBLEM II (80 POINTS)

In 1653, the French mathematician Blaise Pascal described a triangular arrangement of numbers corresponding to the number of ways to choose n objects from a group of m indistinguishable objects. The first five rows of Pascal's triangle of binomial coefficients are:

|1 |n =1 |

|1 1 |n =2 |

|1 2 1 |n =3 |

|1 3 3 1 |n =4 |

|1 4 6 4 1 |n =5 |

In actuality, the triangle predates Pascal, through developments in Persia (Omar Khayyam) and in China and Europe and India. The objective of this problem is to explore properties Pascal's triangle in the framework of numerical linear algebra.

We begin by assembling the truncated triangle of binomial coefficients into three different (n(n) matrices: a symmetric matrix S(n), a lower triangular matrix L(n) and an upper triangular matrix U(n). We illustrate the pattern for n=4:

[pic]

[pic]

and

[pic]

In MATLAB( , S= pascal(n) returns the (n(n) Pascal matrix. Each element is the sum of its north and west neighbors. L = pascal(n,1) returns the (n(n) lower triangular matrix.

(A – 15 Points) Identify the connection(s) between the three matrices for all values of n.

(B – 10 Points) Compute the determinant of S(n), L(n) and U(n) for all values of n.

(C – 15 Points) Compute the pivots of S(n) for all values of n.

(D – 10 Points) Compute L2(4) and L3(4) and then generalize your findings to write Lp(4).

(E – 20 Points) Set p = -1 to obtain L-1(4). Factor L-1(4) into the product of three matrices:

L-1(4)= D M D where M = L(4) and D is a diagonal matrix.

(F – 10 Points) Compute the natural logarithm of L(4):

[pic]

Interpret your findings.

PROBLEM III (60 POINTS)

Throughout this problem, let us assume that the columns of the (16(4) matrix Q are orthonormal.

(A – 25 Points) Compute the least-squares solution [pic]to Q x = y.

(B – 25 Points) Is QQT positive definite? Why?

(C – 10 Points) Compute all of the singular values of Q. Explain your findings.

PROBLEM IV (70 POINTS)

The projection of the vector b onto the line through a is the vector

[pic]

where the projection matrix

[pic]

(A – 15 Points) Construct the projection matrix P for the vector a = [1 2 –4]T.

(B – 15 Points) Locate the subspace onto which P projects.

(C – 15 Points) Compute the distance from this subspace to the vector b = [1 1 1]T.

(D – 15 Points) Characterize completely the eigenvalues and eigenvectors of P for any arbitrary a.

(E – 10 Points) Let the n-vectors a1, a2, … , an be a collection of linearly independent vectors in m-dimensional space. The problem is to find the linear combination of the ai that is closest to the vector b. Write down the (n(n) projection matrix P that produces the vector [pic] that is the projection of b onto the n-dimensional subspace spanned by the ai.

PROBLEM V (50 POINTS)

For MATLAB( computation, vectorize the following double for loops to create a matrix by computation.

A = magic(100);

B = pascal(100);

for j = 1 : 100

for k = 1 : 100

x(j,k)= sqrt(A(j,k)) * (B(j,k) –1);

end

end

_ _

Carnegie mellon university

Department of electrical and computer engineering

18-771 linear systems spring 2003

_ _

midterm examination

GRADING SHEET

Tuesday 25 February 20023

NAME SCORE

PROBLEM I (90 POINTS)

(A – 5 POINTS)

(B – 10 POINTS)

(C – 10 POINTS)

(D – 10 POINTS)

(E – 10 POINTS)

(F – 10 POINTS)

(G – 10 POINTS)

(H – 10 POINTS)

(I – 10 POINTS)

(J – 5 POINTS)

PROBLEM II (80 POINTS)

(A – 15 POINTS)

(B – 10 POINTS)

(C – 15 POINTS)

(D – 10 POINTS)

(E – 20 POINTS)

(F – 10 POINTS)

PROBLEM III (60 POINTS)

(A – 25 POINTS)

(B – 25 POINTS)

(C – 10 POINTS)

PROBLEM IV (70 POINTS)

(A – 15 POINTS)

(B – 15 POINTS)

(C – 15 POINTS)

(D – 15 POINTS)

(E – 10 POINTS)

PROBLEM V (50 POINTS)

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

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download