Shared Flashcard Set

Details

Numerical Integration and Differentiation
Numerical quadrature; Extrapolation methods; Numerical differentiation
22
Computer Science
Graduate
03/04/2014

Additional Computer Science Flashcards

 


 

Cards

Term
Riemann Sums
Definition
[image]
Term
Existence of Riemann Integral
Definition
If f is bounded and continuous almost everywhere on an interval [a,b], then the Riemann integral I(f) exists.
Term
Ill-posedness of Differentiation
Definition
No unique solution (can always add a constant)
Term
Interpolatory Quadrature
Definition

1. Evaluate the integrand function f at the points xi

2. Determine the polynomial of degree n-1 that interpolations the function values at those points

3. Take the integral of the interpolant as an approximation to the integral of the original function

Term
Method of Undetermined Coefficients
Definition
Choose the weights so that the rule integrates the first n polynomial basis functions exactly, resulting in a system of n equations in n unknowns.
Term
Moment Equations
Definition

Method of undetermined coef with monomial basis

[image]

Term
Newton-Cotes Quadrature
Definition
  • Choose equally spaced nodes in the interval [a,b].  
  • An n-point open Newton-Cotes rule has nodes xi=a + i(b-a)/(n+1)
  • An n-point closed Newton-Cotes rule has nodes xi=a+(i-1)(b-a)/(n-1)
  • An n-point rule with odd n has dress one greater than that of the polynomial on which it is based
Term
Midpoint Rule
Definition

Interpolate function value at the midpoint of the interval by polynomial of degree 0.

M(f) = (b-a) f((a+b)/2)

Term
Trapezoid Rule
Definition

Interpolate function values at the two endpoints of the interval by a polynomial of degree one (straight line).

T(f) = (b-a)/2 (f(a)+f(b))

Term
Simpson's Rule
Definition

Interpolate function values at two endpoints and midpoint by polynomial of degree two.

S(f) = (b-a)/6 (f(a) +4f((a+b)/2) + f(b))

Term
Gaussian Quadrature
Definition
Both the nodes and the weights are optimally chosen to maximize the degree of the resulting quadrature rule.  n-point Gaussian rule has degree 2n-1.
Term
Composite Quadrature
Definition
  • On a given interval [a,b], subdivide the interval into k subintervals, typically of uniform length h = (b-a)/k.
  • Apply n-point simple quadrature rule in each subinterval.
  • Take the sum of these results as approximate value of the integral.
Term
Adaptive Quadrature
Definition
  • Take a pair of quadrature rules whose difference provides an error estimate, or a single rule at two different levels of subdivision
  • Apply both rules on the initial interval of integration.  If the resulting approximate values differ by more than tolerance, divide interval into two or more subintervals and repeat
Term
Richardson Extrapolation
Definition
  • Compute approximate values for some step sizes and then estimate what value would be for step size zero.
  • F(h) - value for some step size h
  • a0- approximate solution to F(0)
  • a0 = F(h) + (F(h) - F(h/q))/(q-p-1) + O(hr)
Term
Romberg Integration
Definition
  • Richardson extrapolation with composite trapezoid rule
  • F(h) = a0+a1h2+O(h4)
  • F(0) = a0=F(h) + (F(h) - F(h/2))/(2-2-1)
  • F(0) = (4 F(h/2) - F(h)) / 3
Term
Conditioning of Numerical Differentiation
Definition

Inherently Sensitive

Small perturbations in the data can cause large changes in the result

Term
Numerical Differentiation: Interpolation
Definition
If data are sufficiently smooth, interpolation may be appropriate but if noisy then use smoothing approximating function (least squares polynomial or spline).
Term
Finite Difference Approximation
Definition
Useful for approximating derivatives for smooth data.  Given a smooth function f, we wish to approximate its first and second derivatives at a point x.
Term
Forward Difference Formula
Definition
[image]
Term
Backward Difference Formula
Definition
[image]
Term
Centered Difference Formula
Definition
[image]
Term
Centered Difference Formula for Second Derivative
Definition
[image]
Supporting users have an ad free experience!