Numerical Analysis Fall, 1988

Instructions

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 chosen from problems 6–10. The answers to three of the questions must be handed in after two (2) hours.

1. Consider the function f defined by

f(x) := x^{α} + x^{α+2}

for x ∈ [0, ∞); here 0 < α < 1.

(a) Show that for each y ∈ [0, ∞) there is a unique x such that y = f(x).

(b) Describe an algorithm, based on the secant method, to obtain x for any prescribed value y. This method requires two initial iterates for x; be sure to explain how these iterates are chosen. Hint: The choice of initial iterates depends on y.

(c) Prove that this method converges for all y. Hint: Exploit the local convexity or concavity of f.

(d) Suggest a way to minimize the number of iterations required by carefully choosing the initial approximations. This is important especially when y is nearly zero or y is large.

2. Consider the two schemes

y_{n+1} = y_{n−1} + 2hf(x_{n}, y_{n})  (I)

and

y_{n+1} = y_{n} + \frac{h}{2} [f(x_{n}, y_{n}) + f(x_{n+1}, y_{n+1})]  (II)

for approximating the solution of an initial-value problem y′(x) = f(x, y(x)) with y(x_{0}) = y_{0}.

(a) Show that the local discretization errors for schemes (I) and (II) are \frac{1}{3}h^{3}y′′′(ξ) and −\frac{1}{12}h^{3}y′′′(ξ), respectively.

(b) Describe the algorithm for a predictor-corrector method based on schemes (I) and (II).

(c) Use the results of (a) to calculate an extra correction that improves the method of part (b). How else can the estimates of (a) be used in the algorithm?

(d) In place of scheme (I) one might use the forward Euler scheme. Why is part (c) impossible to carry through if Euler’s scheme were used?

(e) What possible disadvantage is there in using (I) for an initial-value problem?

3. Consider the linear system

Ax = b ,

where A is a singular n×n matrix; suppose that this equation has a solution x = x_{∗}. Given a nonsingular matrix M, write A = M − N and consider the iteration scheme

Mx^{(k+1)} = Nx^{(k)} + b , k = 0, 1,…,

with x^{(0)} = 0.

Give necessary and sufficient conditions on K = M^{−1}N in order that x^{(k)} → x_{∗} as k → ∞.

4. For the initial-value problem

\begin{aligned}y′ & = f(y) \\ y(0) & = y_{0} \end{aligned}

consider the predictor-corrector method

Y_{n+r}^{∗} = ∑_{j=0}^{r−1} a_{j}Y_{n+j} + h ∑_{j=0}^{r−1} b_{j}f(Y_{n+j})  (I)

Y_{n+r} = ∑_{j=0}^{r−1} α_{j}Y_{n+j} + h ∑_{j=0}^{r−1} β_{j}f(Y_{n+j}) + hβ_{r}f(Y_{n+r}^{∗})  (II)

with β_{r} ≠ 0. Assume: (i) that the implicit multistep scheme

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

is stable and accurate of order q ≥ 1; and (ii) that the explicit multistep scheme

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

is unstable and accurate of order q − 1.

Is the predictor-corrector method convergent and accurate of order q? Supply a proof of your answer.

5. Consider the following problem in numerical differentiation: You are given the value of a bivariate function f at three distinct points a, b, and c in the plane. ¿From this information, you want to approximate, in some reasonable way, the value at 0 of the partial derivative D_{1}f (i.e., the partial derivative of f with respect to its first argument).

(a) Propose (and defend) a particular way of solving this problem.

(b) Give an estimate, in powers of h, of the error in your approximation when f is smooth and a, b, and c lie within a distance h from 0.

(c) Could you improve the estimate in part (b) by choosing a, b, and c carefully? If so, how? What is the highest power of h that you can hope for?

6. Let X denote the Banach space C[0, 1] equipped with the uniform norm ∥ · ∥_{∞}.

(a) Describe Nystrom’s method for solving the integral equation

