On the convergence of Wang-Zheng's method

The choice of initial conditions ensuring safe convergence of the implemented iterative method is one of the most important problems in solving polynomial equations. These conditions should depend only on the coefficients of a given polynomial P and initial approximations to the zeros of P. In this paper we state initial conditions with the described properties for the Wang-Zheng method for the simultaneous approximation of all zeros of P. The safe convergence and the fourth-order convergence of this method are proved.     

Finding roots of a real polynomial simultaneously by means of Bairstow's method

Aberth's method for finding the roots of a polynomial was shown to be robust. However, complex arithmetic is needed in this method even if the polynomial is real, because it starts with complex initial approximations. A novel method is proposed for real polynomials that does not require any complex arithmetic within iterations. It is based on the observation that Aberth's method is a systematic use of Newton's method. The analogous technique is then applied to Bairstow's procedure in the proposed method. As a result, the method needs half the computations per iteration than Aberth's method. Numerical experiments showed that the new method exhibited a competitive overall performance for the test polynomials.     

Point estimation and some applications to iterative methods

We consider one of the crucial problems in solving polynomial equations concerning the construction of such initial conditions which provide a safe convergence of simultaneous zero-finding methods. In the first part we deal with the localization of polynomial zeros using disks in the complex plane. These disks are used for the construction of initial inclusion disks which, under suitable conditions, provide the convergence of the Gargantini-Henrici interval method. They also play a key role in the convergence analysis of the fourth order Ehrlich-Aberth method with Newton's correction for the simultaneous approximation of all zeros of a polynomial. For this method we state the initial condition which enables the safe convergence. The initial condition is computationally verifiable since it depends only on initial approximations, which is of practical importance.     

A note on the improved derivative free root-solvers

Using a fixed point relation of the square-root type and the basic fourth-order method, improved methods of fifth and sixth order for the simultaneous determination of simple zeros of a polynomial are obtained. An increase in convergence is achieved without additional numerical operations, which points to high computational efficiency of the accelerated methods. The main aim of this work is the convergence analysis of improved simultaneous methods given under computationally verifiable initial conditions in the spirit of Smale’s point estimation theory.     

Efficient methods for the inclusion of polynomial zeros

Using a suitable zero-relation and the inclusion isotonicity property, new interval iterative methods for the simultaneous inclusion of simple complex zeros of a polynomial are derived. These methods produce disks in the complex plane that contain the polynomial zeros in each iteration, providing in this manner an information about upper error bounds of approximations. Starting from the basic method of the fourth order, two accelerated methods with Newton’s and Halley’s corrections, having the order of convergence five and six respectively, are constructed. This increase of the convergence rate is obtained without any additional operations, which means that the methods with corrections are very efficient. The convergence analysis of the basic method and the methods with corrections is performed under computationally verifiable initial conditions, which is of practical importance. Two numerical examples are presented to demonstrate the convergence behavior of the proposed interval methods.     

A family of fourth-order parallel splitting methods for parabolic partial differential equations

A family of numerical methods which are L-stable, fourth-order accurate in space and time, and do not require the use of complex arithmetic is developed for solving second-order linear parabolic partial differential equations. In these methods, second-order spatial dderivatives are approximated by fourth-order finite-difference approximations, and the matrix exponential function is approximated by a rational approximation consisting of three parameters. Parallel algorithms are developed and tested on the one-dimensional head equation, with constant coefficients, subject to homogeneous and time-dependent boundary conditions. These methods are also extended to two- and three-dimensional heat equations, with constant coefficients, subject to homogeneous boundary conditions. © 1997 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 13 : 357–373, 1997     

On an iterative method for simultaneous inclusion of polynomial complex zeros

Starting from disjoint discs which contain polynomial complex zeros, the iterative interval method of the third order for the simultaneous finding inclusive discs for complex zeros is formulated. The Lagrangean interpolation formula and complex circular arithmetic are used. The convergence theorem and the conditions for convergence are considered. The proposed method has been applied for solving an algebraic equation.     

An efficient higher order family of root finders

A one parameter family of iterative methods for the simultaneous approximation of simple complex zeros of a polynomial, based on a cubically convergent Hansen–Patrick's family, is studied. We show that the convergence of the basic family of the fourth order can be increased to five and six using Newton's and Halley's corrections, respectively. Since these corrections use the already calculated values, the computational efficiency of the accelerated methods is significantly increased. Further acceleration is achieved by applying the Gauss–Seidel approach (single-step mode). One of the most important problems in solving nonlinear equations, the construction of initial conditions which provide both the guaranteed and fast convergence, is considered for the proposed accelerated family. These conditions are computationally verifiable; they depend only on the polynomial coefficients, its degree and initial approximations, which is of practical importance. Some modifications of the considered family, providing the computation of multiple zeros of polynomials and simple zeros of a wide class of analytic functions, are also studied. Numerical examples demonstrate the convergence properties of the presented family of root-finding methods.     

