Search

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

For the approximation and simulation of twofold iterated stochastic integrals and the corresponding Lévy areas w.r.t. a multi-dimensional Wiener process, we review four algorithms based on a Fourier series approach. Especially, the very efficient algorithm due to Wiktorsson and a newly proposed algorithm due to Mrongowius and Rößler are considered. To put recent advances into context, we analyse the four Fourier-based algorithms in a unified framework to highlight differences and similarities in their derivation. A comparison of theoretical properties is complemented by a numerical simulation that reveals the order of convergence for each algorithm. Further, concrete instructions for the choice of the optimal algorithm and parameters for the simulation of solutions for stochastic (partial) differential equations are given. Additionally, we provide advice for an efficient implementation of the considered algorithms and incorporated these insights into an open source toolbox that is freely available for both Julia and Matlab programming languages. The performance of this toolbox is analysed by comparing it to some existing implementations, where we observe a significant speed-up. [ABSTRACT FROM AUTHOR]

In this paper we introduce two algorithms for stable approximation with and recovery of short cosine sums. The used signal model contains cosine terms with arbitrary real positive frequency parameters and therefore strongly generalizes usual Fourier sums. The proposed methods both employ a set of equidistant signal values as input data. The ESPRIT method for cosine sums is a Prony-like method and applies matrix pencils of Toeplitz + Hankel matrices while the ESPIRA method is based on rational approximation of DCT data and can be understood as a matrix pencil method for special Loewner matrices. Compared to known numerical methods for recovery of exponential sums, the design of the considered new algorithms directly exploits the special real structure of the signal model and therefore usually provides real parameter estimates for noisy input data, while the known general recovery algorithms for complex exponential sums tend to yield complex parameters in this case. [ABSTRACT FROM AUTHOR]

In this paper, stochastic approximation (SA) algorithm with a new adaptive step size scheme is proposed. New adaptive step size scheme uses a fixed number of previous noisy function values to adjust steps at every iteration. The algorithm is formulated for a general descent direction and almost sure convergence is established. The case when negative gradient is chosen as a search direction is also considered. The algorithm is tested on a set of standard test problems. Numerical results show good performance and verify efficiency of the algorithm compared to some of existing algorithms with adaptive step sizes. [ABSTRACT FROM AUTHOR]

A projection and contraction algorithm for solving multi-valued variational inequalities is proposed. The algorithm is proved to converge globally to a solution of a given multi-valued variational inequality under standard conditions. We present an analysis of the convergence rate. Finally, preliminary computational experiments illustrate the advantage of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Two different approaches based on cubic B-spline are developed to approximate the solution of problems in calculus of variations. Both direct and indirect methods will be described. It is known that, when using cubic spline for interpolating a function g∈ C [ a, b] on a uniform partition with the step size h, the optimal order of convergence derived is O( h ). In Zarebnia and Birjandi (J. Appl. Math. 1-10, 2012) a non-optimal O( h ) method based on cubic B-spline has been used to solve the problems in calculus of variations. In this paper at first we will obtain an optimal O( h ) indirect method using cubic B-spline to approximate the solution. The convergence analysis will be discussed in details. Also a locally superconvergent O( h ) indirect approximation will be describe. Finally the direct method based on cubic spline will be developed. Some test problems are given to demonstrate the efficiency and applicability of the numerical methods. [ABSTRACT FROM AUTHOR]

In order to find the least squares solution of a very large and inconsistent system of equations, one can employ the extended Kaczmarz algorithm. This method simultaneously removes the error term, so that a consistent system is asymptotically obtained, and applies Kaczmarz iterations for the current approximation of this system. It has been shown that for random corrections of the right hand side and Kaczmarz updates selected at random, the algorithm converges to the least squares solution. In this work we consider deterministic strategies like the maximal-residual and the almost-cyclic control, and show convergence to a least squares solution. [ABSTRACT FROM AUTHOR]

In this paper, we find some relationships among the coefficients matrices of second derivative general linear methods (SGLMs) which are sufficient conditions, but not necessary, to ensure the methods have Runge-Kutta stability (RKS) property. Considering these conditions, we construct some A- and L-stable SGLMs with inherent RKS of orders up to five. Also, some numerical experiments for the constructed methods in variable stepsize environment are given. [ABSTRACT FROM AUTHOR]

