On the Starting Algorithms for Fully Implicit Runge-Kutta Methods

This paper is concerned with the behavior of starting algorithms to solve the algebraic equations of stages arising when fully implicit Runge-Kutta methods are applied to stiff initial value problems. The classical Lagrange extrapolation of the internal stages of the preceding step and some variants thereof that do not require any additional cost are analyzed. To study the order of the starting algorithms we consider three different approaches. First we analyze the classical order through the theory of Butcher's series, second we derive the order on the Prothero and Robinson model and finally we study the stiff order for a general class of dissipative problems. A detailed study of the orders of some starting algorithms for Gauss, Radau IA-IIA, Lobatto IIIA-C methods is also carried out. Finally, to compare the most relevant starting algorithms studied here, some numerical experiments on well known nonlinear stiff problems are presented.     

On the convergence of Runge–Kutta methods for stiff non linear differential equations

Summary. This paper studies the convergence properties of general Runge–Kutta methods when applied to the numerical solution of a special class of stiff non linear initial value problems. It is proved that under weaker assumptions on the coefficients of a Runge–Kutta method than in the standard theory of B-convergence, it is possible to ensure the convergence of the method for stiff non linear systems belonging to the above mentioned class. Thus, it is shown that some methods which are not algebraically stable, like the Lobatto IIIA or A-stable SIRK methods, are convergent for the class of stiff problems under consideration. Finally, some results on the existence and uniqueness of the Runge–Kutta solution are also presented. Received November 18, 1996 / Revised version received October 6, 1997     

On improving the absolute stability of local extrapolation

Summary A widely used technique for improving the accuracy of solutions of initial value problems in ordinary differential equations is local extrapolation. It is well known, however, that when using methods appropriate for solving stiff systems of ODES, the stability of the method can be seriously degraded if local extrapolation is employed. This is due to the fact that performing local extrapolation on a low order method is equivalent to using a higher order formula and this high order formula may not be suitable for solving stiff systems. In the present paper a general approach is proposed whereby the correction term added on in the process of local extrapolation is in a sense a rational, rather than a polynomial, function. This approach allows high order formulae with bounded growth functions to be developed. As an example we derive anA-stable rational correction algorithm based on the trapezoidal rule. This new algorithm is found to be efficient when low accuracy is requested (say a relative accuracy of about 1%) and its performance is compared with that of the more familiar Richardson extrapolation method on a large set of stiff test problems.     

Exponential fitted Gauss, Radau and Lobatto methods of low order

Several exponential fitting Runge-Kutta methods of collocation type are derived as a generalization of the Gauss, Radau and Lobatto traditional methods of two steps. The new methods are capable of the exact integration (with only round-off errors) of differential equations whose solutions are linear combinations of an exponential and ordinary polynomials. Theorems of the truncation error reveal the good behavior of the new methods for stiff problems. Plots of their absolute stability regions that include the whole of the negative real axis are provided. A different procedure to find the parameter of the method is proposed. The variable step Radau method of two stages is derived. Finally, numerical examples underscore the efficiency of the proposed codes, especially when they are integrating stiff problems.      

Approximation results by difference schemes of fracture energies: the vectorial case

In this paper we deal with Monge-Ampère type equations in two dimensions and, using the symmetrization with respect to the perimeter, we prove some comparison results for solutions of such equations involving the solutions of conveniently symmetrized problems.     

Comparison results for Monge-Ampère type equations with lower order terms

In this paper we deal with Monge-Ampère type equations in two dimensions and, using the symmetrization with respect to the perimeter, we prove some comparison results for solutions of such equations involving the solutions of conveniently symmetrized problems.     

Variable-Order ESIRK Methods for Stiff Differential Equations

ESIRK methods (Effective order Singly-Implicit Runge–Kutta methods) have been shown to be efficient for the numerical solution of stiff differential equations. In this paper, we consider a new implementation of these methods with a variable order strategy. We show that the efficiency of the ESIRK method for stiff problems is improved by using the proposed variable order schemes.     

