Optimal Quadratic and Cubic Spline Collocation on Nonuniform Partitions

We develop optimal quadratic and cubic spline collocation methods for solving linear second-order two-point boundary value problems on non-uniform partitions. To develop optimal nonuniform partition methods, we use a mapping function from uniform to nonuniform partitions and develop expansions of the error at the nonuniform collocation points of some appropriately defined spline interpolants. The existence and uniqueness of the spline collocation approximations are shown, under some conditions. Optimal global and local orders of convergence of the spline collocation approximations and derivatives are derived, similar to those of the respective methods for uniform partitions. Numerical results on a variety of problems, including a boundary-layer problem, and a nonlinear problem, verify the optimal convergence of the methods, even under more relaxed conditions than those assumed by theory.     

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     

Comparison of collocation methods for the solution of second order non-linear boundary value problems

This article concerns the application of cubic spline collocation tau-method for solving non-linear second order ordinary differential equations. Three collocation methods [Taiwo, O.A., 1986, A computational method for ordinary differential equations and error estimation. MSc dissertation, University of Ilorin, Nigeria (unpublished); Taiwo, O.A., 2002, Exponential fitting for the solution of two point boundary value problem with cubic spline collocation tau-method. International Journal of Computer Mathematics, 79(3), 229–306.] are discussed and applied to some second order non-linear problems. They are standard collocation, perturbed collocation, and exponentially fitted collocation. Numerical examples are given to illustrate the accuracy, efficiency and computational cost.     

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.     

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.     

Dimension–Adaptive Tensor–Product Quadrature

We consider the numerical integration of multivariate functions defined over the unit hypercube. Here, we especially address the high–dimensional case, where in general the curse of dimension is encountered. Due to the concentration of measure phenomenon, such functions can often be well approximated by sums of lower–dimensional terms. The problem, however, is to find a good expansion given little knowledge of the integrand itself. The dimension–adaptive quadrature method which is developed and presented in this paper aims to find such an expansion automatically. It is based on the sparse grid method which has been shown to give good results for low- and moderate–dimensional problems. The dimension–adaptive quadrature method tries to find important dimensions and adaptively refines in this respect guided by suitable error estimators. This leads to an approach which is based on generalized sparse grid index sets. We propose efficient data structures for the storage and traversal of the index sets and discuss an efficient implementation of the algorithm. The performance of the method is illustrated by several numerical examples from computational physics and finance where dimension reduction is obtained from the Brownian bridge discretization of the underlying stochastic process.     

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.     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

多重样条小波与微分方程自适应正交配置算法

０．引 言 由于小波的分层性,时－频空间的局部性,能量正交性等,使得它在构造微分方程自适应快速求解算法方面具有独特的应用价值．最近蔡伟等［８］通过构造一类能量内积意义下的紧支集半正交三次单重样条小波,得到了求解微分方程初边值问题的自适应样条小波结点配置算法．然而,三次样条结点配置解一般只能达到Ｏ（ｈ２）的逼近阶,而利用多重样条（如Ｈｅｒｍｉｔｅ样条）建立的正交配置格式却可以达到更高逼近阶．因此,构造能量内积意义下的紧支集半正交多重样条小波基,并建立相应的微分方程自适应小波快速正交配置算法是一项有意…     

Numerical integration of partial differential equations using cubic splines

This paper presents techniques for the numerical solution of partial differential equations using cubic spline collocation.

The main spline relations are presented and incorporated into solution procedures for partial differential equations. The computational algorithm in every case is a tridiagonal matrix system amenable to efficient inversion methods. Truncation errors and stability are briefly discussed. Finally, some examples of their application to parabolic and hyperbolic systems with mixed boundary conditions are presented.

The results obtained are encouraging and justify further research in this field.     

Adaptive hierarchical boundary elements

A residual definition of error indicators and estimators is used. A p-and a h-implementation of an adaptive hierarchical boundary element method is presented.

The direct version of boundary elements based on the collocation method is reviewed and the way in which the residual boundary function is obtained is presented. The hierarchical definition of the interpolation and its advantages are discussed. Numerical interpolation to compute error estimators and indicators is established and its non-dimensionality is defined.     

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.     

The Tau Method as an analytic tool in the discussion of equivalence results across numerical methods

