M371 - Alexiades
                                Review3: for Quiz 2
Material:

Interpolation

Quadrature (numerical integration)

Concepts:

discretization error, roundoff error

interpolation concept, interpolation types (non/piecewise, Hermite, Bezier, splines), advantages/disadvantages of each

polynomial interpolation errors:  discretization: ∥ f − P_N ∥_∞ ≤ ( M/ 4(N+1) ) h^N+1 , roundoff: ∥ P_N − Q_N ∥_∞ ≤ ½(2^N+1) ε
                        total error = ∥ f − Q_N ∥_∞ ≤ ∥ f − P_N ∥_∞ + ∥ P_N − Q_N ∥_∞

quadrature rules for I(f)= ∫_a^bf(x)dx: general form of N-point rule:   Q_N(f) = ∑_i=1^N A_i f(ξ_i)   ≈ I(f)

order and precision of quadrature rule

Newton-Cotes type rules: user-specified nodes ξ_i, rule weights A_i obtained by integration of interpolating polynomial

Gaussian rules: nodes and weights chosen for maximum precision (2N-1 for N-point rule) and tabulated

ideas about orthogonal polynomials and Gaussian quadrature

idea of adaptive quadrature (finer mesh where error is estimated to be high)

idea of Richardson extrapolation

Methods:

Lagrange and Newton form of the (unique!) interpolating polynomial

standard Newton-Cotes rules: rectange, trapezoidal, midpoint, Simpson for I(f) = ∫_a^bf(x)dx

standard Gaussian rules:
  Gauss-Legendre for I(f) = ∫₋₁¹f(x) dx
  Gauss-Chebyshev for I(f) = ∫₋₁¹ 1/√(1−x²) f(x) dx
  Gauss-Laguerre for I(f) = ∫₀^∞ e^−x f(x) dx
  Gauss-Hermite for I(f) = ∫_−∞^∞ e^−x2 f(x) dx

very simple and useful: the 2-point Gauss-Legendre: GL₂ = f(−1/√3) + f(1/√3) approximates I(f)=∫₋₁¹f(x)dx at precision 3 !!!

For each Method should know: what it is for, idea, advantages/disadvantages, and:
 
  Interpolation   (ill-conditioned for high N)

Method	know	discr.error	roundoff error
polynomial interpolation	algo	eN = f(N+1)(ξ) /(N+1)! ∏i=0N(x-xi)    ≤ M/ 4(N+1) hN+1	½(2N+1) ε
piecewise interpolation	idea
spline	idea
Bezier curve	idea
Hermite	idea

  Quadrature   (well conditioned process)

Method	know	discr.error, order	precision	roundoff error
Rectangle rule	algo	O( h ) , 1st	0	(b-a) ε
Trapezoidal rule	algo	O( h2 ) , 2nd	1	(b-a) ε
Simpson rule	algo	O( h4 ) , 4th	3	(b-a) ε
2-pt Gauss-Legendre	algo		3(for 2-point) (2N-1 for N-point)	(b-a) ε

---