B-convergence properties of defect correction methods. I

Summary B-convergence properties of defect correction methods based on the implicit Euler and midpoint schemes are discussed. The property ofB-convergence means that there exist global error bounds for nonlinear stiff problems independent of their stiffness. It turns out that the orders ofB-convergence of these methods coincide with the conventional orders of convergence of these methods derived under the assumption that.hL is small (whereL is a Lipschitz constant of the right-hand side). In Part I these assertions are reduced to the validity of the so-called Hypothesis A which is discussed in greater detail in Part II. Numerical experiments confirming the theoretical analysis are also given in Part II.     

On the relation between algebraic stability andB-convergence for Runge-Kutta methods

Summary This paper is concerned with the numerical solution of stiff initial value problems for systems of ordinary differential equations using Runge-Kutta methods. For these and other methods Frank, Schneid and Ueberhuber [7] introduced the important concept ofB-convergence, i.e. convergence with error bounds only depending on the stepsizes, the smoothness of the exact solution and the so-called one-sided Lipschitz constant . Spijker [19] proved for the case <0 thatB-convergence follows from algebraic stability, the well-known criterion for contractivity (cf. [1, 2]). We show that the order ofB-convergence in this case is generally equal to the stage-order, improving by one half the order obtained in [19]. Further it is proved that algebraic stability is not only sufficient but also necessary forB-convergence.This study was completed while this author was visiting the Oxford University Computing Laboratory with a stipend from the Netherlands Organization for Scientific Research (N.W.O.)     

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     

B-Convergence of Lobatto IIIC formulas

Summary A completion ofB-convergence results of Lobatto IIIC schemes is presented. In particular, it is shown that Lobatto IIIC schemes with more than two stages areB-convergent when applied to IVPs with a negative one-sided Lipschitz constantm; they are notB-convergent, however, for IVPs with a non-negativem.     

B-convergence results for linearly implicit one step methods

B-consistency andB-convergence of linearly implicit one step methods with respect to a class of arbitrarily stiff semi-linear problems are considered. Order conditions are derived. An algorithm for constructing methods of order>1 is shown and examples are given. By suitable modifications of the methods the occurring order reduction is decreased.     

Order results for Rosenbrock type methods on classes of stiff equations

Summary In this paper we give conditions for theB-convergence of Rosenbrock type methods when applied to stiff semi-linear systems. The convergence results are extended to stiff nonlinear systems in singular perturbation form. As a special case partitioned methods are considered. A third order method is constructed.Dedicated to the memory of Professor Lothar Collatz     

High orderP-stable formulae for the numerical integration of periodic initial value problems

Summary Recently there has been considerable interest in the approximate numerical integration of the special initial value problemy=f(x, y) for cases where it is known in advance that the required solution is periodic. The well known class of Störmer-Cowell methods with stepnumber greater than 2 exhibit orbital instability and so are often unsuitable for the integration of such problems. An appropriate stability requirement for the numerical integration of periodic problems is that ofP-stability. However Lambert and Watson have shown that aP-stable linear multistep method cannot have an order of accuracy greater than 2. In the present paper a class of 2-step methods of Runge-Kutta type is discussed for the numerical solution of periodic initial value problems.P-stable formulae with orders up to 6 are derived and these are shown to compare favourably with existing methods.     

The order ofB-convergence of algebraically stable Runge-Kutta methods

In a previous paper it was shown that for a class of semi-linear problems many high order Runge-Kutta methods have order of optimalB-convergence one higher than the stage order. In this paper we show that for the more general class of nonlinear dissipative problems such as result holds only for a small class of Runge-Kutta methods and that such methods have at most classical order 3.     

A note onB-stability of Runge-Kutta methods

Summary Burrage and Butcher [1, 2] and Crouzeix [4] introduced for Runge-Kutta methods the concepts ofB-stability,BN-stability and algebraic stability. In this paper we prove that for any irreducible Runge-Kutta method these three stability concepts are equivalent.Chapters 1–3 of this article have been written by the second author, whereas chapter 4 has been written by the first author     

