Study guide for Exam 1

Here is a non-exhaustive list of questions you should be able to answer as you prepare for the first midterm. The exam will cover chapters 1-2. Note that, as in lecture, this includes the singular value decomposition (SVD), which appears in Chapter 3 (Section 3.6) of Heath. The midterm will be 50 minutes in length and will consist of questions similar to the multiple-choice and short-entry questions on the quizzes. You will have access to a RELATE code submission box with numpy/scipy functions available, for use as a calculator.

Scientific Computing

What are posedness and conditioning of problems?
What are absolute and relative errors?
What are forward and backward errors?
What are the categories of sources of error in numerical methods?
How can a Taylor series expansion be used to quantify truncation error? What does it mean for an error to be $O(h^k)$ as $h \to 0$?
What is the difference between the conditioning of a problem and the stability of an algorithm? What does it mean for an algorithm to be accurate? to be (backward) stable?
What does it mean for a result to have $n$ accurate digits?
How does the number of accurate digits relate to rounding?
What is the relative and absolute condition number of evaluating a function for a given input? over a domain of inputs?
What are the main components of floating point numbers?
What is the typical relative accuracy in a floating point representation of a real number?
What are normalized floating point numbers?
How are floating point numbers spaced along the real number line? How does this spacing relate to machine epsilon and to the roundoff error in representing a given number?
Why are subnormal numbers used?
What are the exceptional floating point values, and which operations produce them? What happens when a computation overflows or underflows?
What is catastrophic cancellation and when does it occur? What is the conditioning of adding versus multiplying two numbers? How can reformulating an expression sometimes avoid cancellation?
How many digits can be lost during addition and multiplication of floating point numbers?

Linear Systems

What is a vector norm? a normalized vector? a unit ball?
What defines a matrix norm? what are induced matrix norms? what is the Frobenius norm?
What is the matrix condition number?
What is the conditioning of solving a linear system? of matrix-vector multiplication?
How are the propagated data error, forward error, and backward error related? in terms of conditioning?
What is the residual of an approximate solution to a linear system? How is it related to the backward error, and what does a small residual imply about the forward error for well-conditioned and ill-conditioned matrices?
How does one solve a diagonal, orthogonal, or triangular linear system? What is the cost of each? What is the determinant of a triangular matrix?
What is LU factorization, when does it exist and when is it unique?
What is the Schur complement, and what role does it play in Gaussian elimination?
Why is pivoting necessary and what type of pivoting strategies are possible? How does pivoting affect the round-off error incurred in LU factorization, and for what classes of matrices can pivoting be safely omitted?
What is the cost of Gaussian elimination?
How can Gaussian elimination be done with elementary elimination and permutation matrices?
How do you solve a linear system given a pivoted LU factorization? What is the cost of reusing a stored factorization to solve additional systems, e.g. with multiple right-hand sides?
What is the SVD of a matrix? What are the properties of the 3 matrices obtained from SVD of a matrix?
How does one express the norm, condition number, and minimizing/maximizing vectors for these quantities, in terms of the SVD?
When does a linear system have a unique solution? How can the SVD be used to detect that a matrix is singular or nearly singular, and to solve a linear system?
What matrix properties permit LU-type factorization without pivoting?