The role of conditioning in mesh selection algorithms for first order systems of linear two point boundary value problems

Codes for the numerical solution of two-point boundary value problems can now handle quite general problems in a fairly routine and reliable manner. When faced with particularly challenging equations, such as singular perturbation problems, the most efficient codes use a highly non-uniform grid in order to resolve the non-smooth parts of the solution trajectory. This grid is usually constructed using either a pointwise local error estimate defined at the grid points or else by using a local residual control. Similar error estimates are used to decide whether or not to accept a solution. Such an approach is very effective in general providing that the problem to be solved is well conditioned. However, if the problem is ill conditioned then such grid refinement algorithms may be inefficient because many iterations may be required to reach a suitable mesh on which to compute the solution. Even worse, for ill conditioned problems an inaccurate solution may be accepted even though the local error estimates may be perfectly satisfactory in that they are less than a prescribed tolerance. The primary reason for this is, of course, that for ill conditioned problems a small local error at each grid point may not produce a correspondingly small global error in the solution. In view of this it could be argued that, when solving a two-point boundary value problem in cases where we have no idea of its conditioning, we should provide an estimate of the condition number of the problem as well as the numerical solution. In this paper we consider some algorithms for estimating the condition number of boundary value problems and show how this estimate can be used in the grid refinement algorithm.     

Asymptotically correct error estimation for collocation methods applied to singular boundary value problems

We discuss an a posteriori error estimate for collocation methods applied to boundary value problems in ordinary differential equations with a singularity of the first kind. As an extension of previous results we show the asymptotical correctness of our error estimate for the most general class of singular problems where the coefficient matrix is allowed to have eigenvalues with positive real parts. This requires a new representation of the global error for the numerical solution obtained by piecewise polynomial collocation when applied to our problem class.     

Efficient mesh selection for collocation methods applied to singular BVPs

We describe a mesh selection strategy for the numerical solution of boundary value problems for singular ordinary differential equations. This mesh adaptation procedure is implemented in our MATLAB code sbvp which is based on polynomial collocation. We prove that under realistic assumptions our mesh selection strategy serves to approximately equidistribute the global error of the collocation solution, thus enabling to reach prescribed tolerances efficiently. Moreover, we demonstrate that this strategy yields a favorable performance of the code and compare its computational effort with other implementations of polynomial collocation.     

An efficient meshfree point collocation moving least squares method to solve the interface problems with nonhomogeneous jump conditions

We are going to study a simple and effective method for the numerical solution of the closed interface boundary value problem with both discontinuities in the solution and its derivatives. It uses a strong‐form meshfree method based on the moving least squares (MLS) approximation. In this method, for the solution of elliptic equation, the second‐order derivatives of the shape functions are needed in constructing the global stiffness matrix. It is well‐known that the calculation of full derivatives of the MLS approximation, especially in high dimensions, is quite costly. In the current work, we apply the diffuse derivatives using an efficient technique. In this technique, we calculate the higher‐order derivatives using the approximation of lower‐order derivatives, instead of calculating directly derivatives. This technique can improve the accuracy of meshfree point collocation method for interface problems with nonhomogeneous jump conditions and can efficiently estimate diffuse derivatives of second‐ and higher‐orders using only linear basis functions. To introduce the appropriate discontinuous shape functions in the vicinity of interface, we choose the visibility criterion method that modifies the support of weight function in MLS approximation and leads to an efficient computational procedure for the solution of closed interface problems. The proposed method is applied for elliptic and biharmonic interface problems. For the biharmonic equation, we use a mixed scheme, which replaces this equation by a coupled elliptic system. Also the application of the present method to elasticity equation with discontinuities in the coefficients across a closed interface has been provided. Representative numerical examples demonstrate the accuracy and robustness of the proposed methodology for the closed interface problems. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1031–1053, 2015     

Second-order finite element approximations and a posteriori error estimation for two-dimensional parabolic systems

Summary We discuss an adaptive local refinement finite element method of lines for solving vector systems of parabolic partial differential equations on two-dimensional rectangular regions. The partial differential system is discretized in space using a Galerkin approach with piecewise eight-node serendipity functions. An a posteriori estimate of the spatial discretization error of the finite element solution is obtained using piecewise fifth degree polynomials that vanish on the edges of the rectangular elements of a grid. Ordinary differential equations for the finite element solution and error estimate are integrated in time using software for stiff differential systems. The error estimate is used to control a local spatial mesh refinement procedure in an attempt to keep a global measure of the error within prescribed limits. Examples appraising the accuracy of the solution and error estimate and the computational efficiency of the procedure relative to one using bilinear finite elements are presented.Dedicated to Prof. Ivo Babuka on the occasion of his 60th birthdayThis research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0156 and the U.S. Army Research Office under Contract Number DAAL 03-86-K-0112     