Decoupled smooth interfaces for spectral-element approximations of parabolic or elliptic type

A method is examined to approximate the interface conditions for Chebyshev polynomial approximations to the solutions of parabolic problems, and a smoothing technique is used to calculate the interface conditions for a domain decomposition method. The methods uses a polynomial of one less degree then the full approximation to calculate the first derivative so that interface values can be calculated by using only the adjacent subdomains. Theoretical results are given for the consistency of the scheme and practical results are presented. Computational results are given for both a fourth-order Runga-Kutta methods and an explicit/implicit scheme. © 1993 John Wiley & Sons, Inc.     

A new higher-order family of inclusion zero-finding methods

Starting from a suitable fixed point relation, a new one-parameter family of iterative methods for the simultaneous inclusion of complex zeros in circular complex arithmetic is constructed. It is proved that the order of convergence of this family is four. The convergence analysis is performed under computationally verifiable initial conditions. An approach for the construction of accelerated methods with negligible number of additional operations is discussed. To demonstrate convergence properties of the proposed family of methods, two numerical examples results are given.     

Finite difference methods for a class of two-point boundary value problems with mixed boundary conditions

We discuss the construction of three-point finite difference aproximations for the class of two-point boundary value problems: [p(x)y′]′ = f(x, y), α₀y(a) - α₁y′(a) = A, β₀y(b) + β₁y′(b) = B.We first establish an identity from which general three-point finite difference approximations of various orders can be obtained. We then consider in detail obtaining fourth-order methods based on three evaluations of f. We obtain a family of fourth-order discretizations for the differential equations; appropriate discretizations for the boundary conditions are also obtained for use with fourth-order methods. We select the free parameters available in this discretizations which lead to a “simplest” fourth-order method. This method is described and its convergence is established; numerical examples are given to illustrate this new fourth-order method.     

A new,simple approach to the derivation of exact analytical formulae for the zeros of analytic functions

A very simple method for the construction of the polynomial whose zeros coincide with the zeros of an analytic function inside and along a simple closed contour in the complex plane, based on an appropriate application of the Cauchy theorem in complex analysis, is proposed. The present method was motivated by the classical Burniston-Siewert method, based on the theory of the Riemann-Hilbert boundary-value problem for the construction of the aforementioned polynomial, but, although essentially equivalent to the Burniston-Siewert method, it is much simpler.     

The use of compact boundary value method for the solution of two-dimensional Schrödinger equation

In this paper, a high-order and accurate method is proposed for solving the unsteady two-dimensional Schrödinger equation. We apply a compact finite difference approximation of fourth-order for discretizing spatial derivatives and a boundary value method of fourth-order for the time integration of the resulting linear system of ordinary differential equations. The proposed method has fourth-order accuracy in both space and time variables. Moreover this method is unconditionally stable due to the favorable stability property of boundary value methods. The results of numerical experiments are compared with analytical solutions and with those provided by other methods in the literature. These results show that the combination of a compact finite difference approximation of fourth-order and a fourth-order boundary value method gives an efficient algorithm for solving the two dimensional Schrödinger equation.     

Relationships between different types of initial conditions for simultaneous root finding methods

The construction of initial conditions of an iterative method is one of the most important problems in solving nonlinear equations. In this paper, we obtain relationships between different types of initial conditions that guarantee the convergence of iterative methods for simultaneously finding all zeros of a polynomial. In particular, we show that any local convergence theorem for a simultaneous method can be converted into a convergence theorem with computationally verifiable initial conditions which is of practical importance. Thus, we propose a new approach for obtaining semilocal convergence results for simultaneous methods via local convergence results.     

Construction of two-step Runge-Kutta methods of high order for ordinary differential equations

The construction of two-step Runge-Kutta methods of order p and stage order q=p with stability polynomial given in advance is described. This polynomial is chosen to have a large interval of absolute stability for explicit methods and to be A-stable and L-stable for implicit methods. After satisfying the order and stage order conditions the remaining free parameters are computed by minimizing the sum of squares of the difference between the stability function of the method and a given polynomial at a sufficiently large number of points in the complex plane. This revised version was published online in August 2006 with corrections to the Cover Date.     

Necessary Optimality Conditions and New Optimization Methods for Cubic Polynomial Optimization Problems with Mixed Variables

