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.     

Order conditions for canonical Runge-Kutta-Nyström methods

We are concerned with Runge-Kutta-Nyström methods for the integration of second order systems of the special formd ² y/dt ²=f(y). If the functionf is the gradient of a scalar field, then the system is Hamiltonian and it may be advantageous to integrate it by a so-called canonical Runge-Kutta-Nyström formula. We show that the equations that must be imposed on the coefficients of the method to ensure canonicity are simplifying assumptions that lower the number of independent order conditions. We count the number of order conditions, both for general and for canonical Runge-Kutta-Nyström formulae.This research has been supported by Junta de Castilla y León under project 1031-89 and by Dirección General de Investigación Científica y Técnica under project PB89-0351.     

Symplectic integration of Hamiltonian wave equations

Summary The numerical integration of a wide class of Hamiltonian partial differential equations by standard symplectic schemes is discussed, with a consistent, Hamiltonian approach. We discretize the Hamiltonian and the Poisson structure separately, then form the the resulting ODE's. The stability, accuracy, and dispersion of different explicit splitting methods are analyzed, and we give the circumstances under which the best results can be obtained; in particular, when the Hamiltonian can be split into linear and nonlinear terms. Many different treatments and examples are compared.     

Error analysis and applications of the Fourier-Galerkin Runge-Kutta schemes for high-order stiff PDEs

An integrating factor mixed with Runge-Kutta technique is a time integration method that can be efficiently combined with spatial spectral approximations to provide a very high resolution to the smooth solutions of some linear and nonlinear partial differential equations. In this paper, the novel hybrid Fourier-Galerkin Runge-Kutta scheme, with the aid of an integrating factor, is proposed to solve nonlinear high-order stiff PDEs. Error analysis and properties of the scheme are provided. Application to the approximate solution of the nonlinear stiff Korteweg-de Vries (the 3rd order PDE, dispersive equation), Kuramoto-Sivashinsky (the 4th order PDE, dissipative equation) and Kawahara (the 5th order PDE) equations are presented. Comparisons are made between this proposed scheme and the competing method given by Kassam and Trefethen. It is found that for KdV, KS and Kawahara equations, the proposed method is the best.     

The non-existence of symplectic multi-derivative Runge-Kutta methods

A sufficient condition for the symplecticness ofq-derivative Runge-Kutta methods has been derived by F. M. Lasagni. In the present note we prove that this condition can only be satisfied for methods withq1, i.e., for standard Runge-Kutta methods. We further show that the conditions of Lasagni are also necessary for symplecticness so that no symplectic multi-derivative Runge-Kutta method can exist.This research has been supported by project PB89-0351 (Dirección General de Investigación Científica y Técnica) and by project No. 20-32354.91 of Swiss National Science Foundation.     

Global error estimation and control in linearly-implicit parallel two-step peer W-methods

The class of linearly-implicit parallel two-step peer W-methods has been designed recently for efficient numerical solutions of stiff ordinary differential equations. Those schemes allow for parallelism across the method, that is an important feature for implementation on modern computational devices. Most importantly, all stage values of those methods possess the same properties in terms of stability and accuracy of numerical integration. This property results in the fact that no order reduction occurs when they are applied to very stiff problems. In this paper, we develop parallel local and global error estimation schemes that allow the numerical solution to be computed for a user-supplied accuracy requirement in automatic mode. An algorithm of such global error control and other technical particulars are also discussed here. Numerical examples confirm efficiency of the presented error estimation and stepsize control algorithm on a number of test problems with known exact solutions, including nonstiff, stiff, very stiff and large-scale differential equations. A comparison with the well-known stiff solver RODAS is also shown.     

Some remarks on an ODE-solver of Kirchgraber

Summary Kirchgraber derived in 1988 an integration procedure (called the LIPS-code) for long-term prediction of the solutions of equations which are perturbations of systems having only periodic solutions. His basic idea is to use the Poincaré map to define a new system which can be integrated with large step-size; the method is specially successful when the period is close to the unperturbed one. Obviously the size of the perturbation modifies the period and therefore affects the precision of the algorithm. In this paper we propose a double modification of Kirchgraber's code: to use a first-order approximation of the perturbed period instead of the unperturbed one, and a scheme specially designed for integration of orbits instead of the Runge-Kutta method. We show that this new code permits a spectacular improvement in accuracy and computation time.     

Butcher's simplifying assumption for symplectic integrators

Implicit Runge-Kutta methods with vanishingM matrix are discussed for preserving the symplectic structure of Hamiltonian systems. The number of the order conditions independent of the number of stages can be reduced considerably for the symplectic IRK method through the analysis utilizing the rooted tree and the corresponding elementary differentials. Butcher's simplifying condition further reduces the number of independent order conditions.     

Discrete mechanics and its application to the solution of the n-body problem

A theory of discrete mechanics is developed based on the results of D. Greenspan. Discrete dynamical equations in an inertial frame, in a coordinate system related to some material point, and in a rotating frame are given and the consistency, stability, and convergence of the methods are studied and some numerical examples presented.     

On the influence of numerical preservation of invariants when simulating Hamiltonian relative periodic orbits

We study the structure of the error when simulating relative periodic solutions of Hamiltonian systems with symmetries. We identify the mechanisms for which the preservation, in the numerical integration, of the Hamiltonian and the invariants associated to the symmetry group, implies a better time behavior of the error. A second consequence is a more correct simulation of the parameters that characterize the relative periodic orbit.     

