Higher-order simultaneous methods for the determination of polynomial multiple zeros

Starting from Laguerre's method and using Newton's and Halley's corrections for a multiple zero, new simultaneous methods of Laguerre's type for finding multiple (real or complex) zeros of polynomials are constructed. The convergence order of the proposed methods is five and six, respectively. By applying the Gauss–Seidel approach, these methods are further accelerated. The lower bounds of the R-order of convergence of the improved (single-step) methods are derived. Faster convergence of all proposed methods is attained with negligible number of additional operations, which provides a high computational efficiency of these methods. A detailed convergence analysis and numerical results are given.     

Efficient iterative algorithms for bounding the inverse of a matrix

In this paper we are considering iterative methods for bounding the inverse of a matrix, which make use of interval arithmetic. We present a class of methods as a combination of ordinary Schulz's methods for only approximating the inverse matrix (see [3]) and of well-known interval Schulz's methods (see [1]). Two convergence theorems are proved. Our methods are shown to be asymptotically of the same order of convergence as the ordinary Schulz's methods being part of them. Therefore we are getting considerably more efficient interval methods by our approach than by the classical interval Schulz's methods in [1] or [5]. A numerical example is given.     

On theR-order of some accelerated methods for the simultaneous finding of polynomial zeros

A Gauss-Seidel procedure is applied to increase the convergence of a basic fourth order method for finding polynomial complex zeros. Further acceleration of convergence is performed by using Newton's and Halley's corrections. It is proved that the lower bounds of theR-order of convergence for the proposed serial (single-step) methods lie between 4 and 7. Computational efficiency and numerical examples are also given.     

On the improved Newton-like methods for the inclusion of polynomial zeros

The aim of this paper is to present some modifications of Newton's type method for the simultaneous inclusion of all simple complex zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, the convergence analysis shows that the convergence rate of the basic method is increased from 3 to 6 using Jarratt's corrections. The proposed method possesses a great computational efficiency since the acceleration of convergence is attained with only few additional calculations. Numerical results are given to demonstrate convergence properties of the considered methods.     

一类求解非线性奇异方程组的牛顿改进算法

受一个求解非线性奇异方程组迭代格式的启示,将两种牛顿改进算法推广成一般形式,并将其发展为一类求解具有奇异雅可比矩阵的非线性方程组的牛顿改进算法.首先,描述这类新算法的迭代格式,并导出其收敛阶,该新格式每步迭代仅需计算一次函数值和一次导函数值;然后,对测试函数进行检验,并与牛顿算法及其他奇异牛顿算法进行比较,从而验证该算法的快速收敛性;最后,通过两个实际问题验证所提出算法的有效性.     

Moving boundary transformation for American call options with transaction cost: finite difference methods and computing

The pricing of American call option with transaction cost is a free boundary problem. Using a new transformation method the boundary is made to follow a certain known trajectory in time. The new transformed problem is solved by various finite difference methods, such as explicit and implicit schemes. Broyden's and Schubert's methods are applied as a modification to Newton's method in the case of nonlinearity in the equation. An alternating direction explicit method with second-order accuracy in time is used as an example in this paper to demonstrate the technique. Numerical results demonstrate the efficiency and the rate of convergence of the methods.     

Schröder-like algorithms for multiple complex zeros of a polynomial

Using the iterative method of Newton's type in circular arithmetic, introduced in [14], a new iterative method for finding a multiple complex zero of a polynomial is derived. This method can be regarded as a version of classical Schröder's method. Initial conditions which guarantee a safe convergence of the proposed method are stated. The increase of the computational efficiency is achieved by a combination of the complex approximation methods of Schröder's type with some interval methods. The presented algorithms are analysed in view of their efficiency and illustrated numerically in the example of a polynomial equation.     

On optimal parameter of Laguerre's family of zero-finding methods

ABSTRACT

A one parameter Laguerre's family of iterative methods for solving nonlinear equations is considered. This family includes the Halley, Ostrowski and Euler methods, most frequently used one-point third-order methods for finding zeros. Investigation of convergence quality of these methods and their ranking is reduced to searching optimal parameter of Laguerre's family, which is the main goal of this paper. Although methods from Laguerre's family have been extensively studied in the literature for more decades, their proper ranking was primarily discussed according to numerical experiments. Regarding that such ranking is not trustworthy even for algebraic polynomials, more reliable comparison study is presented by combining the comparison by numerical examples and the comparison using dynamic study of methods by basins of attraction that enable their graphic visualization. This combined approach has shown that Ostrowski's method possesses the best convergence behaviour for most polynomial equations.     

