Efficient sixth order methods for nonlinear oscillation problems

A class of two-step (hybrid) methods is considered for solving pure oscillation second order initial value problems. The nonlinear system, which results on applying methods of this type to a nonlinear differential system, may be solved using a modified Newton iteration scheme. From this class the author has derived methods which are fourth order accurate,P-stable, require only two (new) function evaluations per iteration and have a true real perfect square iteration matrix. Now, we propose an extension to sixth order,P-stable methods which require only three (new) function evaluations per iteration and for which the iteration matrix is a true realperfect cube. This implies that at most one real matrix must be factorised at each step. These methods have been implemented in a new variable step, local error controlling code.     

Accurate fourteenth-order methods for solving nonlinear equations

We establish new iterative methods of local order fourteen to approximate the simple roots of nonlinear equations. The considered three-step eighth-order construction can be viewed as a variant of Newton’s method in which the concept of Hermite interpolation is used at the third step to reduce the number of evaluations. This scheme includes three evaluations of the function and one evaluation of the first derivative per iteration, hence its efficiency index is 1.6817. Next, the obtained approximation for the derivative of the Newton’s iteration quotient is again taken into consideration to furnish novel fourteenth-order techniques consuming four function and one first derivative evaluations per iteration. In providing such new fourteenth-order methods, we also take a special heed to the computational burden. The contributed four-step methods have 1.6952 as their efficiency index. Finally, various numerical examples are given to illustrate the accuracy of the developed techniques.     

A family of optimal three-point methods for solving nonlinear equations using two parametric functions

Using an interactive approach which combines symbolic computation and Taylor’s series, a wide family of three-point iterative methods for solving nonlinear equations is constructed. These methods use two suitable parametric functions at the second and third step and reach the eighth order of convergence consuming only four function evaluations per iteration. This means that the proposed family supports the Kung-Traub hypothesis (1974) on the upper bound 2^m of the order of multipoint methods based on m + 1 function evaluations, providing very high computational efficiency. Different methods are obtained by taking specific parametric functions. The presented numerical examples demonstrate exceptional convergence speed with only few function evaluations.     

A class of Steffensen type methods with optimal order of convergence

In this paper, a family of Steffensen type methods of fourth-order convergence for solving nonlinear smooth equations is suggested. In the proposed methods, a linear combination of divided differences is used to get a better approximation to the derivative of the given function. Each derivative-free member of the family requires only three evaluations of the given function per iteration. Therefore, this class of methods has efficiency index equal to 1.587. Kung and Traub conjectured that the order of convergence of any multipoint method without memory cannot exceed the bound 2^d-1, where d is the number of functional evaluations per step. The new class of methods agrees with this conjecture for the case d=3. Numerical examples are made to show the performance of the presented methods, on smooth and nonsmooth equations, and to compare with other ones.     

A family of three-point methods of optimal order for solving nonlinear equations

A family of three-point iterative methods for solving nonlinear equations is constructed using a suitable parametric function and two arbitrary real parameters. It is proved that these methods have the convergence order eight requiring only four function evaluations per iteration. In this way it is demonstrated that the proposed class of methods supports the Kung-Traub hypothesis (1974) [3] on the upper bound 2ⁿ of the order of multipoint methods based on n+1 function evaluations. Consequently, this class of root solvers possesses very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed with only few function evaluations.     

Derivative free two-point methods with and without memory for solving nonlinear equations

Two families of derivative free two-point iterative methods for solving nonlinear equations are constructed. These methods use a suitable parametric function and an arbitrary real parameter. It is proved that the first family has the convergence order four requiring only three function evaluations per iteration. In this way it is demonstrated that the proposed family without memory supports the Kung-Traub hypothesis (1974) on the upper bound 2ⁿ of the order of multipoint methods based on n + 1 function evaluations. Further acceleration of the convergence rate is attained by varying a free parameter from step to step using information available from the previous step. This approach leads to a family of two-step self-accelerating methods with memory whose order of convergence is at least and even in special cases. The increase of convergence order is attained without any additional calculations so that the family of methods with memory possesses a very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed of the proposed methods using only few function evaluations.     

A hybrid iterative method for symmetric indefinite linear systems

Hybrid iterative methods that combine a conjugate direction method with a simpler iteration scheme, such as Chebyshev or Richardson iteration, were first proposed in the 1950s. The ease with which Chebyshev and Richardson iteration can be implemented efficiently on a large variety of computer architectures has in recent years lead to renewed interest in iterative methods that use Chebyshev or Richardson iteration. This paper presents a new hybrid iterative method for the solution of linear systems of equations with a symmetric indefinite matrix. Our method combines the conjugate residual method with Richardson iteration. Special attention is paid to the determination of two real intervals, one on each side of the origin, that contain most of the eigenvalues of the matrix. These intervals are used to compute suitable iteration parameters for Richardson iteration. We also discuss when to switch between the methods. The hybrid scheme typically uses the Richardson method for most iterations, and this reduces the number of arithmetic vector operations significantly compared with the number of arithmetic vector operations required when only the conjugate residual method is used. Computed examples illustrate the competitiveness of the hybrid scheme.     

Unifying fourth-order family of iterative methods

In this work, we develop a new two-parameter family of iterative methods for solving nonlinear scalar equations. One of the parameters is defined through an infinite power series consisting of real coefficients while the other parameter is a real number. The methods of the family are fourth-order convergent and require only three evaluations during each iteration. It is shown that various fourth-order iterative methods in the published literature are special cases of the developed family. Convergence analysis shows that the methods of the family are fourth-order convergent which is also verified through the numerical work. Computations are performed to explore the efficiency of various methods of the family.     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

New eighth-order iterative methods for solving nonlinear equations

In this paper, three new families of eighth-order iterative methods for solving simple roots of nonlinear equations are developed by using weight function methods. Per iteration these iterative methods require three evaluations of the function and one evaluation of the first derivative. This implies that the efficiency index of the developed methods is 1.682, which is optimal according to Kung and Traub’s conjecture [7] for four function evaluations per iteration. Notice that Bi et al.’s method in [2] and [3] are special cases of the developed families of methods. In this study, several new examples of eighth-order methods with efficiency index 1.682 are provided after the development of each family of methods. Numerical comparisons are made with several other existing methods to show the performance of the presented methods.     

A new general eighth-order family of iterative methods for solving nonlinear equations

In this work, we present a family of iterative methods for solving nonlinear equations. It is proved that these methods have convergence order 8. These methods require three evaluations of the function, and only use one evaluation of the first derivative per iteration. The efficiency of the method is tested on a number of numerical examples. On comparison with the eighth-order methods, the iterative methods in the new family behave either similarly or better for the test examples.     

A family of optimal fourth-order methods for multiple roots of nonlinear equations

Newton-Raphson method has always remained as the widely used method for finding simple and multiple roots of nonlinear equations. In the past years, many new methods have been introduced for finding multiple zeros that involve the use of weight function in the second step, thereby, increasing the order of convergence and giving a flexibility to generate a family of methods satisfying some underlying conditions. However, in almost all the schemes developed over the past, the usual way is to use Newton-type method at the first step. In this paper, we present a new two-step optimal fourth-order family of methods for multiple roots (m > 1). The proposed iterative family has the flexibility of choice at both steps. The development of the scheme is based on using weight functions. The first step can not only recapture Newton's method for multiple roots as special case but is also capable of defining new choices of first step. A stability analysis of some particular cases is also given to explain the dynamical behavior of the new methods around the multiple roots and decide the best values of the free parameters involved. Finally, we compare our methods with the existing schemes of the same order with a real life application as well as standard test problems. From the numerical results, we find that our methods can be considered as a better alternative for the existing procedures of same order.     

Some second-derivative-free variants of Halley’s method for multiple roots

In this paper, we present two new families of third-order methods for finding multiple roots of nonlinear equations. Each of them is based on a variant of the Halley’s method (for simple roots) free from second derivative. One of the families requires one evaluation of the function and two of its first derivative per iteration, and the other family requires two evaluations of the function and one of its first derivative. Several numerical examples are given to illustrate the performance of the presented methods.     

Three-step iterative methods with optimal eighth-order convergence

In this paper, based on Ostrowski’s method, a new family of eighth-order methods for solving nonlinear equations is derived. In terms of computational cost, each iteration of these methods requires three evaluations of the function and one evaluation of its first derivative, so that their efficiency indices are 1.682, which is optimal according to Kung and Traub’s conjecture. Numerical comparisons are made to show the performance of the new family.     

