Monotonieeigenschaften des Steffensen-Verfahrens

Steffensen's method is slightly generalized by introducing a real parameter. In this way one can get different monotonicity properties, depending on the choice of this parameter. These monotonicity statements give the possibility of bracketing the solution of a given problem. In a special case they even ensure the convergence and the existence of a solution. Furthermore there are given sufficient conditions, which show that Steffensen's method converges at least as quickly as Newton's method. A numerical example shows the efficiency of the theorems and compares Steffensen's and Newton's method.

     

Approximants de Padé-Hermite 2ème partie: programmation

Summary In this second paper we propose an algorithm for the construction of the -tables and of the Padé-Hermite tables [3]. Then we present some numerical applications.

     

Asymptotische Entwicklungen für Eigenwerte und Eigenvektoren bei der Approximation parameternichtlinearer Eigenwertaufgaben

Summary In order to apply extrapolation processes to the numerical solution of eigenvalue problems depending nonlinear on a parameter the existence of asymptotic expansions for eigenvalues and eigenvectors is studied. At the end of the paper some numerical examples are given.

     

Über die Effektivität einiger nichtlinearer Verfahren bei der numerischen Behandlung steifer Differentialgleichungssysteme

Summary The stability and accuracy of some explicit nonlinear methods for the numerical integration of stiff systems of ordinary differential equations are investigated. It is shown, that in the general case they can produce the essential error. The special class of stiff systems is singled out, for which these methods are highly efficient. Some numerical results are also presented.

     

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.     

Numerische Quadratur bei Projektionsverfahren

Summary In this paper we investigate the influence of the numerical quadrature in projection methods. In particular we derive conditions for the order of the quadrature formulas in finite element methods under which the order of convergence is not perturbed. It seems that this question has been discussed only for the Ritz method. There is an essential difference between this method on one side and the Galerkin and least squares methods on the other side. The methods using numerical integration are only in the latter case still projection methods. The resulting conditions for the quadrature formulas are often much weaker than those for the Ritz method. Numerical examples using cubic splines and polynomials show that the conditions derived are realistic. These examples also allow the comparison of some projection methods.

     

Approximants de pade-hermite. 1ère partie: theorie

Summary We present in this first paper a generalization of Padé approximants which gives us as particular cases Shafer's and Baker'sD-log approximants.First we define these approximants following an old idea of Hermite, then we prove some fundamental properties for their constructions.

     

Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen

Summary A numerical method for constrained approximation problems in normed linear spaces is presented. The method uses extremal subgradients of the norms or sublinear functionals involved in the approximation problem considered. Under certain weak assumptions the convergence of the method is proved. For various normed spaces hints for practical realization are given and several numerical examples are described.

---

Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen

     

Baryzentrische Formeln zur trigonometrischen Interpolation (II) Stabilität und Anwendung auf die Fourieranalyse bei ungleichabständigen Stützstellen

Summary In Part I we have presented barycentric formulas for trigonometric interpolation. Here we show that these formulas make it possible to calculate Fourier coefficients easily and efficiently. The only inconvenience is their instability when the number of interpolating points becomes large; this instability can be avoided in a special case. The formulas can be used to approximate the inverse of a periodic function, for instance of the boundary correspondence function in numerical conformal mapping.

---

Résumé Dans la première partie, nous avons présenté des formules barycentriques pour l'interpolation trigonométrique. Ici, nous montrons que ces formules permettent une analyse de Fourier particuliérement simple et efficiente; leur seul inconvénient réside dans leur instabilité lorsque le nombre de noeuds croît, instabilité qui peut être évitée dans un cas particulier. Elles sont applicables à l'approximation de l'inverse d'une fonction périodique, par exemple de la fonction de correspondance des frontières en application conforme numérique.

     

Estimation de l'erreur d'interpolation d'Hermite dans ℝ n

Summary This paper is devoted to study the Hermite interpolation error in an open subset of ⁿ .It follows a previous work of Arcangeli and Gout [1]. Like this one, it is based principally on the paper of Ciarlet and Raviart [7].We obtain two kinds of the Hermite interpolation error, the first from the Hermite interpolation polynomial, the other from approximation method using the Taylor polynomial.Finally in the last part we study some numerical examples concerning straight finite element methods: in the first and second examples, we use finite elements which are included in the affine theory, but it is not the case in the last example. However, in this case, it is possible to refer to the affine theory by the way of particular study (cf. Argyris et al. [2]; Ciarlet [6]; ciarlet and Raviart [7]; Raviart [11]).

     

