Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

Optimal solution of ordinary differential equations

We survey some recent optimality results for the numerical solution of initial value problems for ODE. We assume that information used by an algorithm about a right-hand-side function is partial. Two settings of information-based complexity are considered: the worst case and asymptotic. Upper and lower bounds on the error are presented for three types of information: standard, linear, and nonlinear continuous. In both settings, minimum error algorithms are exhibited.     

Error estimation in nonlinear optimization

Methods are developed and analyzed for estimating the distance to a local minimizer of a nonlinear programming problem. One estimate, based on the solution of a constrained convex quadratic program, can be used when strict complementary slackness and the second-order sufficient optimality conditions hold. A second estimate, based on the solution of an unconstrained nonconvex, nonsmooth optimization problem, is valid even when strict complementary slackness is violated. Both estimates are valid in a neighborhood of a local minimizer. An active set algorithm is developed for computing a stationary point of the nonsmooth error estimator. Each iteration of the algorithm requires the solution of a symmetric, positive semidefinite linear system, followed by a line search. Convergence is achieved in a finite number of iterations. The error bounds are based on stability properties for nonlinear programs. The theory is illustrated by some numerical examples.     

On Numerical Solution of the Markov Renewal Equation: Tight Upper and Lower Kernel Bounds

We develop tight bounds and a fast parallel algorithm to compute the Markov renewal kernel. Knowledge of the kernel allows us to solve Markov renewal equations numerically to study non-steady state behavior in a finite state Markov renewal process. Computational error and numerical stability for computing the bounds in parallel are discussed using well-known results from numerical analysis. We use our algorithm and computed bounds to study the expected number of departures as a function of time for a two node overflow queueing network.     

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.     

Numerical methods for the linear Boltzmann transport equation in slab geometry

An iterative method for computing numerical solutions of a finite-difference system corresponding to the linear Boltzmann equation in slab geometry is presented. This iterative scheme gives a straightforward marching process starting from the given boundary and initial conditions. It is shown that with a suitable initial iteration the sequence of iterations converges monotonically to a unique solution of the finite-difference system. This monotone convergence leads to improved upper and lower bounds of the solution in each iteration, and to the well-posedness of the discrete system in the sense of Hadamard. It also leads to the convergence of the discrete system to the continuous system as the mesh size of the space–velocity–time variables approaches to zero. Under a mild restriction on the time-increment the discrete system is numerically stable, independent of the mesh-size of the space and velocity. An error estimate for the computed solution due to simultaneous initial and iteration error is obtained. Also given are some numerical results for the time-dependent and the steady-state solutions.     

On Eigenvector Bounds

We show under very general assumptions that error bounds for an individual eigenvector of a matrix can be computed if and only if the geometric multiplicity of the corresponding eigenvalue is one. Basically, this is true if not computing exactly like in computer algebra methods. We first show, under general assumptions, that nontrivial error bounds are not possible in case of geometric multiplicity greater than one. This result is also extended to symmetric, Hermitian and, more general, to normal matrices. Then we present an algorithm for the computation of error bounds for the (up to normalization) unique eigenvector in case of geometric multiplicity one. The effectiveness is demonstrated by numerical examples.This revised version was published online in October 2005 with corrections to the Cover Date.     

On a decoupled algorithm for solving a finite element problem for the approximation of viscoelastic fluid flow

Summary. The aim of this work is to study a decoupled algorithm of a fixed point for solving a finite element (FE) problem for the approximation of viscoelastic fluid flow obeying an Oldroyd B differential model. The interest for this algorithm lies in its applications to numerical simulation and in the cost of computing. Furthermore it is easy to bring this algorithm into play. The unknowns are the viscoelastic part of the extra stress tensor, the velocity and the pressure. We suppose that the solution is sufficiently smooth and small. The approximation of stress, velocity and pressure are resp. discontinuous, continuous, continuous FE. Upwinding needed for convection of , is made by discontinuous FE. The method consists to solve alternatively a transport equation for the stress, and a Stokes like problem for velocity and pressure. Previously, results of existence of the solution for the approximate problem and error bounds have been obtained using fixed point techniques with coupled algorithm. In this paper we show that the mapping of the decoupled fixed point algorithm is locally (in a neighbourhood of ) contracting and we obtain existence, unicity (locally) of the solution of the approximate problem and error bounds. Received July 29, 1994 / Revised version received March 13, 1995     

Solving boundary value problems,integral, and integro-differential equations using Gegenbauer integration matrices

We introduce a hybrid Gegenbauer (ultraspherical) integration method (HGIM) for solving boundary value problems (BVPs), integral and integro-differential equations. The proposed approach recasts the original problems into their integral formulations, which are then discretized into linear systems of algebraic equations using Gegenbauer integration matrices (GIMs). The resulting linear systems are well-conditioned and can be easily solved using standard linear system solvers. A study on the error bounds of the proposed method is presented, and the spectral convergence is proven for two-point BVPs (TPBVPs). Comparisons with other competitive methods in the recent literature are included. The proposed method results in an efficient algorithm, and spectral accuracy is verified using eight test examples addressing the aforementioned classes of problems. The proposed method can be applied on a broad range of mathematical problems while producing highly accurate results. The developed numerical scheme provides a viable alternative to other solution methods when high-order approximations are required using only a relatively small number of solution nodes.     

关于两类具有不同基函数的标准模糊系统逼近精度问题的研究

在标准模糊系统的基础上提出了以正规二次多项式和正规三角函数为基函数的两类标准模糊系统.通过采用数值分析中的余项与辅助函数方法,对这两类模糊系统进行了误差精度的分析,给出了从SISO到MISO的误差界公式.同时,对这两类模糊系统误差界进行了比较,指出了两类模糊系统的优劣.最后,通过算例验证了理论结果的正确性.     

