Numerical Analysis

A student taking the exam for “breadth” must answer three (3) questions. A student taking the exam for “depth” must answer six (6) questions, with at least three (3) chosen from problems 6–10. In either case, the answers to three questions must be turned in after 2 hours and these will be the only questions looked at for the “breadth” grade.

1. In all calculations in this question you may use only the four basic arithmetic operations. You are asked

to compute the number

a = \sqrt{5 − ^{3} \sqrt{2}} .

(a) Suggest an iterative method that computes a with as few iterations as possible.

(b) Estimate the number of iterations required to obtain a within an error not exceeding 10^{−6}, using the initial value a_{0} ≈ 1.9.

(c) How sensitive is your method to the choice of a_{0}?

2.

(a) Describe the composite Simpson’s rule for numerical integration. What is the relation between this rule and polynomial interpolation?

(b) Analyze the error of the (non-composite) Simpson’s rule.

(c) Derive a new integration rule by applying one step of Richardson’s extrapolation to Simpson’s rule.

3.

(a) Discuss a constructive approach for the proof of the following statement:

Every real square symmetric matrix A is orthogonally similar to a diagonal matrix.

(b) Does the statement remain true upon replacing “similar” by “congruent”?

(c) Find the condition number of

( \begin{matrix}1 & 0 & 0 \\ 0 & −1.2 & 2.4 \\ 0 & 2.4 & .2 \end{matrix} )

in the L_{2}-norm.

4. Let A = (a_{ij}) be a real N × N matrix which satisfies

a_{ii} ≥ ∑_{j≠i} |a_{ij}| + 2  (1)

and

5 ≤ a_{ii} ≤ 7  (2)

(a) Prove that A^{−1} exists.

(b) Find a numerical bound for ∥A^{−1}∥_{∞}.

(c) Assume A = A^{T}. Find numerical bounds on ∥A∥_{2} and ∥A^{−1}∥_{2}.

5. In this question Π_{n} denotes the space of all polynomials of degree ≤ n. Further, given a function f

defined on [−1, 1] we denote

dist(f, Π_{n}) = inf_{p∈Π_{n}} ∥f − p∥,

with

∥f − p∥ = sup_{x∈[−1,1]} |f(x) − p(x)|.

(a) Given f(x) = x^{n+1}, find p ∈ Π_{n} such that

∥f − p∥ = dist(f, Π_{n}).  (3)

Prove that your p indeed satisfies (3).

(b) For the same f, compute dist(f, Π_{n}).

(c) With f and p as above, discuss briefly the use of the error function f −p in polynomial interpolation.

6. Consider the Initial-Value Problem

y′ = f(y),  y(0) = y_{0}.  (4)

Consider the linear multistep method

Y_{n} + 2Y_{n−1} − 3Y_{n−2} = 2h [f(Y_{n−1}) + f(Y_{n−2})]  (5)

Discuss the consistency and stability of the method.

7. Consider a Predictor-Corrector Method for the numerical solution of

\begin{aligned}y′ & = f(y), 0 ≤ t ≤ T \\ y(0) & = 0. \end{aligned}

Predictor (explicit)

a_{0}Y_{n} = − ∑_{j=1}^{k} a_{j}Y_{n−j} + h ∑_{j=1}^{k} b_{j}f(Y_{n−j})  (6)

Corrector

α̃_{0}Y_{n} = − ∑_{j=1}^{L} α̃_{j}Y_{n−j} + h ∑_{j=0}^{L} β̃_{j}f(Y_{n−j})  (7)

Predictor-Corrector Method

\begin{aligned}Y_{n}^{∗} & = −\frac{1}{a_{0}} ∑_{j=1}^{k} a_{j}Y_{n−j} + h\frac{1}{a_{0}} ∑_{j=1}^{k} b_{j}f(Y_{n−j}) \\ Y_{n} & = \frac{1}{α̃_{0}} [− ∑_{j=1}^{L} α̃_{j}Y_{n−j} + hβ̃_{0}f(Y_{n}^{∗}) + h ∑_{j=1}^{L} β̃_{j}f(Y_{n−j})] \end{aligned}

(a) Consider the predictor equation and the corrector equation as separate Linear Multistep Methods to solve this problem. Define “order of consistency” of these methods.

(b) Consider the Predictor-Corrector Method. Suppose method (6) has order of consistency R. Suppose method (7) has order of consistency P. What is the order of consistency of the Predictor-Corrector Method?

(c) State a theorem giving necessary and sufficient conditions for the Predictor-Corrector Method to be “stable”. Sketch the proof.

8. Consider the finite difference scheme

v_{m}^{n+1} = e^{−2bμ}v_{m}^{n} + \frac{1 − e^{−2bμ}}{2} (v_{m+1}^{n} + v_{m−1}^{n})

as an approximation to the heat equation u_{t} = b u_{xx} with μ = Δt/(Δx)^{2}. Discuss the stability, consistency, and accuracy of the scheme for solving the initial value problem.

9. Consider the boundary value problem

−Δu = −\frac{∂^{2}u}{∂x^{2}} − \frac{∂^{2}u}{∂y^{2}} = −u^{3} + 1 in Ω

u = 0 on ∂Ω

where Ω is the unit square.

(a) Describe a finite-difference scheme to solve this problem. This scheme must produce a unique solution.

(b) Prove that your scheme has a unique solution.

10.

(a) Let λ be a nontrivial linear functional on some linear space X. Prove: For all x ∈ X and all y ∈ X\ ker λ, the modified element x − (λx/λy)y is in ker λ.

(b) Relate the abstract construction in (a) to Gauss elimination.

(c) Relate the abstract construction in (a) to Gram-Schmidt orthogonalization.

(d) Describe in some detail how Gauss elimination would look if it were carried out in the same order as Gram-Schmidt orthogonalization.