Several New Third-Order Iterative Methods for Solving Nonlinear Equations

In this paper, we present some new third-order iterative methods for finding a simple root α of nonlinear scalar equation f(x)=0 in R. A geometric approach based on the circle of curvature is used to construct the new methods. Analysis of convergence shows that the new methods have third-order convergence, that is, the sequence {x _n }₀^∞ generated by each of the presented methods converges to α with the order of convergence three. The efficiency of the methods are tested on several numerical examples. It is observed that our methods can compete with Newton’s method and the classical third-order methods.     

Nonlocal representation of the sl(2, R) algebra for the Chazy equation

A demonstration of how the point symmetries of the Chazy equation become nonlocal symmetries for the reduced equation is discussed. Moreover we construct an equivalent third-order differential equation which is related to the Chazy equation under a generalized transformation, and find the point symmetries of the Chazy equation are generalized symmetries for the new equation. With the use of singularity analysis and a simple coordinate transformation we construct a solution for the Chazy equation which is given by a right Painlevé series. The singularity analysis is applied to the new third-order equation and we find that it admits two solutions, one given by a left Painlevé series and one given by a right Painlevé series where the leading-order behaviors and the resonances are explicitly those of the Chazy equation.     

Third-order iterative methods with applications to Hammerstein equations: A unified approach

The geometrical interpretation of a family of higher order iterative methods for solving nonlinear scalar equations was presented in [S. Amat, S. Busquier, J.M. Gutiérrez, Geometric constructions of iterative functions to solve nonlinear equations. J. Comput. Appl. Math. 157(1) (2003) 197-205]. This family includes, as particular cases, some of the most famous third-order iterative methods: Chebyshev methods, Halley methods, super-Halley methods, C-methods and Newton-type two-step methods. The aim of the present paper is to analyze the convergence of this family for equations defined between two Banach spaces by using a technique developed in [J.A. Ezquerro, M.A. Hernández, Halley’s method for operators with unbounded second derivative. Appl. Numer. Math. 57(3) (2007) 354-360]. This technique allows us to obtain a general semilocal convergence result for these methods, where the usual conditions on the second derivative are relaxed. On the other hand, the main practical difficulty related to the classical third-order iterative methods is the evaluation of bilinear operators, typically second-order Fréchet derivatives. However, in some cases, the second derivative is easy to evaluate. A clear example is provided by the approximation of Hammerstein equations, where it is diagonal by blocks. We finish the paper by applying our methods to some nonlinear integral equations of this type.     

Given a one-step numerical scheme,on which ordinary differential equations is it exact?

A necessary condition for a (non-autonomous) ordinary differential equation to be exactly solved by a one-step, finite difference method is that the principal term of its local truncation error be null. A procedure to determine some ordinary differential equations exactly solved by a given numerical scheme is developed. Examples of differential equations exactly solved by the explicit Euler, implicit Euler, trapezoidal rule, second-order Taylor, third-order Taylor, van Niekerk’s second-order rational, and van Niekerk’s third-order rational methods are presented.     

Application of modified homotopy perturbation method for solving the augmented systems

In this paper, a new approach is proposed for solving the augmented systems. Based on the modified homotopy perturbation method, we construct the new iterative methods and derive the sufficient and necessary conditions for guaranteeing its convergence. Some numerical experiments show that this method is more simple and effective.     

Runge–Kutta methods for affinely controlled nonlinear systems

Rooted tree analysis is adapted from stochastic differential equations to derive systematically general Runge–Kutta methods for deterministic affinely controlled nonlinear systems. Order conditions are found and some specific coefficients for second- and third-order methods are determined, which are then used for simulations compared with the Taylor methods for affinely controlled nonlinear systems derived by Grüne and Kloeden.     

On implicit Runge-Kutta methods with high stage order

It is well known that high stage order is a desirable property for implicit Runge-Kutta methods. In this paper it is shown that it is always possible to construct ans-stage IRK method with a given stability function and stage orders−1 if the stability function is an approximation to the exponential function of at least orders. It is further indicated how to construct such methods as well as in which cases the constructed methods will be stiffly accurate.     

An iterated Radau method for time-dependent PDEs

