G W Reddien

PROJECTION METHODS FOR TWO-POINT BOUNDARY VALUE PROBLEMS

Abstrad. A survey of the many different projection methods for the numerical solution of two-point boundary value problems is given along with an introduction to the techniques by which their convergence is established.

Introduction.

. An important aspect of code development and evaluation is theoretical support. Theory provides one basis for selecting the algorithms. Also, theoretical error bounds not only give the order of convergence basis for deciding among different methods, but also suggest mesh selection schemes and extrapolation procedures. We will illustrate some of these points here.

. There are certain hybrid methods with attractive features that will be presented here.

Section 2 describes various examples of projection methods with references. Section 3 recalls some basic facts about projections and convergence theorems for projection methods. It is also explained there how the basic methods of § 2 fit into a general framework. Section 4 discusses superconvergence and more refined error bounds.

. We also do not discuss eigenvalue problems, partial differential equations, integra-differential equations and functional differential equations.

A comprehensive survey of the literature on numerical methods for two-point boundary value problems was given by H. B. Keller [50) in June, 1974. The reader is referred there and also to a monograph by Keller [93) for possible references. We have made no attempt here to be all inclusive. Analyses and applications of projection methods can also be found in the chemical engineering literature. In particular, we cite the method of orthogonal collocation as given by Finlayson [92).

Examples.

Before beginning an abstract description of projection methods, indeed before even giving a definition, we consider some examples. We will, for simplicity, consider these examples as applied to the problem (2.1) -y" + ao(x )y' + a1 (x )y = f(x ), O<x<1, with Dirichlet boundary conditions (2.2) y(O) = y(1) = 0.

We assume a0 , a 1 and f are continuous and that f = 0 implies y = 0.

We stress here that the problem (2.1)-(2.2) will be used as a common setting for the description of several methods, in spite of the fact that projection methods are attractive because they apply to general nonlinear systems. For many projection methods, analysis and programming for nonlinear systems is not much more difficult than for (2.1)- (2.2). The smoothness conditions on a 0 , a 1 and/ can be easily weakened and the boundary conditions generalized. References are cited later. However, some methods have only been defined and analyzed for (2.1)-(2.2). These cases will be pointed out.

Projection methods for (2.1)-(2.2) are global function space approximation methods. That is, a function y,(x) in an approximating space is determined to approximate y for all x in [0, 1]. The most used approximating spaces are polynomials and polynomial splines. The use of polynomial splines is responsible for the popularity of projection methods, since in addition to their excellent approximation properties, the associated matrix problems are banded and their setup is well suited for digital computation. The emphasis here will be on projection methods with splines, although some mention will be made of polynomials. Polynomials of course are splines, albeit on a very simple partition. The Russian literature on projection methods actually predates the Western effort. Detailed discussions of projection methods are contained in the books by Kantorovich and Akilov [START_REF] Kantorovich | Functional Analysis in Normed Spaces[END_REF] and also by Krasnoselskii, et al. [START_REF] Krasnoselskii | Niiherungsverfahren zur Losung von Operatorgleichungen[END_REF]. Their omissions are a result of an unfamiliarity with piecewise polynomial functions.

Let Ll:O=xo<x 1 < .. •<x,=1 be a partition of 1=[0,1] with h= maxi (xi-Xi-J). A family of partitions is said to be quasi-uniform if there is a constant c so that h;;:;; c mini (xi-xi-1) for all partitions in the family. By splines, we mean the elements of S(r, k, Ll)={v E Ck(I): for each i, v agrees on (x;-t. x;) with some polynomial of degree;;:;; r}.

Here r ~ k ~ -1 are integers. With k = -1, splines are simply piecewise polynomials with no continuity conditions. We are restricting our splines to a uniform set of continuity conditions. This is not necessary. We let I;= (X;-1 , x;) and h; = x; = x;-X;-1.

Collocation.

