I. Orientation

Interpolation estimates the value of a function between known data points, while numerical integration estimates the accumulated area under a curve when an exact antiderivative is unavailable. In robotics, these methods support trajectory generation, sensor calibration, motion prediction, velocity estimation, and computation of work or distance from sampled data.

• Governing principle: A smooth function can often be approximated locally by a polynomial constructed from known values.
• Interpolation condition: The approximating polynomial must pass through the available data points, such as ((x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)).
• Distinct nodes: Interpolation formulas generally require distinct values of (x_i); repeated nodes require derivative information and lead to Hermite interpolation.
• Uniform versus non-uniform spacing: Newton forward and backward formulas assume equally spaced points, whereas divided differences and Lagrange interpolation can use unequally spaced points.
• Approximation error: The difference between the exact function and its interpolating polynomial depends on the degree, node locations, and smoothness of the function.
• Notation: (f(x)) denotes the exact function, (P_n(x)) its degree-(n) interpolating polynomial, and (h) the common spacing when nodes are equally spaced.

II. Newton's Divided-Difference Interpolating Polynomials — Efficient hierarchical construction

A. Newton's divided-difference interpolating polynomials

Newton's divided-difference polynomial expresses the interpolant in nested terms, making it convenient to add new data points without rebuilding all previous terms.

• First divided difference: For two data points, the slope is
  [
  f[xi,x{i+1}]=\frac{f(x_{i+1})-f(xi)}{x{i+1}-x_i}.
  ]
  Here, (f[xi,x{i+1}]) is the first divided difference.

• Higher divided differences: They are defined recursively:
  [
  f[xi,\ldots,x{i+k}]

  \frac{f[x{i+1},\ldots,x{i+k}]-f[xi,\ldots,x{i+k-1}]}
  {x_{i+k}-x_i}.
  ]
  The order (k) indicates the number of recursive levels.

• Newton form: For (n+1) points,
  [
  P_n(x)=f[x_0]+fx_0,x_1
  +fx_0,x_1,x_2(x-x_1)+\cdots
  ]
  [
  +f[x_0,\ldots,xn]\prod{j=0}^{n-1}(x-x_j).
  ]
• Divided-difference table: The first column contains (f(x_i)); each next column contains higher-order differences. The top entries of the columns supply the coefficients of (P_n(x)).
• Worked example: For ((0,1),(1,3),(2,7)),
  [
  f[0,1]=2,\qquad f[1,2]=4,\qquad f[0,1,2]=1.
  ]
  Thus,
  [
  P_2(x)=1+2x+x(x-1)=x^2+x+1.
  ]
• Robotics use: With sampled positions (q(t_i)), the polynomial estimates position at an unsampled time (t), and its derivative estimates velocity:
  [
  \hat v(t)=\frac{dP_n(t)}{dt}.
  ]
• Limitation: A high-degree polynomial over a wide interval can oscillate severely, especially near endpoints; piecewise low-degree interpolation is usually more stable.

III. Lagrange Interpolating Polynomials — Direct formula from data nodes

A. Lagrange interpolating polynomials

The Lagrange method constructs a polynomial directly from basis functions that equal one at their own node and zero at all other nodes.

• Lagrange basis: For (n+1) distinct nodes (x_0,\ldots,x_n),
  [
  Li(x)=\prod{\substack{j=0\j\ne i}}^n
  \frac{x-x_j}{x_i-x_j}.
  ]
  Here, (L_i(x)) is the basis polynomial associated with (x_i).
• Interpolation polynomial:
  [
  Pn(x)=\sum{i=0}^{n} f(x_i)L_i(x).
  ]
  The coefficient (f(x_i)) weights the basis function according to the measured data value.
• Cardinal property:
  [
  L_i(x_k)=
  \begin{cases}
  1,&i=k,\
  0,&i\ne k.
  \end{cases}
  ]
  Therefore, (P_n(x_k)=f(x_k)) at every known node.
• Worked example: For ((0,1),(1,3),(2,7)),
  [
  L_0(x)=\frac{(x-1)(x-2)}{2},\quad
  L_1(x)=-x(x-2),\quad
  L_2(x)=\frac{x(x-1)}{2}.
  ]
  Substitution gives (P_2(x)=x^2+x+1).
