34 Cubic Spline Approximation Problem:Given n x y i 0,1 ...

1 Spline InterpolationCubic Spline Approximation : problem :Givenn 1 pairs of data pointsxi,yi,i 0,1,..,n, find a piecewise- Cubic polynomialS x S x S0 x a0 b0 x xi c0 x x0 2 d0 x x0 3ifx0 x x1S1 x a1 b1 x x1 c1 x x1 2 d1 x x1 3ifx1 x x2::Sn 1 x an 1 bn 1 x xn 1 cn 1 x xn 1 2 dn 1 x xn 1 3ifxn 1 x xnandS xi yi,i 0,1,.., Splines:Si x ai bi x xi ci x xi 2 di x xi 3,i 0,1,..,n :(1)Si xi yi,i 0,1,2,..,n- interpolating dataxi,yi(2)Si xi 1 Si 1 xi 1 ,i 0,1,..,n 2 continuity at interior points(3)Si xi 1 Si 1 xi 1 ,i 0,1,..,n 2 - continuous slope at interior points(4)Si xi 1 Si 1 xi 1 ,i 0,1,..,n 2 - continuous curvature at interior points(5)S0 x0 0, andSn 1 xn 0 free Spline or natural splineS0 x0 andSn 1 xn -clamped splineTotally we have 4nunknowns:ai,bi,ci,anddi,i 0,1.

2 ,n 1andtherearen 1equationin(1),n 1 equations in (2),n 1 equations in (3)n 1 conditions in (4) and 2 equations in (5). So, again wecan solveai,bi, (1):Si xi yi,wehaveSi xi ai yi,i 0,1,2,..,n 1,andSn 1 xn yn,wehaveanequationinbn 1,cn 1anddn 1:yn 1 bn 1 xn xn 1 cn 1 xn xn 1 2 dn 1 xn xn 1 3 yn.( )From (2):Si xi 1 Si 1 xi 1 ,i 0,1,..,n 2, we haven 1 equations inbi,cianddi,yi bi xi 1 xi ci xi 1 xi 2 di xi 1 xi 3 yi 1,i 0,1,..,n 2. ( )Si x bi 2ci x xi 3di x xi 2. From (3):Si xi 1 Si 1 xi 1 ,i 0,1,..,n 2, we haven 1 equations inbi,cianddi:bi ci xi 1 xi 3di xi 1 xi 2 bi 1,i 0,1,..,n 2.( )Si x 6di x xi 2ci. From (4):Si xi 1 Si 1 xi 1 ,i 0,1,..,n 2, we haven 1 equationsincianddi:2ci 6di xi 1 xi 2ci 1,i 0,1,..,n 2.( )For afree Spline or natural Spline , from conditions:S0 x0 0, andSn 1 xn 0, we have anequation inc0andanequationincn 1anddn 1:2c0 0, and 6dn 1 xn xn 1 2cn 1 0.

3 ( )For aclamped Spline , from conditions:S0 x0 andSn xn , we have a condition inb0and anequation inbn 1,cn 1anddn 1:b0 0, andbn 1 2cn 1 xn xn 1 3dn 1 xn xn 1 2 0.( )To solveai,bi,cianddifrom equations in ( )-( ), we first lethi xi 1 xi,i 0,1,..,n y0y1:yn 1,b b0b1:bn 1,c c0c1:cn 1cn,cn 0,d d0d1:dn 1 Forafreesplineornaturalspline:(I) SetA 1000 0 .. 000h02 h0 h1 h10 0 .. 0000h12 h1 h2 h20 .. 000:::: : .. 0::0000 0 ..hn 22 hn 2 hn 1 hn 10000 0 .. 001 n 1 n 1 v 031h1 y2 y1 1h0 y1 y0 31h2 y3 y2 1h1 y2 y1 :31hn 1 yn yn 1 1hn 2 yn 1 yn 2 0 n 1 1 SolveAc v forc .(II) Evaluate:bi 1hi ai 1 ai hi3 2ci ci 1 ,i 0,1,..,n 13hi ci 1 ci ,i 0,1,..,n aclamped Spline :(I) SetA 2h0h000 0 .. 000h02 h0 h1 h10 0 .. 0000h12 h1 h2 h20.

