Numerical Analysis I, Fall 2011 (http://www.math.nthu.edu.tw/˜ wangwc/)

Final Exam

Jan 13, 2012, 13:10PM.

1. (12 pts ×4 ) Consider solving the nonlinear scalar equation exp(x) − 0.99 = 0.

(a) Give a convergent fixed point iteration. Explain why it converges. Then start with x_{0} = 1, report x_{1} and x_{2}.

(b) Give formula for the secant method. Then start with x_{0} = 2, x_{1} = 1, report x_{2} and x_{3}.

(c) Give formula for the Newton’s method. Then start with x_{0} = 1, report x_{1} and x_{2}.

(d) Give a cubically convergent iterative method. Then start with x_{0} = 1, report x_{1} and x_{2}.

2. (16 pts ×2) Consider solving the nonlinear system of equations sin(sin(x) + 2y) = 0.01, 5x + sin(6y) = 0.02.

(a) Give formula for the Newton’s method. Then start with (x_{0}, y_{0}) = (0, 0), report (x_{1}, y_{1}) and (x_{2}, y_{2}) and your final answer.

(b) Give a convergent fixed point iteration. Explain why it converges. Then start with

(x_{0}, y_{0}) = (0, 0), report (x_{1}, y_{1}) and (x_{2}, y_{2}).

3. (12 pts ×3) The following is a pseudo-code of Gauss-Siedel iteration for some linear system: u_{0} = 0, u_{N} = 0,

do k = 1, ⋯,
do i = 1, ⋯, N − 1,
u_{i} = −0.5 ∗ (u_{i−1} + u_{i+1}) + sin(iπ/N)
end i
end k

(1)

(a) Write a pseudo-code for Jacobi and SOR methods for the same linear system.

(b) Estimate the relative error of the numerical solution for N = 1, 000. Explain (Need not implement).

(c) Repeat (a) (only (a)) for the following system:

u_{0,0} = u_{1,0} = ⋯ = u_{N,0} = 0 u_{0,N} = u_{1,N} = ⋯ = u_{N,N} = 0

u_{0,0} = u_{0,1} = ⋯ = u_{0,N} = 0 u_{N,0} = u_{N,1} = ⋯ = u_{N,N} = 0
do k = 1, ⋯,
do j = 1, ⋯, N − 1,
do i = 1, ⋯, N − 1,
u_{i,j} = −0.25 ∗ (u_{i−1,j} + u_{i+1,j} + u_{i,j−1} + u_{i,j+1}) + sin(iπ/N) sin(jπ/N)
end i
end j
end k

(2)

4. (12 pts) Find the polynomial p(x) that minimizes ∫_{0}^{1}(e^{x} − p(x))^{2}dx among all quadratic polynomials.

5. (12 pts) Derive Aitken’s Δ^{2} acceleration method. Then apply it to the sequence a_{n} = (\frac{1}{2})^{n}.