• Strength: The formula is symmetric in all data points and works for non-uniform nodes, such as irregularly sampled sensor times.
• Limitation: Adding one new point changes every basis polynomial, so repeated updates are less efficient than Newton's form.
• Error term: If (f) has (n+1) continuous derivatives,
  [
  f(x)-Pn(x)=
  \frac{f^{(n+1)}(\xi)}{(n+1)!}
  \prod{i=0}^{n}(x-x_i),
  ]
  where (\xi) lies within the interpolation interval.

IV. Newton's Forward and Backward Interpolating Polynomials — Uniform-grid formulas

A. Newton's forward and backward interpolating polynomials

These formulas use finite differences on equally spaced nodes and are selected according to whether the required value is near the beginning or end of the data table.

• Uniform grid: The nodes satisfy
  [
  x_i=x_0+ih,\qquad i=0,1,\ldots,n,
  ]
  where (h) is the constant interval and (i) is an integer index.
• Forward difference: The operator (\Delta) is defined by
  [
  \Delta yi=y{i+1}-y_i,\qquad
  \Delta^2yi=\Delta y{i+1}-\Delta y_i.
  ]
• Forward polynomial: With
  [
  p=\frac{x-x_0}{h},
  ]
  Newton's forward formula is
  [
  P_n(x)=y_0+p\Delta y_0
  +\frac{p(p-1)}{2!}\Delta^2y_0
  +\frac{p(p-1)(p-2)}{3!}\Delta^3y_0+\cdots.
  ]
  Here, (y_i=f(x_i)), and (p) measures the location relative to (x_0).
• Best placement: The forward formula is most effective when (x) is close to (x_0), because the initial finite differences dominate.
• Backward difference: The operator (\nabla) is defined by
  [
  \nabla y_i=yi-y{i-1}.
  ]
• Backward polynomial: With
  [
  p=\frac{x-x_n}{h},
  ]
  the backward formula is
  [
  P_n(x)=y_n+p\nabla y_n
  +\frac{p(p+1)}{2!}\nabla^2y_n
  +\frac{p(p+1)(p+2)}{3!}\nabla^3y_n+\cdots.
  ]
• Best placement: The backward formula is most effective near (x_n), the final tabulated point.
• Practical selection: For a table from (t=0) to (t=1), use forward interpolation near (t=0) and backward interpolation near (t=1); interior values may use either or a central formula.

V. Numerical Integration — Approximation of accumulated quantities

A. Numerical integration

Numerical integration approximates a definite integral from function values, making it useful when a robot's sensor provides discrete samples rather than a symbolic function.

• Definite integral: The quantity
  [
  I=\int_a^b f(x)\,dx
  ]
  represents accumulated area, where (a) and (b) are limits and (f(x)) is the integrand.
• Geometric interpretation: If (f(x)\ge 0), (I) is the area between the curve (y=f(x)) and the (x)-axis from (a) to (b).
• Sampled motion: If velocity (v(t)) is measured, displacement is approximated by
  [
  \Delta s\approx\int_{t_0}^{t_1}v(t)\,dt.
  ]
  The units remain consistent: ((\mathrm{m/s})(\mathrm{s})=\mathrm{m}).
• Basic procedure:
  1. Divide ([a,b]) into subintervals.
  2. Approximate (f(x)) on each subinterval by a simple polynomial.
  3. Integrate that polynomial exactly.
  4. Add all subinterval contributions.
• Sources of error: Truncation error comes from replacing the curve by a polynomial; measurement and round-off errors come from inaccurate sampled values.
• Accuracy principle: Smaller subintervals generally improve accuracy for smooth functions, but excessive subdivision can increase computational cost and accumulated round-off error.

VI. Newton-Cotes Formulae — Integration from equally spaced samples

A. Newton-Cotes formulae

Newton-Cotes rules integrate an interpolation polynomial through equally spaced values, producing weighted sums of function samples.

• Closed Newton-Cotes rule: The endpoints (a) and (b) are included among the nodes:
  [
  x_i=a+ih,\qquad h=\frac{b-a}{n},\qquad i=0,\ldots,n.
  ]
