In the Lagrange method, polynomial of order n is used to interpolate between n+1 data points. But in some cases, this technique leads to erroneous results. For example there are some cases which the function is generally smooth, but undergoes an abrupt change somewhere along the region of interest. Using high order polynomials causes wild oscillations around of the abrupt change. Spline curves are the best choices in thesekind of problems. They use simple low order polynomials which are connected together to built the desired curve. Cubic spline curves use third order polynomials between each two points. Suppose a third order polynomial as follows: For n+1 data points x_{0} to x_{n} there are n intervals and consequently n third order polynomials. Therefore there are 4n unknowns constants to evaluate. 4n conditions are required which can be represented as follows: 1. The curve should pass through all data points. (2n conditions) 2. The first derivative of the polynomials at interior points should be the same. (n-1 conditions) 3. The second derivative of the polynomial at the interior points should be the same. (n-1 conditions) To have a smooth curve which pass through all data points, above conditions are completely obvious. Now, there are 4n unknown and 4n-2 conditions. To solve the problem, 2 conditions should be added to the above conditions. In many literatures, these conditions define as follows: 4. the second derivative of the curve should be zero at the end data points. (2 conditions) Now, the problem is transformed to a system of 4n linear algebraic equations which can be solved easily. Cheney and Kinciad in 1985 showed that cubic spline curve can be obtained by solving a three diagonal system of algebraic equations having only n-1 unknowns. Using this method the third order polynomial within each interval can be represented as follows:
f”(x_{i}) at the end data points are zero. Other f”(x_{i})s can be determined solving the following system of n-1 linear equations:
Curve Fitting (Source Code in C++) |
About Numerical Methods > Curve Fitting >