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.     

Improving a method for computing non-dominant solutions of certain second-order recurrence relations of Poincaré-type

Summary In this paper we present a method of convergence acceleration for the calculation of non-dominant solutions of second-order linear recurrence relations for which the coefficients satisfy certain asymptotic conditions. It represents an improvement of the method recently proposed by Jacobsen and Waadeland [3, 4] for limit periodic continued fractions. For continued fractions the method corresponds to a repeated application of the Bauer-Muir transformation. Some examples and a generalization to non-homogeneous recurrence relations are given.     

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.     

On a generalization of the Richardson extrapolation process

Summary A convergence result for a generalized Richardson extrapolation process is improved upon considerably and additional results of interest are proved. An application of practical importance is also given. Finally, some known results concerning the convergence of Levin's T-transformation are reconsidered in light of the results of the present work.     

Estimation of convergence orders in repeated richardson extrapolation

LetA(h) be an approximation depending on a single parameterh to a fixed quantityA, and assume thatA–A(h)=c ₁ h k ₁ +c ₂ h ^k ₂ +.... Given a sequence ofh-valuesh ₁>h ₂>...>h _n and corresponding computed approximationsA(h _i ), the orders for repeated Richardson extrapolation are estimated, and the repeated extrapolation is performed. Hence in this case the algorithm described here can do the same work as Brezinski'sE-algorithm and at the same time provide a check whether repeated extrapolation is justified.     

The average a posteriori error of numerical methods

