Adaptive Techniques for Spline Collocation

We integrate optimal quadratic and cubic spline collocation methods for second-order two-point boundary value problems with adaptive grid techniques, and grid size and error estimators. Some adaptive grid techniques are based on the construction of a mapping function that maps uniform to non-uniform points, placed appropriately to minimize a certain norm of the error. One adaptive grid technique for cubic spline collocation is mapping-free and resembles the technique used in COLSYS (COLNEW) [2], [4]. Numerical results on a variety of problems, including problems with boundary or interior layers, and singular perturbation problems indicate that, for most problems, the cubic spline collocation method requires less computational effort for the same error tolerance, and has equally reliable error estimators, when compared to Hermite piecewise cubic collocation. Comparison results with quadratic spline collocation are also presented.     

Quintic splines method for second-order boundary value problems

Abstract

We develop a numerical method for computing smooth approximations to the solution of a system of second-order boundary value problems associated with obstacle, unilateral and contact problems based on uniform mesh quintic splines. It is shown that this method gives better approximations than those produced by other collocation, finite-difference and spline methods. A numerical example is given to illustrate the applicability of the new method.     

Cubic Spline Collocation for Volterra Integral Equations

In the standard step-by-step cubic spline collocation method for Volterra integral equations an initial condition is replaced by a not-a-knot boundary condition at the other end of the interval. Such a method is stable in the same region of collocation parameter as in the step-by-step implementation with linear splines. The results about stability and convergence are based on the uniform boundedness of corresponding cubic spline interpolation projections. The numerical tests given at the end completely support the theoretical analysis. Received: January 15, 2002; revised July 27, 2002 Published online: December 19, 2002     

Quadratic spline quasi-interpolants and collocation methods

Univariate and multivariate quadratic spline quasi-interpolants provide interesting approximation formulas for derivatives of approximated functions that can be very accurate at some points thanks to the superconvergence properties of these operators. Moreover, they also give rise to good global approximations of derivatives on the whole domain of definition. From these results, some collocation methods are deduced for the solution of ordinary or partial differential equations with boundary conditions. Their convergence properties are illustrated and compared with finite difference methods on some numerical examples of elliptic boundary value problems.     

Quadratic spline quasi-interpolants and collocation methods

Univariate and multivariate quadratic spline quasi-interpolants provide interesting approximation formulas for derivatives of approximated functions that can be very accurate at some points thanks to the superconvergence properties of these operators. Moreover, they also give rise to good global approximations of derivatives on the whole domain of definition. From these results, some collocation methods are deduced for the solution of ordinary or partial differential equations with boundary conditions. Their convergence properties are illustrated and compared with finite difference methods on some numerical examples of elliptic boundary value problems.     

Symplectic algorithms with mesh refinement for a hypersensitive optimal control problem

A symplectic algorithm with nonuniform grids is proposed for solving the hypersensitive optimal control problem using the density function. The proposed method satisfies the first-order necessary conditions for the optimal control problem that can preserve the structure of the original Hamiltonian systems. Furthermore, the explicit Jacobi matrix with sparse symmetric character is derived to speed up the convergence rate of the resulting nonlinear equations. Numerical simulations highlight the features of the proposed method and show that the symplectic algorithm with nonuniform grids is more computationally efficient and accuracy compared with uniform grid implementations. Besides, the symplectic algorithm has obvious advantages on optimality and convergence accuracy compared with the direct collocation methods using the same density function for mesh refinement.     

The discrete minimum principle for quadratic spline discretization of a singularly perturbed problem

We consider a singularly perturbed boundary value problem with two small parameters. The problem is numerically treated by a quadratic spline collocation method. The suitable choice of collocation points provides the discrete minimum principle. Error bounds for the numerical approximations are established. Numerical results give justification of the parameter-uniform convergence of the numerical approximations.     

Spline methods for solving system of second-order boundary-value problems

In this paper, we use cubic polynomial splines to derive some consistency relations which are then used to develop a numerical method for computing smooth approximations to the solution and its derivatives for a system of second order boundary value problems associated with obstacle, unilateral and contact problems. We show that the present method gives approximations which are better than that produced by other collocation, finite difference and spline methods. Numerical example is presented to illustrate the applicability of the new method.     

