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

Final Exam

Jan 12, 2018.

1. (15 pts) Use any desingularization method to evaluate the improper integral

∫_{0}^{∞} \frac{1}{1 + x^{3}} dx

with a composite quadrature rule of 4th order accuracy. Demonstrate numerically that the result is indeed 4th order accurate.

2. (15 pts) Consider discretizing

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

with uniformly spaced grids 0 = x_{0} < x_{1} < ⋯ < x_{5N} = 5, 0 = y_{0} < y_{1} < ⋯ < y_{N} = 1, x_{i} − x_{i−1} = y_{j} − y_{j−1} = h = \frac{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) → ⋯,  (1)

and

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

result in two linear systems A^{(1)}u^{(1)} = f^{(1)} and A^{(2)}u^{(2)} = f^{(2)}. For large N, which linear system is faster to solve using Gaussian elimination without pivoting, combined with backward substitution? or are they the same? Explain.

3. (7+7 pts)

(a) Perform the required row interchanges for the following linear system using scaled partial pivoting:

\begin{aligned}& x_{2}+ & x_{3} = & 4 \\ x_{1}− & 2x_{2}− & x_{3} = & 5 \\ x_{1}− & x_{2}+ & x_{3} = & 6 \end{aligned} ,  (3)

Give all details and the final linear system. Need not solve it.

(b) Find P, L, U in the factorization P A = LU for the matrix

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

where P is the permutation matrix corresponding to partial pivoting.

4. (15 pts) True or False? Explain.

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

5. (15 pts) Write down the definition of ’condition number’. Derive a related inequality that gives an estimate of relative error of the solution of a linear system.

6. (15 pts) Consider the integral equation

u(x_{i}) = f(x_{i}) + ∫_{0}^{1} K(x_{i}, t) u(t) dt, i = 0, ⋯, M,  (5)

where 0 = x_{0} < x_{1} < ⋯ < x_{M} = 1, with x_{j} − x_{j−1} = h = \frac{1}{M}, f(x) = x^{2}, K(x, t) = −\frac{1}{3}e^{−|x−t|} and ∫_{0}^{1} dt is evaluated using trapezoidal rule.

Form the linear system, find an convergent iterative method, explain why your method converges. Need not solve it.

7. (15 pts) 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. (8 pts) Find the constants a, b, c so that, the quadrature

∫_{−h}^{h} f(x)dx ≈ h · (af(−h) + bf(0) + cf(h)) has highest degree of precision, where f is

sufficiently smooth. Under the assumption (need not prove this assumption) that the error of this quadrature is of the form

∫_{−h}^{h} f(x)dx − h · (af(−h) + bf(0) + cf(h)) = Kf^{(n)}(ξ)h^{p},

find K, n and p.

9. (8 pts) Use any method to solve the nonlinear system of equations

\begin{aligned}1x_{1} + 2x_{2} + 0.03 ∗ sin(x_{1} + x_{2}) & = 4 \\ 5x_{1} + 6x_{2} + 0.07 ∗ cos(x_{1} − x_{2}) & = 8 \end{aligned}

Write your answer in the format of ’format long e’ and hand in your code.