• General construction: If (P_n(x)) interpolates (f(x)), then
  [
  \int_a^b f(x)\,dx\approx\int_a^b Pn(x)\,dx
  =h\sum{i=0}^{n}w_i f(x_i),
  ]
  where (w_i) are dimensionless weights determined by (n).
• Examples of rules: (n=1) gives the trapezoidal rule; (n=2) gives Simpson's (1/3) rule. Larger (n) produces higher-order closed Newton-Cotes formulas.
• Exactness: A Newton-Cotes rule based on degree-(n) interpolation is exact for every polynomial of degree at most (n), although some symmetric rules are exact for still higher degrees.
• Composite method: The interval is divided into several panels, and the same low-degree rule is applied repeatedly. This is generally more stable than using one high-degree polynomial over the full interval.
• Robotics relevance: Composite rules estimate energy, travelled distance, or integrated tracking error from regularly sampled time-series data.
• Limitation: High-order equally spaced Newton-Cotes rules can have large alternating weights and numerical instability; composite trapezoidal or Simpson rules are usually preferred.

VII. Trapezoidal Rule — Piecewise-linear integration

A. Trapezoidal rule

The trapezoidal rule replaces the function on each interval by a straight line, so the area becomes the area of a trapezoid.

• Single-panel formula: For (a\le x\le b),
  [
  \int_a^b f(x)\,dx\approx
  \frac{b-a}{2}\,[f(a)+f(b)].
  ]
  The two endpoint values determine the linear interpolant.
• Composite formula: With (n) equal subintervals and (h=(b-a)/n),
  [
  \int_a^b f(x)\,dx\approx
  h\left[\frac{f(x_0)+f(xn)}{2}
  +\sum{i=1}^{n-1}f(x_i)\right].
  ]
• Error: If (f'') is continuous,
  [
  E_T=I-T_n=-\frac{(b-a)}{12}h^2f''(\xi),
  ]
  for some (\xi\in(a,b)). Thus the composite rule has order (O(h^2)).
• Interpretation: Convex portions of the curve and concave portions produce opposite signed errors; the total error depends on the curvature (f''(x)).
• Worked example: For (f(x)=x^2) on ([0,2]) with (n=2), (h=1):
  [
  T_2=1\left[\frac{0+4}{2}+1\right]=3.
  ]
  The exact integral is (8/3), so the error is (3-8/3=1/3).
• Advantages and limitation: It requires only function values and works with streaming data, but its (O(h^2)) accuracy is lower than Simpson's rule for comparably smooth data.

VIII. Simpson's 1/3 Rule — Quadratic integration

A. Simpson's 1/3 rule

Simpson's (1/3) rule fits a quadratic polynomial through three equally spaced points and integrates that parabola exactly.

• Panel requirement: Two subintervals are required, so (n) must be even. With (h=(b-a)/n), the three-point panel width is (2h).
• Single-panel formula:
  [
  \int_{x_0}^{x_2}f(x)\,dx\approx
  \frac{h}{3}\left[f(x_0)+4f(x_1)+f(x_2)\right].
  ]
  The middle sample receives weight (4) because of the integrated quadratic basis.
• Composite formula:
  [
  \int_a^b f(x)\,dx\approx
  \frac{h}{3}\left[
  f(x_0)+f(xn)
  +4\sum{\text{odd }i}f(xi)
  +2\sum{\text{even }i\ne0,n}f(x_i)
  \right].
  ]
• Error: If (f^{(4)}) is continuous,
  [
  E_S=I-S_n=-\frac{b-a}{180}h^4f^{(4)}(\xi),
  ]
  for some (\xi\in(a,b)). Its composite accuracy is (O(h^4)).
• Exactness: The rule integrates every polynomial of degree at most three exactly, despite being derived from a quadratic interpolant.
• Worked example: For (f(x)=x^3) on ([0,2]), (h=1):
  [
  S=\frac{1}{3}[0+4(1)+8]=4,
  ]
  which equals (\int_0^2x^3dx=4).
• Operational condition: Samples must be equally spaced and the total number of subintervals must be even; otherwise, a different rule or a combined method is needed.
• Robotics application: Simpson's rule can integrate regularly sampled velocity or acceleration data with high accuracy when the signal is smooth and sufficiently free of noise.