An algorithm to compute a sparse basis of the null space

Summary LetA be a realm×n matrix with full row rankm. In many algorithms in engineering and science, such as the force method in structural analysis, the dual variable method for the Navier-Stokes equations or more generally null space methods in quadratic programming, it is necessary to compute a basis matrixB for the null space ofA. HereB isn×r, r=n–m, of rankr, withAB=0. In many instancesA is large and sparse and often banded. The purpose of this paper is to describe and test a variation of a method originally suggested by Topcu and called the turnback algorithm for computing a banded basis matrixB. Two implementations of the algorithm are given, one using Gaussian elimination and the other using orthogonal factorization by Givens rotations. The FORTRAN software was executed on an IBM 3081 computer with an FPS-164 attached array processor at the Triangle Universities Computing Center and on a CYBER 205 vector computer. Test results on a variety of structural analysis problems including two- and three-dimensional frames, plane stress, plate bending and mixed finite element problems are discussed. These results indicate that both implementations of the algorithm yielded a well-conditioned, banded, basis matrixB whenA is well-conditioned. However, the orthogonal implementation yielded a better conditionedB for large, illconditioned problems.The research by these authors was supported by the U.S. Air Force under grant No. AFOSR-83-0255 and by the National Science Foundation under grant No. MCS-82-19500The research by these authors was supported by the Applied Mathematical Sciences Program of the U.S. Department of Energy, under contract to Martin Marietta Energy Systems, Inc.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

A- andB-stability for Runge-Kutta methods-characterizations and equivalence

Summary Using a special representation of Runge-Kutta methods (W-transformation), simple characterizations ofA-stability andB-stability have been obtained in [9, 8, 7]. In this article we will make this representation and their conclusions more transparent by considering the exact Runge-Kutta method. Finally we demonstrate by a numerical example that for difficult problemsB-stable methods are superior to methods which are onlyA-stable.Talk, presented at the conference on the occasion of the 25th anniversary of the founding ofNumerische Mathematik, TU Munich, March 19–21, 1984     

Derivative free multipoint iterative methods for simple and multiple roots

A one-parameter family of derivative free multipoint iterative methods of orders three and four are derived for finding the simple and multiple roots off(x)=0. For simple roots, the third order methods require three function evaluations while the fourth order methods require four function evaluations. For multiple roots, the third order methods require six function evaluations while the fourth order methods require eight function evaluations. Numerical results show the robustness of these methods.     

Finite difference methods and their convergence for a class of singular two point boundary value problems

Summary We discuss the construction of three-point finite difference approximations and their convergence for the class of singular two-point boundary value problems: (x y)=f(x,y), y(0)=A, y(1)=B, 0<<1. We first establish a certain identity, based on general (non-uniform) mesh, from which various methods can be derived. To obtain a method having order two for all (0,1), we investigate three possibilities. By employing an appropriate non-uniform mesh over [0,1], we obtain a methodM ₁ based on just one evaluation off. For uniform mesh we obtain two methodsM ₂ andM ₃ each based on three evaluations off. For =0,M ₁ andM ₂ both reduce to the classical second-order method based on one evaluation off. These three methods are investigated, theirO(h ²)-convergence established and illustrated by numerical examples.     

Algebraic connections between the least squares and total least squares problems

Summary In this paper the closeness of the total least squares (TLS) and the classical least squares (LS) problem is studied algebraically. Interesting algebraic connections between their solutions, their residuals, their corrections applied to data fitting and their approximate subspaces are proven.All these relationships point out the parameters which mainly determine the equivalences and differences between the two techniques. These parameters also lead to a better understanding of the differences in sensitivity between both approaches with respect to perturbations of the data.In particular, it is shown how the differences between both approaches increase when the equationsAXB become less compatible, when the length ofB orX is growing or whenA tends to be rank-deficient. They are maximal whenB is parallel with the singular vector ofA associated with its smallest singular value. Furthermore, it is shown how TLS leads to a weighted LS problem, and assumptions about the underlying perturbation model of both techniques are deduced. It is shown that many perturbation models correspond with the same TLS solution.Senior Research Assistant of the Belgian N.F.W.O. (National Fund of Scientific Research)     