A recurrence method for a special class of continuous time linear programming problems

This article studies a numerical solution method for a special class of continuous time linear programming problems denoted by (SP). We will present an efficient method for finding numerical solutions of (SP). The presented method is a discrete approximation algorithm, however, the main work of computing a numerical solution in our method is only to solve finite linear programming problems by using recurrence relations. By our constructive manner, we provide a computational procedure which would yield an error bound introduced by the numerical approximation. We also demonstrate that the searched approximate solutions weakly converge to an optimal solution. Some numerical examples are given to illustrate the provided procedure.     

Optimal adaptive solution of initial-value problems with unknown singularities

The optimal solution of initial-value problems in ODEs is well studied for smooth right-hand side functions. Much less is known about the optimality of algorithms for singular problems. In this paper, we study the (worst case) solution of scalar problems with a right-hand side function having r   continuous bounded derivatives in R$\mathbf{R}$, except for an unknown singular point. We establish the minimal worst case error for such problems (which depends on r similarly as in the smooth case), and define optimal adaptive algorithms. The crucial point is locating an unknown singularity of the solution by properly adapting the grid. We also study lower bounds on the error of an algorithm for classes of singular problems. In the case of a single singularity with nonadaptive information, or in the case of two or more singularities, the error of any algorithm is shown to be independent of r.     

A computational methodology to study coupled physical processes over partitioned domains

In this paper, we describe a computational methodology to couple physical processes defined over independent subdomains, that are partitions of a global domain in three-dimensions. The methodology presented helps to compute the numerical solution on the global domain by appropriately piecing the local solutions from each subdomain. We discuss the mixed method formulation for the technique applied to a model problem and derive an error estimate for the finite element solution. We demonstrate through numerical experiments that the method is robust and reliable in higher dimensions.     

Approximate Solutions and Duality Theorems for Continuous-Time Linear Fractional Programming Problems

This article proposes a practical computational procedure to solve a class of continuous-time linear fractional programming problems by designing a discretized problem. Using the optimal solutions of proposed discretized problems, we construct a sequence of feasible solutions of continuous-time linear fractional programming problem and show that there exists a subsequence that converges weakly to a desired optimal solution. We also establish an estimate of the error bound. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

Error estimates for large-scale ill-posed problems

The computation of an approximate solution of linear discrete ill-posed problems with contaminated data is delicate due to the possibility of severe error propagation. Tikhonov regularization seeks to reduce the sensitivity of the computed solution to errors in the data by replacing the given ill-posed problem by a nearby problem, whose solution is less sensitive to perturbation. This regularization method requires that a suitable value of the regularization parameter be chosen. Recently, Brezinski et al. (Numer Algorithms 49, 2008) described new approaches to estimate the error in approximate solutions of linear systems of equations and applied these estimates to determine a suitable value of the regularization parameter in Tikhonov regularization when the approximate solution is computed with the aid of the singular value decomposition. This paper discusses applications of these and related error estimates to the solution of large-scale ill-posed problems when approximate solutions are computed by Tikhonov regularization based on partial Lanczos bidiagonalization of the matrix. The connection between partial Lanczos bidiagonalization and Gauss quadrature is utilized to determine inexpensive bounds for a family of error estimates. In memory of Gene H. Golub. This work was supported by MIUR under the PRIN grant no. 2006017542-003 and by the University of Cagliari.     

解带有Hilbert核的奇异积分方程的高精度组合算法

该文给出了用求积法解带Hilber核的奇异积分方程的高精度组合算法.把网格点分成互不相交的子集合, 在子集合上并行求解离散方程组, 再利用组合算法求得全局网格点的逼近.如果积分方程的系数属于B_δ, 则求积法的精度可达O(e^-nδ). 此外, 使用组合算法不仅能得到更高的精度阶, 而且能够得到后验误差估计. 数值算例的结果表明组合算法是极其有效的.     

Extrapolation techniques for reducing the pollution effect or reentrant corners in the finite element method

Summary Standard finite element schemes applied to boundary value problems on domains with reentrant corners suffer from a global loss of accuracy caused by the influence of the corner singularities. For a model situation, it is shown that this pollution effect can be completely described in terms of an asymptotic error expansion with respect to fractional powers of the mesh size parameter. This provides the basis of an extrapolation procedure which recovers the full order of accuracy for the solution as well as for the corresponding stress intensity factors.     

Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.     

Dynamic Lagrangian dual and reduced RLT constructs for solving 0–1 mixed-integer programs

In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.     

Convergence from an electromagnetic fluid system to the full compressible MHD equations