Multivariate cubic polynomial optimization problems, as a special case of the general polynomial optimization, have a lot of practical applications in real world. In this paper, some necessary local optimality conditions and some necessary global optimality conditions for cubic polynomial optimization problems with mixed variables are established. Then some local optimization methods, including weakly local optimization methods for general problems with mixed variables and strongly local optimization methods for cubic polynomial optimization problems with mixed variables, are proposed by exploiting these necessary local optimality conditions and necessary global optimality conditions. A global optimization method is proposed for cubic polynomial optimization problems by combining these local optimization methods together with some auxiliary functions. Some numerical examples are also given to illustrate that these approaches are very efficient.     

On the convergence of the sequences of Gerschgorin-like disks

Carstensen’s results from 1991, connected with Gerschgorin’s disks, are used to establish a theorem concerning the localization of polynomial zeros and to derive an a posteriori error bound method. The presented quasi-interval method possesses useful property of inclusion methods to produce disks containing all simple zeros of a polynomial. The centers of these disks behave as approximations generated by a cubic derivative free method where the use of quantities already calculated in the previous iterative step decreases the computational cost. We state initial convergence conditions that guarantee the convergence of error bound method and prove that the method has the order of convergence three. Initial conditions are computationally verifiable since they depend only on the polynomial coefficients, its degree and initial approximations. Some computational aspects and the possibility of implementation on parallel computers are considered, including two numerical examples.In honor of Professor Richard S. Varga.     

Smoothing schemes for reaction-diffusion systems with nonsmooth data

Cox and Matthews [S.M. Cox, P.C. Matthews, Exponential time differencing for stiff systems, J. Comput. Phys. 176 (2002) 430–455] developed a class of Exponential Time Differencing Runge–Kutta schemes (ETDRK) for nonlinear parabolic equations; Kassam and Trefethen [A.K. Kassam, Ll. N. Trefethen, Fourth-order time stepping for stiff pdes, SIAM J. Sci. Comput. 26 (2005) 1214–1233] have shown that these schemes can suffer from numerical instability and they proposed a modified form of the fourth-order (ETDRK4) scheme. They use complex contour integration to implement these schemes in a way that avoids inaccuracies when inverting matrix polynomials, but this approach creates new difficulties in choosing and evaluating the contour for larger problems. Neither treatment addresses problems with nonsmooth data, where spurious oscillations can swamp the numerical approximations if one does not treat the problem carefully. Such problems with irregular initial data or mismatched initial and boundary conditions are important in various applications, including computational chemistry and financial engineering. We introduce a new version of the fourth-order Cox–Matthews, Kassam–Trefethen ETDRK4 scheme designed to eliminate the remaining computational difficulties. This new scheme utilizes an exponential time differencing Runge–Kutta ETDRK scheme using a diagonal Padé approximation of matrix exponential functions, while to deal with the problem of nonsmooth data we use several steps of an ETDRK scheme using a sub-diagonal Padé formula. The new algorithm improves computational efficiency with respect to evaluation of the high degree polynomial functions of matrices, having an advantage of splitting the matrix polynomial inversion problem into a sum of linear problems that can be solved in parallel. In this approach it is only required that several backward Euler linear problems be solved, in serial or parallel. Numerical experiments are described to support the new scheme.     

Point estimation of simultaneous methods for solving polynomial equations: A survey (II)

The construction of computationally verifiable initial conditions which provide both the guaranteed and fast convergence of the numerical root-finding algorithm is one of the most important problems in solving nonlinear equations. Smale's “point estimation theory” from 1981 was a great advance in this topic; it treats convergence conditions and the domain of convergence in solving an equation f(z)=0$f(z)=0$ using only the information of f   at the initial point _z0$z_0$. The study of a general problem of the construction of initial conditions of practical interest providing guaranteed convergence is very difficult, even in the case of algebraic polynomials. In the light of Smale's point estimation theory, an efficient approach based on some results concerning localization of polynomial zeros and convergent sequences is applied in this paper to iterative methods for the simultaneous determination of simple zeros of polynomials. We state new, improved initial conditions which provide the guaranteed convergence of frequently used simultaneous methods for solving algebraic equations: Ehrlich–Aberth's method, Ehrlich–Aberth's method with Newton's correction, Börsch-Supan's method with Weierstrass’ correction and Halley-like (or Wang–Zheng) method. The introduced concept offers not only a clear insight into the convergence analysis of sequences generated by the considered methods, but also explicitly gives their order of convergence. The stated initial conditions are of significant practical importance since they are computationally verifiable; they depend only on the coefficients of a given polynomial, its degree n and initial approximations to polynomial zeros.