Finite-difference technique based on exponential splines for the solution of obstacle problems

In this paper, we introduce a new technique based on cubic exponential spline functions for computing approximations to the solution of a system of fourth-order boundary value problems associated with obstacle, unilateral and contact problems. It is shown that the present method is of order two and four and gives approximations which are better than those produced by other collocation, finite difference and spline methods. Numerical evidence is presented to illustrate the applicability of the new methods.     

Discrete least-squares technique for eigenvalues. Part I: The one-dimensional case

A discrete least-squares technique for computing the eigenvalues of differential equations is presented. The eigenvalue approximations are obtained in two steps. Firstly, initial approximations of the desired eigenvalues are computed by solving a quadratic matrix eigenvalue problem resulting from the least-squares method applied to the equation under consideration. Secondly, these initial approximations, being of sufficient accuracy in some cases, are improved by using the Gauss-Newton method. Results from numerical experiments are reported that show great efficiency of the proposed technique in solving both regular and singular one-dimensional problems. The high flexibility of the technique enables one to use also the multidomain approach and the trial functions not satisfying any of the prescribed boundary conditions.     

Iterative methods for domain decomposition using spectral tau and collocation approximation

In this paper we consider the numerical approximation of elliptic problems by spectral methods in domains subdivided into substructures. We review an iterative procedure with interface relaxation, reducing the given differential problem to a sequence of Dirichlet and mixed Neumann-Dirichlet problems on each subdomain. The iterative procedure is applied to both tau and collocation spectral approximations. Two optimal strategies for the automatic selection of the relaxation parameter are indicated. We present several numerical experiments showing the convergence properties of the iterative scheme with respect to the decomposition. A multilevel technique for domain decomposition methods is proposed.     

Numerische Lösung gewöhnlicher Differentialgleichungen mit Splinefunktionen

In this paper a general procedure to obtain spline approximations for the solutions of initial value problems for ordinary differential equations is presented. Several well-known spline approximation methods are included as special cases. It is common practice to partition the interval for which the initial value problem is defined into equidistant subintervals and to construct successively the spline approximation; thereby the spline function has to satisfy certain conditions at the knots. In the general procedure presented here additional knots are admitted in every subinterval. At these points which need not be equally spaced the spline approximation has to fulfill analogous conditions as at the original knots. Convergence and divergence theorems are proved; especially the influence of the additional knots on convergence and divergence of the method is investigated.     

Quadratic spline methods for the shallow water equations on the sphere: Collocation

In this study, we present numerical methods, based on the optimal quadratic spline collocation (OQSC) methods, for solving the shallow water equations (SWEs) in spherical coordinates. The error associated with quadratic spline interpolation is fourth order locally at certain points and third order globally, but the standard quadratic spline collocation methods generate only second-order approximations. In contrast, the OQSC methods generate approximations of the same order as quadratic spline interpolation. In the one-step OQSC method, the discrete differential operators are perturbed to eliminate low-order error terms, and a high-order approximation is computed using the perturbed operators. In the two-step OQSC method, a second-order approximation is generated first, using the standard formulation, and then a high-order approximation is computed in a second phase by perturbing the right sides of the equations appropriately. In this implementation, the SWEs are discretized in time using the semi-Lagrangian semi-implicit method, and in space using the OQSC methods. The resulting methods are efficient and yield stable and accurate representation of the meteorologically important Rossby waves. Moreover, by adopting the Arakawa C-type grid, the methods also faithfully capture the group velocity of inertia-gravity waves.     

A sparse collocation method for solving time-dependent HJB equations using multivariate B-splines

This paper presents a sparse collocation method for solving the time-dependent Hamilton–Jacobi–Bellman (HJB) equation associated with the continuous-time optimal control problem on a fixed, finite time-horizon with integral cost functional. Through casting the problem in a recursive framework using the value-iteration procedure, the value functions of every iteration step is approximated with a time-varying multivariate simplex B-spline on a certain state domain of interest. In the collocation scheme, the time-dependent coefficients of the spline function are further approximated with ordinary univariate B-splines to yield a discretization for the value function fully in terms of piece-wise polynomials. The B-spline coefficients are determined by solving a sequence of highly sparse quadratic programming problems. The proposed algorithm is demonstrated on a pair of benchmark example problems. Simulation results indicate that the method can yield increasingly more accurate approximations of the value function by refinement of the triangulation.     

