POLYNOMIAL CURVE AND SURFACE FITTING - UNT Digital Library

By Newton's FormulaNew on's FormulaItis usefulis s t i l la n o t h e r way o f w r i t i n g a p o l y n o m i a l .i n t h a t t h e number o f p o i n t s can be i n c r e a s e d w i t h o u trepeating a l lcomputation.Let ( x Q , y 0 ) ,(x , y),.,(*n yn)ben 1 p o i n t s t h r o u g h w h i c h t h e n h degree p o l y n o m i a l Pn( ) i s passed.P ( x ) can be e x p r e s s e d as(1-9)P ( x ) - y ( x - x )P , ( x ) ,n'oo n-1where P - ( x )is a polynomial oft h a t F 3 n ( X Q) yQ nomial P n i ( x ) .degree n - 1 .Itis obvious from (1-9)Thus t h e p r o b l e m reduces t o d e t e r m i n i n g t h e p o l y Now f r o m ( 1 - 9 ) ,P n ! f x ) - Poi2S2zttL(x-x0)Thus t h e f o l l o w i n g must be t r u efori 1, 2,.,n: n 1 X i Pn x i ) Pn x n ) Yi Yn xi xoxi'xow h i c h means t h a t Pn ( x ) passes t h r o u g h t h e p o i n t s o f t h e f o r m xj'Vi Vnx, - x Qand w i l l The v a l u e s y ; - y n a r e c a l l e d " d i v i d e d d i f f e r e n c e s "x. - x Qbe d e n o t e d by [ x . , x Q ] .Similarly,p(1-10)where P p 2 x )n*s3-1(x) [ xi'x]0 X"VPn-2(x)'p o l y n o m i a l of degree n - 2 .Then P . (x ) [x , x ]n— ll uand f o ri 2, 3 ,.,n, P(x)n-2(1-10)Pn 2 (x) fh-1 ( x ) - [ x 1 , x 0 ]x-xxis from

and(t-mtheP„.2( iPn-1 (x; ) - [ x , , x n ][x T , x n ] - [ x i , x n ]xV i V * i, last term in (1-11)is t h e d i v i d e d d i f f e r e n c e of t h e d i v i d e dd i f f e r e n c e and i s denoted by [ x . , , x].By e x p r e s s i n g each succeeding p o l y n o m i a lwhose degree i si n terms o f a p o l y n o m i a lless by one, t h e f o l l o w i n g g e n e r a l e x p r e s s i o n isderived:d-12)P.(x) [ x - ,x, 1 , . . ,x ] ( x - x ; ) P(x),J J 10J n - ( j 1)Jwhere 1 j n - 1 and i - j ,j 1,.,n.By s u b s t i t u t i n g each o f t h e s e e q u a t i o n sformulai n t o ( 1 - 9 ) , Newton'sis(1-13) y ( x ) y0 ( x - x 0 ) [ [ x 1 , x 0 ] ( x - x 1 ) { [ x 2 , x 1 , x 0 ] ( x - x 2 ){.}}].A t a b l e may be c o n s t r u c t e d t o c a l c u l a t e t h e d i v i d e d d i f f e r e n c e s :XV0XI0Yr[Vxo]1[XXExampIe:2' 0,y*3*[ X»tX2'Xl'X0]]2X 3 X[X[X3'Xlfx0]3'X2'X]'X0], By u s i n g t h e data of Example 1, d e t e r m i n e a c u b i c poly-nomial p a s s i n g t h r o u g h t h e data by Newton's 190 1.0000.00000.00000

8Thus,y(x) 0 (x-0){,01667 (x-30)[.00000 (x-60)(.0000)]}.Check:y ( 3 0 ) - 301.01667] .5001.From t h e d e r i v a t i o n o f t h e f o r m u l a , t h e p o i n t s f o r t h e t a b l e don o t n e c e s s a r i l y need t o be i nnumericalorder.Thus a p o i n t may beadded a t t h e bottom o f t h e t a b l e and t h e n e x t h i g h e r o r d e r degree p o l y nomial may be computed f r o m t h e a l t e r e d t a b l e .ExampIe 4 ;tableGiven t h e p o i n t s(2,8),(0,0),(3,27) the f o l l o w i n gis c o n s t r u c t e d .28004519327Thus t h e a p p r o x i m a t i n g p o l y n o m i a lisy(x) 8 (x-2)[4 (x-0)5] 3x2-6x.Now ( 1 , 1 ) may be added t o t h e t a b l e and [ X g , X g ] ,[x3, x2, Xpx„] calculated.[x3,x1,x0],Then t h e v a l u e s f o r d e t e r m i n i n g a c u b i cappear i n t h e t a b Ie:280032741971and1Therefore,y(x) 8 (x-2){4 x [5 (x-3)1 ] }- 8 (x--2) (x 2 h 2x 4) v3