y,(O) = y,(1) = 0. i= 1, • • • ,N-2,
General analyses of such methods and specific examples can be found in deBoor [START_REF] Deboor | The method of projections as applied to the numerical solution of two-point boundary value problems using cubic splines[END_REF], Phillips [START_REF] Phillips | The use of collocation as a projection method for solving linear operator equations[END_REF], Russell and Shampine [START_REF] Shampine | A collocation method for boundary value problems[END_REF], Lucas and Reddien [START_REF] Lucas | Some collocation methods for nonlinear boundary value problems[END_REF], deBoor and Swartz [START_REF] Deboor | Collocation at Gaussian points[END_REF] and Douglas and Dupont [START_REF] Douglas | Collocation methods for parabolic equations in a single space variable based on C -piecewise-polynomial spaces[END_REF]. Related references here include Ahlberg and Ito [START_REF] Ahlberg | A collocation method for two-point boundary value problems[END_REF] and Kammerer, Reddien and Varga [ 4 7]. With k = 1, an effective choice for the collocation points is to let -1 < p 1 < • • • < Pr-t < 1 be the zeros of the Legendre polynomial of degree r -1 and define gii = t(x;-1 +X;+ Pi(x;-x;_t)) to be the collocation points. With sufficient smoothness, this method which is called collocation at Gauss points achieves optimal rates of convergence in the L oo norm, i.e.JJy-Ynlloo = O(h'+ 1 ).

Moreover, superconvergence results hold at the mesh points. We return to this later. On the other hand, smooth spline collocation methods converge at rates equal to the truncation error, namely O(h'-1 ), for (2.1)-(2.2). With Yn in S(3, 2, 6.) and choosing t; =X;, then convergence in the

L oo norm is O(h 2 ).
The convergence rate is not, of course, the sole criterion for selecting a method.

Rather overall computational effort is critical. Note here that dim S(3, 2, 6.) = n + 3 and dim S(3, 1, 6.) = 2n + 3, and in general the smooth spline methods result in smaller matrices. For numerical comparisons indicating that in some cases smooth spline methods are competitive, see Sincovec [START_REF] Sincovec | On the relative efficiency of higher order collocation methods for solving two-point boundary value problems[END_REF] and Russell [START_REF]A comparison of collocation and finite differences for two-point boundary value problems[END_REF]. Smooth spline methods were given by Ahlberg and Ito [START_REF] Ahlberg | A collocation method for two-point boundary value problems[END_REF] that replaced a few equations of the type (2.1.1) by interpolation equations for the differential equation. Let ~J=f(x;) and ~Jt=f'(x;). In this notation, the method ~;(-y~+aoyn+a1yn)= ~J,i=1,•••,n, and ~J(-y~+a 0y~+a 1 y)=~Jf,j=O,n, with Yn in S(5,4,6.) was considered along with an analogue for Yn in S (7, 6, 6.). Numerical comparison results are given in [START_REF] Ahlberg | A collocation method for two-point boundary value problems[END_REF] and [START_REF] Sincovec | On the relative efficiency of higher order collocation methods for solving two-point boundary value problems[END_REF].

Collocation theory allows one to consider more general problems than (2.1)-(2.2). The papers [START_REF] Deboor | Collocation at Gaussian points[END_REF], [START_REF] Lucas | Some collocation methods for nonlinear boundary value problems[END_REF], [START_REF] Shampine | A collocation method for boundary value problems[END_REF] follow the lead of Vainikko [START_REF]Galerkin's perturbation method and the general theory of approximate methods for nonlinear equations[END_REF] and treat nonlinear problems. Extensions to the case of nonlinear boundary conditions are given in Wittenbrink [START_REF] Wittenbrink | High order projection methods of moment-and collocation-type for nonlinear boundary value problems[END_REF], Weiss [START_REF] Weiss | The application of implicit Runge-Kutta and collocation methods to boundary value problems[END_REF], Reddien [START_REF] Reddien | Approximation methods for two-point boundary value problems with nonlinear boundary conditions[END_REF] and Voss [START_REF] Voss | Projektionsverfahren fur Randwertsaufgaben mit nichtlinearen Randbedingungen[END_REF]. Many of the papers on collocation assume that the lead order part of the differential equation is invertible subject to the given boundary conditions. This restriction can be easily removed as was shown by Witten brink [START_REF] Wittenbrink | High order projection methods of moment-and collocation-type for nonlinear boundary value problems[END_REF] and Cerutti [START_REF] Cerutti | Collocation for systems of ordinary differential equations[END_REF]. Another approach using alternative theory is given in Reddien [START_REF]Approximation methods and alternative problems[END_REF]. Collocation methods are also applicable to general vector systems. These results are described by Weiss [START_REF] Weiss | The application of implicit Runge-Kutta and collocation methods to boundary value problems[END_REF], Cerutti [START_REF] Cerutti | Collocation for systems of ordinary differential equations[END_REF], Russell [START_REF] Russell | Collocation for systems of boundary value problems[END_REF] and Houstis [START_REF] Elias Housns | A collocation method for systems of nonlinear ordinary differential equations[END_REF].

2.2. Ritz-Galerkin method. The Galerkin method approximates the solution to (2.1)-(2.2) by solving for Yn E S0 (r, k, 6.) = S(r, k, 6.)

n {v: v(O) = v(l) = 0} the equations (2.2.1)
where {v;} is a basis for S0 (r, k, 6.). The Ritz method chooses Yn E S0 (r, k, A) so that (2.2.2) with {v;} as in (2.2.1). Although there is only a small difference between (2.2.1) and (2.2.2), the difference is important. Equation (2.2.2) allows r = 1. The methods are not equivalent if k = 0 because then (2.2.2) cannot be integrated by parts. If the integrals in (2.2.1) and (2.2.2) are done by a quadrature, then even though the continuous equations are the same, the discretized versions will not be. Moreover, different quadratures are required for the discrete methods to be well defined. The Ritz method for (2.1)-(2.2) using C 1 -cubics requires three point Gauss quadrature in each subinterval to be well-posed, [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF], while the Galerkin method using C 1 -cubics requires only two-point Gauss quadrature in each subinterval. In this case, the quadrature-Galerkin method is equivalent to collocation at Gauss points. See [START_REF]A comparison of collocation and finite differences for two-point boundary value problems[END_REF] and also § 2.6. Finally, a more subtle point concerns extension of the two methods to more general problems with more general boundary conditions. The Galerkin method can be extended in the obvious way to any problem. See Strang and Fix [START_REF] Strang | An Analysis of the Finite Element Method[END_REF], for example. The Ritz method requires even order problems (however, see Ciarlet, Schultz and Varga [START_REF]Numerical methods of high order accuracy for nonlinear boundary value problems[END_REF] and Petryshyn [START_REF] Petryshyn | Direct and iterative methods for the solution of linear operator equations in Hilbert space[END_REF]) and the approximations are taken in spaces satisfying only the essential boundary conditions [START_REF] Strang | An Analysis of the Finite Element Method[END_REF]. General boundary conditions require the use of a modified functional or approximation space so that the Ritz method corresponds to the correct minimum principle. See, for example, Hallet, Hennart and Mund [START_REF] Hallet | A Galerkin method with modified peicewise polynomials for solving a second-order boundary value problem[END_REF]. For the most part, the Galerkin method is not analyzed in the literature but rather the Ritz method is studied and for problems essentially no more general than (2.1)-(2.2). Dirichlet boundary conditions are nearly always assumed. Although it is obvious that many results extend to general even order equations, as in Natterer [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF], and more general boundary conditions, as in [START_REF] Hallet | A Galerkin method with modified peicewise polynomials for solving a second-order boundary value problem[END_REF], a systematic extension of all results to general problems is unavailable. It is also assumed that either the problem (2.1)-(2.2) is self-adjoint and elliptic, as in Nitsche [START_REF] Nitsche | Bin Kriterium fiir die Quasi-Optimalitiit des Ritzschen Verfahrens[END_REF], or that at least the lead order part is, as in Schatz [7 5]. No such assumptions are required for collocation methods. However, if a problem is selfadjoint, then (2.2.2) gives a symmetric matrix while collocation does not. This has obvious implications for the computations, also for the associated eigenvalue problems.

Convergence proofs for the Ritz-Galerkin method have been somewhat different from those for collocation even though both are projection methods. The proofs follow classical lines [START_REF] Kantorovich | Approximate Methods of Higher Analysis[END_REF] to get existence and error estimates in the usual energy norm and then use Nitsche's trick [START_REF] Nitsche | Bin Kriterium fiir die Quasi-Optimalitiit des Ritzschen Verfahrens[END_REF] to obtain optimal bounds in the L 2 norm. Important theoretical papers on the existence and convergence for the Ritz-Galerkin method include Ciarlet, Schultz and Varga [START_REF] Ciarlet | Numerical methods of high-order accuracy for nonlinear boundary value problems. I. One dimensional problem[END_REF], [START_REF]Numerical methods of high order accuracy for nonlinear boundary value problems[END_REF], [START_REF]Numerical methods of high order accuracy for nonlinear boundary value problems[END_REF], Perrin, Price and Varga [START_REF] Perrin | On higher-order methods for nonlinear two-point boundary value problems[END_REF], Douglas and Dupont [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF], [START_REF]Superconvergence for Galerkin methods for the two-point boundary problem via local projections[END_REF], Nitsche [START_REF] Nitsche | Bin Kriterium fiir die Quasi-Optimalitiit des Ritzschen Verfahrens[END_REF], Wheeler [START_REF] Wheeler | An optimal L 00 error estimate for Galerkin approximation to two-point boundary value problems[END_REF], Schatz [START_REF] Schatz | An observation concerning Ritz-Galerkin methods with indefinite bilinear forms[END_REF], Blair [START_REF] Blair | Error bounds for the solution of nonlinear two-point boundary value problems by Galerkin's method[END_REF], Aubin [START_REF] Aubin | Approximation of Elliptic Boundary-ValLie Problems[END_REF], Schultz [START_REF] Schultz | Spline Analysis[END_REF], Urabe [START_REF] Urabe | Numerical solution of multi-point boundary value problems in Chebychev series. Theory and method[END_REF], Natterer [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF] and Strang and Fix [START_REF] Strang | An Analysis of the Finite Element Method[END_REF].

Early papers established optimal orders of convergence in the L 2 norm. With k = 0, i.e. continuous splines, Wheeler [START_REF] Wheeler | An optimal L 00 error estimate for Galerkin approximation to two-point boundary value problems[END_REF] established optimal rates of convergence in the L oo norm for (2.1)-(2.2). Partial extensions of this result are given by Natterer [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF].

Blair [START_REF] Blair | Error bounds for the solution of nonlinear two-point boundary value problems by Galerkin's method[END_REF] has results for the L oo norm but for special cases of S(r, k, a) with quasiuniform assumptions on the mesh. Optimal rates in the L oo norm for arbitrary S(r, k, a) were given by Douglas, Dupont and Wahlbin [START_REF] Douglas | Optimal L 00 error estimates for Galerkin approximations to solutions of two-point boundary value problems[END_REF] but with the assumption of quasiuniform meshes. Some relaxation of this condition is given by Natterer [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF]. The optimal order collocation methods given by de Boor and Swartz [START_REF] Deboor | Collocation at Gaussian points[END_REF] do not require quasi-uniformity.

The influence of quadrature error on the Ritz-Galerkin method has been considered by Herbold, Schultz and Varga [START_REF] Herbold | The effect of quadrature errors in the numerical solution of boundary value problems by variational techniques[END_REF], Fix [START_REF] Fix | Effects of quadrature errors in finite element approximation of steady state, eigenvalue, and parabolic problems, The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations[END_REF], Schultz [START_REF]Quadrature-Galerkin approximations to solutions of elliptic differential equations[END_REF], and Douglas and Dupont [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF]. The papers [START_REF] Herbold | The effect of quadrature errors in the numerical solution of boundary value problems by variational techniques[END_REF] and [START_REF]Quadrature-Galerkin approximations to solutions of elliptic differential equations[END_REF] were concerned with the influence of quadrature error on the right hand side only while the papers [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF], [START_REF] Fix | Effects of quadrature errors in finite element approximation of steady state, eigenvalue, and parabolic problems, The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations[END_REF] consider setting up both the left and right hand sides by quadrature. An advantage that the Ritz method has over collocation is that less continuity for the solution is required in order to achieve best rates. For (2.1)-(2.2), collocation methods require two more continuous derivatives than the Ritz method. Moreover, from the standpoint of approximation theory, the Ritz method requires minimal smoothness. However, when the Ritz method is implemented with a quadrature scheme, this advantage is lost. See Douglas and Dupont [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF].

Most of the Ritz-Galerkin papers consider linear problems only. However, see [7 4 ]. This is not always a theoretical limitation since the techniques used by de Boor and Swartz [START_REF] Deboor | Collocation at Gaussian points[END_REF], H. B. Keller [START_REF]Approximation methods for nonlinear problems with application to two-point boundary value problems[END_REF] and Vainikko [START_REF]Galerkin's perturbation method and the general theory of approximate methods for nonlinear equations[END_REF] can be used to extend results for linear problems to nonlinear problems.

Ritz-Galerkin methods exhibit superconvergence at the mesh points, see Douglas and Dupont [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF]. The Ritz-Galerkin method also has the property that after the approximation Yn has been computed, certain auxiliary computations can be performed to achieve higher accuracy at selected points. See, for example, Wheeler [START_REF]A Galerkin procedure for estimating the flux for two-point boundary value problems[END_REF], Douglas and Dupont [START_REF]Superconvergence for Galerkin methods for the two-point boundary problem via local projections[END_REF], and Dupont [START_REF] Dupont | A unified theory of superconvergence for Galerkin methods for two-point boundary value problems[END_REF]. These papers treat linear, second order problems.

2.3. Least squares. The method of least squares approximates the solution to (2.1)-(2.2) by solving for Yn E So(r, k, a) so that (2.3.1) r 1 (-y~ +aoy~ +atyn)(-v7 +aov: +atV;) dx = ( f(-v7 +aov: +a;V;) dx Jo Jo for all V; as in (2.2.1 ). Basic references on the method of least squares are Baker [START_REF] Baker | Simplified proofs of error estimates for the least squares method for Dirichlefs problem[END_REF], Russell and Varah [START_REF] Russell | A comparison of global methods for two-point boundary value problems[END_REF], Sammon [START_REF] Sammon | A discrete least squares method[END_REF] and Ascher [START_REF] Uri Ascher | Discrete least squares approximations for ordinary differential equations[END_REF]. The first three of these papers treat 2mth order linear problems with Dirichlet boundary conditions. They obtain optimal error estimates in the L 2 norm. Sammon considers the use of Gaussian quadrature to perform the integrals as does Ascher [START_REF] Uri Ascher | Discrete least squares approximations for ordinary differential equations[END_REF]. However, the paper of Ascher considers general nonlinear mth order equations plus general linear boundary conditions. These two papers both require quasi-•uniform meshes. Ascher establishes his error bounds for the L(" norm. The quasi-uniform assumption for smooth splines as given by Ascher is necessary since he relies on an interesting bound in the L co norm for the orthogonal projection operator into splines established by Douglas, Dupont and Wahlbin [START_REF] Douglas | Optimal L 00 error estimates for Galerkin approximations to solutions of two-point boundary value problems[END_REF]. See also deBoor [START_REF]A bound on the L 00 -norm of the L 2 -approximation by splines in termsofa global mesh ratio[END_REF]. Superconvergence results are also obtained in [START_REF] Uri Ascher | Discrete least squares approximations for ordinary differential equations[END_REF].

It is concluded [START_REF] Uri Ascher | Discrete least squares approximations for ordinary differential equations[END_REF] that collocation is generally superior to discrete least squares for ordinary differential equations. Computational examples are given by Serbin [START_REF] Serbin | Computational investigations of least-squares type methods for the approximate solution of boundary value problems[END_REF] verifying the fact that for the same order equation, the condition number for the matrix problem resulting from the method of least squares is the square of that for the Ritz-Galerkin method.

Method of moments.

There are a variety of methods that can be put in this category. The method of moments finds an approximation Yn E S 0 (r, k, a) so that where {cfJ;(x)} is a basis for S(r', k', a) for suitable r' and k'. In principle, there is no need for the ¢; 's to span even a space of splines. One particular method was considered by deBoor [START_REF] Deboor | The method of projections as applied to the numerical solution of two-point boundary value problems using cubic splines[END_REF] and Lucas and Reddien [START_REF]A high order projection method for nonlinear two-point boundary value problems[END_REF]. The integers r, k were chosen to be 3 and 2 respectively and r', k' were chosen to be 1 and 0. The paper [START_REF]A high order projection method for nonlinear two-point boundary value problems[END_REF] considers generalizations to general 2mth order problems with Dirichlet boundary conditions and achieves optimal rates of convergence in the L co norm with a quasi-uniform assumption on the mesh. Compared to the Ritz method, less computation is required to set up the method by quadrature. A general theory of similar methods for elliptic problems is given by Mock [START_REF] Mock | Projection methods with different trial and test spaces[END_REF] including superconvergence results. This method has been considered in the setting of parabolic problems by Douglas, Dupont and Wheeler [START_REF] Douglas | H 1 -Galerkin methods for the Laplace and heat equations[END_REF] where it is called an H 1 -Galer kin procedure. Also included in this class is the H 1 -Galerkin procedure of Rachford and Wheeler [START_REF] Rachford | An H-1 -Galerkin procedure for the two-point boundary value problem[END_REF], Kendall and Wheeler [START_REF] Kendall | A Crank-Nicolson H-1 -Galerkin procedure for parabolic problems in a single space variable[END_REF], and Douglas, Dupont and Wheeler [START_REF]Some superconvergence results for an H-1 -Galerkin procedure for the heat equation[END_REF]. The analysis is restricted to second order problems but general separated boundary conditions are considered. The lead order part of the equation needs to be elliptic. The method approximates oscillatory solutions well. See [START_REF] Rachford | An H-1 -Galerkin procedure for the two-point boundary value problem[END_REF] for numerical experiments.

Write (2.1) as Ly

2.5.

Other. There are a number of other methods with attractive features that do not fit into any of the preceding categories. Indeed, some of these methods cannot properly be called projection methods but are modifications of projection methods.

One projection method is the C 0 -collocation-finite element scheme described by Diaz [START_REF] Diaz | A collocation-Galerkin method for two-point boundary value problems using continuous piecewise polynomial spaces[END_REF] and Wheeler [START_REF]A C 0 -collocation-finite element method for two-point boundary value problems and one space dimensional parabolic problems[END_REF]. This method chooses Yn in S0 (r, 0, A) so that (2.5.1) --y~ (g;;) + ao(~;; )y~ (g;;) + a1 (~;; )yn (g;;) = f(~;i) and (2.5.2) r (y~v: + aoy~v; +atYnV;) dx = r fv; dx where ~ii are the translated roots of the monic Jacobi polynomial of degree r-1, and{v;} spans S0 (1, 0, A). This method achieves optimal rates of convergence in the L oo norm for arbitrary meshes and, in contrast to pure collocation methods, requires only minimal smoothness on the solution in order to a_chieve this optimal rate. Superconvergence results (better than for collocation) are obtained and extrapolation procedures as in Dupont [START_REF] Dupont | A unified theory of superconvergence for Galerkin methods for two-point boundary value problems[END_REF] are also developed. Similar results for a combination of collocation and the H-1 -Galerkin method are given by Dunn and Wheeler [START_REF] Dunn | Some co/location-Galerkin methods for two-point boundary value problems[END_REF].

Another method of interest is the extrapolated collocation method using C 2 -cubic splines given by Fyfe [START_REF] Fyffe | The use of cubic splines in the solution of two-point boundary value problems[END_REF], Archer and Diaz [START_REF] Juuo | A family of modified collocation methods for second order two-point boundary value problems[END_REF], and Daniel and Swartz [START_REF] Daniel | Extrapolated collocation for two-point boundary value problems using cubic splines[END_REF]. This method requires uniform meshes and applies to general second-order problems. Optimal rates of convergence are obtained with a minimal set of equations, but again extra smoothness is required. The solution to (2.1) with general boundary conditions must lie in C 6 . Equations that a cubic spline interpolant of the solution satisfies to high accuracy are derived and then solved numerically. We mention here also a related O(h 4 ) method using C 2 -cubics of Albasiny and Hoskins [START_REF] Hoskins | Cubic spline solutions to two-point boundary value problems[END_REF] which also requires a uniform mesh.

Finally, we mention the finite difference methods of Doedel [START_REF] Doedel | The construction of finite difference approximations to ordinary differential equations[END_REF], [START_REF]Finite difference methods for nonlinear two-point boundary value problems[END_REF] and Lynch and Rice [START_REF] Lynch | A higher order difference method for differential equations[END_REF]. Although one approach to these methods uses ideas of classical finite differences, Doedel [START_REF]Finite difference methods for nonlinear two-point boundary value problems[END_REF] has shown they can be interpreted as collocation methods using overlapping piecewise polynomial functions.

2.6. Interdependence. The methods cited above are in some cases closely related, and possibly identical, even though they have been derived from different starting points. In the quadrature-Galerkin method, if the total number of quadrature points used is equal to dim S0(r, k, A) and the quadrature weights are nonzero, then collocation at the quadrature points is equivalent to it. Generally, however, more quadrature points are used [START_REF] Russell | A comparison of global methods for two-point boundary value problems[END_REF]. For least squares, normally more than dim S0 (r, k, A) quadrature points are used and then the method can be viewed as an overdetermined collocation scheme whose equations have been scaled and solved by discrete least squares. See Russell and Varah [START_REF] Russell | A comparison of global methods for two-point boundary value problems[END_REF] and Ascher [START_REF] Uri Ascher | Discrete least squares approximations for ordinary differential equations[END_REF].

The equivalence of the quadrature-Galerkin method when the quadrature points are chosen to be Gauss points with collocation at Gauss points has important theoretical implications. Douglas and Dupont [START_REF]Galerkin approximations for the two-point boundary value problem using continuous, piecewise polynomial spaces[END_REF] develop their proofs of convergence of collocation from the quadrature-Galerkin formulation. This approach is extendable to more general problems whereas the projection method approach is more difficult. For parabolic problems, see Douglas and Dupont [START_REF] Douglas | Collocation methods for parabolic equations in a single space variable based on C -piecewise-polynomial spaces[END_REF], and for hyperbolic problems, see Houstis [START_REF] Housns | Application of method of collocation on lines for solving nonlinear hyperbolic problems[END_REF]. Hulme [START_REF] Hulme | One-step piecewise polynomial Galerkin methods for initial value problems[END_REF] made this observation for the initial value problem for ordinary differential equations.

Nonspline bases.

Projection methods can of course be applied to (2.1)-(2.2) without using splines. For example, one can use polynomials of degree n + 2 satisfying the boundary conditions (2.2) and use collocation with collocation points chosen to be Chebyshev points translated to [0, 1]. See Vainikko [START_REF] Vainikko | Convergence of the collocation method for nonlinear differential equations[END_REF], Kantorovich and Akilov [START_REF] Kantorovich | Functional Analysis in Normed Spaces[END_REF] or Finlayson [START_REF] Finlayson | The Method of Weighted Residuals and Variational Principles[END_REF]. One can also use polynomials with Galerkin's method. See, for example, Urabe [START_REF] Urabe | Numerical solution of multi-point boundary value problems in Chebychev series. Theory and method[END_REF] and Urabe and Reiter [START_REF] Urabe | Numerical computation of nonlinear forced oscillations by Galerkin's procedure[END_REF] and the books by Kantorovich and Krylov [START_REF] Kantorovich | Approximate Methods of Higher Analysis[END_REF], Mikhlin [START_REF] Mikhlin | The Numerical Performance of Variational Methods[END_REF] and Finlayson [START_REF] Finlayson | The Method of Weighted Residuals and Variational Principles[END_REF].

Projection methods.

In this section we explain why the preceding methods are called projection methods and then give a few basic results that enable one to begin their analysis.

.. Projection operators.

Let X be a normed linear space. A projection operator P on X is a linear, idempotent (P 2 = P) mapping from X into itself. We will be concerned only with projections of finite rank. Let X' denote the algebraic dual of X. Then the following characterization result is known [START_REF] Deboor | Linear Operators, part I[END_REF].

LEMMA 3.1.1. Let P, be a projection on X. Define X, = PnX. Let P~ be the conjugate operator associated with Pn and define X~ = P~X'. Then

{x E Xn: x'(x) = 0 for all x' EX~}={O}.

Conversely, given subspaces Xn and X~ of X and X' respectively of the same dimension and satisfying (3.1.2), then a unique projection operator Pn is defined by the relations Pnx = Xn if and only if Xn E Xn and x'(xn) = x'(x) for all x' EX~.

We have not required the linear functionals x' to be continuous. However, the following result holds [START_REF] Deboor | Linear Operators, part I[END_REF].

LEMMA 3 .1.2. Pn is bounded if and only if X~ c X*, the dual space of continuous linear functionals on X.

The projection operators considered here will be mappings generally from L 2 [0, 1], C[O, 1] or certain Sobolev spaces onto S(r, k, .:l). Given a sequence of such projections, {Pn}, it is desirable, but not necessary [START_REF]A high order projection method for nonlinear two-point boundary value problems[END_REF], to have sequences satisfying SUPn IIPnll<oo.

We next show how to bound the projections. Suppose that the sequence {Pn} is formed by adding vectors to Xn and functionals to X~, i.e. Xn =span {!/>I.• • • , !f>n} and X~ =span {At,•••, An}. Then Pnx = I7=t a~"l!/>; and Pnx satisfies Thus bounding IIPnll can be broken down into the following steps. First note IIPnxll~ (max laj"ll) L~=tii«Pdl. A basis{!/>;} with L~=tii«Pdl~const. would be convenient here. Actually, I7=t !/>; ~const. with!/>; ~0 would do. Then we need to bound IIA~1 IIoo if we know max /AJ/ ~ const. /It!/ in order to bound the projectors. This can be a difficult matrix problem and is dependent on a detailed knowledge of specific bases for X". For an excellent discussion of these matters for the case that X" is a spline space, see de Boor [START_REF] Deboor | Bounding the error in spline interpolation[END_REF].

I a~"lAi(!/>;)=Ai(f), j= 1, • • •, n.
Projections Pn may be thought of as general interpolation mappings since Pnf interpolates fin the sense that A;({)= A;(Pnf>• The following estimate of the distance between a vector and its projection is useful. LEMMA 3.1.4. 1/x-Pnx/1 ~//I-Pn/1 dist (x, Xn).

A uniformly bounded (in norm) sequence of projections achieves best asymptotic rates of convergence. If X is a Banach space, a sequence of projections will be uniformly bounded in norm if they converge strongly to the identity operator on X.

Projection methods.

Let A be a linear operator with domain in a normed linear space X and range in a normed linear space Y. Let Xn be a finite dimensional subspace of X and Yn a finite dimensional subspace of Y* with dim Xn =dim Y" < oo.

We assume A (Ax) = 0 for x E Xn and all A E Y* implies x = 0. DEFINITION 3.

.6)

If A is not bounded, then there is no guarantee that the functionals A' A are bounded and so Pn may be bounded while On is not.

Let Zn be any subspace of Y with dimension equal to the dimension of Y" and so that for Zn E Z"' A (zn) = 0, all A in Yn implies Zn = 0. Then, Zn and Yn define a projection, R"' and (3.2.2) may be written as and convergence results follow from the properties of the projections Pn. Also note (3.2.12) There are many special cases of the operator A that are easy to handle. We consider two. Suppose A = I+ T where T is compact on X~ X where X is a Banach space. Then our problem may be written as (3.2.13)

(I+ T)v = f
and our numerical method may be written following ( and so (I+ RnT)-1 exists for n sufficiently large and supn 1\(I + RnT)-1 1\ < oo is valid.

Apply now Rn to both sides of (3.2.13), subtract this from (3.2.14) and subtract v from both sides to get the equation (3.2.16) We can now bound the quantities in (3.2.11) and have proved the following theorem. THEOREM 3.2.17. LetT be a completely continuous mapping on a Banach space X into itself, let (I+ T)-1 exist, and let {Rn} be a sequence of projections on X with RnX = Xn so that Rn converges strongly to the identity on X. Then for all n sufficiently large, the equation Vn + RnTVn = Rnf, with Vn E Xn. has a unique solution Vn for any f EX. Let v solve v + Tv =f. Then (3.2.18)

1\v-Vn\1 ~ 1\(I + Rn)-1 1\ • 1\v-Rnv\1~ const. \II-Rn\1 dist (v, Xn).
Several improvements on this basic and important theorem are immediately possible. One is by a Newton's method argument to nonlinear mappings T that are completely continuous and continuously Frechet differentiable. We omit statements of these important nonlinear results here, but refer the reader to Vainikko [START_REF]Galerkin's perturbation method and the general theory of approximate methods for nonlinear equations[END_REF], deBoor and Swartz [START_REF] Deboor | Collocation at Gaussian points[END_REF], and Keller [START_REF]Approximation methods for nonlinear problems with application to two-point boundary value problems[END_REF]. For the Galerkin method in the nonlinear case, analysis can be done using monotone operator theory, e.g. Ciarlet, Shultz, Varga [START_REF]Numerical methods of high order accuracy for nonlinear boundary value problems[END_REF].

Suppose our given equation has the form

(3.2.19) Ax+Bx =f
where A and B are mappings, possibly unbounded, from X into Y but with A -l bounded and with a constant c > 0 so that (3.2.20)

1\BA-1 1\~c.

Assume (A+ B)-1 exists and is bounded. Given a projection method defined by Xn and

Yn. define Zn = AXn and write the approximation equations (3.2.21)

In the case of the Galerkin method with continuous splines for (2.1)-(2.2), Natterer [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF] established the bound (4.2.2) IIY-YniiL =en~ C max (h;+ 1 lly'+ 1 lk =u,l)• ' Generalizations of this result to higher order equations are also given in [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF]. The integrals required for the method were assumed done exactly. It was also indicated there that a bound of the form (4.2.2) does not hold for collocation at Gauss points. The existence of bounds such as (4.2.1) seems at present to be more important computationally than superconvergence, although they occur together.

Remarks.

We close with a few comments about current research on projection methods for two-point boundary value problems. There are many such methods using splines, each with its own special feature which makes it competitive on certain types of problems. Collocation at Gauss points is applicable to general vector systems which in combination with its good convergence properties makes it an excellent method. Basic codes for its implementation are easy to write and general ones are being written for publication. In the setting of second order problems, the choice of a method is not clear. Available ones such as the H-1 -Galerkin and C 0 -collocation-finite element use low order continuity classes of splines and thus would seem to have a good chance to approximate well solutions to problems with mild boundary layers. Their theoretical properties are superior. However, there have not been enough computations done to make a clear judgement. Extensions of these methods to general two-point boundary value problems remains open. The low order continuity class methods are also potentially attractive in higher dimensions. Some work has been done on extending them, but much more is needed.

One key point for the efficiency of the application of these methods (or any other discretization) is the selection of the mesh and the related estimation of the error. For this, local error estimates are important. Development of adaptive codes with mesh selection strategies is currently an active research area.

( 2 .

 2 4.1) f (-y~ +any~ +atYn)cP;(x) dx = /(x)cfJ;(x) dx I Jl Jo o

  = f and let L *denote the formal adjoint of L. This method develops approximations Yn E S(r, k, A) by solving (2.4.2) f 1 YnL*v;dx = f 1 fv;dx Jo Jo where {v;} forms a basis for S(r + 2, k + 2. A) n {v: v'(O) = v'( 1) = 0}. Optimal rates of convergence are obtained in the L 2 norm and superconvergence results are obtained for the case k = -1.

i=l

  Define An= [a;i] with a;i = A;(!/>i). The definition of Pn by Xn and X~ and condition (3.1.2) imply (3.1.3)

( 3 .

 3 2.4) holds. Alternatively, define the projection On through Xn and A' Yn. Then (3.2.2) may be written as (3.2.5) (A'A)x,. = Af= .>o..Ax = A'A.x, or as (3.2

( 3 . 2 . 7 )

 327 These projections can be related by the identities (3.2.8) Pn = (Rn/AxJ-l Rn and (3.2.9) These operator formulations can be used to give an error analysis. Since (3.2.10) then (3.2.11) \\x-Xn\\ ~ \\A-1 \\\\I-Pn\\ dist (/, AXn), \\Ax-Axn\1 ~\\I-Pn\1 dist (f, AXn)

  2.1. projection method approximates the solution x of the equation Ax = f by Xn E Xn where Xn is defined as the solution of the equations (3.2.2) all A E Yn• The setting for this definition can obviously be generalized. Several projection operators can be associated with (3.2.2). Using Lemma 3.2.2, define the projection Pn through AXn and Yn. Then (3.2.2) may be written as

	(3.2.3)
	and the representation formula

  Define Rn so that it has range Xn; Eq. (3.2.14) becomes Vn + RnTVn = Rnf• Suppose Rn converges strongly to the identity operator on X. Then 1\Rn\1 ~ const. and by Lemma 3.1.4 we have that approximation by Rn achieves best rates of convergence. With T compact and if (I+ T)-1 exists, then (I+ T)-1 is automatically bounded. It follows that(3.2.15)

	3.2.7) as
	(3.2.14)

as (3.2.22)

Defining the projection Rn by Zn and Ym we see that (3.2.22) becomes (3.2.23) Vn + R,,BA-1 Vn = Rnf.

If BA -! is compact, then we may use Theorem 3. 2.17.

This analysis applies to many of the examples in § 2. Equations ( 2 As a consequence of formula (3.2.9) in this setting, we obtain LEMMA 3.2.24.

This lemma is contained in deBoor and Swartz [START_REF] Deboor | Collocation at Gaussian points[END_REF] and also Natterer [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF]. As a consequence of it, the boundedness of On can be deduced from a study of Rn. The practical implication is that one need only consider the projector associated with the lead order part of the differential operator.

Many variations on Theorem 3.2.18 and Lemma 3.2.24 are possible. We cite here Vainikko [START_REF]Galerkin's perturbation method and the general theory of approximate methods for nonlinear equations[END_REF], Polskii [START_REF] Polskij | Projection methods in applied mathematics[END_REF], Petryshn [START_REF] Petryshyn | Direct and iterative methods for the solution of linear operator equations in Hilbert space[END_REF], Browder [START_REF] Browder | Approximation-solvability of nonlinear functional equations in normed linear spaces[END_REF], Krasnoselskii et al. [START_REF] Krasnoselskii | Niiherungsverfahren zur Losung von Operatorgleichungen[END_REF], and Witsch [START_REF] Witsch | Konvergenzaussagen fur l'roJektzonsverfahren bei linearen Operatoren[END_REF] as important references. Kramarz [START_REF] Lvis Kramarz | Global approximations of solutions to initial value problems[END_REF] replaces projections with general mappings using the theory of collectively compact operators.

Consider as another example the Ritz-Galerkin method for (py')'

with the Hilbert space norm [START_REF] Aubin | Approximation of Elliptic Boundary-ValLie Problems[END_REF]. Here f is considered in, say, L 2 , but f could be in H-1 , the dual of Hb. Since pis positive, J~ py'v' dx defines a coercive bilinear form on Hb and can be written for fixed y as (Ay, v) in the duality product on H 1 with A linear, A -1 bounded, and A mapping onto H • 1 • See Aubin [START_REF] Aubin | Approximation of Elliptic Boundary-ValLie Problems[END_REF] or Strang and Fix [START_REF] Strang | An Analysis of the Finite Element Method[END_REF] for details. Define the Ritz-Galerkin projection by the subspace AS0 (k, r, a) and the Improvements in the bound implied by (3.2.27) for both the L 2 and L oo -norms are possible using a duality argument. See Aubin [START_REF] Aubin | Approximation of Elliptic Boundary-ValLie Problems[END_REF], Blair [START_REF] Blair | Error bounds for the solution of nonlinear two-point boundary value problems by Galerkin's method[END_REF], Nitsche [START_REF] Nitsche | Bin Kriterium fiir die Quasi-Optimalitiit des Ritzschen Verfahrens[END_REF], Dupont, Douglas and Wahlbin [START_REF] Douglas | Optimal L 00 error estimates for Galerkin approximations to solutions of two-point boundary value problems[END_REF], Wheeler [START_REF] Wheeler | An optimal L 00 error estimate for Galerkin approximation to two-point boundary value problems[END_REF] and Schultz [START_REF] Schultz | Spline Analysis[END_REF]. Theoretically treating the Ritz-Galerkin method the same way as collocation leads to projections that seem impossible to bound [START_REF] Deboor | The method of projections as applied to the numerical solution of two-point boundary value problems using cubic splines[END_REF].

The method of least squares can also be formulated as an operator equation with projections. Applied to ( Thus basic convergence results follows from Theorem 3.2.17. Of course, 11Pnlk2 = 1.

However, IIP~~Ik oc• ~ const. is also known for quasi-uniform meshes and arbitrary r, k. See Douglas, Dupont and Wahlbin [START_REF] Douglas | Optimal L 00 error estimates for Galerkin approximations to solutions of two-point boundary value problems[END_REF] and deBoor [START_REF]A bound on the L 00 -norm of the L 2 -approximation by splines in termsofa global mesh ratio[END_REF].

If one uses collocation at the Chebyshev points with polynomials as described in § 2. 7, the projections Rn defined in analogy with spline collocation schemes satisfy on C

This lack of uniform boundedness for the projections does not prevent convergence of the method. For the modification of Theorem 3.2.17 that will treat this case see [START_REF] Vainikko | Convergence of the collocation method for nonlinear differential equations[END_REF]. 4. Superconvergence. Some methods give higher order convergence rates at certain points than might be anticipated from global approximation rates. We mention here some important examples and then discuss implications of these results for more refined error estimates and the development of adaptive codes.

Examples.

For problem (2.1)-(2.2), suppose we solve for Yn E S0(r, 1, ~)and collocate at Gaussian points as defined in § 2.1. Then the following theorem holds. Let the coefficients a 0 and a 1 be in C 2 k and let y be in C 2 + 2 k. Then i = 0, 1. Thus, if k = 4, i.e. quintic splines are used, convergence at the mesh points is O(h 8 ) while global convergence is O(h 6 ). In the case k = 2, i.e. cubic splines, there is no improvement. This theorem in the quintic case requires that the solution have ten continuous derivatives.

We contrast this with the Ritz-Galerkin method. Using Eq. (2.2.2) with continuous splines, we have the next theorem. THEOREM 4.1.2 (Douglas and Dupont). Let a 0 and a 1 be in C'-\ r?;. 1, with a!> in L 00 and let f E C. Suppose the solution y of (2.1)-(2.2) is in C'+ 1 (1) and that Yn is chosen from S 0 (r, 0, ~) solving (2.2.2). Then

Theorem 4.2.2 does not require additional smoothness to achieve superconvergence, and in the cubic spline case, r = 3, superconvergence occurs. However, if one implements (2.2.2) by using r-point Gauss quadrature, y is implicitly required to be in H2r+2.

Both the proofs of Theorem 4.1.1 and Theorem 4.1.2 rely on the low order continuity class of the splines used in an essential way.

Other superconvergence results are known. For more facts about collocation at Gauss points, see Russell and Christiansen [START_REF]Error analysis for spline collocation methods with application to knot selection[END_REF]. The C 0 -collocation method of Diaz [START_REF] Diaz | A collocation-Galerkin method for two-point boundary value problems using continuous piecewise polynomial spaces[END_REF] and Wheeler [START_REF]A C 0 -collocation-finite element method for two-point boundary value problems and one space dimensional parabolic problems[END_REF] Converges at the meash of order O(h 2 ') for arbitrary mesh spacings. The H-1 method of Rachford and Wheeler [START_REF] Rachford | An H-1 -Galerkin procedure for the two-point boundary value problem[END_REF] and Kendall and Wheeler [START_REF] Kendall | A Crank-Nicolson H-1 -Galerkin procedure for parabolic problems in a single space variable[END_REF] achieves superconvergence at the Gauss points in the case k = -1. See equation (2.4.2). Convergence there is one order bctkf than the best rate.

Dupont [START_REF] Dupont | A unified theory of superconvergence for Galerkin methods for two-point boundary value problems[END_REF] has shown how performing certain auxiliary computations using Galerkin solutions (also H-1 and H 1 -Galerkin) can give superconvergent approximations to the value of the solution and its derivative at any points. Arbitrary continuity classes for the splines are considered. See also Diaz [START_REF] Diaz | A collocation-Galerkin method for two-point boundary value problems using continuous piecewise polynomial spaces[END_REF], Wheeler [START_REF]A C 0 -collocation-finite element method for two-point boundary value problems and one space dimensional parabolic problems[END_REF], Kendall and Wheeler [START_REF] Kendall | A Crank-Nicolson H-1 -Galerkin procedure for parabolic problems in a single space variable[END_REF], and Douglas and Dupont [START_REF]Superconvergence for Galerkin methods for the two-point boundary problem via local projections[END_REF].

Refined error bounds.

If superconvergence occurs, it is possible to modify the argument that produced the superconvergence to obtain refined error bounds that indicate local dependence for the error. Suppose one uses collocation at Gauss points for (2.1)-(2.2). Then with suitable smoothness, deBoor [START_REF] Deboor | Good approximation by splines with variable knots[END_REF] has shown (see also Christiansen and Russell [START_REF]Error analysis for spline collocation methods with application to knot selection[END_REF] and Ascher, Christiansen and Russell [START_REF] Ascher | A collocation solver for mixed order systems of boundary value problems[END_REF]) that (4.2.1) Thus to lead order the method is local and an estimate for D'+ 1 y can lead to algorithms for equidistributing the error. See Pereyra and Sewell [START_REF] Sewell | Mesh selection for discrete solution of boundary value problems in ordinary differential equations[END_REF] and [START_REF] Ascher | A collocation solver for mixed order systems of boundary value problems[END_REF], [START_REF] Christiansen | Adaptive mesh selection strategies for solving boundary problems[END_REF], [START_REF]Error analysis for spline collocation methods with application to knot selection[END_REF] and [START_REF] Deboor | Good approximation by splines with variable knots[END_REF]. Similar results are known for the Galerkin method [START_REF] Frank Natterer | Uniform convergence of Galerkin's method for splines on highly nonuniform meshes[END_REF], for the H-1 -Galerkin method [START_REF] Rachford | An H-1 -Galerkin procedure for the two-point boundary value problem[END_REF], and the C 0 -collocation-Galerkin method [START_REF]A C 0 -collocation-finite element method for two-point boundary value problems and one space dimensional parabolic problems[END_REF].