MASTER’S COMPREHENSIVE EXAMS Numerical Analysis January 2000

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

1. Consider the following data (at right).

a) Find the Newton form of the interpolating polynomial.

b) Use this form to approximate f(0.5).

c) Given that the above data actually comes from f(x) = sin(x), obtain a bound on the error (without computing the actual value).

d) Compare with the actual error.

\underline{x f(x)} 0.0 0.0 0.2 0.19867 0.4 0.38942 0.6 0.56464 0.8 0.71736 1.0 0.84147

2. Prove the iteration (Schröder series)

x_{n+1} = x_{n} − \frac{f(x_{n})}{f′(x_{n})} − \frac{f(x_{n})^{2} f′′(x_{n})}{2 f′(x_{n})^{3}}

has at least cubic order of convergence to a root of the equation f(x) = 0 when started in the neighborhood of a solution, under reasonable assumptions on the function f(x) and its derivatives f′(x), f′′(x). Be explicit about applicable definitions and required conditions.

(CONT’D NEXT PAGE • • •)

3.a) For ∫_{a}^{b} f(x) dx state formulas defining the Composite Trapezoidal Rule T_{N}, the Composite Midpoint Rule M_{N}, and the Composite Simpson Rule S_{N} on N subintervals of equal length.

b) Show the following formulas are correct (these are useful for efficient coding of the Romberg table):

T_{2N} = \frac{1}{2}(T_{N} + M_{N});
S_{N} = \frac{4T_{2N} − T_{N}}{3}

= \frac{T_{N} + 2 M_{N}}{3} .

4. Consider the matrix A = [ \begin{matrix}2.00 & −1.99 \\ −1.98 & 1.97 \end{matrix} ] . Solving the equation Ax = b with

b = [ \begin{matrix}7.98 \\ −7.90 \end{matrix} ] , the solution vector is x, while the right–hand side vector b̂ = [ \begin{matrix}7.9801 \\ −7.8999 \end{matrix} ] results in x̂ as solution of Ax̂ = b̂.

a) Compute the solution vectors x, x̂ as well as the error vector e = x̂ − x and the residual vector r = b̂ − b.

b) Using the ∞–norm, ∥x∥ = max_{j=1..n} |x_{j}|, determine numerically the norm–relative error, e_{rel} = ∥e∥/∥x∥ as well as the norm–relative residual, r_{rel} = ∥r∥/∥b∥, and decide whether the ratio e_{rel}/r_{rel} is maximal for this given matrix A. HINT: You will need the condition number of the matrix.