We are concerned with the zero dielectric constant limit for the full electro-magneto-fluid dynamics in this article. This singular limit is justified rigorously for global smooth solution for both well-prepared and ill-prepared initial data. The explicit convergence rate is also obtained by a elaborate energy estimate. Moreover, we show that for the well-prepared initial data, there is no initial layer, and the electric field always converges strongly to the limit function. While for the ill-prepared data case, there will be an initial layer near t=0. The strong convergence results only hold outside the initial layer.     

Adaptive finite elements for exterior domain problems

Summary. We present an adaptive finite element method for solving elliptic problems in exterior domains, that is for problems in the exterior of a bounded closed domain in , . We describe a procedure to generate a sequence of bounded computational domains , , more precisely, a sequence of successively finer and larger grids, until the desired accuracy of the solution is reached. To this end we prove an a posteriori error estimate for the error on the unbounded domain in the energy norm by means of a residual based error estimator. Furthermore we prove convergence of the adaptive algorithm. Numerical examples show the optimal order of convergence. Received July 8, 1997 /Revised version received October 23, 1997     

Error Bounds for Low-Rank Approximations of the First Exponential Integral Kernel

A hierarchical matrix is an efficient data-sparse representation of a matrix, especially useful for large dimensional problems. It consists of low-rank subblocks leading to low memory requirements as well as inexpensive computational costs. In this work, we discuss the use of the hierarchical matrix technique in the numerical solution of a large scale eigenvalue problem arising from a finite rank discretization of an integral operator. The operator is of convolution type, it is defined through the first exponential-integral function and, hence, it is weakly singular. We develop analytical expressions for the approximate degenerate kernels and deduce error upper bounds for these approximations. Some computational results illustrating the efficiency and robustness of the approach are presented.     

First-order accurate finite difference schemes for boundary vorticity approximations in curvilinear geometries

In this work we develop first-order accurate, forward finite difference schemes for the first derivative on both a uniform and a non-uniform grid. The schemes are applied to the calculation of vorticity on a solid wall of a curvilinear, two-dimensional channel. The von Mises coordinates are used to transform the governing equations, and map the irregular domain onto a rectangular computational domain. Vorticity on the solid boundary is expressed in terms of the first partial derivative of the square of the speed of the flow in the computational domain, and the derived finite difference schemes are used to calculate the vorticity at the computational boundary grid points using combinations of up to five computational domain grid points. This work extends previous work (Awartani et al., 2005) [3] in which higher-order schemes were obtained for the first derivative using up to four computational domain grid points. The aim here is to shed further light onto the use of first-order accurate non-uniform finite difference schemes that are essential when the von Mises transformation is used. Results show that the best schemes are those that use a natural sequence of non-uniform grid points. It is further shown that for non-uniform grid with clustering near the boundary, solution deteriorates with increasing number of grid points used. By contrast, when a uniform grid is used, solution improves with increasing number of grid points used.     

A nonstandard multigrid method with flexible multiple semicoarsening for the numerical solution of the pressure equation in a Navier-Stokes solver

Numerical methods for the incompressible Reynolds-averaged Navier-Stokes equations discretized by finite difference techniques on collocated cell-centered structured grids are considered in this paper. A widespread solution method to solve the pressure-velocity coupling problem is to use a segregated approach, in which the computational work is deeply controlled by the solution of the pressure problem. This pressure equation is an elliptic partial differential equation with possibly discontinuous or anisotropic coeffficients. The resulting singular linear system needs efficient solution strategies especially for 3-dimensional applications. A robust method (close to MG-S [22,34]) combining multiple cell-centered semicoarsening strategies, matrix-independent transfer operators, Galerkin coarse grid approximation is therefore designed. This strategy is both evaluated as a solver or as a preconditioner for Krylov subspace methods on various 2- or 3-dimensional fluid flow problems. The robustness of this method is shown. This revised version was published online in June 2006 with corrections to the Cover Date.     

Sharp upper global a posteriori error estimates for nonlinear elliptic variational problems

The paper is devoted to the problem of verification of accuracy of approximate solutions obtained in computer simulations. This problem is strongly related to a posteriori error estimates, giving computable bounds for computational errors and detecting zones in the solution domain where such errors are too large and certain mesh refinements should be performed. A mathematical model embracing nonlinear elliptic variational problems is considered in this work. Based on functional type estimates developed on an abstract level, we present a general technology for constructing computable sharp upper bounds for the global error for various particular classes of elliptic problems. Here the global error is understood as a suitable energy type difference between the true and computed solutions. The estimates obtained are completely independent of the numerical technique used to obtain approximate solutions, and are sharp in the sense that they can be, in principle, made as close to the true error as resources of the used computer allow. The latter can be achieved by suitably tuning the auxiliary parameter functions, involved in the proposed upper error bounds, in the course of the calculations.