
Natural Cubic Spline Interpolation
by admin in Curve Fitting , Interpolation , Math, Statistics, and Optimization , MATLAB Family on June 18, 2019Cubic spline interpolation is a special case for Spline interpolation that is used very often to avoid the problem of Runge’s phenomenon. This method gives an interpolating polynomial that is smoother and has smaller error than some other interpolating polynomials such as Lagrange polynomial and Newton polynomial.
Example On Using This Code
Input
xf = [0 1 2 3]; % X Values yf = [exp(xf(1)) exp(xf(2)) exp(xf(3)) exp(xf(4))]; % Y Values xx = 1.5; % Value we interest to interpolate.
Output
The numbers x(0), ..., x(n) are: 0.0000 1.0000 2.0000 3.0000 The coefficients of the spline on the subintervals are: a(i) b(i) c(i) d(i) 1.00000000 1.46599761 0.00000000 0.25228421 2.71828183 2.22285026 0.75685264 1.69107137 7.38905610 8.80976965 5.83006675 -1.94335558 Interpolated value at 1.5 is equal to = 4.2303 All Splines: 1.465997*conj(x) + 0.25228421*conj(x)^3 + 1.0 5.7823590*conj(x) - 4.3163614*conj(x)^2 + 1.69107137*conj(x)^3 - 0.4387871 17.4902*conj(x)^2 - 37.8307*conj(x) - 1.943355*conj(x)^3 + 28.6366
Contents
- Definition
- Boundary Conditions
- Methods
- Example
- Exercise
- References
Definition
Given a set of n + 1 data points (xi,yi) where no two xi are the same and a = x_(0) < x_(1) < … < x_(n) = b, the spline S(x) is a function satisfying:
- S(x) in C^(2) [a,b];
- On each subinterval [x_(i-1), x_(i)], S(x) is a polynomial of degree 3, where i = 1,… ,n.
- S(x_(i)) = y_(i), for all i = 0, 1,… ,n.
Let us assume that
where each
is a cubic function, i = 1,… ,n.
Boundary Conditions
To determine this cubic spline S(x), we need to determine a_(i), b_(i), c_(i) and d_(i) for each i by:
- C_(i)(x_(i-1)) = y_(i-1) and C_(i)(x_(i)) = y_(i), i = 1,… ,n.
- C’_(i)(x_(i)) = C’_(i+1)(x_(i)), i = 1,… ,n-1.
- C”_(i)(x_(i)) = C”_(i+1)(x_(i)), i = 1,… ,n-1.
We can see that there are n + n + (n-1) + (n-1) = 4n-2 conditions, but we need to determine 4n coefficients, so usually we add two boundary conditions to solve this problem. There are three types of common boundary conditions:
I. First derivatives at the endpoints are known:
This is called clamped boundary conditions.
II. Second derivatives at the endpoints are known:
.
The special case
is called natural or simple boundary conditions.
III. When the exact function f(x) is a periodic function with period x_(n) – x_(0), S(x) is a periodic function with period x_(n) – x_(0) too. Thus
.
The spline functions S(x) satisfying this type of boundary condition are called periodic splines.
Methods
There are several methods that can be used to find the spline function S(x) according to its corresponding conditions. Since there are 4n coefficients to determine with 4nconditions, we can easily plug the values we know into the 4n conditions and then solve the system of equations. Note that all the equations are linear with respect to the coefficients, so this is workable and computers can do it quite well.
The algorithm given in w:Spline interpolation is also a method by solving the system of equations to obtain the cubic function in the symmetrical form.
The other method used quite often is w:Cubic Hermite spline, this gives us the spline in w:Hermite form.
Here, we discuss another method using second derivatives S”(x_(i)) = M_(i)(i = 0,1,… ,n) to find the expression for spline S(x).
Let h_(i) = x_(i) – x_(i-1), i = 1,… ,n, S”(xi) = C”_(i)(xi) = C”_(i+1) (xi) = Mi (i = 1,… ,n-1) and S”(x0) = C”_(1)(x0) = M0, and S”(xn) = C”_(n)(xn) = Mn. Note that M_{i} are unknown (except for type II boundary condition, M_{0} and M_{n} are given).
Since each C_(i) is a cubic polynomial, C”_(i) is linear.
By w:Lagrange interpolation, we can interpolate each C”_(i) on [x_(i-1), x_(i)] since C”_(i)(x_(i-1)) = M_(i-1) and C”_(i)(xi) = Mi, the Lagrange form of this interpolating polynomial is:
for x in [x_{i-1},x_{i}].
Integrating the above equation twice and using the condition that C_{i}(x_{i-1}) = y_{i-1} and C_{i}(x_{i}) = y_{i} to determine the constants of integration, we have
-
(
)
This expression gives us the cubic spline S(x) if M_{i},i=0,1,…. ,n can be determined.
For i=1,… ,n-1 when x in [x_{i}, x_{i+1}], we can calculate that
Therefore,
Similarly, when x in [x_{i-1}, x_{i}], we can shift the index to obtain
-
(
)
Thus,
Since
, we can derive
-
(
)
where
-
(
)
and f[x_{i-1}, x_{i} ,x_{i+1}] is a divided difference. According to different boundary conditions, we can solve the system of equations above to obtain the values of M_{i}‘s.
I. For type I boundary condition, we are given C’_{1}(x_{0}) = f’_{0} and C’_{n}(x_{n}) = f’_{n}. According to equation (2 ), we can obtain
-
-
(
)
-
Similarly, simplifying
we will have
-
-
( )
-
Therefore, let
and
, combine (3 ), (5.1 ) and (5.2 ) together, so the system of equations that we need to solve is
-
-
(
)
-
II. For type II boundary condition, we are given
-
-
and
(
)
-
directly, so let lambda _{0} = mu _{n} = 0, d_{0} = 2f”_{0}, and d_{n} = 2f”_{n}, and we need to solve the system of equations in the same form as (6).
Example
For points (0,0), (1,0.5), (2,2) and (3,1.5), find the interpolating cubic spline S(x) satisfying S'(0) = 0.2 and S'(3) = -1.
Solution:
We can easily see that h_{i} = 1 for i = 1,2,3 so
and mu _{3} = 1.
Also, since this is the type I boundary condition problem, we can calculate that
- and
Therefore, plug into the system of equations, we have
The solution is M_{0} = -0.36, M_{1} = 2.52, M_{2} = -3.72 and M_{3}=0.36.
Therefore, by the general expression of the solution, we have
Similarly,
- and
Thus the cubic spline is
References
- Polynomial and Spline Interpolation, http://www.math.ohiou.edu/courses/math3600/lecture19.pdf
- 数值分析,李庆扬,王能超,易大易,2001. ISBN 7-302-04561-5 (Numerical Analysis, Qinyang Li, Nengchao Wang, Dayi yi.)
Share Now!