CSE 401/CS 450/MATH 450/ECE 491: Sample Questions, Fall 2006

Chapter 1:

1. What does it mean for an algorithm to be stable?
2. What does it mean for a problem to be well conditioned?
3. What does it mean for a problem to be well posed?
4. Are well posed problems always well conditioned?
5. Are well conditioned problems always well posed?
6. If you apply a stable algorithm to a well conditioned problem will you get a relatively accurate solution?
7. What is the absolute forward error? backward error?
8. What is the relative forward error? backward error?
9. What is the relative backward error of approximating cos(x) with 1 + 0.5*x² at x = π/8 ?
10. What is the difference between data error and computational error?
11. What is the difference between truncation error and rounding error?
12. What is the condition number of a problem?
13. How does conditioning relate to forward and backward error?
14. What is machine precision? Underflow? Overflow?
15. When does 1 + a = 1 in floating point? Does this mean a = 0 in floating point?
16. What limits the accuracy of addition, subtraction, multiplication, division of machine numbers?
17. Which operations can result in overflow? underflow?
18. What is cancellation?
19. Which is most accurate: 1/x - 1/(x+1) or 1/(x(x+1)) ? When x =~ 0 or x =~ -1 ? How about for |x| larger than 1 / eps_mach ?

Chapter 2

1. When does A x = b have a solution? a unique solution?
2. What does it mean for a matrix A to be singular?
3. If A x != 0 for all x != 0?
4. If A has rank n, and A is n by n?
5. There exists B such that A B = B A?
6. There exists B such that A B = B A = I ?
7. What is the 1-norm, 2-norm, infinity-norm of a vector?
8. What is the norm of a matrix in the 1-norm, 2-norm, infinity-norm?
9. What is the condition number of a matrix?
10. What is the norm and condition number of a diagonal matrix?
11. When does cond(AB) = cond(B)? When A is a scalar? Matrix?
12. How does cond(A) relate to cond(A^-1)?
13. How sensitive is the solution to A x = b to changes in A and b?
14. Does a relatively small residual indicate a relatively accurate solution?
15. What is the complexity of computing the LU factorization of A?
16. What is the complexity of forward and back substitution?
17. Does the LU factorization always exist? with row-pivoting? with row and column pivoting?
18. How do we decide when to pivot for partial (row) pivoting? full (row and column) pivoting?
19. Which is more expensive: (1) Computing the LU factorization (with pivoting) of A and solving with forward and back substitution or (2) Computing the inverse of A and multiplying times b?
20. What is the advantage of solving symmetric systems? symmetric positive definite systems?
21. What is the Cholesky factorization? When can it be computed?
22. What is the complexity of computing the LU factorization for a banded system if no pivoting is required?

Chapter 3

1. When does a linear system of equations have a least-squares solution?
2. When is the least-squares solution unique?
3. Suppose a matrix A has more rows than columns, does A x = b have a least-squares solution? Is it unique? If A has more columns than rows?
4. How does the rank of A relate to the existence and uniqueness of a least-squares solution?
5. What happens when b is in the span of the columns of A?
6. How does the conditioning of the least squares problem relate to A and the angle between b and the span of the columns of A?
7. What are the normal equations?
8. What do the normal equations tell us about the least-squares residual and the columns of A?
9. What is the pseudo-inverse of a matrix? If A is full rank? If A is not full rank?
10. How does the conditioning of the normal equations relate to the condition number of A?
11. What is the QR factorization of a matrix?
12. Why don't we use the LU factorization for solving the least-squares problem?
13. What does it mean for a matrix to be orthogonal?
14. What is a Householder reflection? How is it used to compute the QR factorization?
15. What is a Givens rotation? How is it used to compute the QR factorization?
16. How many Householder reflections (or Givens rotations) are required to reduce a matrix to upper triangular?
17. What is the singular value decomposition of a matrix?
18. Which method is most expensive, normal equations, householder, SVD?
19. Which method is most accurate, normal equations, householder, SVD?
20. What is the 2-norm and 2-norm condition number of a matrix?
21. Given several data points, what is the least-squares fit of a polynomial of the form p(t) = x1 t + x2 t²?
22. What is the first column of a matrix after the first Householder reflection?
23. What is the (1,1) entry of a matrix after the first Givens rotation?

Chapter 4