Sur laB-stabilité des méthodes de Runge-Kutta

Résumé Dans cet article, nous modifions légèrement la définition de laB-stabilité donnée par J.C. Butcher [1] afin qu'elle s'applique à une plus large classe d'équations différentielles et nous donnons des caractérisations simples de cette propriété.

---

OnB-stability of the methods of Runge Kutta

Summary In this paper, we slightly modify the definition ofB-stability of Butcher [1], so as to cover a wider class of differential equations, and we give simple characterizations of this property.

     

Preconditioning nonconforming finite element methods for treating Dirichlet boundary conditions. II

Summary This work deals with theH ¹ condition numbers and the distribution of theB _h singular values of the preconditioned operators {B _h ^–1 A _h }_{0, whereA h andB h are finite element discretizations of second order elliptic operators,A andB respectively.B is also assumed to be self-adjoint and positive definite. For conforming finite elements, Parter and Wong have shown that the singular values cluster in a positive finite interval. Goldstein also has derived results on the spectral distribution ofB h ^–1 A h using a different approach. As a generalization of the results of Parter and Wong, the current work includes nonconforming finite element methods which deal with Dirichlet boundary conditions. It will be shown that, in this more general setting, the singular values also cluster in a positive finite interval. In particular, if the leading part ofB is the same as the leading part ofA, then the singular values cluster about the point {1}. Two specific methods are given as applications of this theory. They are the penalty method of Babuka and the method of nearly zero boundary conditions of Nitsche. Finally, it will be shown that the same results can be proven by an approach generalized from the work of Goldstein.This research was supported by the National Science Foundation under grant number DMS-8913091.}     

The Chebyshev solution of the linear matrix equationAX+YB=C

Summary In this paper we investigate the properties of the Chebyshev solutions of the linear matrix equationAX+YB=C, whereA, B andC are given matrices of dimensionsm×r, s×n andm×n, respectively, wherer ands. We separately consider two particular cases. In the first case we assumem=r+1 andn=s+1, in the second caser=s=1 andm, n are arbitrary. For these two cases, under the assumption that the matricesA andB are full rank, we formulate necessary and sufficient conditions characterizing the Chebyshev solution ofAX+YB=C and we give the formulas for the Chebyshev error. Then, we propose an algorithm which may be applied to compute the Chebyshev solution ofAX+YB=C for some particular cases. Some numerical examples are also given.     

On the order of composite multistep methods for ordinary differential equations

Summary In this paper, a general class ofk-step methods for the numerical solution of ordinary differential equations is discussed. It is shown that methods with order of consistencyq have order of convergence (q+1) if a very simple condition is satisfied. This result gives a new aspect to previous results of Spijker; it also serves as a starting point for a new theory of cyclick-step methods, completing an approach of Donelson and Hansen. It facilitates the practical determination of high-order cyclick-step methods, especially of stiffly stable,k-step methods.     

Applications of fixed-point methods to discrete variational and quasi-variational inequalities

Summary In this paper, discrete analogues of variational inequalities (V.I.) and quasi-variational inequalities (Q.V.I.), encountered in stochastic control and mathematical physics, are discussed.It is shown that those discrete V.I.'s and Q.V.I.'s can be written in the fixed point formx=Tx such that eitherT or some power ofT is a contraction. This leads to globally convergent iterative methods for the solution of discrete V.I.'s and Q.V.I.'s, which are very suitable for implementation on parallel computers with single-instruction, multiple-data architecture, particularly on massively parallel processors (M.P.P.'s).This research is in part supported by the U.S. Department of Energy, Engineering Research Program, under Contract No. DE-AS05-84EH13145