A formulation to obtain semi-analytical planetary theories using true anomalies as temporal variables

The main methods used to obtain analytical theories of perturbed motion in celestial mechanics are based on the expansion of the disturbing function in trigonometric series of the mean anomalies (or longitudes). In this paper a new method based on the double Fourier series expansion using the true anomalies (or longitudes) is developed. The method involves a semi-analytical technique to allow the expansion of the inverse of the distance with great accuracy, and a new integration technique using a linear combination of the true anomalies based on an iterative method to integrate each term of the expansion of the Lagrange planetary equations.     

Error propagation in numerical approximations near relative equilibria

We study the propagation of errors in the numerical integration of perturbations of relative equilibrium solutions of Hamiltonian differential equations with symmetries. First it is shown that taking an initial perturbation of a relative equilibrium, the corresponding solution is related, in a first approximation, to another relative equilibrium, with the parameters perturbed from the original. Then, this is used to prove that, for stable relative equilibria, error growth with respect to the perturbed solution is in general quadratic, but only linear for schemes that preserve the invariant quantities of the problem. In this sense, the conclusion is similar to the one obtained when integrating unperturbed relative equilibria. Numerical experiments illustrate the results.     

A robust trigonometrically fitted embedded pair for perturbed oscillators

A new kind of trigonometrically fitted embedded pair of explicit ARKN methods for the numerical integration of perturbed oscillators is presented in this paper. This new pair is based on the trigonometrically fitted ARKN method of order five derived by Yang and Wu in [H.L. Yang, X.Y. Wu, Trigonometrically-fitted ARKN methods for perturbed oscillators, Appl. Numer. Math. 9 (2008) 1375–1395]. We analyze the stability properties, phase-lag (dispersion) and dissipation of the higher-order method of the new pair. Numerical experiments carried out show that our new embedded pair is very competitive in comparison with the embedded pairs proposed in the scientific literature.     

Preconditioners for spectral element methods for elliptic and parabolic problems

In this paper we propose preconditioners for spectral element methods for elliptic and parabolic problems. These preconditioners are constructed using separation of variables and are easy to invert. Moreover they are spectrally equivalent to the quadratic forms which they are used to approximate.     

Saving flops in LU based shift-and-invert strategy

The shift-and-invert method is very efficient in eigenvalue computations, in particular when interior eigenvalues are sought. This method involves solving linear systems of the form (A−σI)z=b. The shift σ is variable, hence when a direct method is used to solve the linear system, the LU factorization of (A−σI) needs to be computed for every shift change. We present two strategies that reduce the number of floating point operations performed in the LU factorization when the shift changes. Both methods perform first a preprocessing step that aims at eliminating parts of the matrix that are not affected by the diagonal change. This leads to about 43% and 50% flops savings respectively for the dense matrices.     

Constrained least squares methods for linear timevarying DAE systems

Summary This paper presents a family of methods for accurate solution of higher index linear variable DAE systems, . These methods use the DAE system and some of its first derivatives as constraints to a least squares problem that corresponds to a Taylor series ofy, or an approximative equality derived from a Pade' approximation of the exponential function. Accuracy results for systems transformable to standard canonical form are given. Advantages, disadvantages, stability properties and implementation of these methods are discussed and two numerical examples are given, where we compare our results with results from more traditional methods.     

Polynomial root computation by means of the LR algorithm

By representing the LR algorithm of Rutishauser and its variants in a polynomial setting, we derive numerical methods for approximating either all of the roots or a numberk of the roots of minimum modulus of a given polynomialp(t) of degreen. These methods share the convergence properties of the LR matrix iteration but, unlike it, they can be arranged to produce parallel and sequential algorithms which are highly efficient especially in the case wherek≪n. Supported by 40% and 60% funds of the Progetto Analisi numerica e matematica computazionale of MURST and by G.N.I.M. of C.N.R.     

Implementation of a modified Marder–Weitzner method for solving nonlinear eigenvalue problems

Our goal is to propose four versions of modified Marder–Weitzner methods and to present the implementation of the new-type methods with incremental unknowns for solving nonlinear eigenvalue problems. By combining with compact schemes and modified Marder–Weitzner methods, six schemes well suited for the calculation of unstable solutions are obtained. We illustrate the efficiency of the new algorithms by using numerical computations and by comparing them with existing methods for some two-dimensional problems.     

Twostep-by-twostep PIRK-type PC methods with continuous output formulas

This paper deals with parallel predictor–corrector (PC) iteration methods based on collocation Runge–Kutta (RK) corrector methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of first-order differential equations. At n$n$th step, the continuous output formulas are used not only for predicting the stage values in the PC iteration methods but also for calculating the step values at (n+2)$(n+2)$th step. In this case, the integration processes can be proceeded twostep-by-twostep. The resulting twostep-by-twostep (TBT) parallel-iterated RK-type (PIRK-type) methods with continuous output formulas (twostep-by-twostep PIRKC methods or TBTPIRKC methods) give us a faster integration process. Fixed stepsize applications of these TBTPIRKC methods to a few widely-used test problems reveal that the new PC methods are much more efficient when compared with the well-known parallel-iterated RK methods (PIRK methods), parallel-iterated RK-type PC methods with continuous output formulas (PIRKC methods) and sequential explicit RK codes DOPRI5 and DOP853 available from the literature.