This paper is concerned with the time integration of semi-discretized, multi-dimensional PDEs of advection-diffusion-reaction type. To cope with the stiffness of these ODEs, an implicit method has been selected, viz., the two-stage, third-order Radau IIA method. The main topic of this paper is the efficient solution of the resulting implicit relations. First, a modified Newton process has been transformed into an iteration process in which the 2 stages are decoupled and, moreover, can exploit the same LU-factorization of the iteration matrix. Next, we apply a so-called Approximate Matrix Factorization (AMF) technique to solve the linear systems in each Newton iteration. This AMF approach is very efficient since it reduces the ‘multi-dimensional’ system to a series of ‘one-dimensional’ systems. The total amount of linear algebra work involved is reduced enormously by this approach. The idea of applying AMF to two-dimensional problems is quite old and goes back to Peaceman and Rachford in the early fifties. The situation in three space dimensions is less favourable and will be analyzed here in more detail, both theoretically and experimentally. Furthermore, we analyze a variant in which the AMF-technique has been used to really solve (‘until convergence’) the underlying Radau IIA method so that we can rely on its excellent stability and accuracy characteristics. Finally, the method has been tested on several examples. Also, a comparison has been made with the existing codes VODPK and IMEXRKC, and the efficiency (CPU time versus accuracy) is shown to be at least competitive with the efficiency of these solvers.     

A note on pseudo-symplectic Runge-Kutta methods

Aubry and Chartier introduced (1998) the concept of pseudo-symplecticness in order to construct explicit Runge-Kutta methods, which mimic symplectic ones. Of particular interest are methods of order (p, 2p), i.e., of orderp and pseudo-symplecticness order 2p, for which the growth of the global error remains linear. The aim of this note is to show that the lower bound for the minimal number of stages can be achieved forp=4 andp=5.     

On the stability of spline-collocation methods of multivalue type

In this paper the general classV of spline-collocation methods for first order systems of ordinary differential equations is investigated. The methods can in part be regarded as so-called multivalue methods. This type contains the generalized singly-implicit methods treated by Butcher.It is shown here, how any multivalue type representative ofV yields a matrix valued function, for the characterization of stability at infinity. It is shown in particular, that the structure of allows us to construct infinity-stable methods by an appropriate choice of the collocation points.     

Second order Chebyshev methods based on orthogonal polynomials

Summary. Stabilized methods (also called Chebyshev methods) are explicit Runge-Kutta methods with extended stability domains along the negative real axis. These methods are intended for large mildly stiff problems, originating mainly from parabolic PDEs. The aim of this paper is to show that with the use of orthogonal polynomials, we can construct nearly optimal stability polynomials of second order with a three-term recurrence relation. These polynomials can be used to construct a new numerical method, which is implemented in a code called ROCK2. This new numerical method can be seen as a combination of van der Houwen-Sommeijer-type methods and Lebedev-type methods. Received January 14, 2000 / Revised version received November 3, 2000 / Published online May 4, 2001     

Mean-square convergence of stochastic multi-step methods with variable step-size

We study mean-square consistency, stability in the mean-square sense and mean-square convergence of drift-implicit linear multi-step methods with variable step-size for the approximation of the solution of Itô stochastic differential equations. We obtain conditions that depend on the step-size ratios and that ensure mean-square convergence for the special case of adaptive two-step-Maruyama schemes. Further, in the case of small noise we develop a local error analysis with respect to the h$h$–ε$\epsilon$ approach and we construct some stochastic linear multi-step methods with variable step-size that have order 2 behaviour if the noise is small enough.     

Singularity Structure of Third-Order Dynamical Systems. II

The singularity structure of the solutions of a general third-order system, with polynomial right-hand sides of degree less than or equal to two, is studied about a movable singular point. An algorithm for transforming the given third-order system to a third-order Briot–Bouquet system is presented. The dominant behavior of a solution of the given system near a movable singularity is used to construct a transformation that changes the given system directly to a third-order Briot–Bouquet system. The results of Horn for the third-order Briot–Bouquet system are exploited to give the complete form of the series solutions of the given third-order system; convergence of these series in a deleted neighborhood of the singularity is ensured. This algorithm is used to study the singularity structure of the solutions of the Lorenz system, the Rikitake system, the three-wave interaction problem, the Rabinovich system, the Lotka–Volterra system, and the May–Leonard system for different sets of parameter values. The proposed approach goes far beyond the ARS algorithm.     

Third order nonoscillatory central scheme for hyperbolic conservation laws

Summary. A third-order accurate Godunov-type scheme for the approximate solution of hyperbolic systems of conservation laws is presented. Its two main ingredients include: 1. A non-oscillatory piecewise-quadratic reconstruction of pointvalues from their given cell averages; and 2. A central differencing based on staggered evolution of the reconstructed cell averages. This results in a third-order central scheme, an extension along the lines of the second-order central scheme of Nessyahu and Tadmor \cite{NT}. The scalar scheme is non-oscillatory (and hence – convergent), in the sense that it does not increase the number of initial extrema (– as does the exact entropy solution operator). Extension to systems is carried out by componentwise application of the scalar framework. In particular, we have the advantage that, unlike upwind schemes, no (approximate) Riemann solvers, field-by-field characteristic decompositions, etc., are required. Numerical experiments confirm the high-resolution content of the proposed scheme. Thus, a considerable amount of simplicity and robustness is gained while retaining the expected third-order resolution. Received April 10, 1996 / Revised version received January 20, 1997     

