On the convergence order of accelerated root iterations

Summary A Gauss-Seidel procedure for accelerating the convergence of the generalized method of the root iterations type of the (k+2)-th order (kN) for finding polynomial complex zeros, given in [7], is considered in this paper. It is shown that theR-order of convergence of the accelerated method is at leastk+1+ _n (k), where _n (k)>1 is the unique positive root of the equation ⁿ --k-1 = 0 andn is the degree of the polynomial. The examples of algebraic equations in ordinary and circular arithmetic are given.     

Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

On quadratic-like convergence of the means for two methods for simultaneous rootfinding of polynomials

Durand-Kerner's method for simultaneous rootfinding of a polynomial is locally second order convergent if all the zeros are simple. If this condition is violated numerical experiences still show linear convergence. For this case of multiple roots, Fraigniaud [4] proves that the means of clustering approximants for a multiple root is a better approximant for the zero and called this Quadratic-Like-Convergence of the Means.This note gives a new proof and a refinement of this property. The proof is based on the related Grau's method for simultaneous factoring of a polynomial. A similar property of some coefficients of the third order method due to Börsch-Supan, Maehly, Ehrlich, Aberth and others is proved.     

Superstable implicit Runge-Kutta methods for second order initial value problems

Using the well known properties of thes-stage implicit Runge-Kutta methods for first order differential equations, single step methods of arbitrary order can be obtained for the direct integration of the general second order initial value problemsy=f(x, y, y),y(x _o)=y _o,y(x _o)=y _o. These methods when applied to the test equationy+2y+ ² y=0, ,0, +>0, are superstable with the exception of a finite number of isolated values ofh. These methods can be successfully used for solving singular perturbation problems for which f/y and/or f/y are negative and large. Numerical results demonstrate the efficiency of these methods.     

Superlinear convergence of symmetric Huang's class of methods

Summary In this paper the problem of minimizing the functionalf:DR ⁿ R is considered. Typical assumptions onf are assumed. A class of Quasi-Newton methods, namely Huang's class of methods is used for finding an optimal solution of this problem. A new theorem connected with this class is presented. By means of this theorem some convergence results known up till now only for the methods which satisfy Quasi-Newton condition are extended, that is the results of superlinear convergence of variable metric methods in the cases of exact and asymptotically exact minimization and the so-called direct-prediction case. This theorem allows to interpretate one of the parameters as the scaling parameter.     

A study of Rosenbrock-type methods of high order

Summary This paper deals with the solution of nonlinear stiff ordinary differential equations. The methods derived here are of Rosenbrock-type. This has the advantage that they areA-stable (or stiffly stable) and nevertheless do not require the solution of nonlinear systems of equations. We derive methods of orders 5 and 6 which require one evaluation of the Jacobian and oneLU decomposition per step. We have written programs for these methods which use Richardson extrapolation for the step size control and give numerical results.     

On the order of composite multistep methods for ordinary differential equations

Summary In this paper, a general class ofk-step methods for the numerical solution of ordinary differential equations is discussed. It is shown that methods with order of consistencyq have order of convergence (q+1) if a very simple condition is satisfied. This result gives a new aspect to previous results of Spijker; it also serves as a starting point for a new theory of cyclick-step methods, completing an approach of Donelson and Hansen. It facilitates the practical determination of high-order cyclick-step methods, especially of stiffly stable,k-step methods.     

High order methods for the numerical integration of ordinary differential equations

Summary High order implicit integration formulae with a large region of absolute stability are developed for the approximate numerical integration of both stiff and non-stiff systems of ordinary differential equations. The algorithms derived behave essentially like one step methods and are demonstrated by direct application to certain particular examples.     

Monotone iterative methods for finite difference system of reaction-diffusion equations

Summary This paper presents an existence-comparison theorem and an iterative method for a nonlinear finite difference system which corresponds to a class of semilinear parabolic and elliptic boundary-value problems. The basic idea of the iterative method for the computation of numerical solutions is the monotone approach which involves the notion of upper and lower solutions and the construction of monotone sequences from a suitable linear discrete system. Using upper and lower solutions as two distinct initial iterations, two monotone sequences from a suitable linear system are constructed. It is shown that these two sequences converge monotonically from above and below, respectively, to a unique solution of the nonlinear discrete equations. This formulation leads to a well-posed problem for the nonlinear discrete system. Applications are given to several models arising from physical, chemical and biological systems. Numerical results are given to some of these models including a discussion on the rate of convergence of the monotone sequences.     

Extrapolation methods for some singular fixed point sequences

A fixed point sequence is singular if the Jacobian matrix at the limit has 1 as an eigenvalue. The asymptotic behaviour of some singular fixed point sequences in one dimension are extended toN dimensions. Three algorithms extrapolating singular fixed point sequences inN dimensions are given. Using numerical examples three algorithms are tested and compared.     

Local error estimation for multistep collocation methods