1. What is an eigenvalue (eigenvector) of a square matrix?
2. What is the characteristic polynomial?
3. For every polynomial, p, is there a matrix with p as its characteristic polynomial?
4. What is the conditioning of the eigenvalue problem?
5. What matrices always have well conditioned eigenvalues?
6. What does it mean for a matrix to be normal?
7. What does it mean for a matrix to be defective?
8. Can a normal matrix be defective? Can a defective matrix be normal?
9. Can a matrix be both non-normal and non-defective?
10. Are symmetric matrices always normal? Always non-defective?
11. What is a similarity transformation?
12. What is a unitary matrix? Similarity transformation by a unitary matrix?
13. For real matrices, how close can we get to diagonal using orthogonal similarity transformations?
14. What about with unitary similarity transformations? And with a general similarity transformation?
15. What is the real schur form of a matrix?
16. What is the general schur form of a matrix?
17. What is the power method? Inverse iteration?
18. To which eigenvector does the power method converge?
19. To which eigenvector does the inverse iteration converge?
20. Perform one step of the normalized power iteration with a small matrix.
21. Why do we normalize the power iteration with the infinity-norm?
22. Perform one step of the normalized inverse iteration with a small matrix.
23. What is the Rayleigh quotient? Compute the Rayleigh quotient for a small matrix and approximate eigenvector
24. Why do we use shifts with power and inverse iterations?
25. What is the Rayleigh quotient iteration?
26. What is the purpose of preliminary reduction to Hessenberg or Tridiagonal form?
27. Why can't we just reduce to diagonal or upper triangular directly?
28. What does Lanczos and Arnoldi produce?
29. What is the QR iteration? To what form does the QR iteration converge?

Chapter 5

1. When does a function, f(x), have a root?
2. When is the root of a function well-conditioned?
3. How does the absolute conditioning of evaluating, f(x), at a root relate to the conditioning of that root?
4. What is a multiple root of a function?
5. What is the derivative (at a root) of a function with a multiple root?
6. What is a fixed point iteration?
7. What is the convergence rate of a fixed-point iteration?
8. What is linear, superlinear, and quadratic convergence rates?
9. How does the number of correct digits in the solution increase with a linear convergence rate? quadratic convergence rate?
10. What is the bisection method? Does it always converge? What is its rate of convergence?
11. Given a fixed point method, x_n+1 = x_n - 0.5 (x_n)² + 0.5, will it converge to x = 1 if the initial guess is sufficiently close? How about for x = -1 ?
12. What if g'(x) is zero at the fixed point? What about if g'(x) < -1 ?
13. What is Newton's method? What is the rate of convergence for Newton's method?
14. What happens when Newton's method is applied to a function with a multiple root?
15. What is the secant method? What is the advantage of secant method over Newton's method? Disadvantages?
16. What is general idea of Broyden's method? What is the advantage of Broyden's method over Newton? Disadvantage?
17. Perform one step of Newton's method for a small system of equations.
18. What is a trust region?
19. What is damped Newton?

Chapter 6

1. What is a local minimum of a function? global minimum?
2. Is the derivative always zero at a local minimum? Is the second derivative always positive?
3. If the second derivative is positive and the first derivative is zero, is it always a local minimum?
4. If the second derivative is negative what can we say? What about if the second derivative is zero?
5. How does the first and second derivative test work in higher dimensions?
6. What does it mean for a function to be coercive? How about convex?
7. What does it mean for a set to be convex? What do we know about convex functions on convex sets?
8. What is the first derivative test for a constrained system?
9. What is the conditioning of the local minimization problem? How does this relate to the conditioning of the root finding problem for f'(x) = 0 ?
10. What is the steepest descent method?
11. What is the general idea behind the conjugate gradient method?
12. Which methods use a one-dimensional line search?
13. What is Newton's method for the minimization problem?
14. Does Newton's method only converge to local minima in this context?
15. What is general idea of the BFGS method? How is BFGS related to Broyden's method?
16. For what is Gauss-Newton used?
17. Which methods explicitly require solving a linear system of equations at each step?
18. What is the penalty method? How does it work?
19. What is the purpose of a trust-region in an optimization algorithm?

Chapter 7