4 000:::: : .. 0::0000 0 ..hn 22 hn 2 hn 1 hn 10000 0 .. 0hn 12hn 1 n 1 n 1 2v 31h0 y1 y0 31h1 y2 y1 1h0 y1 y0 31h2 y3 y2 1h1 y2 y1 :31hn 1 yn yn 1 1hn 2 yn 1 yn 2 3 1hn 1 yn yn 1 SolveAc v forc .(II) Same as for the Free f x x 0,1 , 3,2 , 8,3 ,construct a free Cubic Spline and a clampedcubic Freecubicspline:(I) Set up the 3 3matrixAand the 3 1 vectorv :h0 3,h1 5A 10032 3 5 5001 1003165001v 0315 3 2 13 2 1 0 0 250 Solve the vectorc :Ac v ,c A 1v 1003165001 10 250 0 1400(II) Compute the vectorsb andd :a 12,c 0 1400b 13 2 1 332 0 14015 3 2 532 140 0 431201760d 13 3 140 013 5 0 140 136016003S x S0 x 1 43120x 0 1360x3for 0 x 3S1 x 2 1760 x 3 140 x 3 2 1600 x 3 3for 3 x Cubic splinef x 12 x 1 1/2,f 0 12,f 8 1219 16(I) Set up the 3 3matrixAand the 3 1 vectorv :h0 3,h1 5A 2 3 3032 3 5 5052 5 63 0316 50510v 313 2 1 12315 3 2 13 2 1 316 15 3 2 12 25 110 Solve the vectorc.

5 Ac v ,c A 1v 63 0316 50510 1 12 25 110 19240 1120 71200(II) Compute the vectorsb andd : 0,1 , 3,2 , 8,3 ,bi 1hi ai 1 ai hi3 2ci ci 1 ,i 0,1,..,n 13hi ci 1 ci ,i 0,1,..,n 12,c 19240 1120 71200b 13 2 1 332 19240 112015 3 2 532 1120 71200 121980d 13 3 1120 1924013 5 71200 1120 17216016000S x S0 x 1 12 x 19240x2 172160x3for 0 x 3S1 x 2 1980 x 3 1120 x 3 2 16000 x 3 3for 3 x Cubic Cubic splineMatLab programs: and generateai,bi,cianddi(av,bv,cv,dv) with input xi,yi (xv,yv). Now we use these two MatLab program for the above Cubic Spline : xv [0;3;8]; yv [1;2;3]; [av,bv,cv,dv] cbspfun(xv,yv);[A|r], where Ac r for solving c_ 0[avbvcvdv] Cubic Spline : xv [0;3;8]; yv [1;2;3]; [av,bv,cv,dv] cbspcl(xv,yv,1/2,1/6);Matrix A and Vector [avbvcvdv] f x cos x2 ,x0 0,x1 ,and x2 a free Cubic Spline and aclamped Cubic Cubic Spline :(I) Set up the 3 3matrixAand the 3 1 vectorv :h0 ,h1 2 cos cos cos 1 0 0 2.

6 1434680 Solve the vectorc :Ac v ,c A 1v 10 2. 1434680 0 1. 190820(II) Compute the vectorsb andd :a cos 0 cos ,c 0 1. 190820b cos 1 2 0 1. 19082 cos cos 2 1. 19082 0 13 1. 19082 0 13 0 1. 19082 32313S x S0 x 1 x 0 x3for 0 x x cos x 1. 19082 x 2 1. 32313 x 3for x Clamped Cubic Spline :f x 2xsin x2 ,f 0 0 ,f 2 sin 1. 30371 (I) Set up the 3 3matrixAand the 3 1 vectorv :h0 ,h1 2 2 cos 1 cos cos cos cos 0 3 1. 30371 cos cos 2. 1435 1. 44714 Solve the vectorc :Ac v ,c A 1v 1 2. 1435 1. 44714 1. 94536(II) Compute the vectorsb andd :a cos 0 cos ,c 1. 94536b cos 1 2 cos cos 2 1.