Theorem 1 . 2 .polynomialG i v e n n 1 sample p o i n t s , t h e c o r r e s p o n d i n g n" passing through the pointsProof:is uniquely determined.Assume t h e p o l y n o m i a l y ( x )a p p r o x i m a t i o n f o r t h e n 1 sample p o i n t sand t h e p o l y n o m i a l zCx)method.y(x.)-z(x.)for 0 forboth y ( x )i 0,and z ( x ) .following solutions:is o b t a i n e d by one method o f xQJYQ i s o b t a i n e d by u s i n g t h e same p o i n t sThe d i f f e r e n c e y ( x ) - z C x )1, 2 ,is a f.,is a p o l y n o m i a l(x O),.,is t h e polynomial 0 . x , o r y ( x ) - z ( x )(x ,y),in anothermost a p o l y n o m i a l o f d e g r e e n .n, s i n c e ( x . , y . )Thus y ( x ) - z ( x )(x0,O)sdegree(x , 0 ) . 0.is a s o l u t i o nhaving t h eTherefore y ( x ) - z ( x )Thus y ( x ) z(x).Curve F i t t i n g by S p l i n e F u n c t i o n sThe f o r e g o i n g methods i n d i c a t e ways o f f i t t i n g an n"l*h d e g r e e p o l y n o m i a l t o n 1 d a t a p o i n t s .As n i n c r e a s e s t h e number n o fe q u a t i o n s w h i c h must be s o l v e dxn.is f i td e g r e e men such t h a t each s e t o farebecomes t h e f i r s teach o t h e r , and t h e y u s u a l l yin the f i r s tDeff ni t ion:Given a s e t ofwhere x Q x 1 . , . x , a r e a l[x ,xn]point of t h e nextpointsSpline functionsdo n o t o c c u r .(x.,y.),i 0,function defined for a l li s c a l l e d a s p l i n e f u n c t i o n ofd e n o t e d by P ( x )introduce d i s c o n t i n -d e r i v a t i v e at the j u n c t i o n points.a r e d e f i n e d so t h a t t h e s e d i s c o n t i n u i t i e sval(m 1 ) E x c e p t f o r t h e common p o i n t , t h e c o n s e c u t i v e p o l y n o m i a l sindependent ofuities(m 1) c o n s e c u t i v ew i t h t h e c o r r e s p o n d i n g m" d e g r e e p o l y n o m i a l ; t h ep o i n t of t h e p r e c e d i n g p o l y n o m i a lpolynomial.large magnitude;Thus a u s u a l method i s t o f i t t h e d a t a by means o f a s e t o fpolynomials ofpointsinvolve c o e f f i c i e n t s oflinear1, 2 ,.,nr e a l x i n an i n t e r -d a y e e k f o r t h e p o j n t s andif t h e f o l l o w i n g properties are t r u e :

