課程名稱︰線性代數二 課程性質︰必修 課程教師︰林紹雄 開課學院：理學院 開課系所︰數學系 考試日期（年月日）︰2012/6/16 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : There are problems A to F with a total of 140 points. Please write down your computational or proof steps clearly on the answer sheets. ----------------------------------------------------------------------------- A. Consider A = ┌ 1 -a ┐ , where a >=0 is a constant. └ -4a 1 ┘ (a) (10 points) Write down the associated Jacobi matrix J and the SOR-matrix Lω. Compute their eigenvalues, and find ρ(J) and p(Lω). (b) (10 points) If 0 < ω < 1, show that the Jacobi method converges iff the SOR-method converges iff A is a M-matrix. (c) (5 points) Find the optimal parameter ωopt for the SOR-method. ----------------------------------------------------------------------------- B. (15 points) A feed-mix company is preparing a mixture of three feeds, feed 1, feed 2 and feed 3. Each unit of feed 1 contains 1 gram of protein, 2 grams of fat, and cost 20 cents; each unit of feed 2 contains 2 grams of protein, 2 grams of fat, and cost 30 cents; each unit of feed 3 contains 2 grams of protein, 1 gram of fat, and cost 25 cents. If the mixture of these three feeds must contain at least 200 grams of protein, and at least 150 grams of fat, how many units of each feed should the company use so as to minimize costs? ----------------------------------------------------------------------------- C. Consider the linear programming problem of minimizing x1 + x2 - x3 subjected to 2x1 - 4x2 + x3 <= 4, 3x1 + 5x2 + x3 <= 2 and xj >= 0 (j = 1, 2, 3). (a) (4 points) Apply whatever method (Farka's lemma, or the phase I method, or...) to show that this problem is feasible. (b) (9 points) Apply the simplex method to find an optimal feasible solution. (c) (7 points) Write down the dual problem. Apply the complementary slackness conditions to find the optimal feasible solution of the dual problem complemantary to the solution in (b). ----------------------------------------------------------------------------- D. (10 points) Find a Nash equilibrium for the two-person game with payoff matrix ┌ (3,1) (1,3) ┐. │ (2,2) (2,1) │ └ (1,1) (3,0) ┘ ----------------------------------------------------------------------------- E. (15 points) Players A and B play the scissor-paper-stone-glass-water game. The two players simultaneously choose one of the five objects. (有給圖但不好畫，以說明代替如下: 石頭贏水，水贏杯子.剪刀.紙， 剪刀贏石頭.杯子，杯子贏石頭.布，布贏石頭.剪刀) The winner gets $1 pay from the loser. Find the optimal mixed strategy for both players. ----------------------------------------------------------------------------- F. Work out the following problems. (a) (12 points) Let A ∈ M(n,F) be an irreducible Hessenberg matrix, and α∈ F. Perfrom the QR-decomposition A - αI = QR, and n define A' = RQ + αI . If α 不屬於 ρ(A), prove that A' n is also an irreducible Hessenberg matrix. (b) (8 points) The Jacobi method applied to a positive definite matrix always converges. Is this a true statement? (c) (10 points) Assume that A ∈ M(n,F) has a decomposition A = S - T with S, T ∈ M(n,F) such that S is invertible. If the sequence (k) (k+1) (k) x defined by the iteration scheme Sx = Tx + b (0) (k = 0, 1, ...) converges for all b, x ∈ F(n). Prove that A is nonsingular. T T (d) (15 points) Let A ∈ M(m ×n,R) have row vectors v1, ..., vm T T m (so that A = [v1...vm] ), and b = [b1...bm] ∈ R . n Define P = {x ∈ R | x >= 0, and Ax >= b}. Prove that x* ∈ P is an extreme point of P iff the set T {vi | i = 1, ..., m, vi x* = bi} contains n linearly independent vectors. (e) (10 points) There exists a nonzero payoff matrix A ∈ M(3 ×2,R) for a two-person zero-sum game whose Von Newmann value is 0, while the optimal strategies x*, y* for both players satisfy x* > 0, y* > 0. Is this a true statement? -- --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.239.2