A Tau Method approximate solution of a given differential equation defined on a compact [a, b] is obtained by adding to the right hand side of the equation a specific minimal polynomial perturbation termH _n(x), which plays the role of a representation of zero in [a,b] by elements of a given subspace of polynomials. Neither discretization nor orthogonality are involved in this process of approximation. However, there are interesting relations between the Tau Method and approximation methods based on the former techniques. In this paper we use equivalence results for collocation and the Tau Method, contributed recently by the authors together with classical results in the literature, to identify precisely the perturbation termH(x) which would generate a Tau Method approximate solution, identical to that generated by some specific discrete methods over a given mesh Π ∈ [a, b]. Finally, we discuss a technique which solves the inverse problem, that is, to find adiscrete perturbed Runge-Kutta scheme which would simulate a prescribed Tau Method. We have chosen, as an example, a Tau Method which recovers the same approximation as an orthogonal expansion method. In this way we close the diagram defined by finite difference methods, collocation schemes, spectral techniques and the Tau Method through a systematic use of the latter as an analytical tool.     

三次Cardinal样条函数的自由参数优化方案

为了合理地取定三次Cardinal样条函数所含的自由参数,讨论了插值问题中三次Cardinal样条函数所含自由参数的优化问题。首先分析了自由参数对三次Cardinal样条函数曲线形状的影响,然后给出了数据插值与函数逼近这2种情形下自由参数最优取值的计算方案,分别得到了具有极小二次平均振荡与极小逼近误差的三次Cardinal样条函数。当需要构造具有良好形状保持效果或逼近效果的三次Cardinal样条函数时,可通过所提出的方案选取自由参数的最优取值。     

An integrated approach to structural shape optimization of linearly elastic structures. Part II: Shape definition and adaptivity

In this paper we initially study how the number of design variables used affects the final optimum shape of the structure when employing two different types of curves to describe the boundary of the structure, i.e. quadratic Bezier and cubic B-spline curves. The advantage of using better shape definition is highlighted with several examples. An adaptive mesh refinement (AMR) procedure using six-node triangular elements is adopted in the structural shape optimization process. The procedure makes use of an h-version adaptive refinement technique based on error estimates determined from either best-guess stress values or residual terms in the governing equation. An example is presented to illustrate the performance of these error estimators with respect to their convergence, accuracy and cost of computation. Different strategies for the inclusion of AMR procedures in the shape optimization process are also proposed. Anomalies in predicting the optimum shape due to discretization errors are demonstrated using several examples.     

Sparse Grids, Adaptivity, and Symmetry

Sparse grid methods represent a powerful and efficient technique for the representation and approximation of functions and particularly the solutions of partial differential equations in moderately high space dimensions. To extend the approach to truly high-dimensional problems as they arise in quantum chemistry, an additional property has to be brought into play, the symmetry or antisymmetry of the functions sought there. In the present article, an adaptive sparse grid refinement scheme is developed that takes full advantage of such symmetry properties and for which the amount of work and storage remains strictly proportional to the number of degrees of freedom. To overcome the problems with the approximation of the inherently complex antisymmetric functions, augmented sparse grid spaces are proposed.     

Error analysis of solutions of second-order boundary value problems obtained with residual correction method

Based on the maximum principle of differential equations and with the aid of asymptotic iteration technique, this paper tries to establish monotonic relation of second-order obstacle boundary value problems with their approximate solutions to eventually obtain the upper and lower approximate solutions of the exact solution. To obtain numerical solutions, the cubic spline approximation method is applied to discretize equations, and then according to the ‘residual correction method’ proposed in this paper, residual correction values are added into discretized grid points to translate once complex inequalities’ constraint mathematical programming problems into simple equational iteration problems. The numerical results also show that such method has the characteristic of correcting residual values to symmetrical values for such problems, as a result, the mean approximate solutions obtained even with a considerably small quantity of grid points still quite approximate the exact solution. Furthermore, the error range of approximate solutions can be identified very easily by using the obtained upper and lower approximate solutions, even if the exact solution is unknown.     

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.     

Adaptive methods for frictionless contact problems

In this paper a posteriori error indicators for frictionless contact problems are presented. In detail, error indicators relying on superconvergence properties and error estimators based on duality principles are investigated. Applications are to 3D solids under the hypothesis of non-linear elastic material behaviour associated with finite deformations. A penalization technique is applied to enforce multilateral boundary conditions due to contact. The approximate solution of the problem is obtained by using the finite element method. Several numerical results are reported to show the applicability of the adaptive algorithm to the considered problems.