101)For each ( x . , y . ) ,t ' i2)P(x)P(x.) v . ;iiis of c l a s s Ck 1jP ( x ) has k - 1 c o n t i n u o u s d e r i -vatives;3)P(x)is equal on each i n t e r v a ldegree k o rDef i n i t ion:[x. , x . ] t o a p o l y n o m i a l ofless.Each x .i n (1) above w i l lS p l i n e f u n c t i o n s o f degree one r e s u l tsegments between each p a i r of j o i n t sbe c a l l e d a j o i n t .in f i t t i n g s t r a i g h t[x.,x. 13 ' 0,lineU 2,n-1,w h i l e s p l i n e f u n c t i o n s o f degree two have c o n t i n u o u s f i r s t d e r i v a t i v e s .S p l i n e f u n c t i o n s of odd degree k, where k 2m-1, a r e a l s of o r t h e f o l l o w i n g reason:Q(x. ) y . ,fori 0,importantOf a I I t h e f u n c t i o n s Q(x) e C " ' ,1, 2 ,}., .jsuch t h a tn, t h e s p l i n e f u n c t i o n P ( x ) e Ck - 1I t fIMC-3piI IIOl U l l l i W Mi\ /\ Jt, minimizes t h e i n t e g r a lxnJ[Q'Tx)] dx.T h i s s t a t e m e n t is proven f o r c u b i c s p l i n e f u n c t i o n s i n Theorem 1 . 3 .Cubic s p l i n e f u n c t i o n s a r e examined i n d e t a i lsince they give approx-i m a t e l y t h e shape of a t h i n beam o r " s p l i n e " which i s f o r c e d t o gothrough t h e points ( X j , y . ) .T h i s r e s u l t can be seen by c o n s i d e r i n gt h e i n t e g r a I / [ Q " ( x ) ] 2 d x as an a p p r o x i m a t i o n t o t h e s t r a i n energy o f at h i n beam, which i s / Q " 2 / ( 1 Q' 2 ) 5 / ' 2 d x .Thus t h e a p p r o x i m a t i o n is agood one i f t h e data p o i n t s r e p r e s e n t a smooth n e a r l y h o r i z o n t a l c u r v e .Further,i f t h e c u b i c s p l i n e a p p r o x i m a t i o n i s t o c l o s e l y resemblep a s s i n g a s p l i n e t h r o u g h t h e g i v e n p o i n t s , t h e n c o n d i t i o n s must bes p e c i f i e d a t t h e end p o i n t s . given a t x Q and x n .end p o i n t s .Namely, t h e s l o p e s sQ and sR s h a l lbeT h i s resembles t h e s p l i n e b e i n g clamped a t t h e two