Consistency and convergence of general linear multistep variable stepsize variable formula methods

Linear multistep (LM) formulae are commonly used in the numerical solution of initial value problems of first order ordinary differential equations (ODE's). A rigorous theory for LM formulae, when these are implemented as constant stepsize constant formula methods, was developed after the publication of Dahlquist's classical paper [1] in 1956. After 1969 LM formulae have often been applied in practical codes as variable stepsize variable formula methods (VSVFM's). Therefore the development of a rigorous theory for LM formulae also in the case where these are used as VSVFM's is desirable. A formal definition of general LM VSVFM's is given in this paper. Then some theorems concerning the consistency and the convergence of general LM VSVFM's are formulated and proved. The results obtained in this paper can be extended for one-leg VSVFM's and for VSVFM's based on predictorcorrector schemes of different types.     

Discrete weighted residual methods A survey

This paper introduces find exemplifies discrete weighted residual methods (DWRM's) for the approximate solution of discrete boundary-value problems in ordinary and partial difference equations. The solution of the discrete boundary-value problem is approximated by a linear combination of known functions with undetermined coefficients. DWRM's specify procedures for determining these coefficients as the solution of a. system of algebraic equations

This paper develops the discrete analogue of the continuous weighted residual methods. In so doing, the differences arising from this development are delineated and resolved. The convergence of DWRM's is demonstrated and the monotone decreasing properties of the root-mean-square error are noted. The DWRM's surveyed are: the collocation technique, the subdomain method, the Galerkin procedure, and the method of least-squares

Numerical results are presented to illustrate the efficacy of DWRM's.     

On the behaviour of approximate Newton methods

Newton's method for solving non linear operator equations requests at each step the solution of a linear equation. When these equations are solved only approximately we have a so called Approximate Newton Method (A.N.M.). In this paper we examine the convergence and the order of convergence of A.N.M.'s under Kantorovich type hypotheses, giving criteria for controlling the behaviour of the iterations. Moreover a posteriori error estimates are proposed. The application of the general results to the case of Newton-Iterative methods is illustrated.     

Convergence and numerical analysis of a family of two-step steffensen's methods

We provide sufficient conditions for the semilocal convergence of a family of two-step Steffensen's iterative methods on a Banach space. The main advantage of this family is that it does not need to evaluate neither any Fréchet derivative nor any bilinear operator, but having a high speed of convergence. Some numerical experiments are also presented.     

A shortest path routing algorithm using Hopfield neural network with an improved energy function

A shortest path routing algorithm using the Hopfield neural network with a modified Lyapunov function is proposed. The modified version of the Lyapunov energy function for an optimal routing problem is proposed for determining routing order for a source and multiple destinations. The proposed energy function mainly prevents the solution path from having loops and partitions. Experiments are performed on 3000 networks of up to 50 nodes with randomly selected link costs. The performance of the proposed algorithm is compared with several conventional algorithms including Ali and Kamoun's, Park and Choi's, and Ahn and Ramakrishna's algorithms in terms of the route optimality and convergence rate. The results show that the proposed algorithm outperforms conventional methods in all cases of experiments. The proposed algorithm particularly shows significant improvements on the route optimality and convergence rate over conventional algorithms when the size of the network approaches 50 nodes.     

时间约束的实体解析中记录对排序研究

实体解析是数据集成和数据清洗的重要组成部分,也是大数据分析与挖掘的必要预处理步骤.传统的批处理式实体解析的整体运行时间较长,无法满足当前(近似)实时的数据应用需求.因此,研究时间约束的实体解析,其核心问题是基于匹配可能性的记录对排序.通过对多路分块得到的块内信息与块间信息分别进行分析,提出两个基本的记录匹配可能性计算方法.在此基础上,提出一种基于二分图上相似性传播的记录匹配可能性计算方法.将记录对、块及其关联关系构建二分图;相似性沿着二分图不断地在记录对结点与块结点之间传播,直到收敛.收敛结果可以通过不动点计算得到.提出近似的收敛计算方法来降低计算代价,从而保证实体解析的实时召回率.最后,在两个数据集上进行实验评价,验证了所提出方法的有效性,并测试方法的各个方面.     

The improved Farmer–Loizou method for finding polynomial zeros

An improvement of the Farmer–Loizou method for the simultaneous determination of simple roots of algebraic polynomials is proposed. Using suitable corrections of Newton's type, the convergence of the basic method is increased from 4 to 5 without any additional calculations. In this manner, a higher computational efficiency of the improved method is achieved. We prove a local convergence of the presented method under initial conditions which depend on a geometry of zeros and their initial approximations. Numerical examples are given to demonstrate the convergence behaviour of the proposed method and related methods.     

Global convergence of Oja's PCA learning algorithm with a non-zero-approaching adaptive learning rate

A non-zero-approaching adaptive learning rate is proposed to guarantee the global convergence of Oja's principal component analysis (PCA) learning algorithm. Most of the existing adaptive learning rates for Oja's PCA learning algorithm are required to approach zero as the learning step increases. However, this is not practical in many applications due to the computational round-off limitations and tracking requirements. The proposed adaptive learning rate overcomes this shortcoming. The learning rate converges to a positive constant, thus it increases the evolution rate as the learning step increases. This is different from learning rates which approach zero which slow the convergence considerably and increasingly with time. Rigorous mathematical proofs for global convergence of Oja's algorithm with the proposed learning rate are given in detail via studying the convergence of an equivalent deterministic discrete time (DDT) system. Extensive simulations are carried out to illustrate and verify the theory derived. Simulation results show that this adaptive learning rate is more suitable for Oja's PCA algorithm to be used in an online learning situation.     

On the global and superlinear convergence of a discretized version of Wilson's method

This paper discusses an algorithm for the minimization of a nonlinear objective function subject to nonlinear inequality constraints. The considerations are influenced by a paper of Best/Bräuninger/Ritter/Robinson (published in this journal). Their idea of combining a penalty-method with Robinson's method can be generalized by extending the principle of coupling to a whole class of locally convergent algorithms. An example is given by using a discretized version of Wilson's method, advantageously in the following sense: During the second phase, only linear equations occur in the subproblems. After a sufficiently large number of iterations, these systems are uniquely solvable. The minimization of penalty functions, necessary in the first phase, is asymptotically exact. Altogether, the implementability of the method can be guaranteed. The given convergence results are verified by using Banach's fixed-point theorem mainly. On the whole, they correspond with the paper mentioned above. The assumptions for proving global convergence are permitted to be weaken. By using different consistent approximations of the Hessian of the Lagrange function several methods arise, which have estimates of theR-order well-known from the treatment of nonlinear equations.     

Newton's method for the Navier-Stokes equations with finite-element initial guess of stokes equations

It is shown that finite element solutions of Stokes equations may be chosen as the initial guess for the quadratic convergence of Newton's algorithm applied to Navier-Stokes equations provided there are sufficiently small mesh size h and the moderate Reynold's number. We provide also a mixed convergence analysis in terms of iterations and finite-error estimates of the initial guess with a regularity estimate and error analysis for each Newton's step.     

Family of quadratic spline difference schemes for a convection–diffusion problem

We consider the finite difference approximation of a singularly perturbed one-dimensional convection–diffusion two-point boundary value problem. It is discretized using quadratic splines as approximation functions, equations with various piecewise constant coefficients as collocation equations and a piecewise uniform mesh of Shishkin type. The family of schemes is derived using the collocation method. The numerical methods developed here are non-monotone and therefore apart from the consistency error we use Green's grid function analysis to prove uniform convergence. We prove the almost first order of convergence and furthermore show that some of the schemes have almost second-order convergence. Numerical experiments presented in the paper confirm our theoretical results.     

Modified bacterial foraging algorithm based multilevel thresholding for image segmentation

Multilevel thresholding is one of the most popular image segmentation techniques. In order to determine the thresholds, most methods use the histogram of the image. This paper proposes multilevel thresholding for histogram-based image segmentation using modified bacterial foraging (MBF) algorithm. To improve the global searching ability and convergence speed of the bacterial foraging algorithm, the best bacteria among all the chemotactic steps are passed to the subsequent generations. The optimal thresholds are found by maximizing Kapur's (entropy criterion) and Otsu's (between-class variance) thresholding functions using MBF algorithm. The superiority of the proposed algorithm is demonstrated by considering fourteen benchmark images and compared with other existing approaches namely bacterial foraging (BF) algorithm, particle swarm optimization algorithm (PSO) and genetic algorithm (GA). The findings affirmed the robustness, fast convergence and proficiency of the proposed MBF over other existing techniques. Experimental results show that the Otsu based optimization method converges quickly as compared with Kapur's method.