Interpolation and approximation List of numerical analysis topics

1 interpolation , approximation

1.1 polynomial interpolation
1.2 spline interpolation
1.3 trigonometric interpolation
1.4 other interpolants
1.5 approximation theory
1.6 miscellaneous

interpolation , approximation

interpolation — construct function going through given data points

nearest-neighbor interpolation — takes value of nearest neighbor

polynomial interpolation

polynomial interpolation — interpolation polynomials

linear interpolation
runge s phenomenon
vandermonde matrix
chebyshev polynomials
chebyshev nodes
lebesgue constant (interpolation)
different forms interpolant:

newton polynomial

divided differences
neville s algorithm — evaluating interpolant; based on newton form


lagrange polynomial
bernstein polynomial — useful approximation
brahmagupta s interpolation formula — seventh-century formula quadratic interpolation


extensions multiple dimensions:

bilinear interpolation
trilinear interpolation
bicubic interpolation
tricubic interpolation
padua points — set of points in r unique polynomial interpolant , minimal growth of lebesgue constant


hermite interpolation
birkhoff interpolation
abel–goncharov interpolation

spline interpolation

spline interpolation — interpolation piecewise polynomials

spline (mathematics) — piecewise polynomials used interpolants
perfect spline — polynomial spline of degree m mth derivate ±1
cubic hermite spline

centripetal catmull–rom spline — special case of cubic hermite splines without self-intersections or cusps


monotone cubic interpolation
hermite spline
bézier curve

de casteljau s algorithm
composite bézier curve
generalizations more dimensions:

bézier triangle — maps triangle r
bézier surface — maps square r




b-spline

box spline — multivariate generalization of b-splines
truncated power function
de boor s algorithm — generalizes de casteljau s algorithm


non-uniform rational b-spline (nurbs)

t-spline — can thought of nurbs surface row of control points allowed terminate


kochanek–bartels spline
coons patch — type of manifold parametrization used smoothly join other surfaces together
m-spline — non-negative spline
i-spline — monotone spline, defined in terms of m-splines
smoothing spline — spline fitted smoothly noisy data
blossom (functional) — unique, affine, symmetric map associated polynomial or spline
see also: list of numerical computational geometry topics

trigonometric interpolation

trigonometric interpolation — interpolation trigonometric polynomials

discrete fourier transform — can viewed trigonometric interpolation @ equidistant points

relations between fourier transforms , fourier series


fast fourier transform (fft) — fast method computing discrete fourier transform

bluestein s fft algorithm
bruun s fft algorithm
cooley–tukey fft algorithm
split-radix fft algorithm — variant of cooley–tukey uses blend of radices 2 , 4
goertzel algorithm
prime-factor fft algorithm
rader s fft algorithm
bit-reversal permutation — particular permutation of vectors 2 entries used in many ffts.
butterfly diagram
twiddle factor — trigonometric constant coefficients multiplied data
cyclotomic fast fourier transform — fft on finite fields
methods computing discrete convolutions finite impulse response filters using fft:

overlap–add method
overlap–save method




sigma approximation
dirichlet kernel — convolving function dirichlet kernel yields trigonometric interpolant
gibbs phenomenon

other interpolants

simple rational approximation

polynomial , rational function modeling — comparison of polynomial , rational interpolation


wavelet

continuous wavelet
transfer matrix
see also: list of functional analysis topics, list of wavelet-related transforms


inverse distance weighting
radial basis function (rbf) — function of form ƒ(x) = φ(|x−x0|)

polyharmonic spline — commonly used radial basis function
thin plate spline — specific polyharmonic spline: r log r
hierarchical rbf


subdivision surface — constructed recursively subdividing piecewise linear interpolant

catmull–clark subdivision surface
doo–sabin subdivision surface
loop subdivision surface


slerp (spherical linear interpolation) — interpolation between 2 points on sphere

generalized quaternion interpolation — generalizes slerp interpolation between more 2 quaternions


irrational base discrete weighted transform
nevanlinna–pick interpolation — interpolation analytic functions in unit disc subject bound

pick matrix — nevanlinna–pick interpolation has solution if matrix positive semi-definite


multivariate interpolation — function being interpolated depends on more 1 variable

barnes interpolation — method two-dimensional functions using gaussians common in meteorology
coons surface — combination of linear interpolation , bilinear interpolation
lanczos resampling — based on convolution sinc function
natural neighbor interpolation
nearest neighbor value interpolation
pde surface
transfinite interpolation — constructs function on planar domain given values on boundary
trend surface analysis — based on low-order polynomials of spatial coordinates; uses scattered observations
method based on polynomials listed under polynomial interpolation



approximation theory

approximation theory

orders of approximation
lebesgue s lemma
curve fitting

vector field reconstruction


modulus of continuity — measures smoothness of function
least squares (function approximation) — minimizes error in l-norm
minimax approximation algorithm — minimizes maximum error on interval (the l-norm)

equioscillation theorem — characterizes best approximation in l-norm


unisolvent point set — function given function space determined uniquely values on such set of points
stone–weierstrass theorem — continuous functions can approximated uniformly polynomials, or other function spaces
approximation polynomials:

linear approximation
bernstein polynomial — basis of polynomials useful approximating function
bernstein s constant — error when approximating |x| polynomial
remez algorithm — constructing best polynomial approximation in l-norm
bernstein s inequality (mathematical analysis) — bound on maximum of derivative of polynomial in unit disk
mergelyan s theorem — generalization of stone–weierstrass theorem polynomials
müntz–szász theorem — variant of stone–weierstrass theorem polynomials if coefficients have zero
bramble–hilbert lemma — upper bound on l error of polynomial approximation in multiple dimensions
discrete chebyshev polynomials — polynomials orthogonal respect discrete measure
favard s theorem — polynomials satisfying suitable 3-term recurrence relations orthogonal polynomials


approximation fourier series / trigonometric polynomials:

jackson s inequality — upper bound best approximation trigonometric polynomial

bernstein s theorem (approximation theory) — converse jackson s inequality


fejér s theorem — cesàro means of partial sums of fourier series converge uniformly continuous periodic functions
erdős–turán inequality — bounds distance between probability , lebesgue measure in terms of fourier coefficients


different approximations:

moving least squares
padé approximant

padé table — table of padé approximants


hartogs–rosenthal theorem — continuous functions can approximated uniformly rational functions on set of lebesgue measure zero
szász–mirakyan operator — approximation e x on semi-infinite interval
szász–mirakjan–kantorovich operator
baskakov operator — generalize bernstein polynomials, szász–mirakyan operators, , lupas operators
favard operator — approximation sums of gaussians


surrogate model — application: replacing function hard evaluate simpler function
constructive function theory — field studies connection between degree of approximation , smoothness
universal differential equation — differential–algebraic equation solutions can approximate continuous function
fekete problem — find n points on sphere minimize kind of energy
carleman s condition — condition guaranteeing measure uniquely determined moments
krein s condition — condition exponential sums dense in weighted l space
lethargy theorem — distance of points in metric space members of sequence of subspaces
wirtinger s representation , projection theorem
journals:

constructive approximation
journal of approximation theory



miscellaneous

extrapolation

linear predictive analysis — linear extrapolation


unisolvent functions — functions interpolation problem has unique solution
regression analysis

isotonic regression


curve-fitting compaction
interpolation (computer graphics)