CARNEGIE MELLON UNIVERSITY



Carnegie mellon university

Department of electrical and computer engineering

18-771 linear systems spring 2002

_ _

midterm examination

open textbook and course notes

Tuesday 26 February 2002

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

ph a22

_

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 6. 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 – 10 Points) Find the rank of A.

(B – 20 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 most general solution of the system of linear algebraic equations in (1)

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

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

PROBLEM II (50 POINTS)

An engineer is attempting to orthogonalize (orthonormalize) the columns of the (2x2) matrix

[pic] (1)

The engineer begins by implementing in floating point arithmetic the classical and modified Gram – Schmidt (G – S) algorithms on a computer that rounds all computational results to five digits of relative accuracy. For (2x2) matrices, the classical and modified Gram – Schmidt algorithms are identical. The engineer computes

[pic] (2)

The engineer proceeds to test the following MATLAB( – script on a computer with sixteen-digit precision. eye(2) is the (2x2) identity matrix.

A = [.70000 .70711 %Define A.

.70001 .70711];

[Q,R] = qr(A); %Compute Q by Householder.

norm(Q’*Q-eye(2)) %Test orthogonality of Q.

[Q,R] = mgs(A); %Compute Q by modified G-S.

norm(Q’*Q-eye(2)) %Test orthogonality of Q.

The lines without semicolons produce the following printed output:

ans = 2.3515e-16

ans = 2.3014e-11

The engineer hires you to accomplish the following tasks and assess the quality of the computational results.

(A – 25 Points) Evaluate quantitatively the orthogonality of the Q matrix in (2). Justify your evaluation.

(B – 25 Points) Interpret the MATLAB( output and draw your conclusions.

PROBLEM III (55 POINTS)

Let

[pic]

(A – 30 Points) Compute manually the LU decomposition of M(4). Show all steps.

(B – 15 Points) Generalize and comment on your findings for the (nxn) matrix M(n).

(C – 10 Points) Write MATLAB( code to compute the LU decomposition of M(n).

PROBLEM IV (55 POINTS)

Let A be an (nxn) symmetric positive definite matrix. Write computationally efficient MATLAB( – script to evaluate the quadratic form

Q (x) = xT A-1 x

Comment on the efficacy of your algorithm.

PROBLEM V (100 POINTS)

Matrix factorizations and decompositions abound throughout numerical linear algebra. Familiar examples include the LU factorization, Cholesky decomposition, QR factorization and singular value decomposition of the matrix A. The objective of this problem is to formulate and illustrate an algorithm for computing the full rank factorization of the rank r matrix A[mxn].

The goal is to compute the rank r matrices F[mxr] and G[rxn] such that

A = FG (1)

The factorization in (1) is called the full rank factorization of A. Intuition correctly tells us that all [mxn] matrices A with rank r > 0 have a full rank factorization.

(A – 50 Points) Formulate a MATLAB( – oriented algorithm for computing the full rank factorization of the rank r matrix A[mxn].

(B – 50 Points) Apply your algorithm to compute manually the full rank factorization of

A[3x3][pic]

_ _

Carnegie mellon university

Department of electrical and computer engineering

18-771 linear systems spring 2002

_ _

midterm examination

GRADING SHEET

Tuesday 26 February 2002

NAME SCORE

PROBLEM I (90 POINTS)

(A – 10 POINTS)

(B – 20 POINTS)

(C – 10 POINTS)

(D – 10 POINTS)

(E – 10 POINTS)

(F – 10 POINTS)

(G – 10 POINTS)

(H – 10 POINTS)

PROBLEM II (50 POINTS)

(A – 25 POINTS)

(B – 25 POINTS)

PROBLEM III (55 POINTS)

(A – 30 POINTS)

(B – 15 POINTS)

(C – 10 POINTS)

PROBLEM IV (55 POINTS)

PROBLEM V (100 POINTS)

(A – 50 POINTS)

(B – 50 POINTS)

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

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

Google Online Preview   Download