Multistep collocation methods for initial value problems in ordinary differential equations are known to be a subclass of multistep Runge-Kutta methods and a generalisation of the well-known class of one-step collocation methods as well as of the one-leg methods of Dahlquist. In this paper we derive an error estimation method of embedded type for multistep collocation methods based on perturbed multistep collocation methods. This parallels and generalizes the results for one-step collocation methods by Nørsett and Wanner. Simple numerical experiments show that this error estimator agrees well with a theoretical error estimate which is a generalisation of an error estimate first derived by Dahlquist for one-leg methods.     

On the order conditions of Runge-Kutta methods with higher derivatives

Summary Runge-Kutta methods have been generalized to procedures with higher derivatives of the right side ofy=f(t,y) e.g. by Fehlberg 1964 and Kastlunger and Wanner 1972. In the present work some sufficient conditions for the order of consistence are derived for these methods using partially the degree of the corresponding numerical integration formulas. In particular, methods of Gauß, Radau, and Lobatto type are generalized to methods with higher derivatives and their maximum order property is proved. The applied technique was developed by Crouzeix 1975 for classical Runge-Kutta methods. Examples of simple explicit and semi-implicit methods are given up to order 7 and 6 respectively.     

Acceleration methods based on convergence tests

Summary In this paper we propose an acceleration method based on a general convergence test and depending on an auxiliary sequence (x _n). For different choices of (x _n) we obtain some known and some new transformations and for each one sufficient conditions for acceleration are given.     

The local convergence of ABS methods for nonlinear algebraic equations

Summary In this paper we consider an extension to nonlinear algebraic systems of the class of algorithms recently proposed by Abaffy, Broyden and Spedicato for general linear systems. We analyze the convergence properties, showing that under the usual assumptions on the function and some mild assumptions on the free parameters available in the class, the algorithm is locally convergent and has a superlinear rate of convergence (per major iteration, which is computationally comparable to a single Newton's step). Some particular algorithms satisfying the conditions on the free parameters are considered.     

The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems

Summary The Chebyshev and second-order Richardson methods are classical iterative schemes for solving linear systems. We consider the convergence analysis of these methods when each step of the iteration is carried out inexactly. This has many applications, since a preconditioned iteration requires, at each step, the solution of a linear system which may be solved inexactly using an inner iteration. We derive an error bound which applies to the general nonsymmetric inexact Chebyshev iteration. We show how this simplifies slightly in the case of a symmetric or skew-symmetric iteration, and we consider both the cases of underestimating and overestimating the spectrum. We show that in the symmetric case, it is actually advantageous to underestimate the spectrum when the spectral radius and the degree of inexactness are both large. This is not true in the case of the skew-symmetric iteration. We show how similar results apply to the Richardson iteration. Finally, we describe numerical experiments which illustrate the results and suggest that the Chebyshev and Richardson methods, with reasonable parameter choices, may be more effective than the conjugate gradient method in the presence of inexactness.This work was supported in part by National Science Foundation Grants DCR-8412314 and DCR-8502014The work of this author was completed while he was on sabbatical leave at the Centre for Mathematical Analysis and Mathematical Sciences Research Institute at the Australian National University, Canberra, Australia     

One-step methods of any order for ordinary differential equations with discontinuous right-hand sides

Summary The right-hand sides of a system of ordinary differential equations may be discontinuous on a certain surface. If a trajectory crossing this surface shall be computed by a one-step method, then a particular numerical analysis is necessary in a neighbourhood of the point of intersection. Such an analysis is presented in this paper. It shows that one can obtain any desired order of convergence if the method has an adequate order of consistency. Moreover, an asymptotic error theory is developed to justify Richardson extrapolation. A general one-step method is constructed satisfying the conditions of the preceding theory. Finally, a simplified Newton iteration scheme is used to implement this method.     

Generalized Runge-Kutta methods of order four with stepsize control for stiff ordinary differential equations

Summary GeneralizedA()-stable Runge-Kutta methods of order four with stepsize control are studied. The equations of condition for this class of semiimplicit methods are solved taking the truncation error into consideration. For application anA-stable and anA(89.3°)-stable method with small truncation error are proposed and test results for 25 stiff initial value problems for different tolerances are discussed.     

Monotone iterative methods for nonlinear equations involving a noninvertible linear part

Summary We study monotone iterative methods for the numerical solution of a class of nonlinear elliptic boundary value problems by applying a theorem of Ortega and Rheinboldt. This generalizes the work of earlier authors to the case of nonlinear perturbations of linear problems with a nontrivial kernel.     

On the local error and the local truncation error of linear multistep methods

Two different measures of the local accuracy of a linear multistep method — the local error and the local trunction error — appear in the literature. It is shown that the principal parts of these errors are not identical for general linear multistep methods, but that they are so for a sub-class which contains all methods of Adams type. It is sometimes argued that local error is the more natural measure; this view is challenged.     

A class of pseudo Runge-Kutta methods

This paper develops a general theory for a class of Runge-Kutta methods which are based, in addition to the stages of the current step, also on the stages of the previous step. Such methods have been introduced previously for the case of one and two stages. We show that for any numbers of stages methods of orderp withs+1 p 2s can be constructed. The paper terminates with a study of step size change and stability.