405/607E Exam Review
====================

(You *are* responsible for the material up from the first midterm.)

Interpolation
  - cardinal poly
  - existence/uniqueness
  - error formulae

Quadrature
  - idea of interpolant as "proxy"
  - Trapezoidal Rule and Simpson's Rule.
  - error formulae
  - composite methods
  - adaptive methods

The forward and backward Euler methods

Local truncation error vs one-step error

Stability
  - various types...
  - stability for the BVP problem (example in class)
  - absolute stability analysis based on Dahlquist test equation
  - difference between the exact soln of this problem and the definition of
    abs. stab: a property of the *method*
  - growth factor
  - stability regions
  - A-stability
  - L-stability

consistency + stability => convergence

How to find a finite difference method using Taylor series.

Understanding convergence studies ($O(h^p)$: h/2, error down by?)

some idea about stiffness: we had various definitions
  - *stiff problem*, not just DE

MOL: what is it?

stencil diagram showing finite difference schemes and dependency on points

how absolute stability analysis leads to restrictions on the time-step and
space-step,   i.e., k <= dx^2/4

IMEX idea

leap-frog scheme

upwinding for advection

some rough idea about how to apply finite differences in 2D (not going to ask
  complicated things about kron)

von neumann analysis

floating point
  - how numbers are represented (binary sci. not., no details)
  - IEEE FP principle: each arithmetic operator gives the exact answer, rounded
    to the nearest floating point number.
  - every step of your algorithm, a relative error is introduced in 16th decimal
    digit

General notion of stability and conditioning
  forward error: want f(x), get hat{y} = hat{f}(x).  $y-hat{y}$ is forward error

  backward error: f(x + delta x) = hat{y}: smallest such delta x is
                  the backward error

  diagram of forward error, backward error

  backward stable algorithm:
    gives exact solution of a nearby problem

  Conditioning: measure how sensitive *problem* is to perturbations in input
  (contrast with *stability* of a method).

  condition number of a matrix: what is the practical effect, i.e., on solving Ax=b

NumLinAlg:
  orthog matrix
  LU/GE
  householder/givens
  QR factorization
  eigenvalue problems, QR algorithm
  svd (basics)
  iterative methods (QR alg is one example)
  Gauss-Jacobi and Gauss-Seidel
  Basic ideas of preconditioning and multigrid.

Spectral methods
  cost of FFT
  how to evaluate a derivative

  chebfun: basic idea (represent functions as an expansion in
  polynomial basis), keep all coefficients until the coefficients are
  O(eps_mach).

RBF: just basic idea of scattered grid and placing radially
     basis symmetric fcns at each point.
     - how to find the weights?  (with linear algebra).

FEM: basic ideas
  - review Poisson problem in 1D as in notes: we did this in some detail.