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

Algorithm for Evaluating

S

(x)

i

= 0 : n 1

x

x

i

h

= x

i

x

i

a

b

c

d

S

= a + (x x

i

) (b + (x x

i

) (c + (x x

i

)d))

How many ops are required to for each spline function evaluation?