→ t0444564 :已收錄 05/06 02:11
課程名稱︰計算數學導論
課程性質︰數學系大三必修
課程教師︰薛克民
開課學院：理學院
開課系所︰數學系
考試日期︰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