課程名稱︰線性代數二 課程性質︰必\選修 課程教師︰林紹雄 開課學院：理學院 開課系所︰數學系 考試日期（年月日）︰ 2008/06/15 考試時限（分鐘）：180分鐘 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Math 201-14410 (Linear Algebra) Final There are problems A to F with a total of 130 points. Please write down your computational or proof steps clearly on the answer sheets. A.(15 points) Consider the matrix [ 2 -1 0] A= [-1 2 -1]=L+D+U [ 0 -1 2] Write down the Jacobi matrix J=-D^-1(L+U) and the SOR-matrix Lw=(D+wL)^-1 [(1-w)D-wU]. Compute their eigenvalues, and find their spectral radiusρ(J) and ρ(Lw). What is the optimal parameter w(opt) for the SOR-method? B.(20 points) Apply the Householder matrices to find the QR-decomposition of the following matrix, and reduce it to a tridiagonal matrix. [ 1 2 1 0] [ 2 2 -1 0] A= [ 1 -1 1 1] [ 0 0 1 1] C.(15 points) A company produces two types of commodities, A and B, which are sold per unit profits of 3 dollars and 2 dollars respectively,in quantities up to 12 dozens of each commodity per day. The company has three machines to produce A and B. In order to produce each unit of A,5 minutes are required on machine 1,7 minutes on machines 2, and 4 minutes on machine 3.To make each unit of B,3,9, and 7 minutes are requires on machine1 2 and 3 respectively.Find the most profitable amount of A and B the company should produce in each day. D.Consider the linear programming problem T minimize c x subjected to Ax≧b , x≧0 T T where A=[1 4 2] c=[2 1 1] and b=[10 8] [2 3 4] T (a) (10 points)Apply the simplex method to show that x*=[0,12/5,1/5] is the unique optimal feasible solution. (b) (8 points)Write down its dual linear programming problem. Apply the complementary slackness conditions(or the Kuhn-Tucker conditions) to find the unique optimal feasible solution of the dual problem. E.(12 points_ Apply the interior point method method to find the central paths for the primary and the dual problems of the following linear programming problem: maximizing(y1+y2) subjected to -1≦y1≦1 , y2≦1 Then obtain their optimal feasible solutions. F.Work out the following problems. Each has 10 points. (a)Let A belong to Mn(C) and σ(A)={λ1,λ2, ...λn}. Prove that 2 2 2 2 ||A||f ≧|λ1| +|λ2| +......+|λn| and the equality holds iff A is a normal matrix. (where ||A||F is the Frobenius norm of A) (b) Let A=[aij] be a nxn Hessenberg matrix such that a(i,i-1)≠0 for i=2,3..n. If λ is an eigenvalue of A, prove that the nullity of A-λI is 1. Moreover,when σ(A)={0,1} and the algebraic multiplicity of 0 and 1 is 3 and 4 respectively, write down the Jordan canonical form of A. (c) Let A=L+D+U be an nxn matrix with a corresponding decomposition into the lower triangular, diagonal and upper triangular parts,where D^-1 exists. The JOR-method to solve Ax=b is the iteration scheme given by Dx^(k+1)=-w(L+U)x^(k)+(1-w)Dx^(k)+wb for k=0,1,...and x^(0) given. If the Jacobi method for Ax=b converges, prove that the JOR-method also converges for 0＜w≦1. (d) Consider the primal linear programming problem of minimizing c^Tx on F={x belong R^n| Ax=b, x≧0} where A is an mxn real matrix,and c belong R^n,b belong R^m. Then it is impossible for the Phase I method of the primal and the dual problems to have both positive minimum. Is this statement true? (e) Let A belong Mn(C).Zk belong C (k=0,1,2...) is a sequence of numbers. Perform the shifted QR-algorithm to define A^(k) as follows:A^(0)=A and (k) (k) (k) (k+1) (k) (k) A -ZkIn=Q R and A =R Q +ZkIn for k=0,1,2,.... Then it is possible to choose Zk such that A^(k) is in Hessenberg form, but A^(k+1) is not in Hessenberg form. Is this statement true? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.175.32.168 ※ 編輯: whatsme 來自: 218.175.32.168 (06/18 20:51) ※ 編輯: whatsme 來自: 218.175.32.168 (06/18 20:51)