The choice of piecewise polynomials of degree 3 for interpolation is justifiably popular: even-degree splines are algebraically awkward to construct, degree 1 is simply piecewise linear interpolation (not smooth), and degree 5, while feasible, entails juggling too many coefficients. Besides, a cubic polynomial minimizes the amount of wiggling (the integral of second derivative squared) for given values and slopes at the endpoints of an interval. (Recall Connecting dots naturally.)

But the derivative of a cubic spline is a quadratic spline. And one needs the derivative to find the critical points. This results in an awkward example in SciPy documentation, annotated with “(NB: sproot only works for order 3 splines, so we fit an order 4 spline)”.

Although not implemented in SciPy, the task of computing the roots of a quadratic spline is a simple one. Obtaining the roots from the internal representation of a quadratic spline in SciPy (as a linear combination of B-splines) would take some work and reading. But a quadratic polynomial is determined by three values, so sampling it at three points, such as two consecutive knots and their average, is enough.

## Quadratic formula with values instead of coefficients

Suppose we know the values of a quadratic polynomial q at -1, 0, 1, and wish to find if it has roots between -1 and 1. Let’s normalize so that q(0)=1, and let x = q(-1), y = q(1). If either x or y is negative, there is definitely a root on the interval. If they are positive, there is still a chance: we need the parabola to be concave up, have a minimum within [-1, 1], and for the minimum to be negative. All of this is easily determined once we note that the coefficients of the polynomial are a = (x+y)/2 – 1, b = (y-x)/2, and c = 1.

The inequality ensures the suitable sign of the discriminant. It describes a parabola with vertex (1, 1) and focus (2, 2), contained in the first quadrant and tangent to the axes at (4, 0) and (0, 4). Within the orange region there are no real roots.

The line x+y=2, tangent to the parabola at its vertex, separates convex and concave parabolas. While concavity in conjunction with x, y being positive definitely precludes having roots in [-1, 1], slight convexity is not much better: it results in real roots outside of the interval. Here is the complete picture: green means there is a root in [-1, 1], orange means no real roots, red covers the rest.

## Back to splines

Since the derivative of a spline is implemented in SciPy (B-splines have a nice formula for derivatives), all we need is a root-finding routine for quadratic splines. Here it is, based on the above observations but using built-in NumPy polynomial solver np.roots to avoid dealing with various special cases for the coefficients.

def quadratic_spline_roots(spl): roots = [] knots = spl.get_knots() for a, b in zip(knots[:-1], knots[1:]): u, v, w = spl(a), spl((a+b)/2), spl(b) t = np.roots([u+w-2*v, w-u, 2*v]) t = t[np.isreal(t) & (np.abs(t) <= 1)] roots.extend(t*(b-a)/2 + (b+a)/2) return np.array(roots)

A demonstration, which plots the spline (blue), its critical points (red), and original data points (black) as follows:

import numpy as np import matplotlib.pyplot as plt from scipy.interpolate import InterpolatedUnivariateSpline x = np.arange(7) y = np.array([3, 1, 1, 2, 2, 4, 3]) f = InterpolatedUnivariateSpline(x, y, k=3) crit_pts = quadratic_spline_roots(f.derivative()) t = np.linspace(x[0], x[-1], 500) plt.plot(t, f(t)) plt.plot(x, y, 'kd') plt.plot(crit_pts, f(crit_pts), 'ro') plt.show()

Ā

I have been working on techniques for non-linear interpolation. I got started a long time ago when I saw a short note in a design magazine that demonstrated a graphical technique that could generate points on a parabola.

The technique was an example of Aitken’s graphical expression for Lagrange interpolation.

Details of my work can be found on my blog. https://alfred-excel-vachris.com/

Titled: My Graphical Tool Kit for Tabular Functions

My algorithms use a sliding set of three points to process 2D and 3D tabular functions. My algorithms calculate as they go along the tabular function without computing coefficients.

My algorithms include:

Non-Linear Interpolation

Non-Linear Inverse Interpolation

Arc Length (used for parameterizing the tabular function)

Slopes

Smoothing

Root Finding

Regards

Alfred F Vachris Jr ex-aerospace engineer, Senior Excel VBA Devloper