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

1. For linear interpolation at points x_{0}, x_{1} = x_{0} + h, h > 0, one obtains an error estimate:

(∗)  |f(x) − p_{1}(x)| ≤ \frac{h^{2}}{8} max_{x_{0}≤x̃≤x_{1}} |f^{(2)}(x̃)|.

Here, p_{1}(x) is the linear Lagrange interpolation polynomial of the function f(x), such that p_{1}(x_{i}) = f(x_{i}) for i = 0, 1. Prove the correctness of the estimate (∗) for functions f ∈ C^{2}[x_{0}, x_{1}].

2. As a numerical approach toward solving the equation f(x) = x − cos x = 0, estimate the error |x_{1} − x_{∗}| as accurately as you can, where f(x_{∗}) = 0, and x_{1} = x_{0} − f(x_{0})/f′(x_{0}), x_{0} = 0.75. HINT: Consider the mapping g(x) = x − f(x)/m, m = f′(x_{0}), for example on the interval given by 0.7 ≤ x ≤ 0.8. Apply a corollary of the Contraction Mapping Theorem. You may choose a different interval, if you wish.

3.a) Given a function f ∈ C^{2}(I), with I = [a, b] an interval, x ∈ I ⟺ −∞ < a ≤ x ≤ b < ∞, the Newton iteration for solving f(x) = 0 is defined by

(∗)  x_{n+1} = g(x_{n}), g(x) = x − \frac{f(x)}{f′(x)}.

If an initial point x_{0} of the independent variable is given, the sequence generated by the Newton method may or may not converge to a solution of the equation. If it does, how rapid is the convergence? State definitions and a theorem guaranteeing, under suitbable conditions, the Newton method converges and has a certain order of convergence.

b) Prove the Theorem that you stated in part a) concerning convergence and order of convergence of the Newton iteration (∗).

(CONT’D NEXT PAGE • • •)

4. Consider the matrix A = [ \begin{matrix}2/7 & 4/7 & −1/7 \\ 3/7 & −1/7 & −5/7 \\ 6/7 & −9/7 & 11/7 \end{matrix} ] ∈ R^{3×3} which has the factorization

A = Q R with Q = [ \begin{matrix}2/7 & 6/7 & 3/7 \\ 3/7 & 2/7 & −6/7 \\ 6/7 & −3/7 & 2/7 \end{matrix} ] ∈ R^{3×3} and R = [ \begin{matrix}1 & −1 & 1 \\ 0 & 1 & −1 \\ 0 & 0 & 1 \end{matrix} ] ∈ R^{3×3}.

a) Verify the equations A = QR, Q^{−1} = Q^{T}.

b) Solve the equation A x = b given the vector b = [ \begin{matrix}5 \\ −10 \\ −13 \end{matrix} ] ∈ R^{3} for the unknown vector

x ∈ R^{3}, by using what you know about the matrices A, Q, and R, and by applying Gaussian elimination to a suitable equation R x = y, but without explicitly computing the numerical entries of A^{−1} or R^{−1}.

5.a) Compute terms of the Romberg Table for the integral

I = ∫_{0}^{1}\sqrt{2 + cos x} dx,

in the first three (3) columns at most, but sufficient in number to obtain at least five (5) correct decimals in your best approximate value for the integral I. Use plausible (or heuristic) reasoning in deciding on the accuracy.

b) State rates of convergence of the columns of the Romberg table (these are consequences of the Euler-MacLaurin summation formula), suitable for heuristic estimates of accuracy in part a) above.