Numerical Analysis

A student taking the exam for “breadth” must answer three (3) questions and these must be handed in after two hours. A student taking the exam for “depth” must answer six (6) questions, with at least three (3) chosen from problems 6-10.

1. In a graphics program destined for a very small machine, the distance

d := \sqrt{(x_{1} − x_{2})^{2} + (y_{1} − y_{2})^{2}}

between two points (x_{1}, y_{1}) and (x_{2}, y_{2}) needs to be computed, but, for reasons of speed and memory requirements, the direct use of the squareroot function is not desirable.

How could you compute d to ‘graphic accuracy’, say within 1%, using just arithmetic operations (and comparisons)? Could you do it in less than 10 floating point operations?

(Hint: Assuming |x_{1} − x_{2}| ≥ |y_{1} − y_{2}|, one has d = |x_{1} − x_{2}|\sqrt{1 + r} with r ∈ [0, 1].)

2. Describe the Choleski factorization of a matrix and its uses. Is it possible to obtain the advantage of the Choleski factorization without the use of squareroots?

3. Discuss the uses (if any) of the determinant in numerical calculations.

4. Here is an algorithm:

input: the n × n matrix A and the n-vector x.

do until satisfied: compute y := Ax, then set x := y/∥y∥.

output: the final n-vector x.

(a) What is this algorithm used for?

(b) State and prove a sufficient condition for the convergence of the algorithm.

(c) Explain why the algorithm might not converge for the particular input

A = ( \begin{matrix}2 & 1 & 0 \\ 2 & 3 & 0 \\ 9 & −7 & −4 \end{matrix} )

(d) Suggest another iterative method which would provide the desired answer for this particular A.

5. (a) State and prove a necessary and sufficient condition on the matrix A for Gauß elimination without pivoting to achieve its goal in an infinite precision environment.

(b) Give a detailed example to show that the assumption of an infinite precision environment is essential for your answer to (a).

6. Let P be the n-dimensional space spanned by the monomials x, x^{2},…, x^{n}, and let x_{1},…, x_{n} be n distinct points. For given data y_{1},…, y_{n}, we look for p ∈ P which matches these data at the x_{j}, i.e., satisfies

p(x_{j}) = y_{j} j = 1,…, n.

(a) Prove or disprove the statement “A solution for all possible data y_{1},…, y_{n} exists if and only if there is at most one solution for some data”.

(b) Prove that there exists a unique solution to the above interpolation problem in case none of the x_{j} is zero.

In your proof, you may rely on known results concerning interpolation from span{1, x,…, x^{n}}.

7. Consider the boundary value problem

Δu = \frac{∂^{2}u}{∂x^{2}} + \frac{∂^{2}u}{∂y^{2}} − (1 + \frac{1}{2} sin x)u = 1 + x^{2}  in Ω  (7.1)
u = 0  on ∂Ω  (7.2)

Let Ω be the unit square, i.e., 0 < x, y < 1. Consider the finite difference equation

U_{k+1,j} + U_{k−1,j} + U_{k,j+1} + U_{k,j−1} − [4 + h^{2}(1 + \frac{1}{2} sin kh)]U_{kj} = (1 + (kh)^{2})h^{2}

for 1 ≤ k, j ≤ N, and

U_{k,0} = U_{k,N+1} = U_{0,j} = U_{N+1,j} = 0,

with h := 1/(N + 1).

(a) Discuss the convergence of U_{kj} to u(x, y).

(b) Obtain a good bound for the finite difference solution, i.e., an M for which

|U_{kj}| ≤ M for all k, j, h.

8. Consider the system

−x_{k−2} + x_{k−1} + 7x_{k} − x_{k+1} + x_{k+2} = y_{k}, k = 1, 2,…, N
x_{−2} = x_{−1} = x_{N+1} = x_{N+2} = 0

of linear equations.

(a) Is the system solvable? (Explain your answer.)

(b) Give a good estimate for the constant K_{N} (which may depend on N) for which

∥x∥_{∞} ≤ K_{N}∥y∥_{∞}

for all y.

(c) Give a convergent iteration method for obtaining the solution x and discuss its convergence properties.

9. Consider the initial value problem

y′ = f(t, y),  y(t_{0}) = y_{0}.  (9.1)

Discuss (a) the stability, and (b) the convergence of the two numerical schemes

Y_{N} − \frac{3}{2}Y_{N−1} + \frac{1}{2}Y_{N−2} = \frac{h}{2}f(Y_{N−1})  (9.2)
Y_{N} − \frac{3}{2}Y_{N−1} + \frac{1}{2}Y_{N−2} = \frac{h}{4}[f(Y_{N−1}) + f(Y_{N−2})]  (9.3)

10. Show that the finite difference scheme

\begin{aligned}w_{m}^{n} & = v_{m}^{n} + \frac{1}{4}Δt b δ^{2}v_{m}^{n} \\ v_{m}^{n+1} & = v_{m}^{n} + Δt b δ^{2}w_{m}^{n} \end{aligned}

for the heat equation u_{t} = bu_{xx} (with b > 0) is stable for bΔt ≤ (Δx)^{2}.