Uniform Pointwise Convergence of Finite Difference Schemes Using Grid Equidistribution

A singularly perturbed quasilinear two-point boundary value problem is considered. The problem is discretized using a simple upwind finite difference scheme on adapted meshes using grid equidistribution of monitor functions. We derive sufficient conditions on the monitor function that guarantee uniform convergence in the discrete maximum norm no matter how small the perturbation parameter is. These results can be used to deduce uniform convergence of the scheme for a number of layer-adapted meshes. We also propose an adaptive procedure for the numerical treatment of the boundary value problem. Numerical experiments for the schemes are presented. Received November 12, 1999; revised April 20, 2000     

A class of methods based on a septic non-polynomial spline function for the solution of sixth-order two-point boundary value problems

Two new second- and fourth-order methods based on a septic non-polynomial spline function for the numerical solution of sixth-order two-point boundary value problems are presented. The spline function is used to derive some consistency relations for computing approximations to the solution of this problem. The proposed approach gives better approximations than existing polynomial spline and finite difference methods up to order four and has a lower computational cost. Convergence analysis of these two methods is discussed. Three numerical examples are included to illustrate the practical use of our methods as well as their accuracy compared with existing spline function methods.     

A remez type algorithm for generalized spline spaces

Best uniform approximation by generalized spline spaces was studied by Nürnberger, Schumaker, Sommer, and Strauß [5]. In this paper we describe a Remez type algorithm for computing best spline approximations. Although some of the proofs are quite different we are able to prove results similar to the convergence of the Remez algorithm for polynomial spline functions by Nürnberger and Sommer [8].     

Pseudospectral methods for solving infinite-horizon optimal control problems

An important aspect of numerically approximating the solution of an infinite-horizon optimal control problem is the manner in which the horizon is treated. Generally, an infinite-horizon optimal control problem is approximated with a finite-horizon problem. In such cases, regardless of the finite duration of the approximation, the final time lies an infinite duration from the actual horizon at t=+∞. In this paper we describe two new direct pseudospectral methods using Legendre–Gauss (LG) and Legendre–Gauss–Radau (LGR) collocation for solving infinite-horizon optimal control problems numerically. A smooth, strictly monotonic transformation is used to map the infinite time domain t∈[0,∞) onto a half-open interval τ∈[−1,1). The resulting problem on the finite interval is transcribed to a nonlinear programming problem using collocation. The proposed methods yield approximations to the state and the costate on the entire horizon, including approximations at t=+∞. These pseudospectral methods can be written equivalently in either a differential or an implicit integral form. In numerical experiments, the discrete solution exhibits exponential convergence as a function of the number of collocation points. It is shown that the map ?:[−1,+1)→[0,+∞) can be tuned to improve the quality of the discrete approximation.     

Fast evaluation of vector splines in three dimensions

Vector spline techniques have been developed as general-purpose methods for vector field reconstruction. However, such vector splines involve high computational complexity, which precludes applications of this technique to many problems using large data sets. In this paper, we develop a fast multipole method for the rapid evaluation of the vector spline in three dimensions. The algorithm depends on a tree-data structure and two hierarchical approximations: an upward multipole expansion approximation and a downward local Taylor series approximation. In comparison with the CPU time of direct calculation, which increases at a quadratic rate with the number of points, the presented fast algorithm achieves a higher speed in evaluation at a linear rate. The theoretical error bounds are derived to ensure that the fast method works well with a specific accuracy. Numerical simulations are performed in order to demonstrate the speed and the accuracy of the proposed fast method.     

A-stabile Kollokationsverfahren mit mehrfachen Knoten

The collocation methods treated by the author in [3] produce spline approximations for the solutions of initial value problems for ordinary differential equations. Some general results on A-stability given by Wanner, Hairer and Nørsett [6] are formulated for these methods in the case where they are equivalent to certain implicit Runge-Kutta-methods. Hereby the dependence of A-stability on the nodes and their their multiplicities becomes apparent.