On the solvability of the systems of equations arising in implicit Runge-Kutta methods

In this paper we present a new condition under which the systems of equations arising in the application of an implicit Runge-Kutta method to a stiff initial value problem, has unique solutions. We show that our condition is weaker than related conditions presented previously. It is proved that the Lobatto IIIC methods fulfil the new condition.     

A family of A-stable Runge Kutta collocation methods of higher order for initial-value problems

^{We consider the construction of a special family of Runge–Kutta(RK) collocation methods based on intra-step nodal points ofChebyshev–Gauss–Lobatto type, with A-stability andstiffly accurate characteristics. This feature with its inherentimplicitness makes them suitable for solving stiff initial-valueproblems. In fact, the two simplest cases consist in the well-knowntrapezoidal rule and the fourth-order Runge–Kutta–LobattoIIIA method. We will present here the coefficients up to eighthorder, but we provide the formulas to obtain methods of higherorder. When the number of stages is odd, we have considereda new strategy for changing the step size based on the use ofa pair of methods: the given RK method and a linear multistepone. Some numerical experiments are considered in order to checkthe behaviour of the methods when applied to a variety of initial-valueproblems.}     

An application of some high order operator splitting methods to systems of stiff differential equations

In this work we compare operator splitting methods of high order that are applied to problems with stiff matrices. In order to efficiently solve the resultant subproblems is possible to use implicit Runge-Kutta methods. We apply an alternative extrapolation technique that works well for the tested problems. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spectral Deferred Correction Methods for Ordinary Differential Equations

We introduce a new class of methods for the Cauchy problem for ordinary differential equations (ODEs). We begin by converting the original ODE into the corresponding Picard equation and apply a deferred correction procedure in the integral formulation, driven by either the explicit or the implicit Euler marching scheme. The approach results in algorithms of essentially arbitrary order accuracy for both non-stiff and stiff problems; their performance is illustrated with several numerical examples. For non-stiff problems, the stability behavior of the obtained explicit schemes is very satisfactory and algorithms with orders between 8 and 20 should be competitive with the best existing ones. In our preliminary experiments with stiff problems, a simple adaptive implementation of the method demonstrates performance comparable to that of a state-of-the-art extrapolation code (at least, at moderate to high precision).Deferred correction methods based on the Picard equation appear to be promising candidates for further investigation.     

Iterative operator-splitting methods with higher-order time integration methods and applications for parabolic partial differential equations

In this paper we design higher-order time integrators for systems of stiff ordinary differential equations. We combine implicit Runge–Kutta and BDF methods with iterative operator-splitting methods to obtain higher-order methods. The idea of decoupling each complicated operator in simpler operators with an adapted time scale allows to solve the problems more efficiently. We compare our new methods with the higher-order fractional-stepping Runge–Kutta methods, developed for stiff ordinary differential equations. The benefit is the individual handling of each operator with adapted standard higher-order time integrators. The methods are applied to equations for convection–diffusion reactions and we obtain higher-order results. Finally we discuss the applications of the iterative operator-splitting methods to multi-dimensional and multi-physical problems.     

Squared polynomial extrapolation methods with cycling: an application to the positron emission tomography problem

Roland and Varadhan (Appl. Numer. Math., 55:215–226, 2005) presented a new idea called “squaring” to improve the convergence of Lemaréchal’s scheme for solving nonlinear fixed-point problems. Varadhan and Roland (Squared extrapolation methods: A new class of simple and efficient numerical schemes for accelerating the convergence of the EM algorithm, Department of Biostatistics Working Paper. Johns Hopkins University, , 2004) noted that Lemaréchal’s scheme can be viewed as a member of the class of polynomial extrapolation methods with cycling that uses two fixed-point iterations per cycle. Here we combine these two ideas, cycled extrapolation and squaring, and construct a new class of methods, called squared polynomial methods (SQUAREM), for accelerating the convergence of fixed-point iterations. Our main goal is to evaluate whether the squaring device is effective in improving the rate of convergence of cycled extrapolation methods that use more than two fixed-point iterations per cycle. We study the behavior of the new schemes on an image reconstruction problem for positron emission tomography (PET) using simulated data. Our numerical experiments show the effectiveness of first- and higher-order squared polynomial extrapolation methods in accelerating image reconstruction, and also their relative superiority compared to the classical, “unsquared” vector polynomial methods.     

