8.2.S The Math of Cubic SplinesProblem StatementHere I show you how to derive the spline algorithm we use. First let us state the problem. Given is a set of points which belong to an unknown function y=f(x). We also know the first derivative of the function in the given points y'=f'(x). What we want to compute is an approximation of the unknown function value y for a given x. |
![]() |
Algorithm OverviewLike you can see is the x value for which we want to compute y enclosed between two points. In a first step the algorithm finds the surrounding points with binary search. After that we interpolate with the information provided by the two surrounding points. Spline InterpolationThe cubic splines are polynomials of the form: y = a*x3 + b*x2 + c*x + d =: P(x) To evaluate the above expression we have to find the parameters a, b, c and d. If we have the parameters we can simply evaluate the expression with the given x and we will get y. ![]() We call the above polynomial P, and state four equations for the four unknown parameters a, b, c and d. The first line states the equations of the two surrounding points, which are known, and the second line shows two equations for the first derivatives, which are also known. Now you could already solve this system, but it would lead to quite unpleasant expressions. ![]() To avoid that we introduce the new parameter t. Like you can see from the definition and the expressions it is 0 at xi and 1 at xi+1. This will be very pleasant, because evaluating a polynomial for 0 or 1 is much easier than for most of the other numbers. Now we work with t, so I state a new polynomial Q(t) := a*t3 + b*t2 + c*t + d ![]() We need to convert the given points from P(x) to Q(t), and we get the expected Q(0) and Q(1). ![]() The same applies for the derivatives P'(x), we convert it to Q'(t) and get Q'(0) and Q'(1). ![]() Now we compute the derivative of the concrete polynomial. ![]() We evaluate the equations for t=0 and get the parameters c and d. ![]() We evaluate the equations with t=1, and get two equations with two unknown parameters. You can solve this system for a and b. ![]() Finally we got all parameters a, b, c and d. We can now evaluate the polynomial. The expression used in the concrete algorithm uses the Horner-Schema to improve efficiency. Summary
|
Back |
The pit class. |