7 94536 13 13 1. 94536 1. 12474S x S0 x 1 x x2 x3for 0 x x cos x x 2 1. 12474 x 3for x x - a free x - a clamped spline7 Use MatLab programs: and , for above exampleFree Spline : xv [0; ; ]; yv cos(xv.^2); [av,bv,cv,dv] cbspfun(xv,yv);[A|r], where Ac r for solving c_ 0[avbvcvdv] Spline : [av,bv,cv,dv] cbspcl(xv,yv,0, );Matrix A and Vector [avbvcvdv] of Spline Interpolations:Whenf xi yi,i 0,1,..,n, we can useS x to approximatef x x S x ; x S x ;c. abf x dx abS x error:Letf 4 be continuous on a,b with maxa x b|f 4 x | the unique clamped Cubic splineinterpolant tofwith respect to the nodesa x0 x1 .. xn b, thenmaxa x bf x S x 5M384max0 j n 1 xj 1 xj 4 The free Spline will generally give less accurate results than the clamped conditions near the ends of theintervalx0,xnunless the functionfhappens to nearly satisfyf x0 f xn ruddy duck: To approximate the top profile of the duck, we have chosen points alongthe curve through which we want the approximating curve to pass.

8 Notice that more pointsare used when the curve is changing rapidly than when it is changing Spline vs Lagrangian Interpolating Polynomial:80246810121401234 Natural Cubic Spline0246810121401234 Interpolating Polynomial using the Neweton Divided Difference FormulaFree Spline vs Linear Spline :0246810121401234 Natural Cubic Spline0246810121401234linear splineExampleLet S x S0 x 1 Bx 2x2 2x3if0 x 1S1 x 1 b x 1 4 x 1 2 7 x 1 3if1 x 2. Suppose thatS x interpolates f x at x0 0,x1 1and x2 2by a clamped Cubic Spline . Find f 0 andf 2 .9f 0 S0 0 Bf 2 S1 2 b 8 x 1 21 x 1 |x 2 b 8 21 b 13 FindBandb. By the conditions for a clamped Cubic Spline :S0 1 S1 1 1 B 2 2 1 B 1,B 1 S1 1 S0 1 B 4x 6x2 |x 1 4 6 2 S1 1 b,b 2 Therefore,f 0 0andf 2 2 13 f x sin ex 2 and S be the clamped Cubic Spline which interpolates f x at0, , , , , , , ,1, (1) Estimate the Approximation error for f x S x for x in0, 1.

9 (2) Estimate the Approximation error for 01f x dx 01S x dxf x cos ex 2 ex,f x sin ex 2 cos ex 2 exf x cos ex 2 e3x 3sin ex 2 e2x cos ex 2 exf 4 x sin ex 2 e4x 6 cos ex 2 e3x 7 sin ex 2 e2x cos ex 2 |f 4 x |,xin 0,1 f 4 x f 4 1 86. 8 87 Error f x S x 5 87 384max0 j 4 hj4 5 87 384 4 01f x dx 01S x dx 01f x S x dx 1 0 5 87 384max0 j 4 hj4 :1. Given the following 1yi f xi Consider the problem of constructing a free Cubic splineS x . Form the matrixAand vectorv which are used to solve the vectorc containing all coefficientsci s. (Do not solvec .)b. Consider the problem of constructing a clamped Cubic splineS x if we knowf 0 1and10f 1 Form the matrixAand vectorv which are used to solve the vectorc containing allcoefficientsci s.

10 (Do not solvec .)2. Given a Cubic Spline interpolation:S x S0 x 1 2x x3if 0 x 1S1 x 2 b x 1 c x 1 2 d x 1 3if 1 x 2,determine constantsb,c,anddso that all conditions for a natural Cubic Spline Given a Cubic Spline interpolation:S x S0 x 3 x 1 2 x 1 2 x 1 3if 1 x 2S1 x a b x 2 c x 2 2 d x 2 3if 2 x 3andf 1 f 3 , determine constantsa,b,c,anddso that all conditions for a clamped Cubic xi,yi 0, 1 , 1,2 , 2,1 whereyi f xi for somef x , construct a free Cubic splineS x that agrees withf x atx0,x1andx2(with or without using the MatLab program ).a. Approximatef 12 byS 12 .b. Approximatef 1 byS 1 andf 32 byS 32 .c. Extra points: Approximate 01f x dxby 01S x The clamped Cubic splineS x is constructed which agrees with thefunctionf x xcos x 2x2 3x 1 at data points xi,yi : , , , , , , , and satisfies conditions:S , andS Find an upper bound as small aspossible for the Approximation error whenf x is approximated byS x forxin.