1. How many points can we interpolate with an nth degree polynomial?
2. What is the difference between interpolation and least-squares? When do we use one versus the other?
3. What is the advantage of using the Monomial vs. Newton vs. Lagrange basis?
4. What is the disadvantage of using each of these basis representations?
5. Do all three of these basis representations generate the same polynomial?
6. What does it mean for a basis representation to allow for the interpolating polynomial to be built incrementally? Which representation allows for incremental construction?
7. What is the problem with using equally spaced points for polynomial interpolation?
8. What are the Chebyshev points?
9. What is Hermite interpolation? Spline interpolation?
10. Which is smoother, Hermite or Spline?
11. How many free parameters does a cubic spline have?
12. What can we enforce with these free parameters?
13. What is a natural cubic spline? periodic cubic spline?

Chapter 8

1. What is the conditioning of integration? How about differentiation?
2. Is it a good idea to integrate noisy data? How about differentiate?
3. What does it mean for a set of quadrature rules to be progressive?
4. Which classes of quadrature rules have progressive subsets?
5. What is Newton-Cotes quadrature? How are the nodes and weights determined?
6. What is Gauss quadrature? How are the nodes and weights determined?
7. What does it mean for a quadrature rule to be open? How about closed?
8. Which quadrature rules are open? Which are closed?
9. What is an advantage of using an open rule?
10. What is a composite quadrature rule?
11. Apply the composite midpoint (or trapezoid) rule to some tabulated data (or to a given function.
12. What is the degree of a quadrature rule?
13. What is the degree of an n-point Newton-Cotes rule? How about a Gauss rule?
14. What is the forward difference approximation to the first-derivative? How about backward difference? And centered difference?
15. What is the centered difference approximation to the second-derivative?
16. Apply the forward/backward/centered difference formula to tabulated data (or to a given function).
17. What is Richardson extrapolation? Why is it useful?
18. Apply Richardson extrapolation to some function of order h^p with given results for two different values of h.

Chapter 9

1. What does it mean for a system of initial value problem (IVP) ordinary differential equations (ODEs) to have stable solutions?
2. Consider the coupled system du/dt = c w and dw/dt = u, where c is a constant. For what values of c is this system stable?
3. Consider the coupled system du/dt = a u + b w and dw/dt = c w, where a, b, and c are constants. For what values of a,b,c is this system stable?
4. Given a linear system of ODEs, dx/dt = A x, where A is a matrix and x(t) is a vector for each value of t. When is this stable?
5. Consider the linear system of ODEs above, what is the condition for forward Euler to be stable? How about backward Euler?
6. Apply one step (or two steps) of forward or backward Euler to any of the ODEs given above.
7. What is the trapezoid rule? When is the trapezoid rule stable for linear systems?
8. Given a higher-order ODE, how do you convert it into first-order form and find the stability?
9. What is the difference between stable and asymptotically stable?
10. How do we determine stability for nonlinear systems?
11. What is a Runge-Kutta method? What is a multistep method?
12. What is the advantage of using an implicit method? Cost per step? Stability? Accuracy?
13. What is a stiff differential equation?

Chapter 10

1. What is a boundary value problem?
2. How is the conditioning of the boundary value problem (BVP) related to growing and decaying modes?
3. Describe the steps involved in applying a shooting method. What is the dimension of the system of equations that must be solved?
4. Describe the steps involved in applying a finite difference method. What is the dimension of the system of equations that must be solved?
5. Describe the steps involved in applying a collocation method. What is the dimension of the system of equations that must be solved?
6. What does it mean for a BVP to be linear? Have separated boundary conditions?
7. Approximate the solution to a BVP using a three-point finite difference approximation (i.e., one interior point).
8. Approximate the solution to a BVP using collocation with a quadratic polynomial (i.e., three unknown coefficients).

Chapter 11

1. What is the advection equation? What is the solution to the advection equation?
2. What is the heat equation? Is the heat equation parabolic, elliptic, or hyperbolic?
3. What is the wave equation? Is the wave equation parabolic, elliptic, or hyperbolic?
4. What is the laplace equation? Is the laplace equation parabolic, elliptic, or hyperbolic?
5. What class of PDEs have solutions which are evolving toward a steady state solution: parabolic, elliptic, or hyperbolic?
6. What class of PDEs have solutions which are not evolving toward any steady state: parabolic, elliptic, or hyperbolic?
7. What class of PDEs has as its solution the steady state solution: parabolic, elliptic, or hyperbolic?
8. What are characteristics of a PDE? What are the characteristics for the advection equation?
9. How do characteristics help to determine if boundary conditions are properly specified?
10. How does semi-discretization work in the method of lines?
11. Approximate the solution to a simple 2D PDE using centered differences and only one unknown interior point.
12. Compute the solution to an advection equation at some point in time and space given the initial conditions.