Study guide for the final exam

Here is a non-exhaustive list of questions you should be able to answer as you prepare for the final exam. The exam will cover everything taught in class but the focus will be on the fundamentals of the topics.

This guide is a complement to the previous 2 study guides and it only covers topics from chapters 8 through 12. Refer to those for the missing material.

Numerical Integration and Quadrature

  • What are quadrature rules based on? What are the possible degrees of freedom?

  • Newton-Cotes Quadrature:

    • What is the degree of a quadrature rule?

    • What degree is Midpoint rule, Trapezoid rule, Simpson's rule?

    • How roughly is error related to degree and grid spacing?

    • What is the accuracy of Newton-Cotes quadrature?

    • What are the drawbacks of Newton-Cotes quadrature?

    • How does Clenshaw-Curtis quadrature solve some of these issues?

  • Gaussian Quadrature:

    • What is the main difference between Newton-Cotes and Gaussian Quadrature?

    • What is the accuracy of Gaussian quadrature?

    • How do we do error estimation for Gaussian quadrature? How do Kronrod rules help?

  • Composite quadrature?

    • What advantages are provided by composite qudature rules?

    • What accuracy is attained with composite quadrature rules?

  • Differentiation

    • What are forward, backward and central differencing?

    • What is the general accuracy of these schemes?

    • How does the accuract of differentiation compare to interpolation? to integration?

  • Extraploation

    • How does Richardson's extrapolation improve accuracy?

    • What is Romberg integration?

Initial Value Problems

  • What is the order of an ordinary differential equation (ODE)? How can you turn higher order problems into first order problems?

  • What is an initial value problem (IVP)?

  • What is/are the condition(s) for uniqueness for first order ODEs?

  • Understand the concept of stability of solutions for an ODE in 1D and in multiple dimensions

  • Understand the errors associated with solving ODEs numerically:

    • What is Local error?

    • What is global error?

    • What is truncation error?

    • How are they related?

  • Understand how numerical stability related to analytical stability:

    • What is a growth factor? How does it relate to local/global error?

  • Understand the different methods to solve ODEs

  • What is the difference between explicit vs implicit schemes? What are some examples?

  • What is a single-step scheme, what is a multi-step scheme? What is a multi-stage scheme? What are some examples?

  • How accurate are these methods?

  • What are their stability properties?

  • What is a stiff ODE? What methods are effective for this type of ODEs?

Boundary Value Problems

  • How are boundary value problems problems (BVPs) different from IVP problems?

  • How can you use methods for IVP problems to solve BVP problem?

  • Take a simple BVP and transform it into a linear system of equations using finite differences, then solve the problem

  • Derive a first and second order finite difference for the first derivative. Explain the order of convergence for each case.

  • When using the collocation method, what is satisfied exactly?

  • How does the collocation method relate to a Galerkin method?

  • Take a simple BVP for which you know the solution and solve it using the Galerkin method

  • What is the stiffness matrix? Compute the stifness matrix and the second order finite difference matrix for a set of equispaced points and analyze their sparsity patterns and entries?

  • How do you solve an eigenvalue BVP problem?

  • What does it mean to have local support?

  • What is a weighted residual method? Give some examples

Partial Differential Equations

  • How is a partial differential equation (PDE) different from a BVP or and IVP?

  • What are the three main families of PDEs? Give an example for each

  • How do you determine the order of a PDE?

  • What are characteristics of a PDE?

  • What types of PDEs are suitable for semidescrete methods (reduction to ODE IVPs)?

  • How are time-independent PDEs discretized and solved?

  • How does stability determine the permissible ratio of time-step size and spatial discretization width?

  • What is the CFL condition? What is the domain of dependence? To what class PDEs is the CFL condition usually applicable?

  • When factorizing a sparse matrix, do you expect the same level of fill regardless of the ordering of the rows and columns?

  • How does a linear system change when the unknowns (graph vertices) are permuted?

  • What are the main algorithmic differences and relative convergence rates of Jacobi/Gauss-Seidel/SOR?

  • What is the conjugate gradient method? What are you trying to minimize in the context of linear systems?

  • Explain the advantages and disadvantages of direct methods vs iterative methods

  • What is the computational complexity of multigrid for solving the Poisson equation?

  • What is restriction and interpolation? What type of error is resolved on fine grids? coarse grids?

Fast Fourier Transform

  • What is the purpose of the DFT?

  • What is the time domain? What is the frequency domain? How can I move between them?

  • How do you compute the DFT? What is the FFT? What is its complexity?

  • How is the DFT useful for solving linear systems arising from discretizations of PDEs?