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

Final Exam

15 pts each, total 150 pts. Hand in code problem 3 and 8

1. Describe Choleski decomposition and write a pseudo-code.

2. True or False?

Suppose that A = N − P is nonsingular. Then the iteration Nx^{(k+1)} = b + P x^{(k)} converges for any x^{(0)} if N is nonsingular and T = N^{−1}P satisfies ∥T ∥ < 1 for some matrix norm ∥ · ∥.

3. Solve for Ax = b with an iterative method, where

A = ( \begin{matrix}1/2 & −1 & 0 \\ 1 & 1/2 & 0 \\ −1 & 1 & 1/2 \end{matrix} )  (1)

and b = (1, 1, 1)^{T}. To get a convergent iteration, try with a proper splitting A = N −P and analyze the eigenvalues of the corresponding T. If you don’t know how to analyze it, you can use matlab to help you find the eigenvalues of T. If you cannot find a convergent iteration, change the diagonal entries to −3. If you do this one correctly, you get (minimal) partial credit.

4. 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

(2)

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

5. Consider discretizing

(∂_{x}^{2} + ∂_{y}^{2})u(x, y) = f(x, y), (x, y) ∈ (0, 2) × (0, 1) u = 0, on the boundary of (0, 2) × (0, 1)

(3)

with uniformly spaced grids 0 = x_{0} < x_{1} < ⋯ < x_{2N} = 2, 0 = y_{0} < y_{1} < ⋯ < y_{N} = 1, x_{i} − x_{i−1} = y_{j} − y_{j−1} = h = 1/N, using second order centered finite difference method. The following two possible ordering of the unknowns u_{i,j},

(i, j) = (1, 1) → (1, 2) → ⋯ → (1, N − 1) → (2, 1) → (2, 2) → ⋯,  (4)

and

(i, j) = (1, 1) → (2, 1) → ⋯ → (2N − 1, 1) → (1, 2) → (2, 2) → ⋯,  (5)

result in two linear systems A^{(1)}x = b^{(1)} and A^{(2)}x = b^{(2)}. Which one is faster to solve using LU decomposition? or are they the same? Explain.

6. Derive the inequality that defines the condition number.

7. Find the polynomial p(x) that minimizes ∫_{0}^{1}(sin x−p(x))^{2}dx among all odd polynomials (p(−x) = −p(x)) with degree less than or equal to 5. Derive the linear system and need not solve it numerically.

8. Evaluate (1 + 10^{−7})^{\frac{1}{4}} − (1 − 10^{−7})^{\frac{1}{4}} to 15 correct digits. No points for less than 10 correct digits.

9. Suppose f is smooth and the data f(x), f(x ± h), f(x ± 2h), ⋯ are prescribed. Find an approximation of f^{(3)}(x + \frac{h}{2}) with minimal number of data points and derive an error bound of the form |f^{(3)}(x + \frac{h}{2}) − f_{h}^{(3)}(x + \frac{h}{2})| ≤ C|f^{(n)}(ξ_{2})|h^{p}.

10. Find a quadrature of the form

∫_{−1}^{1} f(x)dx = a(f(c) + f(−c)) + bf(0)

with largest degree of precision p, where a, b ∈ R and 0 < c < 1 are to be determined. Find the value p and derive the equations for a, b, c but need not solve them.