f − ∫_{0}^{1} k(·, t)f(t)dt = g

of the second kind for f ∈ X. Here g ∈ X and the kernel k is continuous, so that the linear map K : X → X defined by

f ↦ ∫_{0}^{1} k(·, t)f(t)dt

is continuous.

(b) Let K_{n} denote the approximation to K provided by Nystrom’s method with n quadrature points, and assume that the method converges as n → ∞. Prove or disprove: lim_{n→∞} ∥K − K_{n}∥ = 0.

7. Let (x_{n}, y_{n}), n = 1,…, N, be a given set of data points. Suppose that these data are to approximated, in the sense of least squares, by a function that is linear combination of the basis functions ϕ_{k}, k = 1,…, K, where K ≤ N.

(a) Construct a matrix A and a vector b such that the least squares problem reduces to the following minimization problem:

find x for which ∥Ax − b∥_{2} is minimized.  (∗)

(b) Show that the problem (∗) always has a solution.

(c) Under what conditions does the minimization problem (∗) have a unique solution?

(d) Suppose that these conditions for uniqueness are not met. Suggest a method for choosing an “optimal” solution.

8. The elliptic partial differential equation

\frac{∂^{2}u}{∂x^{2}} + \frac{∂^{2}u}{∂y^{2}} = −1 + u^{2}

on the unit square (0 ≤ x, y ≤ 1), with boundary conditions u = 0, has the finite difference approximation

\frac{1}{h^{2}} [U_{i+1,j} + U_{i−1,j} + U_{i,j+1} + U_{i,j−1} − 4U_{i,j}] = −1 + (U_{i,j})^{2} .

Here i, j = 1,…, N, h = Δx = Δy = 1/(N + 1), and, by convention, U_{i,j} := 0 when i or j is either 0 or N + 1 (i.e., on the boundary).

(a) Show that if we consider only solutions such that U_{i,j} ≥ 0 for all i, j, then there exists a unique solution and it satisfies 0 ≤ U_{i,j} < 1.

(b) Show that the following iterative method converges to the solution of part (a):

U_{i,j}^{n+1} + \frac{h^{2}}{4} (U_{i,j}^{n+1})^{2} = \frac{h^{2}}{4} + \frac{1}{4} [U_{i+1,j}^{n} + U_{i−1,j}^{n} + U_{i,j+1}^{n} + U_{i,j−1}^{n}]

for i, j = 1,…, N, where U_{i,j}^{0} = 0. Hint: Use the fact that the function g defined by g(x) = x + h^{2}x^{2}/4 increases monotonically for x ≥ 0.

9. Give a finite-difference scheme for solving the partial differential equation

u_{t} = u_{xxx} for x ∈ R , t ≥ 0 .

The scheme must be stable and (at least) first-order accurate in time and secondorder accurate in space. Justify your choice.

10. Consider the linear system

Ax = b ,  (∗)

where A is an m × n matrix. Recall that a matrix B_{L} is a left inverse for A in case B_{L}A = I_{n}, and similarly that B_{R} is a right inverse for A if AB_{R} = I_{m}.

(a) Show that if A has a right inverse, then system (∗) has at least one solution (although it may have more). Show that if A has a left inverse, then system (∗) has at most one solution (although it may have none).

(b) Define what one might mean by saying that A is “nonsingular.” Prove that if A is nonsingular, then it has right and left inverses, and that all its right and left inverses coincide.

(c) Assume that A is nonsingular, and let C be an approximation to A^{−1}. Why is it possible for C to be a “good” left inverse for A but a “bad” right inverse, and vice versa. (Your answer should specify what “good” and “bad” mean here.)

(d) Assume that A is nonsingular, and let C be the approximation to A^{−1} computed by Gaussian elimination (in finite-precision arithmentic). Is C a “good” left inverse or a “good” right inverse? If you decide that it is one rather than the other, how would you compute the other kind well?