Spline wielomianem 3 stopnia.pdf

Algorithms for Cubic Spline Interpolation

Algorithm for nding z i , i = 0 : : : n

% Compute the h i and b i

for i = 0 : n 1

h i = x i+1 x i

b i = (y i+1 y i )=h i

end

% Gaussian Elimination

u 1 = 2(h 0 + h 1 )

v 1 = 6(b 1 b 0 )

for i = 2 : n 1

u i = 2(h i1 + h i ) h i1 =u i1

v i = 6(b i b i1 ) h i1 v i1 =u i1

end

% Back-substitution

z n = 0

for i = n 1 : 1 : 1

z i = (v i h i z i+1 )=u i

end

z 0 = 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:

z i

6h i

(x i+1 x) 3 + z i+1

6h i

(x x i ) 3 + C i (x x i ) + D i (x i+1 x)

S i (x) =

with C i = y i+1

h i h 6 z i+1 and D i = y h i h 6 z i .

This, however, is not the most ecient 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 ) 2 + d i (x x i ) 3

Notice that this is just the innite Taylor expansion S i (x) = 1 P

n=1

n! (x x i ) n S (n)

(x i ) (with S (n)

= 0 for

n 4 since S i is a cubic polynomial).

Therefore,

a i

S i (x i ) = y i

h i

6 z i+1

h i

3 z i + y i+1 y i

S 0 i (x i ) =

b i

h i

2 S 00 i (x i ) = z i

c i

6 S 000

(x i ) = z i+1 z i

6h i

d i

Algorithm for Evaluating S(x)

for i = 0 : n 1

if x x i+1

break;

end

h = x i+1 x i

Compute a, b, c and d as above.

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?

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: