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.     

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.     

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.     

Multipoint efficient iterative methods and the dynamics of Ostrowski's method

ABSTRACT

In this work, we introduce a modification into the technique, presented in A. Cordero, J.L. Hueso, E. Martínez, and J.R. Torregrosa [Increasing the convergence order of an iterative method for nonlinear systems, Appl. Math. Lett. 25 (2012), pp. 2369–2374], that increases by two units the convergence order of an iterative method. The main idea is to compose a given iterative method of order p with a modification of Newton's method that introduces just one evaluation of the function, obtaining a new method of order p+2, avoiding the need to compute more than one derivative, so we improve the efficiency index in the scalar case. This procedure can be repeated n times, with the same approximation to the derivative, obtaining new iterative methods of order p+2n. We perform different numerical tests that confirm the theoretical results. By applying this procedure to Newton's method one obtains the well known fourth order Ostrowski's method. We finally analyse its dynamical behaviour on second and third degree real polynomials.     

Gradient methods exploiting spectral properties

We propose a new stepsize for the gradient method. It is shown that this new stepsize will converge to the reciprocal of the largest eigenvalue of the Hessian, when Dai-Yang's asymptotic optimal gradient method (Computational Optimization and Applications, 2006, 33(1): 73–88) is applied for minimizing quadratic objective functions. Based on this spectral property, we develop a monotone gradient method that takes a certain number of steps using the asymptotically optimal stepsize by Dai and Yang, and then follows by some short steps associated with this new stepsize. By employing one step retard of the asymptotic optimal stepsize, a nonmonotone variant of this method is also proposed. Under mild conditions, R-linear convergence of the proposed methods is established for minimizing quadratic functions. In addition, by combining gradient projection techniques and adaptive nonmonotone line search, we further extend those methods for general bound constrained optimization. Two variants of gradient projection methods combining with the Barzilai-Borwein stepsizes are also proposed. Our numerical experiments on both quadratic and bound constrained optimization indicate that the new proposed strategies and methods are very effective.     

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.     

Composite Adaptive Control of Uncertain Euler‐Lagrange Systems with Parameter Convergence without PE Condition

This work proposes a novel composite adaptive controller for uncertain Euler‐Lagrange (EL) systems. The composite adaptive law is strategically designed to be proportional to the parameter estimation error in addition to the tracking error, leading to parameter convergence. Unlike conventional adaptive control laws which require the regressor function to be persistently exciting (PE) for parameter convergence, the proposed method guarantees parameter convergence from a milder initially exciting (IE) condition on the regressor. The IE condition is significantly less restrictive than PE, since it does not rely on the future values of the signal and that it can be verified online. The proposed adaptive controller ensures exponential convergence of the tracking and the parameter estimation errors to zero once the sufficient IE condition is met. Simulation results corroborate the efficacy of the proposed technique and also establishes it's robustness property in the presence of unmodeled bounded disturbance.     

A fourth-order B-spline collocation method and its error analysis for Bratu-type and Lane–Emden problems

Recently, Caglar et al. [B-spline method for solving Bratu's problem, Int. J. Comput. Math. 87(8) (2010), pp. 1885–1891] proposed a numerical technique based on cubic B-spline for solving a Bratu-type problem. This method provides a second-order convergent approximation to the solution of the problem. In this paper, we develop a high-order numerical method based on quartic B-spline collocation approach for the Bratu-type and Lane–Emden problems. The error analysis of the quartic B-spline interpolation is carried out. Some numerical examples are provided to demonstrate the efficiency and applicability of the method and to verify its rate of convergence. The numerical results are compared with exact solutions and a numerical method based on cubic B-spline approach. Comparison reveals that our method produces more accurate results than the method proposed by Caglar et al. [B-spline method for solving Bratu's problem, Int. J. Comput. Math. 87(8) (2010), pp. 1885–1891].     

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.     

基于AdaGrad的自适应NAG方法及其最优个体收敛性

与梯度下降法相比,自适应梯度下降方法(AdaGrad)利用过往平方梯度的算数平均保存了历史数据的几何信息,在处理稀疏数据时获得了更紧的收敛界.另一方面,Nesterov加速梯度方法(Nesterov's accelerated gradient,NAG)在梯度下降法的基础上添加了动量运算,在求解光滑凸优化问题时具有数量...     

Descent three-term conjugate gradient methods based on secant conditions for unconstrained optimization

The conjugate gradient method is an effective method for large-scale unconstrained optimization problems. Recent research has proposed conjugate gradient methods based on secant conditions to establish fast convergence of the methods. However, these methods do not always generate a descent search direction. In contrast, Y. Narushima, H. Yabe, and J.A. Ford [A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM J. Optim. 21 (2011), pp. 212–230] proposed a three-term conjugate gradient method which always satisfies the sufficient descent condition. This paper makes use of both ideas to propose descent three-term conjugate gradient methods based on particular secant conditions, and then shows their global convergence properties. Finally, numerical results are given.     

An acceleration of preconditioned generalized accelerated over relaxation methods for systems of linear equations

In this paper, a new type of preconditioners are proposed to accelerate the preconditioned generalized accelerated over relaxation methods presented by Zhou et al. [Preconditioned GAOR methods for solving weighted linear least squares problems, J. Comput. Appl. Math. 224 (2009), pp. 242–249] for the linear system of the generalized least-squares problem. The convergence and comparison results are obtained. The comparison results show that the convergence rates of the proposed methods are better than those of the original methods. Finally, numerical experiments are provided to confirm the results obtained in this paper.     

Observer based fault reconstruction schemes using terminal sliding modes

ABSTRACT

Two state/fault estimation methods using terminal sliding mode (TSM) concepts are presented in this paper. In contrast with conventional sliding modes, which guarantee asymptotic convergence of non-output estimation errors and faults, TSMs enable finite time convergence of estimation errors for faults and all the states. The minimum-phase condition, as a common condition required for fault estimation, is released in the proposed methods. Method I implements fractional power of the so-called switching term to make it robust against matched faults and disturbances. Compared with previous terminal scheme, this method covers a wider class of systems. In Method II, fractional power sliding variable is considered to achieve finite time convergence of estimation errors and their derivatives. In contrast with Method I, this approach is also robust against unmatched faults. Finally, the methods are applied to an unstable aircraft model.     

Order of convergence of evolution operator method

In this paper the order of convergence of the evolution operator method used to solve a nonlinear autonomous system in ODE's [2] is investigated. The order is found, to be 2N+1 where N comes from the [N+1,N] Pade approximation used in the method. The order is independent of the choice of the weight function.     

Construction of iterative processes with high order of convergence

From the influence of convexity in Newton's method, a recursive procedure is obtained to construct iterative processes with order of convergence m, for each m∈N. Computational efficiency is also analysed.     

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.     

多项式方程区间内重根的快速判定和裁剪

目的多项式求实根问题有着广泛的应用。改进传统的裁剪方法,在多项式重根的情形下,保持计算稳定性的同时显著地提高相应的收敛阶。方法提出了基于R~3空间内的3次裁剪方法。该方法继承了传统裁剪求根方法的优点,充分利用了Bernstein基函数较好的计算稳定性,同时给出简单方法判别重根的存在性,从而使得重根的情形可以转化为单根的情形。结果与已有的基于R~1和R~2空间的3次裁剪方法相比,本文方法可以具有更好的逼近效果。单根情形下,本文方法与基于R~2空间的3次裁剪方法同时具有5次收敛阶,略高于基于R~1空间3次裁剪方法的4次收敛阶;m(≥2)重根情形下,本文方法理论上可具有5次收敛阶,明显优于已有的基于R~1和R~2空间的3次裁剪方法的4/m或5/m收敛阶。基于R~1,R~2和R~3空间的3次裁剪方法的计算时间复杂度大致相当,均为O(n~2)。结论本文方法可以快速判定重根的情形,同时具有更高的收敛阶和更好的逼近效果。     

On widening region of convergence for newton' method - a numerical ODE perspective

A heuristic analysis is given showing the connection between failures of Newton' method and solving an initial value problem of ODE'with an unstable numerical scheme. As an option to overcome the convergence difficulty encountered by Newton' method, three families of iteration methods, based on nonlinear approximations, are briefly studied. Numerical examples are presented showing the advantages of using proposed iterations in terms of having, in general, much wider regions of convergence for certain “difficult geometries.     

Optimal equi-scaled families of Jarratt's method

In this paper, we present many new fourth-order optimal families of Jarratt's method and Ostrowski's method for computing simple roots of nonlinear equations numerically. The proposed families of Jarratt's method having the same scaling factor of functions as that of Jarratt's method (i.e. quadratic scaling factor of functions in the numerator and denominator of the correction factor) are the main finding of this paper. It is observed that the body structures of our proposed families of Jarratt's method are simpler than those of the original families of Jarratt's method. The efficiency of these methods is tested on a number of relevant numerical problems. Furthermore, numerical examples suggest that each member of the proposed families can be competitive to other similar robust methods available in the literature.     

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.