J. Herzberger (ed.) Inclusion Methods for Nonlinear Problems With Applications in Engineering, Economics and Physics Computing Supplement 16 Springer-Verlag Wien GmbH Univ.-Prof. Dr. Jiirgen Herzberger Faculty of Mathematics, University of Oldenbourg, Oldenbourg, Germany This work is subject to copyright. AlI rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machines or similar means, andstorage in data banks. Product Liability: The publisher can give no guarantee for all the information contained in this book. This does also refer to information about drug dosage and application thereof. In every individual case the respective user must check its accuracy by consulting other pharmaceutical literature. The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. © 2003 Springer-Verlag Wien Originally published by Springer-Verlag Wien New York in 2003 Typesetting: Scientific Publishing Services (P) Ltd., Madras, India Printed on acid-free and chlorine-free bleached paper SPIN: 10879532 With 24 Figures CIP-data applied for ISSN 0344~8029 ISBN 978-3-211-83852-5 ISBN 978-3-7091-6033-6 (eBook) DOI 10.1007/978-3-7091-6033-6 Foreword This workshop was organized with the support of GAMM, the International Association of Applied Mathematics and Mechanics, on the occasion of J. Herzberger's 60th birthday. GAMM is thankful to him for all the time and work he spent in the preparation and holding of the meeting. The talks presented during the workshop and the papers published in this volume are part of the field of Verification Numerics. The important subject is fostered by GAMM already since a number of years, especially also by the GAMM FachausschuB (special interest group) "Rechnerarithmetik und Wissenschaft liches Rechnen". Karlsruhe, Dezember 2001 GiHz Alefeld (President of GAMM) Preface At the end of the year 2000, about 23 scientists from many countries gathered in the beautiful city of Munich on the occasion of the International GAMM Workshop on "Inclusion Methods for Nonlinear Problems with Applications in Engineering, Economics and Physics" from December 15 to 18. The purpose of this meeting was to bring together representatives of research groups from Austria, Bulgaria, China, Croatia, Germany, Japan, Russia, Ukraine and Yugoslavia who in a wider sense work in the field of calculating numerical solutions with error-bounds. Most of those participants have already known each other from earlier occasions or closely cooperated in the past. Representatives from three Academies of Sciences were among the speakers of this conference: from the Bulgarian Academy, the Russian Academy and the Ukrainian Academy of Sciences. The contributions covered a wide field of topics with emphasis on nonlinear problems and possible implications to the solution of practical problems. The pleasant atmosphere of the location of the conference, the Adolf-Kolping-House in the very center of the city, was stimulating many direct contacts among the participants and gave them the opportunity for intensive discussions and scientific exchange. This volume, extended by some contributions from authors who belong to these research groups but who were not able to attend the meeting due to the restricted number of invited guests, is intended to inform a broader audience about the result and scientific progress made in this area by a number of com petent members of the international scientific community. I would like to express my sincere thanks to all of those who have contributed to this volume and to all the numerous referees who helped to keep this volume on a high level. I am also grateful to my colleague Professor Dr. R. Albrecht, Innsbruck, for drawing the attention of Springer-Verlag in Vienna to this con ference proceedings. My special thanks go to Ms. Silvia Schilgerius and Mag. Wolfgang Dollhaubl from the Springer-Verlag in Vienna who helped to make the appearance of this special volume possible and showed patience for this project. Last but not least, I would like to thank Ms. Theresia Meyer from the University of Olden bourg for promptly handling all the correspondence connected with my editorial work on this volume. Oldenbourg, October 2002 Jurgen llerzberger List of Participants of the International GAMM-Workshop on "Inclusion Methods for Nonlinear Problems with Applications in Engineering, Economics and Physics" Munich and OberschleiBheim, December 15-18, 2000 Prof. Dr. R. Albrecht, Innsbruck (Austria) Prof. Dr. G. Alefeld, Karlsruhe (Germany) Prof. Dr. A. Andreev, Sofia (Bulgaria) Dr. L. Atanassova, Munich (Germany) Acad. Dr. F.L. Chernousko, Moscow (Russia) Dr. H. Fischer, Munich (Germany) Prof. Dr. V. Hari, Zagreb (Croatia) Prof. Dr. G. Heindl, Wuppertal (Germany) Prof. Dr. J. Herzberger, Oldenburg (Germany) Prof. Dr. V. Hristov, Sofia (Bulgaria) Prof. Dr. G. Iliev, Sofia (Bulgaria) Prof. Dr. U. Kulisch, Karlsruhe (Germany) Prof. Yong-xiang Ling, Xi'an (PR China) Prof. Dr. G. Mayer, Rostock (Germany) Prof. Shin'ichi Oishi, Tokyo (Japan) Prof. K. Okomura, Kyoto (Japan) Prof. Dr. M. Petkovic, Nis (Yugoslavia) Prof. Dr. Lj. Petkovic, Nis (Yugoslavia) Prof. Dr. N. Popivanov, Sofia (Bulgaria) Acad. Dr. V.L. Rvachev, Kharkov (Ukraine) Prof. Dr. S. Smelyakov, Kharkov (Ukraine) Prof. Dr. Yu. Stoyan, Kharkov (Ukraine) Prof. Dr. Shen Zuhe, Nanjing (PR China) Contents Alefeld, G., Kreinovich, V., Mayer, G.: On Symmetric Solution Sets Atanassova, L., Kyurkchiev, N., Yamamoto, T.: Methods for Computing all Roots of a Polynomial Simultaneously - Known Results and Open Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Detmers, F., Herzberger, J.: Narrow Bounds for the Effective Rate of Return Concerning a Special Problem for Annuities . . . . . . . . . . . . . . . 43 Fischer, H.: Algorithmic Differentiation with Intervals . . . . . . . . . . . . . 45 Frischmuth, K., Tsybulin, V. G.: Computation of a Family of Non- co symmetrical Equilibria in a System of Nonlinear Parabolic Equations. 67 Hari, V., Matejas, J.: Quadratic Convergence of Scaled Iterates by Kogbetliantz Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Heindl, G.: On a Method for Computing Inclusions of Solutions of the Basic GPS Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 107 Herzberger, J., Langer, A.: Construction of Bounds for the Positive Root of a General Class of Polynomials with Applications. . . . . . . . . . . . . . . 121 Kulisch, D.: Rounding Near Zero. . . . . . . . . . . . . . . . . . . . . . . . . . .. 135 Kyurkchiev, N.: A Note on the Convergence of the SOR-like Weierstrass Method .............................................. 143 Langemann, D.: Boundary Regularity Aspects in Solving Contact Problems 151 Ling, Y.-x., Cao, H.-I., Sheng, H.-f.: The Convex-decomposable Operator and Inclusive Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 165 Ogita, T., Oishi, S., Ushiro, Y.: Fast Inclusion and Residual Iteration for Solutions of Matrix Equations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 Petkovic, L. D., Petkovic, M. S.: Schroder-like Methods for the Simulta- neous Inclusion of Polynomial Zeros. . . . . . . . . . . . . . . . . . . . . . . . .. 185 XII Contents Petkovic, L. D., Petkovic, M. S., Zivkovic, D.: Interval Root-finding Methods of Laguerre's Type. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Pop ivanov, N., Popov, T.: Exact Behaviour of Singularities of Protter's Problem for the 3-D Wave Equation. . . . . . . . . . . . . . . . . . . . . . . . . . 213 Smelyakov, S. V.: Construction of Shortest Line of Restricted Curvature in a Non-singly-connected Polygonal Area. . . . . . . . . . . . . . . . . . . . . . .. 237 Computing [Suppl] 16, 1-22 (2002) Computing © Springer-Verlag 2002 On Symmetric Solution Sets G. Alefeld, V. Kreinovich and G. Mayer Abstract Given an n x n interval matrix [A] and an interval vector [b] with n components we present an overview on existing results on the solution set Ssym of linear systems of equations Ax = b with symmetric matrices A E [A] and vectors b E [b]. Similarly we consider the set Esym of eigenpairs associated with the symmetric matrices A E [A]. We report on characterizations of Ssym by means of inequalities, by means of intersection of sets, and by an approach which is generalizable to more general dependencies of the entries. We also recall two methods for enclosing Ssym by means of interval vectors, and we mention a characterization of Esym. AMS Subject Classifications: 65GIO. Keywords: Solution set of linear systems, symmetric solution set of linear systems, eigenpair set, symmetric eigenpair set, linear interval systems, Oettli-Prager theorem. 1. Introduction With this paper we intend to give an overview on existing results for the sym metric solution set Ssym := {x E IRnl Ax = b, A = AT E [AJ, b E [b]}, (1) where [A] is a given n x n interval matrix with [A] = [Af, and [b] is a given interval vector with n components. This set obviously is a subset of the general solution set S := {x E IRnl Ax = b, A E [AJ, bE [b]}, (2) where the restriction A = AT on A E IRnxn is not required. Knowing Sand Ssyrn is particularly interesting in the following situations: (a) Assume that one has to solve a linear system Ax = h on a computer using x floating point arithmetic. Due to rounding errors, the computed result nor mally will not fulfill Ax = h. If L1A E IRnxn, L1b E IRnare given nonnegative tol erances one may view x as an acceptable solution whenever xES with S formed as in (2) with respect to [A] := A + [-L1A, L1AJ, [b] := h + [-L1b, L1b]; in this case x can be interpreted as exact solution of a linear system Ax = b with some A E [AJ, bE [b]. 2 G. Alefeld et al. (b) In contrast to (a), where the linear system is known we assume now that one has to solve a linear system Ax = b where A, b are not given exactly, but they are known to differ from some A E IRnxn, b E IRn by at most LiA E IRnxn and Lib E IRn, respectively (LiA, Lib nonnegative). Then A E [A] := A + [-LiA, LiAJ, bE [b] := b + [-Lib, Lib]. Compute a solution x* of Ax = b. Since x* E S one can accept x* as a good approximation for the unknown solution of Ax = b. This situation can occur due to - conversion errors (from decimal to binary or vice versa), - errors in measurements, - errors in adjusting the technical devices. As we shall see Sand Ssym are not so easy to handle. Therefore, enclosures of S and Ssym are important. For S such enclosures can be computed by means of interval arithmetic. Since such methods are contained in textbooks like [1], [20], e.g., we will omit them here. They trivially deliver also enclosures for Ssym s::; S. But there are also methods to enclose Ssym without bounding S at the same time. We will study such methods later on. Although we shall concentrate on Ssym in this paper we will give a short glance at S in order to work out particularities of Ssym. So we start in Sect. 3 with several equivalent statements for xES and list some properties of S. In Sect. 4, we characterize the boundary 8Ssym of Ssym by means of parts of hyperplanes and quadrics. In Sect. 5, we introduce two methods for enclosing Ssym and in Sect. 6, we report on the eigenpair set E := {(xT,.-1f E IRn+11 Ax = Ax, x =f. 0, A E [A]} (3) and the symmetric eigenpair set It turns out that quadrics are needed in order to describe E and algebraic in equalities of order at most three in order to describe Esym. 2. Notations In the sequel we denote intervals in square brackets, i.e., [aJ = [g, aJ, and identify point intervals [a, a] by their unique element omitting the brackets. We assume that the reader is familiar with the elementary rules and basic facts of interval arithmetic as introduced in the first chapters of [1] or [20], e.g. We will write m, IlRn, IlRmxn for the set of real compact intervals, interval vectors with n compo nents and m x n interval matrices, respectively. We apply the notation [AJ = [4,A] = ([aL) = ([gij' aij]) simultaneously for interval matrices and have a similar notation for interval vectors, real vectors and real matrices. An interval matrix [A] is called regular if each A E [A] has this property. By A we denote the midpoint of [AJ, i.e., A := ! (4 + A), and by rad[AJ := ! (A - 4) its radius which we