M371 - Alexiades
What to know for the Midterm
in addition to the material for Quiz 1
Material
  • floating point numbers and arithmetic
  • measures and types of error
  • Taylor expansion
  • finding roots
  • linear systems
  • finite-differences for derivatives
  • interpolation
  • nonlinear systems
    Concepts
  • finite precision and consequencies, machine epsilon, dangers in machine arithmetic
  • roundoff error: cause, consequencies, strategies for minimizing loss of significant digits
  • absolute / relative error of an approximation, big O notation
  • well / ill conditioned process (having small / large rel.error amplification factor)
  • basics of linear algebra, Fundamental Thm for square matrices (at least 8 equivalent statements)
  • norm axioms ; standard vector, matrix, function norms
  • well / ill conditioned matrix, condition number
  • absolute / relative error bounds in solving Ax=b
  • iterations: order of convergence, stopping criteria
  • interpolation concept, interpolation types (non/piecewise, Hermite, splines), advantages/disadvantages of each
  • polynomial interpolation errors:  discretization: ∥ f − PN ≤ ( M/ 4(N+1) ) hN+1 , roundoff: ∥ PN − QN ≤ ½(2N+1) ε
        total error = ∥ f − QN ≤ ∥ f − PN + ∥ PN − QN
  • Jacobian of a vector function F: ℝn → ℝn is the n×n matrix   J(x) = [ ∂Fi(x) / ∂xj ]
    Methods
  • nested form of polynomial for efficient evaluation
  • find roots by bisection, Newton-Raphson, secant, fixed point
  • solve Ax=b:   reduction to REF + backsubstitution, LU factorization, pivoting, relevant matlab functions
  • Lagrange and Newton form of interpolating polynomial
  • finite-difference approximation of derivatives: forward, backward, centered
  • Newton method for a nonlinear system F(x) = 0 : solve the system  J(xn) Δx = −F(xn) ; xn+1 = xn + Δx

  • For each Method should know: what it is for, idea, advantages/disadvantages, and:
    Method know discretization error "roundoff" error order/rate
    Taylor expansion algo en = f(n+1)(ξ) / (n+1)!  (x-xo)n+1  
    bisection algo en = (b-a) / 2n   linear
    fixed point algo |en+1| ≤ K |en| ,   K=Lipschitz constant ε / (1−K) linear
    Newton-Raphson algo |en+1| ≤ C |en|2   quadratic
    secant algo |en+1| ≤ C |en|p ,  p ≈ 1.62   p ≈ 1.62
    Müller idea |en+1| ≤ C |en|p ,  p ≈ 1.84   p ≈ 1.84
    inverse quadratic interpolation idea |en+1| ≤ C |en|p ,  p ≈ 1.84   p ≈ 1.84
    polynomial interpolation algo eN = f(N+1)(ξ) /(N+1)!   ∏i=0N(x-xi) ½(2N+1) ε  
    piecewise interpolation idea  
    Hermite idea  
    spline idea  
    Bezier curve idea  
    forward FD for f′(x) algo O(h) ε / h 1st order
    backward FD for f'(x) algo O(h) ε / h 1st order
    centered FD for f'(x) algo O(h2) ε / h 2nd order