Numerical error bounds for fourth order boundary value problems,simultaneous estimation ofu(x) andu″(x)

Summary For certain nonlinear two-point boundary value problems of the fourth order an estimation theory is developed which yields simultaneous estimates of the solution and its second derivative. Methods for computing numerical error bounds for approximate solutions are described and tested. The theory provides also uniqueness and existence statements. The results can be applied to many problems for which a corresponding theory on two-sided bounds is not suitable.     

Round-off error for retarded ordinary differential equations:A priori bounds and estimates

Summary Consider the numerical solution of a retarded ordinary differential equation (RODE) by some standard algorithms. For a linear RODE, we estimate the accumulated round-off error as a linear combination of the preceding local round-off errors, and we bound the accumulated round-off error. For a non-linear RODE, we obtain by linearization similar estimates and bounds for the dominant part of the accumulated round-off error.Presented at SIAM National Meeting, June, 1971, Seattle, Washington.     

Interval bounds on the solutions of semi-explicit index-one DAEs. Part 1: analysis

This article presents two methods for computing interval bounds on the solutions of nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs). Part 1 presents theoretical developments, while Part 2 discusses implementation and numerical examples. The primary theoretical contributions are (1) an interval inclusion test for existence and uniqueness of a solution, and (2) sufficient conditions, in terms of differential inequalities, for two functions to describe componentwise upper and lower bounds on this solution, point-wise in the independent variable. The first proposed method applies these results sequentially in a two-phase algorithm analogous to validated integration methods for ordinary differential equations. The second method unifies these steps to characterize bounds as the solutions of an auxiliary system of DAEs. Efficient implementations of both are described using interval computations and demonstrated on numerical examples.     

Interval bounds on the solutions of semi-explicit index-one DAEs. Part 2: computation

This article presents two methods for computing interval bounds on the solutions of nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs). Part 1 presents theoretical developments, while Part 2 discusses implementation and numerical examples. The primary theoretical contributions are (1) an interval inclusion test for existence and uniqueness of a solution, and (2) sufficient conditions, in terms of differential inequalities, for two functions to describe componentwise upper and lower bounds on this solution, point-wise in the independent variable. The first proposed method applies these results sequentially in a two-phase algorithm analogous to validated integration methods for ordinary differential equations (ODEs). The second method unifies these steps to characterize bounds as the solutions of an auxiliary system of DAEs. Efficient implementations of both are described using interval computations and demonstrated on numerical examples.     

Strict Chebyshev approximation for general systems of linear equations

Summary An ascent exchange algorithm for computing the strict Chebyshev solution to general systems of linear equations is presented. It uses generalized exchange rules to ensure convergence and splits up the entire system into subsystems by means of a canonical decomposition of a matrix obtained by Gaussian elimination methods. All updating procedures are developed and several numerical examples illustrate the efficiency of the algorithm.     

Stability of piecewise polynomial collocation for computing periodic solutions of delay differential equations

Summary. We prove numerical stability of a class of piecewise polynomial collocation methods on nonuniform meshes for computing asymptotically stable and unstable periodic solutions of the linear delay differential equation by a (periodic) boundary value approach. This equation arises, e.g., in the study of the numerical stability of collocation methods for computing periodic solutions of nonlinear delay equations. We obtain convergence results for the standard collocation algorithm and for two variants. In particular, estimates of the difference between the collocation solution and the true solution are derived. For the standard collocation scheme the convergence results are “unconditional”, that is, they do not require mesh-ratio restrictions. Numerical results that support the theoretical findings are also given. Received June 9, 2000 / Revised version received December 14, 2000 / Published online October 17, 2001     

Bounds for symmetric elliptic integrals

Lower and upper bounds for the four standard incomplete symmetric elliptic integrals are obtained. The bounding functions are expressed in terms of the elementary transcendental functions. Sharp bounds for the ratio of the complete elliptic integrals of the second kind and the first kind are also derived. These results can be used to obtain bounds for the product of these integrals. It is shown that an iterative numerical algorithm for computing the ratios and products of complete integrals has the second order of convergence.     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

A Posteriori Error Bounds for Gaussian Elimination

Explicit bounds are constructed for the error in the solutionof a system of linear algebraic equations obtained by Gaussianelimination using floating-point arithmetic. The bounds takeaccount of inherent errors in the data and all abbreviations(choppings or roundings) introduced during the process of solution.The bounds are strict and agree with the estimate for the maximumerror obtained by linearized perturbation theory. The formulationof the bounds avoids the need for specially directed roundingprocedures in the hardware or software; in consequence the boundscan be evaluated on most existing computers. The cost of computingthe bounds is comparable with the cost of computing the originalsolution.     

Modified integral current methods in electrodynamics of nonhomogeneous media

The main difficulty in numerical solution of integral equations of electrodynamics is associated with the need to solve a high-order system of linear equations with a dense matrix. It is therefore relevant to develop numerical methods that lead to linear equation systems of lower order at the cost of more complex evaluation of the coefficients. In this article we propose a method for solving linear equations of electrodynamics which is a modification of the integral current method. The main distinctive feature of the proposed method is double integration of the electric Green’s tensor in the process of algebraization of the original integral equation. The solutions of the system of linear equations are thus integral means of the electric field inside the anomaly constructed by the proposed transformation formula. We prove convergence and derive error bounds for both the solution of the integral equation and the electromagnetic field components evaluated from approximate transformation formulas.