Summary The definition of the average error of numerical methods (by example of a quadrature formula to approximateS(f)= f d on a function classF) is difficult, because on many important setsF there is no natural probability measure in the sense of an equidistribution. We define the average a posteriori error of an approximation by an averaging process over the set of possible information, which is used by (in the example of a quadrature formula,N(F)={(f(a ₁), ...,f/fF} is the set of posible information). This approach has the practical advantage that the averaging process is related only to finite dimensional sets and uses only the usual Lebesgue measure. As an application of the theory I consider the numerical integration of functions of the classF={f:[0,1]/f(x)–f(y)||x–y|}. For arbitrary (fixed) knotsa _i we determine the optimal coefficientsc _i for the approximation and compute the resulting average error. The latter is minimal for the knots . (It is well known that the maximal error is minimal for the knotsa _i .) Then the adaptive methods for the same problem and methods for seeking the maximum of a Lipschitz function are considered. While adaptive methods are not better when considering the maximal error (this is valid for our examples as well as for many others) this is in general not the case with the average error.     

Pointwise rational approximation and iterative methods for III-posed problems

Summary We study the connection between the pointwise approximation of the zero function by rational functions and iterative methods for the approximate solution of ill-posed linear equations. Results are presented on convergence, stability and saturation phenomena.Dedicated to Professor Dr. G. Hämmerlin on the occasion of his 60th birthday     

On two methods for accelerating convergence of series

Summary The Euler-Knopp transformation and a recently considered transformation, effective for entire function of order 1, are applied to series involving completely monotonic coefficients. Some properties of the resulting series are analyzed; these include uniform convergence with respect to the index, a priori and a posteriori estimates of the remainder. For the latter transformation a compact recursive algorithm is established which enables one to make effective use of the transformation. To illustrate the effectiveness of the transformations three applications, with examples, are included.     

Two composition methods for solving certain systems of linear equations

Summary This note is concerned with the following problem: Given a systemA·x=b of linear equations and knowing that certains of its subsystemsA ¹·x ¹=b ¹, ...,A ^m ·x ^m =b ^m can be solved uniquely what can be said about the regularity ofA and how to find the solutionx fromx ¹, ...,x ^m ? This question is of particular interest for establishing methods computing certain linear or quasilinear sequence transformations recursively [7, 13, 15].Work performed under NATO Research Grant 027-81     

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.     

Repeated modifications of limitk-periodic continued fractions

Summary The advantages of using modified approximants for continued fractions, can be enhanced by repeating the modification process. IfK(a _n /b _n) is limitk-periodic, a natural choice for the modifying factors is ak-periodic sequence of right or wrong tails of the correspondingk-periodic continued fraction, if it exists. If the modified approximants thus obtained are ordinary approximants of a new limitk-periodic continued fraction, we repeat the process, if possible. Some examples where this process is applied to obtain a convergence acceleration are also given.     

On richardson extrapolation for finite difference methods on regular grids

Summary Difference solutions of partial differential equations can in certain cases be expanded by even powers of a discretization parameterh. If we haven solutions corresponding to different mesh widthsh ₁,...,h _n we can improve the accuracy by Richardson extrapolation and get a solution of order 2n, yet only on the intersection of all grids used, i.e. normally on the coarsest grid. To interpolate this high order solution with the same accuracy in points not belonging to all grids, we need 2n points in an interval of length (2n–1)h ₁.This drawback can be avoided by combining such an interpolation with the extrapolation byh. In this case the approximation depends only on grid points in an interval of length 3/2h ₁. The length of this interval is independent of the desired order.By combining this approach with the method of Kreiss, boundary conditions on curved boundaries can be discretized with a high order even on coarse grids.This paper is based on a lecture held at the 5th Sanmarinian University Session of the International Academy of Sciences San Marino, at San Marino, 1988-08-27-1988-09-05     

On the convergence of multi-grid methods with transforming smoothers

Summary In the present paper we give a convergence theory for multi-grid methods with transforming smoothers as introduced in [31] applied to a general system of partial differential equations. The theory follows Hackbusch's approach for scalar pde and allows a convergence proof for some well-known multi-grid methods for Stokes- and Navier-Stokes equations as DGS by Brandt-Dinar, [5], TILU from [31] and the SIMPLE-methods by Patankar-Spalding, [23].This work was supported in part by Deutsche Forschungsgemeinschaft     

Equilibria of Runge-Kutta methods

Summary It is known that certain Runge-Kutta methods share the property that, in a constant-step implementation, if a solution trajectory converges to a bounded limit then it must be a fixed point of the underlying differential system. Such methods are calledregular. In the present paper we provide a recursive test to check whether given method is regular. Moreover, by examining solution trajectories of linear equations, we prove that the order of ans-stage regular method may not exceed 2[(s+2)/2] and that the maximal order of regular Runge-Kutta method with an irreducible stability function is 4.     

Linear convergence of the row cyclic Jacobi and Kogbetliantz methods

Summary Linear convergence of the row cyclic Jacobi and Kogbetliantz methods can be guaranteed if certain constraints concerning the angles of rotations are implemented. Unlike the results of Forsythe and Henrici, convergence can be achieved without under-rotations.This work was carried out under the MOD Contract No. A94C/2243 in collaboration with the Royal Signals and Radar Establishment     

Natural Runge-Kutta and projection methods

Summary Recently the author defined the class of natural Runge-Kutta methods and observed that it includes all the collocation methods. The present paper is devoted to a complete characterization of this class and it is shown that it coincides with the class of the projection methods in some polynomial spaces.This work was supported by the Italian Ministero della Pubblica Istruzione, funds 40%     

Rosenbrock methods for Differential Algebraic Equations

Summary This paper deals with the numerical solution of Differential/Algebraic Equations (DAE) of index one. It begins with the development of a general theory on the Taylor expansion for the exact solutions of these problems, which extends the well-known theory of Butcher for first order ordinary differential equations to DAE's of index one. As an application, we obtain Butcher-type results for Rosenbrock methods applied to DAE's of index one, we characterize numerical methods as applications of certain sets of trees. We derive convergent embedded methods of order 4(3) which require 4 or 5 evaluations of the functions, 1 evaluation of the Jacobian and 1 LU factorization per step.     

An algebraic characterization ofB-convergent Runge-Kutta methods

Summary In the analysis of discretization methods for stiff intial value problems, stability questions have received most part of the attention in the past.B-stability and the equivalent criterion algebraic stability are well known concepts for Runge-Kutta methods applied to dissipative problems. However, for the derivation ofB-convergence results — error bounds which are not affected by stiffness — it is not sufficient in many cases to requireB-stability alone. In this paper, necessary and sufficient conditions forB-convergence are determined.This paper was written while J. Schneid was visiting the Centre for Mathematics and Computer Science with an Erwin-Schrödinger stipend from the Fonds zur Förderung der wissenschaftlichen Forschung     

Linearly implicit extrapolation methods for differential-algebraic systems

Summary We consider the numerical solution of implicit differential equations in which the solution derivative appears multiplied by a solution-dependent singular matrix. We study extrapolation methods based on two linearly implicit Euler discretizations. Their error behaviour is explained by perturbed asymptotic expansions.