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.     

Development of the Levin-type algorithms for accelerating convergence of sequences

There are two aims of this paper. Firstly we shall introduce the determinantal representations of the new Levin-type algorithms and secondly we shall demonstrate further development of the Levin-type algorithms. We consider the use of the Levin-type algorithms to accelerate the convergence of scalar sequence and their effectiveness for approximating the solution of a given power series is illustrated. In process we shall demonstrate the convergence of each of the methods considered. The approximate solution of the super enhanced Levin algorithm and the efficient Levin algorithm are found to be substantially more accurate than the Cizek, Zamastil and Skala transformation and the iterated Aitken Δ²${\mathrm{\Delta }}^2$ algorithm.     

Extensions of Levin's transformations to vector sequences

Levin's transformations are extended to vector sequences. Convergence theorems for certain linear and certain logarithmic vector sequences are proved. Numerical examples are also given.     

Pointwise inclusions of fixed points by finite dimensional iteration schemes

Summary Finite dimensional iteration schemes which provide pointwise bounds for the solutions of nonlinear integral equations are considered. The method is based on a discretization technique which takes advantage of apriori known structure properties of the solutions. The resulting iteration can be carried out on a computer for as many steps as desired. Its high degree of accuracy is shown by numerical examples.     

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.     

On the relation between quadratic termination and convergence properties of minimization algorithms

Summary It is shown that the theory developed in part I of this paper [22] can be applied to some well-known minimization algorithms with the quadratic termination property to prove theirn-step quadratic convergence. In particular, some conjugate gradient methods, the rank-1-methods of Pearson and McCormick (see Pearson [18]) and the large class of rank-2-methods described by Oren and Luenberger [16, 17] are investigated.This work was supported in part at Stanford University, Stanford, California, under Energy Research and Development Administration, Contract E(04-3) 326 PA No. 30, and National Science Foundation Grant DCR 71-01996 A04 and in part by the Deutsche Forschungsgemeinschaft     

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.     

On the D-suitability of implicit Runge-Kutta methods

The concept of suitability means that the nonlinear equations to be solved in an implicit Runga-Kutta method have a unique solution. In this paper, we introduce the concept of D-suitability and show that previous results become special cases of ours. In addition, we also give some examples to illustrate the D-suitability of a matrixA.     

On fixed point linear equations

Summary By means of successive partial substitutions it is possible to obtain new fixed point linear equations from old ones and it is interesting to determine how the spectral radius of the corresponding matrices varies. We prove that, when the original matrix is nonnegative, this variation is decreasing or increasing, depending on whether the original matrix has its spectral radius smaller or greater than 1. We answer in this way a question posed by F. Robert in [5].     

A modification of the stiefel-bettis method for nonlinearly damped oscillators

We report a modification of the Stiefel-Bettis method which is of trigonometric order one and of polynomial order two for the general second order initial value problems. We also discuss the modified Stiefel-Bettis method made explicit for the undamped nonlinear oscillators. Numerical solution of problems are given to illustrate the methods.     

Some convergence results for asynchronous algorithms

Resumé Nous présentons dans cet article des résultats de convergence des algorithmes asynchrones basés essentiellement sur la notion classique de contraction.Nous généralisons, en particulier, tous les résultats de convergence de ces algorithmes qui font l'hypothèse de contraction en norme vectorielle qui récemment a été très souvant utilisée.Par ailleurs, l'hypothèse de contraction en norme vectorielle peut se trouver difficile, voire impossible à vérifier pour certains problèmes qui peuvent être cependant abordés dans le cadre de la contraction classique que nous adoptons.

---

Some convergence results for asynchronous algorithms

Summary In this paper we present convergence results for the asynchronous algorithms based essentially on the notion of classical contraction.We generalize, in particular, all convergence results for those algorithms which are based on the vectorial norm hypothesis, in wide spread use recently.Certain problems, for which the vectorial norm hypothesis can be difficult or even impossible to verify, can nontheless be tackled within the scope of the classical contraction that we adopte.

     

Convergence acceleration of continued fractions of Poincaré's type 1

A new method of convergence acceleration is proposed for continued fractions of Poincaré's type 1. Each step of the method (and not only the first one, as in the Hautot method [1]) is based on an asymptotic behaviour of continued fraction tails. A theorem is proved detailing properties of the method in six cases considered here. Results of numerical tests for all Hautot's examples confirm a good performance of the method.     

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.     

Error analysis of splitting algorithms for polynomials

An error analysis is given for the general splitting algorithm, proposed by Shaw and Traub, for evaluating a polynomial and some of its derivatives. The results show that the usual synthetic division is least likely to be affected by round-off errors if only single-precision arithmetic is available for all the algorithms. However, the new splitting algorithms are better than the synthetic division if extended-precision arithmetic is available for the evaluation of powers ofx.This work supported in part by the United States Air Force under grant AFOSR 76-3020     

Nonlinear hybrid procedures and fixed point iterations

Let (x_n) and (?_n) be two vector sequences converging to a common limit. First, we shall define nonlinear hybrid procedures which consist of constructing a new vector sequence (y_n) with better convergence properties than (x_n) and (?_n). Then, this procedure is used for accelerating the convergence of a given sequence and applied to the construction of fixed point methods. New methods are derived. Finally, the connection between fixed point iterations and methods for the numerical integration of differential equations is also exploited. Numerical results are given.     

Vorzeichenstabile Differenzenverfahren für parabolische Anfangsrandwertaufgaben

Summary In this paper we consider certain structure conserving properties of finite difference methods for the solution of parabolic initial-boundary value problems. We are interested in conditions on the step size ratio =t/x ² in one-step methods which guarantee that the number of sign changes of the discrete approximation does not increase while proceeding from one time level to the following one. This means that difference schemes of this type possess a so-called variation-diminishing property which is known to hold for continuous diffusion equations also. It turns out that our conditions on are stronger than the classical ones which imply the maximum principle for the finite difference equations. By means of an example we show that our sign stability condition is necessary too.

     

A short note on the generalized Euler transform for the summation of power series

Applying the generalized Euler transform to the firstn partial sums of a power series results in a triangular array whose inferior diagonal givesn approximate values of the sum of this series. The aim of this short note is to estimate the best of thesen values and to compare it with the actual best one for a collection of test series.     

Baryzentrische Formeln zur Trigonometrischen Interpolation (I)

Summary Barycentric formulas for the interpolation of a periodic functionf by a trigonometric polynomial have been given by Salzer [11] in the case of an odd number of arbitrary (interpolating) points and by Henrici [7] in the special case of equidistant points. We present here formulas for the interpolation with an even number of arbitrary points as well as simpler versions for an even or an odd functionf.

Der Autor dankt Dr. M. H. Gutknecht und Prof. P. Henrici, ohne welche diese Arbeit vielleicht nicht entstanden wäre.     

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.     

Taylorian fields and subdivision algorithms

Some recents papers [3,8] provide a new approach for the concept of subdivision algorithms, widely used in CAGD: they develop the idea of interpolatory subdivision schemes for curves. In this paper, we show how the old results of H. Whitney [13,14] on Taylorian fields giving necessary and sufficient conditions for a function to be of classC ^k on a compact provide also necessary and sufficient conditions which can be used to construct interpolatory subdivision schemes, in order to obtain, at the limit, aC ¹ (orC ^k ,k>1 eventually) function. Moreover, we give general results for the approximation properties of these schemes, and error bounds for the approximation of a given function.