Search

Matsumoto, Saito and Matoba recently proposed the Walsh figure of merit (WAFOM), which is a computable criterion for quasi-Monte Carlo point sets using digital nets. Several algorithms have been proposed for finding low-WAFOM point sets. In the existing algorithms, the number of points is fixed in advance, but extensible point sets are preferred in some applications. In this paper, we propose a random search algorithm for extensible low-WAFOM point sets. For this, we introduce a method that uses lookup tables to compute WAFOM faster. Numerical results show that our extensible low-WAFOM point sets are comparable with Niederreiter-Xing sequences for some low-dimensional and smooth test functions. [ABSTRACT FROM AUTHOR]

This paper gives a numerical method for reconstructing the original function and its derivatives from discrete input data. It is well known that this problem is ill-posed in the sense of Hadamard. The solution for the first order derivative has been proposed by [10] and [17], using the Tikhonov regularization technique. In this paper, under an assumption that the original function has a square integrable k-th order derivative, we propose a reconstruction method for the j-th order derivative where 0 ≤ j ≤ k - 1. A convergence rate estimate is obtained by taking a new choice of the Tikhonov parameter. Numerical example is given to verify the effectiveness and accuracy of the proposed method. [ABSTRACT FROM AUTHOR]

We study the two-factor CIR model and using the main idea of two of our previous papers, we propose explicit numerical schemes that preserves positivity and converges strongly in the mean square sense to the true solution. Our results apply for the multi-factor and the one-factor cases as well. [ABSTRACT FROM AUTHOR]

The extended linear complementarity problem (denoted by XLCP), of which the linear and horizontal linear complementarity problems are two special cases, can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed smoothing Fischer-Burmeister function, the XLCP is approximated by a family of parameterized smoothness optimization problems. A smoothing damped Gauss-Newton method is designed for solving the XLCP. The proposed algorithm is proved to be convergent globally under suitable assumptions. Some numerical results are reported in the paper. [ABSTRACT FROM AUTHOR]

The paper is concerned with the superconvergence of numerical evaluation of Hadamard finite-part integral. Following the works [6-9], we studied the second-order and the third-order quadrature formulae of Newton-Cotes type and introduced new rules. The rule for the second-order gives the same convergence rate as the rule [6] but in more general cases, the rule for the third-order gives better results than the rule in [9] In this work, first we mention the main results on the superconvergence of the Newton-Cotes rules, we mention trapezoidal and Simpson's rules and then we introduce a rule based on the cubic approximation. In the second part we describe important error estimates and in the last section we demonstrate theoretical results by numerical examples. [ABSTRACT FROM AUTHOR]

We investigate semismooth Newton and quasi-Newton methods for minimization problems arising from weighted ℓ1-regularization. We give proofs of the local convergence of these methods and show how their interpretation as active set methods leads to the development of efficient numerical implementations of these algorithms. We also propose and analyze Broyden updates for the semismooth quasi-Newton method. The efficiency of these methods is analyzed and compared with standard implementations. The paper concludes with some numerical examples that include both linear and nonlinear operator equations. [ABSTRACT FROM AUTHOR]

This is a review paper of the role of Carleman estimates in the theory of multidimensional coefficient inverse problems since the first inception of this idea in 1981. [ABSTRACT FROM AUTHOR]

This paper is devoted to the numerical study for a class of boundary value problems of singularly perturbed linear second-order differential-difference equations with small shifts (i. e., containing both terms having a negative shift and terms having a positive shift). In particular, the numerical study for the problems where second order derivative is multiplied by a small parameter e and the shifts depend on the small parameter have been considered. To obtain a parameter-uniform convergence, a piecewise-uniform mesh is constructed, which is dense in the boundary layer region and coarse in the outer region. The parameter-uniform convergence analysis of the method has been discussed. The method is shown to have almost second order parameter-uniform convergence. The effect of small shifts on boundary layers have also been discussed. To demonstrate the efficiency of the proposed scheme several examples having boundary layers have been carried out. [ABSTRACT FROM AUTHOR]

In this paper we develop a fast multiscale Galerkin method solving ill-posed integral equations with not exactly given input data via Tikhonov regularization. The method leads to fast solutions of discrete Tikhonov regularization. The convergence rates of the Tikhonov regularization are achieved by using a modified discrepancy principle. Finally, numerical experiments are given to illustrate the efficiency of the method. [ABSTRACT FROM AUTHOR]

