MASTER’S COMPREHENSIVE EXAM–NUMERICAL ANALYSIS AUGUST 1993 INSTRUCTION: Calculator required for some problems. Show at least eight (8) figures in numerical results, or exact answer if available.

1. For a binary floating point machine with t-bit mantissa, t = 24, let fl(x) denote the symmetrically rounded machine approximation of x, x ∈ R (barring over- or underflow). Let x = 2^{−1} + 2^{−24}, y = 2^{−2} + 2^{−25}, z = 2^{−3} + 2^{−26}.

a) Are these machine numbers? Given machine numbers x, y explain on what grounds one would claim machine addition can be defined by the mathematical operation x ˆ+y = fl(x + y) (again, barring over- or underflow).

b) Compute s_{1} = (x ˆ+y) ˆ+z, s_{2} = x ˆ+(y ˆ+z).

c) Is machine addition associative in this example?

2. This problem considers the (2n-1)-st degree Lagrange interpolation polynomial p_{n}(x) at equidistant nodes x_{k}, k ∈ {1, 2, ⋯, n − 1, n, n + 1, n + 2, ⋯, 2n − 1, 2n}, given by

x_{k} = \frac{2k − 2n − 1}{2n − 1} ∈ [−1, 1], k = 1, …, 2n.

Equivalently, the interpolation nodes (in a different order) are given by

x_{k} = ±\frac{1}{2n − 1}, ±\frac{3}{2n − 1}, ⋯, ±\frac{2n − 3}{2n − 1}, ±\frac{2n − 1}{2n − 1} = ±1.

a) Using M_{2n} = \frac{1}{(2n)!} max_{−1≤x≤1} |f^{(2n)}(x)| < ∞ , state a general upper bound estimate for the interpolation error

e_{2n−1}(x̄) = |f(x̄) − p_{2n−1}(x̄)|,

for a function f(x), defined and (2n)–times continuously differentiable on the interval [−1, 1].

b) For the special nodes stated above and for the special interval \frac{−1}{2n − 1} < x < \frac{1}{2n − 1}

show e_{2n−1}(x̄) ≤ M_{2n} ∏_{k=1}^{2n} x_{k}^{2}.

M O R E O N B A C K … 3. By Newton’s method compute a real root x of the equation

f(x) = x^{5} − 4x^{4} + 9x^{3} − 8x^{2} + 5x − 1 = 0,

beginning with x_{0} = 0.5. Be careful to state as many accurate iterates as possible.

4. Solve the system Ax = b, where A = QR, with A, Q, R, b given below.

a) Show that Q^{T} Q = I (the 4 × 4 identity matrix).

b) Letting y = Rx obtain an algorithm to solve Ax = b for x which requires only minimal computational effort in its execution. HINT: The desired algorithm involves two easily solved linear systems. Don’t compute A^{−1} explicitely!

c) Solve the given system by means of the algorithm that you have devised in part b) above.

A = [ \begin{matrix}1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 2 \\ 1 & 2 & 2 & 3 \\ 1 & 2 & 3 & 6 \end{matrix} ] , Q = \frac{1}{2} [ \begin{matrix}1 & −1 & −1 & 1 \\ 1 & −1 & 1 & −1 \\ 1 & 1 & −1 & −1 \\ 1 & 1 & 1 & 1 \end{matrix} ] ,

R = [ \begin{matrix}2 & 3 & 4 & 6 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{matrix} ] , b = [ \begin{matrix}2 \\ 2 \\ 2 \\ 0 \end{matrix} ] .

5. The four-point Gauss-Lobatto quadrature formula is given by the equation

∫_{−1}^{1} f(x) dx = A_{1}f(−1) + A_{2}f(1) + A_{3}f(\sqrt{0.2}) + A_{4}f(−\sqrt{0.2}) + E_{6}^{Lob}.

The error term is known to satisfy E_{6}^{Lob} = c_{6}f^{(6)}(x̃), −1 < x̃ < 1.

a) Determine the weights A_{k}, k = 1, 2, 3, 4.

b) Compute the error constant c_{6}. HINT: Substitute f(x) = x^{m}, m = 0, 1, …, 6.