In scientific computing, it is time-consuming to calculate an inverse operator $\mathcal {A}^{-1}$ of a differential equation $\mathcal {A}\phi = f$ , especially when $\mathcal {A}$ is a highly nonlinear operator. In this paper, based on the homotopy analysis method (HAM), a new approach, namely the method of directly defining inverse mapping (MDDiM), is proposed to gain analytic approximations of nonlinear differential equations. In other words, one can solve a nonlinear differential equation $\mathcal {A}\phi = f$ by means of directly defining an inverse mapping $\mathcal J$ , i.e. without calculating any inverse operators. Here, the inverse mapping $\mathcal {J}$ is even unnecessary to be explicitly expressed in a differential form, since 'mapping' is a more general concept than 'differential operator'. To guide how to directly define an inverse mapping $\mathcal {J}$ , some rules are provided. Besides, a convergence theorem is proved, which guarantees that a convergent series solution given by the MDDiM must be a solution of problems under consideration. In addition, three nonlinear differential equations are used to illustrate the validity and potential of the MDDiM, and especially the great freedom and large flexibility of directly defining inverse mappings for various types of nonlinear problems. The method of directly defining inverse mapping (MDDiM) might open a completely new, more general way to solve nonlinear problems in science and engineering, which is fundamentally different from traditional methods. [ABSTRACT FROM AUTHOR]

The main object of this paper is to propose a product approximation for the gamma function. The estimates derived here are studied via the theory of completely monotonic functions. Sharp inequalities are stated. [ABSTRACT FROM AUTHOR]

In this article, we address the problem of approximating data points by C-smooth polynomial spline curves or surfaces using L-norm. The use of this norm helps to preserve the data shape and it reduces extraneous oscillations. In our approach, we introduce a new functional which enables to control directly the distance between the data points and the resulting spline solution. The computational complexity of the minimization algorithm is nonlinear. A local minimization method using sliding windows allows to compute approximation splines within a linear complexity. This strategy seems to be more robust than a global method when applied on large data sets. When the data are noisy, we iteratively apply this method to globally smooth the solution while preserving the data shape. This method is applied to image denoising. [ABSTRACT FROM AUTHOR]

We consider the problem of computing verified real interval perturbations of the coefficients of two univariate polynomials such that there exist corresponding perturbed polynomials which have an exact greatest common divisor (GCD) of a given degree k. Based on the certification of the rank deficiency of a submatrix of the Bezout matrix of two univariate polynomials, we propose an algorithm to compute verified real perturbations. Numerical experiments show the performance of our algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates a numerical method for solving two-dimensional nonlinear Fredholm integral equations of the second kind on non-rectangular domains. The scheme utilizes the shape functions of the moving least squares (MLS) approximation constructed on scattered points as a basis in the discrete collocation method. The MLS methodology is an effective technique for approximating unknown functions which involves a locally weighted least square polynomial fitting. The proposed method is meshless, since it does not need any background mesh or cell structures and so it is independent of the geometry of the domain. The scheme reduces the solution of two-dimensional nonlinear integral equations to the solution of nonlinear systems of algebraic equations. The error analysis of the proposed method is provided. The efficiency and accuracy of the new technique are illustrated by several numerical examples. [ABSTRACT FROM AUTHOR]

Using the Multivariate Decomposition Method (MDM), we develop an efficient algorithm for approximating the ∞-variate integral for a class of functions f that are once differentiable with respect to each variable. MDM requires efficient algorithms for d-variate versions of the problem. Such algorithms are provided by Smolyak's construction which is based on efficient algorithms for the univariate integration Detailed analysis and development of (nearly) optimal quadratures for I( f) is the main contribution of the current paper. [ABSTRACT FROM AUTHOR]

We describe several approximation algorithms for the joint spectral radius and compare their performance on a large number of test cases. The joint spectral radius of a set Σ of $n \times n$ matrices is the maximal asymptotic growth rate that can be obtained by forming products of matrices from Σ. This quantity is NP-hard to compute and appears in many areas, including in system theory, combinatorics and information theory. A dozen algorithms have been proposed this last decade for approximating the joint spectral radius but little is known about their practical efficiency. We overview these approximation algorithms and classify them in three categories: approximation obtained by examining long products, by building a specific matrix norm, and by using optimization-based techniques. All these algorithms are now implemented in a (freely available) MATLAB toolbox that was released in 2011. This toolbox allows us to present a comparison of the approximations obtained on a large number of test cases as well as on sets of matrices taken from the literature. Finally, in our comparison we include a method, available in the toolbox, that combines different existing algorithms and that is the toolbox's default method. This default method was able to find optimal products for all test cases of dimension less than four. [ABSTRACT FROM AUTHOR]

Meshless Finite Difference Method (MFDM) is nowadays a powerful engineering tool for numerical analysis of boundary value problems. Nowadays, its computational capabilities are not fully used mainly due to the lack of suitable commercial software. This paper briefly presents current state-of-the-art of the MFDM solution approach as well as deals with the selected computational aspects of the MFDM. A set of Matlab functions written by the author is attached to the paper. Techniques for generation of nodes, MFD stars, formulas, equations as well as local approximation technique and numerical integration schemes are discussed there. [ABSTRACT FROM AUTHOR]