THE DISCRETE LEAST SQUARES METHOD FOR 2m-th ORDER ELLIPTIC BOUNDARY-VALUE PROBLEMS by PETER HENRY SAMMON B.Sc., Uni v e r s i t y of B r i t i s h Columbia, 1973 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of MATHEMATICS and the INSTITUTE OF APPLIED MATHEMATICS AND STATISTICS We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA December, 1974 In presenting th is thes is in pa r t i a l fu l f i lment of the requirements for an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary shal l make it f ree ly ava i l ab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho la r ly purposes may be granted by the Head of my Department or by h is representat ives . It is understood that copying or pub l i ca t ion of th is thes is fo r f inanc ia l gain shal1 not be allowed without my wri t ten permission. Department of M a t h e m a t I CS The Univers i ty of B r i t i s h Columbia Vancouver 8, Canada Date D e c e m b e r 6, 19 74 - i i -Abstract Many p o s i t i v e r e s u l t s are known for the Least Squares method of numerically computing an approximant s o l u t i o n f o r a 2m-th order e l l i p t i c boundary value problem on a r e a l i n t e r v a l . However due to i n t e g r a l s that appear i n the l i n e a r system that must be solved to f i n d the approximant s o l u t i o n , the Least Squares method i s computationally unattractive. Thus one i s led to consider other, more p r a c t i c a l , methods. In t h i s t h e s i s , such a method i s examined. It i s f i r s t shown that minimizing a quantity i n v o l v i n g d i s c r e t e quadrature sums to f i n d an approxi-mation to the so l u t i o n leads to a l i n e a r system i n which quadrature sums, not i n t e g r a l s , appear. The approximation generated by t h i s method, known as the Discrete Least Squares method, i s thus e a s i l y computed. Error estimates are then proven f or the Discrete method. A c e r t a i n polynomial i n t e r p o l a t e i s f i r s t constructed and then using Sobolev space theory and known estimates from the related Least Squares method, the desired estimates are obtained. These estimates are l i k e the usual Least Squares estimates although more continuity of the c o e f f i c i e n t s of the problem i s required i n the f i n a l stages. Comparisons are then drawn between the Discrete method and the Col l o c a t i o n method. It i s noted that both methods o f f e r easy computability and shown why the Discrete method can generate a smoother approximation i n most s i t u a t i o n s . Results of numerical computations are then provided which support the theory and a discussion of what problems the theory applies to i s also given. - i i i -Table of Contents Page Abstract i i Table of Contents i i i L i s t of Tables v Acknowledgement v i Chapter 0 : Some Motivation 1 Chapter 1 : The Preliminaries 7 1.1 Sobolev Spaces 7 1.2 Piecewise Polynomial Spaces 11 1.3 R e s t r i c t i o n s on L 14 Chapter 2 : The Least Squares Methods : Continuous and Discrete 17 2.1 Introduction 17 2.2 The Continuous Method 17 2.3 Further Error Bounds f o r the Continuous Method 22 2.4 A Discussion 27 2.5 An Interpolate 28 2.6 Quadrature Sums 35 2.7 Preliminary Error Bounds Needed for the Discrete Method 38 - iv -Table of Contents (Contd.) Page 2.8 The Discrete Method 46 2.9 Further Error Bounds for the Discrete Method 56 2.10 Some Extensions 62 Chapter 3 : Practical Considerations 65 3.1 Properties of L 65 3.2 A Comparison 67 3.3 Discrete Least Squares Computations 68 Bibliography 75 - V -L i s t of Tables Page Table I : Results f or Equations (3.3.1) - (3.3.3) 73 Table II : Results f or Equations (3.3.4) - (3.3.6) 74 - v i -Acknowledgement I wish to express my deep appreciation to my advisor, Dr. James M. Varah, for his continuing encouragement and interest in my studies and also for his assistance with the problem discussed in this thesis. I would also l i k e to thank Dr. A.T. Bui for his help and suggestions, Mrs. Y.S. Chdo for her excellent typing and my family and friends, especially my parents Kathleen and Andrew Sammon and Christine Hellwig, for their interest and patience throughout the writing of this work. The assistance of the University of British Columbia and the National Research Council i s also gratefully acknowledged. - 1 -Chapter 0 Some Motivation Many results,, are known for the Least Squares Method of numerically computing an approximate s o l u t i o n f o r a 2m—th order e l l i p t i c boundary value problem. However for reasons to be noted l a t e r , t h i s method i s computation-a l l y u n a ttractive, i f not impossible, i n actual s i t u a t i o n s . In t h i s t hesis we w i l l examine a more p r a c t i c a l method, commonly known as the Discrete Least Squares Method. (To avoid misunderstandings, we w i l l always use the term Continuous Least Squares f or the usual approach). To show how the Discrete method d i f f e r s from the usual Continuous method and how the Discrete method compares with the we l l known C o l l o c a t i o n Method we w i l l consider these three methods as applied to the following d i f f e r e n t i a l equation problem. Consider m (0.1.1) Lu(x) = I (-l) rD r(a'(x)D ru(x)) = f(x) ; x e [a, b] , r=0 r Boundary Conditions : D ru(a) = D ru(b) = 0 for 0 <_ r <_ m-1 , where D denotes d i f f e r e n t i a t i o n . (The primes on the c o e f f i c i e n t s ^ a j ^ are used f or l a t e r n o t a t i o n a l reasons). We assume a l l the c o e f f i c i e n t func-tions are su i t a b l y smooth and also that a\(x) > 0 for x e [a, b ] , 1 <_ j <_ m. Thus the operator L i s uniformly strongly e l l i p t i c on [a, b ] . 2 Let S q be a f i n i t e dimensional subspace of L (a, b) that con-s i s t s of su i t a b l y smooth functions which s a t i s f y the boundary conditions - 2 -stated i n (0.1.1). We w i l l specify a pa r t i c u l a r choice l a t e r . Given t h i s subspace each of the three methods finds an approximation i n S q , denoted by w, to the solution u of equation (0.1.1). I f ^ e ^ i = i ^ s a basis for S , then equivalently, each of the three methods finds a vector q d = (d, , d ) so that the corresponding function w = 7 d.e. i n S — 1 q ^f; i i o i s "close" to u i n some norm. We choose to use the usual L^-norm on (a, b) (denoted by | |» | | ^ ) . To be p r a c t i c a l , the method must be able to define d_ i n some ea s i l y computed way. The Continuous method determines w as the unique function i n S Q that minimizes ||Lv - f | J ^ over a l l functions v e S q . This process would appear to give a reasonable approximation to u. In fact i t w i l l be shown that jl i s easily found as the solution to the li n e a r system r rb (0.1.2) I r=l Le • Le r s a d r •b f .Le a for 1 < s < q . But as mentioned before, actual computations are d i f f i c u l t or impossible because of the integrals i n th i s system. To avoid integrals we need some form of in t e g r a l approximation. Given a p a r t i t i o n a = x^ < x^ < x 2 < ... < x N < = b of [a, b] and a function g e C[a, b] we can approximate N K g(x) dx by I I w g(z ) i - O J - 1 1 J 1 J where K i s a positive integer, the {w„} are certain positive numbers K called weights and the {z..}. n are certain points i n (x., x..,), for i j j = l i ' i + l " 0 <_ i <_ N, called the Gauss points. We w i l l discuss this approximation i n more detail in Section 2.6. Given these integral approximations we can now describe the Discrete method. The Discrete method determines w as the unique function in S that minimizes o N K I I w i=0 j=l (Lv - f ) ( z i j ) J over a l l functions v e S . Thus the Discrete method i s equivalent to the o , Continuous method with approximate integration replacing integration. We w i l l also show later that d_ i s easily found as the solution to (0.1.3) q C N K I I I -v.. (Le -Le ) (z. .) r=lii=0 j-1 1 J r S 1 J d = r r N K I I w..(f-Le )(z. .) i=0 A 1 3 s i j -for 1 < s < q , where we note that (0.1.3) i s the same as (0.1.2) with the appropriate integral approximations. Thus calculating <i for the Discrete method from (0.1.3) becomes feasible as each term of the system only involves a f i n i t e sum of function values. The motivation for the Collocation method i s different from the norm minimizing concepts used above in the Continuous method. For the Collocation method in i t s most general form we pick q distinct points e {y^}?_^ in [a, b] and require that w satisfy (0.1.4) Lw(y.) = I Le r(y.) d r r=l f(y ±) for 1 < i <^ q , which gives an easily computed system for d_ . However i f good approximation - 4 -qualities are to be obtained, the choice of the points must be made carefully. To further discuss the methods we must specialize our choice for the approximation space S q . We choose to use a space of piecewise polyno-mials of odd degree which i s known to have good approximation qualities. More precisely given two integers n, z where n - l < ^ z < ^ 2 n - 2 and a partition of [a, b] as before, we let S q be the collection of a l l func-tions e e C [a, b] that are polynomials of degree 2n - 1 on (x^, x^+^) for 0 <_ i _< N and that satisfy the boundary conditions. In this case q = (2n - 1 - z)N + (2n - 2m). We w i l l choose z >^ 2m - 1 also so that 2 Le E L (a, b) for e e S Q . If we order the points {z..} and {w..} of the Discrete method lexicographically and c a l l them ^ s j ^ a n c^ respectively then (0.1.4) becomes (0.1.5) STDSd = STDf where S = [Le ( s . ) ] ^ ^ + 1 ^ q . i s a K(N+1) x q matrix, r 3 3=1 r=l H ' D = diag(t 1, t R ( N + 1 ) ) and f = [f ( S j) . Now (0.1.5) i s precisely the system, known as the system of normal equations, that must be solved to find the unique vector d_ that minimizes | | D 5 ( S V - f ) | | over a l l v = (v^, v ) in q-dimensional Euclidean space. Here ||*|| denotes the K(N+l)-dimensional Euclidean norm. We note that K = 2n - 2m w i l l be our f i n a l choice for K so n > m i s required. Thus both w and d are found as solutions to least squares minimization problems under the Discrete least squares method. If, on the other hand, we have q = K(N + 1) (which i s equivalent to z = 2m - 1) and pick the points f° r t n e Collocation method as the Gauss points, that i s ^±^<±=± = ^ si^j [ i i + " ^ ' w e Set good approximation properties (Russell and Varah [10]). In this case the system (0.1.4) for d_ becomes Sd_ = f_ . Thus the system (0.1.5) which determines the Discrete method and also finds the vector d_ that minimizes ||D2(Sv - f ) | | over a l l v = (v^, v ) may be viewed as an extension of the Collocation method, which describes the particular case when S i s square and Sd_ = f_ i s directly solvable. Essentially under the Discrete method we are collocating k at more points than unknowns, scaling the equations by D and looking for d as a least squares solution i n K(N+1)-dimensional Euclidean space. We have seen that both the Discrete and Collocation methods are practical for computations. However the Discrete method has the advantage that 2n - 2 :> z >_ 2m - 1 i s allowed. Since z = 2m - 1 is required for Collocation, we can find an approximation w by the Discrete method that has more continuity than that available from the more restrictive Collocation method. This i n fact allows a more convenient basis to be chosen when T T z = 2n - 2 that allows the formation and solution of S DSd_ = S Df_ for the Discrete method to be about as much work as solving Sd_ = f_ for the Collo-cation method, where a more restricted continuity of basis i s required. - 6 -Thus because of the computational competitiveness of the Discrete method when z = 2n - 2 and the higher continuity of the approximation obtained i t seems worthwhile to show that the Discrete method has approxima-tion properties similar to those known for the Collocation method. This w i l l be the objective of this thesis. We begin by stating known results, from Sobolev space and piecewise polynomial space theory in Chapter 1, as well as our assumptions on the differential equation problem. In Chapter 2 we define formally the Contin-uous and Discrete methods. We prove known results for the Continuous method and also examine a certain type of function approximation that w i l l be necessary for further results. We then examine integral approximations and prove the convergence results for the Discrete method. Finally in Chapter 3 we examine our hypotheses from a practical point of view, compare the Collocation method and the Discrete method again and give some numerical results. - 7 Chapter 1 The Preliminaries 1.1 Sobolev Spaces We wish to find an approximation to the solution u of the linear self adjoint differential equation m Lu = I (-l) rD r(a' DSu) = f , n rs ' r,s=0 Boundary Conditions : D u(a) = D u(b) = 0 for 0 <_ r <_ m - 1 , on the interval (a, b), where a' = a' for 0 < r, s < m . Note that rs sr — — we are allowing a slightly more general operator than the operator of equation (0.1.1). We begin the formal description of our methods by examining some Sobolev space theory (see Agmon [2]). Definition (1.1.1) : (1) Let C r(c, d) de.note. the, 6pa.ce. o{, r tw2J> continuoualy dX-i^eAeyvUxiblt ^anctiom,- on (c, d) . oo (2) Let C°°(c, d) = n C j(c, d) . (3) let supp g(x) = cto&uAe. 0^ {x : g(x) ^ 0} (4) LU C (c, d) = {g e C°°(c, d) : supp g C (c, d) } . o r rd (5) LeX C* r(c, d) = {g e C r(c, d) : \ s=0 J (D Sg) 2 < » } . - 8 -(6) LU ||.|| = ( I f ( D s ( - ) ) 2 r,(.c,a> ^ g = Q ^ j 1/2 ( 7 ) Lzt thz uiual L p 4paces be dznotzd by L p ( c , d) <)0A p >^ 1. 'r,(c,d) Similar d e f i n i t i o n s hold for C [c, d] and C [c, d]. Clearly i s a norm on C* r(c, d) associated with the inner product r,(c,d) d • r I D S(-)D S(-) . c s=0 D e f i n i t i o n ( 1 . 1 . 2 ) : Lzt H r(c, d) = {complztiovi oft C* r(c, d) undeA 'r,(c,d) ). Thus H (c, d) i s a Hilbert space. 2 2 We say g e L (c, d) has weak L -derivatives up to order r i f 2 there i s a function g g e L (c, d) for 0 <_ s <^ r so that e g s = ( - 1 ) S g DSe for e e C 0(c, d) r 2 D e f i n i t i o n ( 1 . 1 . 3 ) : L&t W (c, d) = { g e L (c, d) : g htU uizak 2 L -doAA-vautivu up to OfldQA r } . We w i l l ignore i n t e r v a l designations i f the i n t e r v a l involved i s (a, b). Agmon [ 2 ; p. 1 1 ] shows that W r(c, d) = H r(c, d) for r >_ 0 . We note that W°(c, d) = H°(c, d) = L 2 ( c , d). We w i l l now state a form of the Sobolev imbedding theorem found i n Agmon [ 2 ; p. 3 2 ] . - 9 -Theorem (1.1.4) : 1{ g e W r(c, d) {oh. r > I -then £neAe -C6 a r - l g' E C [c, d] 60 that g = g 1 a . e . We w i l l i d e n t i f y g with g' i n the usual way. We also have a stronger r e s u l t . Theorem (1.1.5) : l{ g e W r(c, d) {oh. r > 1 -then D r _ 1 g -C6 absolutely continuous on [c, d] . Proof : See Berezanskii 1 [ 4 ; p. 25] . /// r r 2 Thus g e W (c, d) implies that D g e L (c, d). Hence Theorem (1.1.6) : We have, g e w r(c, d) {on. r > 1 and on£(/ ^ we have r 2 r—1 D g e L (c, d) and D g AJ> absolutely continuous on [c, d] {on. r >_ 1. We w i l l also need : r 0 0 D e f i n i t i o n (1.1.7) : Le t H Q ( C , d) = ( completion o{ C Q ( c , d) undeh. l l -Hr . (cd) ' • Note that H^(c, d) i s a d o s e d subspace of H r(c, d). We also have the (non-optimal) r e s u l t : Theorem (1.1.8) : ( 1 ) 1{ g e H^(c, d) {on. r > 1 then g e H r(c, d) and D Sg(c) = D sg(d) = 0 {oh. 0 <s ± r-l . (2) J{ g e C r [ c , d] and D sg(c) = D sg(d) = 0 {oh. 0 < s < r - l then g e H^(c, d) . - 10 -Proof : See Berezanskii [4; p. 21] and Agmon [2; p. 131] . /// Tr. The spaces W"(c, d) are called Sobolev spaces and they w i l l provide the framework for much of the remainder of our analysis. We note that due to Theorem (1.1.6) we have Taylor expansions i n Sobolev spaces. Theorem (1.1.9) : 1{ g e Wr(c, d), x, y e [c, d] and 1 ±s < r then 8<*> = I (x " y ) j + D Sg(t)(x - t ) 5 " 1 dt. j=0 Proof : See Hewitt and Stromberg [8; p. 287]. /// We now state a result that comes from the theory of interpolation between Banach spaces. We let L(B^, B2) denote the space of linear opera-tors and let B(B^, B^) denote the space of bounded linear operators from a normed linear space B^ to a normed linear space • (For a proof of the following and some discussion see Adams [1; pp 334-339]). We have : Theorem (1.1.10) : 1{ T e B(W°(c, d) , Y) A B(Wr(c, d) , Y) {on. Some Banach space Y and thene an,e constants M , so that l|Tg|| Y 1 M olls l l 0,(c,d) i o f l § e w°(c, d) l l T s l l y 1 MlHg|lr,(c,d) g e Wr(c, d) , then given 0 < e < 1 so that er u> an tntegen. we have that then.e a constant C so that • (1) T e 8(W 9 r(c, d), Y) - 11 -(2) ||Tg||Y < CMj- 9Mj||g|| 6 r ) ( C ) d ) ioJL g e W 9 r ( c , d ) . 1.2 Piecewise Polynomial Spaces We w i l l now take a closer look at the space of functions from which our approximations w i l l come. This section w i l l follow the definitions and results from Schultz's paper [11]. Definition (1.2.1) : (1) fan. zach N >_ 0 lU P N(a, b) dznotz the. i>U o{) aJUL paxtitioni, A o{> tkz ^onm A : a = x Q < X]_ < x 2 < ... < ^ < x N + 1 = b . LU P(a, b) = U P (a, b) N=0 (2) Fo*. A e P(a, b) and n, z > 1 uineAZ n-1 < z < 2n-2 we LU S(2n-1, A, z) = {e(x) e C z[a, b] : e AJ> a polynomial, ol degree 2n-l on ( x ^ x i + 1 ) ioh. 0 <_ i <_ N} . We now f i x our attention on some S(2n-1, A, z) which we denote by S, which satisfies n > m and z >_ 2m - 1 . (Note that i f z = 2n - 2 then z > 2m - 2 so z >_ 2m - 1) . The reasons for these restrictions w i l l appear later. Given a function g we want to consider an interpolate, denoted - 12 -by Ig, in S ; that is Ig i s a function i n S whose derivative values at certain prescribed points equal the corresponding values of the derivatives of g . Thus we define : Definition (1.2.2) : Let I : C n - 1 [ a , b] —> S be given by Ton, g e C n "*"[a, b], Ig Is the unique {unction In S that SatU{leS : DrIg(a) = Drg(a) {on. 0 < r £ n-1, DrIg(b) = Drg(b) {on, 0 <_ r .<_ n-1 and D rIg(x i) = D rg(x ±) {on. 1 < i <N, 0 < r < 2n-2-z . We need one other approximation space. Definition (1.2.3) : Let S q be the Subspace o{ s given by S q = {e e S : Dre(a) = Dre(b) = 0 {oh. 0 <_ r <_ m-1 } . Since S C m[a, b], this definition makes sense. Note that i f g e C n ''"[a, b] satisfies the conditions Drg(a) = Drg(b) = 0 for 0 <_ r < m-1, then Ig e S . o Definition (1.2.4) : let h = max { x ± + 1 - x ± : 0 £ i <_ N } , h' = min { x ± + 1 - x ± : 0 < i < N } and {oh. g e Wr(x±, x ± + 1 ) {oh, 0 <_ i < N let • r N r r x i + l 0 \l/2 l | g | l r A = 1 1 (D S8) 2 ' <• i=0 s=0 J x ± > We assume h' <_ h <_ 1 although this is not crucial. Note that ||:*||r ^ i s l i k e the usual Sobolev norm. In fact for g^, e.Wr(x^, x i +^) - 13 -for 0 < i -< N we have that < M 8 i + 8 2 Mr , A > N r r x i + l - ( l l « 1 l l r > 4 ) 2 + ( l l « 2 l l r , / + 2 I I x=U s=0 < ( | | g l l l r , A + l | g 2 l l r > A ) 2 • D S g l D Sg 2 We let a be a bound on the mesh ratio ; that i s 1 _< (h/h1) < a . In what follows we w i l l use the symbol C to denote a generic constant that depends on m, n, z, a, b, the mesh ratio bound a and the coefficient functions of L . The coefficient C i s hardly ever the same in two different places. From Schultz [11; p. 510, p. 512] we have : Theorem (1.2.5) : T{ g e W2n tkzn M D r ( g - I g ) M 0 1 Ch 2 n- r||D 2 ng|| 0 i0K 0 < r < n . Theorem (1.2.6) : !{, g e Wp {on. n < p <_ 2n, 4n-2p-l ± z <_ 2n-2 thzn 1=0 Jx± 1/2 (D r(g - I g ) ) 2 ] < Ch ( p~ r )||D P g| | ioK n < r < p ' 0 From these two results we get the immediate corollary ,2n Theorem (1.2.7) : l{ g e W tkm {on. 0 < r < 2n m nave. M s - i g | | r > 4 i ch2»-||g||2n wkznz wz may fizplacz \\-\\ . by | | • | | l{ 0 < r < 2m TO • A 1C "~— - 14 -Proof : We have the following with obvious simplifications i f r £ n .2 g - I g | , r > A n r N v S , . T _ N I I 2 x I l | D S ( g - I g ) | | ^ + I I =0 s=n+l i=0 J x ± i+1 (DS(g - I g ) ) 2 < I C ( S ) h 2 ( 2 n - s ) | | D 2 n g | | 2 + I C(s)h 2 ( 2 n- s )||D 2 ng|| 2 s=0 U ' s=n+l < d l . I l L l h 2 < 2°" S ) i ch2<2-"||gi|^ s=0 where we have used Theorems (1.2.5) and (1.2.6) and h <_ 1 . /// 2 Clearly S q i s a f i n i t e dimensional subspace of L . Thus we can choose a basis {e^} for 1 £ i <_ q of S q . The particular choice of basis i s not important for the analysis as i t does not enter into the determination of any estimates. However the choice i s important for practical computations, as noted in Chapter 0 . Note S q C H™ n W2m by Theorems (1.1.6) and (1.1.8). 1.3 Restrictions on L We now have enough background to state a l l our assumptions on the operator L . We w i l l assume without further mention, throughout this section and throughout Chapter 2, that : / I N i r,max(4n-4m,2m)+rr c n ^ (1) a' e C [a, b] for 0 <_r, s <_m . - 15 -(2) given g e WP for 0 <_ p < max(4n-4m, 2m) there exist s an TTm ~ rTp+2m , p unique v e H Q n w so that Lv = g i n W and |v|| p + 2 m £ C | | g | | p C||Lv| We w i l l discuss i n Section 3.1 what kind of operators have these properties. We note that given g e W we have by Leibniz's rule Lg = r,s=0 p=0 1=0 where we define m I r=0 ^ 0<p,s<m p+s=j I ( - D r o ^ rs 0 i f p < r 1 i f p > r for 1 < j < 2m. Note a e c m a x ( 4 n - 4 m ' 2 m ) [ a , b] for 1 < j < 2m by our standing assumption (1). We now show the general result '• T h e°rem (1.3.1) : 1{ g e W P + 2 m(c, d), & e C P[a, b] {ofi 1 < j < 2m and (c, d) c (a, b) thm Lg e Wp(c, d) and l | L g | lP,(c,d) <- CH^llp +2m,(c, d) Proof ' Using Leibniz's rule and the continuity of the functions {a } we know Lg e WP(c, d) by Theorem (1.1.6) and l L g | |P,(c,d) - I r=0 d r r 2m 2 Dr I a DSg (-s=0 J - 16 -r=0 2m r • s=0 t=0 Z S 1 C l 1^1 lp+2xn,(o,d) ' "I Now since we can use Theorem (1.3.1) for 0 £ p <_ max(4n-4m, 2m) (by assumption (1)) we see that L is a continuous linear operator from wp+2m n Rm t Q y P b y ( 2 ) we see that there exists a continuous linear operator L 1 : WP —> W P + 2 m H H™ , for 0 £ p <_max(4n-4m, 2m) . We now formally state these conclusions : Definition (1.3.2) : Voh. r > 0 let V r = Wr D H m . — o Theorem (1.3.3) : Given g e v p + 2 m {oh. 0 £ p <_max(4n-4m, 2m) we know Lg e Wp and -l | g | | p + 2 m 1 c||Lg|| p < C||g|| p + 2 m . Theorem (1.3.4) : Given g e WP {oh. 0 <_p <_ max(4n-4m, 2m) we know theh.e exJj>ti> an unique v e v p + 2 m so that Lv = g and M v | l p + 2 m 1 C | M | . - 17 -Chapter 2 The Least Squares Methods : Continuous and Discrete 2.1 Introduction We have established the setting for our analysis and we now are going to formally define and analyze the Continuous and Discrete least squares methods discussed in Chapter 0. We note that since we already have an estimate for the type of approximations possible in S q , via Theorem (1.2.7), i t would be satisfying to see our methods provide the same order of accuracy. We w i l l see this i s possible in some cases. 2.2 The Continuous Method We w i l l assume that f e W2n 2 m throughout this chapter so that the unique solution u is in V 2 n by Theorem (1.3.4). We also have I I-I i 2 n < cMf | We note that Sections 2.2 and 2.3 are elaborations of work done by Russell and Varah [10]. We now define the basic operator . Definition (2.2.1) : IdX. A : V 2 m — > S q be given by Ton. g e V 2 m lit Ag = | e e S q : | |Le - Lg| | 2 XA minimal, j - 18 - V We w i l l soon show that A i s in fact a well defined linear operator and hence Au is a well defined function in S • Thus Au i s o the Continuous least squares approximation discussed in Chapter 0 . We w i l l need : Definition (2.2.2) : Let b(«, •) denote the blllneaA map-rb b(-, •) = L(-)M-) on w2m x w 2 m .. 2m That b(-, •) i s well defined follows from Theorem (1.3.1) We now have : Theorem (2.2.3) : A Is in {act a well defined tineaJi opefiatoA. {torn V to S ; that Is k z L(V , S ) . o ' o Proof : We f i r s t show that A i s well defined as an operator following Schultz [12; p. 69]. Let g e V 2 m . q Let e e S . Then e = J c.e. for some coefficients {c.} . o . S 1 1 1 i=l Now define q 2 F(c) = F(c 1 5 c ) = ||Lg - I c.Le.||0 . i=l We w i l l show that there i s an unique c_' minimizing F . Now q F(c) = I c c b(e e ) - 2 \ c b(e g) + ||Lg||2 i,j=l i=l 1 1 U Thus F i s a quadratic form in c^ so F has a minimum c/ i f and only i f the following two conditions are satisfied : (1) (3F/8c i)(c') = 0 for l < i < q ( ( 2 ) The matrix H= [ (82F/9c. 3c.) (c')]? . 1 i s positive definite. I j — i,j=l Condition (1) is satisfied precisely when c/ satisfies q ( 2 . 2 . 4 ) I b(e ,e )c! = b(e,g) for l < l < q . j=l This is a linear system that may be solved for c_' . We w i l l show that an unique solution exists. Let d = (d 1, d^) and B = IXe^.e )]? j = 1 . Then = b ( j d.e., J d.e.) > Gj | j d.e.||2m x=l 1=1 1=1 by Theorem (1.3.3) since S q C V . Thus B is positive definite. Hence an unique solution c_' to ( 2 . 2 . 4 ) exists. A calculation shows H = 2 B so we know H is positive definite and that condition ( 2 ) is satisfied when we calculate c/ from ( 2 . 2 . 4 ) . Thus we can calculate an unique solution c_' from ( 2 . 2 . 4 ) that minimizes F(c) . Hence setting q A § = I c ' - e i , i=l 1 we see that A i s well defined as an operator. - 20 2m Now we w i l l show that A i s linear. Let g^, g 2 e V and consider A(g^ + dg2) for real d . We can associate the form F as before and note that conditions (1) and (2) apply as before. Now condition (1) is satisfied for c_' precisely when q I b(e ,e )c' = b(e ,g1) + db(e ,g ) for 1 <_ i <_ q. Thus in an obvious notation : c_' (g^ + dg2) = c_' (g-^ ) + dc_' (g 2) . Condition (2) i s satisfied since H = 2B as before. Thus A ( 8 1 + d g 2 } = A ( s l ) + d A ( § 2 ) *• 1 , 1 Hence A i s a well defined linear operator which may be calculated in practice by solving (2.2.4) for c_' . We note that by (2.2.4) we have b(g - Ag,e) = 0 for e e S Q . By Theorem (1.3.3), for g e V we have C||g|lL 1 ||Lg||2 = b(g,g) < C||g||2n . 2m Thus we conclude that b(«, •) is an inner product on the subspace V of W2m and the norm associated with this inner product i s equivalent to the 2m ||•||2m norm on V . Thus from (2.2.4) we see that Ag i s the unique 2m 2m projection of g e V onto the subspace S q of V i n the inner product b(-, •) . We also have - 21 -2 2 Theorem (2.2.5) : CowildeAlng S Q and V m 06 AubipaceA o{ W m we have that A E 8(V 2 m, S ) . ' o Proof: Let g e V 2 m . . Now | | L(Ag - g) | | 2 < | | L(0 - g) | | 2 by the minimization property of the operator A . Thus using Theorem (1.3.3) we have M A g | | 2 m 1 M A 8 - 8 | | 2 n + . | | 8 | l 2 n < C||L(Ag - g)|| 0 + ||g|| 2 m 1 C||g| 2m ' Hence A e B(V 2 m, S Q ) . / / / Theorem (2.2.6) : Givtn g e V 2 n we.have l l s - A g | l 2 B £ Ch 2°- 2»|| g|| 2 n . Remark (2.2.7) : We know that f e W2n 2 m . Thus we have I|U-A„|| 2 b •< C K 2 " - 2 ° | | £ | | 2 ] i . 2 n s i n c e l l u l l 2 n 1 C||fI|2n_2m by Theorem (1.3.4). 2n Proof : Since g E V we know lg E S q exists. Hence using the minimization properties of A we have l |L(g " Ag)|| 2 < ||L(g - Ig)|| 2 . Thus by Theorems (1.3.3) and (1.2.7) we have - 22 -g-Ag|| 2 m 1 c||L(g - Ag)||0 < C||L(g - Ig)|| 0 1 c | | g - l g | | 2 m < c h 2 n - 2 m | | g | ! 2 n • / / / Thus we see that Au and Iu both provide the same order of accuracy as approximations to u when measured i n the M* I 12m n°rm. Note that the positive definite system (2.2.4) which must be solved to find Au i s just equation (0.1.2) as discussed before. Thus we only require knowledge of L and f to calculate the function Au in practice. 2.3 Further Error Bounds for the Continuous Method We now wish to obtain estimates on the quantity ||u - Au||^ . The main objective i s the following theorem whose proof uses Banach space interpolation theory and a trick, due to Nitsche. Theorem (2.3.1) : Suppose, that f e W2n~2m . Than |u - Au||0 < c h m i n ( 2 n ' 4 n - 4 m ) | | f | 2n-2m We remark that we do not obtain convergence at the interpolate rate in the case where 4n - 4m < 2n since by Theorems (1.2.7) and (1.3.4) we see | | « - I « | | „ < Ch 2 n||u|| 2 n < Ch 2"||f|| 2 n. 2 m . However for large enough n we get convergence at the interpolate rate. - 23 -We w i l l need the following two Lemmas before we can prove the Theorem. The proof of the f i r s t uses techniques from Bramble and Schatz [5; p. 4]. 2m Lemma (2.3.2) : Say v £ W m wkoA.Z 2n-2m > 2m . Thm theAe. JU> an e £ S Q i>0 that I Iv - Lei L < Ch 2 m| Ivl L . 1 1 10 — 1' 112m Proof : Let LS = (Le : e £ S } . Now LS i s a f i n i t e dimensional o o o subspace of W by Theorem (1.3.4) since S C V . Hence LS is o o closed in W^ . Let Y = W^/LS q be the usual quotient space which i s a Banach space under the norm [g] £ Y >||[g]||Y = inf{||g - e||Q : e e L S Q } where [g] denotes the equivalence class of g E W^ . Say g E W° . Then (2.3.3) inf{||g - e n : e e LS } < g - 0 0 b V 1. MS " u l l 0 = II SI I o Say g e W2n 2 m . Then we w i l l show that (2.3.4) i n f { | | g - e|| 0 : e e LSo} < C h 2 n " 2 m | | g | | ^ . <-. • TT2n-2m , , 2n Since g £ W there i s an unique g' E V so that Lg' = g and I l§'I l 2 n 1 CMg| l2n-2m ' b y 1 1 1 6 0 : 1 : 6 1 1 1 (1-3.4). Now Ig' e S q is defined so by Theorems (1.2.7) and (1.3.3) we have - 24 -inf{||g - e|| Q : e e LS q} < ||g - L(Ig')|| Q - ||L(g' " Ig*)|! 0 1 C | | g « - Ig' | | 2 m . 2 n - 2 m i 1 , 1 1 ^ _ , 2 n - 2 m i 1 1 1 1 c h Ms' \\nn 1 Ch ||g |L o„ Thus we have demonstrated equation (2.3.4). Now we define T : —> Y by -Tg = [g] for g £ , which i s the usual map associating the equivalence class of g in Y , with the function g . Let g £ W° . Then (2.3.3) implies l|Tg||Y = ||[g ] | l Y < l|g | l 0 • Let g E W2n 2 m . Then (2.3.4) implies l|Tg | l Y = | | [ g ] | | Y 1 Ch 2 n- 2 m|| g|| 2 n_ 2 m . Thus T e B(W°, Y) O B(W 2 n~ 2 m, Y) . Now setting r = 2n-2m, 9 = 2m/(2n-2m), we can apply Theorem (1.1.10) to show T e B(W , Y) and Tg y = inf{j |g - .e| | Q : e e L S Q } < c i H (ch 2"" 2") 6 || g|| 2 m for g E W2m . Thus inf{||v - Le|| Q : e E S q} <_ Ch m||v|| . Hence choosing a new C = 2C , we have the result. /// - 25 -We also have : 2m Lemma (2.3.5) : Say v e W m wheAC 2n-2m <_ 2m . Then letting v' be. the. 4m unique, {unction tn V ^hctt t>atli>{ieJi> Lv' = v we have | | v-L ( I v ' ) | | 0 < Ch 2 n- 2 m||v|| 2 m . Proof : The existence and uniqueness of y' e V 4 m, as stated in the Lemma, is guaranteed by Theorem (1.3.4). We also have M V | l 4 n < C||Lv'||2m = C||v||2m . Am 2n Now v 1 e V C V since 2n < 4m . Thus Iv' e S exists and — o hence by Theorems (1.2.7) and (1.3.3) we have ||v - L ( Iv ' ) | | 0 = ||L(v« - T v ' ) | | 0 1 C||V - I v ' | | 2 m < Ch 2 n- 2 m||v'|| 2 n < Ch 2 n - 2 m | | vML m < Ch 2 n- 2 m||Lv'|| 4m - ~" ' ' I 12m 2m ' Ch2 n- 2 m||v||^ • /// Now we are ready for the proof of the main result. Proof of Theorem (2.3.1) : Suppose ||u - AU||Q ^ 0 ; otherwise the result 2m i s t r i v i a l . Let v be the unique function in V that satisfies Lv = (u - Au)/||u - Au[|Q (e W^ ) whose existence is guaranteed by Theorem (1.3.4). Note that we also have ||v||2 <_ C||Lv||Q = C . Now since v e V 2 m and u - Au e V 2 m we know that u - Au and v - 26 -satisfy the endpoint conditions given by Theorem (1.1.8) for r = m. Thus integrating by parts and using the self adjointness of L we have 2 u - Au Q = (u - Au) / u - Au Q (u - Au) • Lv m rb I ( " D r r,s=0 (u - Au)Dr(a' DSv) rs m I r,s=0 J a' Dr(u - Au) DSv rs m cb s I ( - D r,s=0 DS(a* Dr(u - Au))v rs L(u - Au)v . (The above representation of ||u - AU||Q is Nitsche's t r i c k ) . By equation (2.2.4) we know that given e e S q , we have b(u-Au, e) = 0 . Thus for any e e S , o |u - Au||0 = L(u - Au) v - b(u - Au, e) L(u - Au) (v - Le) - 27 -< ||L.(u - Au)||0||v - Le|| 0 < C||u - Au||2m||v - Le|| Q by Theorem (1.3.3). Recall that by Theorem (2.2.6) we know ||u - AU|L < c h 2 n - 2 m | | f | L . . 1 1 112m — i i ii2n-2m Now, i f 2n-2m > 2m then by Lemma (2.3.2) we can choose e e S so that ||v - Le|| 0 < Ch2m|IvI I2m • Or i f 2n-2m <_ 2m then by Lemma (2.3.5) we can choose e e S Q so that IIv - Le| L < Ch 2 n 2 m||v||_ I I 0 1 1 1 2m Hence we can choose e e S so that o I I T I I ^ min(2m,2n-2m. M M „, min(2m,2n-2m) | | v - Le I I Q <_ Ch ) I I v | | 2 m <_ Ch . With this choice we thus have ||u - Au||0 < C||u - Au||2m||v - Le|| 0 ^min(2m,2n-2m)+2n-2m I l ^ l I — I I II2n-2m - c h m i n ( 2 n ' 4 n " 4 m > | | f | ! 2 n _ 2 m . / / / 2.4 A Discussion o We have examined the Continuous least squares method and i t s associated error bounds. Now we intend to examine the Discrete least squares method. - 28 -We w i l l soon define a new operator much lik e the operator A defined before. We w i l l show that the calculation of values for our new operator w i l l involve the solution of a system li k e (2.2.4) with approximate integration. Thus the new system w i l l be amenable to automatic computation as discussed in Chapter 0 . However much background i s needed before we can describe the necessary integral approximations and prove error results. We thus find i t necessary to leave the mainstream of our development and look at some general techniques. We w i l l return to our problem in Section 2.7. 2.5 An Interpolate We wish to look now at a specific way of finding polynomial inter-polates that w i l l prove very useful later (see Section 2.8). The results and methods of proof of our main theorem come from Ciarlet and Raviart [6]. Theorem (2.5.1) : Say 0 < Q £ M-l . Let c <_ c± < c 2 < ... < c M_^ <_ d be M-Q point* in [c, d]. Let • c^ = (2c^-d-c)/(d-c) {on. 1 <_ j <_ M-Q noting that y = (2x-d-c)/(d-c) ti, the. unique, a{{ine. txani>{onmation o{ [c, d] onto [-1, 1]. Suppose, g e ^ ( c , d). Thm : . (1) TheAe. e,xjj>t M unique, polynomials (Pj(y)} o{ de.gn.e.e. M-l on [-1,1] that i>atAj>{y : (i) Fon. 1 < j <_ Q : D Qp!(cp =0 {on. 1 <_ i <_M-Q - 2 9 -D r p ^ ( c p = 5 R ( J _ 1 ) {OK 0 < r <_Q-1 ( i i ) Fo*. Q+l < 3 < M : D Qp^ ( c p = 6 - L ( J _ Q ) d o f l 1 1 1 1 M-Q D r P j ( c p = 0 {on. 0 <_ r <_ Q - l . ( 2 ) TheAe exists an unique, polynomial Eg(x) o{ degn.ee M-l on [ c , d] that i>atis{iei> D^Eg(c) = D^g(c) {on 1 <_ j <_ M-Q and D r E g ( c p = D rg( C ; L) ^0*. 0 <_ r < Q - l . ( 3 ) Von 0 <_ r £ M and (d-c) <_ 2 we have l|g.-Eg|| r f ( c > d ) £ C G ( d - c ) M - r | | g | | M f ( C f d ) whene G = max{ | D r p l (y) I : - 1 <_ y <_ 1 , 0 <_ r <_ M - l , 1 <_ j <_ M-Q } . {This theonem constructs an interpolate Eg o{ g on [ c,d] o{ a generalized Henmite type). Proof : We f i r s t prove the following lemma. Lemma : Say s <_ d 1 < d 2 < .. . < <_ t one M-Q distinct points [s, t ] . Then thene i [s, t] that Aatis>{y -cn h * exi/St M unique polynomials igj) otf degnee M-l on (i) Fo*. 1 < j < Q : D Q g j (d ±) = 0 {on 1 < i < M-Q D r g j(dp = 6 R ( J _ 1 ) ^ 0 < r < Q-l ( i i ) Fo*. Q+l < j < M : D Q g j(d.) = « r ( j_ Q ) H i £ M-Q Drg.(dp = 0 {on 0 <_ r <_ Q-l - 30 -Proof of Lemma : We f i r s t consider the cases when 1 £_ j £ Q . M . v r—1 We l e t g.(x) = l d .x where we w i l l uniquely s p e c i f y the J r=l r j c o e f f i c i e n t s . Since u^§j a polynomial of degree M-Q-l that i s required to vanish at M-Q points we must l e t d r j = 0 for Q+l <_ r <_ M. Thus g.. (x) w i l l be determined when we f i x d r j for 1 £_ r £ Q . Now "*"g (d^) = ( Q - l ) ! d q j = ^ J Q i s desired. Using t h i s equation we can uniquely determine dqj . Now D Q _ 2 g j ( d 1 ) = ( Q - l ) ! d Q j d 1 + ( Q - 2 ) ! d ( Q _ 1 ) j and D Q ~ 2 g j ( d ^ = ^ j (Q 1) d e s ^ r e d ' Using t h i s equation we can uniquely define ^ ( Q - i ) j • Continuing i n t h i s fashion we can define the rest of our c o e f f i -cients uniquely for 1 £ j <_ Q . Thus g..(x) i s uniquely determined f o r 1 <_ j <_ Q so that the necessary properties hold. We now consider the cases where 0+1 <_ j <_ M . M . r r—1 We again l e t g.(x) = /, d ,x where we w i l l again uniquely 3 r=l r J s p e c i f y the c o e f f i c i e n t s . Now D^ g.. (x) i s a polynomial of degree M-Q-l that i s required to s a t i s f y (D^g..)(dr) = ^ f o r 1 <_ r <_ M-Q . Q M " Q r - l Let (D vg.)(x) = . £ d'.x . Now by the notation of the l a s t J r=l r j paragraph we have d, .r(r-l)...(r-Q+1) = d' for 1 < r < M-Q . Thus ( r - Q ) j r j - -uniquely s p e c i f y i n g d ^ f o r 1 _< r <_ M-Q we have uniquely s p e c i f i e d d r j - 31 -for Q+l < r < M . Let the matrix D be defined by D = [(d ) ] . , . x — — r r , i = l Now det D i s a Vandermonde determinant and i s nonzero as d ^ d. for r x r ^ i . Thus we can uniquely spe c i f y {d^} as the so l u t i o n of the system M-Q 7 (D) . d'. . = <5 ,. v for 1 < r < M-Q ' n i j r(-j-Q) - -i = l Hence d ^ for Q+l <_ r <_ M has been uniquely s p e c i f i e d , Now "'"gj (d^) = 0 i s required. We thus uniquely define d ^ by l e t t i n g (Q - l ) ! d Q j = -D Q-l M I d . r - l r=Q+l x x=d-, Now D g.. (d^) = 0 i s required. We thus uniquely define d ( Q - l ) j b y l e t t i n S d ^ Q - D I d Q . + ( Q-2 ) ! d ( Q _ 1 } . = -D Q-2 M I d . r - l r=Q+l x=d^ Continuing i n t h i s fashing we can define the rest of the c o e f f i -c i e n t s , and thus g.. (x) f o r Q+l <_ j <_ M, so that the necessary properties hold. Thus the Lemma i s proved. / / / Now we apply t h i s Lemma with s = -1, d = 1 and d. = c! to construct the M unique polynomials {pj(y)} as described i n conclusion (1) of the theorem. - 32 -We also apply t h i s Lemma with s = c, t = d and d. = c. to 3 3 construct M unique polynomials of degree M-1 on [c, d], which we denote by (Pj(x)}, that s a t i s f y the conclusions of the Lemma. Now g e C^[c, d] so we can l e t Eg be defined by Eg(x) = I D g(c )p (x) + I D^g(c )p (x) . j= l ' 3=1 3 Thus by our d e f i n i t i o n of the { } we see that Eg i s the unique polyno-mial on [c, d] of degree M-1 that s a t i s f i e s conclusion (2) of the theorem. Now consider g'(y) = g(((d-c)y + d + c)/2) . Note g' e WM(-1, 1). Thus we can define E'g'(y) as the unique polynomial of degree M-1 on [-1, 1] that s a t i s f i e s D rE'g'(cp = D rg'(c|) f o r 0 <_ r <_ Q-l and D^E'g'(c^) = D^g'(cp for 1 £ j <_ M-Q as was done above on [c, d]. Thus Q ._ M-Q E'g'(y) = I D J ^ ' ( c p p ' C y ) + I D V ( C ' ) P ; (y) j = l - j = l J where the {p^} were defined previously. I t i s e a s i l y seen that Eg(((d-c)y + d + c)/2) s a t i s f i e s the same conditions as E'g'.(y) by a simple c a l c u l a t i o n using the known conditions s a t i s f i e d by Eg on [c, d]. Thus by the uniqueness of our constructions we have E'g'(y) = Eg(((d-c)y + d + c)/2) Now we w i l l show - 33 -Lemma : Ton 0 £ r < M and -1 <_ y <_ l we have. M-Q Q DrE'g'(y) = D rg'(y) + £ A c ! ) D r p ' (y) + £ R< j _ 1 ) ( O D V (y) i=l J^ Q i=l y 1 J w f i e A e rx R J ( X ) " (M-r-1)! CD Mg'(t))(x-t) M r 1 dt fail x e [-1, 1] Proof of Lemma : Since g' e 1) we know we can Taylor expand g' about any x e [-1, 1] by'Theorem (1.1.9). Hence for -1 <_x, y < 1 and 0 <_ r < M we can define M-l p x 8 ' ( y ) = I n V ' ^ g ' W (y-x) 3 r and R"g'(y) as noted above. Note that ( D V)(C ; ) = p x s ' ( c r ) + RJg'Ccp for 0 <_ j < M and 1 < r < M-Q . Now let M-l , r g'(y) = I 7-rrDrg'(x) (y-*) r x r=0 w ' for -1 <_ x, y <_ 1 . A simple calculation shows that D rP g'(y) = Prg' (y) for 0 <_ r < M . Now E' is a linear operator defined for functions in A - l , 1) so that E'Pxg'(y) i s defined. Because of the uniqueness of our construc-tions we have E'P^g'ty) = P^g'(y) for -1 <_ x, y <_ 1 . - 34 -Hence for 0 £ r < M and -1 £ x, y £. 1 we have D rE'g'(y) = I R^j 1 )g'(c ;[)D rp'(y) + M j ; Q R^g'(c:)D rp' Q ( y ) j= l 3 j = l + D X D 3 AP g'Cc^plCy) + I D^ P g'(cj)p' (y) U j = 1 J j = 1 Q' M-Q Dy(E'Pxg»(y)) + ^ R ^ ' ^ g ' C c ^ D ^ ' C y ) + ^ R^g 1 (c! ) D r P ' ^ ( y ) Q f-i -1 \ v M-Q Dy(P xg'(y)) + I R x 3 _ 1 ;g '(ci)D rp^(y) + I R xg»(c')D rp^(y) . Now choose x = y i n the above. Thus f o r 0 < r < M we have D y ( P x g ' ( y ) ) | x = y - D rg'(y) Thus the Lemma i s proved. / / / Thus Now l e t G be defined as i n conclusion (3) and l e t 0 < r < M U s - E s M r , ( c , d ) = JQ (DS(g - E g ) ( x ) ) 2 dx I s=0 ( ^ r )S Df(g' - E'g')(y) , IM-C y <??) dy s=0 J - l < d V d-c Y R y g ' ( c ? D ^ + Q ( y ) + I R v ( j _ 1 )g»(c[)D Sp!(y) 3=1 7 J J <^> dy < c v v - ) 1 - 2 * — d-c 35 -^ M 7 (D g'Cy)) dy = C 2 G 2 ( d - c ) 2 ( M - r ) M 7 (D g (x) ) dx 2.2 *2(M-r)., , .2 < C G (d-c) g''M .Cc.d) where we have used the second Lemma and changes i n the i n t e g r a t i o n v a r i a b l e . Noting that the case r = M i s done since Eg has degree M-l on [c, d] , the theorem i s proved. 2.6 Quadrature Sums We now describe a well known method of approximating i n t e g r a l s that w i l l be used i n Section 2.7. Say g E C[c, d] and we want to f i n d a number close to the number g(x) dx . Let K > 0 . We choose to f i n d points ^ z j ^ f ° r 1 £ j i K (so that c < z, < ... < zv < d) and numbers {w.} for 1 < j < K (so 1 K 3 — — that Wj > 0 ) so that the quadrature.sum K £ w.g(z.) i s close to j-1 J 2 d g(x) dx c The points ^ z j ^ a r e c a l l e d nodes or quadrature points and the numbers {Wj} are c a l l e d quadrature weights. Given K nodes and K weights, we say that the corresponding quadrature sum has a degree of p r e c i s i o n r i f r i s the la r g e s t integer - 36 -so that rd K g = I w g(z ) J c j=l for a l l polynomials g of degree r . We w i l l choose our nodes and weights so the corresponding quadra-ture sum has maximum degree of precision. The unique nodes and weights characterized by maximum degree of precision are called the Gaussian nodes and weights and the corresponding quadrature i s called Gaussian quadrature. To define Gaussian quadrature, we need some notation. Let g Q, g^, ... be the unique sequence of orthonormal polynomials obtained by 2 applying the Gram-Schmidt process to the sequence of polynomials 1, x, x ,.. using the inner product (•)(•) • Thus (g.» g-) n • » = . for i , j ^ _ 0 and g^_ has degree r . We note that i t i s well known that g^ has r distinct roots in (c, d). The polynomials ^g r^ a r e called the Legendre polynomials on [c, d] . Now we can state : Theorem (2.6.1) : (1) A quad/iatuAe 6um oven. K distinct nodes can have a de.gn.ce. o{ precision o{ at moit 2K - l . (2) Case (1) ii, attained i{ and only i{ the K nodes {z..} one the K floats o{ g in (c, d) . K (3) The. weights {w^ } used when case (1) is attained one unique, 6tnictty positive and t>atis{y - 37 -w. •d K TT c j£L=l ( x - z . z . - z. J 1 ' dx tfuA 1 £ j £ K . Proof : See Isaacson and Keller [9; p. 328] / / / Hence the nodes for Gaussian quadrature are the K roots of g^ , and the weights are as given in Theorem (2.6.1). We w i l l often c a l l the nodes the Gauss points . Let {z\} for 1 £ j £ K be the K Gauss points on [-1, 1] with associated weights {wl} for 1 £ j £ K . Let g^, g^, g^, ... be the Legendre polynomials on [-1, 1] • Now g (((d-c)y + c + d)/2) is a polynomial of degree r on [-1, 1]. Also for r, s >_ 0 we have r - -\ -1 gr(((d-c)y+c+d)/2)gs(((d-c)y+c+d)/2) dy = d-c v. 1 rs Thus by the uniqueness ensured by the Gram-Schmidt process we have that g;(y) d-c , 2 , 1/2 g r(((d-c)y + d + c)/2) Thus the Gauss points {z } on [c, d] and the Gauss points {z!} on [-1, 1] are related by Zj = ((d-c)zj + d + c)/2 for 1 £ j £ K Now by Theorem (2.6.1) we have - 38 -w. d K TT c j ^ i = l x - z. i 1 z . - z . 3 i dx f l K TT -1 y - zl z\ - z! , 3 l J dy = for 1 < j < K Hence the weights {w.} on [c, d] and the weights {w!} on 3 3 [-1, 1] are related by w = ((d-c)/2)w! •J 3 for 1 < j < K . These relations between the parameters of the Gaussian quadrature rule for different intervals w i l l prove to be very useful later. In fact we soon w i l l be discussing the Gauss points on (x^, x^ +^) r o r 0 £ i £ N and w i l l use the fact that the correct affine transformation of these Gauss points gives the Gauss points on [-1, 1] (which are independent of i and h ). How these transformations w i l l aid obtaining error bounds has already been hinted at in Theorem (2.5.1) when we defined the peculiar constant G that relied on affine transformations of interpolation points. 2.7 Preliminary Error Bounds Needed for the Discrete Method We now return to our particular differential equation problem by defining the specific integral approximations that w i l l be used for the Discrete method. It i s known that the error involved in approximating the integral - 39 -of some function over an interval is proportional to some power of the length of the interval (Isaacson and Keller [9])'. With this in mind we are now able to define our integral approximations as follows. Definition (2.7.1) : Let K > 0 and n.ecall A : a = X q < ... < ^ = b . We denote the K Gauss points In [x^, by {z..} {OK. 1 £ j <_ K 13 and the. associated weights by {w„} {on. -1 <_ j <_ K . We also denote the K Gauss points In [-1, 1] by {z^} {on. 1 < j < K and the associated weights by (w^} {on 1 <_ j <_ K . Then given g(x) so that g e C[x i s x ^ for 0 <_ i <_ N we can approximate N K g by the composite quadrature sum given by £ 1 w..g(z..) i=0 j=l 13 13 We note that from Section 2.6 we have z. . = ((x. ..-x.)zf. + x . j . . + in.) 12 ; w. . = ^ 1 w! 13 i+l 1 3 i+l 1 ' i j 2 j for 1 <_ j £ K . Of course the definitions of ^ z j } a n d } a r e independent of h and i . We now prove the basic integral approximation result : Theorem (2.7.2) : Say g e W (x., x ) {on. 0 < i < N . Then i ' "i+l' N , x i + l N K I g(x)dx - I I w g(z..) i=0 Jx. 1 i=0 j=l 13 13 ch 2 K I 1=0 Jx N x i + l |D 2 Kg(t)| dt - 40 -2K 2 1 Proof : We note D g e L (x., x.,-) C L (x., x . ) for 0 < i < N . & l i+l i ' I + I — — Now by Theorem (1.1.9) we can Taylor expand g(x) about x_^ for 0 £ i £ N. Thus, letting 2K-1 P .gOO = I ~T D rg(x,)(x - x , ) r r=0 ri and R i g ( x ) (2K-1)! (D2 Kg(t))(x - t ) 2 K 1 dt , we have for x. < x < x.,n that l — — i+l g(x) = P ±g(x) + R±g(x) . We now recall that w.. = ( (x. ..,-x. )/2)w! for 0 < i < N, l j i+l I j — — ' 1 <_ 3 £ K and that Gaussian quadrature i s accurate for polynomials of degree 2K-1 by Theorem (2.6.1). Noting that P ig(x) is a polynomial of degree 2K-1 on [x i ? for 0 <_ i <_ N we thus have -N 1=0 u x i + l K g(x) dx - I w .g(z ) x± j=l I i=0 *i+l K P. .g(x) dx - I w P.g(Z..) j=l , x i + l + U X . 1 K 11 R.g(x) dx - ^ w i j R i g ( z i j ) j ) - 41 -1 1=0 Jx. I (2K-1)! J ( D 2 K g ( t ) ) ( x - t ) 2 K 1 dt dx x. i + I i-o ( 2 K " 1 ) ! j-1 w j J X . ( D ^ g C t ) ) ^ . . ^ )2 ^ 1=0 N 4.+1 |D 2 Kg(t)| dt . / / / We now need more notation Definition (2.7.3) : (1) 1{ g e C r(x ±, x ) {on. 0 <_ i <_ N then let 'r,A N r K N1/2 I I I w (DSg(z ) ) 2 1 i=0 s=0 j=l J 1 J ,2m (2) 1{ g±, g 2 e C (x,., x + 1 ) {on. 0 < i <N then let b ' ( g r 82) N K Jo j=l W i 3 L g l ( Z i 3 ) L g 2 ( Z i J ) whene we n.eeall A : a = x <...<x ,=b o N+l We note that [ I ' M 1 . is an approximation to I I • I I where we r, A 1 ' 1r,A have replaced integration on ( x ^ with a quadrature sum. Similarly b'(-, •) is an approximation to the bilinear map b(., ') . N o w II ' I l r A satisfies the triangle inequality and hence i s clearly a seminorm; say g 2 e C r(x ±, x ± + 1> for 0 <_ 1 £N . Then - 42 -. 2^ r N K X I I w s=0 i=0 j=l J ( D S g l ( z . . ) ) 2 + (D Sg 2(z..)) 2 r N K + 2 I I I w DSg (z )DSg (z ) s=0 1=0 j=l 3 3 i (i|glM;,A)2 + (i|g2M;)A)2' + 2 I I f ( w ^ V g l ( z )|)(w^ 2|D Sg 2(z )|) s=0 1=0 j=l 1 J le I I 1 + I Is I I * ) 2 where we have used the positivity of the weights. We can now state and prove the following with the additional assumptions on the coefficients t a j } °f ^ noted. Theorem (2.7.4) : Suppose g±, g 2 e W 2 K + 2 m( X i, x ± + 1 ) {on. 0 <_ i £N , g±> g 2 e W2m and a., e C 2 K[a, b] {on. 1 <_ j <_ 2m . Then |(b-b'),(gr g 2)| < c h 2 K | | g 1 | | 2 K + 2 m ) A | | g 2 | | 2 K + 2 m > A • Proof : Note that 2K+2m > 2m so that b ' ^ , g2) i s defined. We w i l l i ' L s 2 e w 2 K( xi» x i + i ) 2K now apply Theorem (2.7.2) noting that Lg, , Lg 9 e W (x., x. ..) for 0 < i < N by Theorem (1.3.1). Thus - 43 -(b-b')( g ; L, g 2)| < Ch 2 K I i=0 N x i + l < Ch 2K r N r x i + l 2K I xl I li=0 J r=0 X . 1 .2K-r, |D 2 KL g lLg 2 l < Ch 2 K l|g 1 M 2 K + 2 m ) A l l 8 2 l l 2 K + 2 n f A where we have used the continuity of the coefficients. / / / We now recall an inequality due to Schmidt and described in Bellman [3]. This inequality w i l l eventually lead to some corollaries of the previous theorem. Proposition (2.7.5) : T{ g(x) lt> a polynomial o{ dzQftnz s on [-1, 1] tkm r l (Dg)2 < ((s+l) 4/2) -1 (g) 2 • -1 Lemma (2.7.6) : 1{ g(x) -C6 a polynomial o{ d<LQHQ,2. s on [c, d] thm <d-c)MDsM0,(c,d) ± ( 3 + l ) 2 2 1 / 2 | [g| l 0 , ( c , d ) • Proof : Note that g(((d-c)y + d + c)/2) i s a polynomial of degree s on [-1, 1]. Thus by Proposition (2.7.5) we have J (Dg)2 = ^ (s+1) -1 4 f l ((Dg)(((d-c)y + c + d)/2)) 2 dy (d-c) J - l (g(((d-c)y + c + d)/2)) 2 dy - 44 2(s+l) (d-c) : ( g ( x ) T dx •/// We now show the very important result : Theorem (2.7.7) : Say e li, a polynomial o{ dtQfmz p on (x ±, {on. 0 . <_ i <_ N and 0 <_ r <_ s £ p . Thm |e | l s > 4 <_ Cb-||.|| r i l Proof : Using Lemma (2.7.6) repeatedly we have for r < s *. r N 's,A ci+l I I (D je) 2+ I I N j=0 i=0 Jx. N s-r t 4+1 (D^e)2 j=r+l i=0 J 1 l|e|r , + I I C(j)(h') r , A i=0 i=l -N-2J x i + l (Dre)' 1 M e M r , A + Ch2<r-S> N 1=0 .x i+l (D re) 2 < Ch 2 ( r- S)||e|| 2 A — 1 1 1 1 r, A where we have used h' <_ h <_ 1 . Noting that the theorem i s t r i v i a l for r = s, we are done. /// We now have the following corollaries to Theorem (2.7.4) using Theorem (2.7.7). - 45 -2K Corollary (2.7.8) : Say a., e C [a, b] {OH 1 £ j < 2m . Then : (1) 1{ g e W2m, g e W 2 K + 2 m( X i, x ± + 1 ) {on. 0 < i < N and e e thin letting r = max(0, 2K+2m-2n+l) we have o |(b-b')(g, e)| 1 Ch r!|g|| 2 K + 2 m ) A l|e|| 2 m ) A (2) l{ e±, e 2 e S q then letting r = max(-2K, 2K-2(2n-2m)+2) we have |(b-b')(e r e 2)| < C h ' l ' l e J I ^ l | e 2 M 2 m > A . Proof : We w i l l just demonstrate the f i r s t case as the second case is similar. Applying Theorems (2.7.4) and (2.7.7) we have |(b-b')(g, e)| < C h 2 K | | g | | 2 K + 2 m ) A l |e | | 2 K + 2 m 5 A , 2 K i | M || |I l | g | [ 2 K + 2 m > A Il ell min(2K+2m,2n-l),A 0 1 2K+2m-min(2K+2m,2n-l) M M I I I I A C h H g | l 2 K + 2 m > A l h M 2 m , A - ' c h r M g M 2 K + 2 m j A M e l l 2 m j A where we have used the f a c t t h a t e E S has degree 2n-l on (x., x.,..) o 1 i + l f o r 0 < i < N . /// The second part of Corollary (2.7.8) w i l l be decisive in our choice for K, the number of quadrature points. It seems natural to expect K to only depend on n and m but not h . However the particular choice - 46 -for K cannot be made unti l we make one more definition and examine a theorem. This i s done i n the next section where we define the Discrete method. 2.8 The Discrete Method To specify our method we w i l l define a mapping much li k e the A mapping of Definition (2.2.1). The mapping w i l l depend on K, the number of quadrature points in each interval. Definition (2.8.1) : Let A' : v 2 n —> S Q be given by : FoA. g e V 2 n let A'(g) = | e e S Q : (| |L(e-g) | | ^ A ) 2 ts minimal j- . We note that for e e S q and g e V the quantity l l L(e-g)||g A i s defined as L(e-g) e C(x i > x ± + 1 ) for 0 £ i £ N by the continuity of the coefficients of L . We w i l l now show that A' i s a well defined linear operator for certain choices of K . 2K Theorem (2.8.2) : VoK. K £ 2n-2m, a., e C [a, b] {on. 1 £ j £ 2m, and Au^lciently small h, A' U> tn {act a well defined linean opeAaA {nam V 2 n to S ; that tS A' e i-(V 2 n, S ) . o o Proof : The proof follows the same line as that of Theorem (2.2.3). We f i r s t show that A' i s well defined as an operator. Let g e V 2 n . - ! Again define a functional Let e E S . Then e = / c.e. for some coefficxents {c.} o . T 1 i i i=l F'(c) = ||Lg- I c.Le.M' We again look for an unique c/ minimizing F' . We know that F'(£) = I c . c b ' ( e , e ) - 2 \ c b•(e g) +, (||Lg||J ) 2 i , j = l i=l 1 1 U , A Thus F' is a quadratic form in c_ so F1 has a minimum at c_' i f and only i f the following two conditions are satisfied : (1) (3F'/3ci)<£') = 0 for 1 < i < q (2) The matrix H* = [(3 2F'/8c.8c.)(c 1)]? ._. i s positive i J 1 > 3 I definite. Now condition (1) i s satisfied precisely when _c' satisfies (2.8.3) I b'(e , e )c' = b'(e, g) for l < r < q . j=l This is a linear system that may be solved for c_' . We w i l l show that an unique solution exists. Let d = (d, , ..., d ) and B' = [b'(e., e . ) ] ? . . . Then — 1 q i J i,j = l - 48 -T q q d B'd = b'( Y d.e., y d.e.) i=l i=l q q 3 3 = (b'-b)( y d.e., y d.e.) + b( ) d.e., ) d.e.) .L- i i .L. i I i i . , i i ' i=l i=l i=l i=l Now q ..2 b( y d.e., V d.e.) , > clI 7 d.e.,, „ • _ i 1 1 i i — 1 1 A i l 1 '2m 1=1 1=1 x=l by Theorem (1.3.3) since S q C V m . Also we have that |(b'-b)(j d ± e l f \ d.e.) | < Ch2|| j d.e .M 2 m i=l i=l i=l by Corollary (2.7.8), part (2), since K >_ 2n-2m and S q C W m . Hence letting K' denote the constant obtained from Theorem (1.3.3), we have dTB'd > (K* - Ch2)|I \ d.e.II2 . — — — , — i i M 2 m i=l Thus for sufficiently small h we have dTB'd > (K'/2)|| I d.e.||2m . i=l Thus B' i s a positive definite matrix for sufficiently small h and hence an unique solution c_' to (2.8.3) exists. Now a calculation shows H1 = 2B1 so we know H' i s positive definite also, for sufficiently small h . Thus condition (2) i s satisfied when we calculate c/ from (2.8.3). - 49 -Thus we can calculate a c_' uniquely from (2.8.3) which q minimizes F 1(c) . Setting A'g = £ c!e. we see that A' is well i=l 1 1 defined as an operator. The linearity of A' follows as in the proof of Theorem (2.2.3). /// Thus we have shown A' is a well defined operator which may be calculated in practice by solving the linear system given by (2.8.3) for c_' . Of course the important point here is that (2.8.3) i s l i k e (2.2.4) except that the integrals have been replaced by composite quadrature sums. Since the quadrature sums are amenable to automatic computation we have a practical method, as noted in Chapter 0 . It also may be seen why K >_ 2n-2m i s necessary. If K was less than 2n-2m then the power of h obtained from Corollary (2.7.8) would be zero or negative and we could not show that A' was well defined. In the sequel we w i l l always assume K = 2n-2m, which i s the practical choice. 2K Note that e C [a, b]- for 1 £ j <_ 2m then, by Section (1.3). Owing to the d i f f i c u l t i e s with the non-norm l i k e behaviour of b'(-, •) on V we cannot obtain a characterization of our operator A' as a projection. However we can prove a result much lik e Theorem (2.2.6) although the proof i s more d i f f i c u l t . In the following theorem the statement "for h sufficiently small" means that h must be small enough to obtain the necessary estimate used in the proof of Theorem (2.8.2). We recall that the "smallness" of h only depends on constants. - 50 -Theorem (2.8.4) : Suppose. K = 2n-2m and h AJ> i,a{i{i-icA.entty imatt. Then given g e V 2 n we have l l s-A'g|| 2 n < C h 2 - 2 » | | g | | 2 n , Remark (2.8.5) : Suppose K = 2n-2m, h is sufficiently small and f e W2n 2 m . Then we have ||u-A'u|| 2 m < Ch 2"- 2»||f|| 2 n. 2 m since I IuI I 2 n — CI IfI I2n-2m b y T h e o r e m (1-3.4). Proof : We start by showing I I (A" A')g|| 2 m < c||Ag-gM 2 m j A • Now as in the proof of Theorem (2.8.2) we have ^ 9 3 q O d B'd = b'( ) d.e., > d.e.) > (K'/2)I I 7 d.e.I I , — — I l l i' — v M . L n l i M 2 m 1=1 i=l 1=1 where d^ = (d^, d ), since h i s sufficiently small. Let d_ represent the coefficients of Ag - A'g e S q . Thus h'(Ag-A'g, Ag-A'g) >_ C||Ag - A'g||2m • From (2.8.3) we know b'(e, g-A'g) = 0 for e e S q . Hence b'(Ag-A'g, Ag-A'g) = b'(Ag-A'g, Ag-g) . Thus using Holder's inequality we have 51 c | | A g - A'g|| 2 m < b'(Ag-A'g, Ag-g) N K 1 / 9 1 / 9 < I I (w ^L(Ag-A' g)(z )|)(w|^|L(Ag-g)(z )|) 1=1 j=l J 1 J J 1 3 < b'(Ag-A'g, Ag-A'g) 1 / 2b'(A g-g, Ag-g) 1 / 2 Now using Theorem (1.3.3) and Corollary (2.7.8) we have b' (Ag-A'g, Ag-A'g) = b(Ag-A*g, Ag-A'g) + (b'-b)(Ag-A'g, Ag-A'g) < C||Ag - A* g J | 2 + Ch2||Ag - A'g||2 < C||Ag - A'g 1 | 2 2m By a simple computation using the continuity of the coefficients of L (as in Theorem (1.3.1)) we have b'(Ag-g, Ag-g) < C ( | | A g - g | l 2 m j A ) 2 . Thus using the results above we have C||Ag - A'glJ 2 m < b'(Ag-A'g, Ag-A'g) 1 / 2b'(Ag-g, Ag-g) 1 / 2 < c||Ag-A' g|| 2 m ||A g-g||' m } A . So ||Ag - A'g|| 2 m ± C||Ag - g|| 2 m A and we have our result. We now apply Theorem (2.5.7) with c = x^, d = M = 2n, Q = 2m, C j = z.^ for 1 <_ j _< 2n-2m to obtain a polynomial E i g of - 52 -degree 2n-l on [x^, x ^ + p that satisfies *. (1) D 2 mE.g( Z ; L j) = D 2 mg(z i :.) for l<.j£2n-2m (2) D rE ±g(z i l) = D rg(z ± 1) for 0 <_ r <_ 2m-l . Also, for 0 £ s 2n, we have r s (2.8.6) I r=0 c i + l (D r(g-E.g)) 2 1/2 „ , 2n r x i + l < CGh 2 n- S I (D rg) 2 lr=0 J x ± 1/2 Recalling the definition of G and the remarks following Definition (2.7.1) we see that G depends only on {z^} for 1 <_ j <_ 2n-2m . Thus G is independent of h and i and hence we can denote G by C . We have also the following for 1 £ j <_ K and 0 £ i <_ N : 2m 2m-l I w (D (g-E g)(z ) ) Z = I w (Dr(g-E g)(z..)) 2 r=0 J 1 J r=0 J J Now g - E.g e C [x. , x . n ] for 0 < i < N . Thus we can use l i i+l — — r 2 a one term Taylor expansion of (D (g-E^)) (x) about x_L for £ x <_ x i + ^ and 0 _< r <_ 2m . Recalling that our quadrature sum i s exact for polynomials of degree zero, by (2.8.6) we have N 2m-1 i=0 r=0 K I I I w. (Dr(g-E g)(z ) ) 2 -_ r \ r\ x J -LJ 3=1 ,x i + 1 (D r(g-E.g)) 2 N 2m-l r K r ,«ij I I I I w i i (Ag-E g)(x ) ) 2 + D(D r(g-E.g)(t)) Zdt i = 0 r=0 *>j=l Jx, 1 - 53 -<i+l (D r(g-E.g)(x.)) 2 + D(Dr(g-E g)(t)) 2dt dxl Jx, > J N 2m-1 i=0 r=0 K ^ J I I I w . D(D r(g-E,g)(t)) 2 dt x i + l ex x-; D(D r(g-E i g) ( t ) ) 2 dt dx N 2m-l r K , -v fx±+l ± w! + h I I I i=0 r=0 2 " j |D(D r(g-E.g)(t)) 2| dt N 2m Ch I I i=0 r=0 x i + l x-(D r(g-E.g)) : c h2(2n-2m) +l ,,^,2^ where {w^ } are the Gauss weights on [-1, 1] Thus from the above we have N 2m K (2-8-7) I I I w (Dr(g-E g)(z..)) i = 0 r=0 j=l 1 J 1 1 J < c h 2 ( 2 n - 2 m ) + 1 | | g | | 2 n + j 2mf i=0 r=0 x i + l (Dr(g-E.g)) < c h 2 ( 2 n - 2 m ) + 1 | | g | | 2 - 1 l & l ! 2 n Now Ag and E ^ are both polynomials of degree 2n-l on [x ±, x ± + 1 ] for 0 £ i <_ N. Thus by Theorems (2.7.2) and (2.7.7) we have - 54 -N 2m f K i=0 r=0 I I I w..(Dr(Ag-E,g)(z,,)) 2 - (Dr(Ag-E,g)) 1 i J x i + l x. OT, N 2m 1 c h 2 K I I x i + l D 2 K(D r(Ag-E,g)) 1=0 r=0 J x 1 c h 2 K I I 1=0 r=0 J N 2K+2m x i + l (D r(Ag-E. g)) : = C h 2 K I I (Dr(Ag-E.g)) N 2n-l r x i + l 1=0 r=0 J x < c h 2 K _ 2 K + 2 I I i=0 r=0 (D r(Ag-E.g)) : Thus from the above we have N 2m K (2.8.8) I I I w,.(Dr(Ag-E g)(z ) ) 2 • —r\ r \ • — "i - L J ' -L J - J i=0 r=0 j = l £ (1 + Cti ) f N 2m x i + l I I (Dr(Ag-E g))" li=0 r=0 Jx. Now define Eg(x) as follows : Eg(x) E.g(x) i f x. < x < x. L 1 for some i or zero otherwise Thus by (2.8.6) we know ||g - E g | l 2 m A < C n 2n-2mi g 2 n , by (2.8.7) we know I Is " E s l l 2 m,A - C h 2 n Ig|l 2n ' b y ( 2 - 8 - 8 ) we know I |Ag - Eg I|2m>A 1 C||Ag - ESI!2m,A a n d f r o m t h e b e g i n n i n g o f the proof we - 55 -know ||Ag - A'g|| 2 m < C||Ag - g H ^ Hence by Theorem (2.2.6) and the above we have l l s - A ' g | | 2 m < | | g - A g | | 2 n + ||Ag-A'g|| 2 m < C h 2"- 2™l|g|l 2 n +C||Ag- g || 2 m i S ± ^ 2 n - 2 , n | U I I 2 n*C||A g-E 8|| 2 B j A + C||Eg-g|| 2 i n j A 1 Ch2-2»|lgll2ll + C||Ag-Eg|| 2 m > 4 1 »>2n"2m|lsll2n + c r i A 8 - g | | 2 i n + c|| 8-Eg|| 2 m j 4 1 c h 2 n - 2 ° | | g | | 2 n . /// From Theorem (2.8.4) we can prove 2 2 Corollary (2.8.5) : Conildentng V n ai, a 4ub6pa.ce. o{ W n and SQ ai a 2m 6ub6pace o{ w m {on. K = 2n-2m and h 6u{{lclentty small, m have that A' e 8(V 2 n, S ) . 2xi Proof : Let g e V n . Then by Theorem (2.8.4) we have l|A'g||2m < l|g|l 2 m+ IIS -1 llslla. + ch2"-2-!!,!^ < c||g||2ii . Hence A» e B(V 2 n, S ) . /// - 56 -Now from our proven results we see that A'u, Au and Iu a l l provide the same order of accuracy as approximations to u when measured i n t h e I I'I I 2m n ° r m ' We note that the system (2.8.3) which must be solved to find A'u is just equation (0.1.4) (or (0.1.5)) as discussed before in Chapter 0 . We also recall that for h sufficiently small, the smallness of h only depending on the problem's parameters, the system (2.8.3) i s a positive definite one. Thus we only require knowledge of L and f to calculate A'u in practice. Since (2.8.3) involves no integration but rather f i n i t e linear combinations of function values, we c a l l the calculation of A'u the Discrete least squares method, as noted before. 2.9 Further Error Bounds for the Discrete Method We now want to get estimates on the quantity ||u - A'u||Q similar to estimates obtained for the Continuous method in Theorem (2.3.1). However several d i f f i c u l t i e s are involved. The trick used for Theorem (2.3.1) relies on the fact that b(u-Au, e) = 0 for e e S q . However by (2.8.3) we only know that b'(u-A'u, e) = 0 for e e S q where b'(', •) involves only approximate integration. However we can obtain our desired estimates i f we assume more continuity of u . Thus we w i l l now assume f e W2^2n for the remainder of this An™ 2TTI section so that u e V and M u l l , „ < Cl IfI I. . by Theorem 1 1 114n-2m — 1 1 114n-4m (1.3.4). - 57 -Now we state the main result. We note that the phrase "for sufficiently small h " means that h must be small enough for Theorem (2.8.4) to be used. Theorem (2.9.1) : Glvzn that K = 2n-2m and f E w 4 n _ 4 m tkm {on. Sa{{l-dtuntlij small h we have that . ||u- A'u |L < C h M n ( 4 n - ^ ' 2 n ) | | f | | . , . i i i i o — i i i i 4 n - 4 m Proof : We proceed as in the proof of Theorem (2.3.1). Suppose ||u - A ' U | | Q £ 0 . Let v be the unique function in V 2 m that satisfies Lv = (u - A'u)/||u - A'u||Q (e W^ ) whose existence i s guaranteed by Theorem (1.3.4). Note that we also have ||v|| 2 m <_ C||Lv||q = C . Since v e V 2 m and u - A'u e V 2 m we have by integration by parts as before |u - A'u||Q b L(u - A'u)v a By (2.8.3) we know that b'(u-A'u, e) = 0 for e E S . Hence o by Theorem (1.3.3) we have (2.9.2) ||u-A'u|| 0 = I L(u - A'u)(v-Le) + (b-b')(u-A'u, e) ' a < C||u-A'u|| 2 m||v-Le|| 0+|(b-b')(u-A'u, e)| for any e E S o Now we can use Lemmas (2.3.2) and (2.3.5) again to pick a - 58 -particular e . We consider two cases. Am Say 2m >_ 2n-2m. By Lemma (2.3.5) we can find a v' e V so that Lv' = v, ||v'|| 4 m < C||v||2m < C and II T / T i \ I i _ zn -2mi i i i „ , 2n—2m | |v - L(Iv') | | Q <_ Ch | | v j j 2 m <_ Ch Now u - A'u, Iv' e W2m and u - A'u, Iv' e W 2 K + 2 m(x^, xi+-|) f° r 0 <_ i £ N . Thus by Theorems ( 2 . 7 . 4 ) and ( 2 . 7 . 7 ) we have | (b-b')(u-A'u, Iv*) | < Ch 2 K||u- A ' u | ! 2 K + 2 m } A IUv'||2K+2mjA = Ch 2 K||u- A ' u | | 2 K + 2 m > A l | I V | | 2 n _ l f A since Iv' has degree 2n-l on each subinterval. Noting 4m >_ 2n, we also have v ' „ , A < v 1 I. . < C . Hence by Theorem (1.2.7) we see 1 1 1 12n-l,A — 1 1 114m,A — J . that HV' " I v*ll 2n-1,A 1 ChllV'N2n,A 1 C h ' Thus we have from the above : I I Iv* I ] < I Iv' - Iv' I I +1 Iv' I I I I x v M2n-1,A - H v x v H2n-1,A 1 1 M2n-1,A £ Ch + C <_ C . Thus using Theorem (2.8.4) and choosing e = Iv' i n (2.9.2) we have that (2.9.3) ||u - A'u||Q < C u - A'u _ v - L'(Iv') _+ (b-b') (u-A'u, Iv*) — zm U ^ nu2n-2mi|-|i n,2n-2m , 4n-4mr i ., - C h I I f I i 2r>-2mCh + C h I Iu " A u I 12K+2m,A 1 C h ^ ( | | f | | 4 n . 4 m + | | u - A . „ | | 4 n . 2 m > 4 ) . Now we consider the case when 2m < 2n-2m. By Lemma (2.3.2) we can find an e e S so that o ||v - Le| L < Ch 2 m||v|L < Ch 2 m I I i 10 — ' 1 ' ' 2m — By Theorem (2.7.4) again, we have |(b-b')(u-A'u, e)| < Ch2K||u - A'u|| 4 n_ 2 m > A||e|| 4 n_ 2 m > A _,4n-4mi i A i I I I I I I = Ch u-A'u . „ . e „ . . 1 1 1 14n-2m ,A 1 1 1 1 2 n-l , A „ n , 4n-4m-2n+l+4mi i . i l l I I II ± C h Hu - A'u | | 4 n _ 2 m ) A M e | | 4 m j A = Ch 2 n + 1||u - A 'u| | . 0 JleU, . 1 1 • 1 '4n-2m ,A' 1 1 14m,A where we have used Theorem (2.7.7) noting 4m < 2n . 4m Let v' again be the unique function i n V that satisfies Lv' = v and | |v' | 14m <_ c| |v| | <_ C . Now apply Theorem (2.5.1) to this situation with M = 4m, Q = 2m, c.. = z^ .. for 1 <^ j <_ 2m (we note 2m < K) c = and d = to obtain a polynomial E^v' of degree 4m-l on - 60 -(x., x..,) that satisfies 1 i+l r r xi+l r I (DS(v« - E.v')) 2 < CGh 2 ( 4 m- r ) I =n Jx. 1 s=0 s 0 X i+l ( D V ) 2 i " " x i for 0 <_• r <_ 4m . As noted in the proof of Theorem (2.8.4), G depends only on the Gauss points in [-1, 1] and hence we can denote G by C . We remark that the interpolation properties of E/v* w i l l not be essential . Only the degree of E v r and the above integral inequality w i l l be used. Continuing, we define Ev' (x) = | E^' (x) i f x i < x < x i + 1 for some i or zero otherwise Thus for 0 £ r <_ 4m we have (2.9.4) ||V " Ev'|| r > A 1 Ch 4 m- r||v'|| 4 m < ch 4 m" r . Hence using the above we have I l e l1/ A < I|e - v * I | . + I I v ' I I . 1 1 1 1 4m,A — 1 1 1 1 4m,A 1 1 1 1 4 m <- H e - E v ' l l 4 m , A + HEV' -V'!Um,A + C < Ile - Ev'II. + C (by ( 2 . 9 . 4 ) ) — 1 1 1 1 4m,A < Ch~ 2 m| [ e - Ev' I I 2m A + C ( b y T h e o r e m ( 2' 7* 7^ < Ch-2m(||e - v'|| 2 m+ ||v- -Ev'|| 2 m f A) +C < Ch" 2 m(||L(e - v')|| 0 + Ch 2 m) + C - 61 -(by Theorem (1.3.3) and (2.9.4)) = Ch" 2 m(| |Le - v| | Q + Ch 2 m) + C <_ C . Thus using (2.9.2) with the particular e e S q guaranteed by Lemma (2.3.2), by Theorem (2.8.4) we have that (2.9.5) ||u - A'u||Q C||u - A'u||||v - Le|| Q + |(b-b')(u-A'u, e) < Ch | |f | | 2 n _ 2 n C h - + C h ^ | |„ - | 4 n . 2 m > 4 C i Ch2n(Hf|l4n-4n+ l|u-A.u||4n_2mi4) . Now since u e W 4 n 2 m we know Iu e S q exists. Thus using Theorems (1.2.7), (2.7.7) and (2.8.4) we have that (2.9.6) | | u - A ' u | | 4 n _ 2 m ) A < l|u|l 4 n-2m + , , A' U , ,2n-l,A < ||A'u - Iu|-| 2 n_ l f A-+ I Uu " u l Un-l.A + Mull2n-1 + HuIUn-2m < ||A'u - l u | | 2 n _ 1 ) A + C||u|| 4 n_ 2 m < C h 2 m - 2 n + 1 | | A ' u - I u l | 2 m + C | | f | | 4 n _ 4 m < Ch 2 m- 2 n + 1(||A'u - u | | 9 m + ||u - I u | | 9 J + C||f 2m '' \Zml I"''4n-4m < c h 2 n , " 2 n + 1 ( c h 2 n " 2 m | | f | | 2 n . 2 m + c h 2 - 2 " | |„| | 2 J + c| |f, , 4 n . 4 m — H I ^ I 4 n_4 m Thus by equations (2.9.3), (2.9.5) and (2.9.6) we have the desired result. 2.10 Some Extensions We now summarize and slightly extend the results of Theorems (2.3.1) and (2.9.1). ' 2xi—2m Theorem (2.10.1) : (1) Suppose that f e W n m . Then I|Dr(u - Au)|| 0 > A 1 c h m i n ( 2 n ' 4 n - 4 m ) - r | | f | | 2 n _ 2 m ioK 0 < r < 2m ||Dr(u - Au)|| 0 ) A < Ch 2 n- r||f|| 2 n_ 2 m ion. 2 m < r < 2 n . (2) Suppose that f e W , K = 2n-2m and h <U> Su{{ieiently smatt. Then ||Dr(u - A'u)|| 0 j A < Ch 2 n- r||f|| 2 n_ 2 m {on 2 m < r < 2 n . (3) Suppose that f e w4n_4m, K = 2n-2m and h is su{{icientty Smatt. Then ||D r(u-A'u)|| 0 ) A < Ch- n< 2 n' 4 n- 4^- r||f|| 4 n_ 4 m fa 0<r<2m. (4) We note that in (1), (2), (3) we may replace I I ' I I Q A ^ | H | Q i{ 0 < r < z+1 . Here "h sufficiently small" means that h must be small enough for Theorem (2.8.4) to be used. We note that these results reflect the - 63 -interpolate results of Theorem (1.2.7); that i s , one "pays" for each deri-vative by a loss in a power of h . Also, for large enough n, min(2n,4n-4m) = 2n so that Theorem (1.2.7) is even more closely reproduced. Thus we get results for Au and A'u that are very much like the interpo-late results. Proof of Theorem (2.10.1) : We start with (1). Noting that Iu e S q is defined we have for 0 < r < 2m that (2.10.2) ||Dr(u - Au)|| Q ) A < ||u-Au|| r^ < | | u - I u | | r > A + | | l u - A u | | r ) A < C h 2 n r | | u | L + Ch" r(||lu - Au| L ) — '1 1 12n 0 1 C h 2 n - r | | f | | 2 n _ 2 m + Ch- r(|| u - Iu|| Q + I|u - Au||Q) <- C h 2 n " r H f l l 2n- 2m + C h - r ( c h 2 n ||u|l + clim±n(2ru,4r1-4m) | | f | | ) ^ 2n 1,112n-2m-' min(2n,4n-4m)-r , i , • < Ch f — 112n-2m where we have used Theorems (1.2.7), (2.7.7) and (2.3.1) . For 2m < r < 2n-l we have - 64 -(2.10.3) ||Dr(u - Au)|| 0 ) A 1 ||u-Au|| r j A < I|u - IulI . + Illu - AulI . _ I I M r , A 1 1 1 1 r,A £ch2"-||u||2n + ch2»-r(||r„-Au||2o>A) ^ 2 n - r l l f l l 2 n - 2 B . _, 2m-r 2 n - 2 m i i n , „ , 2 n - 2 m i i - i i v + Ch (Ch ||u|| 2 n + Ch IUII2n.2m) i C h 2"" rH fll 2„-2 m where we have used Theorems (1.2.7), (2.7.7) and (2.2.6). Now since the case r = 2n is t r i v i a l as Au has only degree 2n-l we have shown (1). Case (2) is proved by an argument similar to (2.10.3) only we use Theorem (2.8.4) instead of Theorem (2.2.6). Case (3) is proved by an argument similar to (2.10.2) only we use Theorem (2.9.1) instead of Theorem (2.3.1). Since case (4) is clear due to the continuity of functions in S we are done. /// - 65 -Chapter 3 Practical Considerations 3.1 Properties of L We listed the properties required of the operator L in Section 1.3. We now wish to indicate which operators have these properties. T T i ..t. f „max(4n-4m,2m)+r r . .. We know that a' e C 1 1 [a, b] for 1 < r, s < 10 s —*•* ni already. Now we suppose that : (1) J(v, v) _> C v 'm for v e C™(a, b), (2) a' > 8 > 0 mm — for x e [a, b] m cb where JC^ , v2> = £ r,s=0 J a' DSv0Drv- is a bilinear form on W™ x W™ rs 2 1 and C^(a, b) = | v e C m(a, b) : supp v (a, b) j Note that for v e C 2 m(a, b) we have j m fb ciIvII < J ( V , v) = y r,s=0 a * DrvDSv rs m fb I r,s=0 (-l) rD r(a' DSv)v = rs rb Lvv 1 L v L v n L v | v - 66 -where we have used integration by parts. Thus we have (3.1.1) c M v l l m ± I M I Q for v e C 2 m(a, b). Now since (3.1.1) holds for v e C~(a, b) c C 2 m(a, b) we have that (3.1.1) holds for v e H m . Note that by Theorem (1.3.1) we also know |Lv||0 <C||v||2m for v e W2m Now by Agmon [2; p. 102, p. 129] we have that given conditions (1) and (2) above and g e WP for 0 £ p max(4n-4m, 2m) there i s an unique v £ H™ Pi W2nrt"P so that Lv = g in WP and Mv||p+2m i c(||8||p+ |MI0) 1 C(||g|| p+ l|v||m) < c | | g | | p = c||Lv|| p . Thus under (1) and (2) above we-have the necessary conditions stated for L in Section 1.3. Note that i f L i s of the form stated in (0.1.1) then (1) above is clearly satisfied i f a' i s sufficiently smooth and a' > 6 > 0 for r J r — 1 <_ r <_ m on [a, b]. Thus i f L i s of this form then the totality of restrictions : - 67 -,^ -> o \ / i \ i _max(4n-4ra,2m)+r r c A „ (3.1.2) (1) e C ' [a, b] for 0 <_ r £ m (2) a^ . >_ 6 > 0 for 0 <_ r <_ m on [a, b] are sufficient for Section 1.3. 3.2 A Comparison We wish to briefly compare Theorem (2.9.1) with the following result on the usual Collocation method from, for example, Russell and Varah [10]. Theorem (3.2.1) : Say L ii, of the {ohm given by equation (0.1.1), L satisfies (2) of (3.1.2), z = 2m-l and the coefficients of L and f a/ie sufficiently smooth. Then we have the folZowina result fon the Collocation approximation w : II II min(4n-4m,2n) I I u - w | | <. Ch whehe h is sufficiently small . Now since we know from the preceding section that L satisfies the necessary properties needed for Section 1.3 i f L is of the form given in (0.1.1) and satisfies (3.1.2), we have by Theorem (2.9.1) ||u - A'u||0 < c h m l n ( 4 n - 4 m ' 2 n ) . for h sufficiently small and f sufficiently smooth. - 68 -Thus we can see that the Collocation method and the Discrete method both generate approximations in S q that have the same convergence proper- ties. Thus both methods are feasible for practical computations, with the limitations outlined in Chapter 0 . 3.3 Discrete Least Squares Computations By the use of numerical computations we now intend to examine Theorem (2.9.1) for the Discrete method. However before we state the examples we w i l l make some preliminary remarks. (The results of this section were obtained by the author, on the IBM 360/67 and the later IBM 370/168 computers at U.B.C.) . A l l calculations in the following examples utilized double preci-sion arithmetic to minimize roundoff errors. The choices made for the various parameters in the examples are : (1) h = h' = 1/(N+1) for integer N . (Thus the meshes are uniform and a = 1 is a mesh bound). (2) [a, b] = [0, 1]. (3) n = 2, z = 2 . (Thus the space S is the space of cubic splines on [0, 1]). (A) m = 1 . (Thus 2n-2m = 2 > 0). The basis {e.} used for S i s the B-spline basis on a uniform mesh 1 - 69 -described in Schultz [12; p. 73] or de Boor [7]. For reasons noted before K = 2n-2m = 2 Gauss points in ( x ^ ( for 0 £ i ± N) were used where w. . = (x.,.. - x.)/2 = h/2 (for 0 < i < N , l < j < K) , are the 13 i+l l — — ' — ' associated weights. Note that z = 2n-2 = 2 ^ 1 = 2m-l . Thus the Discrete method gives an approximation with one more degree of continuity than that available from the Collocation method. In each of the examples an estimate of | |u - A'u| |ro = max{ |u - A'u| (x) : 0 <_ x <_ 1} was made as follows. An i n i t i a l set of calculations was made of |u - A'u|(x) at _^ N non-mesh points in [0, 1]. The maximum of these numbers was taken and a further calculation of |u - A'u|(x) was made at twenty additional points in a neighborhood of where the largest error was observed. The maxi-mum over a l l these values was then called IIu — A * uI I * Since the number of points checked in the i n i t i a l calculations differed l i t t l e from N in many cases, ||u - A'u||^ is only an estimate of ||u - A'u|| • and no doubt some anomalies in a calculations (following) are due to this fact. Now the following asymptotic result is expected : ||u - A ' u l ^ = Ch 3 . Thus given two values e.^ and e,, of ||u - A ' u l j ^ calculated at h^ and h 2, we can see that 6 = l o g ^ / e ^ / l o g O ^ / b ^ ) . With this in mind we - 70 -define a to be as i n the above formula for g where we use I I" I 1^ values instead of | |« | | values. Hence we have a way to estimate 6 . Now we can state the results of our calculations. Consider the following operators and solution functions : (3.3.1) Lu = -D((1/TT 2)DU) + e Xu = f ; u = s i n ( T r x ) (3.3.2) Lu = -D ( ( e 1 0 x - s)Du) + lOOsu = f ; u = ( x 2 - x ) e 1 0 j where s = .999999999 (3.3.3) Lu = -D(l-Du) + 4u = f ; u = cosh(2x-l) - cosh 1 . In each of the above equations we can see that L and the asso-ciated f satisfy the assumptions of Section 1.3 (by the conditions (3.1.2)) and in fact they also satisfy the assumptions of Theorem (2.9.1). Thus we expect 4 u - A' u | | <_ Ch . Referring to Table I we can see the results of the a calcula-tions imply llu " A'u||0 < ||u - A'ull^ « ||u - A'u||; < Ch4 in a l l cases. We also note the higher rate of convergence observed i n the case of (3.3.2) in spite of the almost singular coefficient in L and the growth of u . This heightened convergence rate w i l l probably approach 4.0 as the error ||u - A'u||^ becomes fractionally small. - 71 -We now consider (3.3.4) Lu = -D(eXDu) + e Xu = f ; p(x) - -|^ -(x - j ) 4 for 0 <_ x <_ j / N 79, 1.4 - 1 p(x) - y-(x - -j) for -j < x £ 1 1 3 1 2 5 29 where p(x) = x + 7 4 ' x + 8" x + 48" ' N o w L a n d ^ satisfy the assumptions of Section 1.3 (again by the conditions (3.1.2)). Also we note 1 2 1 that f £ C [0, 1] and D f has a jump discontinuity at x = y . Thus by Theorem (1.1.6) we have f e W2n_2m = W2 but f £ w 2 ( 2 n " 2 m ) = w 4 . H e n c e the hypotheses of Theorem (2.9.1) do not apply so we cannot guarantee |u - Au||0 < Ch4 4 u - A u _< Ch ' However by Theorem (2.3.1) we do have Referring to Table II we see that I l« - A'u| | Q < | |u - A»u| \oo* | |u - A'u| |; < Ch4 . Thus the hypotheses of Theorem (2.9.1) would appear to be too strong. We 2n—*2m suspect f e W should be sufficient for Theorem (2.9.1). The Discrete least squares method was also tried on the following equations which do not satisfy the conditions discussed in Section 3.1 : (3.3.5) Lu = (1/TT)2D2U + (1/TT)DU + u = f ; u = sin(Trx) (3.3.6) Lu = D2u + Du = f ; u = (x 2-x)e X . - 72 -In both cases a = 4 convergence was obtained using the Gauss points, as seen in Table II. Thus the method appears to be stronger than our i n i t i a l analysis would indicate. Other quadrature approximations were tried using (3.3.5) and (3.3.6) but no increase in the convergence rate was discovered. Thus by these calculations we can see that the Discrete least squares approximation method can be used for practical problems. - 73 -Table I Results for Equations (3.3.1) - (3.3.3) (3.3 •1) (3.3.2) (3.3.3) N ||u - A'u i i : a I I " - A'ul1 * I I 1 CO a 1|u - A'ul1' I I 1 1 00 a • 5" .13E - 3 .78E + 4 .46E - 4 4.0 O A 3.9 - 3. U 10 .HE - 4 •13E + 4 .42E - 5 4.0 4.9 4.0 20 .82E - 6 .54E + 2 .32E - 6 4.0 5.5 4.2 30 .17E - 6 .64E + 1 .63E - 7 4.0 5.7 4.2 40 .56E - 7 •13E + 1 .20E - 7 4.0 5.8 3.8 50 .23E - 7 .36E + 0 •87E - 8 4.0 5.9 6.3 60 .11E - 7 .13E + 0 .28E - 8 4.0 6.0 1. 3 70 .62E - 8 .51E - 1 .23E - 8 3.7 80 — — .14E - 8 3.9 90 .90E - 9 Table II Results for Equations (3.3.4) - (3.3.6) (3.3.4) (3.3. 5) (3.3.6) N 1 lu - A'u| |' a ||u - A'u f: a 1 1 " - A'ul1 1 a 5 .19E - 2 .13E - 3 .83E - 4 • 3.7 4.0 H . y 10 • H E - 3 .14E - 4 .76E - 5 • 3.9 • 3.8 4.0 20 •83E - 5 .12E - 5 •57E - 6 - 4.0 • 4.1 /. 1 4 . 1 30 .17E - 5 .25E - 6 .12E - 6 - 4.0 3.8 5.4 40 .55E - 6 .88E - 7 .26E - 7 • 3.8 50 .24E - 6 — — 4.7 60 • H E - 6 — — 3.2 70 .63E - 7 — — • 3.9 80 .38E - 7 — 4.0 90 .24E - 7 — — - 75 -Bibliography 1. Adams, R.A., Sobolev Spaces, Academic Press, New York, (to appear -1975). 2. Agmon, Shmuel, Lectures on E l l i p t i c Boundary Value Problems, D. Van Nostrand Co., New York, 1965. 3. Bellman, Richard, A Note on an Inequality of E. Schmidt, Bull. Amer. Math. Soc, V50, 1944, pp 734-736. 4. Berezanskii, Ju. M., Expansions in Eigenfunctions of Self Adjoint Operators, American Math. Society, Providence, Rhode Island, 1968. 5. J.H. Bramble and A.H. Schatz, Least Squares Methods for 2m-th Order E l l i p t i c Boundary-Value Problems, Math. Comp., V25, 1970, pp 1-33. 6. P.G. Ciarlet and P.A. Raviart, General Lagrange and Hermite Interpo-lation in Rn with Applications to Finite Element Methods, Arch. Rational Mech. Anal., V46, 1972, pp 177-199 7. De Boor, C., On Calculating with B-splines, J. Approx. Theory, V6, 1972, pp 50-62. 8. E. Hewitt and K. Stromberg, Real and Abstract Analysis, Springer-Verlag, New York, 1969. 9. E. Isaacson and H.B. Keller, Analysis of Numerical Methods, John Wiley and Sons, Inc., New York, 1966. f 10. R.D. Russell and J.M. Varah, A Comparison of Global Methods for Linear Two-Point Boundary Value Problems, Dept. of Computer Sc., U.B.C., Technical Report, 1974. 11. Schultz, M.H., Error Bounds for Polynomial Spline Interpolation, Math. Comp., V24, 1970, pp 507-515. 12. Schultz, M.H., Spline Analysis, Prentice-Hall, Inc., New Jersey, 1973.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The discrete least squares method for 2m-th order elliptic...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The discrete least squares method for 2m-th order elliptic boundary-value problems Sammon, Peter Henry 1974
pdf
Page Metadata
Item Metadata
Title | The discrete least squares method for 2m-th order elliptic boundary-value problems |
Creator |
Sammon, Peter Henry |
Date Issued | 1974 |
Description | Many positive results are known for the Least Squares method of numerically computing an approximant solution for a 2m-th order elliptic boundary value problem on a real interval. However due to integrals that appear in the linear system that must be solved to find the approximant solution, the Least Squares method is computationally unattractive. Thus one is led to consider other, more practical, methods. In this thesis, such a method is examined. It is first shown that minimizing a quantity involving discrete quadrature sums to find an approximation to the solution leads to a linear system in which quadrature sums, not integrals, appear. The approximation generated by this method, known as the Discrete Least Squares method, is thus easily computed. Error estimates are then proven for the Discrete method. A certain polynomial interpolate is first constructed and then using Sobolev space theory and known estimates from the related Least Squares method, the desired estimates are obtained. These estimates are like the usual Least Squares estimates although more continuity of the coefficients of the problem is required in the final stages. Comparisons are then drawn between the Discrete method and the Collocation method. It is noted that both methods offer easy computability and shown why the Discrete method can generate a smoother approximation in most situations. Results of numerical computations are then provided which support the theory and a discussion of what problems the theory applies to is also given. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-28 |
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. |
IsShownAt | 10.14288/1.0080125 |
URI | http://hdl.handle.net/2429/19263 |
Degree |
Master of Science - MSc |
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_1975_A6_7 S24_5.pdf [ 3.74MB ]
- Metadata
- JSON: 831-1.0080125.json
- JSON-LD: 831-1.0080125-ld.json
- RDF/XML (Pretty): 831-1.0080125-rdf.xml
- RDF/JSON: 831-1.0080125-rdf.json
- Turtle: 831-1.0080125-turtle.txt
- N-Triples: 831-1.0080125-rdf-ntriples.txt
- Original Record: 831-1.0080125-source.json
- Full Text
- 831-1.0080125-fulltext.txt
- Citation
- 831-1.0080125.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-0080125/manifest