11Theorem 1.3Given ( x - , y . ) ,i 0, 1, 2,n where x ( ) x 1 . . . x n ,l e t P(x) be a s p i i n e f u n c t i o n of degree t h r e e such t h a t P ( x - ) - y j a t eachjoinlx.Let Q(x) be a f u n c t i o n having c o n t i n u o u s f i r s t and secondd e r i v a t i v e s on O o x R ] such t h a t Q ( x . ) P ( x . ) , Q ' ( x 0 ) Q'(xn) - P'(xn).P'(XQ),andThenrx n nJ/ [[Q"Q " ( x ) ] 2 dx J [r P " ( x ) l] 22 di x .(1-14)xProof:f [ Qxv" x00Let 3 ( x ) Q(x) - P ( x ) .( x ) ] 2dx -f [npu(x)]2dxxoo { [ Q " ( x ) ] 2 - 2 [ Q " ( x ) ] [P , ! ( x ) ] f [ p » ( x ) ] 2 } d xx0i n/n 2 J [Q" ( x ) ] [ P1' ( x ) ] dx - 2 J [ P " ( x ) ] 2 d xx xo/[&"(* ]2a* o2 J [P" (x)] f p" (x)] dx*0x0 n1 /»x i 12 / f e " ( x ) ] dx 2 „ / B" (x) P" (x) dxx0i -0 x .i n t e g r a t i n g each t e r m of t h e summation t e r m by p a r t s y i e l d s2xQThe f i r s tdx - p [ P u U ) ] 2 dxx-Xpn-1J [ e , f ( x ) ] 2 dx 2 [ 0 ' ( x)P"(x) - B ' ( x . ) P " ( x . )]i 11 1x0i 0n-1 r x i 1-2 j ? J P " l ( x ) 8 ' ( x ) d x .i 0 xfQsummation t e r m s i m p l i i i e s t o 2 [ g1 (x ) P" ( x p ) - p' (: 0 ) P " ( x 0 ) 3 ,because ' l X j i i ) -8 ' ( x j ) - 0 a t each of t h e i n t e r i o r j o i n t s .summation t e r m i n t e g r a t e s simply s i n c e P I M ( x )is a c o n s t a n t .The secondThus

12[Q"(x)]2dx -2dx J ' " ( x ) ] 2 d xn 2[e'(xn)P»ixn)-e«(x0)P«(x0)] ,1-2 L P"' (i h1 0In t h e s e c o n d t e r m 0 ' ( x n )- ?f C x n ) .P' ( x n )Q(x.)-fJhson J rf , itrx(1-15).R(x) -b.and[P"(x)]2dx.JR ( x ) a Cx-a)mm 0i s e x a c t l y one c u b i c p o l y n o m i a lThis polynoniaIa t end p o i n t s on an i n t e r v a lisf—*-,R' C b) R' ( a ) 1Tb-a)2J' (x-a)3.( b - a ) 3"Since R(x) (x a,mandR 1 ( x ) m-0system of Q(x)-P(x)f3CR(b)-R(a) ) - R ' ( b ) - 2 R ' (a) 1R(a) R' ( a M x - a H L(b-a)2 (b-cTFJ * ( x - a ) 2 Proof and[ P " ( x ) ] 2 d x - [ 3 " ( x ) ] 2 d x 0,[Q n ( x ) ] 2 d xThere1Final iy,which assumes g i v e n v a l u e s R(x and R ' ( x )where a f- Q'(x0)The s u m m a t i o n t e r m i s 0 s i n c e S ( x )p ( x . ) f o r 0 i n .) - g ( x . )] .1 1 B-(X()) 0 since P'(xQ) '[Qn(x)]2dx - [a,b]i n t e r v a l ) [ g (xlinear equations T h em-]resultingi.e.1be w r i t t e n as m a t r i c e s R Q. A,from t h e f o u r given c o n d i t i o n sR('b)R» ( a )!R (b)The dererrr.i narvl of1(b--a)oooR(a)2(b-a) "010c12(b-a)1h tc oo prf rf ki r ii oe nR- rr"'(b-a)a00U13c3(b-aI2 i» r-; v n i r i x 0 is equalXa2a3to the valuemay

13(b-a)(b a)21012(b-a) QjThus Q /-3(b-aP0 since a /unique s o l u t i o n ;(a,R(a)),( b - a )3(b-a)32(b-a)3(b-a 3(b-af 2(b-a)4 -(b-a)4.b, and t h e s y s t e m o fLe ., t h e r e(b-a)20l i n e a r e q u a t i o n s has ai s one c u b i c w h i c hi s d e f i n e d by t h o p o i n t s( b , R ( b ) ) , and t h e d e r i v a t i v e a t each o f a and b.By t h oa p p l i c a t i o n o f C r a m e r ' s R u l e , A may be d e t e r m i n e d t o p r o d u c e t h eresultsin ( 1 - 1 5 ) .i M i L L t L 9 I L L G i v e n anP(x)willi n t e r v a I [ xQ . x n ]w i t h j o i nts x x . . . xn ,be c a l l e d a p i e c e w i s e c u b i c p o l y n o m i a l o v e r [ xo'P(X) Ri-i( x )on heintervalwhere R . 1 ( x )x 1nifis a c u b i cpolynomiaI.Corollaryx.,i - 0,1.5.1,I f y . and s l o p e s s. a r e g i v e n a t each j o i n tn,("here e x i s t s e x a c t l y one p i e c e w i s e c u b i c p o l y -n o m i a l P(x)eC w h i c h s a t i s f i e s P ( x . ) y.and P ' ( X j ) - s . .From Theorem 1.4 t h e r e e x i s t s one p o l y n o m i a l R(x)J' 1passing through y and y and h a v i n g t h e s l o p e a t each o f x .Xj such t h a tThus P ( x ) Sj , and Ri s d e f i n e d on t h e(1-16)Ax2-intervalX l/0,Let x 0 ,xl}butnecessarilynot- w " )if sforand o n l yif.jf o r ,/2 [x, , , x . ] .JJx 2 be such t h a t Axc u b i c p o l y n o m i a l s such t h a t v X j ) Then v " ).and[ x , x ] as0 nP ( x ) - R. . ( x ) x2-1XqwfX]L)/Xj,. Y l,oL e xiv ( x )and v ' ( x j )x Q -f 0 arida n dw ( x )bQw'(Xj)- S1

14( i "*** i / "1p, A x 1 v ' ( x 0 ) 2 ( A x 1 4 A x 0 ) s 1 , ' - A x 0 w ( x 2 ) 31ax Lw(x ? ) - y j A L Y l - v ( x Q ) J j ,Assure v (Xj ) - w"' x ).d e f i n e d i n t h e form o f R(x)R"(x)L e t each of v ( x ) and w(x) bei n Theorem 1 . 4 .F 2(R(b)-R(a))R'(b) R'(a)l 6L(b-a)3" '(b-a )2T J x - a )j"3(R(b)-R(a) ? 2L(b-a)2Furlher,R' (b) 2R' (a) ](b-a) j .-l e t a - x , and b x such t h a tV ' C x , ) r 3 ( v ( x n ?-v(x, )) -«„); -v'fxpHPs, iP i V ' X0 ) -y-i )1 -AX 0 L-ix0" - v» (x 0 ) - 2 s r J .Similarly,l e t t i n g a x and b - x 9 ,2 [" 3(w(x ? ) - y i )-jw " ( x 1 ) - AXj LAXj' w'(x2)-2SlJ .l i then follows t h a t(1-J7)is t r u e .v i d e s t h e proof o f t h e c o n v e r s e ; t h a tRetracing t h i s proof pro-is g i v e n e q u a t i o n ( 1 - 1 7 ) , t h e nv " ( x 1 ) w"(Xj ) .' f A is a r e a l(,"18 laiil(nxn) m a f r i x such t h a t % k lk 1, kf- i1 1,2then A is n o n s i n g u l a r .Assume A 0 ;i . e . , A is s i n g u l a r .Then t h e system ofequat ions'ailX ai2*2 a21Xl a22 X 2 nlxl1n2x2 aa a ainxn 02 „*„ axnil0„ 0

15has a n o n - t r i v i a lthats o l u t i o n (Xj , x 2 , . . . ,x ) . xm m a x { [ x j , x 2 [ , . . . , x }.Let rn be t h e index suchThen t h e m e q u a t i o n may bewr i t t e ni naxmm m " a m i x ii 1, i f mi n ar n i x i f ' 1, i Mlamml f ml lEamixil i EIami I"I x iI - EIam1 I"I x m hI s mmI — 1 a m i ! »which i s a c o n t r a d i c t i o n t o t h e h y p o t h e s i s i n ( 1 - 1 8 ) .Thus j A j f 0,o r A is nons i rigu I a r .Core I I a ry 1 »8.Le*f P(x) be a p i e c e w i s e c u b i c p o l y n o m i a l of c l a s sC1 w i t h j o i n t s x 0 , x1,and s 0 P ' ( X q ) ,Sj .,xn.n- 'suc2,n-1.Let R j j ( x ) and R . ( x )interval [ x j , X j j ] , j 1, 2,mial on each open i n t e r v a l1. .,n-1.and Rj x) P(x) on t h eSince P(x)is a cubic polyno-( x j . . i , X j ) , P " ( x ) e x i s t s f o r each p o i n tAssume t h a tA XjRj-1( Xj-1) f 2 ( A xfAX)-1" ' AXjin t h e( x j ) R"j ( x - ) a t each j o i n t x1 , x 2 , . . . , ] 9 )nbe c u b i c p o I y n o m i a I ( s ) such[xj . ,Xj]From Theorem 1 . 6 , R , f j ( x j ) R J - ' x j )(.,h t h a t P(x)eC2.t h a t R j j (x) P(x) on t h e i n t e r v a l*n-11,Since P t x k C 1 , t h e r e does e x i s t a s e t of v a l u e s s. P ' ( x - ) ,JJProof:interval.i - 0,s n P ' ( x n ) , t h e r e e x i s t s e x a c t l y one s e t o f v a l u e s j KFor g i v e n y? P ( x . ) ,j A xj - t }* R j(R(Xj(xj 1) Yjj Axi f and o n l y i fj - 1 R j ( x j 1}AXrj-15 AX](yj""Rj-1(Xj 1

16where Ax.« ? x . - x . , .vJJw r i t t e n asL e t s . P ' ( x . ) , 1hen e q u a t i o n ( 1 - 1 9 ) may beJJfAy. t 1A x . s . ! 2 ( A x . A x . , ) s . A x . 1 s . , 1 3LAx. -'Ax". Ax? A x . J .J J-1JJ-1 JJ - 1 J 1J-1JJJ-1The c o e f f i c i e n t m a t r i x Q o f t h e unknowns ( s x , s 2 , . . . , s2(Ax l -fAx )A )00 .00AXj0 .0000Ax 2(AX 2 AX 1 )0AXg0000 . . . 2(AxR 2 xn 3 0000 .2 (AXg HA x, ) A c, . . .AxAx2 (Ax1n-lSince 2 A X - A X .Uij A x . A X .sj\J, , by Lemma 1.7 q[ 0 .j 1, 2,.,n 3 .Ax 0 )n-ln-l.Thus t h eusystem of e q u a t i o n s d e r i v e d f r o m ( 1 - 1 9 )s;,isislinearlyindependent andn - 1 , may be d e t e r m i n e d u n i q u e l y .Let 3 . , jJ::1, 2 ,Jn - 1 , where s . R ' ( x . ) , be t h e s e t such t h a tJJf r o m Theorem 1.6 R " . ( x . ) R " . ( x . ) .jjjjNotation:Let S ( x ; x Q , x 1 , . , . , x n ) ,Theorem 1 . 9 .Proof:where x 0 x 1 . . . x n , denote t h eFor each s e t { y 0 , y 1 } . . . ,interval[x0,xn]and with(x; ) y{,y n , s Q , s } of values t h e r esuch t h a ti 0,1,2,.,n; P'(x0) s0;From C o r o ! I a r y 1 . 8 , g i v e n y js n P' (Xj.t) t h e r e e x i s t s one s e t Sj , jP(x) e C2.Thenx ,e x i s t s one P ( x ) e S ( x ; x Q , x 1 , . . . , x )pis t r u e .Thus P ( x ) e C 2 .s e t of a I I c u b i c s p l i n e f u n c t i o n s P ( x ) on t h ej o i n t s XQ , x , . . . ,(1-19)F u r t h e r from C o r o l l a r yp o l y n o m i a l of c l a s s C 1 such t h a t P ( x - ) , s0 P ' ( x Q ) , 1, 2 ,n - 1 such t h a t1 . 5 , t h e r e e x i s t s one p i e c e w i s e

17P(x. )-- y. and P' (x, ) s, . so Thus f o r g i v e n (Xj YjP(x) e S ( x ; x Q , x i , . .an( c r eex i "t'sone).C o r o l l a r y 1.5 and Theorem 1.4 may be used i n a c o m p u t a t i o n a l scheme f o r t h e e v a l u a t i o n of P ( x ) f o r g i v e n ( x j , y j ) , s Q , and s n .Each S ,i 1, 2 ,.n-1,is computed f r o m e q u a t i o n ( 1 - 1 7 ) .s i n c e P ( x ) equals a c u b i c p o l y n o m i a l R j i ( x )[ x , 1 , x , ] and each ofTheni n each i n t e r v a l( X j j , y j j ) , ( x - , y . ) , sj -j and Sje q u a t i o n ( 1 - 1 5 ) may be u t i l i z e d t o compute eachR j j ( x ) ,is known,1 1 , 2 ,. . n .Example 5:Given t h e data p o i n t s ( 0 , - 2 . ) ,arid (4, . 5 ) w i t h s(1,3.),(2,2.),(3,-1.).5 and s . 5 , d e t e r m i n e t h e r e s u l t i n g c u b i cs p l i ne f u n c t i o n .F i r s t equation (1-17)is, t h e«oO—.This y i e l d s s; thatf o l l o w i n g must be d e t e r m i n e d :1s o l u t i o n m a t r i x of t h ei s used t o d e t e r m i n e Sj , s S1.4.1. X0.1.4.11 .51C"2- S 3-r-12.0-5.0 2 . 8 7 5 , s2 - 3 . 6 3 3 , s3 - . 3 4 2 .(1-15), the spline functionFinally,by e q u a t i o nisP ( x ) - - 2 . 0 0 0 4 0.50Gx P(x) -5 . 1 1 7 ( x - 1 ) 2 1 . 2 4 2 ( x - 1 ) 3 , where 1 x 2;!.000 - 3.633(x--2) -i . 3 9 2 ( x - 2 ) 2 2 . 0 2 5 ( x - 2 ) 3 , where 2 x 3;P(x) - -1.000 - 0.542(x 3) 4 . 6 8 3 ( x - 3 ) - 2.842{x- 3) , where 3 x 4,P(x)3.000 2.875(x-1)11 . 1 2 5 X 26.625x, where 0 x 1;

18A computer program f o r t h i s scheme is shown i n Appendix A; g i v e n t h einitialp o i n t s and end s l o p e s t h e program computes t h e r e s u l t i n g P ( x ) .Theorem 1.10.The s e t S { x ; x o x , . . . , x n of s p l i n e f u n c t i o n s w i t hj o i n t s x , x ,Proof:x i s a v e c t o r space over t h e f i e l d o f r e a l numbers.Let each o f P ( x ; x Q , x 1 , . . . , xR ( x ; x , x , . . . , x ) be elements o f S.o 1ndenote P on t h e i n t e r v a lnumbers.Let " ") , Q ( x ; x 0 , X j , . . . , x ) andFurther,'eac[x.3l e t P. E p. .x i-1jto i - j f .andb be r e a li n d i c a t e t h e normal a d d i t i o n o f f u n c t i o n s , namelys p l i ne f u n c t i o n s .i.)(P Q) R p (Q R), s i n c e i n each i n t e r v a l[x.thes p l i n e f u n c t i o n is a c u b i c p o l y n o m i a l , and t h e a s s o c i a t i v e p r o p e r t yholds f o r cubic polynomials.ii.)By t h e same r e a s o n i n g as i n ( i ) ,(F-fQ) (Q P).i I i . ) T h e s e t S has a z e r o Z. where Z 0 on each i n t e r v a l t x . , , x . ] ,i-1' i 'and P Z P.iv.)Each element o f S has an i n v e r s e s i n c eP ( - P ) Z;i . e . , P. (-P.'-1f o r each i n t e r v a lv.)In each i n t e r v a l) p .'-1[x.[x.j 0,.x -! 5 f ( - p .! Jj 0.)x - 0 Z"1'J xj] X-L3. 3Ja ( P . . Q. .) a ( D . . .x X q . . . x J ) -1'-1j o' ' 1 ' Jj 0 , 1 ' J- alo., Y.,x JJ -J a rtq. .aP . . -i- aQ . ,.i-1i-1

19T h e

I. METHODS OF POLYNOMIAL CURVE-FITTING 1 By Use of Linear Equations By the Formula of Lagrange By Newton's Formula Curve Fitting by Spiine Functions I I. METHOD OF LEAST SQUARES 24 Polynomials of Least Squares Least Squares Polynomial Approximation with Restra i nts III. A METHOD OF SURFACE FITTING 37 Bicubic Spline Functions