An optimal Steffensen-type family for solving nonlinear equations

In this paper, a general family of Steffensen-type methods with optimal order of convergence for solving nonlinear equations is constructed by using Newton’s iteration for the direct Newtonian interpolation. It satisfies the conjecture proposed by Kung and Traub [H.T. Kung, J.F. Traub, Optimal order of one-point and multipoint iteration, J. Assoc. Comput. Math. 21 (1974) 634-651] that an iterative method based on m evaluations per iteration without memory would arrive at the optimal convergence of order 2^m−1. Its error equations and asymptotic convergence constants are obtained. Finally, it is compared with the related methods for solving nonlinear equations in the numerical examples.     

New quasi-Newton method for solving systems of nonlinear equations

We propose a new Broyden method for solving systems of nonlinear equations, which uses the first derivatives, but is more efficient than the Newton method (measured by the computational time) for larger dense systems. The new method updates QR or LU decompositions of nonsymmetric approximations of the Jacobian matrix, so it requires O(n ²) arithmetic operations per iteration in contrast with the Newton method, which requires O(n ³) operations per iteration. Computational experiments confirm the high efficiency of the new method.     

A class of asynchronous multisplitting two-stage iterations for large sparse block systems of weakly nonlinear equations

For the block system of weakly nonlinear equations Ax=G(x), where is a large sparse block matrix and is a block nonlinear mapping having certain smoothness properties, we present a class of asynchronous parallel multisplitting block two-stage iteration methods in this paper. These methods are actually the block variants and generalizations of the asynchronous multisplitting two-stage iteration methods studied by Bai and Huang (Journal of Computational and Applied Mathematics 93(1) (1998) 13–33), and they can achieve high parallel efficiency of the multiprocessor system, especially, when there is load imbalance. Under quite general conditions that is a block H-matrix of different types and is a block P-bounded mapping, we establish convergence theories of these asynchronous multisplitting block two-stage iteration methods. Numerical computations show that these new methods are very efficient for solving the block system of weakly nonlinear equations in the asynchronous parallel computing environment.     

New higher-order methods for the simultaneous inclusion of polynomial zeros

Higher-order methods for the simultaneous inclusion of complex zeros of algebraic polynomials are presented in parallel (total-step) and serial (single-step) versions. If the multiplicities of each zeros are given in advance, the proposed methods can be extended for multiple zeros using appropriate corrections. These methods are constructed on the basis of the zero-relation of Gargantini’s type, the inclusion isotonicity property and suitable corrections that appear in two-point methods of the fourth order for solving nonlinear equations. It is proved that the order of convergence of the proposed methods is at least six. The computational efficiency of the new methods is very high since the acceleration of convergence order from 3 (basic methods) to 6 (new methods) is attained using only n polynomial evaluations per iteration. Computational efficiency of the considered methods is studied in detail and two numerical examples are given to demonstrate the convergence behavior of the proposed methods.     

Efficient derivative-free variants of Hansen-Patrick’s family with memory for solving nonlinear equations

In this paper, we present a new tri-parametric derivative-free family of Hansen-Patrick type methods for solving nonlinear equations numerically. The proposed family requires only three functional evaluations to achieve optimal fourth order of convergence. In addition, acceleration of convergence speed is attained by suitable variation of free parameters in each iterative step. The self-accelerating parameters are estimated from the current and previous iteration. These self-accelerating parameters are calculated using Newton’s interpolation polynomials of third and fourth degrees. Consequently, the R-order of convergence is increased from 4 to 7, without any additional functional evaluation. Furthermore, the most striking feature of this contribution is that the proposed schemes can also determine the complex zeros without having to start from a complex initial guess as would be necessary with other methods. Numerical experiments and the comparison of the existing robust methods are included to confirm the theoretical results and high computational efficiency.     

A second-order pseudo-transient method for steady-state problems

This article gives a second pseudo-transient method for a special system of nonlinear equations, which arises from chemical reaction rate equations. This method uses a special second-order Rosenbrock method as the discrete difference scheme, which satisfies a linear conservation law. Moreover, it adaptively adjusts the time step in inverse proportion to an arithmetic mean of the current residual and the previous residual at every iteration step. For a singular system of nonlinear equations, under some standard assumptions, local convergence of the new method is addressed. Finally, some promise numerical results are also reported.