MASTER’S COMPREHENSIVE EXAM NUMERICAL ANALYSIS AUGUST 1995

INSTRUCTIONS: Calculator required for some problems. Show at least eight (8) figures where numerical results occur.

1. Given t–bit binary floating point numbers a, b, c define x = a ∗ b ∗ c, y = (a˜∗b)˜∗c, z = a˜∗(b˜∗c) barring over- or under-flow. Here, the usual machine floating point operations xω̃y replace exact arithmetic operations xωy, with ω ∈ {+, −, ∗, /}. Estimate the distance ||x − y| − |y ˜−z|| of the true rounding error |x − y| from the machine– computable |y ˜−z|, using only general properties of t–bit binary floating point arithmetic.

2.a) For a positive integer n and real numbers x_{i}, y_{i}, i = 0, 1, …, n, x_{0} < x_{1} < … < x_{n}, state Newton’s formula for the interpolation polynomial p_{n}(x) = ∑_{k=1}^{n} a_{k}x^{k} of degree at most n such that p_{n}(x_{i}) = y_{i}, i = 0, 1, …, n. Recall that Newton’s interpolation formula is based on divided differences.

b) State formulas for the error f(x) − p_{n}(x) given data y_{i} = f(x_{i}), i = 0, 1, …, n.

c) For the special data y_{i} = x_{i}^{n+1}, i = 0, 1, …, n, prove p_{n}(0) = (−1)^{n}x_{0}x_{1} ⋯ x_{n}.

(CONTINUED ON NEXT PAGE • • • )

3. Given is the integration formula, valid for arbitrary functions f ∈ C^{k}[−1, 1],

∫_{−1}^{1} f(x)dx = \frac{7}{15}f(−1) + \frac{16}{15}f(0) + \frac{7}{15}f(1) + \frac{1}{15}f′(−1) − \frac{1}{15}f′(1) + c_{k}f^{(k)}(x̃),

−1 < x̃ < 1. Determine the numerical values of the order k ∈ N in the error term as well as the error constant c_{k}. HINT: Test the formula for monomials f(x) = x^{m}, m = 0, 1, ….

4. The matrix equation Ax = b, with A = [ \begin{matrix}0.780 & 0.563 \\ 0.913 & 0.659 \end{matrix} ] , b = [ \begin{matrix}0.217 \\ 0.254 \end{matrix} ] , has the

column vector x = [1, −1]^{T} as the exact solution. Thus, of the “approximate solutions” y = [0.999, −1.001]^{T} and z = [0.341, −0.087]^{T} the former would be considered to be more accurate (by far) as ∥x − y∥_{∞} < ∥x − z∥_{∞}.

a) For the residuals, however, ∥Ay − b∥_{∞} > ∥Az − b∥_{∞}. Show this is so.

b) Give a quantitative explanation for these seemingly contradictory facts.

5.a) State a definition of convergence of order q (q = 1: linear, q = 2: quadratic, q = 3: cubic,... convergence) of an iteration of the form x_{n} = G(x_{n}), n = 0, 1, …. Here, G(x) is a suitable real function differentiable on a real interval.

b) Given an equation f(x) = 0, where again f(x) is a suitable differentiable function with f′(x) > 0, define G(x) = x − f′(x)^{−1}f(x). Under what conditions is the iteration in part a) at least quadratically (q ≥ 2) convergent? Prove your answer is correct.