In this paper, we describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbol of each cell updated at each step of the algorithm using estimation of distributions algorithms (EDA). This update is done using the empirical estimators of these probabilities for a fraction of the best puzzles according to a cost function. We develop also some partial restart techniques in the RESEDA algorithm to obtain a convergence for the most difficult puzzles. Our algorithm is tested numerically on puzzles with various levels of difficulty starting from very easy ones to very hard ones including the famous puzzle AI Escargot. The CPU times vary from few hundreds of a second for the easy ones to about one minute for the most difficult one. [ABSTRACT FROM AUTHOR]

We study in this paper a P1 finite element approximation of the solution in of a biharmonic problem. Since the P1 finite element method only leads to an approximate solution in , a discrete Laplace operator is used in the numerical scheme. The convergence of the method is shown, for the general case of a solution with regularity, thanks to compactness results and to the use of a particular interpolation of regular functions with compact supports. An error estimate is proved in the case where the solution is in . The order of this error estimate is equal to 1 if the solution has a compact support, and only 1/5 otherwise. Numerical results show that these orders are not sharp in particular situations. [ABSTRACT FROM AUTHOR]

For solving linear ill-posed problems regularization methods are required when the right-hand side is with some noise. In the present paper regularized solutions are obtained by multi-parameter regularization and the regularization parameters are chosen by a multi-parameter discrepancy principle. Under certain smoothness assumptions we provide order optimal error bounds that characterize the accuracy of the regularized solutions. For the computation of the regularization parameters fast algorithms of Newton type are applied which are based on special transformations. These algorithms are globally and monotonically convergent. Some of our theoretical results are illustrated by numerical experiments. We also show how the proposed approach may be employed for multi-task approximation. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the properties of a class of generalized harmonic numbers H( n, r). By means of the method of coefficients, we establish some identities involving H( n, r). We obtain a pair of inversion formulas. Furthermore, we investigate certain sums related to H( n, r), and give their asymptotic expansions. In particular, we obtain the asymptotic expansion of certain sums involving H( n, r) and the inverse of binomial coefficients by Laplace's method. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the identification of parameter with semi-linear parabolic equations. The convergence rates of the parameter and the solution of parabolic equations are discussed. [ABSTRACT FROM AUTHOR]

In the paper we present several numerical algorithms to simulate the fractional Brownian motion (the generalized Wiener process). The algorithms have been developed on the basis of the integral representation of the fractional Brownian motion and the spectral decomposition for its increments. The convergence of the numerical methods has been studied. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of computing the minimizers for Tikhonov functionals associated with inverse problems with sparsity constraints in general Banach spaces. We present, based on splitting the Tikhonov functional into a smooth and a non-smooth part, a general iterative procedure for the Banach-space setting. In case of sparsity constraints, this algorithm yields a successive application of thresholding-like functions which generalizes the well-known iterative soft-thresholding procedure. The convergence properties of the proposed method are studied. Depending on the smoothness and convexity of the underlying spaces, convergence of asymptotic rate is obtained with the help of Bregman and Bregman–Taylor distance estimates. In particular, strong convergence can be achieved for a large class of linear inverse problems with sparsity constraints in Banach space. [ABSTRACT FROM AUTHOR]

In this paper we propose a numerical method for solving nonstationary Maxwell equations on unstructured triangular grids, which is based on the finite volume method. We give the results of test calculations which confirm the second order of convergence of the method both for homogeneous media and media with space-variable dielectric permittivity. [ABSTRACT FROM AUTHOR]

Nonlinear first order partial functional differential systems are considered in the paper. Classical solutions of the local Cauchy problem on the Haar pyramid are approximated by solutions of suitable quasilinear systems of difference functional equations. The proposed numerical methods are difference schemes of the Euler type. A complete convergence analysis is given and it is shown by examples that the new methods are considerable better than the classical methods. It is shown that the Lax scheme is superfluous for the numerical approximations of classical solutions to nonlinear functional differential problems. The proof of the stability is based on a comparison technique with nonlinear estimates of the Perron type for given operators. [ABSTRACT FROM AUTHOR]

