MASTER’S COMPREHENSIVE EXAMS Numerical Analysis August 2000

A computing machine may be used. Copy all required results from screen. Show ten or more decimal figures. Three problems completely solved will be sufficient for a passing grade.

1. For a positive constant a > 0 let x_{0} be an approximate squareroot,

x_{0} ≈ \sqrt{a}, x_{0} > 0.

Suppose that x_{0} has been computed in double precision, and the relative error ϵ of the square x_{0}^{2} is known: ϵ = \frac{1}{a}|x_{0}^{2} − a|. If ϵ = 10^{−15}, determine an accurate estimate of the relative error δ of x_{0} itself, δ = \frac{1}{\sqrt{a}}|x_{0} − \sqrt{a}|.

Hint: This relates to the condition number K = \frac{a f′(a)}{f(a)} of the square root function

x = f(a) = \sqrt{a}, f′(a) = \frac{dx}{da}.

2. One popular method for solving an equation f(x) = 0 is the Secant Method. A solution x_{∗} of the equation is given, i.e., x_{∗} ∈ R and f(x_{∗}) = 0. It is also known that f(x) ∈ C^{2}(R), and f′(x) > 0, ∀x ∈ R.

a) State a definition of the Secant Method in the form of x_{n+1} = T (x_{n}, x_{n−1}), with an operation x = T (a, b) that involves function values f(a) and f(b).

b) Show that the operation x = T (a, b) satisfies the equation T (a, b) = T (b, a).

c) Define the errors e_{m} = |x_{m} − x_{∗}|. Show that there is an equation e_{n+1} = M_{n} e_{n} e_{n−1} and find an expression in terms of derivatives of f(x) for the factor M_{n}.

(CONT’D NEXT PAGE • • •)

3.a) Calculate the LU-factors of the matrix A = [ \begin{matrix}3 & −1 & 1 \\ 2 & −1 & 1 \\ −1 & 1 & 1 \end{matrix} ] = L U. We require L

to be unit-lower triangular and U upper triangular.

b) By means of the LU-factors from a) solve the equations Ly = b, Ux = y, and

Ax = b in that order, where the given right-hand side vector B is b = [ \begin{matrix}6 \\ 5 \\ 6 \end{matrix} ] . You

may not apply Gaussian elimination, pivoting, or the inverse of A to obtain x, but only involve the LU-factors, and the vectors y, b. This process is known as triangular solving or backsubstitution. Show all results, L, U, y, x.

4. A certain quadrature formula with error term exists of the form

∫_{0}^{h} f(x)dx = A_{1} f(0) + A_{2} f(\frac{h}{2}) + A_{3} f(h) + E(f).

It is known that given f(x) ∈ C^{4}([0, h]), the error E(f) can be expressed in terms of the fourth derivative of the integrand,

E(f) = C h^{5} f^{iv}(x̃), 0 < x̃ < h.

Determine the constant A_{1}, A_{2}, A_{3} and C, and, by means of a Taylor series expansion of the integral, prove the validity of the formula.