Chemistry - De Boor algorithm

In the mathematical subfield of numerical analysis the De Boor algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. It is a generalization of De Casteljau's algorithm for Bézier curves.

Introduction

The general setting is as follows. We would like to construct a curve passing through a sequence of p points $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}$ . The curve can be described as a function $\vec{s}(x)$ of one parameter x. To pass through the sequence of points, the curve must satisfy $\vec{s}(u_0)=\vec{d}_0, \dots, \vec{s}(u_{p-1})=\vec{d}_{p-1}$ . We assume that u₀, ..., u_p-1 are given to us along with $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}$ . This problem is called interpolation.

One approach to solving this problem is by splines. A spline is a curve that is piecewise n^th degree polynomial. This means that, on any interval [u_i, u_i+1), the curve must be equal to a polynomial of degree at most n. It may be equal to a different polynomials on different intervals. The polynomials must be synchronized: when the polynomials from intervals [u_i-1, u_i) and [u_i, u_i+1) meet at the point u_i, they must have the same value at this point and their derivatives must be equal (to ensure that the curve is smooth).

De Boor algorithm is an algorithm which, given u₀, ..., u_p-1 and $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}$ , finds the value of spline curve $\vec{s}(x)$ at a point x. It uses O(n²) operations. Notice that the running time of the algorithm depends only on degree n and not on the number of points p.

Outline of the algorithm

Suppose we want to evaluate the spline curve for a parameter value $x \in [u_{\ell},u_{\ell+1})$ . We can express the curve as

$\vec{s}(x) = \sum_{i=0}^{p-1} \vec{d}_i N_i^n(x),$

where N_iⁿ(x) are polynomials in x with coefficients depending on u₀, ..., u_p but not $\vec{d}_i$ . Due to the spline locality property,

$\vec{s}(x) = \sum_{i=\ell-n}^{\ell} \vec{d}_i N_i^n(x)$

So the value $\vec{s}(x)$ is determined by the controlpoints $\vec{d}_{\ell-n},\vec{d}_{\ell-n+1},\dots,\vec{d}_{\ell}$ ; the other control points $\vec{d}_i$ have no influence. De Boor's algorithm, described in the next section, is a procedure which efficiently evaluates the expression for $\vec{s}(x)$ .

The algorithm

Suppose $x \in [u_{\ell},u_{\ell+1})$ and $\vec{d}_i^{[0]} = \vec{d}_i$ for i = l-n+k, ..., l. Now calculate

$\vec{d}_i^{[k]} = (1-\alpha_{k,i}) \vec{d}_{i-1}^{[k-1]} + \alpha_{k,i} \vec{d}_i^{[k-1]}; \qquad k=1,\dots,n; \quad i=\ell-n+k,\dots,\ell$

with

$\alpha_{k,i} = \frac{x-u_i}{u_{i+n+1-k}-u_i}.$

Then $\vec{s}(x) = \vec{d}_{\ell}^{[n]}$ .

Categories: Algorithms | Numerical analysis