MASTER’S COMPREHENSIVE EXAM–NUMERICAL ANALYSIS–AUG 1990

INSTRUCTIONS: Answer all questions in detail. You should use a calculator with more than one memory cell. Show eight digits in all numerical values that you are required to compute.

1. In estimating floating point rounding errors, the following situation arises frequently. Given that individual relative rounding errors δ_{k}, k = 1, …, n have occured, each due to executing a single floating point operation, define the quantity α_{n} by the equation

1 + α_{n} = ∏_{k=1}^{n}(1 + δ_{k}).

Now |δ_{k}| ≤ ϵ, where ϵ = 2^{−t} on a machine with t-bit binary floating point arithmetic, and it is important to have a similar upper bound for |α_{n}|. By mathematical induction prove:

Proposition. If nϵ ≤ .01, then |α_{n}| ≤ (1.011) nϵ.

The hypothesis means that n is not too large.

2. a) For x_{i} = i − 2, i = 0, …, 4, and f(x) = x^{5}, compute the divided difference table.

b) Determine the quartic Newton polynomial p_{4}(x) for these data by means of the above divided difference table.

c) For the error e_{n}(x̄) = |f(x̄) − p_{n}(x̄)| in n-th degree Lagrange interpolation state an upper bound. This should involve the quantity M_{n+1} = max_{−2≤x≤2} |f^{(n+1)}(x)|.

d) Apply the formula to estimate e_{n}(x̄) for the example of parts a) and b). Verify the error is given exactly by the formula. Why?

3. Solve the equation f(x) = x^{5} + 15x − 8 = 0 in the interval I = {x : 0 ≤ x ≤ 1} by means of the iteration x_{n+1} = g(x_{n}) with the iteration function g(x) = x − (0.05)f(x).

a) Carry out several iterations with an initial guess of x_{0} = 0.5. Continuing this way, about how many iterations do you think it would take to obtain roughly 12 correct decimals?

b) Prove convergence of this iteration for any x_{0} in the interval [0, 1]. You may do so by verifying the hypotheses of an important theorem, that permits to draw this kind of inference. You should quote the theorem before you apply it.

4. For ∫_{a}^{b} f(x) dx apply the Composite Trapezoidal Rule T_{N} and the Composite

Simpson Rule S_{N} on N subintervals. Then S_{N} = \frac{4T_{2N} − T_{N}}{3} . Proceeding similarly, define T_{N}^{0} = T_{N} and for each positive integer m let

T_{2N}^{m} = \frac{4^{m}T_{2N}^{m−1} − T_{N}^{m−1}}{4^{m} − 1} .

Then: T_{2N}^{1} = S_{N} and each sequence T_{2^{k}}^{m}, k = 0, 1, …, (known as a column in the Romberg table) converges more rapidly to the integral than the preceding column provided the integrand f ∈ C^{∞}[a, b]. Prove: The preceding statement is a consequence of the fact that an asymptotic expansion (the Euler–Maclaurin Summation Formula) is valid for the error in the Trapezoidal Rule:

∫_{a}^{b} f(x) dx − T_{N} = c_{1}h^{2} + c_{2}h^{4} + … + c_{m}h^{2m} + O(h^{2m+2})

(Here, h = \frac{b−a}{N}.)