Final Exam Study Guide/Practice Aid

Content

The final exam is cumulative and covers all content from the course, with an even distribution across the whole course. The exam covers everything up to and including the BVP chapter. (Specifically, the lectures on large linear systems and PDEs are not included.)

Prior Material (Summary)

For detailed coverage, refer to past study guides:

Key highlights:

Linear Algebra & Eigenvalues

  • LU/Cholesky: Solving $Ax=b$, pivoting, costs.
  • SVD: $A=U\Sigma V^T$, low-rank approximation, condition number.
  • QR: Householder/Givens, solving least squares.
  • Eigenvalues: Power iteration (converges to dominant $\lambda$), QR algorithm (converges to Schur form), Arnoldi/Lanczos (Krylov).
  • Sensitivity: Bauer-Fike theorem ($|\mu - \lambda| \le \text{cond}(X) \|E\|$).

Nonlinear Equations & Optimization

  • Convergence Rates: Linear ($e_{k+1} \approx C e_k$), Quadratic ($e_{k+1} \approx C e_k^2$).
  • Newton's Method: $x_{k+1} = x_k - J^{-1}f(x_k)$.
  • Optimization: $\nabla f = 0$, $H_f$ positive definite.
  • Steepest Descent: Direction $-\nabla f$, slow for ill-conditioned Hessians.
  • Newton for Opt: $x_{k+1} = x_k - H_f^{-1}\nabla f$.
  • Constrained Opt: Lagrangian $\mathcal{L}$, KKT conditions (Stationarity, Primal/Dual feasibility, Complementary Slackness).

Interpolation & Quadrature

  • Vandermonde: $V\alpha = y$. Ill-conditioned for monomials.
  • Chebyshev: Nodes clustered at boundaries to minimize Runge phenomenon.
  • Quadrature Weights: Sum of weights = interval length; $\sum w_i f(x_i)$.
  • Gaussian Quadrature: $n$ points integrate degree $2n-1$ exactly.
  • Diff Matrices: $f' \approx D f$; $D = V' V^{-1}$.

New Material

The following topics are new since the last exam:

  • Finite differences via Taylor
  • Richardson extrapolation
  • Initial value problems: setup
  • Initial value problems: Well-posedness
  • Euler's method
  • Initial value problems methods: accuracy and stability
  • Initial value problems: Stiffness
  • Runge-Kutta methods

Some questions to ask yourself (on the new material)

Finite Differences and Richardson Extrapolation

  • How can I derive a finite difference rule (e.g., forward or centered) using Taylor series expansions?
  • What is the truncation error order of a given finite difference formula?
  • What is Richardson extrapolation? If I have an estimate $F(h)$ with error $O(h^p)$, how can I combine $F(h)$ and $F(h/2)$ to get an $O(h^{p+1})$ (or higher) estimate?
  • Can I apply Richardson extrapolation to numerical differentiation or integration?

IVPs: Setup and Well-posedness

  • How do I convert a $k$-th order scalar ODE into a system of first-order ODEs?
  • What is the general form of an IVP: $\boldsymbol{y}'(t) = \boldsymbol{f}(t, \boldsymbol{y})$, $\boldsymbol{y}(t_0) = \boldsymbol{y}_0$?
  • What does it mean for $\boldsymbol{f}$ to be Lipschitz continuous in $\boldsymbol{y}$?
  • How does the Lipschitz constant $L$ relate to the existence and uniqueness of solutions (Picard-Lindelöf)?
  • What is the difference between the stability of the ODE itself (conditioning) and the stability of a numerical method?

IVPs: Euler's Method, Accuracy, and Stability

  • Write out the update steps for Forward Euler (explicit) and Backward Euler (implicit).
  • What is the difference between local truncation error (LTE) and global error? How do their orders typically relate?
  • For a method to be "stable," what must happen to the amplification factor when applied to the test equation $y' = \lambda y$?
  • What is the stability region of Forward Euler? Why is it restrictive for large negative $\text{Re}(\lambda)$?
  • What is the stability region of Backward Euler? What does it mean for a method to be $A$-stable?

IVPs: Stiffness and Runge-Kutta

  • What is a "stiff" ODE? Why do explicit methods perform poorly on stiff problems?
  • How do implicit methods (like Backward Euler) handle stiffness?
  • What is a stability function? How does it relate to stability region? How do I find either of those?
  • What is a Runge-Kutta method? What are the "stages"?
  • Can I interpret a Butcher table (tableau)? $$ \begin{array}{c|c} c & A \\ \hline & b^T \end{array} $$
  • When is a Runge-Kutta method explicit? (When $A$ is strictly lower triangular.)
  • What are the advantages of RK methods over simple Euler steps?