In this paper, the four-parameter nonconforming finite element proposed in [30] and [19] is analyzed with the framework of Double Set Parameter (DSP) method, then it is applied to the stationary Stokes problem. The element exhibits some features of the well-known Q1-P0 element under rectangular meshes. An optimal convergence rate is established for both the velocity and smoothed pressure. Furthermore, the superconvergent approximation between the interpolation of the exact solution and the finite element solution is proved. A superconvergent estimate on the centers of elements and the global superconvergence for the gradient of the velocity and the pressure are derived with the aid of a postprocessing method. Based on the superconvergence property, an asymptotically exact a posteriori estimator of ZZ type is also studied. [ABSTRACT FROM AUTHOR]

The Random Walk on Fixed Spheres (RWFS) introduced in our paper [25], and further developed in [26], is presented in details for Laplace and Lamé equations governing static elasticity problems. The approach is based on the Poisson type integral formulae written for each disc of a domain consisting of a family of overlapping discs. The original differential boundary value problem is equivalently reformulated in the form of a system of integral equations defined on the intersection surfaces (arches, in 2D, and caps, if generalized to 3D spheres). To solve the obtained system of integral equations, a Random Walk procedure is constructed where the random walks are living on the intersection surfaces. Since the spheres are fixed, it is convenient to construct also discrete random walk methods for solving the system of linear equations approximating the system of integral equations. We develop here two classes of special Monte Carlo iterative methods for solving these systems of linear algebraic equations which are constructed as a kind of randomized versions of the Chebyshev iteration method and Successive Over Relaxation (SOR) method. It is found that in this class of randomized SOR methods, the Gauss-Seidel method has a minimal variance. In [25] we have concluded that in the case of classical potential theory, the Random Walk on Fixed Spheres considerably improves the convergence rate of the standard Random Walk on Spheres method. More interesting, we succeeded there to extend the algorithm to the system of Lamé equations which cannot be solved by the conventional Random Walk on Spheres method. We present here a series of numerical experiments for 2D domains consisting of 5, 10, and 17 discs, and analyze the dependence of the variance on the number of discs and elastic constants. Further generalizations to Neumann and Dirichlet-Neumann boundary conditions are possible, see [23]. [ABSTRACT FROM AUTHOR]

In [2] we introduced a new type of mixed finite element approximations for two- and three-dimensional problems on distorted polygonal and polyhedral meshes that consist of cells having different forms. Additional degrees of freedom that arise in the process are excluded by a special condition that is natural for the mixed finite element approximations considered. This paper is devoted to the error analysis of the respective finite element solutions. We show that under certain assumptions on the regularity of the exact solution the convergence rate for the new approximations is the same as for the Raviart-Thomas finite element approximations of the lowest order. [ABSTRACT FROM AUTHOR]

The Monte Carlo method called "random walks on boundary" has been successfully used for solving boundary-value problems. This method has significant advantages when compared with random walks on spheres, balls or on discrete grids when an exterior Dirichlet or Neumann problem is solved, or when we are interested in computing the solution to a problem at an arbitrary number of points using a single random walk. In this paper we will investigate ways: • to increase the convergence rate of this method by using quasirandom sequences instead of pseudorandom numbers for the construction of the boundary walks, • to find an efficient parallel implementation of this method on a cluster using MPI. In our parallel implementation we use disjoint contiguous blocks of quasirandom numbers extracted from a given quasirandom sequence for each processor. In this case, the increased convergence rate does not come at the cost of less trustworthy answers. We also present some numerical examples confirming both the increased rate of convergence and the good parallel efficiency of the method. [ABSTRACT FROM AUTHOR]

The paper is devoted to study of a modification of the random walks on spheres in a finite domain G ⊂ Rm, m ≥ 2. It is proved that the considered spherical process with shifted centres converges to the boundary of G very rapidly. Namely, the average number of steps before fitting the ε-neighborhood of the boundary has the order of ln |ln ε| as ε → 0 instead of the standard order of |ln ε|. Thus, the spherical process with shifted centres can be effectively used for Monte Carlo solution of different problems of the mathematical physics related to the Laplace operator. [ABSTRACT FROM AUTHOR]

In this paper we propose an improved quasi-Monte Carlo method for solving Linear Algebra problems. We show that by using low-discrepancy sequences both the convergence and the CPU time of the algorithm are improved. Two parallelization schemes using the Message Passing Interface with static and dynamic load balancing are proposed. The dynamic scheme is useful for computing in the GRID environment. [ABSTRACT FROM AUTHOR]