Table of Contents

BSpline

Modified in 0.9.1

f = InterpolatingFunction.BSpline(x, y, n) makes a B-spline of degree $n$ through the points $(x_i, y_i)$, an interpolating function of type “BSpline”. It is a sum of $N$ B-splines of degree $n$, $$ f(x) = \sum_{j=1}^{N} c_j B_j(x), $$ with the coefficients $c_j$ such that $f(x_i) = y_i$ for all $N$ points. Between two knots $f$ is a polynomial of degree $n$, and $f$ and its derivatives up to order $n - 1$ are continuous.

Input

Output

A B-spline $B_j(x)$ of degree $n$ is a polynomial of degree $n$ between two knots, nonzero on at most $n + 1$ intervals, and smooth up to the derivative of order $n - 1$ at the knots. The knots are made from the data points: $n + 1$ knots at $x_1$, $n + 1$ at $x_N$, and in between the averages of $n$ neighbouring points, $t_{j+n+1} = (x_{j+1} + \dots + x_{j+n})/n$. f.knots lists the $N - n + 1$ different knots. For degree 1 the knots are the data points and the interpolation is a straight line between neighbouring points. For degree 3 it is a cubic interpolation as smooth as a cubic spline, but with fewer knots and without end conditions to choose.

A B-spline of degree $n$ reproduces every polynomial up to degree $n$ exactly, and for smooth data the error decreases as $h^{n+1}$ with the distance $h$ between the points; the $k$-th derivative as $h^{n+1-k}$. A higher degree is therefore more accurate for smooth data. For data with a jump or a kink a high degree oscillates more, see the example on the interpolating function page. The coefficients solve a linear system that becomes worse conditioned with the degree; at degree 9 rounding changes them by about $10^{-14}$ relative, and the $k$-th derivative amplifies this.

New in 0.9.1

-f, and the sum and difference of two B-splines with the same degree and knots, act on the coefficients and are exact. B-splines of any degree are integrated exactly by InterpolatingFunction.Integrate().

Example

Modified in 0.9.1

$\sin(x)$ sampled at 11 points on $[0, \pi]$, interpolated with degrees 1 to 7: every two degrees the error of the function and of its second derivative drop by more than an order of magnitude. The second part shows the properties of a B-spline of degree 3 through points of $x^2$, which it reproduces exactly.

Input

Example.Quanty
-- sin(x) sampled at 11 points on [0, pi], interpolated by B-splines of degree 1 to 7
x, y = {}, {}
for i = 0, 10 do x[i+1] = i*math.pi/10; y[i+1] = math.sin(x[i+1]) end
for _, n in ipairs({1, 2, 3, 5, 7}) do
  local f, e0, e2 = InterpolatingFunction.BSpline(x, y, n), 0, 0
  for i = 0, 1000 do
    local t = i*math.pi/1000
    e0 = math.max(e0, math.abs(f(t) - math.sin(t)))
    if n >= 2 then e2 = math.max(e2, math.abs(f(t, 2) + math.sin(t))) end
  end
  print(string.format("degree %d: %2d knots, max |f - sin| = %.1e, max |f'' + sin| = %s",
                      n, #f.knots, e0, n >= 2 and string.format("%.1e", e2) or "-"))
end
 
-- a B-spline of degree 3 through 6 points
g = InterpolatingFunction.BSpline({0, 1, 2, 3, 4, 5}, {0, 1, 4, 9, 16, 25}, 3)
print("x            = " .. table.concat(g.x, ", "))
print("y            = " .. table.concat(g.y, ", "))
print("knots        = " .. table.concat(g.knots, ", "))
c = g.coefficients
for i = 1, #c do c[i] = string.format("%.4f", c[i]) end
print("coefficients = " .. table.concat(c, ", "))
print("g(2.5) = " .. g(2.5) .. ", type " .. g.type .. ", degree " .. g.degree)
Example.out
degree 1: 11 knots, max |f - sin| = 1.2e-02, max |f'' + sin| = -
degree 2: 10 knots, max |f - sin| = 1.4e-03, max |f'' + sin| = 2.6e-01
degree 3:  9 knots, max |f - sin| = 8.8e-05, max |f'' + sin| = 1.9e-02
degree 5:  7 knots, max |f - sin| = 7.0e-06, max |f'' + sin| = 2.4e-03
degree 7:  5 knots, max |f - sin| = 5.2e-07, max |f'' + sin| = 2.3e-04
x            = 0, 1, 2, 3, 4, 5
y            = 0, 1, 4, 9, 16, 25
knots        = 0, 2, 3, 5
coefficients = 0.0000, 0.0000, 2.0000, 10.3333, 18.3333, 25.0000
g(2.5) = 6.25, type BSpline, degree 3

Table of contents