Transcription of Cubic Splines - Stanford University
1 Cubic SplinesAntony JamesonDepartment of Aeronautics and Astronautics, Stanford University , Stanford ,California, 943051 References on splines1. J. H. Ahlberg, E. N. Nilson, J. H. Walsh. Theory of Splines and their applica-tions , Academic Press, I. J. Schoenberg (ed.). spline functions , (Symposium at U. Wisconsin, 1969),Academic Press, I. J. Schoenberg. Quart. Appl. Math. 4, 1946, pp. 45-99, pp. C. H. Reinsch. Numer. Math. 10, 1967, pp. 177-183. Smoothing by spline Schulz, spline Definition of splineA spline is a piecewise polynomial in which the coefficients of each polynomial arefixed between knots or 1:Typically cubics are used.
2 Then the coefficients are chosen to match the function andits first and second derivatives at each joint. There remain one free condition at eachend, or two conditions at one end. However, using only starting conditions the splineis unstable. In general withnthdegree polynomials one can obtain continuity up tothen 1 derivative. The most common spline is a Cubic spline . Then the splinefunctiony(x) satisfiesy(4)(x) = 0,y(3)(x) = const,y (x) =a(x) +h. But for a beambetween simple supportsy (x) =M(x)EIwhereM(x) varies linearly. Thus a spline is the curve obtained from a draughtsman 2:Draughtsman s spline3 Equations of Cubic splineLet data be given atx0,x1, xnwith valuesy0,y1, yn.
3 LetS(x) bet the (xj), hj=xj xj 1be moment atjthpoint. Then betweenxj 1andxjS (x) =Mj 1xj xhj+Mjx xj 1hjS (x) = Mj 1(xj x)22hj+Mj(x xj 1)22hj+AS(x) =Mj 1(xj x)36hj+Mj(x xj 1)36hj+Ax+BButS(xj 1) =yj 1, S(xj) = obtainS(x) =Mj 1(xj x)36hj+Mj(x xj 1)36hj+(yj 1 Mj 1h2j6)xj xhj+(yj+Mjh2j6)x xjhj3S (x) = Mj 1(xj x)22hj+Mj(x xj 1)22hj+yj yj 1hj Mj Mj 16hjWe now have continuity ofS (x) andS(x) atxj. We also require continuity ofS (x).NowS (x j) =hj6Mj 1+hj3Mj+yj yj 1hjS (x+j) = hj+13Mj hj+16Mj+1+yj+1 yjhj+1 Equating these gives equations for theMjat every interior node:hj6Mj 1+hj+hj+13Mj+hj+16Mj+1=yj+1 yjhj+1 yj yj 1hjTo complete the system we need 2 additional equations.
4 SettingS (x0) =M0= 0,S (xn) =Mn= 0, corresponds to simple supports at the ends of the beam. Betteraccuracy is obtained ifS (x0) andS (xn) are known. Then from the equation forS (xn) we haveh13M0+h16M1=y1 y0h1 y 0hn6Mn 1+hn3Mn=y n yn yn 1hnIf neitherS (x) norS (x) are known at the ends, one may setS (x) = 0, orM1 M0= 0Mn 1 Mn= 0 Alternatively one may use some linear combination of these end conditions. In any4case one obtains a tridiagonal set of equations which may be written 2 0 12 1 n 12 n 1 n2 M0M1Mn 1Mn = d0d1dn 1dn where at interior points j=hj+1hj+hj+1, j= 1 jdj= 6(yj+1 yj)/hj+1 (yj yj 1)/hjhj+hj+1and 0, n,d0,dndepend on the end conditions.
5 These equations are diagonallydominant, leading to stable equations for first derivativesLetmj=S (xj)ThenS(x) =mj 1(xj x)2(x xj 1)h2j mj(x xj 1)2(xj x)h2j+yj 1(xj x)2[2(x xj 1) +hj]h3j+yj(x xj 1)2[2(xj x) +hj]h3j5S (x) =mj 1(xj x)(2xj 1+xj 3x)h2j mj(x xj 1)(2xj xj 1 3x)h2j+6yj yj 1h3j(xj x)(x xj 1)S (x) = 2mj 12xj+xj 1 3xh2j 2mj2xj 1+xj 3x)h2j+6yj yj 1h3j(xj+xj 1 2x)S (x j) =2mj 1hj+4mjhj 6yj yj 1h2jS (x+j) = 4mjhj+1 2mj+1hj+1+ 6yj+1 yjh2j+1 Equating these gives1hjmj 1+ 2(1hj+1hj+1)mj+1hj+1mj+1= 3yj yj 1h2j+ 3yj+1 yjh2j+1 Then 2 0 12 1 N 12 N 1 N2 m0m1mN 1mN = c0c1cN 1cN where at interior pointscj= 3 jyj yj 1hj+ 3 jyj+1 yjhj+16 The end conditionS = 0 gives 0= 1, c0= 3yj y0hj N= 1, cN= 3yN yN 1hN 14 Minimum curvature property of splinesConsider all functionsf(x) such thatf(xi) =yiThen the Splines (x) withS (x0) =S (xn) = 0 is that functionf(x) which minimize: xnx0f (x)2dx(Ahlberg, p.
6 76)Proof xnx0(f (x) S (x))2dx= xnx0f (x)2dx 2 (f (x) S (x))S (x)dx S (x)2dxThe middle term isn i=1 xixi 1(f (x) S (x))S (x)dxIntegrating by parts it becomesn i=1[(f (x) S (x))S (x)]ii 1 n i=1 xixi 1(f (x) S (x))S (x)dx7S (x) is constant in each segment, and can be taken out of each integral in the xixi 1(f (x) S (x))dx= [f(x) S(x)]ii 1which vanishes becausef(xi) =S(xi) =yi, i= 0,1,..nAlso the contributions to the sum in the first term vanish at every interior node,leaving(f (xn) S (xn))S (xn) (f (x0) S (x0))S (x0)Thus xnx0(f (x) S (x))S (x)dx= 0if eitherS (x) = 0 at each end orf (x) =S (x).
7 Consequently xnx0f (x)2dx xnx0S (x)2dx= xnx0(f (x) S (x))2dx >0unlessf(x) =S(x).85 Errors in spline approximationIf the maximum interval ishthenf(x) S(x) h4f (x) S (x) h3f (x) S (x) h2f (x) S (x) hThis is proved by Ahlberg, Nilson and Walsh, p. 29, provided thatf(4)is study convergence properties of Splines we need an estimate of the norm of theinverse of the matrixBof the equations for the spline . Taking x = max|xi|the induced norm ofBis B = supx6=0 Bx x = maxin j=1|bij|9 With a diagonally dominant matrix we have y = Bx = maxi n j=1bijxj n j=1bijxj where x =|xk|, or y {|bkk| j6=k|bkj|} x mini{|bii| j6=i|bij|} x Thus B 1 = supy6=0 B 1y y [mini{|bii| j6=i|bij|}] 1or for the spline matrix B 1 max[(2 0) 1,(2 n) 1,1]Now let = maxhjand letmax hj <.
8 Then the spline has the following convergence propety as the maximum mesh spacing10 is reduced:Theorem A:(Ahlberg, p. 22)Letf(x) be continuous on [a,b] and let max [| 0|,| n|]<2. Then ifS(x) is a splinefit tof(x) withx0=a,xn=b, then|f(x) S(x)| 0 as if|f(x) f(x )| |x x | ,0 1then|f(x) S(x)|=O( ).Proof:On [xj 1,xj] the spline equations can be arranged asS(x) f(x) =Mj 1(xj x)[(xj x)2 h2j]6hj+Mj(x xj 1)[(x xj 1)2 h2j]6hj+fj+fj 12 f(x) + (fj fj 1)xj+xj 1 2x2hjBy maximizing the coefficients ofMjandMj 1we find that they do not exceedh2j/35/2.
9 LetAijbe the elements ofB 1whereBis the coefficient matrix. ThenMj= 6n 1 i=1 Aji(fi+1 fi)/hi+1 (fi fi 1)/hihi+hi+1+Aj0d0+ let (f, ) be the modulus of continuity off(x) on [a,b] defined as (f, ) = sup|x x |< |f(x) f(x )|Then remembering the condition that hj, we find thath2j (fi+1 fi)/hi+1 (fi fi 1)/hihi+hi+1 2 (f, )Thush2j(|Mj 1+|Mj|) 2 B 1 {6 2 (f, ) + 2(|d0|+|dn|)}and finally|S(x) f(x)| 2352 B 1 {6 2 (f, ) + 2(|d0|+|dn|)}+ (f, )(1 +12)If the function satisfies|f(x) f(x )| (x x ) ,0< 1then (f, ) establishing the required result, in light of the inequality satisfied by B 1 , providedthat <2, n< inC2we can proveTheorem B:(Ahlberg, p.)
10 27)12|f(p)x S(p)(x)|=O( 2 p)whereS(x) satisfies end conditions2M0+M1=6h1(f1 f0h1 f 0)orM0=f :IfBis the matrix of the spline we haveBM=dwhenceB(M d3)=(I B3)dThe right side is13 d0 d1 1(d1 d0) 1(d2 d1) dN dN 1 Now at interior pointsdj6=(fj+1 fj)/hj+1 (fj fj 1)/hjhj+hj+1=f[xj 1,xj,xj+1]=12f ( j), xj 1 j xj+113 Also by the Taylor theoremd06=(f1 f0)/h1 f 0h1=12f ( 0), x0 0 x1 Thus if is the modulus of continuity off ,|f (x) f (x )| (f , ),|x x | then here since j+ j= 1, (I B3)d 3 (f , )Also with the given end conditions B 1 1 so M d3 B 1 (I B3)d 3 (f , )Now sincedj3=f ( j)
