課程名稱︰計算數學導論 課程性質︰數學系大三必修 課程教師︰陳宜良 開課學院：理學院 開課系所︰數學系 考試日期（年月日）︰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. -- 移居二次元(|R^2)的注意事項： 3. 如果你在從事random walk，往上下左右的 1. connectedness不保證pathwise connec- 的機率都是1/4，則你能回家的機率是1。 tedness。可能你跟你的幼馴染住很近， 4. 下面這個PDE是二次元上的波方程式 卻永遠沒辦法到她家。 http://i.imgur.com/2H9HllP.png 2. ODE的C^1 autonomous system不會出現 它的解不滿足Huygens' principle，因此 chaos，在預測事情上比較方便。 講話時會聽到自己的回音，很不方便。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.212.7 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1449582954.A.244.html ※ 編輯: xavier13540 (140.112.212.7), 12/08/2015 21:59:41 ※ 編輯: xavier13540 (140.112.212.7), 12/08/2015 22:01:00