Efficient implementation of Radau collocation methods

In this paper we define an efficient implementation of Runge–Kutta methods of Radau IIA type, which are commonly used when solving stiff ODE-IVPs problems. The proposed implementation relies on an alternative low-rank formulation of the methods, for which a splitting procedure is easily defined. The linear convergence analysis of this splitting procedure exhibits excellent properties, which are confirmed by its performance on a few numerical tests.     

NP-stability of Runge-Kutta methods based on classical quadrature

Recently Bellen, Jackiewicz and Zennaro have studied stability properties of Runge-Kutta (RK) methods for neutral delay differential equations using a scalar test equation. In particular, they have shown that everyA-stable collocation method isNP-stable, i.e., the method has an analogous stability property toA-stability with respect to the test equation. Consequently, the Gauss, Radau IIA and Lobatto IIIA methods areNP-stable. In this paper, we examine the stability of RK methods based on classical quadrature by a slightly different approach from theirs. As a result, we prove that the Radau IA and Lobatto IIIC methods equipped with suitable continuous extensions are alsoNP-stable by virtue of fundamental notions related to those methods such as simplifying conditions, algebraic stability, and theW-transformation.     

MODIFIED PARALLEL ROSENBROCK METHODS FOR STIFF DIFFERENTIAL EQUATIONS

1. IntroductionIn many fields of science and engineering technology, we often meet with stiff ordinarydifferential equations. In order to solve these systems, we have to use the implicit methods,which lneans that nonlinear implicit equations must be solve…     

Estimating Joint Distributions of Markov Chains

Suppose we observe a stationary Markov chain with unknown transition distribution. The empirical estimator for the expectation of a function of two successive observations is known to be efficient. For reversible Markov chains, an appropriate symmetrization is efficient. For functions of more than two arguments, these estimators cease to be efficient. We determine the influence function of efficient estimators of expectations of functions of several observations, both for completely unknown and for reversible Markov chains. We construct simple efficient estimators in both cases.     

Speeding up Newton-type iterations for stiff problems

Iterative schemes based on the Cooper and Butcher iteration [5] are considered, in order to implement highly implicit Runge–Kutta methods on stiff problems. By introducing two appropriate parameters in the scheme, a new iteration making use of the last two iterates, is proposed. Specific schemes of this type for the Gauss, Radau IA-IIA and Lobatto IIIA-B-C processes are developed. It is also shown that in many situations the new iteration presents a faster convergence than the original.     

数值解多维问题的外推与组合技术的若干新进展

本文综述近年来数值解多维问题的外推与组合技术的新进展，内容包括分裂外推及其在偏微分方程、多堆积分方程、多维数值积分中的应用；Ｃ．Ｚｅｎｇｅｒ的稀疏网格法与组合求解技术；以及解边界积分方程的组合方法，本文通过算例表明这些方法是非常有效的，是解多维问题的钥匙。     

Matrix free MEBDF method for the solution of stiff systems of ODEs

In this paper, we present the details of a new method which is a hybrid method of MF-BDF and MEBDF. To obtain this new method which we call MF-MEBDF, we compose the matrix free properties of the first method and the accuracy of MEBDF, elaborately. Application of this new method to some important stiff problems show that MF-MEBDF is generally faster than MEBDF and more accurate than MF-BDF and MEBDF. Since in MEBDF, the LU factorization is used, we expect MF-MEBDF to be more efficient than the other two methods for large stiff systems of ODEs.