MASTER’S COMPREHENSIVE EXAM NUMERICAL ANALYSIS JANUARY 1997 INSTRUCTIONS: Calculator required. Show eight or more figures in numerical results.

1. For cubic Lagrange interpolation at equidistant points x_{i} = x_{0} + ih, i = 0, 1, 2, 3, one obtains an error estimate of the following form in the central interval x_{1} < x < x_{2}:

(∗)  |f(x) − p_{3}(x)| ≤ K h^{4} max_{x_{0}≤ξ≤x_{3}} |f^{(4)}(ξ)|, if x_{1} < x < x_{2}.

Here, p_{3}(x) is the cubic Lagrange interpolation polynomial of the function f(x), such that p_{3}(x_{i}) = f(x_{i}) for i = 0, 1, 2, 3. Determine the smallest value of K for which (∗) is valid, and prove the validity of (∗) for the value of K that you have found.

2. Solve approximately the equation f(x) ≡ x^{2} − cos x = 0, in the interval 0.5 ≤ x ≤ 1.0, by means of the Simplified Newton method

x_{n+1} = g(x_{n}), g(x) = x − f(x)/m, m = f′(x_{0}), x_{0} = 0.75.

a) For the given iteration function g(x) determine a contraction constant λ, such that

1 > λ ≥ max_{0.5≤x≤1.0} |g′(x)|.

b) Iterate twice, obtaining x_{1}, and x_{2}.

c) Determine α and β, accurate bounds for the root x_{∗} = lim_{n→∞} x_{n} of the equation f(x) = 0 such that 0.5 < α < x_{∗} < β < 1.0. The bounds must be as accurate as possible, incorporate the numerical data from parts a) and b) above, and be based on an error estimate which is a corollary to the Contraction Mapping Theorem.

(CONT’D NEXT PAGE • • •)

3. The Schröder series iteration for solving f(x) = 0, f ∈ C^{∞}(R), is defined by

(∗)  x_{n+1} = g(x_{n}), g(x) = x − \frac{f(x)}{f′(x)} − \frac{[f(x)]^{2}f′′(x)}{2[f′(x)]^{3}}.

a) State a Theorem to the effect that Schröder series iteration (∗) has at least cubic order of convergence. Be precise and include all the needed definitions and conditions.

b) Prove the Theorem that you stated in part a).

4. Given is a matrix A ∈ R^{m×n} and a factorization A = U S V^{T} , where the factors U ∈ R^{m×k}, S ∈ R^{k×k}, and V ∈ R^{n×k} satisfy the conditions

(i) U^{T} U = I_{k}, the kxk identity matrix; (ii) V^{T} V = I_{k}; (iii) S is invertible.

a) Let B = V S^{−1} U^{T} ∈ R^{n×m} and verify that (i) A B A = A, (ii) B A B = B, (iii) A B = (A B)^{T}, (iv) B A = (B A)^{T}.

b) Define column vector norms by ∥w∥^{2} = w^{T} w, and for x ∈ R^{n}, y ∈ R^{m} show that

(I) ∥x∥^{2} = ∥(I_{n} − BA)x∥^{2} + ∥BAx∥^{2}, (II) ∥y∥^{2} = ∥(I_{m} − AB)y∥^{2} + ∥ABy∥^{2}.

5. Apply the Composite Trapezoidal Rule on N subintervals,

T_{N} = h (\frac{1}{2}f(a) + ∑_{i=1}^{N−1} f(a + ih) + \frac{1}{2}f(b)) , h = \frac{b − a}{N},

to approximate J = ∫_{0}^{2π}ln(2 + cos x) dx.

a) Explain why “the Euler-Maclaurin sum formula implies that T_{N} →_{(N→∞)} J very rapidly.”

b) Verify empirically the expected high accuracy of T_{N} by computing both, T_{N} and T_{2N}, for small N (N = 4 or N = 8; recall the recursive procedure in the Romberg Table).