Linear Interpolating Splines - USM

1 Jim LambersMAT 772 Fall Semester 2010-11 Lecture 17 NotesThese notes correspond to Sections , , and in the Interpolating SplinesWe have seen that high-degree polynomial interpolation can be problematic. However, if the fittingfunction is only required to have a few continuous derivatives, then one can construct apiecewisepolynomialto fit the data. We now precisely define what we mean by a piecewise (Piecewise polynomial) Let[ , ]be an interval that is divided into subintervals[ , +1],where = 0,.., 1, 0= and = . Apiecewise polynomialis a function ( )definedon[ , ]by ( ) = ( ), 1 , = 1,2,.., ,where, for = 1,2,.., , each function ( )is a polynomial defined on[ 1, ]. Thedegreeof ( )is the maximum degree of each polynomial ( ), for = 1,2,.., .It is essential to note that by this definition, a piecewise polynomial defined on [ , ] is equal tosome polynomial on each subinterval [ 1, ] of [ , ], for = 1,2.

2 , , but a different polynomialmay be used for each first consider one of the simplest types of piecewise polynomials, a piecewise Linear polyno-mial. Let [ , ]. Given the points 0, 1,.., defined as above, thelinear spline L( ) thatinterpolates at these points is defined by L( ) = ( 1) 1 + ( ) 1 1, [ 1, ], = 1,2,.., .The points 0, 1,.., are theknotsof the we study the accuracy of Linear Splines , we introduce some terminology and , we say that a function isabsolutely continououson [ , ] if its derivative is finite almosteverywhere in [ , ] (meaning that it is not finite on at most a subset of [ , ] that hasmeasurezero), is integrable on [ , ], and satisfiesZ ( ) = ( ) ( ), .Any continuously differentiable function is absolutely continuous, but the converse is not example, ( ) = is absolutely continuous on any interval of the form [ , ], butit is not continuously differentiable on such an interval.

3 Next, we define theSobolev spaces ( , ) as follows. The space 1( , ) is the set of allabsolutely continuous functions on [ , ] whose derivatives belong to 2( , ). Then, for >1, ( , ) is the subset of 1( , ) consisting of functions whose ( 1)st derivatives are absolutelycontinuous, and whose th derivatives belong to 2( , ). If we denote by [ , ] the set of allfunctions defined on [ , ] that are times continuously differentiable, then [ , ] is a propersubset of ( , ). For example, any Linear spline belongs to 1( , ), but does not generallybelong to 1[ , ].ExampleThe function ( ) = 3/4belongs to 1(0,1) because ( ) =34 1/4is integrable on[0,1], and alsosquare-integrableon [0,1], sinceZ10 ( ) 2 =Z10916 1/2=98 1/2 10= , / 1[ , ], because ( ) is singular at = 0.

4 Now, if 2[ , ], then by the error in Lagrange interpolation, on each subinterval [ 1, ],for = 1,2,.., , we have ( ) L( ) = ( )2( 1)( ).If we let = 1, then the function ( 1)( ) achieves its maximum absolute valueat = ( 1+ )/2, with a maximum value of 2 /4. If we define = max1 , then we have L 18 2 ,where denotes the -norm over [ , ].One of the most useful properties of the Linear spline L( ) is that among all functions in 1( , ) that interpolate ( ) at the knots 0, 1,.., , it is the flattest . That is, for anyfunction 1( , ) that interpolates at the knots, L 2 prove this, we first write 22= L 22+ 2 L, L + L , applying integration by parts, we obtain L, L =Z [ ( ) L( )] L( ) 2= X =1Z 1[ ( ) L( )] L( ) = X =1([ ( ) L( )] L( ) 1 Z 1[ ( ) L( )] L( ) ).

5 However, Lis a Linear function on each subinterval [ 1, ], so L( ) 0 on each , because both ( ) and L( ) interpolate ( ) at the knots, the bounday terms vanish,and therefore L, L = 0, which establishes the Functions for Linear SplinesLagrange interpolation allows the unique polynomial ( ) of degree that interpolates ( ) atthe knots 0, 1,.., to be expressed in the convenient form ( ) = X =0 ( ) , ( ).A similar form can be obtained for the Linear spline L( ) usinglinear basis Splines , which arepiecewise Linear functions that are equal to one at one of the knots, and equal to zero at all functions, known ashat functionsdue to the shapes of their graphs, are defined as follows: 0( ) = ( 1 )/ 1 0 < 1,0 1 , ( ) = 0 0 < 1,( 1)/ 1 < ,( +1 )/ +1 < +1,0 +1 , = 1,2.