Comparative study on order-reduced methods for linear third-order ordinary differential equations

The linear third-order ordinary differential equation (ODE) can be transformed into a system of two second-order ODEs by introducing a variable replacement, which is different from the common order-reduced approach. We choose the functions p(x) and q(x) in the variable replacement to get different cases of the special order-reduced system for the linear third-order ODE. We analyze the numerical behavior and algebraic properties of the systems of linear equations resulting from the sinc discretizations of these special second-order ODE systems. Then the block-diagonal preconditioner is used to accelerate the convergence of the Krylov subspace iteration methods for solving the discretized system of linear equation. Numerical results show that these order-reduced methods are effective for solving the linear third-order ODEs.     

A third-order semi-discrete genuinely multidimensional central scheme for hyperbolic conservation laws and related problems

Summary. We construct a new third-order semi-discrete genuinely multidimensional central scheme for systems of conservation laws and related convection-diffusion equations. This construction is based on a multidimensional extension of the idea, introduced in [17] – the use of more precise information about the local speeds of propagation, and integration over nonuniform control volumes, which contain Riemann fans. As in the one-dimensional case, the small numerical dissipation, which is independent of , allows us to pass to a limit as . This results in a particularly simple genuinely multidimensional semi-discrete scheme. The high resolution of the proposed scheme is ensured by the new two-dimensional piecewise quadratic non-oscillatory reconstruction. First, we introduce a less dissipative modification of the reconstruction, proposed in [29]. Then, we generalize it for the computation of the two-dimensional numerical fluxes. Our scheme enjoys the main advantage of the Godunov-type central schemes –simplicity, namely it does not employ Riemann solvers and characteristic decomposition. This makes it a universal method, which can be easily implemented to a wide variety of problems. In this paper, the developed scheme is applied to the Euler equations of gas dynamics, a convection-diffusion equation with strongly degenerate diffusion, the incompressible Euler and Navier-Stokes equations. These numerical experiments demonstrate the desired accuracy and high resolution of our scheme. Received February 7, 2000 / Published online December 19, 2000     

On a class of higher order methods for simultaneous rootfinding of generalized polynomials

Summary Using the argument principle higher order methods for simultaneous computation of all zeros of generalized polynomials (like algebraic, trigonometric and exponential polynomials or exponential sums) are derived. The methods can also be derived following the continuation principle from [3]. Thereby, the unified approach of [7] is enlarged to arbitrary orderN. The local convergence as well as a-priori and a-posteriori error estimates for these methods are treated on a general level. Numerical examples are included.     

High order methods on Shishkin meshes for singular perturbation problems of convection–diffusion type

In this paper we construct and analyze two compact monotone finite difference methods to solve singularly perturbed problems of convection–diffusion type. They are defined as HODIE methods of order two and three, i.e., the coefficients are determined by imposing that the local error be null on a polynomial space. For arbitrary meshes, these methods are not adequate for singularly perturbed problems, but using a Shishkin mesh we can prove that the methods are uniformly convergent of order two and three except for a logarithmic factor. Numerical examples support the theoretical results. This revised version was published online in June 2006 with corrections to the Cover Date.     

Structure preservation of exponentially fitted Runge–Kutta methods

The preservation of some structure properties of the flow of differential systems by numerical exponentially fitted Runge–Kutta (EFRK) methods is considered. A complete characterisation of EFRK methods that preserve linear or quadratic invariants is given and, following the approach of Bochev and Scovel [On quadratic invariants and symplectic structure, BIT 34 (1994) 337–345], the sufficient conditions on symplecticity of EFRK methods derived by Van de Vyver [A fourth-order symplectic exponentially fitted integrator, Comput. Phys. Comm. 174 (2006) 255–262] are obtained. Further, a family of symplectic EFRK two-stage methods with order four has been derived. It includes the symplectic EFRK method proposed by Van de Vyver as well as a collocation method at variable nodes that can be considered as the natural collocation extension of the classical RK Gauss method. Finally, the results of some numerical experiments are presented to compare the relative merits of several fitted and nonfitted fourth-order methods in the integration of oscillatory systems.