課程名稱︰計算數學導論
課程性質︰數學系大三必修
課程教師︰陳宜良
開課學院：理學院
開課系所︰數學系
考試日期（年月日）︰2015/11/23
考試時限（分鐘）：180
試題 :
k
1. Let us solve the equation x = a, a > 0 and k > 1 is an integer by Newton's
method.
(a) (5%) Write down the Newton iteration: x = g(x ) for solving this
n+1 n
equation.
1/k
(b) (5%) Show that the fixed point iteration g of Newton's method maps [a ,
1/k 1/k 1/k
∞) → [a , ∞) and (0, a ) → (a , ∞).
1/k
(c) (5%) Show g is increasing on (a , ∞).
(d) (5%) Show that the sequence x = g(x ) converges quadratically.
n+1 n
n m
2. Let A = (a ) be a linear map from (|R , |・| ) → (|R , |・| ).
ij m ×n ∞ ∞
(a) (5%) Show that the operator norm ║A║ := sup |Ax| is given
∞ |x| = 1 ∞
∞
by max Σ |a |.
i j ij
(b) (5%) Write a pseudo code for Jacobi method for solving the linear system
Ax = b
n
where A is n ×n and x, b ∈ |R .
(c) (10%) A matrix A is called row diagonally dominant if |a | >
ii
Σ |a |. Prove that the Jacobi method converges for a row diagonally
j≠i ij
dominant matrix A.
3. Let us find the largest eigenvalue in magnitude of an n ×n matrix A.
(a) (10%) Write down a pseudocode for power method to solve this problem.
(b) (10%) Suppose the eigenvalue of A are ordered by
|λ | > |λ | > ...
1 2
Show that the power method converges if λ is simple. Find the
1
convergent rate also.
4. This problem is about interpolation. Let f be function on [-1, 1]. Let x <
0
x < ... < x be grid points on [-1, 1].
1 n
(a) (5%) Write down the polynomial P that interpolates f at x , x , x , x .
0 1 2 3
(b) (5%) Show that there exists an ξ ∈ (x , x ) such that
0 3
(4)
f (ξ) 3
f(x) - P(x) = ──── Π (x - x ).
4! i=0 i
(c) (10%) What is Runge phenomenon? How to fix it? (explain your argument,
but no need to prove)
5. This problem is about Fourier transform.
(a) (10%) Derive the Fast Fourier Transform (FFT) algorithm.
(b) (5%) What is Gibbs phenomenon? (10%) Prove it.