Algorithms for Cubic Spline Interpolation
Algorithm for finding
z
i
,
i
= 0 . . . n
h
i
b
i
i
= 0 : n 1
h
i
= x
i
x
i
b
i
= (y
i
y
i
)/h
i
u
= 2(h + h )
v
= 6(b
b
)
i
= 2 : n 1
u
i
= 2(h
i
+ h
i
) h
i
/u
i
v
i
= 6(b
i
b
i
) h
i
v
i
/u
i
z
n
= 0
i
= n 1 : 1 : 1
z
i
= (v
i
h
i
z
i
)/u
i
z
= 0
How many ops are required to compute the z
i
?
Evaluating
S
(x)
Remember that once you have the z
i
, you can evaluate S(x) as follows:
S
i
(x) =
z
i
6h
i
(x
i
x
) +
z
i
6h
i
(x x
i
) + C
i
(x x
i
) + D
i
(x
i
x
)
with C
i
=
y
h
h
z
i
and D
i
=
y
h
h
z
i
.
This, however, is not the most e cient computational form. We would like to use the idea of nested
multiplication, so write:
S
i
(x) = a
i
+ b
i
(x x
i
) + c
i
(x x
i
) + d
i
(x x
i
)
Notice that this is just the in nite Taylor expansion S
i
(x) =
P
n
n
(x
x
i
)
n
S
n
i
(x
i
) (with S
n
i
= 0 for
n
4 since S
i
is a cubic polynomial).
Therefore,
a
i
= S
i
(x
i
) = y
i
b
i
= S
i
(x
i
) =
h
i
6
z
i
h
i
3
z
i
+
y
i
y
i
h
i
c
i
=
1
2
S
i
(x
i
) =
z
i
2
d
i
=
1
6
S
i
(x
i
) =
z
i
z
i
6h
i
