課程名稱︰計算數學導論 課程性質︰數學系大三必修 課程教師︰薛克民 開課學院：理學院 開課系所︰數學系 考試日期︰2012年01月09日(一)，15:30-17:20 考試時限：170分鐘 是否需發放獎勵金：是 試題 : 國立臺灣大學100學年度第1學期 221 U4280計算數學導論 　　　　　　　　　　　　　　　Written Test Date: 15:30-17:20, 01/09, 2012 (1) Open books, notes, and laptop. (2) Total points 100. 1. (20 points) The Newton's iteration function defined by 　　　　　　　　　　 x^2 - c 　　　　ψ(x) = x - --------- 　　　　　　　　　　　 2x 　　belongs to a fixed point method x_(n+1) = ψ(x_n), n≧0, yielding √c with 　　quadratic convergence to the root-finding problem f(x) = x^2 - c = 0. 　　Suppose that we consdier a modification of it that has the form 　　　　　　　　　　　x^2 - c 　　　　ψ(x) = x - (---------)h(x). 　　　　　　　　　　　　2x 　　(a) (10 points) What are the conditions to be satisfied by h at the point 　　　　x = √c, if cubic convergnece is to be achieved? 　　(b) (10 points) Find an h of the form 　　　　　h(x) = a + bx^(-2) 　　　　satisfying these requirements. 2. (30 points) Many applications give rise to linear systmes involving 　　tridiagonal matrices, i.e., matrices that are zero except for the main 　　diagonal, first superdiagonal, and first subdiagonal. Hence algorithms for 　　efficiently solving such systems are highly important. Though the inverse 　　of a tridiagonal matrix is typically dense, the factors in the LU 　　decomposition are bidiagonal. 　　 (a) (10 points) Suppose we have a generic 3 ×3 tridiagonal matrix that 　　　　 can be factored into A = LU: 　　　　　　　┌ a1 c1 0 ┐　　　　┌ 1 0 0 ┐　　　　┌ u11 u12 0 ┐ 　　　　　A = │ b1 a2 c2 │，　L = │L21 1 0 │，　U = │ 0 u22 u23 │ 　　　　　　　└ 0 b2 a3 ┘　　　　└ 0 L32 1 ┘　　　　└ 0 0 u33 ┘ 　　　　Work out simple formulas for computing u11,u12,L21,u22,... in terms of 　　　　the entries of the tridiagonal matrix A. 　　 (b) (10 points) Generalize this procedure to obtain an algorithm for 　　　　computing the LU factorization of an arbitrary m ×m tridiagonal matrix 　　　　(assuming no divisions-by-zero occur). The matrix L should have ones on 　　　　the main diagonal, entries L_(j+1,j) on the first subdiagonal, and 　　　　zeros everywhere else. The matrix U should have entries u_(j,j) on the 　　　　main diagonal, u_(j,j+1) on the first superdiagonal, and zeros 　　　　elsewhere. 　　 (c) (10 points) Having computed the factorization A = LU in (b), explain 　　　　how to efficiently solve the linear system Ax = b. Roughly estimate the 　　　　number of floating point operations required (o.e., O(m), O(m^2), or 　　　　O(m^3), etc.), and compare to the operation count required if L and U 　　　　were dense. 3. (20 points) Let a≦x0＜x1＜…＜xm≦b be an arbitrary partition of the 　　interval [a,b]. Show that there exist unique numbers γ0,γ1,...,γm 　　such that 　　　　 m　　　　　　　　 b 　　　　Σ [γj *p(xj)] = ∫p(x)dx 　　　　j=0　　　　　　　　a 　　for all polynomials p with degree(p)≦m. 4. (30 points) The three-eighths rule is a 4-point interpolatory quadrature 　　method that exactly integrates cubic polynomials. It is defined by the 　　formula 　　　　　　　　3h 　　　　I(f) = ----( f(a) + 3f(a+h) + 3f(a+2h) + f(b)), 　　　　　　　　8 　　where h = (b-a)/3. Prove that there exists ξ∈[a,b] such that 　　　　　　　　b　　　　　　　　　 3　 5 (4) 　　　　E(f) = ∫f(x)dx - I(f) = - ---- h * f (ξ). 　　　　　　　　a　　　　　　　　　 80 --

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