Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

Acceleration methods based on convergence tests

Summary In this paper we propose an acceleration method based on a general convergence test and depending on an auxiliary sequence (x _n). For different choices of (x _n) we obtain some known and some new transformations and for each one sufficient conditions for acceleration are given.     

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.     

Gauss-Tchebycheff quadrature formulas

Summary It is well known that the Tchebycheff weight function (1-x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe explicitly all weight functions which have the property that then _k-point Gauss quadrature formula has equal weights for allk, where (n _k),n ₁<n ₂<..., is an arbitrary subsequence of . Furthermore results on the possibility of Tchebycheff quadrature on several intervals are given.     

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.     

On Gauss quadrature formulas with equal weights

Summary It is well known that the Chebyshev weight function (1–x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe all weight functions for which thenm point Gauss quadrature formula has equal weights for alln, wherem is fixed.     

Projektive Newton-Verfahren und Anwendungen auf nichtlineare Randwertaufgaben

Summary In this paper we consider the following Newton-like methods for the solution of nonlinear equations. In each step of the Newton method the linear equations are solved approximatively by a projection method. We call this a Projective Newton method. For a fixed projection method the approximations often are the same as those of the Newton method applied to a nonlinear projection method. But the efficiency can be increased by adapting the accuracy of the projection method to the convergence of the approximations. We investigate the convergence and the order of convergence for these methods. The results are applied to some Projective Newton methods for nonlinear two point boundary value problems. Some numerical results indicate the efficiency of these methods.

     

Regions of stability,equivalence theorems and the Courant-Friedrichs-Lewy condition

Summary The celebrated CFL condition for discretizations of hyperbolic PDEs is shown to be equivalent to some results of Jeltsch and Nevanlinna concerning regions of stability ofk-step,m-stage linear methods for the integration of ODEs. We characterize the methods for the numerical integration of the model equation,u _t=u _x which are weakly stable when the mesh-ratio takes the maximum value allowed by the CFL condition. We provide new equivalence theorems between stability and convergence, which improve on the classical results.     

Asymptotisches Verhalten und Konvergenzbeschleunigung von Iterationsfolgen

Summary The effectivity of iterative numerical methods depends on the rate of convergence. In this note general procedures to accelerate the convergence of finite-dimensional stationary one-step-methods (fixed point methods) by extrapolation methods are studied. In this connection the investigation of the asymptotic behaviour of the sequences is fundamental. Differentiability and contractivity qualities supposed in the following an asymptotic expansion for such iterative sequences is proved. Neglecting the remainder the expansion fulfils a linear difference equation with constant coefficients. Wynn's -algorithm work off this expansion term by term, and the attainable acceleration can be exactly estimated. Skelboe's convergence statement is refuted. First test results demonstrate the advantage of acceleration methods.

     

Some vector sequence transformations with applications to systems of equations

First, recursive algorithms for implementing some vector sequence transformations are given. In a particular case, these transformations are generalizations of Shanks transformation and the G-transformation. When the sequence of vectors under transformation is generated by linear fixed point iterations, Lanczos' method and the CGS are recovered respectively. In the case of a sequence generated by nonlinear fixed point iterations, a quadratically convergent method based on the -algorithm is recovered and a nonlinear analog of the CGS method is obtained.     

Sur les bornes d'erreur a posteriori pour les éléments propres d'opérateurs linéaires

Summary The theoretical framework of this study is presented in Sect. 1, with a review of practical numerical methods. The linear operatorT and its approximationT _n are defined in the same Banach space, which is a very common situation. The notion of strong stability forT _n is essential and cannot be weakened without introducing a numerical instability [2]. IfT (or its inverse) is compact, most numerical methods are strongly stable. Without compactness forT(T ^–1) they may not be strongly stable [20].In Sect. 2 we establish error bounds valid in the general setting of a strongly stable approximation of a closedT. This is a generalization of Vainikko [24, 25] (compact approximation). Osborn [19] (uniform and collectivity compact approximation) and Chatelin and Lemordant [6] (strong approximation), based on the equivalence between the eigenvalues convergence with preservation of multiplicities and the collectively compact convergence of spectral projections. It can be summarized in the following way: , eigenvalue ofT of multiplicitym is approximated bym numbers, _n is their arithmetic mean.- _n and the gap between invariant subspaces are of order _n =(T-T _n)P. IfT _n ^* converges toT ^*, pointwise inX ^*, the principal term in the error on - _n is . And for projection methods, withT _n= _n T, we get the bound . It applies to the finite element method for a differential operator with a noncompact resolvent. Aposteriori error bounds are given, and thegeneralized Rayleigh quotient TP _n appears to be an approximation of of the second order, as in the selfadjoint case [12].In Sect. 3, these results are applied to the Galerkin method and its Sloan variant [22], and to approximate quadrature methods. The error bounds and the generalized Rayleigh quotient are numerically tested in Sect. 4.

---

Sur les bornes d'erreur a posteriori pour les éléments propres d'opérateurs linéaires

     

On a theorem of Stein-Rosenberg type in interval analysis

Summary In classical numerical analysis the asymptotic convergence factor (R ₁-factor) of an iterative processx ^m+1=Ax^m+b coincides with the spectral radius of then×n iteration matrixA. Thus the famous Theorem of Stein and Rosenberg can at least be partly reformulated in terms of asymptotic convergence factor. Forn×n interval matricesA with irreducible upper bound and nonnegative lower bound we compare the asymptotic convergence factor ( _T ) of the total step method in interval analysis with the factor _S of the corresponding single step method. We derive a result similar to that of the Theorem of Stein and Rosenberg. Furthermore we show that _S can be less than the spectral radius of the real single step matrix corresponding to the total step matrix |A| where |A| is the absolute value ofA. This answers an old question in interval analysis.     

Splineapproximationen von beliebigem Defekt zur numerischen Lösung gewöhnlicher Differentialgleichungen. Teil III

Summary In the first part [1] a general procedure is presented to obtain polynomial spline approximations for the solutions of initial value problems for ordinary differential equations; furthermore a divergence theorem is proved there. Sufficient conditions for convergence of the method are given in the second part [2]. The remaining case which has not been considered in [1] and [2] is treated in the present paper. In this special case the procedure is equivalent to an unstable two-step method with special initial values; nevertheless, convergence can be proved. Finally,A ₀-stability of the method as well as the influence of rounding errors are investigated.

     

Regularization of nonlinear illposed problems with closed operators

In this paper Tikhonov regularization for nonlinear illposed problems is investigated. The regularization term is characterized by a closed linear operator, permitting seminorm regularization in applications. Results for existence, stability, convergence and con- vergence rates of the solution of the regularized problem in terms of the noise level are given. An illustrating example involving parameter estimation for a one dimensional stationary heat equation is given.     

The nonlinear programming method of Wilson,Han, and Powell with an augmented Lagrangian type line search function

Summary The paper represents an outcome of an extensive comparative study of nonlinear optimization algorithms. This study indicates that quadratic approximation methods which are characterized by solving a sequence of quadratic subproblems recursively, belong to the most efficient and reliable nonlinear programming algorithms available at present. The purpose of this paper is to analyse the theoretical convergence properties and to investigate the numerical performance in more detail. In Part 1, the exactL ₁-penalty function of Han and Powell is replaced by a differentiable augmented Lagrange function for the line search computation to be able to prove the global convergence and to show that the steplength one is chosen in the neighbourhood of a solution. In Part 2, the quadratic subproblem is exchanged by a linear least squares problem to improve the efficiency, and to test the dependence of the performance from different solution methods for the quadratic or least squares subproblem.     

Accelerating convergence of limit periodic continued fractionsK(a n /1)

Summary It is shown that the convergence of limit periodic continued fractionsK(a _n /1) with lima _n =a can be substantially accelerated by replacing the sequence of approximations {S _n (0)} by the sequence {S _n (x ₁)}, where . Specific estimates of the improvement are derived.     

The convergence of matrices generated by rank-2 methods from the restricted β-class of Broyden

Summary It is shown that the matricesB _k generated by any method from the restricted -class of Broyden converge, if the method is applied to the unconstrained minimization of a functionfC ²(R ⁿ ) with Lipschitz continuous ² f(x) and if the method is such that it generates vectorsx _k converging sufficiently fast to a local minimumx ^* off with positive definite ² f(x ^*). This result not only holds for constant step sizes _k 1 in each iterationx _k x _k+1=x _k – _k B _k ^–1 f(x _k ) of these methods but also for step sizes determined by asymptotically exact line searches. The paper generalizes corresponding results of Ge Ren-Pu and Powell [6] for the DFP and BFGS methods used in conjunction with step sizes _k 1.Dedicated to Professor F.L. Bauer on the occasion of his 60th birthday     

A new interpolation procedure for adapting Runge-Kutta methods to delay differential equations

This paper deals with adapting Runge-Kutta methods to differential equations with a lagging argument. A new interpolation procedure is introduced which leads to numerical processes that satisfy an important asymptotic stability condition related to the class of testproblemsU(t)=U(t)+U(t–) with , C, Re()<–||, and >0. Ifc _i denotes theith abscissa of a given Runge-Kutta method, then in thenth stept _n–1t _n :=t _n–1+h of the numerical process our interpolation procedure computes an approximation toU(t _n–1+c _i h–) from approximations that have already been generated by the process at pointst _j–1+c _i h(j=1,2,3,...). For two of these new processes and a standard process we shall consider the convergence behaviour in an actual application to a given, stiff problem.     

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.     

On the solution of singular linear systems of algebraic equations by semiiterative methods

Summary For a square matrixT ^n,n , where (I–T) is possibly singular, we investigate the solution of the linear fixed point problemx=T x+c by applying semiiterative methods (SIM's) to the basic iterationx ₀ ⁿ ,x _k T c _k–1+c(k1). Such problems arise if one splits the coefficient matrix of a linear systemA x=b of algebraic equations according toA=M–N (M nonsingular) which leads tox=M ^–1 N x+M ^–1 bT x+c. Even ifx=T x+c is consistent there are cases where the basic iteration fails to converge, namely ifT possesses eigenvalues 1 with ||1, or if =1 is an eigenvalue ofT with nonlinear elementary divisors. In these cases — and also ifx=T x+c is incompatible — we derive necessary and sufficient conditions implying that a SIM tends to a vector which can be described in terms of the Drazin inverse of (I–T). We further give conditions under which is a solution or a least squares solution of (I–T)x=c.Research supported in part by the Alexander von Humboldt-Stiftung