Natural Cubic Spline PDF

Preview

Summary

Clelia Pech...

Description

Polynomial Interpolation : Cubic Splines Cl´elia Pech

1

Definition

Cubic splines are a particular type of piecewise-polynomial interpolation, using degree three polynomials. It is the most common type of piecewise-polynomial interpolation, used for instance by graphic designers when converting a drawing to a computer image. Definition 1.1. Given a function f on [a, b] and a set of nodes a = x0 < x1 < · · · < xn−1 < xn = b, a cubic spline interpolant S for f is a function that satisfies the following conditions : (a) S(x) is a cubic polynomial Sj (x) on every [xj , xj+1] ; (b) Sj (xj ) = f (xj ) and Sj (xj+1 ) = f (xj+1) ; (c) S ′j+1 (xj+1) = Sj′ (xj+1) ; ′′ ′′ (x (d) Sj+1 j=1 ) = Sj (xj+1 ) ;

(e) One of the following set of boundary conditions is satified : (i) S ′′ (x0 ) = S ′′(xn ) = 0 : free / natural boundary conditions (ii) S ′ (x0 ) = f ′ (x0 ) and S ′ (xn ) = f ′ (xn ) : clamped boundary conditions.

2

Construction of the natural cubic spline

To construct the cubic polynomials Sj (x), we write : Sj (x) = aj + bj (x − xj ) + cj (x − xj )2 + d j (x − xj )3 and we use the conditions of the definition. Condition (b) gives aj = f (xj ) aj+1 =

(1)

aj + bj hj + cj hj2 + d j hj3 ,

(2)

where we set hj := xj+1 − xj . Condition (c) gives bj+1 = bj + 2cj hj + 3d j hj3,

(3)

cj+1 = cj + 3d j hj ,

(4)

Condition (d) implies

1

and finally, we have the boundary data c0 = 0

(5)

cn−1 + 3d n−1 hn = 0.

(6)

Replacing the aj using Equation (1) in Equation (2), we obtain bj =

f (xj+1 ) − f (xj ) − cj hj − d j hj2. hj

(7)

We use this to eliminate the bj in Equation (3) : 2 cj+1 hj+1 + d j+1hj+1 + cj hj + 2d j hj2 =

f (xj +2 ) − f (xj +1) f (xj+1 ) − f (xj ) . − hj+1 hj

(8)

Finally, we eliminate the d j in this equation using Equation (4) : cj+2 hj+1 + 2cj+1(hj+1 + hj ) + cj hj =

3(f (xj+2 ) − f (xj+1 )) 3(f (xj+1 ) − f (xj )) . (9) − hj+1 hj

Equation (9) together with the boundary conditions (5) and (6) determines all the cj , then Equation (8) determines all the d j , and finally Equation (7) determines the bj . Hence we obtain the following theorem : Theorem 1. If f is defined at a = x0 < x1 < · · · < xn−1 < xn = b, then it has a unique natural spline interpolant S on the nodes x0 , . . . , xn , that is, a spline interpolant satisfying the boundary conditions S ′′ (a) = S ′′ (b) = 0.

3

Algorithm for the construction of the natural spline cubic

The goal of this algorithm is to construct the cubic spline interpolant S for the function f , defined at the numbers x0 < · · · < xn , satisfying S ′′ (x0 ) = S ′′(xn ) = 0. Input : integer n ≥ 1 ; numbers x0 < · · · < xn ; values a0 = f (x0 ), . . . , an = f (xn ). Output: the numbers aj , bj , cj , d j such that Sj (x) = aj + bj (x − xj ) + cj (x − xj )2 + d j (x − xj )3 . for i ← 1 to n − 1 do hi ← xi+1 − xi ; end for i ← 1 to n − 1 do 3 (a − a αi ← h3 (ai+1 − ai ) − hi−1 i i−1 ) ; i

end l0 ← 1 ; µ0 ← 0 ; z0 ← 0 ; cn ← 0. for i ← 1 to n − 1 do li ← 2(xi+1 − xi−1 ) − hi−1 µi−1 ; µi ← end for j ← n − 1 to 0 do cj ← zj − µj cj+1 ; bj ←

aj+1 −aj hj

−

hi li

hj (2cj 3

end for j ← 0 to n − 1 do Print(aj , bj , cj , d j ) ; end

2

; zi ←

αi −hi−1 zi−1 li

− cj+1 ) ; d j ←

;

cj+1 −cj 3hj

;...