Sample questions

I

Finite-precision computation

1. Which is numerically superior: $\sin x - \sin y$ or $2\sin \frac{x-y}{2} \cos \frac{x+y}{2}$

2. What is a machine number? Is $10^6$ one? Is $1/10$. Is the sum of two machine numbers a machine number? Give a counterexample.

3. Can you give an example of a number that is not a machine number?

4. If $x$ and $y$ are machine numbers, what can you say about $x-y$ when $x \propto y$?

5. Why is cancellation good in this case? How can you use it to design a more accurate addition algorithm (tip: magic adding by Kahan)

6. Consider floating point numbers with base=2, precision=24. What is the largest $x$ such that ${\bf round}(x+1) = 1$?

7. In IBM PC Basic: $1.23457-1.23456=1.00313E-5$. Explain the origin of the error.

8. Give an example of an unstable algorithm.

II

Direct Methods for Dense Systems

1. Give a recursive definition of LU factorization. (If you can factor $A_{n-1 \times n-1}$ how can you factor $A_{n \times n}$ ? )

2. Prove Uniqueness for LU factorization.

3. For the problem $A x = b$, it is most useful to divide matrices into two broad classes: general matrices, and (fill in the blank).

4. Why do symmetric and symmetric positive definite matrices arise so often?

5. What is the reduced matrix after one step of Gaussian elimination applied to: $\left(\begin{array}{ll} \alpha & a^T \\ a & B \end{array}\right)$

   If the original matrix is SPD is the reduced matrix also SPD? Prove it.

6. Why do we introduce norms?

7. What are the three properties of a vector norm?

8. What is the definition of a subordinate matrix norm? In this definition how do we know a maximum is attained?

9. What matrix norm is subordinate to the vector max norm?

10. Fully explain the purpose of partial pivoting.

11. Why is partial pivoting not needed for a positive definite matrix?

12. What is the growth factor for Gaussian elimination applied to a SPD system?

III

Least Squares Problems

1. What is a projector? What is an orthogonal projector? What can be said about their eigenvalues?

2. Consider a subspace of $\mathbb{R}^n$ with basis $v_1, v_2, \cdots, v_m$. Explicitly construct the orthogonal projection for this subspace.

3. Given vectors $u$ and $v \neq 0$, determine an expression for the orthogonal projection of $u$ onto $v$.

4. Describe Gram-Schmidt geometrically.

5. Give a derivation of the normal equations guided by the analogous problem in three dimensional Euclidean space.

6. Give a geometric interpretation of a Householder reflection in 2D.

7. What is a Singular Value Decomposition?

IV

Eigenvalue Problems

1. For the eigenvalue problem $A x = \lambda e$, it is most useful to divide matrices into two broad classes: general matrices, and (fill in the blank).

2. For a shifted QR iteration one has
   

   $$A_{k+1} = Q_k^{\mathrm{T}}(A-\mu_kI)Q_k+\mu_kI$$

   $$= Q_k^{\mathrm{T}}AQ_k$$

   
   
   So, what difference does the shift make?

V

Approximation of functions

1. Let $I$ be the operator mapping $f$ onto the poly which interpolates $f$ at $x_0, x_1, \dots, x_n$. Prove that $I$ is a linear operator and a projection operator.

2. Let $p_k(x)$ interpolate $f$ at $x=x_0,x_1,\dots,x_k$. Give a simple expression for $p_n(x)-p_{n-1}(x)$ in terms of $f$ and $x_0, x_1, \dots, x_n$.

3. What is a divided difference? List some properties of divided differences.

4. Do a divided difference interpolation of $1/x$, $x=1,1,2$.

5. How might one use in practice the remainder term for polynomial interpolation? First, what is it?

6. In what sense is a Taylor polynomial an interpolation polynomial? Give examples of interpolation in root finding, quadrature, and ODE methods.

7. Give an abstract definition of best approximation.

8. Does Chebyshev interpolation give best uniform approximation?

VI

Initial Value Problems in ODEs

1. Suppose that $X_1(t)$ and $X_2(t)$ are both solutions of the single ODE $X'(t)=f(t,X(t))$. Is it possible for the graphs $x=X_1(t)$ and $x=X_2(t)$ to cross?
2. Draw a picture of the convergence proof for Euler's method.
3. What is a reasonable way of controlling the stepsize in Euler's method?
4. Consider the following initial value problem:

   $$U'(t) = -U(t)V''(t), \quad U(1) = 1,$$

   $$V'''(t) + [U(t) - V(t)]^2 = 1/t, \quad V(1)=0, V'(1)=1, V''(1)=0.$$

   
   
   Express this in a form suitable for a typical ODE integrator.

5. Given ODE $y'=ty$ what is one step of backward Euler?

6. Given a formula for a 2-stage 2nd order RK method, draw a picture of it.

7. What is a systematic way of generating formulas of arbitrarily high order for $y'=f(t,y)$?.
8. Show graphically the relationship between global and local errors for an ODE IVP method.
9. Do a stability analysis for Euler for the standard test equation.
10. What is a stiff ODE? What is a good method for stiff ODEs? What is its drawbacks? Can you name another method not having this drawback? How does one solve the implicit equations in practice?

11. What information do we get from analyzing $y'=\lambda y$?
12. How can one experimentally determine the order of accuracy of a discretization method?

VII

Boundary Value Problems for a Second Order ODE

1. Give an example of a 2 point BVP for $y''=f(x,y)$.
2. Consider $y''=f(x,y,y')$ with 2 separated boundary conditions.
   • What would boundary conditions look like?
   • Give a second order accurate discretization of this problem?
   • How would you generalize to a non-uniform mesh?
   • How would you solve discrete problem?
   • How much memory could you need for Gauss elimination with pivoting?
3. Consider Blasius equation: $y''' + 2yy'' = 0$, $y(0)=y'(0)=0$, $y'(\infty)=1$. How might one solve it numerically?

VIII

Solutions of Nonlinear Equations

1. What can you say about the convergence of Newton's method?
2. Give the Newton method in one dimension. What is its order of convergence? Does this order always hold?
3. Give the Newton method in multi-dimensions. How can we ensure convergence? Why does this work? What will this converge to?

IX

Elliptic PDEs

1. Draw the shape, or give the nodal basis functions, for quadratic Finite Elements.
2. Express stiffness matrix in terms of element matrix.
3. What is the computational complexity of Multi-Grid fast Poisson solver. Is it fair to compare? cost of reducing error to $\epsilon$, cost of 53 bits versus 24 bits.
4. What are the computational complexities of the stationary iterative methods applied to the 1-D, 2-D, and 3-D Laplacians?
5. Give an operation count for banded Gaussian elimination of an $n \times n$ matrix with half-bandwidth $m$.
6. How much fill-in for a linear system with structure:
   $$\left( \begin{array}{lllll} x & x & x & \cdots & x \\ x & ... ...s & \vdots \\ x & 0 & 0 & \cdots & x \\ \end{array}\right)$$

7. How do we avoid this fill-in.

8. Give an operation count for banded Gaussian elimination without pivoting.

X

Parabolic PDEs

1. Solve heat equation with initial values ${1\over n}\sin nx$
2. For $u_t=au_{xx}$, give additional conditions that would determine a unique solution.
3. If we use forward-time centered-space differencing for $u_t=u_{xx}$, will it converge as $\Delta t$, $\Delta x\rightarrow 0$?
4. Write down the forward-time centered-space difference scheme for the heat equation and do a stability analysis.
5. Write down the Crank-Nicolson difference scheme for the heat equation and do a stability analysis.

XI

Hyperbolic PDEs

1. Given $u_t=cu_x$ and $u(x,0)$ equal to a hat function, describe the graph solution $u(x,t)$.
2. Write down the centered-time centered-space difference scheme for the wave equation and do a stability analysis.