6 , 1, ( ) = 0 0 < 1,( 1)/ 1 .Then, the Linear spline can be expressed as L( ) = X =0 ( ) ( ).3 Cubic SplinesTypically, piecewise polynomials are used to fit smooth functions, and therefore are required tohave a certain number of continuous derivatives. This requirement imposes additional constraintson the piecewise polynomial, and therefore the degree of the polynomials used on each subintervalmust be chosen sufficiently high to ensure that these constraints can be spline InterpolationAsplineis a piecewise polynomial of degree that has 1 continuous derivatives. The mostcommonly used spline is acubic spline , which we now (Cubic spline ) Let ( )be function defined on an interval[ , ], and let 0, 1,.., be + 1distinct points in[ , ], where = 0< 1< < =.

7 Acubic spline , orcubicspline interpolant, is a piecewise polynomial ( )that satisifes the following conditions:1. On each interval[ 1, ], for = 1,.., , ( ) = ( ), where ( )is a cubic ( ) = ( )for = 0,1,.., .3. ( )is twice continuously differentiable on( , ).4. Either of the following boundary conditions are satisfied:(a) ( ) = ( ) = 0, which is calledfreeornatural boundary conditions, and(b) ( ) = ( )and ( ) = ( ), which is calledclamped boundary ( )satisfies free boundary conditions, we say that ( )is anatural spline . The points 0, 1,.., are called thenodesof ( ).Clamped boundary conditions are often preferable because they use more information about ( ),which yields a spline that better approximates ( ) on [ , ]. However, if information about ( )is not available, then free boundary conditions must be used Cubic SplinesSuppose that we wish to construct a cubic spline interpolant ( ) that fits the given data ( 0, 0),( 1, 1).

8 ,( , ), where = 0< 1< < = , and = ( ), for some known function ( ) defined on [ , ]. From the preceding discussion, this spline is a piecewise polynomial of theform ( ) = ( ) = ( 1)3+ ( 1)2+ ( 1) + , = 1,2,.., , 1 .That is, the value of ( ) is obtained by evaluating a different cubic polynomial for each subinterval[ 1, ], for = 1,2,.., .4We now use the definition of a cubic spline to construct a system of equations that must besatisfied by the coefficients , , and for = 1,2,.., . We can then compute these coefficientsby solving the system. Because ( ) must fit the given data, we have = 1, = 1,2,.., .If we define = 1, for = 1,2,.., , and define +1= , then the requirement that ( )is continuous at the interior nodes implies that we must have ( ) = +1( ) for = 1,2.

9 , , because ( ) must fit the given data, we must also have ( ) = ( ) = . Theseconditions lead to the constraints 3 + 2 + + = +1, = 1,2,.., .To ensure that ( ) has a continuous first derivative at the interior nodes, we require that ( ) = +1( ) for = 1, , 1, which imposes the constraints3 2 + 2 + = +1, = 1,2,.., , to enforce continuity of the second derivative at the interior nodes, we require that ( ) = +1( ) for = 1,2,.., 1, which leads to the constraints3 + = +1, = 1,2,.., are 4 coefficients to determine, since there are cubic polynomials, with 4 coefficientseach. However, we have only prescribed 4 2 constraints, so we must specify 2 more in order todetermine a unique solution. If we use free boundary conditions, then these constraints are 0= 0,3 + = the other hand, if we use clamped boundary conditions, then our additional constraints are 0= 0,3 2 + 2 + = ,where = ( ) for = 0,1.

10 , .Having determined our constraints that must be satisfied by ( ), we can set up a systemof Linear equations x=bbased on these constraints, and then solve this system to determinethe coefficients , , , for = 1, , . In the case of free boundary conditions, is an5( + 1) ( + 1) matrix is defined by = 100 0 12( 1+ 2) 22( 2+ 3) 12( 1+ ) 0 001 and the ( + 1)-vectorsxandbarex= 1 +1 ,b= 03 2( 3 2) 3 1( 2 1)..3 ( +1 ) 3 1( 1)0 ,where +1= ( ) the case of clamped boundary conditions, we have = 2 1 10 0 12( 1+ 2) 22( 2+ 3) 12( 1+ ) 0 0 2 andx= 1 +1 ,b= 3 1( 2 1) 3 03 2( 3 2) 3 1( 2 1)..3 ( +1 ) 3 1( 1)3 3 ( +1 ).