MASTER’S COMPREHENSIVE EXAMS NUMERICAL ANALYSIS AUGUST 1999

INSTRUCTIONS: Calculator required. Show eight or more decimal figures. Two problems completely solved will be sufficient for a passing grade.

1. For a certain computer with 54–bit binary arithmetic the floating point conversion operator fl satisfies

fl(a) = a(1 + δ_{a}), |δ_{a}| ≤ ϵ, ϵ = 2^{−54}.

Given a positive integer n and floating point numbers x_{j}, y_{j}, j = 1, …, n, define z = x•y = ∑_{j=1}^{n} x_{j}y_{j}, where sum and product refer to exact mathematical arithmetic. Define ẑ = x_{ˆ•}y to be the result of computing x•y in 54–bit floating point arithmetic.

a) State an explicit recursive definition for ẑ in terms of the data x_{j}, y_{j} and the floating point operator fl.

b) For the special case of n = 3, prove the rounding error |ẑ − z| may be estimated by

|ẑ − z| ≤ (3.1) ϵ ∑_{j=1}^{3} |x_{j}| |y_{j}|.

2. Given a function f(x) ∈ C^{(6)}([a, b]), denote by p_{5}(x) the Lagrange interpolation polynomial of degree at most five such that p_{5}(x_{j}) = f(x_{j}) at equally spaced points x_{j} = a + j h with stepsize h = \frac{b−a}{5}, j = 0, 1, …, 5. Also, let M_{6} = max_{a≤x≤b} |f^{(6)}(x)|. We seek an upper bound for the interpolation error in the “central interval” that should have the form

(∗)  |f(x) − p_{5}(x)| ≤ K M_{6} h^{6}, x_{2} < x < x_{3}.

Determine the constant K as small as you can so that (∗) is valid.

(CONT’D NEXT PAGE • • •)

3. Use Newton’s method to solve the system of nonlinear equations:

\begin{aligned}1 + x − y^{2} & = 0 \\ y − x^{3} & = 0 \end{aligned}

a) Start with (x, y) = (1.5, 1.5), and continue until ||(x_{n+1}, y_{n+1}) − (x_{n}, y_{n})||_{∞} < 0.001.

b) Explain why Newton’s method converges in this instance.