Curve Fitting

Given N points

Find Nice-looking curve through these points

Polynomial Interpolation

1 polynomial of degree N-1 matches points

Complicated,fluctuated,slow

Spline Interpolation

from mechanics

piece together N-1 cubic curves together smoothly

(1)

(2)

(3)

4N-4 unknowns

4N-4 equations

Gaussian Elimination can do

Better approach

Let the curves be S as described as fallows,

Curse

we have the properties:

to show how (2) stands：

so, , such that and note that:

Spline curve

With the two properties above, all we have to do is to determine Pi through the first differential equations:

which leads us to simple matrix computation.

For Example, let n = 7, we can construct a matrix bellow:

Solve , then plug them to Si to finish the approach.

Time complexity: T=O(N)