Die mehrstellenformeln für den Laplaceoperator

Summary Difference methods for the numerical solution of linear partial differential equations may often be improved by using a weighted right hand side instead of the original right hand side of the differential equation. Difference formulas, for which that is possible, are called Mehrstellenformeln or Hermitian formulas. In this paper the Hermitian formulas for the approximation of Laplace's operator are characterized by a very simple condition. We prove, that in two-dimensional case for a Hermitian formula of ordern at leastn+3 discretization points are necessary. We give examples of such optimal formulas of arbitrary high-order.

     

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.

     

Über die Existenz von unendlich vielen periodischen Lösungen einer einfachen Temperaturregelung

Zusammenfassung Eine räumliche Temperaturregelung wird hier durch eine parabolische Differentialgleichung mit gekoppelten Randbedingungen modelliert. Um den bekannten Existenzsatz anwenden zu können, wird die Gleichung durch eine Störung regularisiert. Wegen der Kompaktheit der Menge der Lösungsfunktionen von gestörten Gleichungen existieren in dieser Menge Häufungspunkte. Mit Hilfe des strengen Maximum-Prinzips zeigt man, daß solche Häufungspunkte die Lösungen der ungestörten Gleichung sind. Die damit erzielte Existenzaussage wird numerisch bekräftigt.

---

On the existence of an infinite number of periodic solutions for a simple temperature control

Summary A parabolic differential equation with coupled boundary conditions models a temperature-control-system in the one-dimensional space. In order to use a known existence theorem the equation is regularized by a perturbation. The set of solution functions of the perturbed equations is compact. Accumulation points of this set are solutions of the equation because of the strictly maximum principle. This proposition is confirmed with a numerical example.

     

Ein kurze Anmerkung zur Romberg-Integration

Summary Subject to rather mild assumptions on the integrand, the Romberg table (theT-table) and the modified Romberg table (theU-table) yield asymptotically upper and lower bounds for the value of the integral, and the convergence of the columns of the two tables is asymptotically monotone. This is verified for arbitrary sequences of step sizes satisfying the usual condition of convergence for Romberg integration.

     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

A family of multi-point iterative methods for solving systems of nonlinear equations

We extend to n$n$-dimensional case a known multi-point family of iterative methods for solving nonlinear equations. This family includes as particular cases some well known and also some new methods. The main advantage of these methods is they have order three or four and they do not require the evaluation of any second or higher order Fréchet derivatives. A local convergence analysis and numerical examples are provided.     

Zur effektiven Lösung von booleschen,quadratischen Optimierungsproblemen

Zusammenfassung Es wird die zum booleschen, quadratischen Optimierungsproblem duale Aufgabe untersucht. Ihr optimaler Zielfunktionswert liefert wesentlich schärfere Schranken für den branch and bound Prozeß als die bisher verwendeten.

---

On the efficient treatment of the boolean quadratic programming problem

Summary The dual of the boolean quadratic programming problem is considered. The optimal value of their objective function gives bounds for the branch and bound process, which seem to be better then known from other autors.

     

Une représentation intégrale de l'erreur d'interpolation

Résumé La représentation intégrale de l'erreur d'interpolation dans le cas à une ou plusieurs variables est présentée comme une généralisation de la méthode du Wronskien dans le cas à une variable. Ceci est basé sur la construction d'un système d'opérateurs différentiels associé aux fonctions de base du procédé d'interpolation et sur le noyau de Neumann.

---

An integral representation of interpolation error

The integral representation of interpolation error for one or several variables is considered as a generalization of Wronskien method for one variable. This is based on the construction of a system of differential operators associated with the basis interpolated functions and on the Neumann's Kernel.

     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

Sur la forme des composantes connexes du complémentaire de la courbe brownienne plane

Résumé Nous nous proposons d'étudier la forme des petites composantes connexes du complémentaire de la trajectoire brownienne plane. Nous montrons l'existence d'une loi limite de cette forme. De plus, nous obtenons un théorème limite qui montre que la donnée de l'ensemble des composantes connexes correspondant à une seule trajectoire suffit pour décrire cette loi.

---

Summary We study the shape of the small connected components of the complement of a 2-dimensional Brownian path. We show the existence of an asymptotic law for this shape. Moreover, we prove a limit theorem that shows that the family of all the connected components of the complement of a single path contains all the information about this law.