FITTING•SPLINE FUNCTIONS BY THE METHOD OF' LEAST SQUARES by JOHN TERRY SMITH B.Sc, Acadia University, 1962. B.A., Oxford University, 1965. A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS i n the Department ' of Mathematics We accept this thesis as conforming to the required standard; THE UNIVERSITY OF BRITISH COLUMBIA • August, 1967. In p re sen t i ng t h i s t he s i s in p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r re ference and Study. I f u r t h e r agree that permiss ion fo r ex ten s i ve copying of t h i s t he s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department or by hl'S r e p r e s e n t a t i v e s . It i s understood that copying or p u b l i c a t i o n of t h i s t he s i s f o r f i n a n c i a l gain s h a l l not be a l lowed without my w r i t t e n pe rmi s s i on . Department of The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada i i . ABSTRACT A spline function of degree k with knots 5Q,51,...,5r i s a C k _ 1 function which i s a polynomial of degree at most k i n each of the i n t e r v a l s (-<» ( g ^ ^ ) , . . . , (? r» + 0°) • T n e Gauss-Mar koff Theorem can be used to estimate by l e a s t squares the c o e f f i c i e n t s of a spline function of given degree and knots. Estimating a spline function of known knots without f u l l knowledge of the degree e n t a i l s an extension of the Gauss-Markoff technique. The estimation of the degree when the knots are also unknown has a possible so l u t i o n i n a method employing f i n i t e differences. , The technique of minimizing sums of squared r e s i d u a l s forms the basis f o r a method of estimating the knots of a spline function of given degree. Estimates f o r the knots may also be obtained by a method of successive approximation, provided addit i o n a l information about the spline function i s known. i i i . T A B L E OF CONTENTS P a g e I N T R O D U C T I O N 1 C H A P T E R I 4 1 . T h e G a u s s - M a r k o f f T h e o r e m 4 2. S p l i n e F u n c t i o n s ,/ 6 CH A P TER I I 1 1 1 . A p p l y i n g t h e G a u s s - M a r k o f f T h e o r e m 1 1 2. R a n k o f t h e D e s i g n M a t r i x 1-J5 CHAPTER I I I 22 1 . E s t i m a t i n g t h e D e g r e e : K n o t s K n o w n , 2 2 2. C o n c e r n i n g O r t h o g o n a l P o l y n o m i a l s 24 3. - E s t i m a t i n g t h e D e g r e e : K n o t s U n k n o w n 27 C H A P T E R I V 32 1 . E s t i m a t i n g t h e K n o t s : D e g r e e K n o w n • 32 2. N o n - L i n e a r E s t i m a t i o n b y S u c c e s s i v e A p p r o x i m a t i o n 36 B I B L I O G R A P H Y j 4 0 / i v . ACKNOWLEDGEMENTS I am glad of this opportunity to acknowledge a debt of gratitude to Dr. Stanley W. Nash for suggesting the central problem of the thesis and for giving generously of his time and assistance during the research work on i t . I would like also to extend thanks to Dr. J. R. Hugh Dempster for his advice during the writing and for reading the proofs; to Wayne Welsh who also read the proofs; and to Mr. A. G. Fowler and the University of British Columbia Computing Centre for guidance i n the use of the computer f a c i l i t i e s . My thanks also to the National Research Council for . their financial assistance while the work was i n progress. INTRODUCTION The method of least squares curve f i t t i n g has become a highly developed one for a wide range of functions which are linear in the parameters. Straight line, hyperplane, and polynomial regressions have received special attention and have found wide applications in a l l disciplines which attempt to formulate functional models to explain observed phenomena. The theoretical basis for the general method i s the Gauss-Markoff Theorem, described i n Chapter I, which ensures the existence of and indicates the method for obtaining minimum variance linear unbiased estimates for the parameters of functions which are linear in them. To date, applications to planar curves have been concerned largely with i n f i n i t e l y * differentiable curves f i t t e d to a scatter of data points. Any attempt to f i t a connected sequence of distinct curves to one set of data has had to rely on additional techniques. A type of function developed largely by I. J. Schoenberg in the context of interpolation theory allows the f i t t i n g of segmented polynomial curves to be achieved solely by the Gauss-Markoff Theorem. This function, also introduced in Chapter I, i s called a spline function and consists of a number of distinct polynomial arcs joined together with a specified order of continuous d i f f e r e n t i a b i l i t y at points 2. whose abscissae are called knots. The spline function has a unique representation which i s linear i n i t s coefficients; this allows the Gauss-Markoff Theorem to be applied, i n one operation, to i t s estimation. Spline functions can be cl a s s i f i e d into families by their degree, which i s closely connected with their order of different i a b i l i t y , or by their knots. The coefficients of a spline function of given degree and knots can be estimated as easily as can the coefficients of a polynomial, provided the conditions are known which ensure that the equations to be solved actually have a unique solution. Chapter II j u s t i f i e s the use of the Gauss-Markoff Theorem for spline functions and answers the question concerning the solvability of the equatipns for the estimates. The question then arises as to what procedure to follow when the degree of a spline function i s not specified by the physical situation and so must be estimated. In Chapter III the case of given knots i s considered f i r s t ; the problem i s solved essentially by repeated application of the Gaull-Markoff Theorem un t i l the degree i s found which gives the best f i t . To estimate the degree when no information about the knots i s available, the suggestion i s put forward that one use a method involving f i n i t e differences. The knots of a spline function cannot be estimated directly by the Gauss-Markoff Theorem because the known representations for spline functions are not linear i n the 3. knots. Chapter IV discusses two possible approaches to the problem of knot estimation. The f i r s t , dealing with the case of given degree, evolves out of known techniques for estimat-ing the Join points of segmented curves. The second approach depends on the use of a successive approximation technique for functions which are not linear i n their parameters. Questions which might lead to further research are noted as they arise i n the discussion. A separate numbering system i s used for theorems, definitions and equations i n each chapter. 4. CHAPTER I In this chapter we shall state the Gauss-Markoff Theorem and discuss some well-known applications. The definition of spline function, as i t i s to be used throughout . this paper, w i l l be given, along with some of i t s relevant properties. 1. The Gauss-Markoff Theorem The common uses of least square f i t t i n g techniques deal with straight lines, hyperplanes, polynomial, curves, and, in general, any curves represented by functions which are linear i n the parameters. Each of these examples i s an application of the Gauss-Markoff Theorem [10, pp. 179-182] , 1.1 Theorem (Gauss-Markoff); Let y_ be an nxl column vector of observations and l e t y_ = X£ + £ , where ss i s a random nxl column vector, £ i s a qxl column vector of unknown parameters, X i s an nxq matrix of known weights with rank m no greater than the minimum of n and q . Suppose that z_ has expectation 0 and variance-covariance matrix a I , where a i s an unknown real constant and I i s the nxn identity matrix. Let a be any qxl column vector of real numbers. Then a'|J i s a linear parametric function. If there exists an unbiased estimate of a '>3', that i s , 5 i f there exists an nxl column vector u such that u'y_ has expectation a'£ , then a ' i s a'(X'X)"X'^ i s the linear unbiased estimate of a'£ with minimum variance o 2a'(X'X)"a in the class of a l l linear unbiased estimates of Furthermore, the minimum of the sum of squared residuals S 2(£) = (y_ - *£)'(£ - X£) i s S 2 = v_'(I - X(X'X)~X')y_ which has expectation (n-m)a . We shall omit the proof of the theorem. Note that (x'x)~ denotes a generalized inverse of the matrix X'X . (For any matrix A there exists a generalized inverse A" , not necessarily unique, with the properties: AA"A = A ; and trace (A""A) = rank A . If A i s square and non-singular, then A~ i s unique and A~ = A" 1 , the true inverse* (See [.8, pp. 24-26] for a brief discussion of generalized inverses.) The more common applications of this theorem y i e l d matrices X which are of f u l l rank, i n which case (X'X)~ o (X'X)""1 and the minimum variance linear unbiased estimate of j3 i s given by | - (X 'xj^x'y. , with expectation p , and variance-covariance matrix a 2(X'X)" 1 6. The matrix X appearing i n the Gauss-Markoff Theorem shall be referred to throughout as a design matrix. In f i t t i n g a straight line to a set of data points (x i,y i) , i = l,2,...,n , the vector y_ consists of the observed ordinates, and the matrix X i s a column of n ones followed by a column consisting of the n observed abscissae. The vector f3 has two elements representing the y-intercept and the slope of the li n e , respectively. The example of the hyperplane i s a generalization of the straight line model obtained by adding columns of additional observations to the X matrix and increasing the number of components In the £ vector correspondingly. The situation i s adapted s t i l l further to the case of a polynomial curve f i t by defining the components of the X matrix to be Hi = * i '* i = l*2,...,n; j = 0,1, ...,q. In Chapter II we consider a further application of the Gauss-Markoff Theorem to the f i t t i n g by least squares of a class of functions which, i n some ways, extend and improve upon the f i t t i n g properties of polynomials. These functions, called spline functions, are described i n the following section. 2. Spline Functions It i s i n t u i t i v e l y appealing that a broken-line poly-gonal graph can give a better least squares f i t than can one straight line. For curves of higher degree a similar situation arises. One might speculate, for example, as to whether a sequence of parabolic arcs w i l l better f i t a set of data points than one unbroken polynomial curve of, say, f i f t h degree. These considerations might lead one to the question of whether di f f e r e n t i a b i l i t y conditions can be imposed at th© points where the polynomial segments are joined together. The concept of the spline function allows us to make precise some of the properties of curves formed by piecing together polynomial arcs. The following definition i s one of those used by Schoenberg [16, p. 110]. 2.1 Definition: Let (2.2) • • • < ? . 2 < ? - l < ? 0 < § l < " * < § v < * " be given i n f i n i t e sequence of real numbers such that lim 5 = + o 9 , i f v -» + oo , and l e t k be a given non-negative integer. A spline function Slc(x) of degree k , having knots (2.2), i s a function of the class C k _ 1 for a l l real x such that i n each interval ( ? v ' ? v + 1 ) i - t reduces to a polynomial of degree not exceeding k . In the following discussion we w i l l be largely con-cerned with those spline functions which have only a f i n i t e number of knots. In this case, we w i l l refer to spline functions Sfc(x) , with knots ? 0<? 1<-"<§ r > which reduce to polynomials of degree at most k i n the intervals (-<*,t*0) and (§r,+«) as well as In (§ V*S V + 1) , v = 0,1,...,r-l . It can be readily verified that a spline function of 8. degree zero i s a step function with steps at the knots. Similarly, a spline function of f i r s t degree is a continuous piecewise-linear function whose slope i s discontinuous at the knots. Several equivalent representations of spline func-tions may be found i n the literature; see, for example, [12, 13, 14, 15, 16, 5]. The one most suited to application of the Gauss-Markoff Theorem i s a modification of the notation of Schoenberg [16, p. 352] and Greville [5, p. 54]. k F i r s t , consider the truncated power function x + defined by k i f x > 0 , i f x < 0 . This function may be thought of as a rudimentary spline function of degree k with knot § Q = 0 . I f we apply the different-iation rule, d _ k _ k k-1 dx x+ ~ K x+ k we see that the f i r s t k-1 derivatives of x + are continuous and that the k derivative, ki x_j_ , has a Jump discontinuity of ki at the knot § Q = 0 . Greville [5, p. 54-55] shows that a spline function of degree k with knots §Q<? 1<*"<§ r has the unique representation: (2.3) ' S k(x) = P ( x ) / + / l c (x - § ) k , v=0 where Pfc(x) i s a polynomial of degree at most k . This i s 9. the representation we shall use in Chapter II to apply the Gauss-Markoff Theorem to spline functions. Spline functions behave in some ways l i k e polynomials> but in other ways, their behaviour i s quite different. A summary of some of the properties of spline functions indicates the major similarities and differences. Most of these are mentioned by Schoenberg in [16]. The operations of differentiation and integration respectively decrease and increase the degree of a spline function. The family of spline functions of degree k and knots (2.2) i s closed with respect to forming linear combin-ations of i t s elements with constant coefficients. These properties are shared by the family of polynomials of degree k in fact, a spline function of degree k with no knots i s a polynomial of degree k . Spline functions d i f f e r from polynomials i n their behaviour under the operation of f i n i t e differencing. It i s well known that the f i r s t order difference of a polynomial of degree p i s a polynomial of degree p-1 . The m order difference of a spline function of degree k , however, i s another spline function of degree k , as shown by Schoenberg [12, p. 75]. This fact should be kept i n mind when an attempt i s made to determine the unknown degree of a spline function of least squares f i t by the method of f i n i t e differences described by Kendall and Stuart [7, p. 384], In other words, the linear operation of differencing applied k+1 times to (2.3) results i n a spline function of the form 10. the polynomial part having been "differenced out". Although the problems and demands of interpolation methods are in many ways distinct from those of least squares f i t t i n g , the two techniques share some common ground. The following remark by Greville [4, p, 53] concerning interpolation by spline functions indicates their usefulness in that area and suggests similar advantages for least squares f i t t i n g : By employing polynomials of relatively, low degree, one can often avoid'the marked undulatory behaviour that commonly arises from f i t t i n g a single polynomial exactly to a large number of empirical observations. On the other hand, much greater smoothness is obtained than with the traditional piecewise interpolation procedures which give rise to discontinuities in the f i r s t derivative of the interpolating function. The reader i s referred to Theorems 1 and 2 and Corollary 1 of Schoenberg's paper [16] for a summary of the specific properties of spline functions which give r i s e to their power as interpolating functions. Other kinds of properties may be found i n [12, 1, 13, 14, 15, 16, 5 ] . We now proceed to consider the details of applying the Gauss-Markoff Theorem to spline functions. 11 CHAPTER II The central problem of the thesis concerns f i t t i n g a spline function to a given set of data points. This can be effected by the Gauss-Markoff Theorem provided the condit-ions of the theorem are satisfied. We consider f i r s t the applicability of the theorem and secondly, discuss the rank of the design matrix. 1. Applying the Gauss-Markoff Theorem Let us begin by formulating the problem i n the language of the theorem. Suppose we are given a set {(x^y^)} , i = 0,1,...,n , of points i n the plane represent-ing n+>l pairs of observations. To simplify matters we may assume that X Q < X ^ < « « * < X . Suppose further that a set (SJL) * i = 0,1,...,r , of r+1 fixe'd real numbers i s given, and that x0<?0<?1<---<?r<xn . We hypothesize the following linear model: (1.1) y ± = S k(x ±) + u ± , for i = 0,1,...,n , where Sfc(x) Is a spline function of degree k with knots ?0>5i*.»«>?n > and (u^) , i = 0,1,...,n , i s a sequence of uncorrelated random variables, each with zero expectation and the same variance a c . Using the representation (2,3) i n Chapter I, we may write 12. k r for i = 0,1,...,n . In matrix notation this set of equations may be written i n the form y_ = Pa + Sc + u where y_ i s the (n+l)*l column vector of y-observations; a i s the (k+l)xl column vector of unknown polynomial coefficients; £ i s the (r+l)xl column vector of random variables for which E(u) = 0 and E(uu') = a I , I being the (n+l)x(n+l) identity matrix, and a , an unknown constant; P i s the (n+l)x(k+l) matrix [ P i j = x ^ (J-0,...,k) of successive powers of the x-observations; and S i s the (n+l)x(r+l) matrix [ S ^ = (x i - 5j)+] of spline terms i n the x-observations. Denote by X the (n+l)x(k+r+2) matrix [P|S] , and by £ the (k+r+2)xl column vector [a'jc']' . The observ-ational equations ( l . l ) may now be written as i n Chapter I, Section 1: (1.2) £ = X£ + u . To f i x these ideas i n mind consider the following i l l u s t r a t i o n , where n = J, k = 2, r = 1, x ± = i+1, i = 0,1,...,7, = 3i t and £ 1 = 6 & . Ttye matrix equation for the linear model in this case w i l l be 13. y 0 1 1 1 0 0 'a0 ' u o y l 1 2 4 0 0 a l u l y 2 1 . 3 9 o 0 a 2 U2 y 3 1 4 16 1/4 0 cO + U3 yk 1 5 25 9/V 0 c l u 4 y 5 1 6 36,. 25/4 • 0 U5 y 6 1 7 49 .' 49/4'' 1/4 u 6 y 7 1 8 64.^ 8 1 / 4 / 25/4 U7 • Returning to the general case with observational equations (1.2), l e t us assume for the moment that n i s at least k+r+1 and the rank of X i s k+r+2 . The conditions of the Gauss-Markoff Theorem are satisfied since s k ( x ) i s linear i n the unknown coefficients a^ and C j . Hence, the minimum variance linear unbiased estimate of J3 i s given by | = (X'X)-Vv. , p —1 with variance-covariance matrix a (X'X)~ . If we wish to obtain estimates for the polynomial coefficients and the spline coefficients separately, we can write $ as • « A a P'P P'S ~ 1 P'jr A £ S'P s 's » -I 14. Letting A - I - P f P ' P ) " 1 ? ' and B = S'S - S /P(P'P)" 1P'S = S'AS , and applying the partioned inversion rule, we obtain A a (p'pr^i+p'SB'Vpfp'p)""1] -(p'pr^-p'SB"1 Y m A £ -B^S'PCP'P)" 1 -' B- 1 A ( P' P)-lp'y_ + ( p / p ) - l p / S B - l s / p ( p / p j - l p ' z f (p'pJ-VsB^S'y. -B~1S'P(P'P)"1P'vi + B^S'fc (p/pj-lp/^. _ (p'p)- 1p'SB" 1S /A^ B ' V A ^ Thus far i n the discussion we have assumed the non-singularity of the (k+r+2)x(k+r+2) matrix X'X . In the next section we shall examine the conditions under which this assumption i s ju s t i f i e d and shall show that these conditions do not greatly r e s t r i c t the scope of actual applications. A far more serious limitation of the above procedure, however, i s the fact that i t requires a knowledge of the degree of the spline function to be f i t t e d , as wei^ L as the number and location of the knots. Chapters III and IV attempt to throw l i g h t on 15. these two problems. 2. The Rank of the Design Matrix In this section we discuss the design matrix X which appears In equation (1.2). Let k, r, and n be fixed non-negative Integers and le t xQ<x1<...<xn and ?Q<§ 1<* • • r- be given real numbers. Denote by X(k,r,n) the (n+l)x(k+r+2) matrix > m — 1 x0 x0 • • •• x0 <xO-5o)+ (x0"?l'+ • • • (x0"?r'+ 1 \ 4 • • • x i (xi-?o'+ < xl-5l>£>- • • < xi-5 r)+ V 4 < (xn"?o)+ ( x n - 5 l > + • • • ( x n " 5 r ) + Assuming that n >^ k+r+1 , we shall look for conditions on the x^ and the §j under which X(k,r,n) has f u l l rank k+r+2 . We shall need the following theorem proved by . Schoenberg and Whitney [1>, p. 249]. 2.1, Theorem; Let k be a non-negative integer. I f x0<x1<...<xr , and yQ<y1<"'<yr , then D = (de t U ^ y ^ ] ± = 0 3 l s t _ r \ >0 • i i f and only i f the inequalities j—0 i l 3 <i » 16 . x v - k - l < y v < x v , for v = 0 , 1 , . . . , r ,' hold. The proof w i l l he omitted. Recall that we are dealing with the set df observat-ional equations ( 1 . 1 ) or, equivalently, ( 1 . 2 ) , where now S k(x) = X(k,r,n)£ , or k . k k S k ( x s ) = • ± s 0 a i x s + j ? 0 C ^ X s " § j ^ + , for s = 0 , 1 , . . i • The polynomial p k ( x ) = S a i x s m a v b e written uniquely as where the y v's are k+1 fixed real numbers chosen i n any way such that y0<y1<---<yk<x0 , and y k < ? 0 . r This follows from the well-known fact that given k+1 fixed numbers, we can express any polynomial of degree k uniquely in terms of them. But we may also write k . Pk< x ) = E Y v(x-y )J , for a l l x > y ., V=0 K If we now l e t yk+l = ? 0 * yk+2 = ? 1 > r yk+r+l ? r 3 17. Sk(x) maybe written as k+r+1 k Sk(x) = E q Yv(*-yv)+ > for a l l x > y k , where Y , , = C J f° r v = 0 , 1 , . . . , r . Prom the ascend-ing sequence of given numbers ' X Q J X . ^ , *.. ,xR , arbitrarily choose any subsequence of k+r+2 elements and relabel them as x „ < x „ <* a0 al ak+r+l If we now apply Theorem 2 . 1 , we see that the f i r s t k+1 inequalities in the statement of the theorem are auto-matically satisfied, i.e., y <x„ , for v - o,l,...,k , v and the remaining r+1 inequalities may be expressed as x „ < ? i < x « ° 1 1 °k+2 x a <?r <x„ r 'W+l Hence det [(x - yjO i = 0,l,...,k+r+ll > 0 3=0,1,...,k+r+1 i f and only i f the inequalities c ai+k+l hold. > X a , < ? i < x a j f o r i = 0,l,...,r 18. This implies, however, that the (n+l)x(k+r+2) matrix Y(k,r,n) - [ ( X j - y i ) + ] l a 0 , l , . . . , n j=0,l,...,k+r+l has f u l l rank i f and only i f , for some sequence x„ <x„ <•'...<x„ a 0 a l °k+r+l chosen from x Q,x 1,...,x n , the inequalities x„ <5.,<x„ , for i = 0,1,...,r , °i 1 °i+k+l hold. Note that Y(k,r,n) can be written as the partitioned matrix [Q(k,n)|S(k,r,n)] where Q(k,n) = [x ± - y j ) k ] l s a 0 , 1 > # . . : f n >• J=0,l,...,k and S(k,r,n) - [ ( X j L - S j ) J ] 1 = 0 J L V . , . , N • j=0,l,...,r Finally, we show that there i s a non-singular!.matrix B of order k+r+2 such that 1 Y(k,r,n) = X(k,r,n)B . Having done this, we can immediately conclude that the conditions necessary and sufficient for X(k,r,n) to have f u l l rank are precisely those which ensure the same for Y(k,r,n) . 19. P k ( x ) : or Consider the two ways of writing the polynomial * i P k(x) = E a.x , K 1=0 1 P k(x) = E Y v(x-y ) K v=0 v v = S Y v E ( - D J ( | ) x k - V v=0 , v j = 0 J v = E [ ( - i ) J ( k ) E Y vy^]x k- J j=0 J v=0 v v Equating coefficients for the two forms, we see that Define the (k+l)x(k+l) matrix W to be k a = (-l) k.- J( k) E Y v y ^ d , for j = 0,l,...,k . W = [w, ] where wjv = ( - l ) k " J ( k ) y J j " J Y t = 0,1,. ..,1s. ; v = 0,1,. ..,k . We then see that a = Wx , which implies that , Q(k,n)v. = P(k,n)a = P(k,n)Wy_ , where P(k,n) i s the (n+l)x(k+l) matrix [x^] . Since this expression must be true for arbitrary y_ i t follows that Q(k,n) = P(k,ii)W . Furthermore, we can write 20. [Q(k,n)|S(k,r,n)] = [P(k,n)|S(k,r,n)] W • « 0 r+1 where I r + 1 i a the identity matrix of order r+1 , or, Y(k,r,n) = X(k,r,n)B . It remains only to' show that W , and hence B , i s non-singular. We note f i r s t that W i s row-equivalent to the (k+l)x(k+l) matrix where v i J = y k _ i , i , J = 0,1,...,k , since every element i n the a row of W i s multiplied by the • same non-zero constant (-1) (*) . But detV i s a Vandermpnde determinant of the form detV = ±~fr (y --y ) , s p,q=0 p>q which i s non-zero as long as the y v's are distinct. Hence, V i s non-singular and so i s W . Our results may be summarized i n the following 2.2 Theorem: The matrix X(k,r,n) has f u l l rank i f any only i f , for some sequence x <x <»««<x chosen from °0 a l ak+r+l x 0 , x l , , * , , x n ' t n e * n e < l u a l i * l e s • x a 1 < ? i < x a i + k + 1 , for i = 0,l,...,r , hold. 21 Part of the proof of this theorem i s based on an argument by Schoenberg and Whitney [13, p. 257]. To ensure that the design matrix has f u l l rank, one need only verify that the knots are located correctly among the data abscissae. These restrictions on the knots are not highly stringent, particularly i f the number of data points i s very large compared with k+r+1 ; they merely require that the knots, i n some sense, are not too closely squeezed together at either end of the interval (x,~,x ) . These conditions * u n might well be put into more useful form by characterising the positions of the knots for which the design matrix f a i l s to have f u l l rank; however, an attempt to answer this question w i l l not be made here. f i 22. CHAPTER III Thus far, we have assumed complete knowledge of the degree of the spline function to be f i t t e d and of the number and position of the knots. ' I t i s not unlikely that situations w i l l arise in applications where one or the other or both of these facts i s specified by the physical situation. Such circumstances are by no means assured, however, and so we ' must turn to the problems of estimating the degree and the knots. In this chapter we deal with problems of estimating the unknown degree of a least squares spline function, f i r s t , when f u l l knowledge of the knots i s available, and secondly, when neither the position nor the number of knots i s known. This second situation presents considerable d i f f i c u l t y and has not been completely solved. When both the degree and the knots must be estimated, the greater hope for success i s offered when the degree i s estimated f i r s t . 1.• Estimating the Degree: Knots Known It i s not unrealistic to expect that, i n a whole range of spline f i t t i n g problems, the number and location of the knots w i l l be known, even though the degree may have t a be estimated. One interpretation of this situation i s the case In which different effects on the dependent variable come 23. into play i n different "regimes" of the data, the "cross-over" points being well-known constants. For example, consider density as a function of temperature for some given substance. The three regimes correspond to the solid, l i q u i d , and gaseous states of the substance; the melting point and boiling point may be chosen as knots. Chemists are familiar with cases where different physical mechanisms relate density to termperature i n each of the three states. An analogous situation arises i n Economics. One could argue that the forces which affect the shape of the Gross National Product growth curve i n peacetime;' are different from those which take effect i n wartime. Here again one finds a situation where the knots may be assumed to be known, namely, the times corresponding to the outbreak and termination of war. In light of these considerations we are perhaps jus t i f i e d i n spending some time on a method for estimating the unknown degree of a spline function when complete knowledge of i t s knots i s available. Suppose we are given a set of n+1 data points and r+1 knots and we wish to f i t a spline function of unknown degree k... The method for estimating k i s similar to the technique applied to polynomials [7,pp. 92-95]. Choose a positive integer w to be the highest degree reasonable upon inspection of the data. At worst, w 24. w i l l be one- less than the number of data points.. Denote by R u the sum of squared residuals for the spline function S u(x) , and by D u the quantity R ^ - ^ • T n e variance ratio used to teat the null hypothesis that S u(x) f i t s the data no better than s u - 1 ( x ) i s given by • D u F l , n - u - r - l = R u/(n-u-r-l) * Beginning with u = w , and comparing each successive variance ratio . P 1 n u „ r - i y f o r u = w,w,-l,w-2,..., with the corres-ponding tabled value of the P-distribution with 1 and n-u-r-1 degrees of freedom, we terminate the process when a value i\ of u i s found for which the corresponding spline function S£(x) gives a significantly better f i t than Sic 1 ^ * ' f n e n u m b e r i s then the estimate of the degree. In the process, of course, the required coefficients are estimated as well, producing the desired spline function. i 2. Concerning Orthogonal Polynomials. At this stage one might well ask whether the method of orthogonal polynomials [7>PP» 95-99] may be adapted for use with spline functions. Before attempting to answer this, we should rec a l l that the estimation of the degree of a polynomial i s achieved, essentially, by testing for significance the coefficient of the highest power of the independent variable at each stage. This process i s f a c i l i t a t e d by the trans-formation to orthogonal polynomials which allows the polynomial coefficients to remain unchanged from stage to stage. Another advantage of the method of orthogonal polynomials i s that i t 25 avoids the computational d i f f i c u l t y resulting from the i l l -conditioning of the X'X matrix for polynomials of degree greater than or equal to 6 . The argument for using orthogonal polynomials for spline functions i s not as strong as i t i s for polynomials. In the f i r s t place, the ill-conditioning problem i s not so c r i t i c a l . Secondly, estimation of the degree i s not equivalent to testing the coefficient of the term of highest power at each stage, since each of the spline part coefficients accompanies only terms to the highest power appearing i n the function. If a spline function of degree k and knots 5 0 < V • • < « , . , could be represented equivalently as k ' k k S b.x 1 + £ £ 1=0 1 h=0 j=0 (2.1) S k(x) = V 1 + A c j h ) ( x " so that spline terms of a l l degrees up to k would appear, then we might be j u s t i f i e d i n attempting to use the method of orthogonal polynomials. However, i t can be shown that such an equivalent representation i s not possible. \ 2.2 Theorem; Por a spline function S f c(x)' of order k with knots 5Q<?I<* ' *.<§!."» t n e representation ' K ' \± ./ *• . ,„ . xk S.(x) = E a.x 1 +/ t c,(x - §,)* V • i=0 1 j=0 J - J + 26 is unique i n the sense that i t contains no terms of the form (* - ?r)+ w i t h h = 0,1,...,k-1 ; and the Cj are unique for the given spline function. Proof: Suppose the spline function has an alternative . representation of the form (2.1). In the interval -«»<X<5Q , the spline part does not appear i n either representation and so we must have a^ = b^ for i = 0,1,. . . ,k . In the interval %Q _< x < §^ , which implies that c Q n ^ =0 for h = 0,...,k-l , and c(*> = c . 0 c0 * To perform the induction, suppose that, for a l l s = 0,1,...,v-1 , we have c Q n^= 0 , for h - 0,1,...,k-1 (k) and c g ' - c g . Then i n the interval § v < x < § v + 1 we must have E c (x - s ) k = E E c ( h ) ( x - ? ) h . j=0 J 3 h=0 j=0 J 3 But, taking into account the assumed conditions on the c i n ^ coefficients, we see that c-fx - ? ) k = E c ( n ) ( x - 5 ) n . v v h=0 v v As in the f i r s t step, i t follows that c^n^=0, for h=0,l,...,k-l , and c^ =c^ . This completes the induction step and the proof. The question of the existence of orthogonal sets of spline functions remains an open one.r 27. j . Estimating the Degree: Knots Unknown When neither the location nor the number of knots of a least squares spline function i s known, the representation introduced in Chapter I i s of no use i n estimating the degree. It i s even questionable whether there i s always a spline function of unique degree which gives the best least squares f i t when the knots are allowed to vary a r b i t r a r i l y . A method employing f i n i t e differences has been explored, however, and, for the case bf one particular spline function, the results suggest that a careful refinement of the method might lead to a means of., accurately determining the unknown degree. The method was suggested by a comment by T.N.E. Greville [4, pp. 220-221] concerning the behaviour of actuarial data / under f i n i t e differencing. The a r t i c l e containing the comment deals with interpolation using functions which have since come to be regarded as spline functions.* Greville states that columns of f i n i t e differences of actuarial data often display the following properties: the f i r s t column or two of d i f f e r -ences, while containing marked ir r e g u l a r i t i e s , show a discernible trend; then follows a column with no trend but with an overall ^ tendency toward either positive or negative elements; following this i s a column with seemingly haphazard values, no pattern i n signs, but with about equal numbers of plus and minus signs; succeeding columns display an increasing tendency toward large numerical values and regularly alternating signs. The column * Greville's a r t i c l e was published in 1944. The seminal a r t i c l e on spline functions [12] was written i n 1946 by Schoenberg who drew upon Greville»s work i n generalising and making rigorous the concept of spline function. 28. with no trend and a predominance of plus or "minus signs i s the one which corresponds to the degree of the function to be > fit t e d . In order to test the effectiveness of the procedure recommended by Greville, sets of 50 data points (x 1,y 1) were generated in the following way. The x i's were chosen i n ascending order from the interval [-2,2] i n steps of roughly 0.08 The y^'s were computed using the formula (3.1) y ± = (x ± + 1.82)k + 5.4(X l + 0.l9) k - 13.9(x± - 0.91) + 8 . 5 ^ - 1.57)k + u ± , for i = 1 ,2, . . . ,50 . In other words, y^ represents the sum of the value at x^ of a spline function of degree k with knots at -1.82, -0.19, 0.91* and 1.57 » and a randomly generated value u^ of a normally distributed random variable with mean zero and variance a . An IBM 7044 computer was used to compute a table of eight divided differences for each set of data points. Each d i f f e r -ence column was tested for randomness using a sign test and a • run test (for runs of plus and minus signs), and each was tested for trend. For each column, the percentage excess of the positive numerical values (the difference between the total absolute value of the positive elements and that of the negative elements expressed as a percentage of the total absolute value of the positive elements) was calculated. Difference tables were analysed for each of ; th'e error variances a 2.- 0.10, 0.01, and 0* 001- > for levels of significance for the sign, run and 29.';'; trend tests of 0.05 and 0.01 , and for degrees k = 1,...,5 • To be f a i r to Greville, we should note his further \ comment [4, p. 228] that "as i s usually the case with arm-chair rules of procedure, the difference table cr i t e r i o n ... i s not always clear cut in i t s practical application". A complete summary of the analyses of many difference tables showed a disagreement with Greville's criterion oh two major counts. F i r s t of a l l , for the difference column corresponding to the correct degree, the sign test indicated that there was... no predominance of one sign. Secondly, in the columns following the one associated with the correct degree, a trend was indicated, contradicting the claim that here the values should alternate i n sign. It should be pointed out that the5 data to which Greville referred was of a special nature, consisting of such quantities as mortality rates which imply an underlying sample of thousands of observations. . Further-more, the s t a t i s t i c used, to detect trend for the computer p • p p ' analyses was 6 /s , where 6 i s the mean square successive difference of the elements of a difference column, , m-l .;/••.•' •• • o n m-l m-p and s i s their variance 8 2 = = ^ i ? i ( d i V a ) 2 C r i t i c a l values for- 6 2 / s 2 were found i n [4, p. 25O]. More sensitive, tests for : € $ 6 h d might have yielded results which agree - . - •• •.. • • . . - v . . . . . . • . . . . . . more closely with Greville's criterion. 30. Further study of the computer analyses f a i l e d to explain conclusively the divergence from Greville's criterion or to yield an alternative criterion which would consistently select the correct degree. However, certain consistencies were noted; • these we shall summarize b r i e f l y . The percentage positive excess was close to 100 for the f i r s t column of differences, maintaining almost this level up to the 'degree column', or else the one preceding i t , where i t decreased by at least one-half; i n subsequent columns i t showed a general tendency to oscillate but to increase slowly and irregularly in absolute value. In almost a l l cases examined, the columns including and following the 'degree column' displayed consistent results for the sign, run and trend tests: each column indicated a roughly equal distribute. ion of plus and minus signs, a preponderance of runs almost to the extent of alternating signs, and a significant trend. In the case where the degree, k was taken to be 5 and the error 2 variance a to be 0.001 , these results for the sign, run and trend tests occurred with high frequency for the 'degree column'. . For larger values of the error variance, the post-• degree column' phenomenon was observed to begin at ea r l i e r columns, perhaps indicating an increased contamination, In some sense, of the lower order differences. No claim is.made that these observations support sound conclusions about the b/ehaviour of general least-squares spline functions under f i n i t e differencing. It i s conjectured^ however, that some sort of consistent behaviour does occur which 31. may be i n f l u e n c e d , b u t n o t o b s c u r e d , by v a r i a t i o n s i n t h e degree, the number and l o c a t i o n o f the k n o t s , and, below some upper bound, t h e s i z e o f the e r r o r v a r i a n c e . The r e s u l t s d e s c r i b e d above, i t i s hoped, may r a i s e f u r t h e r q u e s t i o n s about t h e f i n i t e d i f f e r e n c e method f o r d e t e r m i n i n g t h e d e g r e e , and p r o v i d e some h e l p I n f o r m u l a t i o n \ o f a s e n s i t i v e c r i t e r i o n . CHAPTER IV We now turn to the problem of estimating the unknown knots of a spline function. In the literature of the last ten years one can find a growing interest i n the problem. ; of estimating segmented regression curves and their join points. We shall examine some of the techniques developed to date i n an effort to propose a method for estimating the knots of a spline function of known degree; when the degree i s unknown this approach becomes v i r t u a l l y unmanageable. In Section 2 a different sort of procedure i s suggested and an example of i t s application i s discussed. 1. Estimating the Knots: Degree Known There are two cases here which w i l l be discussed separately: f i r s t , the case for which the number of knots i s known, and secondly, the one which requires the number of knots to be estimated, as well as their location. When the number of knots i s known, f u l l use can be made of the spline representation formula (2.3) of Chapter I. However, i t i s clear that this function i s not linear i n the knots, and so the Gauss-Markoff Theorem cannot be used to estimate them. While Quandtf [9], Robison'[11], and Hudson [6] do not have the advantage of the spline representation,,a brie f 33. survey of their techniques may c i a r i f y the specific problems one encounters, and suggest a general procedure. Quandt and Robison both use the maximum likelihood approach with i t s inherent re s t r i c t i o n to normally distributed data. Quandt derives a formula for the maximum likelihood as a function of t , where one regression line i s f i t t e d to the data points (x 1,y 1),...,(x y,y^) , and another line i s f i t t e d to ( xt4.i>yt+i)>"'>( xn , yn) * without requiring the lines to intersect. One then computes their maximum likelihood for a l l possible values of t and selects that value corresponding to the maximum maximorum. Robison recommends a maximum likelihood procedure for estimating the intersection point of two polynomial curves, suggesting an e x p l i c i t formula to be used when the join point i s known to l i e between two given data abscissae. A search; for. the maximum maximorum of the likelihood i s to be carried out, as i n Quandt's procedure, when i t i s not known between which two data abscissae the join point l i e s . Robison imposes no restrictions on the order of d i f f e r e n t i a b i l i t y at the point where the two polynomials intersect. , .- \ . . ' ' An analogous, but more exhaustive, and more general treatment is !given by Hudson, who appeals to least-squares techniques rather than those of maximum likelihood. Limiting his discussion, to the case of one join, he isolates three types of joins: (a) one at /a point i n some unknown open interval ( x ^ x ^ ) where the slope i s discontinuous; 3*. (b) a join at one of the where the slope may or may not be continuous; and (c) one at a point i n (x±>x±+i) where the slope i s continuous. To estimate a join of type (a), Hudson proves i t i s sufficient to minimize separately the two sums of squared residuals for each of the curve segments, impos-ing the continuity condition at the join. Por a join of type (b), one selects the x^ which corresponds to the minimum of the minimized overall sums of squared residuals, the continuity constraint being different for each. A process of successive approximation, not e x p l i c i t l y described, i s recommended for a join of type (c). Hudson also outlines an estimation procedure .' for a join of unknown type involving a selected combination of the three above procedures. Returning to the problem of knot estimation, for spline functions ( s t i l l assuming that the number of knots i s known), we can.see that the spline representation has i t s own r e s t r i c t -ions .on continuity and d i f f e r e n t i a b i l i t y b u i l t into the formula. Hence, Hudson's procedures for joins of type (a) , and type (b) with the slope discontinuous are of no use to us, except for ' , spline functions of degree zero (step functions). Although i t i s desirable to avoid the restriction to normally distributed data imposed by the use of maximum likelihood techniques, the methods of Quandt and Robison are instructive i n that they explore the details of a procedure of estimation which consists, essentially, of optimizing a quantity* under certain re s t r i c t i o n s , by a f i n i t e number of t r i a l s / 35. Let us confine ourselves to the estimation of one knot, the procedure for several knots being much the same i n theory, but computationally more d i f f i c u l t . One distinguishes o between knots which coincide with the data abscissae and those which l i e s t r i c t l y in some interval ( xi> xj. +i) • ' I h e f i r s t type of knot may be handled,with comparative ease, particularly i f one has the help of a computer. In this case one computes a sequence of sums of squared residuals, one for each possible knot x^ in the sequence x Q,...,x n , excluding, of course, the extreme value x n . (Note that a knot at x Q i s equivalent to no knot at a l l , since the spline function over the interval (x Q,x n) w i l l then become a polynomial.) The knot i s then the x^ for which the sum of squared residuals i s a minimum. When several knots of this type are to be estimated, the choice of their possible values w i l l be restricted by the conditions of Theorem 2.2, Chapter II so that the design matrix for the linear model w i l l have f u l l rank. When the unknown knot i s s t r i c t l y contained between;1, two of the adjacent data abscissae, the problem becomes more d i f f i c u l t . Such a knot corresponds to Hudson's join of type (c), for which he recommends:some form of successive approx-imation. Suppose, to begin with, that one knows the interval i n which the knot l i e s . One could calculate values of the sum of squared residuals as a function of the knot 5 , taking equally spaced values of § i n ( x i* x i + 1) •> with A? equal to the maximum permissible error i n the estimate of § . The resulting table of values would readily display the value of 36 5 at which the minimum of the residual sum of squares was achieved. If one does not know between which two data abscissae the knot l i e s , one proceeds i n a manner analogous to the one which le attributed to Robison above. When i t i s not known how many knots one must estimate, the computational d i f f i c u l t i e s expand tremendously; one must compute sums of squared residuals for a l l possible combinations and numbers of knots (up to r = n-k , where n+1 i s the number of data points and k , the degree). Before attempting such an undertaking, one should f i r s t answer the question of whether a better f i t i s achieved by adding additional knots. If the answer i s yes, then one avoids considerable labour by assuming the largest possible number of knots, r = n-k . The question remains open for disucssion. The comments in this section apply to spline functions for which the degree i s known. Such knowledge of the degree w i l l be available i n applications where the physical properties of the model specify either the degree of the polynomials between the knots, or else the order of d i f f e r e n t i a b i l i t y at the joins. 2. Non-Linear Estimation by Successive Approximation As was remarked earlier, the Gauss-Markoff Theorem cannot be applied to the problem of estimating the knots because a spline function i s not linear i n these parameters. The technique of non-linear least-squares f i t t i n g by successive approximation, however, does produce estimates for the 37 coefficients of some types of functions not linear i n the coefficients. The procedure i s described i n [3, pp. 267-269]. The success of this technique i s by no means always assured as we shall see In the case of a particular example. An exploratory test of the method was performed on a known spline function. The function (3«l) of Chapter III was used, as before, to generate sets of f i f t y data points ( x i , y i ) o n t n e i n t e r v a l [-2,2] , this time with no residual error component being added to the y^'s . The successive approximation procedure was applied for degrees k = 1,...,5 , and for three sets of i n i t i a l s estimates of the eight parameters (four coefficients and four knots). The maximum number of iterations was set at 20 and the maximum relative error permitted of the f i n a l estimates was 0.01 . The values of the i n i t i a l estimates are summarized i n the following table.. - true ;[-,'. i n i t i a l values estimates I . . II III 1.0 ' , 1.0 2.0 ' 1.0 1.5 , 6.2 1.0 2.0 -14.7 1.0 '••, 2.5 10.0 • -1.00 -1.72 -1.72 \ 0.00 -0.39 -0.39 1.00 0.71 0.71 1.99 1.47 1.47 coefficients •' 1.0 • • :S::~:./f- 5.4 ' -13.9 -8.5 knots *; -i.82 -0.19 0.91 1.57 The estimation method'failed to yi e l d results for Sets I and II of i n i t i a l estimates. Set III f a i l e d to y i e l d 58.: f i n a l estimates for degrees 2, 4, and 5> out for degrees 1 and 3 the f i n a l estimates for the coefficients and the knots were exact after five and six . Iterations, respectively. In a l l cases where the method fa i l e d , the reason for the failure was the singularity of the matrix A'A /where A represents the matrix of partial derivatives of the function S * W - j i c 3 ( x " 5J>+ with respect to each of the parameters c^,...,c^, f^,...,?^ , evaluated at each of the points x 1,x 2,... ,x^Q . Whenever an Intermediate estimate f j of a knot was obtained which exceeded the maximum x^ , one whole column [ - k C j ( x i -i = 1,2,..,,50 , of the matrix A contained only zeros causing A'A to be singular. At this point the procedure broke down. In case I, the procedure could not get past the f i r s t i teration because i t turned out that none of the x^'s exceeded 1.99 . In case II, i t i s conjectured that the large error i n the i n i t i a l estimates of the coefficients was responsible for an intermediate estimate of some knot exceeding 2.00 . I t i s not at a l l clear why the i n i t i a l estimates III yielded results for some values of the degree and not for others. This example was introduced primarily to establish that the method described can, i n certain limited instances at least, estimate a spline function of known degree with a given number of unknown knots. Besides this, one would l i k e to formulate some questions which would lead to a deeper examination of the effectiveness of the method for general spline functions; 39. an analytic study, i f possible, combined with the methods of computer simulation. Questions that arise immediately concern sensitivity of the method to variations i n the degree, the number and location of th© knots, the maximum deeired relative error i n the f i n a l estimates, the precision of the i n i t i a l estimates, and the variance,of the residual error. Answers to these questions w i l l provide a means of assessing the scope of the method i n practical applications. If the method were discovered to have sufficient f l e x i b i l i t y , one would then be interested in how to obtain i n i t i a l estimates of the parameters with the required degree of accuracy. The further problem of the degree of the spline function being unknown could be solved, for the time being at least, by computing the goodness of f i t for a l l reasonable degrees, and selecting the degree which gives the best f i t . The unknown number of knots situation might be handled i n a similar way using a slightly different criterion i n place of goodness of f i t , because of the variation, at each stage i n the number of parameters being estimated. This non-linear successive approximation method for spline functions, i f i t works, has an added advantage. A very rapid computer subroutine called LQF has been written which accommodates the method. One version of this routine i s available on f i l e at the University of B r i t i s h Columbia Computing Centre. 40. BIBLIOGRAPHY [1] H. B. Curry and I . J . Schoenberg, On Polya Frequency Functions IV: The S p l i n e Functions and T h e i r L i m i t s , B u l l e t i n of the American Mathematical S o c i e t y , 53, (1947), A b s t r a c t 380t, p. 1114. [2] Edwin L. Crow, Frances A. Davis, and Margaret W. Maxf i e l d , . S t a t i s t i c s Manual, Dover P u b l i c a t i o n s , I n c . , New York, I960. [3] N. R. Draper and H. Smith, A p p l i e d Regression A n a l y s i s , John Wiley and Sons, I n c . , New York, 1966. [4] Thomas N. E. G r e v i l l e , The General Theory of O s c u l a t o r y I n t e r p o l a t i o n , the Transac t i o n s of the A c t u a r i a l S o c i e t y of America, 45 (1944), pp. 202-265. [5] Thomas N. E. G r e v i l l e , Numerical Procedures f o r I n t e r - , p o l a t l o n by S p l i n e F u n c t i o n s , The SIAM J o u r n a l of Numerical A n a l y s i s , (B) 1 (1964), pp. 53-68. [6] Derek J . Hudson, F i t t i n g Segmented Curves Whose J o i n P o i n t s Have to be Estimated, J o u r n a l of the American S t a t i s t i c a l A s s o c i a t i o n , 61 (1966), pp. 1097-1129. [7] Maurice G. K e n d a l l and A l a n S t u a r t , The Advanced Theory of S t a t i s t i c s , Volume 3, Charles G r i f f i n and Co. L t d . , . , London, 1966. [8] R. L. P l a c k e t t , P r i n c i p l e s of Regression A n a l y s i s , Oxford: At the Clarendon Pr e s s , i960. [9] R i c h a r d E. Quandt, The E s t i m a t i o n of a L i n e a r R e g r e s s i o n System Obeying Two Separate Regimes, J o u r n a l of the American S t a t i s t i c a l A s s o c i a t i o n , 53 (1958), pp. 873-880. [10] C. R. Rao, L i n e a r S t a t i s t i c a l I n ference and i t s A p p l i c a t i o n s j ; , John Wiley and Son's, I n c . , New York, 1965. 41. [11] D. E. Robison, Estimates for the Points of Intersection of Two Polynomial Regressions, Journal of the • American S t a t i s t i c a l Association, £9 (1964), pp. 214-224. [12] I. J. Schoenberg, Contribution to the Problem of Approx- imation of Equidistant Data by Analytic Functions, Quarterly of Applied Mathematics, 4 (1946), Part A, pp. 45-99. [13] I. J. Schoenberg and Anne Whitney, On Polya Frequency Function III: The Positivity of Translation Determ- inants with an Application to the Interpolation Problem by Spline Curves, Transactions of the American Mathematical Society, J_4 (1953), PP. 246-259-[14] I. J. Schoenberg, Spline Functions, Convex Curves and Mechanical Quadrature, Bulletin of the American Mathematical Society, 64 (1958), pp. 324-357. [15) I. J. Schoenberg, Spline Interpolation and Best Quadrature Formulae, Bulletin of the American Mathematical Society, 70 (1964 , pp. 145-148. [16] I. J. Schoenberg, "On Interpolation by Spline Functions ' a n d i t s Minimal Properties", International Series Numerical Mathematics, 5; On Approximation Theory, Birkhauser Verlag, Basel and Stuttgart, 1964.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Fitting spline functions by the method of least squares
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Fitting spline functions by the method of least squares Smith, John Terry 1967
pdf
Page Metadata
Item Metadata
Title | Fitting spline functions by the method of least squares |
Creator |
Smith, John Terry |
Publisher | University of British Columbia |
Date Issued | 1967 |
Description | A spline function of degree k with knots S₀, S₁,...,Sr is a C[superscript]k-1 function which is a polynomial of degree at most k in each of the intervals (-∞, S₀), (S₀, S₁),…, (Sr,+∞). The Gauss-Markoff Theorem can be used to estimate by least squares the coefficients of a spline function of given degree and knots. Estimating a spline function of known knots without full knowledge of the degree entails an extension of the Gauss-Markoff technique. The estimation of the degree when the knots are also unknown has a possible solution in a method employing finite differences. The technique of minimizing sums of squared residuals forms the basis for a method of estimating the knots of a spline function of given degree. Estimates for the knots may also be obtained by a method of successive approximation, provided additional information about the spline function is known. |
Subject |
Least squares Knot theory |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-11-02 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080581 |
URI | http://hdl.handle.net/2429/38626 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1967_A8 S55.pdf [ 2.64MB ]
- Metadata
- JSON: 831-1.0080581.json
- JSON-LD: 831-1.0080581-ld.json
- RDF/XML (Pretty): 831-1.0080581-rdf.xml
- RDF/JSON: 831-1.0080581-rdf.json
- Turtle: 831-1.0080581-turtle.txt
- N-Triples: 831-1.0080581-rdf-ntriples.txt
- Original Record: 831-1.0080581-source.json
- Full Text
- 831-1.0080581-fulltext.txt
- Citation
- 831-1.0080581.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080581/manifest